Совершенная конъюнктивная нормальная форма.

Пусть зафиксирован набор булевых переменных x_1, x₂, ..., x_n.

Определение 1 . Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза. Если число переменных равно n, то такая элементарная дизъюнкция называется полной.

В примере 2 - полные элементарные дизъюнкции.

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

Теорема. Любая булева формула может быть представлена и притом единственным образом в виде СКНФ.