Минимизация системы булевых функций. Синтез ПЛМ с заданной выходной матрицей, страница 8

столбцы матрицы Х

10101100  b

01101100  f

00101100  k

01101000  q

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

--- —101—00,

не пересекающийся с остатком множества М_f

Отметив значением + покрываемые этим минором элементы матрицы:

Y =	a	b	c	d	e	f	g	H	i	j	k	L	m	n	o	p	q	r	s	t
	0	0	1	0	0	0	1	1	0	1	0	0	0	1	0	0	1	1	0	1	1
	1	1	0	1	0	0	0	1	1	0	0	0	1	1	1	1	0	0	1	1	2
	0	-	0	0	0	+	0	0	0	0	+	0	0	0	0	0	+	0	0	0	3
	1	-	0	0	1	+	0	0	1	1	+	1	0	0	1	1	+	0	0	1	4
	1	0	1	0	0	1	0	0	0	0	0	1	1	1	0	1	1	1	0	0	5
	0	-	1	1	0	+	1	1	0	1	+	0	0	1	1	1	+	0	0	1	6

обратим внимание на элемент у₄^e, оказывающийся единственным единичным элементом в своем столбце. Покрывающие его интервальные миноры, следовательно, однострочны и представляют интервально - поглощаемые подмножества множества М₄¹. Выбор лучшего из них несложен — им оказывается минор (4) Х (а, е, i, j, l, о, р, t), т. е. минор, образованный пересечением строки 4 со столбцами а, е, i, j, l, о, р, t. Он содержит все непокрытые пока единицы в строке 4, и соответствующий ему интервал — — — — 0 — — 1 не пересекается с множеством М₄⁰.

Этот минор принимается в качестве второго элемента решения.

Рассмотрим далее элемент y₂^s, также единственный единичный элемент в своем столбце. Однако, в отличие от предыдущего, он не образует вместе с другими непокрытыми единичными элементами своей строки интервально - поглощаемого подмножества. Поэтому естественно поставить задачу нахождения такого интервального минора, который покрывал бы вместе с элементом y₂^s максимальное

количество непокрытых единичных элементов строки 2, находящихся в столбцах a, b, d, h, i, т, п, о, р, t.