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

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

Напомним, что конституентой нуля называется функция, принимающая значение 0 на одном наборе. Она выражается дизъюнкцией всех переменных функций. Например, набору 0110 соответствует конституента нуля x₁+x₂+x₃+x₄.

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

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

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

(A v x)A = A.

Что касается первого этапа - поиска всех простых имплицент, то практически все методы минимизации ДНФ имеют свои аналоги для КНФ. Рассмотрим это подробнее.

Соотношение склеивания по Квайну:

Соотношение склеивания по Блейку:

Метод Нельсона в применении к задаче минимизации КНФ: раскрытие скобок в произвольной ДНФ функции и выполнение поглощений приводит к сокращенной КНФ. Предполагаются скобки в начале и конце каждого элементарного произведения исходной ДНФ x₁x₂+x₁x₂и использование второго дистрибутивного закона. Например, функция, заданная минимальной ДНФ дает возможность определить ее сокращенную КНФ:

По диаграмме Вейча поиск минимальной КНФ осуществляется так же просто, как и в случае ДНФ. Отличие состоит лишь в том, что анализируются нулевые наборы и переменные выписываются с инверсиями. Например, для функции, заданной диаграммой (рис. 20), минимальной КНФ является

Для сравнения найдем минимальную ДНФ:

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