Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Специальные представления булевых функций





Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний.Для каждой функции логики высказываний можно составить таблицу истинности. Обратная задача тоже всегда разрешима. Введем несколько определений.

Элементарными конъюнкциями (конъюнктами) называются конъюнкции переменных или их отрицаний, в которых каждая переменная встречается не более

одного раза.

Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций.

Элементарными дизъюнкциями (дизъюнктами) называются дизъюнкции переменных с отрицаниями или без них.

Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций.

Для каждой функции алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм.

Алгоритм построения ДНФ:

1. Перейти к булевым операциям, используя формулы эквивалентных преобразований.

2. Перейти к формулам с тесными отрицаниями, то есть к формуле, в которой отрицания располагаются не выше, чем над переменными – применить законы де Моргана.

3. Раскрыть скобки – применить законы дистрибутивности.

4. Повторяющиеся слагаемые взять по одному разу – закон идемпотентности.

5. Применить законы поглощения и полупоглощения.

Пример 6. Найти ДНФ формулы: .

В алгебре Буля справедлив принцип двойственности. Он заключается в следующем.

Функция называется двойственной к функции , если . Т.е. для нахождения функции, двойственной к заданной, необходимо построить отрицание функции от отрицаний аргументов.

Пример 7. Найти функцию, двойственную к .

Среди элементарных функций алгебры логики 1 двойственна 0 и наоборот, х двойственна х, двойственна , двойственна и наоборот.

Если в формуле F1 представляющей функцию все конъюнкции заменить

на дизъюнкции, дизъюнкции на конъюнкции, 1 на 0, 0 на 1, то получим формулу F*, представляющую функцию *, двойственную .

Конъюнктивная нормальная форма (КНФ) – двойственное для ДНФ понятие, поэтому ее легко построить по схеме:

Пример 8. Найти КНФ формулы: .

Воспользовавшись результатом примера 6, имеем

Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы.В каждом из типов нормальных форм (дизъюнктивных и конъюнктивных) можно выделить класс совершенных форм СДНФ и СКНФ.

Совершенной элементарной конъюнкцией называется логическое произведение всех переменных с отрицанием или без них, причем, каждая переменная входит в произведение только один раз.

Всякую ДНФ можно привести к СДНФ расщеплением конъюнкций, которые содержат не все переменные, т.е. добавлением для отсутствующей переменной xi множится с применением закона дистрибутивности



Пример 9. Найти СДНФ для ДНФ примера 6

Совершенной элементарной дизъюнкцией называется логическая сумма всех переменных с отрицаниями или без них, причем, каждая переменная входит в сумму только один раз.

Всякую КНФ можно привести к СКНФ, добавляя член конъюнкции, не содержащий какой – либо переменной Xi конъюнкцией и применяя дистрибутивный закон

Пример 10 . Привести КНФ к СКНФ:

Для построения СКНФ можно воспользоваться схемой

Пример 11. Найти СКНФ для формулы примера 6.

Всякая функция имеет СДНФ и, притом, единственную . Каждая функция имеет СКНФ и, притом, единственную .

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

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

Для построения СКНФ по таблице истинности необходимо выделить в ней строки, где F=0, и записать совершенные элементарные дизъюнкции, после чего соединить их знаками конъюнкции. Если в требуемой строке таблицы истинности (F=0) значение переменной соответствует нулю, то в совершенном дизъюнкте она берется без отрицания, если единице – то с отрицанием.

Пример 12. Найти СДНФ и СКНФ по таблице истинности для формулы примера 6.

В таблице 14 приведено лишь конечное значение F=10101101. В справедливости этого утверждения следует убедиться самостоятельно, построив развернутую таблицу истинности.

 

Таблица 14

x y z

 

СДНФ =

СКНФ = .

Как видно из примеров 9, 10, 11, 12 значения СДНФ и СКНФ, полученные различными способами, для заданной функции совпадают. Это еще раз подчеркивает единственность представления функции в совершенных нормальных формах.





Дата добавления: 2014-01-03; Просмотров: 1520; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.004 сек.