1.4. Алгебра Жегалкина

Определение. Алгеброй Жегалкина называется алгебра над множеством логических функций и переменных, сигнатура которой содержит две бинарные операции & и , и две нульарные операции – константы 0 и 1.

В алгебре Жегалкина выполняются следующие соотношения:

1. x y = y x;

2. x ( y z ) = x y x z;

3. x x = 0;

(1.4)

4. x = 1;

5. x 0 = x.

Эти соотношения легко проверить табличным способом. Кроме перечисленных соотношений в алгебре Жегалкина выполняются соотношения булевой алгебры относительно конъюнкции и констант

.

Найдем выражения для основных элементарных функций алгебры логики в алгебре Жегалкина.

1. = x 1.

Это соотношение проверяется непосредственной подстановкой 0 и 1 в обе части равенства.

2. x y = x y x y.

Доказательство: x y = = 1 = ( x 1 )( y 1 ) 1 =

= x y x y 1 1 = x y x y.

2. x → y = x y x 1.

Доказательство: Используем выражение для импликсации в (1.3). Тогда:

x → y = y = y y = ( x 1 ) y ( x 1 ) y =

= x y y x 1 y = x y x 1.

2. x / y = x y 1.

Доказательство: Используем выражение для x / y в (1.3). Тогда:

x / y = = xy 1.

2. x ↓ y = x y x y 1.

Доказательство: Используем выражение для x ↓ y в (1.3). Тогда:

x ↓ y = = ( x 1 )( y 1) = x y x y 1.

2. x ~ y = 1 x y.

Доказательство: Легко проверить, что x ~ y = x y . Тогда :

x ~ y = x y ( x 1 )( y 1 ) = x y x y x y 1 = 1 x y.

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

менные входят не выше, чем в первой степени:

a ∑ x x … x , ( 1 ≤ k ≤ 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 ).

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

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

f₁ f₂ = f₁ f₂, (1.5)

справедливое при f₁f₂ = 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

Полином Жегалкина для функции двух переменных ищем в следующем виде:

f( x, y ) = a₀ a₁·x a₂·y a₃·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