FINISH (675729), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

|11x

1. Так как ядром покрытия кроме существенных вершин 001 и 111 покрываются также существенные вершины 000 и 110, то не покрытой ядром остается только существенная вершина 100. Для ее покрытия достаточно взять 1 из оставшихся максимальных кубов (х00 или 1х0).

Выводы :

Задача получения минимальной ДНФ сводится к задаче получения минимального покрытия.

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

Цена покрытия.

Цена r-куба представляет собой количество несвязанных координат. Sr=n*r

Для оценки качества покрытия используют два вида цены покрытия :

m

1. S^a=åS_rN_r, где N_r - количество r-кубов, входящих в по-

r=0

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

1. 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)

C⁰(f)=K⁰(f) ; S^a=5*3=15 ; S^b=S^a+5=20

C¹(f)=K¹(f) ; S^a=4*2=8 ; S^b=S^a+4=12

C_min(f) : S^a=3*2=6 ; S^b=9

Цена покрытия S^a представляет собой количество букв, входящих в ДНФ, которая соответствует данному покрытию.

Цена S^b представляет для ДНФ сумму количества букв и количества термов.

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

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

В принципе, между S_Q и ценами S^a и S^b существует соотношение S^a £ S_Q £ S^b Это неравенство имеет место при следующих допущениях по комбинационной схеме :

1. Схема строится по нормальной форме (ДНФ или КНФ).

2. Схема строится на элементах булевого базиса (И, ИЛИ).

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

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

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

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

Нулевое покрытие строится также как и единичное, но только для отрицания исходной функции.

f³(x)=V(0,1,4,6,7) f³(x)=&(2,3,5)

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

K⁰( f )=|011

_ _ |101

C0( f )= K⁰( f ) S^a=9 S^b=12

_ _ _

K1( f )=|01x Z( f )=C_min( f )=|01x S^a=5 S^b=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) и j(x) являются импликантами функции f(x), то их дизъюнкция также является импликантой этой функции.

Простейшими примерами импликант могут служить конъюнктивные термы, входящие в ДНФ данной функции.

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

(f=1) _ _ _

импликантами являются х₁х₂х₃; х₁х₂х₃; х₁х₂;...

Произвольная дизъюнкция этих термов также является импликантой функции.

Определение : Простой (первичной) импликантой булевой функции называется конъюнктивный терм, который сам является импликантой этой функции, но никакая его собственная часть уже не является импликантой этой функции.

Под собственной частью терма понимается новый терм, полученный из исходного, путем вычеркивания произвольного числа букв.

Для данного примера функции (#) простыми импликантами являются : _ _ _

х₁х₂х₃; х₁х₂х₃; х₁х₂;...

Множеству простых импликант можно поставить в соответствие множество максимальных кубов.

Определение : Дизъюнкция всех простых импликант булевой функции представляет собой ДНФ этой функции, которая называется сокращенной - СДНФ.

Для функции (#) из приведенного примера

_ _ _ _ _

СДНФ : y= х₁х₂v х₁х₂vх₂х₃v х₁х₃

Понятие «сокращенное» присвоено ДНФ в том смысле, что она, как правило, содержит меньшее количество букв и термов по сравнению с КДНФ. Для нашего примера КДНФ содержит 15 букв и 5 термов, а СДНФ - 8 букв и 4 терма.

Аналогия между импликантами и кубическим представлением Булевой функции

Любому кубу из К(f) можно поставить в соответствие конъюнктивный терм который можно рассматривать как импликанту булевой функции .Любой простой импликанте булевой функции соответствует максимальный куб ,и в свою очередь множество всех простых импликант соответствует множеству Z(f) всех максимальных кубов К(f).

Таким образом можно провести некоторую аналогию между сокращенной СДНФ и Z(f).

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

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

ПРИМЕР : импликанта х₁х₂ покрывает существенные вершины (110,111) и в свою очередь покрывает куб 11х.

Определение :множество импликант булевой функции образует полную систему импликант ,если любая существенная вершина булевой функции покрывается хотя бы одной импликантой этого множества.

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

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

Определение :система простых импликант называется приведенной ,если она является полной ,а никакая ее собственная часть уже не образует полную систему импликант.

Для функции y= x ₁ x ₂ Ú _{1 2}Ú _{2 3} Ú x _{1 3} (*)

система простых импликант

{ x ₁ x ₂, _{1 2} , _{2 3} , x _{1 3} }

является полной ,но не является приведенной ,т.к. из нее можно исключить одну из импликант не нарушая полноты системы .{ _{2 3} или x_{1 2}}

Определение: Дизъюнкция всех простых импликант ,образующих некоторую приведенную систему называется тупиковой ДНФ булевой функции или ТДНФ

Для функции (*) существуют две ТДНФ

1) у= x ₁ x ₂Ú _{1 2}Ú _{2 3}

2) у= x ₁ x ₂Ú _{1 2}Ú x _{1 3}

В данном случае они совпадaют с минимальной ДНФ. Но в общем случае это утверждение не справедливо. Т.е. минимальная ДНФ обязательно является ТДНФ но не любая ТДНФ является МДНФ. Таким образом множество МДНФ является подмножеством ТДНФ.

Определение: простая импликанта булевой функции называется существенной если она и только она покрывает некоторую существенную вершину этой функции.

Множество существенных импликант соответствует максимальным кубам образующим ядро покрытия.

ПОСЛЕДОВАТЕЛЬНОСТЬ действий для решения канонической задачи минимизации методом Квайна-Мак-Класки.

1)Нахождение множества максимальных кубов или простых импликант функции.

2)Выделение ядра покрытия.

3)Дополнение множества кубов ,принадлежащих ядру покрытия таким минимальным подмножеством из максимальных кубов ,не входящих в ядро покрытия ,для получения покрытия с минимальной ценой.

С точки зрения последовательного преобразования ДНФ булевой функции с целью их упрощения каноническая задача минимизации может быть представлена в виде КДНФ.

КДНФÞСДНФÞ{ТДНФ}Þ{МДНФ}

Распространение терминологии в отношении нулевого покрытия определяется на понятии импликанта как соответствие импликанте и на системе импликант.

Характеристики

Список файлов реферата