2015-04-01
1785
Минимизация КНФ производится аналогично рассмотренным методам минимизации ДНФ булевых функций, поэтому остановимся лишь на основных положениях.
Напомним, что конституентой нуля называется функция, принимающая значение 0 на одном наборе. Она выражается дизъюнкцией всех переменных функций. Например, набору 0110 соответствует конституента нуля x1+x2+x3+x4.
Имплицентой g булевой функции f называется функция, принимающая значение 0 на подмножестве нулевых наборов функции f.
Простой имплицентой функции f называется элементарная дизъюнкция, являющаяся имплицентой функции f, причем никакая ее собственная часть имплицентой функции f не является.
Задачей минимизации КНФ является определение минимальной КНФ. Эта задача также решается в два этапа: поиск сокращенной КНФ (конъюнкция всех простых имплицент) и затем нахождение минимальной КНФ. Второй этап минимизации выполняется с помощью таблицы Квайна точно так же, как и при поиске минимальной ДНФ, так как возможны только два варианта: либо данная простая имплицента поглощает данную конституенту нуля, либо нет в соответствии с соотношением поглощения:
|
|
|
(A v x)A = A.
Что касается первого этапа - поиска всех простых имплицент, то практически все методы минимизации ДНФ имеют свои аналоги для КНФ. Рассмотрим это подробнее.
Соотношение склеивания по Квайну:
Соотношение склеивания по Блейку:
Метод Нельсона в применении к задаче минимизации КНФ: раскрытие скобок в произвольной ДНФ функции и выполнение поглощений приводит к сокращенной КНФ. Предполагаются скобки в начале и конце каждого элементарного произведения исходной ДНФ x1x2+x1x2и использование второго дистрибутивного закона. Например, функция, заданная минимальной ДНФ дает возможность определить ее сокращенную КНФ:
По диаграмме Вейча поиск минимальной КНФ осуществляется так же просто, как и в случае ДНФ. Отличие состоит лишь в том, что анализируются нулевые наборы и переменные выписываются с инверсиями. Например, для функции, заданной диаграммой (рис. 20), минимальной КНФ является
Для сравнения найдем минимальную ДНФ:
В данном случае ДНФ оказалась проще. В общем случае о сравнительной сложности минимальных ДНФ и КНФ нельзя говорить заранее.
