Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Томский Политехнический Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

DisMathTPU

.pdf

Скачиваний:

Добавлен:

29.05.2015

Размер:

753.61 Кб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 1112 / 1712 13 14 15 16 17 > Следующая >>>

111

13.2. Кратчайшая и безызбыточная системы ДНФ

Определение. Длиной системы ДНФ называется число различных конъюнкций, входящих во все ДНФ системы.

Определение. Рангом системы ДНФ называется сумма рангов различных конъюнкций, входящих во все ДНФ системы.

Пример. Рассмотрим систему ДНФ.

ÄÍÔ1 =

z _ x y z _

ÄÍÔ2 =

z _ x y _ x z:

K1 K2 K3 K4

K4 K5

В ДНФ системы входят 6 различных конъюнкций

K1; : : : ; K6

с суммой

рангов 15. Значит, длина этой системы 6, ранг 15.

Далее будем говорить, что система ДНФ D = fD1; : : : ; Dmg задает систему функций F = ff1(x1; : : : ; xn); : : : ; fm(x1; : : : ; xn)g, åñëè ÄÍÔ Di çà- дает функцию fi(x1; : : : ; xn), i = 1; : : : ; m.

Определение. Кратчайшей системой ДНФ (Dêðàò) системы булевых функций F = ff1(x1; : : : ; xn); : : : ; fm(x1; : : : ; xn)g называется система ДНФ наименьшей длины из всех систем ДНФ, задающих систему F.

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

шей системой ДНФ, и наоборот, не все ДНФ кратчайшей системы ДНФ должны быть простыми кратчайшими и даже кратчайшими ДНФ.

Пример. Рассмотрим систему неполностью определенных булевых функций F = ff; g; hg. Построим систему кратчайших ДНФ этих функций,

рассматривая каждую функцию в отдельности.

		c			c	F	?
	d			d
		-C
	D					G	6
		-					6
		-			-		E
b			b				b
a			a				a
	? ?
	? ?

- J

? ?

A B

H I

f(a; b; c; d)

g(a; b; c; d)

h(a; b; c; d)

8КратДНФf = a d _ c d _

_ a b;9

C D

>КратДНФ

= b

c d

b c:

>КратДНФh = a b c

c d

b d:

_ _

;

112

Длина системы D равна 10, ранг 25. Система не является кратчайшей. Например, интервал A в достаточном множестве функции f(a; b; c; d) можно заменить на E, и длина получившейся системы ДНФ будет равна 9.

Построим теперь кратчайшую систему ДНФ для F.

- L

-D

f(a; b; c; d)

K d

- L

g(a; b; c; d)

6 b a

	c
	d
	- J

?
?

h(a; b; c; d)

8ÄÍÔf = a d _ a b _

_ b c d;9

K L

>ÄÍÔ

= b

b d

b c d;

êðàò

>ÄÍÔh = b c d

a b c

b d:

;

Длина этой системы ДНФ равна 7, ранг 18. Все ДНФ из системы Dкрат кратчайшие, но не простые кратчайшие: интервал L не является максимальным для функций f(a; b; c; d) и g(a; b; c; d), интервал K не максимальный для f(a; b; c; d), E не максимальный для h(a; b; c; d).

Построим еще одну кратчайшую систему ДНФ для F.

H I A

f(a; b; c; d)

g(a; b; c; d)

h(a; b; c; d)

8ÄÍÔf0

= a d _ a b _ b c d _

>ÄÍÔ

b c d

c:>

= a d

êðàò

>ÄÍÔh0

= a d

a b c

c d:

;

Длина системы Dêðàò0 равна 7, ранг 18. ДНФ0g не является кратчайшей, так как имеет длину 4, а КратДНФg длину 3.

113

Определение. Безызбыточной системой ДНФ (Dáåç) системы булевых функций F = ff1(x1; : : : ; xn); : : : ; fm(x1; : : : ; xn)g называется система ДНФ D = fD1; : : : ; Dmg, такая, что:

удаление любой конъюнкции K из любой ДНФ Di приводит к тому, ÷òî Di перестает задавать функцию fi(x1; : : : ; xn),

если конъюнкция K входит в ДНФ Di1; : : : ; Dik , то удаление любой буквы из K приводит к тому, что по крайней мере одна из этих ДНФ Dij , 1 j k, перестает задавать функцию fij (x1; : : : ; xn).

Понятно, что система безызбыточных ДНФ будет также и безызбыточ- ной системой ДНФ, обратное же не всегда верно.

Пример. Построим безызбыточную систему ДНФ для системы функций из предыдущего примера.

H I

f(a; b; c; d)

g(a; b; c; d)

h(a; b; c; d)

8ÄÍÔf00

= a d _ a b _ b c d _

>ÄÍÔ

b c d

c:>

= a d

áåç

>ÄÍÔh00

= a b c

c d

b c d:

_ _

;

Интервал L не является максимальным (конъюнкция b c d не является про-

стой импликантой) ни для одной функции. Однако любое расширение этого интервала не является допустимым по крайней мере для одной из функций, что показано на матрицах Грея. Здесь L2, L3, L4 расширения интервала

L по второй, третей и четвертой компонентам соответственно.

d c

a b

f(a; b; c; d)

g(a; b; c; d)

h(a; b; c; d)

114

Интервал M является максимальным для функции g(a; b; c; d), а значит, не

может быть расширен. Остальные интервалы максимальные для функций, в чьи достаточные множества они включены. Ни один интервал нельзя удалить из достаточного множества любой функции так, чтобы множество осталось достаточным. Поэтому, хотя ни одна ДНФ не является безызбыточной, система Dáåç является безызбыточной системой ДНФ.

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

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

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

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

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

Пусть F = ff1(x1; : : : ; xn); : : : ; fm(x1; : : : ; xn)g система булевых функ-

ций. Для ее минимизации в метод конкурирующих интервалов вносятся следующие изменения.

Во-первых, точки и интервалы сопровождаются обозначениями или номерами функций. Так, запись (1) означает точку функции f1(x1; : : : ; xn), а запись I(1; 3) интервал I, допустимый для функций f1(x1; : : : ; xn) è f3(x1; : : : ; xn) и включенный в достаточное множество этих функций.

Во-вторых, расширение интервала I(j1; : : : ; jk) до точки (i) сопровождается номерами функций (i; j1; : : : ; jk).

В-третьих, интервал I(j1; : : : ; jk) и точка (i) совместимы, если и только если интервал I0(i; j1; : : : ; jk) = [I(j1; : : : ; jk); (i)] допустим для функций

fi(x1; : : : ; xn), fj1(x1; : : : ; xn),: : :, fjk (x1; : : : ; xn).

115

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

c	c		c

d	d	d

-I

f(a; b; c; d)

g(a; b; c; d)

h(a; b; c; d)

Рассмотрим точку (f) = 1100 и интервал I(g; h) = 111 . Минимальное расширение интервала I(g; h) до точки (f) (интервал I0(f; g; h) = 11 )

не является допустимым для функции h(a; b; c; d) и, следовательно, не может быть включен в решение. Но если рассмотреть интервал I(g) = 111 и ту же точку (f), то интервал I0(f; g) = [I(g); (f)] = 11 будет допустимым для функций f(a; b; c; d), g(a; b; c; d) и может быть включен в решение для этих функций.

В-четвертых, интервал I(j1; : : : ; jk) при применении правила столбца без единиц расширяется таким образом, чтобы он оставался допустимым для всех функций fj1(x1; : : : ; xn),: : :, fjk (x1; : : : ; xn), номера которых перечислены в скобках.

Остальные понятия и правила алгоритма остаются без изменений.

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

c	c		c

d	d	d

		1							8		9				13
				2						10					14
		3	4		5					11						15
	b		6	7			b		12				b	16
	b						b						b
a						a		g(a; b; c; d)				a		h(a; b; c; d)
		f(a; b; c; d)						g(a; b; c; d)						h(a; b; c; d)

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

116

0000(f) 0111(f) 1100(f) 1001(f) 0101(h) 1000(h)

	1)	0000(f)

	2)	0111(f)	0
	3)	1100(f)	0	0
4)		1101(f)	0	0	1	1	0	0
5)		1110(f)	0	0	1	0	0	0
	6)	1001(f)	0	0	0
7)		1011(f)	0	1	0	1	0	0

8)		0001(g)	1	0	0	1	0	0
9)		0010(g)	1	0	0	0	0	0
10)		0111(g)	0	1	0	0	0	0
11)		1111(g)	0	1	1	1	0	0
12)		1001(g)	0	0	0	1	0	0

13)		0001(h)	0	0	0	1	1	0
	14)	0101(h)	0	0	0	0
15)		1111(h)	0	1	0	1	1	0
	16)	1000(h)	0	0	0	0	0

			1	2	3	4	5	6

Применяем к шестому столбцу матрицы правило столбца без единиц. В результате в решение включается интервал I1 = 101 (h). Здесь и далее на

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

1		c
		d
	- 2
	4	5
		7


b

a? ?

3 4

f(a; b; c; d)

8	9
10

g(a; b; c; d)

- 5

a? ?

6 I1

h(a; b; c; d)

Âрезультате получаем матрицу совместимости на следующей странице.

Âней нет строк без единиц, столбцов без единиц и столбцов с одной единицей, поэтому применяем к первому столбцу правило столбца наибольшего

ранга. Расширяем интервал 0000(f) до восьмой точки 0001(g), получаем интервал 000 (f; g) и добавляем его в частичное решение. Пересчитываем

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

117

0000(f) 0111(f) 1100(f) 1001(f) 0101(h) 000 (f; g)

4)		1101(f)	0	0	1	1	0	0
5)		1110(f)	0	0	1	0	0	0
7)		1011(f)	0	1	0	1	0	0

	8)	0001(g)	1	0	0	1	0
		0001(g)	1	0	0	1	0
9)		0010(g)	1	0	0	0	0	0
10)		0111(g)	0	1	0	0	0	0
11)		1111(g)	0	1	1	1	0	0
12)		1001(g)	0	0	0	1	0	0

13)		0001(h)	0	0	0	1	1	0
15)		1111(h)	0	1	0	1	1	0

			1	2	3	4	5	1

Первый столбец теперь не содержит единиц, применяем соответствующее правило. Интервал I2 = 000 (f; g) нельзя расширить, поэтому добавляем

его в окончательное решение и удаляем первый столбец из матрицы. Получившаяся матрица совместимости представлена ниже на этой странице. Текущее реøåíèе показано на матðèöàõ Ãðåÿ.

3 4

g(a; b; c; d)

f(a; b; c; d)

h(a; b; c; d)

Затем применяем к девятой строке (точка 0010(g)) правило строки без единиц. В матрице появляется седьмой столбец 0010(g).

		0111(f)	1100(f)	1001(f)	0101(h)	0010(g)

4)	1101(f)	0	1	1	0	0
5)	1110(f)	0	1	0	0	0
7)	1011(f)	1	0	1	0	0

10)	0111(g)	1	0	0	0	0
11)	1111(g)	1	1	1	0	0
12)	1001(g)	0	0	1	0	0

13)	0001(h)	0	0	1	1	0
15)	1111(h)	1	0	1	1	0

		2	3	4	5	7

118

Седьмой столбец не содержит единиц, применяем к нему соответствующее правило. Расширяем интервал 0010(g) до интервала I3 = 0 10(g), который включаем в решение. Седьмой столбец удаляем из матрицы.

- I3

- 5

- 2

3 4

g(a; b; c; d)

f(a; b; c; d)

h(a; b; c; d)

Затем применяем ко второму столбцу правило столбца наибольшего ранга. Расширяем интервал 0111(f) до десятой точки 0111(g), получаем интервал

0111(f; g). Пересчитываем второй столбец. Затем применяем к третьему столбцу то же правило, расширяем интервал 1100(f) до четвертой точки 1101(f), получаем интервал 110 (f) и пересчитываем третий столбец.

										0111(f)						1100(f)					1001(f)				0101(h)			0111(f; g)						110 (f)
	4)		1101(f)									0				1					1					0		0
5)			1110(f)									0				1					0					0		0							1
7)			1011(f)									1				0					1					0		0							0

	10)		0111(g)									1				0					0					0
11)			1111(g)									1				1					1					0		1							1
12)			1001(g)									0				0					1					0		0							0

13)			0001(h)									0				0					1					1		0							0
15)			1111(h)									1				0					1					1		1							0

												2				3					4					5		2							3
Частичное решение выглядит следующим образом.
														c												c											c
													d	c										d		c										d	c

	I2																									-	I3
																	I2																13



														-	2																						-	5

									7													12
									7													12
											5												11

		a				?												a											a			?
				b															b											b
				b				?											b											b
			3				4													g(a; b; c; d)											I1
					f(a; b; c; d)															g(a; b; c; d)											h(a; b; c; d)

Далее применяем правило столбца наибольшего ранга к четвертому столбцу и расширяем интервал 1001(f) до двенадцатой точки 1001(g), получаем

интервал 1001(f; g). Удаляем двенадцатую строку и пересчитываем четвертый столбец. Затем применяем это же правило к пятому столбцу и расши-

119

ряем интервал 0101(h) до тринадцатой точки 0001(h), получаем интервал 0 01(h). Удаляем тринадцатую строку и пересчитываем пятый столбец.

1001(f) 0101(h) 0111(f; g) 110 (f) 1001(f; g) 0 01(h)

5)	1110(f)	0	0	0	1	0	0
7)	1011(f)	1	0	0	0	1	0

11)	1111(g)	1	0	1	1	1	0
12)	1001(g)	1	0	0	0

13)	0001(h)	1	1	0	0	0
15)	1111(h)	1	1	1	0	1	0

		4	5	2	3	4	5

Применяем к пятому столбцу правило столбца без единиц. Добавляем в решение интервал I4 = 01(h) и удаляем пятый столбец из матрицы. Частичное решение принимает вид.

				d	c				d	c
I2				d	I2				d	- I3
					- 2

		7
			5
			5					11
a b	?					a b
	3				- 4
	f(a; b; c; d)						g(a; b; c; d)

		d	c
		d	- 5



	15
b
b

a? ?

I1 I4

h(a; b; c; d)

Применяем ко второму столбцу правило столбца наибольшего ранга. Расширяем интервал 0111(f; g) до одиннадцатой точки 1111(g), получаем ин-

тервал 111(f; g). Пересчитываем второй столбец и удаляем одиннадцатую строку.

		0111(	f; g)	110 (f)	1001(f; g)	111(f; g)
		0111(	f; g)	110 (f)	1001(f; g)	111(f; g)
5)	1110(f)	0		1	0	0
7)	1011(f)	0		0	1	0

11)	1111(g)	1		1	1

15)	1111(h)	1		0	1	1

		2		3	4	2

Применяем к третьему столбцу правило столбца с одной единицей. Расширяем интервал 110 (f) до точки 1110(f) (пятая), получаем интервал

I5 = 11 (f), который является максимальным для функции f(a; b; c; d). Третий столбец теперь не содержит единиц, применяем к нему соответ- ствующее правило и включаем I5 в решение. Применяем правило столбца с одной единицей ко второму столбцу. Расширяем интервал 111(f; g) до

точки 1111(h) (пятнадцатая), получаем интервал 111(f; g; h).

120

		110	(f)	1001(f; g)	111(	f; g)	11 (f)	111(f; g; h)
5)	1110(f)		1	0	0
7)	1011(f)		0	1	0		0	0

15)	1111(h)		0	1	1		0

			3	4	2		3	2

Второй столбец теперь не содержит единиц, и сопоставленный ему интервал I6 = 111(f; g; h) нельзя расширить так, чтобы он оставался допусти-

мым для всех функций, включаем I6 в решение.

- I3

- I6

-I5

a b

- 4

f(a; b; c; d)

g(a; b; c; d)

			c
			d
			- I6


b
b

a? ?

I1 I4

h(a; b; c; d)

Применяем к четвертому столбцу правило столбца с одной единицей. Расширяем интервал 1001(f; g) до седьмой точки 1011(f), получаем интер-

âàë 10 1(f; g). Расширяя его так, чтобы он оставался допустимым для f(a; b; c; d) è g(a; b; c; d), получаем интервал I7 = 1 1(f; g), который вклю- чаем в решение. Получаем пустую матрицу. Система ДНФ D, задающая систему булевых функций F, построена.

d -

f(a; b; c; d)

g(a; b; c; d)

h(a; b; c; d)

8ÄÍÔf =

_ a b _ b c d _ a d ;

>ÄÍÔ

a d ;>

c d

b c d

>ÄÍÔh = a b c

c d

b c d:

;

Длина этой системы 7, ранг 18. Как нетрудно убедиться, система является кратчайшей и безызбыточной.

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 1112 / 1712 13 14 15 16 17 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
21.09.201964.51 Кб0Delphi отчёт.doc
#
15.11.2019158.72 Кб3Diagramma_otchet.doc
#
29.05.20153.1 Mб51DIF_calc_2013.pdf
#
29.05.20152.58 Mб46Diplom.docx
#
29.05.20155.95 Mб19Diplom_na_pechat.doc
#
29.05.2015753.61 Кб65DisMathTPU.pdf
#
29.05.2015753.84 Кб64DisMathTPU_new.pdf
#
29.05.20158.69 Mб33dissertatsia.doc
#
25.03.2016419.15 Кб4Dokument_Microsoft_Office_Word_2.PDF
#
29.05.2015118.78 Кб20Dokument_Microsoft_Word (1).doc
#
23.12.201838.93 Кб4Dokument_Microsoft_Word_4.docx