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

К конъюнкциям произвольной д.н.ф. 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)),

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