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

Определение. Выражение вида называется элементарной дизъюнкцией.

Членами дизъюнкции являются либо , либо их отрицания.

Пример.

Определение. Элементарная дизъюнкция, в которую включены все переменные, называется основной элементарной дизъюнкцией.

Пример.

.

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

Пример.

n=3; КНФ, - СКНФ.

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

Пусть . Разложим функцию f^*(x₁,…,x_n) (очевидно ) в СДНФ:

Из принципа двойственности следует, что

Левая часть равенства есть f(x₁,…,x_n), а правая может быть преобразована следующим образом:

Таким образом, получаем разложение

Данная формула носит конструктивный характер, т.к. она по таблице функции позволяет построить формулу, являющуюся СКНФ (если ).

СКНФ функции f содержит ровно столько дизъюнкций, сколько нулей в таблице f. Каждому “нулевому” набору (d ₁,…,d _n) значений переменных, т.е. набору, на котором значение функции равно 0, соответствует дизъюнкция всех переменных, в которых x_i взято с отрицанием, если d _i =1 и без отрицания, если d _i =0.

Пример. Записать СКНФ для функции

x1 xi	x1®x2	Основная элементарная дизъюнкция
0 0	1
0 1	1
1 0	0	Úx2
1 1	1

.