Изменения

'''Полином Жегалкина''' (англ. ''Zhegalkin polynomial'') — полином с коэффициентами вида <tex>0</tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления [[Определение булевой функции|функций булевой логики]]. Полином Жегалкина имеет следующий вид:

<tex>P = a_{000...000\ldots000} \oplus a_{100...0\ldots0} x_1 \oplus a_{010...0\ldots0} x_2 \oplus ... \ldots \oplus a_{00...01\ldots01} x_n \oplus a_{110...0\ldots0} x_1 x_2 \oplus ... \ldots \oplus a_{00...011\ldots011} x_{n-1} x_n \oplus ... \ldots \oplus a_{11..1\ldots1} x_1 x_2 ... \ldots x_n </tex>

Исходя из этого, система функций <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex> является полной, так как в ней:

{| class="wikitable" style="width:8cm" border="1"|-align="center" bgcolor=#Не сохраняет EEEEFF !<tex>x_0</tex>||<tex>x_1</tex>||<tex>\ldots</tex>||<tex>x_n</tex>|<tex>1</tex>||<tex>\land</tex>||<tex>\oplus</tex>|-align="center" !<tex>0</tex>: ||<tex>0</tex>||<tex>\ldots</tex>||<tex>0</tex>|<tex>1</tex>||<tex>0</tex>||<tex>0</tex>|-align="center" !<tex>1</tex>||<tex>0</tex>||<tex>\ldots</tex>||<tex>0</tex>|<tex>1</tex>||<tex>0</tex>||<tex>1</tex>|-align="center" !<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>|<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>|-align="center" !<tex>1</tex>||<tex>1</tex>||<tex>\ldots</tex>||<tex>1</tex>|<tex>1</tex>||<tex> 1 </tex>;||<tex>0</tex>|-align="center" !colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#Не сохраняет .D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Сохраняет 0]]|<tex>0</tex>||<tex>1</tex>: ||<tex> \oplus 1</tex>;|-align="center" !colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#Нелинейна: .D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Сохраняет 1]]|<tex>1</tex>||<tex>1</tex>||<tex> \wedge 0</tex>;|-align="center" !colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#Немонотонна: .D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Самодвойственная]]|<tex>0</tex>||<tex>0</tex>||<tex> \oplus 0</tex>;|-align="center" !colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#Несамодвойственны: .D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Монотонная]]|<tex>1</tex>||<tex> \wedge, \oplus, 1 </tex>||<tex>0</tex>|-align="center" !colspan="4"|[[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Линейная]]|<tex>1</tex>||<tex>0</tex>||<tex>1</tex>|}

Пусть для функции <tex>f(x_1,x_2,..\ldots,x_n)</tex> задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что <tex> a \oplus 1 = \bar{a}</tex>, а <tex> a \oplus 0 = a</tex>. За каждую подстановку находим только один коэффициент.

{| class="wikitable" style="width:8cm" border="1" |-

!class="dark" style="font-weight:normal"| <tex>x_2</tex> !class="dark" style="font-weight:normal"| <tex>x_3</tex> !class="dark" style="font-weight:normal"| <tex>x_4</tex>

<tex>f(1,0,0,0) = a_{0000} \oplus a_{1000} = 1 \Rightarrow ,</tex> следовательно <tex>a_{1000} = 1</tex>

<tex>f(0,1,0,0) = a_{0000} \oplus a_{0100} = 0 \Rightarrow ,</tex> следовательно <tex>a_{0100} = 0</tex>

<tex>f(0,0,1,0) = a_{0000} \oplus a_{0010} = 0 \Rightarrow ,</tex> следовательно <tex> a_{0010} = 0</tex>

<tex>f(0,0,0,1) = a_{0000} \oplus a_{0001} = 0 \Rightarrow ,</tex> следовательно <tex> a_{0001} = 0</tex>

<tex>f(1,1,0,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{1100} = 1 \Rightarrow ,</tex> следовательно <tex> a_{1100} = 0</tex>

<tex>f(1,0,1,0) = a_{0000} \oplus a_{1000} \oplus a_{01000010} \oplus a_{1010} = 0 \Rightarrow , </tex> следовательно <tex> a_{1010} = 1</tex>

<tex>f(1,0,0,1) = a_{0000} \oplus a_{1000} \oplus a_{01000001} \oplus a_{1001} = 0 \Rightarrow , </tex> следовательно <tex> a_{1001} = 1</tex>

<tex>f(0,1,1,0) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0110} = 1 \Rightarrow , </tex> следовательно <tex> a_{0110} = 1</tex>

<tex>f(0,1,0,1) = a_{0000} \oplus a_{0100} \oplus a_{0001} \oplus a_{0101} = 0 \Rightarrow , </tex> следовательно <tex> a_{0101} = 0</tex>

<tex>f(0,0,1,1) = a_{0000} \oplus a_{0010} \oplus a_{0001} \oplus a_{0011} = 0 \Rightarrow , </tex> следовательно <tex> a_{0011} = 0</tex>

<tex>f(1,1,1,0) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{1100} \oplus a_{1010} \oplus a_{0110} \oplus a_{1110} = 1 \Rightarrow , </tex> следовательно <tex> a_{1110} = 0</tex>

<tex>f(1,1,0,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0001} \oplus a_{1100} \oplus a_{1001} \oplus a_{0101} \oplus a_{1101} = 0 \Rightarrow , </tex> следовательно <tex> a_{1101} = 0</tex>

<tex>f(1,0,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0010} \oplus a_{0001} \oplus a_{1010} \oplus a_{1001} \oplus a_{0011} \oplus a_{1011} = 1 \Rightarrow , </tex> следовательно <tex> a_{1011} = 0</tex>

<tex>f(0,1,1,1) = a_{0000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{0111} = 0 \Rightarrow , </tex> следовательно <tex> a_{0111} = 1</tex>

<tex>f(1,1,1,1) = a_{0000} \oplus a_{1000} \oplus a_{0100} \oplus a_{0010} \oplus a_{0001} \oplus a_{1100} \oplus a_{1010} \oplus a_{1001} \oplus a_{0110} \oplus a_{0101} \oplus a_{0011} \oplus a_{1110} \oplus a_{1101} \oplus a_{1011} \oplus a_{0111} \oplus a_{1111} = 0 \Rightarrow , </tex> следовательно <tex> a_{1111} = 1</tex>

Этот способ основан на том, что <tex> X \oplus 1 = \bar{X} </tex>. Если функция задана в виде ДНФ, то можно сначала убрать дизъюнкцию, используя правило Де-де Моргана, а все отрицания заменить прибавлением единицы по модулю два, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю (так как <tex> X \oplus X = 0 </tex>), а нечетное число одинаковых слагаемых равно одному такому слагаемому. Либо же можно заменить дизъюнкцию по следующему правилу:  <tex> A \lor B = AB \oplus A \oplus B </tex> &nbsp; <tex> (1) </tex>.

# Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от <tex>000...00 \ldots00</tex> до <tex>111...11\ldots11</tex>.

# Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке <tex>111 </tex> соответствует член <tex>ABC</tex>, ячейке <tex>101 </tex> — член <tex>AC</tex>, ячейке <tex>010 </tex> — член <tex>B</tex>, ячейке <tex>000 </tex> — член <tex>1 </tex> и т.д.

Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных <tex>P(A,B,C) </tex> показан на рисунке.

Чтобы получить формулу, по которой рассчитывается какой-либо коэффициент, нужно из клетки, в которой он записан, пройтись всеми возможными путями влево, до столбца <tex>''P'' </tex> таблицы истинности, делая ходы влево и влево-вниз, записать значения в конечных ячейках и сложить их все между собой по модулю 2.

<tex> a_3 = P(0,0,0) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,1) = P(0,0,0) \oplus P(0,1,0) \oplus P(0,0,1,0) \oplus P(0,1,1), </tex>

Пусть <tex> i = (i_1, i_2, .. \ldots i_n), \;\; i_k \in \{0 ; 1\}</tex>, и введем обозначение <tex> x ^{i_k} \sim \left\{\begin{matrix} x, \;\; i_k=1

<tex> f(x) = \bigoplus\limits_i \alpha_i \cdot x_1^{i_1} \cdot x_2^{i_2} \cdot ... </tex> <tex>\ldots</tex> <tex>\cdot x_n^{i_n}</tex>, где <tex>\alpha_i \in \{ 0; 1 \}</tex>.

Множество коэффициентов <tex>\{\alpha _i\}</tex> можно рассматривать как функцию <tex>\alpha</tex>, заданной на множестве индексов <tex> i = (i_1, i_2, .. \ldots i_n)</tex>, то есть <tex>\alpha: i \mapsto \alpha_i</tex>.

Очевидно, функцию <tex> f </tex> можно записать и следующим образом: <tex> f(x) = \bigoplus \limits_i \alpha_i \cdot [x_1 , \; </tex> если <tex> \;\; i_1] \cdot [x_2 , \; </tex> если <tex> \;\; i_2] \cdot ... </tex> <tex>\ldots</tex> <tex>\cdot [x_n , \; </tex> если <tex> \;\; i_n]</tex>.

Тогда если для какого-то <tex>x</tex>, <tex>i \succ x*</tex>* ,то в слагаемом будет существовать хотя бы один множитель, равный нулю, и такое слагаемое на сумму не повлияет.Отсюда ясно, что<tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha_i </tex>&nbsp; <tex> (2) </tex>Найдем отображение <tex> f \mapsto \alpha</tex> (То есть такое, которое по заданной функции вычисляет значения всех коэффициентов).

<tex> f(x) = \bigoplus \limits_{*</tex> <tex>i \preceq succ x} \alpha_i </tex>&nbsp; обозначает, что <tex> (2) x</tex> Найдем отображение "меньше" <tex> f \mapsto \alphai</tex> (То есть такое, которое по заданной функции вычисляет значения всех коэффициентов).как последовательность бит

||proof=Докажем при помощи индукции по количеству единиц в векторе <tex> x </tex> ( иначе говоря, по сумме <tex>x_1+x_2+...</tex><tex>\ldots</tex><tex>+x_n</tex> ) и для удобства обозначим это количество единиц(сумму) <tex> wt(x) </tex>.

Рассмотрим сумму <tex> \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] </tex>. Каждый элемент <tex> f(j) </tex> содержится в ней, только если <tex> j \prec x </tex>, и для фиксированных <tex> j, </tex> и <tex> x </tex> элемент <tex> f(j)</tex> встречается ровно столько раз, сколько существует <tex> i </tex> , таких, что <tex> j \prec preceq i \prec x</tex>. Несложно увидеть, что таких <tex> i </tex> существует ровно <tex> 2^{wt(x)-wt(j)}-1 </tex>, то есть нечетное количество раз. Тогда <tex> \left [ \bigoplus \limits_{i \prec x} \bigoplus \limits_{j\preceq i} f(j) \right ] = \bigoplus \limits_{j\prec x} f(j) </tex>.

<tex>== См. также ==* \succ [[Определение_булевой_функции|Булевы функции]]* [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций|Полные системы функций, \preceq , \prec</tex> - бинарные отношениятеорема Поста]]* [[СДНФ|ДНФ]]* [[СКНФ|КНФ]]

* [http://ru.wikipedia.org/wiki/Полином_Жегалкина Википедия{{---}} Полином Жегалкина]