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

Определение. Формула вида , где , i = = 1, 2, …, n, а среди переменных могут быть совпадающие, называется элементарной дизъюнкцией (ЭД).

Определение. Элементарная дизъюнкция называется правильной (ПЭД), если всякая переменная входит в нее не более одного раза (включая вхождение под знаком отрицания).

Определение. ПЭД называется полной (ППЭД) относительно переменных, , если она содержит все эти и только эти переменные (быть может под знаком отрицания).

Пример. - элементарная дизъюнкция; - ПЭД; ; ; - правильные полные ЭД относительно переменных .

Утверждение. Всякая ППЭД равна 0 на единственном наборе значений аргументов: .

Доказательство. Пусть

.

Пусть

.

Определение. Всякая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ).

Пример. - КНФ.

Определение. Совершенной конъюнктивной нормальной формой (СКНФ) относительно переменных называется КНФ, в которых нет одинаковых ЭД и все ЭД правильны и полны относительно переменных .

Пример. - СКНФ относительно переменных

Утверждение. Всякую функцию алгебры логики , не равную тождественно 1, можно представить в виде СКНФ

(2)

Конъюнкция вычисляется по всем наборам значений переменных, на которых данная функция равна 0.

Предварим доказательство формулы (2) примером построения СКНФ.

Пример. Пусть функция трех переменных заданна таблицей истинности (табл. 2).

Таблица 2

Выпишем двоичные наборы, на которых функция равна 0 и составим соответствующие этим наборам ППЭД.

(0,0,0): ; (0,1,0): ;

(0,1,1): ; (1,0,0): ;

(1,1,1): ;

СКНФ: .

Построенная СКНФ равна нулю в точности на наборах (0,0,0), (0,1,0), (0,1,1), (1,0,0), (1,1,1): на каждом из них ровно одна ППЭД, составляющая СКНФ, равна 0. На каждом из остальных трех наборах значений аргументов все пять ППЭД равны 1, поэтому и СКНФ равна 1. Итак, построенная СКНФ и данная функция имеют одну и ту же таблицу истинности – эти функции равносильны.

Перейдем к доказательству формулы (2)

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

Утверждение. Представление функции СКНФ единственно.

Доказательство. Рассмотрим две разных СКНФ n переменных, обозначим их СКНФ₁ и СКНФ₂. Так как СКНФ₁ ≠ СКНФ₂, имеется хотя бы одна ППЭД , которая входит в одну из СКНФ, например, в СКНФ₁, и не входит в другую. Тогда на наборе СКНФ₁ равна 0, а СКНФ₂ равна 1, эти функции имеют разные таблицы истинности.