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

Минимизация монотонных функций

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

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

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

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

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

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

Для первого этапа: соотношения склеивания по Квайну

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

Пример: функция, заданная МДНФ дает возможность определить ее СкКНФ:

По диаграмме Вейча для поиска МКНФ анализируются лишь нулевые наборы и переменные выписываются с инверсиями:

МKНФ:

МДНФ:

Дата добавления: 2014-01-06