Совершенная конъюнктивная нормальная форма (СКНФ).

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

Для каждой строки с нулем в крайнем правом столбце образуем скобки и объединяем их операцией &. В каждую скобку вставляем последовательность из простых элементов, объединенных операцией V: для ячейки таблицы, где проставлен 0, пишем переменную-аргумент, а для каждой ячейки, где проставлена 1, пишем переменную-аргумент со знаком ~ перед ним.

Пример составления СКНФ.

Для нашей функции-примера СКНФ будет выглядеть так:

f(x,y,z) =
(x y z) &
(x y ~z) &
(x ~y z) &
(~x y ~z) &
(~x ~y ~z)

Правила упрощения:

(a b c) & (a ~b c) = a c
(a b) & (a ~b) = a
(b c) & (~b c) = c

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

f(x,y,z) = (x y) & (x ~y z) & (~x ~z)