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

Под минимальным покрытием понимают покрытие, обладающее минимальной ценой 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 представляет для ДНФ сумму количества букв и количества термов.

[pic]

Цена покрытия хорошо согласуется с ценой схемы по Квайну, которая строится по нормальной форме, соответствующей этому покрытию.

Для приведенной схемы цена по Квайну SQ=9=Sb (9-число входов).

В принципе, между SQ и ценами Sa и Sb существует соотношение Sa ( SQ
( Sb Это неравенство имеет место при следующих допущениях по комбинационной схеме :
1) Схема строится по нормальной форме (ДНФ или КНФ).
2) Схема строится на элементах булевого базиса (И, ИЛИ).
3) На входы схемы можно подавать как прямые, так и инверсные значения входных переменных, представляющие собой значения аргументов булевой функции (схема с парафазными входами). Элементы НЕ (инвертора в схеме отсутствуют.

Нулевое покрытие булевой функции и получение минимальной КНФ.

Выше было рассмотрено покрытие булевой функции на наборах аргументов для которых функция равна единице.

Такие покрытия можно назвать единичными. Наряду с единичными покрытиями существуют и нулевые, для которых покрываются наборы аргументов, на которых функция равна нулю, то есть покрытие реализуется для существенных вершин, но не самой функции, а ее отрицания (инверсии).

Нулевое покрытие строится также как и единичное, но только для отрицания исходной функции. f3(x)=V(0,1,4,6,7) f3(x)=&(2,3,5)

(f=1) (f=0) _ |010

K0( f )=|011

_ _ |101
C0( f )= K0( f ) Sa=9 Sb=12

_ _ _
K1( f )=|01x Z( f )=Cmin( f )=|01x Sa=5 Sb=7

|101

Цена минимального нулевого покрытия оказалась меньше цены минимального единичного покрытия.

Так как заранее предсказать невозможно, какое из минимальных покрытий данной функции, единичное или нулевое, будет иметь меньшую цену, то для построения схемы, обладающей минимальной ценой по Квайну, целесообразно решать задачу минимзации в отношении обоих покрытий.

Импликанты булевой функции.

Системы импликант.

Решение задачи минимизации булевой функции методом Квайна и усовершенствованным методом Квайна-МакКласски базируется на понятиях импликант и их систем.
Определение : Булева функция g(x) называется импликантой булевой функции f(x), если для любого набора аргументов, на которых g(x)=1, f(x) также равна единице.

~ ~ ~ g( x )=1 => f( x )=1, где х - некоторый набор аргументов.
Свойства импликант :
1) Между импликантой и самой функцией существует отношение включения g(x)(f(x).
2) Можно утверждать, что для любого набора аргументов, на котором функция равна нулю, ее импликанта также равна нулю.
3) Если g(x) и ((x) являются импликантами функции f(x), то их дизъюнкция также является импликантой этой функции.

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





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