Алгебра жегалкина
= x y
x x z z = x z x
y x
z. - полиномом Жегалкина.
Теорема. Для любой логической функции существует полином Жегалкина и притом единственный.
Доказательство: Существование полинома доказано вышеприведенным алгоритмом получения полинома из логической формулы. Для доказательства единственности надо показать, что между множеством всех логических функций от n переменных и множеством всех полиномов Жегалкина от n переменных существует взаимно однозначное соответствие.
Полином Жегалкина можно найти методом неопределенных коэффициентов. Рассмотрим этот метод на следующим примере.
Пример. Найти полином Жегалкина для функции заданной векторно:
f( x,y ) = ( 0, 1, 1, 0 ).
Составим таблицу 1.14 задания данной функции.
Таблица 1.14
|
x |
y |
f |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
0 |
Полином Жегалкина для функции двух переменных ищем в следующем виде:
f( x, y ) = a0 a1·x
a2·y a3·xy (1.6)
Для определения коэффициентов полинома нужно подставить значения неизвестных и соответствующее значение функции в (1.6), согласно таблице 1.14.
Подставляя набор переменных(0,0) в (1.6) получим:
. 
a
= 0.
Аналогично для набора (0,1) получим: 
. a
= 1.