Определение

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

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

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

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

Пример. Формулы и - дизъюнкты, формулы и - конъюнкты, а является одновременно и дизъюнктом, и конъюнктом.

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

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

 

Теорема.

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

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