Достаточно ясна связь задачи нахождения тупиковых покрытий и минимизации функции покрытия

.

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

Примечание: Операцию поглощения можно применять в процессе раскрытия скобок.

Корректность этой операции следует из примера. Раскрывая скобки, получаем

Мы применяем поглащение в процессе раскрытия скобок в силу того, что покрытия содержащие пару интервалов не будут тупиковыми- соответствующие слагаемое, которое будет содержать только будет короче.

Тупиковые покрытия максимальными интервалами:

;

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

;

Утверждение

Множество тупиковых покрытий функции есть в точности множество всех максимальных интервалов функции покрытия .

Легко установить следующее.

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

Замечание.

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

Дата добавления: 2017-01-13