х1 х2

0 00 1 ,1 01 1

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

Этот интервал включается в решение, и все покрываемые им элементы исключаются из рассмотрения. Очевидно, что если среди них имеется какойлибо определяющий элемент, то он определяет тот же самый интервал. Затем отыскиваются интервалы, содержащие непокрытые элементы. Для этих элементов и интервалов решается задача покрытия, представляемая матрицей

a1	a2	a3	a	5	B
1	1	0	0
	0	1	0		1
1					B
	1	0			2
0			0		B .
0			1		3
	0	1			B
					4
0	0	0	1		B
					5

Дальнейший ход решения не отличается от предыдущего, и в итоге получается тот же результат: х1 х2 х4 х1 х2 х3 х3 х4.

18.2. Метод Блейка-Порецкого

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

произвольной ДНФ х1 х2 х3 х5 х2 х3 х4 х5 х1, имеет 18 элементарных конъюнкций. В то же время минимальную ДНФ легко получить, применив операции обобщенного склеивания и поглощения:

х1 х2 х3 х5 х2 х3 х4 х5 х1 = х1 х2 х3 х5 х2 х3 х4 х5 х1 х2 х3 х5 = х1 х2 х3 х5.

Метод Блейка-Порецкого основан на применении операций обобщенного склеивания и простого поглощения, определяемых формулами

109

А х В х = А х В х А В и А А В = А.

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

У т в е р ж д е н и е 18.1. В результате описанного процесса получаются все простые импликанты, т. е. получается сокращенная ДНФ.

Покажем это следующим образом. Пусть L – множество конъюнкций

заданной ДНФ, L1	– результат преобразования L путем всевозможных
обобщенных склеиваний и поглощений конъюнкций из L, L2 – результат такого
же преобразования	множества L1 и т. д. Получаем последовательность
L0, L1, … , Lm, где L0 = L, а Lm таково, что Lm + 1 = Lm.

Пусть С0, С1, … , Сk – последовательность множеств конъюнкций рангов п, п – 1, … , п – k, полученная в результате выполнения первого этапа метода

Квайна-МакКласки. Очевидно, что для каждой конъюнкции k0 C0 найдется такая конъюнкция l0 L0, что k0 l0. Теперь покажем, что если для каждой

ki Ci найдется lj Lj	такая, что ki lj, то для каждой ki + 1 Ci + 1 найдется
lj + 1 Lj + 1 такая, что	ki + 1 lj + 1. (Такой метод доказательства называется

методом полной математической индукции). Если мы это докажем, то докажем, что для всякой конъюнкции из любого Ci найдется имплицируемая ею конъюнкция в Lm. Отметим, что если k l, то k содержит все литералы,

которые имеются в l. Например, х2 х4 х5 х6 х4 х6.

Может оказаться, что ki + 1 является импликантой для некоторой lj Lj. Тогда очевидно, что и в Lj + 1 будет конъюнкция, для которой ki + 1 является импликантой. Если ki + 1 не является импликантой ни для какой конъюнкции из Lj, то рассмотрим соседние конъюнкции ki′= x k i + 1 и ki′′= x k i + 1. По условию ki′ и ki′′ таковы, что для них есть конъюнкции в Lj, для которых ki′ и ki′′ являются импликантами, причем это разные конъюнкции, иначе имел бы место случай ki + 1 lj. Покажем, что они находятся в отношении смежности.

Пусть ki′ lj′ и ki′′ lj′′, По предположению ki′ не является импликантой для lj′′, а ki′′ – импликантой для lj′. Следовательно, lj′ состоит из каких-то литералов, принадлежащих k i + 1, и литерала х, а lj′′ – из каких-то литералов, также принадлежащих k i + 1 (возможно, других), и литерала x. Следовательно, lj′ и lj′′ смежны, а их продукт обобщенного склеивания имплицируется конъюнкцией k i + 1.

Таким образом, для любой конъюнкции из любого множества Ci, среди которых находятся все простые импликанты, имеется имплицируемая ею конъюнкция в множестве Lm. Следовательно все простые импликанты

110

находятся в Lm. Непростых импликант там нет, так как они удалены в результате выполнения простого поглощения.

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

Пусть булева функция задана следующей троичной матрицей:

x1		x2	x3	x4	x5
1		1	−	0	0		1
		0	−	1	1		2
1
	0	0	0	−	1		3
	0	−	1	0	−		4
−		1	1	1	1		5
		−	1	0	0		6
1
		1	−	0	1		7
1

В этой матрице находим	следующие пары смежных строк: (2, 3), (1, 4),
(3, 4), (2, 5), (4, 5). Выполняя	над ними операцию обобщенного склеивания,

получим строки

	х1		х2	х3	х4	х5
	−		0	0	1	1	8(2,3)
			1	1	0		9(1,4)
	−					0		,
		0	0	−	0		10(3,4)
						1
	1		−	1	1	1	11(2,5)
		0	1	1	−		12(4,5)
						1

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

Дальнейший поиск дает пары смежных строк (4, 6), (1, 7), (4, 7), (5, 7), (6, 7), для которых получим строки

111

х1	х2	х3	х4	х5
−	−	1	0	0		13(4,6)
	1	−	0			14(1,7)
1				−
−	1	1	0	1		15(4,7) .
	1	1	−	1		16(5,7)
1
	1	−	0			17(6,7)
1				−

Строка 13 поглощает строки 6 и 9, а строка 17 – строки 1 и 7. Строка 17 совпадает со строкой 14. Поэтому строки 1, 6, 7, 9 и 17 удаляются. Далее получаются следующие непоглощаемые строки:

x1	x2	x3	x4	x5	18(4,14) .
−	1	1	0	−
	1	1	−		19(5,15)
−				1

Последняя строка поглощает строки 5, 12, 15 и 16. Окончательно получаем следующую матрицу (с естественной нумерацией строк), представляющую сокращенную ДНФ:

x1	x2	x3	x4	x5
1	0	−	1	1		1
	0	0	−	1		2
0
	−	1	0			3
0				−
−	0	0	1	1		4
0	0	−	0	1		5 .
	−	1	1	1		6
1
−	−	1	0	0		7
	1	−	0			8
1				−
−	1	1	0	−		9
	1	1	−	1		10
−

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

112

решение, элементы антиядра исключаются из рассмотрения и оставшимися интервалами покрываются элементы множества М1, не покрытые ядром.

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

Можно предложить другой способ выполнения второго этапа, который не требует разбиения интервалов на отдельные элементы множества М1.

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

Введем обозначение: t(u, U) – множество номеров тех строк матрицы U, которые представляют интервалы, содержащие булев вектор и. Например, для приведенной выше матрицы и и = (1 0 0 1 1) имеем t(u, U) = {1, 4}. Ясно, что t(u, U) является элементом множества Р(U).

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

Остановимся на способе получения множества Р(U). Пусть для двух троичных матриц U1 и U2 с одинаковым числом строк получены множества

Р(U1) и Р(U2).

У т в е р ж д е н и е 18.2. Если из матриц U1 и U2 построить матрицу U, приписав столбцы матрицы U2 к столбцам U1, то множество Р(U) можно получить, взяв за его элементы всевозможные непустые пересечения элементов Р(U1) с элементами Р(U2).

Для того, чтобы это показать, преобразуем матрицы U1 и U2 следующим образом. К матрице U1 припишем справа столько столбцов, сколько их имеет матрица U2. Всем элементам этих столбцов придадим значение «–». Такие же столбцы, число которых равно числу столбцов исходной матрицы U1, припишем слева к матрице U2. Очевидно, Р(U1) и Р(U2) при этом не изменятся. Произвольно выберем вектор и, принадлежащий какому-нибудь интервалу, представляемому строкой матрицы U. По построению матрицы U имеем

t(u, U) = t(u, U1) ∩ t(u, U2), т. е. каждый элемент множества Р(U) является пересечением двух множеств, одно из которых является элементом множества

Р(U1), а другое – элементом множества Р(U2). С другой стороны, для каждой пары пересекающихся элементов, один из которых взят из Р(U1), а другой – из

113

Р(U2), найдется вектор и такой, что t(u, U1) и t(u, U2) являются теми самыми элементами. Множество t(u, U1) ∩ t(u, U2) состоит из номеров всех строк матриц U1 и U2, каждая из которых представляет интервал, содержащий и. Пересечение интервалов, представляемых строками матриц U1 и U2 с общим номером i, равно интервалу, представляемому i-й строкой матрицы U. Следовательно, для любой пары t(u, U1) и t(u, U2) найдется множество t(u, U)

такое, что t(u, U) = t(u, U1) ∩ t(u, U2).

Если матрица U1 представляет собой один столбец и произвольное число одноэлементных строк, то Р(U1) состоит не более, чем из двух элементов. Один из них представляет множество, состоящее из номеров всех строк, имеющих нули и «–», второй – множество, состоящее из номеров всех строк, имеющих единицы и «–». Если все элементы одностолбцовой матрицы U1 имеют одно и то же значение, то Р(U1) состоит из одного элемента.

Пусть матрица U имеет т столбцов. Для матрицы U1, состоящей из единственного первого столбцы получим Р(U1), как указано выше. Множество Р(U2) для матрицы, состоящей из двух первых столбцов матрицы U, получим путем всевозможных пересечений элементов множества Р(U1) с элементами подобного множества для второго столбца. Для матрицы U3, состоящей из трех первых столбцов матрицы U, получим Р(U3) аналогично, путем всевозможных пересечений элементов множества Р(U2) с элементами подобного множества для третьего столбца. Продолжая таким образом выполнять операцию пересечения множеств, получим, наконец, Р(Uт) = Р(U). Если в результате вычисления некоторого Р(Ui) (1 ≤ i ≤ m) появилось одноэлементное множество, то строка матрицы U с соответствующим номером включается в решение как принадлежащая ядру.

Продемонстрируем процесс получения Р(U) на примере матрицы

x1	x2
1	0
	0
0
0	−
	0
−
U = 0	0
	−
1
−	−
	1
1
−	1
	1
−

для которой получаем следующее:

x3	x4	x5
−	1	1		1
0	−	1		2
1	0	−		3
0	1	1		4
−	0	1		5 ,
1	1	1		6
1	0	0		7
−	0			8
		−
1	0	−		9
1	−	1		10

114

Р(U1) = {(1,4,6,7,8,9,10), (2,3,4,5,7,9,10)};

Р(U2) = {(1,4,6,7), (6,7,8,9,10), (2,3,4,5,7), (3,7,9,10)};

Р(U3) = {(1,4), (1,6,7), (8), (6,7,8,9,10), (2,4,5), (3,5,7), (3,7,9,10)};

Р(U4) = {(1,4), (1,6), (7), (8), (6,10), (7,8,9,10), (2,4), (2,5), (3,5,7), (10), (3,7,9,10)}; Р(U5) = {(1,4), (1,6), (7), (8), (6,10), (8,9,10), (7,8,9), (2,4), (2,5), (3,5), (3,7), (10), (3,9,10), (3,7,9)}.

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

1.Если А Р(U), В Р(U) и А В, то В удаляется из Р(U).

2.Если номер i присутствует только в тех элементах множества Р(U), где присутствует номер k, то i удаляется отовсюду.

Применив правило 1, получим Р(U) = {(1,4), (1,6), (7), (8), (2,4), (2,5), (3,5),

(10)}. Строки 7, 8 и 10 составляют ядро. Антиядро состоит из одной строки 9.

По правилу 2 удаляются номера 3 и 6: Р(U) = {(1,4), (1), (7), (8), (2,4), (2,5), (5), (10)}.

Применив снова правило 1, получим Р(U) = {(1), (7), (8), (2,4), (5), (10)}.

Окончательно имеем два решения рассматриваемого примера:

х1		х2	х3 х4		х5				х1	х2	х3 х4		х5
1 0			−	1	1		1		1 0		−	1	1		1
	0	0	0	− 1			2			0	0	1	1		4
								и	−
	0	0	−	0	1		5		0 0		−	0	1		5 .
		−	1	0	0		7			−	1	0	0		7
−									−
1		1	−	0	−		8		1 1		−	0	−		8
		1	1	− 1			10			1	1	− 1			10
−									−

115