DisMathTPU_new

12. Неполностью определенные (частичные) булевы функции

12.1.Неполностью определенная булева функция и способы

ååзадания

Определение. Неполностью определенная (частичная) булева функция f (x1; : : : ; xn) это однозначное отображение подмножества M булева пространства Bn в множество B: f : M ! B, M Bn.

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

1)Задание частичной булевой функции таблицей истинности. В левой части таблицы истинности представляются, как и раньше, все векторы булева пространства, а в ее правой части либо пере- числяются значения функции, либо указывается специальный символ

(если набор в область определения не входит).

2)Задание частичной булевой функции характеристиче-

скими множествами. К двум известным нам характеристическим множествам Mf1 è Mf0 добавляатся третье, Mf , состоящее из набо-

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

3) Задание частичной булевой функции матрицей Грея. В

матрице Грея тем же символом отмечаются клетки, не входящие в

область определения.

Пример. Пусть функция f (x; y; z) задана на множестве булевых

векторов, представляющих целые числа от 1 до 5, и принимает значе- ние 1, если и только если заданное число есть 2k, где k целое.

x y z f (x; y; z)

0 0 0
0 0 1	1
0 1 0	1
0 1 1	0
1 0 0	1
1 0 1	0
1 1 0
1 1 1

Mf1 =f001; 010; 100g Mf0 =f011; 101g

Mf =f000; 110; 111g

				y
				z

x

101

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

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

Определение. Назовем доопределением неполностью определенной булевой функции f (x1; : : : ; xn) булеву функцию f(x1; : : : ; xn), удовлетворяющую условиям:

Mf1 Mf1; Mf0 Mf0:

Это означает, что значения любого доопределения должны совпадать со значениями функции f (x1; : : : ; xn) на наборах из множеств

Mf1 è Mf0 , и доопределение может принимать любые значения на на- борах из Mf . Из этого и из теоремы о числе векторов с очевидностью

следует утверждение.

Утверждение о числе доопределений. Число различ-

ных доопределений неполностью определенной булевой функции f (x1; : : : ; xn) равно 2k, ãäå k = Mf .

Пример. Рассмотренная в предыдущем примере неполностью определенная булева функция имеет восемь доопределений.

z

y

x

f

y

y

y

y

z

z

z

z

x

f1

x

f2

x

f3

x

f4

y

y

y

y

z

z

z

z

x

f5

x

f6

x

f7

x

f8

102

Определение. Минимизировать неполностью определенную булеву функцию это значит выбрать среди кратчайших ДНФ всех ее доопределений самую короткую ДНФ.

Пример. Для рассмотренной в предыдущем примере неполностью определенной булевой функции f (x; y; z) перебор кратчайших ДНФ всех восьми доопределений приводит к следующему результату: самой короткой оказывается кратчайшая ДНФ доопределения f6(x; y; z).

I1				z y	КратДНФ = z	_	x y:
	x			- I2	K1		K2

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

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

Определение. Интервал I назовем допустимым для неполностью

определенной булевой функции f (x1; : : : ; xn), если он удовлетворяет условиям: I Mf1 [ Mf , I \ Mf1 6= ;.

Определение. Интервал I назовем максимальным для неполно-

стью определенной булевой функции, если он допустим для этой функции, и не существует другого допустимого для нее интервала I0 такого,

÷òî I I0.

Пример. Для функции из предыдущего примера на левой матрице Грея изображены два недопустимых интервала I1 = 01 è I2 = 01 , на средней допустимый, но не максимальный интервал I = 00 , на

правой максимальный интервал I0							= 0 .
		z y				z y	z y
								-	I0
x			x			x
	? ?			?
	I1	I2		I

103

12.2.1. Поиск кратчайшей ДНФ неполностью определенной булевой функции

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

Для нахождения всех максимальных интервалов неполностью определенной функции f (x1; : : : ; xn) можно применить алгоритм Квайна-

Мак-Класки или алгоритм Блейка-Порецкого к такому ее доопределению f(x1; : : : ; xn), которое удовлетворяет условию: Mf1 = Mf1 [ Mf ,

а затем исключить из найденных интервалов те, которые не содержат ни одной точки функции f (x1; : : : ; xn). Таблица Квайна неполностью определенной функции f (x1; : : : ; xn) строится аналогично таблице Квайна булевой функции: строкам ставятся в соответствие все максимальные интервалы функции, а столбцам все точки. Элемент матрицы, стоящий на пересечении i-й строки и j-го столбца, полага-

ется равным единице тогда и только тогда, когда i-й максимальный интервал функции содержит ее j-ю точку.

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

Начало. Задана неполностью определенная функция f (x1; : : : ; xn). Шаг 1. Находим любым алгоритмом все максимальные интервалы

функции f (x1; : : : ; xn).

Шаг 2. Строим таблицу Квайна функции f (x1; : : : ; xn).

Шаг 3. Находим кратчайшее покрытие таблицы Квайна, а по покрытию кратчайшую ДНФ функции f (x1; : : : ; xn).

Конец.

104

Пример. Рассмотрим частичную булеву функцию f (a; b; c; d), заданную матрицей Грея, и для удобства пронумеруем ее точки.

												c													c
											d													d
																		1		2			3
																4		5					6
		b												b				7
	a												a

Шаг 1. Найдем все максимальные интервалы функции f (a; b; c; d), обозначим их буквами от A до G и изобразим на двух матрицах.

				c			c
			D				d
			d
				-		- E
		A
a			A		a
							G
	b	?	UA ?		b	R@
						@
		A	B C			- F

Шаг 2. Построим таблицу Квайна функции f (a; b; c; d), используя введенные обозначения точек и интервалов.

	0101 0111 0110 1100 1101 1110 1001
1 0				1	1		1	A
101								B
	1				1
110								C
			1			1
0 1								D
		1	1
01 1								E
	1	1
11 0								F
				1		1
10 1								G
							1
	1	2	3	4	5	6	7

Шаг 3. Кратчайшее покрытие таблицы образуют строки fA; C; Eg. Построим по ним кратчайшую ДНФ функции f (a; b; c; d).

c

d

EHY

HH

b

a ? ?

КратДНФ = a c _ b c d _ a b d: A C E

AC

105

12.2.2. Поиск приближенной кратчайшей ДНФ неполностью определенной булевой функции

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

лишь в том, что цена точки определяется как количество соседних ей векторов из множества Mf1 [ Mf .

Пример. Применим алгоритм к матрице Грея неполностью определенной булевой функции из последнего примера.

Начало. Точки обозначаем греческими буквами (левая матрица). Шаг 1. Вû÷èсляем цены точек (ïðàâая матрица).

							c								c
							d								d
												2	3	3
				"							3	3		2
	b								b			3
a								a

Шаги 2, 3. Выбираем точку (минимальной цены 2). Она вхо-

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

c

c

d

d

3

I1HYH

3

"

3

2

H

3

b

b

a

a

Шаги 2, 3. Выбираем неотмеченную точку (цены 2). Она также

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

106

c				c
d				d

				3
	"		I1YHH		3
					H
b			b	3
a			a		- I2

Шаги 2, 3. Найдем следующую неотмеченную точку (цены 3).

Она входит в два максимальных интервала, содержащих по одной неотмеченной точке. Включаем в решение интервал большей мощно- ñòè I3 и отмечаем его точки.

	c	I1	HH		c
				I3
	d				d
		HY			-
"			3
		b	3
b
a		a	- I2

Шаги 2, 3. Найдем следующую неотмеченную точку " (цены 3).

Она входит в два максимальных интервала (с одной и двумя неотме- ченными точками), поэтому включаем в решение интервал I4 с двумя неотмеченными точками и отмечаем их.

		c	I1HYHH					c
		d				I3
								-
		"
a	b		a	b	I4
					H	Hj
					- I2

Конец. ПриКратДНФ = a b d _ a b d _ a c _ a c: K1 K2 K3 K4

Приближенная кратчайшая ДНФ оказалась длиннее кратчайшей ДНФ, найденной ранее точным алгоритмом, на одну конъюнкцию. Мы могли бы получить и точную кратчайшую ДНФ, если бы на второй итерации шага 2 выбрали другой равноценный вариант интервала (проверьте эту возможность самостоятельно).

107

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

Рассмотрим частичную булеву функцию f (x1; : : : ; xn), ее точку и допустимый интервал I.

Определение. Минимальным расширением интервала I до точ- ки (обозначается [I; ]) называется интервал I0 минимальной мощ- ности, удовлетворяющий условиям: I I0, I0.

Как следует из определения, интервал [I; ] строится так:

внутренние компоненты интервала I остаются внутренними и в интервале [I; ],

внешние компоненты интервала I сохраняют свое значение в интервале [I; ], если и только если они совпадают с соответствующими компонентами вектора ,

внешние компоненты интервала I становятся внутренними в интервале [I; ], если и только если они ортогональны соответствующим компонентам вектора .

Пример.

I = 1 0 10;= 1 0 0 1 10;

[I; ] = 10:

Определение. Интервал I и точка называются совместимыми,

если интервал [I; ] является допустимым для функции f (x1; : : : ; xn). Пример. Для булевой функции из предыдущего примера интервал A = 0 10 и точка = 0111 являются совместимыми, так как

интервал [A; ] = 0 1 допустимый для функции (левая матрица). Интервал B = 110 и та же точка несовместимы, так как интервал [B; ] = 11 не допустимый для функции (правая матрица).

c

QQ

c

[A; ]

HH

[B; ]

YH

d

kQ

d

H

Q

R@A

@

b

b

a

a

?

B

108

Если число переменных функции слишком велико для ее представления на матрице Грея, то проверить интервал I на совместимость с

точкой можно следующим образом: если хотя бы один вектор из Mf0 принадлежит интервалу [I; ], то интервал I и точка несовместимы,

иначе они совместимы.

Пример. Для булевой функции из предыдущего примера интервал B = 110 и точка = 0111 несовместимы, так как существу-

ет вектор = 1111 из множества Mf0 , принадлежащий интервалу

[B; ] = 11 .

Перейдем теперь к изложению метода конкурирующих интервалов. Метод является итерационным. Пусть на k-й итерации есть частичное

решение Uk множество допустимых интервалов функции, и множе-

ñòâî Mk точек функции, не содержащихся ни в одном интервале из Uk (на первой итерации U1 = ;, M1 = Mf1 ). Построим булеву матри- цу совместимости Rk, строкам которой сопоставим точки из Mk, à

столбцам интервалы из Uk. Элемент, стоящий на пересечении i-й строки и j-го столбца, равен единице, если i-я точка совместима с j-м

интервалом.

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

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

Пусть строка матрицы совместимости не содержит единиц. Это означает, что в множестве Uk нет ни одного интервала, совместимого с точкой , то есть ни один интервал не может быть расширен

на множестве Mf1 [ Mf так, чтобы расширение включало точку . Значит, в множество Uk следует добавить интервал, совместимый с .

Такой интервал наименьшей мощности это сама точка. Отсюда вытекает следующее правило.

Правило строки без единиц. Если в матрице совместимости есть строка, не содержащая ни одной единицы, то она удаляется из матрицы. В матрицу добавляется столбец, которому сопоставляется вектор из удаленной строки.

109

Пример. Рассмотрим неполностью определенную булеву функцию пяти переменных и пронумеруем для наглядности ее точки.

c

c

d

d

e

e

																				1		2								3
																								4						5
																						6						7		8
	b																		b													9
a																	a

На первой итерации (матрица совместимости R1) U1 = ;, M1 = Mf1 . Ни одна строка не содержит единиц, следовательно, можно применить

правило строки без единиц к первой строке (договоримся здесь и далее среди равноценных строчек выбирать верхнюю). Первый интервал 00000 не совместим ни с одной точкой функции (матрица R2). Åùå ðàç

применяем правило ко второй строке (матрица R3). Второй интервал 00011 совместим только с шестой точкой, содержащий их допустимый

интервал наименьшей мощности показан на матрице Грея слева. Текущее решение показано на матрице Грея справа. Здесь и далее мы выделяем интервалы из текущего частичного решения и содержащиеся в них точки.

R1			R2		00000 R3			00000	00011
	1) 00000			2) 00011	0		3) 00101	0	0
2) 00011			3) 00101		0		4) 01010	0	0
3) 00101			4) 01010		0		5) 01101	0	0
4) 01010			5) 01101		0		6) 11011	0	1
5) 01101			6) 11011		0		7) 11111	0	0
6) 11011			7) 11111		0		8) 11101	0	0
8) 11111			8) 11101		0		9) 10100	0	0
8) 11101			9) 10100		0			1	2
9) 10100					1

																	c	1																			c
													3																			3
																	d																			d
																		2
2																e																			e
							4							5												4							5
							6					7		8													6				7		8
		a b														9					a b														9

110