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

Любому кубу из К(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)Дополнение множества кубов,принадлежащих ядру покрытия таким минимальным подмножеством из максимальных кубов,не входящих в ядро покрытия,для получения покрытия с минимальной ценой.

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

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

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

ПРИМЕР: (минимизация булевой функции методом Квайна-Мак-Класки)

1) f⁴(x)=V(0,1,5,7,8,10,12,14,15)

(f=1)

f⁴(x)=&(2,3,4,6,9,11,13)

(f=0)

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

В операцию склеивания в этом случае могут вступать только кубы,относящиеся к соседним подмножествам,то есть отличающиеся на единицу

ì 000X ü

ï X000 ÷ K°(f)=C°(f)

ï 0X01 ÷

Z(f)= í 01X1 ý S^=36

ê X111 ú S^=45

ê 111X ú

î 1XX0 þ

K¹(f)=C¹(f) S^=103=30

S^=40

Z(f)=C³(f) S^=20

S^=27

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

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

Выполнение этого этапа реализуется с помощью таблицы покрытий.

Kаждая строка таблицы - максимальный куб(простая импликанта).

Каждый столбец - существенная вершина булевой функции (безразличные наборы не включаются).

Элементы этой таблицы отражают отношение покрытия,то есть на пересечении i-ой строки и j-ого столбца ставится некоторая отметка в том случае если i-ый максимальный куб покрывает j-ую вершину.

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

единицы(нуля).

Существенные вершины

	макс. Кубы
A	000X	*	*			|	|	|	|
B	X000	*				| *	|	|	|
C	0X01		*	*		|	|	|	|
D	01X1			*	*	|	|	|	|
E	X111				*	|	|	|	|	*
F	111X					|	|	|	|	*
	1XX0					| *	| *	| *	| *
		a	b	c	d	|	|	|	|	e

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

Т(f)={1XX0}

3) Определение множества минимальных покрытий.

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

Реализацию этого этапа целесообразно производить с использованием упрощенной таблицы.

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

Для решения задачи 3-го этапа можно использовать один из 3-х методов или их комбинацию:

1) Метод простого перебора

2) Метод Петрика

3) Дальнейшее упрощение.

1)На данном этапе целесообразно ввести обозначение максимальных кубов и существенных вершин.

Максимальные кубы обозначены в таблице А...F

1-ый метод целесообразно применять для упрощенной таблицы небольшого объема.Этот метод не дает гарантии получения всех максимальных покрытий.

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

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

ì Tü ì Tü

C _min¹(f)= êAú C _min ¹(f)= êBú,...

ïCú êCú

îE þ îE þ

2)Достоинство этого метода-получение всех минимальных покрытий.

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

Y=(AvB)(AvC)(CvD)(DvE)(EvF)=(AvBC)(DvCE)(EvF)=

=(AvBC)(DEvCEvDFvCEF)=

=(ADEvACEvADFvBCDEvBCEvBCDF)

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

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

3) Дальнейшее упрощение состоит в применение двух операций: а)Вычеркивание лишних строк.

б)Вычеркивание лишних столбцов.

Если множество меток i-й строки является подмножеством меток j-й строки и куб i имеет небольшую размерность, чем куб j, то из таблицы можно вычеркнуть i-ю строку так как существенные вершины покрываемые i-м кубом будут с гарантией покрыты j-м кубом.

В дальнейшем рекомендуется построить новую упрошенную таблицу.

В отношении новой таблицы можно использовать один из трех методов: 1) Метод простого перебора.

2)Метод Петрика.

3)Дальнейшее упрощение.

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