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

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

Есть несколько способов составления полиномов Жегалкина. Рассмотрим некоторые из них.

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

x y = x&y x y
~x = x true
x y = x y true
x y = x&y x y true
x | y = x&y true
x y = x&y x
x y = x&y y
x y = x&y x true
x y = x&y y true

Далее избавимся от всех скобок с помощью правила:

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

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

x & x = x, x & true = x, true & x = x, x & false = false, false & x = false, x x = false, x false = x, false x = x.

От константы true повсеместно избавиться не удастся, поскольку закон поглощения x true = ~x добавляет операцию "~", от которой мы тоже хотели бы избавиться.

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

В случае, если булева функция представлена не формулой, а таблицей истинности, мы можем составить СДНФ и упростить ее. В результате у нас в руках будет булева формула, к которой можно применить описанные выше методы.

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

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

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

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

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

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

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

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

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

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

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

Вопросы и задания для самостоятельной работы

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