Покрытия булевых функций

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

Отношение включения (покрытия) между кубами принято обозначать А Ì B. В теории множеств отношение включения связывает между собой некоторое множество и его подмножества.

Для рассмотренного примера отношения включения имеют место между следующими кубами: 001Ì0Х1; 011ÌХ11ÌХ1Х. Любой 1-куб покрывает два 0-куба, 2-куб - четыре 0-куба и четыре 1-куба, 3-куб покрывает восемь 0-кубов, двенадцать 1-кубов и шесть 2-кубов (см. геометрическую интерпретацию).

Определение. Покрытием булевой функции f называется такое подмножество кубов из кубического комплекса K(f), которое покрывает все существенные вершины функции.

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

Частным случаем покрытия булевой функции является кубический комплекс K⁰(f), покрытие C₀(f)=K⁰(f). Этому покрытию соответствует КДНФ.

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

.

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

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

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

.

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

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

Покрытию С₂(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) МДНФ=КДНФ;

2) C_min(f) = Z(f) МДНФ=СДНФ;

3) C_min(f) Ì Z(f);

а) C_min(f) = T(f);

б) T(f) Ì C_min(f);

в) T(f) = Æ.