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

Как уже отмечалось, система операций булевой алгебры функционально полна, это означает, что для любой логической формулы переход к булевской формуле всегда возможен. .

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

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

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

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

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