 |
Покрытия булевых функций .
|
|
|
|
Между кубами различной размерности, входящих в кубический комплекс K(f), существует отношение включения или покрытия. Принято говорить, что куб А меньшей размерности покрывается кубом Б большей размерности, если куб А включается в куб Б. Это означает, что при образовании куба Б хотя бы в одном склеивании учавствует куб А.
Отношение включения (покрытия) между кубами принято обозначать АÌБ. В теории множеств отношение включения связывает между собой некоторое множество и его подмножества.
Для рассмотренного примера отношения включения имеют место между 001Ì0х1; 011Ìx11Ìx1x... любой 1-куб покрывает 2 0-куба, 2-куб - 4 0-куба и 2 1-куба, 3-куб покрывает 8 0-кубов, 12 1-кубов и 6 2-кубов.
Покрытием булевой функции f называется такое подмножество кубов из кубического комплекса K(f), которое покрывает все существенные вершины функции.
В связи с тем, что любому кубу комплекса K(f) можно поставить в соответствие конъюнктивный терм, для любого покрытия можно представить некоторую ДНФ булевой функции.
Частным случаем покрытия булевой функции является кубический комплекс K0(f), покрытие c0(f)=K0(f). Этому покрытию соответствует КДНФ.
Для примера покрытием является также
|0x1
|01x
c1(f)=K1(f)=|x10
|x11
|11x
этому покрытию соответствует ДНФ вида
_ _ _ _ _ _ _ _ _ _
f=x1x3vx1x2vx2x3vx2x3vx1x2 приведенная ДНФ не является минимальной.
В качестве минимальной еще одного покрытия можно использовать множество максимальных кубов
|0x1
c2(f)=|x1x
Действительно, куб 0х1 покрывает существенные вершины 0х1É(001, 011), а куб x1xÉ(010, 011, 110, 111).
Множество максимальных кубов булевой функции всегда является ее покрытием.
|
|
|
Покрытие c2(f) соответствует ДНФ вида х1х3vx2. Эта ДНФ является минимальной. Покрытие булевой функции, которое соответствует минимальной ДНФ называется минимальным покрытием.
Минимальное покрытие должно состоять только из максимальных кубов.
В частном случае все множество максимальных кубов является минимальным покрытием. Это справедливо для нашего примера. В общем случае множество максимальных кубов является избыточным и для получения минимального покрытия достаточно взять некоторое его подмножество.
Пример: f3(x)=V(0,1,4,6,7)
(f=1)
|000 (1) |00x (1-2)
|001 (2) |x00 (1-3)
K0(f)=|100 (3) K1(f)=|1x0 (3-4)
|110 (4) |11x (4-5)
|111 (5)
Для данного примера множество максимальных кубов совпадает с комплексом K1(f). Z(f)=K1(f)
Минимальными покрытиями являются
|00x |00x
с1(f)=|11x c2(f)=|11x
|x00 |1x0
Из анализа покрытия существенных вершин максимальными кубами из комплекса K1(f) следует:
1) Куб 00х должен обязательно включаться в покрытие, так как только он покрывает существенную вершину 001, аналогично 11х покрывает 111.
Множество максимальных кубов без которых не может быть образовано покрытие булевой функции называется ядром покрытия T(f)=|00x
|11x
2) Так как ядром покрытия кроме существенных вершин 001 и 111 покрываются также существенные вершины 000 и 110, то не покрытой ядром остается только существенная вершина 100. Для ее покрытия достаточно взять 1 из оставшихся максимальных кубов (х00 или 1х0).
Выводы:
Задача получения минимальной ДНФ сводится к задаче получения минимального покрытия.
Получение минимального покрытия реализуется в таком порядке: а) Находится множество максимальных кубов б) Выделяется ядро покрытия в) Из максимальных кубов, не вошедших в ядро, выбирается такое минимальное подмножество, которое покрывает существенные вершины, не покрытые ядром.
|
|
|
Цена покрытия.
Цена r-куба представляет собой количество несвязанных координат. Sr=n*r
Для оценки качества покрытия используют два вида цены покрытия:
m
1) Sa=åSrNr, где Nr - количество r-кубов, входящих в по-
r=0
крытие, m - максимальная размерность куба. Цена Sa представляет собой сумму цен кубов, входящих в покрытие.
2) Sb=Sa+k, где k - количество кубов, входящих в покрытие
m m
Sa =å(n-r) Nr ; Sb=å(n-r)(Nr+1)
r=0 r=0
Под минимальным покрытием понимают покрытие, обладающее минимальной ценой Sa по сравнению с любым другим покрытием этой функции.
Можно показать, что покрытие, обладающее минимальной ценой Sa обладает также и минимальной ценой Sb.
Пример: f3(x)=V(0,1,4,6,7)
(f=1)
C0(f)=K0(f); Sa=5*3=15; Sb=Sa+5=20
C1(f)=K1(f); Sa=4*2=8; Sb=Sa+4=12
Cmin(f): Sa=3*2=6; Sb=9
Цена покрытия Sa представляет собой количество букв, входящих в ДНФ, которая соответствует данному покрытию.
Цена Sb представляет для ДНФ сумму количества букв и количества термов.
Цена покрытия хорошо согласуется с ценой схемы по Квайну, которая строится по нормальной форме, соответствующей этому покрытию.
Для приведенной схемы цена по Квайну SQ=9=Sb (9-число входов).
В принципе, между SQ и ценами Sa и Sb существует соотношение Sa £ SQ £ Sb Это неравенство имеет место при следующих допущениях по комбинационной схеме:
1) Схема строится по нормальной форме (ДНФ или КНФ).
2) Схема строится на элементах булевого базиса (И, ИЛИ).
3) На входы схемы можно подавать как прямые, так и инверсные значения входных переменных, представляющие собой значения аргументов булевой функции (схема с парафазными входами). Элементы НЕ (инвертора в схеме отсутствуют.
|
|
|
