Полином Жегалкина.

Это - еще один способ выразить произвольную булеву функцию через бинарные операции. Мы уже знаем, что произвольную булеву функцию можно выразить через &, и ~ в виде СДНФ. Мы также знаем, что и ~ можно выразить через & и :

x y = x y (x & y)
~x = x 1

Применив эти формулы, мы всякую булеву функцию выразим через операции & и .

Дальше мы можем раскрыть все скобки, кроме самого последнего уровня, применяя правила дистрибутивности (в точной аналогии с тем, как это делалось в школе с раскрытием скобок и приведением подобных членов):

x & (y z) = (x & y) (x & z)
(x y) & z = (x & z) (y & z).

В результате получится формула вида:

(x_a & x_b & ...) ... (x_c & x_d & ...)

или вида:

(x_a & x_b & ...) ... (x_c & x_d & ...) 1

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

a & a = a, a & 1 = a, 1 & a = a

Затем выполним дополнительное сокращение, убрав одинаковые скобки с помощью законов поглощения

a a = 0, a 0 = a, 0 a = a.

В результате получится формула, которая и называется полиномом Жегалкина.

Пример составления полинома Жегалкина.

Возьмем СДНФ нашей функции, и упростим его, насколько возможно:

f(x,y,z) = (~x & y & z) (x & ~z)

Теперь преобразуем инверсии:

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

Теперь преобразуем операцию :

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

Раскроем скобки:

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

Применим законы поглощения внутри скобок:

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

Применим законы поглощения для одинаковых скобок, учитывая, что переменные, соединенные знаками & можно менять местами:

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

Это - и есть полином Жегалкина. Таким образом, любую логическую функцию можно выразить в виде полинома Жегалкина: цепочки элементов, соединенных операцией . Каждый элемент - 0, 1, переменная или скобка, в которой несколько переменных,