- Дизъюнктивная нормальная форма
-
Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.
Содержание
Примеры и контрпримеры
Формулы в ДНФ:
Формулы не в ДНФ:
Построение ДНФ
Алгоритм построения ДНФ
1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:
2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.
Пример построения ДНФ
Приведем к ДНФ формулу :
Выразим логические операции → и ↓ через :
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
Используя закон дистрибутивности, приводим формулу к ДНФ:
k-дизъюнктивная нормальная форма
k-дизъюнктивная нормальной формой называют дизъюнктивную нормальную форму, в которой каждая конъюнкция содержит ровно k литералов.
Например, следующая формула записана в 2-ДНФ:
Переход от ДНФ к СДНФ
Если в какой-то простой конъюнкции недостает переменной, например, Z, вставляем в нее выражение :, после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем, так как по закону Идемпотентности). Например:
Таким образом, из ДНФ получили СДНФ.
Формальная грамматика, описывающая ДНФ
Следующая формальная грамматика описывает все формулы, приведенные к ДНФ:
- <ДНФ> → <конъюнкт>
- <ДНФ> → <ДНФ> ∨ <конъюнкт>
- <конъюнкт> → <литерал>
- <конъюнкт> → (<конъюнкт> ∧ <литерал>)
- <литерал> → <терм>
- <литерал> → ¬<терм>
где <терм> обозначает произвольную булеву переменную.
См. также
- Конъюнктивная нормальная форма
- Дистрибутивность
- Нормальная форма (математика)
- Закон двойного отрицания
- Законы де Моргана
Примечания
- ↑ Поздняков С.Н., Рыбин С.В. Дискретная математика. — С. 303.
Литература
- Ю.И. Галушкина, А.Н. Марьямов: Конспект лекций по дискретной математике - 2-е изд., испр. - М.: Айрис-пресс, 2008. - 176 с. - (Высшее образование)
Ссылки
Категория:- Булева алгебра
Wikimedia Foundation. 2010.