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

(ab~c) & (a~bc) & (a~b~c)

В отличии от дизъюнктивной формы здесь пришлось добавить скобки, чтобы конъюнкции выполнялись после дизъюнкций.

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

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

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

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

Для той же самой функции:

x	y	z	f(x, y, z)
false	false	false	false
false	false	true	false
false	true	false	false
false	true	true	true
true	false	false	true
true	false	true	false
true	true	false	true
true	true	true	false

СКНФ будет выглядеть так:

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)