гос / Theme4

Прикладная теория цифровых автоматов. Тема №4

x

x

x x

x x

x

x

x

2

x

3

x

x

2

x

2

x

2

x

2

1

1

3

1

3

1

3

1

3

A

x

x

2

*

*

1

B

x

x

*

*

1 3

x2

3

*

*

C

x

D

x x

2

*

*

1

Конъюнктивное представление:

ϕ = ( A + B) A(B + C)(C + D)D = AD(B + C) = ADB + ADC .

Из конъюнктивного представления видно, что тупиковых форм две. Одна

соответствует конъюнкции ADB , вторая – конъюнкции ADC .

Аналитический вид ТДНФ можно получить, выписав импликанты,

соответствующие буквам конъюнкций:

ADB : ТДНФ1( f )= x1x2 + x1x2 + x1x3 ,

ADC : ТДНФ2( f )= x1x2 + x1x2 + x2 x3 .

Метод Блейка – Порецкого

Этот метод позволяет перейти от произвольной дизъюнктивной

(конъюнктивной) нормальной формы к сокращенной дизъюнктивной

(конъюнктивной) нормальной форме. По сути метод Блейка – Порецкого

аналогичен методу Квайна, если соотношение склеивания заменить соотношением обобщенного склеивания:

для дизъюнктивных

форм,

A и B

– любые

Ax + Bx

= Ax + Bx + AB

выражения;

( A + x)(B +

) = ( A + x)(B +

)( A + B)

для конъюнктивных форм,

A и B –

x

x

любые выражения.

Пример 4.5 Методом

Блейка –

Порецкого найти

СкДНФ

функции,

заданной выражением:

1

2

3

4

f (x1, x2 , x3 , x4 ) = x1x2 x3

+ x1

2 x3x4 + x1

3 x4 + x1

4 .

x

x

x

*

*

*

*

© Р. С. Цвентарный, 2009

11

Прикладная теория цифровых автоматов. Тема №4

Далее производятся все возможные обобщенные склеивания и поглощения.

При этом выписываются только неповторяющиеся импликанты.

(1:2) x x x				4	* A	(3:4) x	x			* E	(F:4) или (E:H) x
1	3					1	3				1
(1:3) x1x2 x4					* B	(A:E) x1x4 * F
(2:3) x1		2 x4			* C	(D:E) x1				2 * G
	x							x
(2:4) x1			2 x3		* D	(1:D) x1x3 * H
	x

СкДНФ( f )= x1 .

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

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

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

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

f (x1, x2 , x3, x4 ) = x1(x2 x3 + x2 x3x4 + x3x4 + x4 ) = = x1((x2 x3 + x2 x3x4 + x3x4 ) + x3x4 + x4 ) =

= x1(x2 x3 + x2 x3x4 + (x3x4 + x3 x4 + x4 ) + x4 ) =

= x1(x2 x3 + x2 x3x4 + x3 x4 + x3x4 + x4 + x4 ) = x1 ×1 = x1

14243

=1

Метод Нельсона

Этот метод позволяет перейти от произвольной конъюнктивной

(дизъюнктивной) нормальной формы к сокращенной дизъюнктивной

(конъюнктивной) нормальной форме путем применения закона

дистрибутивности.

Пример 4.6 Методом Нельсона найти СкДНФ функции, заданной

выражением:

© Р. С. Цвентарный, 2009

12

Прикладная теория цифровых автоматов. Тема №4

f (x1, x2, x3) = (x1 + x2 )(x1 + x3)(x1 + x2 + x3) .

Для перехода к СкДНФ необходимо раскрыть все скобки и выполнить все

возможные поглощения.

f (x1, x2 , x3 ) = (x1 + x2 )(x1 + x3 )(x1 + x2 + x3 ) =

=(x1x3 + x1x2 + x2 x3 )(x1 + x2 + x3 ) = x1x3 + x1x2 x3 + x1x2 x3 + x1x2 x3 =

=x1x3 + x1x2 x3

Итак, СкДНФ( f )= x1x3 + x1x2 x3 .

Метод неопределенных коэффициентов

Этот метод наиболее применим для нахождения МДНФ. Идея метода состоит в том, что любую функцию можно записать в виде дизъюнкции всех конституэнт единицы и всех возможных импликант, умноженных на соответствующий коэффициент, который может принимать значение 0 или 1.

Например, любую функцию 2-х переменных можно представить в виде:

f (x1, x2 ) = k11x1 + k10 x1 + k12 x2 + k20 x2 + k1200 x1x2 + k1201x1x2 + k1210 x1x2 + k1211x1x2

Для нахождения значений коэффициентов необходимо решить систему:

f (0,0) = k 0		+ k 0	+ k 00
	1	2	12
	0	1	01
f (0,1)	= k1	+ k2	+ k12
	= k11 + k20 + k1210
f (1,0)
f (1,1) = k1 + k1 + k11
	1	2	12

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

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

Исходя из вышеизложенного, можно сформулировать следующий алгоритм минимизации:

1.Строится таблица коэффициентов, представляющая собой расширение таблицы истинности функций, в которой в дополнительных столбцах

перечислены все возможные коэффициенты. Для упрощения записи в

© Р. С. Цвентарный, 2009

13

Прикладная теория цифровых автоматов. Тема №4

таблице можно указывать только значения коэффициентов, отмеченные

в их верхних индексах.

2.Вычеркиваются коэффициенты в строках таблицы, соответствующих нулевым значениям функции.

3.Из столбцов таблицы вычеркиваются все коэффициенты, которые оказались перечеркнутыми в результате выполнения п. 2.

4.К неперечеркнутым коэффициентам применяется процедура всех возможных поглощений. Например, коэффициент k123010 может быть поглощен коэффициентом k1201 или коэффициентом k10 (и не только ими!), так как импликанты при двух последних коэффициентах полностью входят в состав импликанты при первом коэффициенте.

Поглощенные коэффициенты отмечаются звёздочкой («*»).

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

6.Определяется ядро булевой функции. В ядро входят импликанты при тех коэффициентах, которые остались в строках с единичным значением функции по одному. Ядро покрывает те строки таблицы с единичным значением функции, в которых встречаются коэффициенты, равные коэффициентам при импликантах ядра.

7.Выполняется покрытие всех непокрытых ядром строк таблицы с единичным значением функции, и выписываются ТДНФ, из которых затем выбираются МДНФ.

Пример 4.7 Методом неопределенных коэффициентов найти МДНФ

булевой функции, заданной таблицей истинности (табл. 4.2).

Таблица коэффициентов после выполнения пунктов 1 и 2:

© Р. С. Цвентарный, 2009

14

Прикладная теория цифровых автоматов. Тема №4

x1	x2	x3	k1	k2	k3	k12	k13	k23	k123	f
0	0	0	0	0	0	00	00	00	000	1
0	0	1	0	0	1	00	01	01	001	1
0	1	0	0	1	0	01	00	10	010	1
0	1	1	0	1	1	01	01	11	011	0
1	0	0	1	0	0	10	10	00	100	0
1	0	1	1	0	1	10	11	01	101	0
1	1	0	1	1	0	11	10	10	110	1
1	1	1	1	1	1	11	11	11	111	1

Таблица коэффициентов после выполнения остальных пунктов:

x1	x2	x3
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

k1	k2	k3	k12		k13	k23	k123
0	0	0	00		00	00	000*
0	0	1	00		01	01	001*
0	1	0	01		00	10	010*
0	1	1	01		01	11	011
1	0	0	10		10	00	100
1	0	1	10		11	01	101
1	1	0	11		10	10	110*
1	1	1	11		11	11	111*

f

1

1

1

0

0

0

1

1

Как видно по таблице коэффициентов, после выполнения вычеркиваний и поглощений остались неперечеркнутыми и неотмеченными звёздочкой только

коэффициенты k1200 , k1211, k1300 , k1023 . СкДНФ( f )= x1x2 + x1x2 + x1x3 + x2 x3 . В

ядро булевой функции входят импликанты при коэффициентах k 00 и k11 ,

12 12

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

© Р. С. Цвентарный, 2009

15

Прикладная теория цифровых автоматов. Тема №4

быть покрыта выбором импликанты либо при коэффициенте k1300 , либо при k1023 . Таким образом, получены две тупиковые ДНФ одинаковой сложности и,

соответственно, две минимальные ДНФ:

МДНФ1=ТДНФ1( f )= x1x2 + x1x2 + x1x3 ,

МДНФ2=ТДНФ2( f )= x1x2 + x1x2 + x2 x3 .

Метод диаграмм Вейча (карт Карно)

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

чтобы каждой клетке соответствовал свой двоичный набор переменных и наборы, отличающиеся только в одном двоичном разряде, располагались в соседних клетках. На рисунке 4.1 приведены примеры диаграмм Вейча и карт Карно для булевой функции 2-х, 3-х и 4-х переменных. Десятичные номера наборов расположены в клетках диаграммы (карты).

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

для набора 12 на диаграмме для функции 4-х переменных (рис. 4.1)

конституэнта единицы равна x1x2 x3x4 . Видно, что для этого набора грани переменных x1 и x2 не отмечены чертой, а грани переменных x3 и x4 –

отмечены. Конституэнты нуля строятся наоборот: если черта отсутствует, то переменная входит в конституэнту нуля с инверсией, если присутствует – в

прямом виде. Для набора 12 конституэнта нуля выглядит так: x1 + x2 + x3 + x4 .

© Р. С. Цвентарный, 2009

16

Прикладная теория цифровых автоматов. Тема №4

Диаграммы Вейча		Карты Карно

Рисунок 4.1 – Диаграммы Вейча и карты Карно

Вклетки диаграмм (карт) вписываются значения функции,

соответствующие двоичным наборам переменных. Поскольку соседние клетки соответствуют двоичным наборам, отличающимся лишь в одном двоичном разряде, между конституэнтами единицы (нуля) в этих клетках возможно склеивание (см. методы Квайна и Квайна – Мак-Класки). Иными словами,

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

(имплиценте). Если удастся объединить (склеить) 2k единиц (нулей) для функции n переменных, то в простой импликанте (имплиценте),

соответствующей этому объединению, останется n − k переменных. Следует помнить о том, что одна и та же клетка или группа клеток может многократно участвовать в различных склеиваниях. В импликанту (имплиценту),

соответствующую некоторому объединению, входят лишь те переменные,

которые в рамках объединения сохраняют свое значение (прямое или

© Р. С. Цвентарный, 2009

17

Прикладная теория цифровых автоматов. Тема №4

инверсное). Переменные, изменяющие свое значение в рамках объединения,

поглощаются.

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

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

объединяющих все нули в клетках диаграммы. Совокупности этих объединений будет соответствовать совокупность простых имплицент, входящих в МКНФ.

Запись переменных в простые имплиценты МКНФ производится наоборот по отношению к записи переменных в простые импликанты МДНФ: если на диаграмме Вейча объединение нулей покрывается чертой некоторой грани, то переменная, соответствующая этой грани, записывается в простой имплиценте в прямом виде, если же черта не покрывает объединение, то переменная записывается с инверсией.

Следует отметить, что на диаграммах Вейча поглощенные в импликанте

(имплиценте) переменные располагаются на тех гранях, черта которых пересекает соответствующее импликанте (имплиценте) объединение.

Также необходимо обратить внимание на то, что на диаграммах (картах)

соседними являются клетки, расположенные на противоположных краях диаграммы (карты). Иными словами, левый край карты может склеиваться с правым, а верхний край – с нижним. Кроме того, на диаграммах (картах) для функции четырех переменных склеиваться может четверка клеток,

расположенных по углам диаграммы (карты).

© Р. С. Цвентарный, 2009

18

Прикладная теория цифровых автоматов. Тема №4

На рисунке 4.2 приведены примеры минимизации различных функций с помощью диаграмм Вейча.

1	2					3					1	2					3
МДНФ1( f )= x3x4	+					+					МДНФ2( f )= x3x4	+		3		4	+		1x3
		x	3	x	4		x	1	x	4			x		x			x

1					2						1			2					3
МКНФ( f )= (x3 +		4 ) (		1	+		3	+ x4 )	МДНФ( f )= x1x2					+ x1x2 x3 x4					+ x2 x3x4
	x		x			x

1 2

МДНФ( f )= x3 + x1x4

1 2

МДНФ( f )= x3 + x1x2

A B

МКНФ( f )= (x2 + x3 ) (x1 + x3 )

Рисунок 4.2 – Минимизация булевых функций с помощью диаграмм Вейча

© Р. С. Цвентарный, 2009

19

Прикладная теория цифровых автоматов. Тема №4

Очевидно, что с ростом количества переменных минимизация булевых функций на диаграммах Вейча (картах Карно) становится затруднительной из-

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

которые состоят из совокупности более простых диаграмм для функций меньшего количества переменных. На рисунках 4.3 и 4.4 представлены диаграммы Вейча для булевой функции 5-ти и 6-ти переменных соответственно. Минимизация функций большего количества переменных на диаграммах Вейча (картах Карно) практически не производится.

Рисунок 4.3 – Диаграмма Вейча для булевой функции f (x1, x2 , x3 , x4 , x5 )

Как видно на рисунке 4.3, булева функция 5-ти переменных представляется в виде двух диаграмм функций 4-х переменных. При этом левая диаграмма соответствует 16-ти двоичным наборам, на которых переменная x1 равна 0,

правая – 16ти двоичным наборам, на которых переменная x1 равна 1.

Минимизация производится точно так же, как в вышерассмотренных случаях,

однако диаграммы рассматриваются в совокупности. Иными словами,

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

© Р. С. Цвентарный, 2009

20