Разложение булевых функций в канонический полином Жегалкина
Интерес к разложению булевых функций в канонический полином Жегалкина объясняется прежде всего тем, что такое представление реализуемых функций является основой для синтеза логических схем в базисе элементов И и СЛОЖЕНИЕ по МОДУЛЮ ДВА.
Определение.Полином булевой функции 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) .
Дата добавления: 2018-04-04; просмотров: 326; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!