Студопедия КАТЕГОРИИ: АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Разложение булевых функций в канонический полином Жегалкина
Интерес к разложению булевых функций в канонический полином Жегалкина объясняется прежде всего тем, что такое представление реализуемых функций является основой для синтеза логических схем в базисе элементов И и СЛОЖЕНИЕ по МОДУЛЮ ДВА.
Определение.Полином булевой функции 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-12; просмотров: 211. stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда... |