29. Алгебра Жегалкина. Представление логических функций полиномом Жегалкина.

Определение. Полиномом Жегалкина для n  логических переменных называется полином, являющийся суммой константы и различных одночленов, в которые все переменные входят не выше, чем в первой степени: 

                    a      x x … x ,   ( 1 d k d n ) 

причем в каждом наборе   ( i ,   , i )   все   i различны, а суммирование по mod 2  ведется по некоторому множеству таких  не совпадающих наборов.

Например,    1  x  x x ,      x x x  x x x - некоторые полиномы Жегалкина для двух и трех переменных соответственно.

От формулы алгебры логики всегда можно перейти к формуле алгебры Жегалкина. Для этого нужно заменить основные элементарные функции алгебры логики на соответствующие эквивалентные выражения алгебры Жегалкина (1) - (5), представленные выше.

В полученной формуле нужно раскрыть скобки и произвести упрощения, используя соотношения (1.4), а также следующие соотношения: x & x  = x и   x·1 = x. Полученное выражение и будет полиномом Жегалкина для данной формулы.

Пример. Найти полином Жегалкина для функции:   f( x, y ) = ( x y )(  x z ). 

Полученное выражение и есть полином Жегалкина.

При нахождении полинома Жегалкина для некоторой формулы алгебры логики можно использовать следующее соотношение, вытекающее из представления дизъюнкции в алгебре Жегалкина:

                           f1  f2 = f1 f2,                                                                           (1.5)

справедливое при   f1f2 = 0. Используем соотношение (1.5) для нахождения полинома Жегалкина в следующих примерах.

Пример. Найти полином Жегалкина для функции:        f( x, y ) =  x y     .

Сделаем следующие преобразования: 

                                      f( x,y )  =   x y     =  x y     =  x y  ( x  1 )( y  1 )  =      

                               =  x y  x y  x  y  1  =    1  x  y  - полиномом Жегалкина.

Пример. Найти полином Жегалкина для функции:       f( x, y )  =  x      z. 

 Сделаем следующие преобразования: 

                              f( x,y )  =  x      z  =  x      z   =  x ( y  1 ) ( x  1 ) z  = 

=  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.

Для набора  (1,0) получим:        a = 1.

Для набора  (1,1) получим:      a = 0.

Подставляя в (1.6) найденные значения коэффициентов получим искомый полином для данной функции:

f( x, y )  =  x  y.

Замечание. Можно показать, что переменная   x будет фиктивной для некоторой функции тогда и только тогда, когда полином Жегалкина для нее не содержит переменной   x