Дизъюнктивные и конъюктивные нормальные формы

Если х — логическая переменная, {0,1}, то выражение

называется литерой. Литеры х и называются контрарными.

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

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

Пример: ˄y˄z – конъюнкт;

˅y˅z – дизъюнкт.

Дизъюнкция конъюнктов называется дизъюнктивной нор­мальной формой (ДНФ)

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

Пример: Формула — ДНФ, формула ()()y — КНФ, а формула является одновременно КНФ и ДНФ.

Теорема. 1) Любая формула эквивалентна некоторой ДНФ.

2) Любая формула эквивалентна некоторой КНФ.