гос / Theme4

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

МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ И ИХ СИСТЕМ

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

Задача поиска такой формы и есть задачей минимизации булевых функций.

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

Определение 4.1 Элементарной конъюнкцией называется конъюнкция конечного числа различных (!) между собой булевых переменных, каждая из

которых может иметь или не иметь отрицания.

Определение 4.2 Элементарной дизъюнкцией называется дизъюнкция конечного числа различных (!) между собой булевых переменных, каждая из

которых может иметь или не иметь отрицания.
Определение 4.3 Булева функция g(x1, x2 ,..., xn )			называется импликантой
булевой функции	f (x1, x2 ,..., xn ) , если	для любого	набора	переменных, на
котором g(x1, x2 ,..., xn ) =1, справедливо		f (x1, x2 ,..., xn ) =1.
Определение	4.4 Импликанта g	булевой функции		f , являющаяся

элементарной конъюнкцией, называется простой, если никакая часть импликанты g не является импликантой f .

Пример 4.1 Пусть булева функция задана таблицей истинности (табл.

4.1)

СДНФ( f )= x1x2 x3 + x1x2 x3 + x1x2 x3

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

1

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

Таблица 4.1

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

Импликантами функции f являются:

g1 = x1x2 x3

g2 = x1x2 x3

g3 = x1x2 x3

g4 = x1x2 x3 + x1x2 x3 g5 = x1x2 x3 + x1x2 x3

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

Простыми среди перечисленных импликант являются импликанты g6 и g1. Импликанты g2 и g3 , например, не являются простыми, поскольку импликанта g6 является частью этих импликант.

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

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

Определение 4.5 Сокращенной дизъюнктивной нормальной формой

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

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

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

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

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

2

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

Определение 4.6 Тупиковой дизъюнктивной нормальной формой (ТДНФ)

булевой функции f называется СкДНФ этой функции, в которой отсутствуют лишние импликанты.

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

Определение 4.7 Минимальной дизъюнктивной нормальной формой

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

Минимальных ДНФ функции также может быть несколько.

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

Определение 4.8 Булева функция g(x1, x2 ,..., xn ) называется имплицентой

булевой функции f (x1, x2 ,..., xn ) , если для любого набора переменных, на

котором g(x1, x2 ,..., xn ) = 0 , справедливо f (x1, x2 ,..., xn ) = 0 .

Определение 4.9 Имплицента g булевой функции f , являющаяся элементарной дизъюнкцией, называется простой, если никакая часть имплиценты g не является имплицентой f .

Определение 4.10 Сокращенной конъюнктивной нормальной формой

(СкКНФ) булевой функции f называется конъюнкция всех простых имплицент функции f .

Определение 4.11 Тупиковой конъюнктивной нормальной формой (ТКНФ)

булевой функции f называется СкКНФ этой функции, в которой отсутствуют

лишние имплиценты.

Определение 4.12 Минимальной конъюнктивной нормальной формой

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

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

3

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

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

1.Получение по таблице истинности совершенной формы.

2.Получение сокращенной формы путем применения специальных соотношений.

3.Отыскание лишних простых импликант (имплицент) и получение тупиковых форм.

4.Выбор среди найденных тупиковых форм минимальных форм.

Метод Квайна

Этот метод минимизации позволяет перейти от СДНФ (СКНФ) булевой

функции к МДНФ (МКНФ) этой функции.

Метод Квайна основан на применении двух соотношений:

1.Соотношение склеивания:

1.1.Ax + Ax = Ax + Ax + A для СДНФ, A – любое выражение.

1.2.( A + x)( A + x) = ( A + x)( A + x) A для СКНФ, A – любое выражение.

2.Соотношение поглощения:

2.1.Ax + A = A для ДНФ, A – любое выражение.

2.2.( A + x) A = A для КНФ, A – любое выражение.

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

(СкКНФ).

Для нахождения ТДНФ (ТКНФ) строится так называемая импликантная

(имплицентная) матрица. Строки такой матрицы отмечаются членами СкДНФ

(СкКНФ), а столбцы – членами СДНФ (СКНФ).

Далее производятся поглощения в полученной матрице. Если некоторая импликанта (имплицента), стоящая в строке i , поглощает некоторый член СДНФ (СКНФ), стоящий в столбце j , то в клетку с координатами (i, j)

ставится символ «*» (звёздочка).

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

4

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

Отыскание тупиковых форм по импликантной (имплицентной) матрице

производится следующим образом:

1.Ищутся столбцы матрицы, имеющие только одну звёздочку.

Соответствующие этим звёздочкам простые импликанты

(имплиценты) называются базисными и составляют ядро булевой функции. Ядро обязательно входит в любую тупиковую и минимальную форму.

2.Рассматриваются различные варианты выбора совокупности простых импликант (имплицент), покрывающих звёздочками все те столбцы матрицы, которые остались не покрытыми ядром. Полученные

совокупности и есть тупиковые формы. Среди них выбирают минимальные формы.

Пример 4.2 Методом Квайна найти МДФН функции, заданной таблицей

истинности (табл. 4.2)
	Таблица 4.2											1												2							3			4			5
					СДНФ( f )=									1		2			3 +						1		2 x3 +			1x2			3 + x1x2			3	+ x1x2 x3
													x		x		x							x		x			x			x			x
	x1	x2	x3	f
					Выполним все возможные склеивания. Для удобства
	0	0	0	1	импликанты помечены цифрами. Запись, например,
	0	0	1	1	(1:2) будет обозначать результат склеивания 1-ой и
	0	1	0	1	2-ой импликанты.
	0	1	1	0	(1:2)		1			2 ; (1:3)										1			3	; (1:4); (1:5); (2:3); (2:4); (2:5);
						x		x										x				x
	1	0	0	0
					(3:4) x2						3 ; (3:5); (4:5) x1x2 .
									x
	1	0	1	0																											на то, что пары
					Следует обратить																				внимание
	1	1	0	1
												(1:4);									(1:5);							(2:3);			(2:4);			(2:5);			(3:5)
					импликант																																	не
	1	1	1	1
					склеиваются. Они																	перечислены лишь												для			указания

необходимости перебора всех возможных пар импликант.

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

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

5

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

возможны склеивания. В данном примере склеивания уже невозможны.

Полученная форма:

1

2

3

4

5

(1:2)

(1:3)

(3:4)

(4:5)

1

2

3

+

1

2 x3

+

1x2

3

+ x1x2

3

+ x1x2 x3

+

1

2 +

1

3 + x2

3 + x1x2

x

x

x

x

x

x

x

x

x

x

x

x

x

Теперь выполняются поглощенные импликанты импликанта может быть этом ставится один раз:

все возможные поглощения. Для удобства отмечаются символом «*». Одна и та же поглощена разными импликантами. Звёздочка при

1

2

3

4

5

(1:2)

(1:3)

(3:4)

(4:5)

1

2

3

+

1

2 x3

+

1x2

3

+ x1x2

3

+ x1x2 x3

+

1

2 +

1

3 + x2

3 + x1x2 .

x

x

x

x

x

x

x

x

x

x

x

x

x

*

*

*

*

*

Например, импликанта 1 поглощается импликантами (1:2) и (1:3), а

импликанта 5 поглощается только импликантой (4:5).

В результате выполнения всех возможных поглощений получается СкДНФ:

СкДНФ( f )= x1x2 + x1x3 + x2 x3 + x1x2 .

Далее необходимо отыскать в СкДНФ лишние простые импликанты и получить ТДНФ. Импликантная матрица:

Члены СДНФ (конституэнты единицы)

Члены СкДНФ

(простые

импликанты)

																											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
				x		x		2						*								*
			1
				x		x								*															*
		1 3
			x2					3																					*							*
							x
			x x					2																													*							*
		1

В матрице крупными рамками выделены импликанты, составляющие ядро булевой функции (им соответствует одна звёздочка в одном из столбцов): x1x2 , x1x2 . Серым цветом отмечены столбцы, которые покрываются

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

6

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

импликантами ядра (столбцы, в которых эти импликанты содержат звёздочки).

Как видно по импликантной матрице, непокрытым остается только столбец с конституэнтой единицы x1x2 x3 . Этот столбец может быть покрыт выбором простой импликанты либо x1x3 , либо x2 x3 . То есть рассматриваемая функция имеет две ТДНФ:

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

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

Поскольку суммарное число аргументов и операций (суммарное число букв равно 6) в обеих ТДНФ одинаково, то минимальных ДНФ тоже две и они равны тупиковым формам:

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

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

Метод Квайна – Мак-Класки

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

(см. метод Квайна), что нахождение МДНФ не отличается по сути от нахождения МКНФ, поэтому можно ограничиться рассмотрением нахождения лишь МДНФ. Для нахождения МДНФ методом Квайна – Мак-Класки необходимо:

1.Все конституэнты единицы из СДНФ булевой функции f записать в виде их двоичных наборов. Например, конституэнта единицы x1x2 x3x4

будет записана в виде 0110.

2.Все двоичные наборы разбить на непересекающиеся группы. При этом

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

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

7

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

3.Произвести все возможные склеивания и поглощения, как и в методе Квайна. Для этого необходимо рассмотреть все возможные пары импликант из всех соседних групп. На месте выпадающих переменных при этом ставят прочерк («–»), поглощенные импликанты помечают звёздочкой («*»). Например, если рассмотреть пару импликант 0111 и 0011, то они склеиваются, образуя импликанту 0–11. Импликанта 0–11

при этом может поглотить и импликанту 0111, и импликанту 0011,

поскольку она полностью входит в их состав. Указанные импликанты необходимо пометить звёздочкой. Импликанты 0011 и 1000, например,

не склеиваются, несмотря на то, что находятся в соседних группах (2 и 1

соответственно), поскольку они отличаются более чем в одном разряде двоичного набора. Склеиваются также импликанты 01–0 и 00–0, образуя

0––0, поскольку в обеих отсутствует одна и та же переменная ( x3 ) и

отличие имеется только в одном разряде. Импликанты 0–01 и 00–0 не могут склеиваться, поскольку они содержат разный набор переменных.

Импликанты, не помеченные звёздочкой после всех склеиваний и поглощений, составляют СкДНФ.

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

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

8

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

Пример 4.3 Методом Квайна – Мак-Класки найти МДНФ булевой

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

Таблица 4.3

x1	x2	x3	x4	f
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	0
0	1	1	1	1
1	0	0	0	1
1	0	0	1	0
1	0	1	0	1
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1

СДНФ( f )=0000+0001+0010+0111+1000+1010+1111

1 шаг		2 шаг
0.	0000*	0.	000–, 00–0*, –000*
1.	0001*, 0010*, 1000*	1.	–010*, 10–0*
2.	1010*	2.
3.	0111*	3.	–111
4.	1111*

3 шаг

0. –0–0

Как видно, после 3-го шага дальнейшие склеивания и

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

СкДНФ( f )=000– + –111+ –0–0=

= x1x2 x3 + x2 x3 x4 + x2 x4

Импликантная матрица:

0000

0001

0010

0111

1000

1010

1111

000–

*

*

–111

*

*

–0–0

*

*

*

*

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

9

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

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

МДНФ( f )=ТДНФ( f )=СкДНФ( f )= x1x2 x3 + x2 x3 x4 + x2 x4 .

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

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

(рассматривается случай минимизации дизъюнктивных нормальных форм).

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

пересечение которых с рассматриваемым столбцом отмечено звёздочкой.

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

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

Пример 4.4 По импликантной матрице из примера 4.2 методом Патрика получить все ТДНФ.

Размеченная импликантная матрица:

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

10