Если отказаться от использования в действительном многоч­лене двоичной функции переменных в степенях выше первой, то неоднозначность представления двоичных функций в такой фор­ме можно исключить. В связи с этим в дальнейшем говоря о дей­ствительном многочлене двоичной функции, мы будем считать, что переменные его входят в степенях не выше первой

28. Доказательство теоремы об однозначном представлении двоичной функции в виде действительного многочлена.

Имея это в виду , докажем, что любая двоичная функция f(x₁,x₂,…,x_n) од­нозначно представляется в виде следующего действительного мно­гочлена

D_f (x₁,…,x_n)= a₀    … a_1,2,…,nx₁x₂…x_n

где все коэффициенты являются целыми числами.

Покажем, что по таблице двоичной функции однозначно опре­деляются коэффициенты a₀, a_i, a_ij,…, a_1,2,…n ее действительного многочлена. Воспользуемся методом неопределенных коэффици­ентов. Последовательно вычислим значения искомого действитель­ного многочлена на наборе из одних нулей, затем на наборах о одной единицей, затем с двумя , и т.д.. В результате получим

f(0, 0, …, 0)= a₀

f(1, 0, …, 0)= a₀+ a₁

^{………………………………………..}

f(0, 0, …, 0, 1)= a₀+ a_n

f(1, 1, 0, …, 0)= a₀+ a₁+ a₂+ a₁₂

^{……………………………………….….}

f(1, 1, …, 1)= a₀+   … a_12…n

Из первого уравнения находим a₀, из второго a₁, … , из (n+1)-гo уравнения находим а_n , из (n+2)-го – а₁₂ , ... , из последнего находим а_1,2,…,n . Таким образом, значения двоичной функции однозначно определяют коэффициенты многочлена D_f .

29. Понятие вероятностной функции двоичной функции.

Вероятностная функция двоичной функции.

Будем считать, что значения переменных x₁, x₂, …, x_n двоичной функции f(x₁, …, x_n) являются независимыми случайными величина­ми с распределением

P (x_i=1)= P_i

P (x_i=0)= 1-P_i, 0  P_i  1, i[1,n]

Тогда значение функции f(x)=f(x₁, …, x_n) будет случайной величиной, распределение которой определяется значением ве­роятности

P (f(x)=1)= F_f(p₁, p₂, …, p_n)

Функция F_f называется вероятностной функцией двоичной функции f(x) . Легко видеть, что

F_f(p₁, p₂, …, p_n)=

и

P(x=a)=

для a=(a₁, a₂,…, a_n)F₂ⁿ. Поэтому вероятностная функция F_f(p₁, …, p_n) является многочленом от переменных p₁, …, p_n с целыми коэффициентами. Следующее утверждение показывает , что вероятностная функция, рассматриваемая как многочлен, совпадает с дейст­вительным многочленом D_f двоичной функции f(x).

Утверждение. ( О совпадении многочленов F_f и D_f). Для всякой двоичной функции f(x₁, …, x_n) и произвольных чисел p₁,…,p_n, 0  p_i  1, i[1,n] выполняется тождественное равенство:

F_f(p₁, p₂, …, p_n)=D_f(p₁, p₂, …, p_n)

Доказательство. Проведем доказательство индукцией по числу переменных функции f(x). Если n=1, то существует четыре функции: f₀(x₁)0; f₁(x₁)=x₁; f₂(x₁)= f₃(x₁)1. Для них имеем

P(f₀(x₁)=1)=P(0=1)=0

P(f₁(x₁)=1)=P(x₁=1)=p₁

P(f₂(x₁)=1)=P( =1-p₁

P(f₃(x₁)=1)=P(1=1)=1

Допустим теперь, что утверждение верно для всех функций от (n-1) переменной и покажем его справедливость для функ­ции f(x₁,…,x_n) от n переменных. Разложим функцию по первой переменной

f(x₁,…,x_n)=

Положим

f₀=f(0,x₂,…,x_n), f₁=f(1,x₂,…,x_n)

По предположению имеем

;

В силу однозначности представления действительного мно­гочлена двоичной функции , имеем

D_f(x₁,…,x_n)=

В то же время имеем

F_f(p₁,…,p_n)=P(x₁=1)P(f₁=1)+P(x₁=0)P(f₀=1)=

=p₁ =D_f(p₁,…,p_n)

Утверждение доказано.

Согласно доказанному утверждению для следующих элементар­ных функций имеем

P(x₁x2=1)=p₁p₂

P(x₁x₂=1)=p₁+p₂-p₁p₂

P(x₁x₂=1)=p₁+p₂-2p₁p₂

P( )=1-p₁

В случае, когда вероятности p_i, i[1,n] совпадают, вероят­ностную функцию можно вычислить используя табличное задание двоичной функции не вычисляя действительного многочлена. Пусть p₁=p₂=…=p_n=p сгруппируем строки в таблице функции f(x) так, что­бы векторы с одинаковым числом единиц оказались в одной груп­пе. Множество всех векторов с одинаковым числом i единиц называют i-м уровнем, i[1,n]. Все векторы i-го уровня имеют одинаковые вероятности, равные pⁱ(1-p)^n-i, i[1,n]. Поэтому вероятностная функция может быть записана в виде

где b_i - число векторов на i-м уровне, на которых функ­ция f(x) принимает значение "1". Вектор (b₁,…,b_n) называют распределением весов на уровнях функции f(x). Оче­видно

есть число двоичных наборов, на которых функция f(x) принима­ет значение равное "1

Положим p₁=p₂=…=p_n= . Число  показывает, насколь­ко отклоняется от равновероятного случая распределение ар­гументов функции f(x), и его называют преобладанием. Преоб­ладанием для распределения значений двоичной функции на­зывают величину (), где

F_f

Докажите самостоятельно следующее равенство

()= ₁ + ₂ ² + …+_n ⁿ

где - некоторые рациональные коэффициенты.

Равновероятные двоичные функции называются к - выравни­вающими , если ₁=₂=…=_k-1=0, _k0 и, следовательно, для них

()= ^k(_k+_k+1 + …+_n ^n-k)=O( ^k)

В ряде случаев данное понятие используют и в случае раз­личных значений вероятностей p₁,…,p₂. Именно, функцию f(x) называют к -выравнивающей , если в многочлене

F_f(p₁,p₂,…,p_n)=D_f

от переменных ₁,₂, …,_n все одночлены будут иметь степень не меньше к , где определены из равенства =1/2+

30. Доказательство теоремы о равенстве значений вероятностной функции со значением действительного многочлена от вероятностей р₁,р₂,…,р_n.

Утверждение. ( О совпадении многочленов F_f и D_f). Для всякой двоичной функции f(x₁, …, x_n) и произвольных чисел p₁,…,p_n, 0  p_i  1, i[1,n] выполняется тождественное равенство:

F_f(p₁, p₂, …, p_n)=D_f(p₁, p₂, …, p_n)

Доказательство. Проведем доказательство индукцией по числу переменных функции f(x). Если n=1, то существует четыре функции: f₀(x₁)0; f₁(x₁)=x₁; f₂(x₁)= f₃(x₁)1. Для них имеем

P(f₀(x₁)=1)=P(0=1)=0

P(f₁(x₁)=1)=P(x₁=1)=p₁

P(f₂(x₁)=1)=P( =1-p₁

P(f₃(x₁)=1)=P(1=1)=1

Допустим теперь, что утверждение верно для всех функций от (n-1) переменной и покажем его справедливость для функ­ции f(x₁,…,x_n) от n переменных. Разложим функцию по первой переменной

f(x₁,…,x_n)=

Положим

f₀=f(0,x₂,…,x_n), f₁=f(1,x₂,…,x_n)

По предположению имеем

;

В силу однозначности представления действительного мно­гочлена двоичной функции , имеем

D_f(x₁,…,x_n)=

В то же время имеем

F_f(p₁,…,p_n)=P(x₁=1)P(f₁=1)+P(x₁=0)P(f₀=1)=

=p₁ =D_f(p₁,…,p_n)

Утверждение доказано.

Согласно доказанному утверждению для следующих элементар­ных функций имеем

P(x₁x2=1)=p₁p₂

P(x₁x₂=1)=p₁+p₂-p₁p₂

P(x₁x₂=1)=p₁+p₂-2p₁p₂

P( )=1-p₁

В случае, когда вероятности p_i, i[1,n] совпадают, вероят­ностную функцию можно вычислить используя табличное задание двоичной функции не вычисляя действительного многочлена. Пусть p₁=p₂=…=p_n=p сгруппируем строки в таблице функции f(x) так, что­бы векторы с одинаковым числом единиц оказались в одной груп­пе. Множество всех векторов с одинаковым числом i единиц называют i-м уровнем, i[1,n]. Все векторы i-го уровня имеют одинаковые вероятности, равные pⁱ(1-p)^n-i, i[1,n]. Поэтому вероятностная функция может быть записана в виде

где b_i - число векторов на i-м уровне, на которых функ­ция f(x) принимает значение "1". Вектор (b₁,…,b_n) называют распределением весов на уровнях функции f(x). Оче­видно

есть число двоичных наборов, на которых функция f(x) принима­ет значение равное "1

Положим p₁=p₂=…=p_n= . Число  показывает, насколь­ко отклоняется от равновероятного случая распределение ар­гументов функции f(x), и его называют преобладанием. Преоб­ладанием для распределения значений двоичной функции на­зывают величину (), где

F_f

Докажите самостоятельно следующее равенство

()= ₁ + ₂ ² + …+_n ⁿ

где - некоторые рациональные коэффициенты.

Равновероятные двоичные функции называются к - выравни­вающими , если ₁=₂=…=_k-1=0, _k0 и, следовательно, для них

()= ^k(_k+_k+1 + …+_n ^n-k)=O( ^k)

В ряде случаев данное понятие используют и в случае раз­личных значений вероятностей p₁,…,p₂. Именно, функцию f(x) называют к -выравнивающей , если в многочлене

F_f(p₁,p₂,…,p_n)=D_f

от переменных ₁,₂, …,_n все одночлены будут иметь степень не меньше к , где определены из равенства =1/2+

Спектральное разложение двоичных функций.

31. Доказательство ортогональности функций { (-1)^(а,х), аⁿ

Сопоставим каждому двоичному вектору a= (a₁, …, a_n)Î F₂ⁿ линейную двоичную функцию (а, x)= a₁x₁Å …Å a_nx_n , и определим функции

Покажите , что 2ⁿ функций вида (-1)^(a,x) образуют ортогональную систему.

32. Доказательство теоремы о представлении двоичной функции рядом Фурье.Представление булевых и псевдобулевых функций через базисы линейных пространств.

Утверждение. (О разложении в ряд Фурье). Для. всякой дво­ичной функции имеется единственное разложение вида

f(x)= f (x₁, …, x_n)=

где C_a^f - рациональные числа.