Размерности. Соответствие между покрытием и ДНФ булевой функции

Между кубами различной размерности, входящими в кубический комплекс K(f), существует отношение включения или покрытия . При этом принято говорить, что куб А меньшей размерности покрывается кубом B большей размерности. Куб А включается в куб B, если при образовании куба B хотя бы в одном склеивании участвует куб А.

Отношение включения (покрытия) между кубами обозначается:

  А Ì B. В теории множеств отношение включения связывает между собой некоторое множество и его подмножества. Для примера отношения включения имеют место между следующими кубами: 001Ì 0Х1; 011Ì Х11Ì Х1Х.

Любой 1-куб покрывает два 0-куба, 2-куб - четыре 0-куба и четыре 1-куба, 3-куб покрывает восемь 0-кубов, двенадцать 1-кубов и шесть 2-кубов (см. рис.2.1).

 

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

 

Покрытием булевой функции f называется такое подмножество кубов из кубического комплекса K(f), которое покрывает все существенные вершины функции. В связи с тем, что любому кубу комплекса K(f) можно поставить в соответствие конъюнктивный терм, для произвольного покрытия C(f)можно составить ДНФ булевой функции. Частным случаем покрытия булевой функции является кубический комплекс K ⁰(f) (C ₀(f)= K ⁰(f)). Этому покрытию соответствует КДНФ.

Для примера 2.10 покрытием является также комплекс K ¹(f):

                                  .

Этому покрытию соответствует ДНФ вида:

 которая не является минимальной. В качестве еще одного варианта покрытия можно использовать множество максимальных кубов. Для примера 2.10:

                      .

Действительно, кубы, входящие в Z(f), покрывают все существенные вершины: 0Х1É (001, 011), Х1ХÉ (010, 011, 110, 111).

 

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

 

Покрытию С₂(f) соответствует ДНФ вида:  

Эта ДНФ является минимальной.

Покрытие булевой функции, которое соответствует минимальной ДНФ, называется минимальным покрытием и обозначается С _min ( f ).

Замечание: Минимальное покрытие должно состоять только из максимальных кубов.

 

Множество максимальных кубов булевой функции лишь в частном случае может являться минимальным покрытием. Это справедливо для рассмотренного выше примера 2.10. В общем случае, множество максимальных кубов является избыточным и для получения минимального покрытия достаточно выделить некоторое его подмножество. Рассмотрим подобный случай на примере.

Пример 2.11. Минимизируемая булева функция задана в числовой форме:

 Найти ее минимальное покрытие и МДНФ.

По числовой форме булевой функции составим ее кубический комплекс K ⁰(f):

Произведя всевозможные операции склеивания между 0-кубами, получим кубический комплекс K ¹(f):

Все 0-кубы функции вступили хотя бы в одну операцию склеивания и, следовательно, среди них нет максимальных. Кроме того, среди 1-кубов функции нет соседних (K ²(f)= Æ ). Следовательно, для данного примера множество максимальных кубов совпадает с кубическим комплексом K ¹(f): Z(f)= K ¹(f).

Множеству максимальных кубов, образующих покрытия булевой функции, соответствует ДНФ, которая называется сокращенной (СДНФ).

Для рассматриваемого примера СДНФ:

 

Из анализа покрытия существенных вершин максимальными кубами из комплекса K ¹(f) следует:

1. Куб (00Х) должен обязательно включаться в покрытие, так как он и только он покрывает существенную вершину (001), аналогично, только куб (11Х) покрывает существенную вершину (111).

Множество максимальных кубов, без которых не может быть образовано покрытие булевой функции, называется ядром покрытия и обозначается T(f): T(f)={00Х, 11Х}.

2. Так как ядром покрытия, кроме существенных вершин (001) и (111), покрываются также существенные вершины (000) и (110), то не покрытой ядром остается только существенная вершина (100). Для ее покрытия достаточно взять любой из оставшихся максимальных кубов: (Х00) или (1Х0).

Таким образом, для рассматриваемого примера получены два минимальных покрытия:

        ;

которым соответствуют МДНФ:

               и

Выводы:

1.  Задача получения минимальной ДНФ сводится к задаче получения минимального покрытия булевой функции.

2.  В общем случае: получение минимального покрытия осуществляется в следующем порядке:

а) находится множество максимальных кубов;

б) выделяется ядро покрытия;

в) из множества максимальных кубов, не вошедших в ядро, выбирается такое минимальное подмножество, которое покрывает существенные вершины, не покрытые ядром.

3.  Частными случаями могут являться:

1. C_min(f) = K ⁰(f). Минимальное покрытие совпадает с кубическим комплексом K ⁰(f). При этом МДНФ совпадает с КДНФ;

2. C_min ( f ) = Z ( f ). Минимальное покрытие совпадает с множеством максимальных кубов Z ( f ). При этом МДНФ совпадает с СДНФ;

3. C_min(f) Ì Z(f). Минимальное покрытие представляет собой некоторое подмножество множества максимальных кубов. При этом могут иметь место следующие случаи:

а) C_min(f) = T(f). Минимальное покрытие совпадает с ядром.

б) T(f) Ì C_min(f). Минимальное покрытие включает в себя ядро, как обязательную часть, и дополняется минимальным числом максимальных кубами, не принадлежащими ядру и покрывающих существенные вершины, которые не покрыты ядром.

в) T(f) = Æ . Ядро покрытия отсутствует. Покрытие формируется из минимального числа максимальных кубов. Данный случай является наиболее сложным для получения минимального покрытия.

Цена покрытия

Цена покрытия используется при решении задачи минимизации булевых функций как количественная оценка качества покрытия в смысле его минимальности. Эта оценка базируется на понятии цены кубов, составляющих покрытие. Цена r-куба ( S_r ) представляет собой количество несвязанных координат:   S_r = n – r.

Принято использовать два вида цены покрытия: S^a и S^b.

где N_r - количество r-кубов, входящих в покрытие, m - максимальная размерность кубов, входящих в покрытие. Цена S^a представляет собой сумму цен кубов, входящих в покрытие.

где k – общее количество кубов, входящих в покрытие.

Минимальным покрытием булевой функции называется покрытие, обладающее минимальной ценой S^a по сравнению с любым другим покрытием этой функции.

Можно показать, что покрытие, обладающее минимальной ценой S^a, обладает также и минимальной ценой S^b.

Пример 2.12. Определить цены покрытий функции  из примера 2.11.

C₀(f)=K⁰(f):             S^a=5× 3=15;      S^b=S^a+5=20;

C₁(f)=K¹(f):             S^a=4× 2=8;        S^b=S^a+4=12;

C ₂(f)= C_min(f):          S^a=3× 2=6;       S^b=9.

 

Цены покрытия S^a и S^b связаны с ДНФ, соответствующей этому покрытию, следующим образом:

- цена покрытия S^a представляет собой количество букв, входящих в ДНФ;

- цена S^b представляет сумму количества букв и количества термов, образующих ДНФ.

Цена покрытия хорошо согласуется с ценой схемы, построенной по нормальной форме функции, соответствующей этому покрытию.

Пример 2.13. Построить логическую схему, реализующую булеву функцию по МДНФ из примера 2.11. Определить цену схемы по Квайну и сравнить ее значение с ценами покрытия S^a и S^b.

В качестве исходного аналитического выражения для построения схемы возьмем МДНФ функции f ₂(X):  В качестве системы логических элементов используем элементы булева базиса {И, ИЛИ, НЕ}, при этом на элементах И реализуем конъюнктивные термы, а элементы ИЛИ используем для реализации дизъюнкции конъюнктивных термов. Будем, кроме того, строить схему с парафазными входами, в следствии чего элементы НЕ (инверторы) не понадобятся.

Для интерпретации выражения для МДНФ в схему представим его в следующем виде:

  И(2) И(2) И(2)

          ИЛИ(3)

где показано соответствие термов функции и логических элементов схемы. Значения аргументов булевой функции и их инверсий интерпретируется в схеме в виде входных сигналов, а значение самой функции интерпретируется в виде выходного сигнала у.

Логическая схема приведена на рис. 2.3.

 Рис. 2.3. Логическая схема, построенная по покрытию С₂ примера 2.11.

 

Цена схемы по Квайну, опреледяемая суммарным числом входов во все логические элементы схемы:  S_Q =2*3 (входы в элементы И) + 1*3 (входы в элемент ИЛИ) =9.

В свою очередь, цены покрытия по МДНФ, по которой строилась схема, S^a =6, S^b =9. Таким образом S^a < S_Q = S^b

Замечание. В принципе, между ценой схемы S_Q и ценами покрытия S^a и S^b существует соотношение: S^a £ S_Q £ S^b, которое выполняется при следующих допущениях:

1. Схема строится по нормальной форме (ДНФ или КНФ).

2. Схема строится на элементах булевого базиса (И, ИЛИ).

3. На входы схемы подаются как прямые, так и инверсные значения аргументов булевой функции (схема с парафазными входами). В соответствии с этим элементы НЕ (инверторы) в схеме отсутствуют.

Задание (на освоение материала).

В отношении минимального покрытия или МДНФ сформулировать условия, при которых:

1. S_Q = S^b;

2. S_Q = S^a;

3. S^a < S_Q < S^b.

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: