Предыдущая страница реферата | 3  4  5  6  7  8  9  10  11  12  13 | Следующая страница реферата

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

|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

Рекомендуем скачать другие рефераты по теме: реферат на тему менеджмент, класс.





Предыдущая страница реферата | 3  4  5  6  7  8  9  10  11  12  13 | Следующая страница реферата