и дальнейшее расширение этого множества без потери свойства интервальной поглощаемости невозможно.

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

{1, 2, 6, 7},	(– – 1 – – 0);
{1, 3},	(– – – 1 1 0);
{1, 5, 7},	(– 0 – – 1 –);
{2, 4, 5, 7},	(– 0 – 0 – –);
{2, 4, 6},	(– – 1 0 0 –).

Множества {1, 2, 6, 7}, {1, 3} и {2, 4, 5, 7} составляют кратчайшее покрытие множества М1. После расширения второго интервала получаем троичную матрицу

х1	х2	х3	х4	х5	х6
−	−	1	−	−	0
	−	−	1	1
−					−
−	0	−	0	−	−

и соответствующую ей ДНФ х3 х6 х4 х5 х2 х4.

19.4.Расширение интервалов

Вданном примере минимальные покрывающие интервалы оказались довольно широкими, и расширить удалось только один из них и только в одном направлении (заменив 0 на «–» во втором интервале). Расширять интервал можно, последовательно заменяя единицы и нули на символ «–» в

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

1	1	0	0	0
0	0	0	1	0 .
	1	0	1
1				1

Если по порядку расположения компонент пытаться заменять единицы и нули на «–», то получим не самый широкий интервал (– 1 – 1 0), в то время как можно получить лучше: (0 1 – – –).

120

Поставим следующую задачу. В троичном векторе и, ортогональном всем строкам троичной матрицы U, заменить максимальное число значений 0 и 1 на «–» так, чтобы он оставался ортогональным всем строкам матрицы U.

Можно решать эту задачу следующим образом. Строим матрицу различий вектора и по отношению к строкам матрицы U. Строки матрицы различий соответствуют строкам матрицы U, и каждая из них показывает, по каким компонентам вектор и отличается от соответствующей строки матрицы U. Для этого строка матрицы различий получается путем покомпонентного сложения по модулю два соответствующей строки матрицы U с сектором и. При этом считается, что 0 – = 1 – = 0. Для матрицы различий надо найти минимальную совокупность столбцов такую, чтобы каждая строка матрицы различий имела в данной совокупности хотя бы одну единицу. То есть надо покрыть строки минимальным числом столбцов. В векторе и оставляются прежние значения только для тех компонент, которые соответствуют столбцам из полученной совокупности. Остальные компоненты принимают значение «–».

Для приведенной выше матрицы и вектора и = (0 1 – 1 0) матрица различий имеет вид

1 0 0 1 00 1 0 0 0 .1 0 0 0 1

Кратчайшее столбцовое покрытие этой матрицы составляют ее первые два столбца. Следовательно, решением является вектор (0 1 – – –).

121

Г л а в а 20

Минимизация системы булевых функций

20.1. Минимизация системы ДНФ

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

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

x3 x4

х3 x4

•

•

•

•

•

•

•

•

•

•

•

•

x

1 x2

f1

x1

x2

f2

Рис. 20.1. Система булевых функций

Если минимизировать каждую функцию по отдельности, то получим следующие ДНФ:

f1(x1, x2, x3, x4) = x1 x3 x4 x1 x2 x3 x2 x4; f2(x1, x2, x3, x4) = x1 x2 x4 x1 x3 x4 x2 x3.

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

		f1(x1, x2, x3, x4) = x1 x3 x4 x1 x2 x3 x2 х3 x4;
		f2(x1, x2, x3, x4) = x1 x2 x4 x1 x3 x4 x2 x3 x4.
В	полученных	ДНФ присутствует одна общая элементарная конъюнкция
x2	x3 x4, и за счет этого их число снизилось на единицу.
	Посмотрим,	как метод Квайна-МакКласки можно распространить на

случай системы булевых функций.

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

F′ F, если она является импликантой для любой функции из F′ и перестает быть импликантой при удалении из нее любого литерала и не является

импликантой ни для какой функции, не принадлежащей F′.

122

Процесс минимизации системы ДНФ по данному методу состоит из двух этапов: 1) нахождение множества всех обобщенных простых импликант для заданной системы; 2) выделение из этого множества минимального подмножества, удовлетворяющего условию, что для всякой функции, принадлежащей заданной системе, можно из этого подмножества получить задающую ее ДНФ.

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

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

Так же, как при минимизации одной функции, склеиваемым конъюнкциям приписывается знак «*», но приписывается он только тем конъюнкциям, характеристика которых совпадает с характеристикой результата склеивания.

Рассмотрим процесс получения обобщенных простых импликант на примере системы функций, заданных картами Карно на рис. 20.1. Получаем следующую последовательность пар матриц:

x1 x2	x3	x4		f1	f2		x1 x2		x3	x4			f1	f2
			1*				0 −		0	0			1 0
0 0	0	0		1 0					0	0		*
	0		2 *				− 1						1 0
0 1		0		1	0			0 1	− 0			*
1 1	0	0	3*	1	0
													1 0
							1 1 − 0					*	1 0			x1 x2 x3 x4		f1 f2
0 1	1	0	4 *	1	1		1 1		0	−			1 0
	0		5*			;	− 1		1	0			1 1		;	− 1 − 0		1 0 .
0 1		1		0	1
1 1		0 6 *		1 1
	1							0 1	1	−		*	0 1			− 1	1 −	0 1
1 1	0	1	7 *	1	0			0 1	− 1
	1		8*										0 1
0 1		1		0 1					1			*
	1		9 *				1 1			−			0 1
1 0		1		0 1			− 1		1	1		*	0 1
1 1	1	1	10 *	0 1
									1	1
							1 −						0	1

123

Полученную сокращенную систему ДНФ, которая содержит все обобщенные простые импликанты представим следующей парой матриц, где собраны строки, не отмеченные знаком «*»:

x1		x2	x3	x4		f1	f2
	0	−	0	0		1	0
		1	0
1				−		1	0
−		1	1	0			1
					,	1		.
X =	0	1	−	1		Y =
						0	1
1		−	1	1		0	1
		1	−	0
−						1	0
		1	1
−				−		0	1

Строки матрицы X представляют интервалы булева пространства аргументов. В матрице Y единица в столбце fi и j-й строке показывает, что на всем j-м интервале функция fi имеет значение 1 (j-я конъюнкция входит в ДНФ функции fi). Такая форма названа ранее матричным представлением системы ДНФ.

Рассмотрим теперь выполнение второго этапа минимизации, который сводится к задаче покрытия. Пара одноименных строк матриц X и Y представляет множество пар вида (mi, fj), где mi – элемент булева пространства аргументов, а fj – функция, принимающая значение 1 на этом элементе. Интервал и его характеристика являются сомножителями декартова произведения, результат которого представляет собой множество с элементами вида (mi, fj). Очевидно, всего пар вида (mi, fj) в задании системы булевых функций столько, сколько единиц в исходной матрице функций. Необходимо из полученной совокупности интервалов выбрать минимум так, чтобы выбранные интервалы со своими характеристиками покрыли все множество пар (mi, fj) в задании исходной системы.

Для решения рассматриваемого примера построим следующую матрицу, строкам которой соответствуют пары строк матриц X и Y, а столбцам – пары вида (mi, fj):

124