Алгебра Жегалкина, её свойства и применение

1. Алгебра Жегалкина, её свойства и применение

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

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

• 1. x y = y x;
• 2. x (y z) = x y x z;
• 3. x x = 0; (1)
• 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.

3. x > y = x y x 1.

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

x₁ v x₂ ~ & ~ .

Тогда:

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₂ ~ ~ .

Тогда:

x / y = = xy 1.

5. x v y = x y x y 1.

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

x₁ v x₂ ~ & ~ .

Тогда:

x v 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.

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

алгебра бинарные жегалкин.

a? x x … x, (1? k? n).

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

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

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

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

Пример. Найти полином Жегалкина для функции:

f (x, y) = (xy)(x z).

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

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

f₁ f₂ = f₁ f₂, (2).

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

Пример. Найти полином Жегалкина для функции: 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 задания данной функции.

Таблица 1.

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

f (x, y) = a₀ a₁· x a₂· y a₃· xy (3).

Для определения коэффициентов полинома нужно подставить значения неизвестных и соответствующее значение функции в (3), согласно таблице 1.

Подставляя набор переменных (0,0) в (3) получим:

. a = 0.

Аналогично для набора (0,1) получим:

. a = 1.

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

a = 1.

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

a = 0.

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

f (x, y) = x y.

Замечание.

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

Список использованных источников

• 1. Акимов В. А. Дискретная математика: логика, группы, графы. М.: Лаборатория Базовых Знаний, 2003, 376 с.
• 2. Ершов Ю. А., Полюнин Е. А. Математическая логика: Учебное пособие для вузов. М.: Наука. Гл. ред. физ. — мат. лит., 1987, 336 с.
• 3. Р. Хаггарти Дискретная математика для программистов Москва: Техносфера, 2003, 320 с.
• 4. Гончарова Г. А., Мочалин А. А. Элементы дискретной математики: Учебное пособие. — М.: ФОРУМ: ИНФРА-М, 2004, 128 с.
• 5. Судоплатов С. В., Овчинникова Е. В. Элементы дискретной математики: Учебник. — М.: ИНФРА — М; Новосибирск: НГТУ, 2003, 280 с. — (Серия «Высшее образование»).