СКНФ
[предыдущая глава]  [оглавление]  [следующая глава]

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

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

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

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

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

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

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

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

xyzf(x, y, z)
falsefalsefalsefalse
falsefalsetruefalse
falsetruefalsefalse
falsetruetruetrue
truefalsefalsetrue
truefalsetruefalse
truetruefalsetrue
truetruetruefalse

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


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)