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

Утверждение

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

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

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

Замечание.

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

Метод построения сокращённой д.н.ф. с помощью обобщенного склеивания

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

1)поглощение

,

2)обобщённое склеивание

(Подразумевается, что все преобразования выполняются только слева направо).

.

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

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

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

Рассмотрим теперь множество конъюнкций , удовлетворяющих трём условиям:

1. содержит только те переменные, которые входят в D;

2. ;

3. для всех конъюнкций H из д.н.ф. D.

Множество конъюнкций содержит конъюнкциюK, и, следовательно, непусто. Выберем в нём конъюнкции наибольшего ранга . Рассмотрим конъюнкцию. Она не может содержать все переменные, входящие вD, так как в этом случае интервал , состоял бы из одной вершины, а это вело бы к нарушению условия 3. Возьмём переменнуюx, от которой зависит D и не зависит . Рассмотрим конъюнкциии. Они удовлетворяют условиям 1 и 2 и имеют ранг больший, чем ранг. Значит,ине удовлетворяют условию 3, т.е. В д.н.ф. D имеются конъюнкцииитакие, что,. В конъюнкцию входит сомножительx, так как и. Поэтому

, где,.

Отсюда уже ясно, что при выполнении преобразований 4 на некотором шаге в д.н.ф. Будет включена либо конъюнкция , либотакая, что. Тоже самое верно и для конъюнкций. После этого конъюнкция наибольшего ранга, удовлетворяющая условиям 1, 2 и 3, будет иметь ранг меньшей чем. Следовательно, на некотором шаге в д.н.ф. Будет включена и конъюнкцияK.

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

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

Пример 4. Рассмотрим функцию f(x,y,z) заданную таблицей 1 (§ 1), и её совершенную д.н.ф:

Имеем

(правило 1)),

(правило 1)),

(правило 4) и 2)),

(правило 4)),