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

 

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

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

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

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

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

 

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

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

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

МKНФ:

МДНФ:

 

 






Дата добавления: 2016-07-18; просмотров: 1607; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2020 год. Материал предоставляется для ознакомительных и учебных целей. | Обратная связь
Генерация страницы за: 0.007 сек.