Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
138 собственных подмножеств Xj И Xj множества U имеет место
па -а а
KX1.,X7-)= , , (6.21)
где ах. - число элементов подмножества Xi, ах.х - число элементов
подмножества Xj г> Xj.
Легко убедиться также, что имеют место / (X,, X,) = 1 и
r(X1, Xj) = КXj , Xi) = -r(X,., X,), (6.22)
т.е. г(Х„ Ху) является симметричной мерой подобия подмножеств Xi И Xj. Заметим, что линейное повторение произвольного обыкновенного подмножества X, совпадает с самим этим подмножеством, а линейное
дополнение - с обычным его дополнением Xi. При этом наличие элемента Xj во множестве радиусов-векторов типа л* предопределяет наличие в этом же множестве радиуса-вектора - л/, соответствующего подмножеству Xj.
Прежде чем приступить к формулировке и доказательству дискретных аналогов теорем транзитивности и синонимии, приведем доказательство одного соотношения, являющегося обобщением теоремы сложения, которой, как и ее обобщением, будем пользоваться ниже.
Обобщение теоремы сложения
Известная теорема сложения гласит [6]:
І C''Ctl = Cl (6-23)
ч=о
Покажем сначала, что имеет место
а , „ к
1 </СаС!-а = I CaCl1lAkU),
(6.54)
,=0 /=I
где
Mi)= І Cjtk(- 1Г'. і= і
Представим выражение qk в виде суммы
Чк = I МОП (q-j). (6.25)
/=I J=о
Подставляя здесь поочередно q = 1,2, ...,к, относительно ак(і) полу-
139
ГЛАВА 5 чим систему линеииых уравнении, решение которой приводит к
MO = ^i (-IV+fC/. (6.26)
'!/=I
Путем очевидных преобразований отсюда, с учетом (6.25), получим: QkC4a = І Qk(I)C4a П (q-j)= І СаС'а_\Ак(1), (6.27)
і'=1 / = O /=1
где
At(i) = а,(/)/!= І С/Л-іГ'. (6.28)
/=1
С учетом (6.27) имеем:
І QkC4aCll= І І Cucll\cl<<Ak(I) =
4=0 q=0 / = 1
= I CaAk(I) J C^1Ctl (6.29)
/ = I q=0
Введя новую переменную z = q - і и пользуясь теоремой сложения (6.23), получим:
S = X Ca_jCfH_i)_(a_i) = cf_]. (6.30)
<)=0 Z=-I
Подставляя этот результат в (6.29), приходим к (6.24). Из (6.24), (6.25) и (6.28) легко получить соотношение
І Ciclz4aC4 = с;cf:;, (6.24а)
которое при / = 0 совпадает с (6.23). Отсюда, как и, впрочем, из (6.24), легко получить:
? qclcll=acll (6.31)
ч=о
X я2CqaClya = а(" ~" ~?+a?) c„?:22. (6.32)
</=0 P-I
Перейдем к доказательству дискретных аналогов утверждений и теорем, рассмотренных в предыдущем разделе. Будем рассматривать множество V, элементами которого служат 2" - 2 точки - все вершины //-мерного единичного куба за исключением точек 0(0, 0, ..., 0) и ?(1, 1, ..., 1). Напомним, что это точки - отображения в //-мерном пространстве всех возможных собственных подмножеств Xi универсального множества U.
140 Утверждение 3 (дискретный аналог утверждения /).
Пусть X - случайная точка, имеющая равномерное распределение на элементах множества V, a Y0 - произвольный фиксированный элемент этого множества. Тогда имеют место:
a) M(r(X, Y0)) = О (6.33)
б) М(г\Х, У,,)) = D(r(X, Y0)) = 1 Kn - 1), (6.34)
или для радиусов-векторов х = X* / I А" I и у0 = У0 / ІУ0 I
в) M(CosCvyn)) = 0, (6.33а)
г) M(Cos2Cvy0)) = D(CosCvy0)) = Щп - 1). (6.34а)
Справедливость пункта (а) или. что то же самое, пункта (в) непосредственно следует из симметричности распределения случайной величины г(Х, У0) = Cos(Xy0), в чем легко убедиться из (6.22).
Для доказательства пункта (б) или, что то же самое, пункта (г), пользуемся соотношениями (6.23), (6.31) и (6.32). Покажем, что (6.34) имеет место при произвольном фиксированном значении ах, что, очевидно, будет достаточным для утверждения (6.34) в общем случае, т.е. при равномерном распределении случайной точки X на всех элементах множества V.
Из (6.21) с учетом (6.23), (6.31), (6.32) и (6.33) получим:
M(r2(XJ0)) = D(r(X, У0)) =
^ , ч/ Ч lU,., n-u„.
С C=OaA0{п-ах)(п-а}Ь) ^ n^"
аха (п-ах(п-а )С"*
п2 f а2 Са'тС"х~"Щ) -
^ -п<) «v,, i-u41 V й«о=0
л
-2nara.. X агг С, С,.,, +a a ? Crl llCl. „
* >0 _„ -1^II V() "">() х >0 V() " "чі
«П(,-и "vvu
п- I
Замечание к утверждению 3.
Из соображений симметрии легко убедиться, что утверждение 3 остается в силе при замене фиксированной точки Уд случайной точкой У, имеющей произвольное независимое от X распределение на элементах множества V.
141
ГЛАВА 5 Утверждение 4.
Пусть X - случайная точка, имеющая равномерное распределение на элементах множества V, определенных заданным значением r(X, Z0), где Z0- произвольный фиксированный элемент этого множества. Тогда для точек j и Z0, соответствующих X и Z0, имеет место
М(х - Пр.(Гг) = 0. (6.35)
Из (6.21) следует, что заданное значение r(X, Z0) в общем случае может быть достигнуто при различных парах значений ах,() и ах. Покажем, что для произвольной фиксированной пары значений ах:{) и ах имеет место М(х - Прз^А') = 0, что, очевидно, является достаточным условием для утверждения 4 в общем случае. Для удобства изложения в дальнейшем координатные представления «-мерных векторов будем рассматривать как соответствующие «-разрядные коды.
Будем различать так называемые зоны нулей и единиц, включающие разряды, где код вектора Z0 содержит соответственно нули и единицы. Значения каждого разряда кода вектора Z0 в этих зонах соответственно равны
