17
правок
Изменения
м
Тикет
'''Полином Жегалкина''' — полином с коэффициентами вида <tex>0 </tex> и <tex>1</tex>, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления [[Определение булевой функции|функций булевой логики]]. Полином Жегалкина имеет следующий вид:
<tex>P = a_{000...000} \oplus a_{100...0} x_1 \oplus a_{010...0} x_2 \oplus ... \oplus a_{00...01} x_n \oplus a_{110...0} x_1 x_2 \oplus ... \oplus a_{00...011} x_{n-1} x_n \oplus ... \oplus a_{11..1} x_1 x_2 ... x_n </tex>
== Предпосылки Полнота ==
По [[Теорема Поста о полной системе функций|теореме Поста]], чтобы система булевых функций была полной, надо, чтобы в ней существовали
#Хотя бы одна функция, не сохраняющая <tex>0</tex>;#Хотя бы одна функция, не сохраняющая <tex>1</tex>;
#Хотя бы одна нелинейная функция;
#Хотя бы одна немонотонная функция;
Исходя из этого, система функций <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex> является полной, так как в ней:
#Не сохраняет <tex>0</tex>: <tex> 1 </tex>;#Не сохраняет <tex>1</tex>: <tex> \oplus </tex>;
#Нелинейна: <tex> \wedge </tex>;
#Немонотонна: <tex> \oplus </tex>;
Каждая булева функция единственным образом представляется в виде полинома Жегалкина.
|proof=
Заметим, что различных булевых функций от <tex>n</tex> переменных <tex>2^{2^n}</tex> штук. При этом конъюнкций вида <tex>x_{i_1} \ldots x_{i_k}</tex> существует ровно <tex>2^n</tex>, так как из <tex>n</tex> возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит <tex>0 </tex> или <tex>1</tex>, то есть существует <tex>2^{2^n}</tex> различных полиномов Жегалкина от <tex>n</tex> переменных.
Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.
Таким образом, полином Жегалкина выглядит так:
<tex>f(x_1,x_2,x_3,x_4) = x_1 \oplus x_1 x_3 \oplus x_1 x_4 \oplus x_2 x_3 \oplus x_2 x_3 x_4 \oplus x_1 x_2 x_3 x_4</tex>
=== Преобразование [[Определение_булевой_функции#Дизъюнктивная нормальная форма (ДНФ)|дизъюнктивной нормальной формы]] ===
Запишем функцию так:
<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 + \neg x_1 \neg x_4 + x_1 x_2 + x_2</tex>;
Сгруппируем слагаемые и воспользуемся преобразованием (1):
<tex>f(x_1,x_2,x_3,x_4) = (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_1 x_2 \neg x_3 x_4 \neg x_1 \neg x_4) + (x_1 x_2 \oplus x_2 \oplus \oplus x_1 x_2 x_2)</tex>
Воспользуемся свойствами конъюнкции <tex>A \land A = A</tex> и <tex>\neg A \land A = 0</tex>, а также тем, что <tex>A \oplus A = 0</tex>, и упростим выражение:
<tex>f(x_1,x_2,x_3,x_4) = (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4) + x_2 </tex>
Ещё раз воспользуемся преобразованием (1):
<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_2 \oplus (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4)x_2</tex>
Раскроем скобку по алгебраическим правилам:
<tex>f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_2 \oplus x_1 x_2 x_2 \neg x_3 x_4 \oplus \neg x_1 x_2 \neg x_4 </tex>
Снова воспользуемся свойствами конъюнкции и исключающего ИЛИ:
<tex>f(x_1,x_2,x_3,x_4) = \neg x_1 \neg x_4 \oplus x_2 \oplus \neg x_1 x_2 \neg x_4 </tex>
Заменим отрицание на прибавление <tex>1</tex>:
Тут запись <tex>[x_k , \; </tex> если <tex> \; i_k]</tex> означает, что элелемент <tex> x_k </tex> присутствует в соответствующем члене полинома только если <tex> i_k = 1 </tex>.
Тогда если для какого-то <tex>x</tex>, <tex>i \succ x</tex> * ,то в слагаемом будет существовать хотя бы один множитель, равный нулю, и такое слагаемое на сумму не повлияет.
Отсюда ясно, что
<tex> f(x) = \bigoplus \limits_{i \preceq x} \alpha_i </tex>. <tex> (2) </tex>
Найдем отображение <tex> f \mapsto \alpha</tex> (То есть такое, которое по заданной функции вычисляет значения всех коэффициентов).
Видно, что <tex> (2) </tex> и <tex> (3) </tex> — это одно и тоже преобразование. Значит, если применить преобразование Мёбиуса к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию <tex>f</tex>. То есть преобразование Мёбиуса обратно самому себе, иными словами, является инволюцией.
<tex>* \succ , \preceq , \prec</tex> - бинарные отношения
== Литература и источники информации ==
