Покрытия булевых функций.
Геометрическая интерпретация кубов малой размерности. Графическое представление булевых функций.
Подобный подход носит ограниченный характер и как правило является наглядным для булевых функций от 2-х и 3-х переменных.
F3(x)=V(1,2,3,6,7)
(f=1)
Геометрическим местом 0-куба является точка, представляющая существенную вершину.
Два соседних 0-куба являются концами какого-либо ребра.
Геометрическим местом 1-куба является ребро, замыкаемое склеивающимися 0-кубами, образующими данный 1-куб.
Два параллельных ребра, образующих грань, являются образами склеивающихся 1-кубов. В соответствии с этим геометрической интерпретацией 2-куба является грань, образуемая парой параллельных ребер. Так как любую грань можно определить одной из пар параллельных ребер, 2-куб может быть получен как результат склеивания двух различных пар 1-кубов, то есть представляется в двух экземплярах.
Геометрическим образом 3-куба можно считать 3-х мерный куб. Так как он может быть образован 3-мя способами как пара параллельных граней, то при склеивании он получается в трех экземплярах.
Между кубами различной размерности, входящих в кубический комплекс 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).
Выводы :
Задача получения минимальной ДНФ сводится к задаче получения минимального покрытия.
Получение минимального покрытия реализуется в таком порядке : а) Находится множество максимальных кубов б) Выделяется ядро покрытия в) Из максимальных кубов, не вошедших в ядро, выбирается такое минимальное подмножество, которое покрывает существенные вершины, не покрытые ядром.