Нулевое покрытие булевой функции

И получение минимальной КНФ

Выше было рассмотрено покрытие булевой функции на наборах аргументов для которых функция равна единице. Такие покрытия можно назвать единичными. Наряду с единичными покрытиями существуют и нулевые, для которых покрываются наборы аргументов, на которых функция равна нулю, то есть покрытие реализуется для существенных вершин, но не самой функции, а ее отрицания (инверсии). Нулевое покрытие строится также как и единичное, но только для отрицания исходной функции [12-14].

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

Пример 5.2.

В результате выполнено перекрытие четырех интервалов 3^го ранга двумя интервалами 2^го ранга. Таким образом, установлено взаимо-однозначное соответствие между заданием функции в виде ДНФ и покрытием множества Т для данной функции интервалами некоторого ранга.

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

(5.5.)

есть суммарный ранг ДНФ, который численно совпадает с числом букв, входящих в ДНФ. Тогда задача о минимизации есть задача нахождения такого покрытия множества Т, которое имеет минимальный суммарный ранг R. Интервал Y называется максимальным, если не существует другого интервала с рангом, меньшим, чем у Y, и такого, что

Пример 5.3.

Решение. Здесь интервал является максимальным, а , не являются максимальными. Интервал тоже является максимальным.

ДНФ, соответствующая покрытию множества Т всеми максимальными интервалами, называется сокращенной ДНФ.

Пример 5.4.

Сокр. ДНФ

Очевидно, что Сокр. ДНФ не является минимальной, т. к. МДНФ в этом примере

Пример 5.5.

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

Пример 5.6.

Для

существует две МДНФ:

Сравнив все ТДНФ по числу букв, можно определить МДНФ.

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