Алгебра Жегалкина. Основные свойства операций алгебры Жегалкина.

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

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

1. x y = y x;

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

3. x x = 0;

4. x = 1;

5. x 0 = x.

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

Функцию Шеффера, функцию стрелка Пирса и можно представить следующими эквивалентными формулами:

х1 / x2 = = , x1 “ x2 = & =

 

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

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.

3. x ’ y = x y x 1.

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

x ’ y = y = y y = (x 1) y (x 1) y =

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

4. x / y = x y 1.

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

x / y = = xy 1.

5. x “ y = x y x y 1.

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

x “ y = = (x 1)(y 1) = x y x y 1.

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

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

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

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