Разложение булевых функций в канонический полином Жегалкина
Разложение булевых функций в канонический полином Жегалкина
Интерес к разложению булевых функций в канонический полином Жегалкина объясняется прежде всего тем, что такое представление реализуемых функций является основой для синтеза логических схем в базисе элементов И и СЛОЖЕНИЕ по МОДУЛЮ ДВА.
Определение. Полином булевой функции 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). При этом воспользуемся тем, что произведение (конъюнкция) любых полных дизъюнкций СДНФ всегда равно нулю. Следовательно, СПНФ будет иметь вид:
.
Лекция "6 Протокол передачи файлов - FTP" также может быть Вам полезна.
Все переменные с отрицанием заменяем по формуле (2), затем раскрываем скобки и из полученного выражения удаляем попарно одинаковые слагаемые в соответствии с (1):
.
Ответ: P(F) .