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

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

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


Для нашей функции-примера СКНФ будет выглядеть так:
f(x,y,z) = 
(x y z) & 
(x y ~z) & 
(x ~y z) & 
(~x y ~z) & 
(~x ~y ~z) 

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


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

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

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