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

Замечание: Каждая элементарная конъюнкция (дизъюнкция), входящая в СНДФ (в СНКФ), должна содержать все пропозиционные буквы, входящие в исходную формулу. Только в этом случае можно говорить о том, что полученная форма является совершенной. Иначе имеем ДНФ (КНФ).

СНДФ и СНКФ можно составлять для данной формулы, пользуясь её таблицей истинности.

Рассмотрим таблицу истинности для произвольной формулы алгебры высказываний :

 

		...
...	...	...	...	...
и	л	...	и	и
...	...	...	...	...

 

Для каждой строки таблицы истинности строим элементарную конъюнкцию , которая истинна только для этой строки, а для всех остальных строк эта элементарная конъюнкция ложна. Пропозиционная переменная входит в элементарную конъюнкцию без черты, если в данной строке принимает значение «истина». Если же переменная принимает в данной строке значение «ложь», то в элементарную конъюнкцию эта буква входит с чертой.

Тогда дизъюнкция всех элементарных конъюнкций, построенная для всех строк, в которых формула принимает значение «истина», будет иметь ту же таблицу истинности, что и рассмотренная формула . Такое представление данной формулы и будет являться совершенной нормальной дизъюнктивной формой (СНДФ).

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

Например, составим СНДФ для формулы .

 

и	и	и	л	и	и
и	и	л	л	и	л
и	л	и	л	л	и
л	и	и	и	и	и
и	л	л	л	л	и
л	и	л	и	и	л
л	л	и	и	и	и
л	л	л	и	и	л

 

СНДФ для данной формулы имеет вид: =

.

В правой части равносильности просто «перечислены» все строки таблицы истинности, в которых наша формула принимает значение «истина».

Из рассмотренного примера видно, что СНДФ существует для всякой выполнимой формулы.

Аналогичные рассуждения можно привести и для СНКФ.

Если произвольная формула не является тождественно истинной, то по таблице истинности для каждой строки, где наша формула ложна, строим элементарную дизъюнкцию, которая принимает значение «ложь» только в данной строке, а в остальных строках принимает значение «истина». Если пропозиционная буква в данной строке принимает значение «ложь», то она входит в элементарную дизъюнкцию без черты. Если же переменная в данной строке принимает значение «истина», то в элементарную дизъюнкцию она входит с чертой. Если построить такие дизъюнкции для всех строк таблицы, в которых формула принимает значение «ложь», и соединить их знаками конъюнкции, то полученная конъюнкция таких элементарных дизъюнкций имеет такую же таблицу истинности, что и исходная формула. Полученное представление формулы называется совершенной нормальной конъюнктивной формой (СНКФ).

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

Если же формула является тавтологией, то её можно представить в виде дизъюнкции .

Для рассмотренного примера СНКФ имеет вид:

↔ .

Искать СНДФ или СНКФ по таблице не всегда удобно. Особенно для тех формул, которые зависят от 4-х и более переменных. Поэтому рассмотрим алгоритм, позволяющий преобразовать произвольную формулу в СНДФ или СНКФ.