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

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

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

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

Такие покрытия можно назвать единичными. Íàðÿäó ñ åäèíèчными покрытиями существуют и нулевые, для которых покрываются наборы аргументов, на которых функция равна нулю, то есть покрытие реализуется для существенных вершин, но не самой функции, а ее отрицания (инверсии).

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

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 терма.

Дата добавления: 2014-11-29