Дизъюнктивные и конъюнктивные нормальные формы. Алгоритм приведения формулы к ДНФ и КНФ

Если х – логическая переменная, , то выражение: называется литерой. Литеры x и называются контрарными.

Элементарной конъюнкцией или конъюнктом называется конъюнкция литер. Элементарной дизъюнкцией или дизъюнктом называется дизъюнкция литер.

ДНФ – дизъюнкция конъюнктов. КНФ – конъюнкция дизъюнктов. Любая формула эквивалентна некоторой ДНФ и КНФ.

Алгоритм приведения формулы к ДНФ:

1) Выразить все логические операции, участвующие в построении формулы через дизъюнкции, конъюнкции и отрицания: , .

2) Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания.

3) Используя закон дистрибутивности , преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций.

Алгоритм приведения формулы к КНФ:

4) Выразить все логические операции, участвующие в построении формулы через дизъюнкции, конъюнкции и отрицания: , .

5) Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания.

6) Используя закон дистрибутивности , преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше конъюнкций.