Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.
Формулы в ДНФ:
Формулы не в ДНФ:
Но последние две формулы эквивалентны следующим формулам в ДНФ:
1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:
2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.
Приведем к ДНФ формулу
Выразим логическую операцию → через
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
Используя закон дистрибутивности, получаем:
Используя идемпотентность конъюкции, получаем ДНФ:
k-дизъюнктивной нормальной формой называют дизъюнктивную нормальную форму, в которой каждая конъюнкция содержит ровно k литералов.
Например, следующая формула записана в 2-ДНФ:
Если в какой-то простой конъюнкции недостаёт переменной, например, Z, вставляем в неё выражение
после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем, так как по закону идемпотентности). Например:
Таким образом, из ДНФ получили СДНФ.
Следующая формальная грамматика описывает все формулы, приведенные к ДНФ:
где <терм> обозначает произвольную булеву переменную.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .