Реферат: Конспект лекций по дискретной математике

|110 (4) |11x (4-5)

|111 (5)

Для данного примера множество максимальных кубов совпадает с комплексом K¹ (f). Z(f)=K¹ (f)

Минимальными покрытиями являются

|00x |00x

с¹ (f)=|11x c² (f)=|11x

|x00 |1x0

Из анализа покрытия существенных вершин максимальными кубами из комплекса K¹ (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) S^a =åS_r N_r , где N_r - количество r-кубов, входящих в по-

r=0

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

2) S^b =S^a +k, где k - количество кубов, входящих в покрытие

m m

S^a =å(n-r) N_r ; S^b =å(n-r)(N_r +1)

r=0 r=0

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

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

Пример : f³ (x)=V(0,1,4,6,7)

(f=1)