1.5. Минимизация конъюнктивных нормальных форм

Теория минимизации КНФ аналогична теории минимизации ДНФ за исключением некоторых определений, которые будут ниже приведены.

Булева функция называетсяимплицентой БФ , если на каком-либо наборе переменныхгде функцияравна нулю или не определена, функциятакже равна нулю.

Простой имплицентой БФ называется элементарная дизъюнкция, которая являетсяимплицентой булевой функции и никакая ее часть не может быть имплицентой функции.

К числу элементарных дизъюнкций относится также константа нуля. При этом предполагается, что справедливы следующие утверждения:

- конъюнкция конечного числа имплицент булевой функции также является имплицентой данной БФ;

- конъюнкция всех имплицент булевых функции является полной системой;

- конъюнкция всех простых имплицент БФ называется сокращенной конъюнктивной нормальной формой.

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

Пример 1.5. СКНФ задана в числовом виде: . С помощью алгоритма Квайна - Мак-Класки найти МКНФ. Запишем эти макстермы в двоичном коде и разделим их на группы (см. табл. 1.8).

Согласно с алгоритмом Квайна - Мак-Класки сравниваем между собой соседние группы и выполняем операцию неполного конъюнктивного склеивания (см. табл. 1.9).

Продолжаем выполнять операцию неполного конъюнктивного склеивания до тех пор, пока имеется возможность.

В нашем примере после еще одного цикла склеивания имеем три простые имплиценты: . Строим имплицентную таблицу 1.10.

Таблица 1.10

Таблица простых имплицент

Таким образом, получили минимальную КНФ: