Разложение булевых функций в канонический полином Жегалкина

Интерес к разложению булевых функций в канонический полином Жегалкина объясняется прежде всего тем, что такое представление реализуемых функций является основой для синтеза логи­ческих схем в базисе элементов И и СЛОЖЕНИЕ по МОДУЛЮ ДВА.

Определение. Полином булевой функции F, в слагаемые которого все переменные F входят только без отрица­ния или только с отрицанием, называется монотонно-поляризован­ным. Причем в первом случае полином функции F называется поло­жительно-поляризованный и обозначается через P(F), а во втором случае - отрицательно-поляризованным и обозначается через Q(F). Полином P(F) иначе называется каноническим полиномом Жегалкина (или в зарубежной научно-технической литературе - формой Рида-Мюллера).

Например, для булевой функции, заданной вектором значений таблицы истинности w(F)=(00100111) полиномы P(F) и Q(F) имеют вид:

,

.

Отметим некоторые свойства монотонно-поляризованных поли­номов P(F) и Q(F) булевой функции :

1. Полиномы P(F) и Q(F) являются для булевой функции F единственными.

2. Полиномы P(F) и Q(F) имеют степень n тогда и только тогда, когда

таблица истинности функции F содержит нечетное число единиц.

3. Число слагаемых полинома P(F) (Q(F)) четно тогда и только тогда, когда

(соответственно ).

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

Опишем метод построения канонического поли­нома Жегалкина P(F) путем преобразования СДНФ для произвольных булевых функций n пе­ременных F, заданных посредством таблицы истинности.

Предварительно отметим основные свойства логической опе­рации сложения по модулю два, которые используются при описа­нии метода.

Имеет место

(1)

(2)

(3)

(4)

, если (5)

, (6)

если для , , .

Метод построения полинома P(F) заключается в последова­тельном выполнении следующих действий:

1) выписывается СДНФ булевой функции F;

2) на основе применения (6) СДНФ F пре­образуется в СПНФ функции F;

3) в СПНФ все переменные с отрицанием заменяют­ся по формуле (2);

4) в скобочной форме осуществляется раскрытие скобок согласно (3);

5) из полученного выражения удаляются попарно одинаковые слагаемые в

соответствии с (1);

6) полу­ченное выражение обозначается через P(F).

Пример. Составить канонический поли­ном Жегалкина P(F) булевой функции, если СДНФ данной булевой функции, имеет вид: .

Решение. Заменим операцию дизъюнкции операцией сложения по модулю два по (6). При этом воспользуемся тем, что произведение (конъюнкция) любых полных дизъюнкций СДНФ всегда равно нулю. Следовательно, СПНФ будет иметь вид:

.

Все переменные с отрицанием заменяем по формуле (2), затем раскрываем скобки и из полученного выражения удаляем попарно одинаковые слагаемые в соответствии с (1):

.

Ответ: P(F) .