Rukovodstvo_po_resheniju_zadach

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

1. Наносим на карту Вейча заданную функцию f.

2.			Строим карту Вейча для её инверсии (т.е. для f ) .
																														1		1
3.			Находим минимальную ДНФ функции f .																												1	1
4. Результат инвертируем по теореме де Моргана.																																	1
Например, найдём минимальную КНФ функции
																														1		1	1
f (A, B,C, D) (0, 1, 2, 6, 7, 8, 12, 15).
																															Рис. 1
Решение. Наносим её на карту Вейча (рис.1). Инвертируем функцию (рис. 2). Находим ми-
нимальную ДНФ инверсии:
																															1		1
f		(A, B,C, D)		ABC						BCD ACD ACD.
																														1			1
Полученное выражение инвертируем по теореме де Моргана:
																														1	1	1
f (A, B,C, D) (A B C)(B C D)(A C D)(A C D).
																															1
В минимальную КНФ входит 8 знаков дизъюнкции и 12 букв.
																															Рис. 2
Ответ: 8, 12.

3.5. Минимизация в классе ДНФ с учётом неопределённых состояний

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

На рис. 1–28 приведены примеры минимизации булевых формул.

1	1		×		1	×		1			×		1			×	1	×
	×	1			×	1	×	1		1		1	×		1	×		1
	Рис. 1					Рис. 2					Рис. 3					Рис. 4

1 ×	×	1		×	1	1			1	×	×		1	1	×	×
1		1		1		1		1		1	1				1	×
1 ×	×	1		× 1	1	1		1		×	×			×		1
1		1		1	×	1		× 1		×	1		1	×	1	1
Рис. 9				Рис. 10					Рис. 11					Рис. 12

1		×			1				1			1			1					1 ×		1		×				1			1		1
1					×				1		×	1			×					×				1				× 1					1
1					1				1		×	1			1					1 1		×									×
1 ×		1			×				1			×			1					× ×		1		×				1 ×			1		1
	Рис. 13										Рис. 14										Рис. 15								Рис. 16
	1			1							×			1							1		1		1					1		×			1
	1		×			1				1				1		1					1		×		×				1	×		1
	1					×					×			1			1				1		×							1		×			1
	1			×						1	×			1			1				×		1						1	×
	Рис. 17										Рис. 18										Рис. 19								Рис. 20

1	×	1			1	×	1	1		× 1		1	1		1	1		1
1	×	×	1		×	1		1		1	×		×		× ×			1
× 1		1			1			1		×		×	1		1	×	1	×
1 ×		×			× 1		1	1		1					1	1		1
	Рис. 21					Рис. 22					Рис. 23					Рис. 24

11.2. Синтез комбинационных схем

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

Комбинационные схемы обычно содержат несколько выходов. Однако в

данной работе рассматриваются схемы лишь с одним выходом, как наиболее

простые (рис. 1). На входы схемы подаются двоичные уровни напряжения,

Лог.

f

низкие или высокие, обозначаемые нулями и единицами соответственно,

схема

снимаемые с выходов четырёх триггеров A, B, C, D. Выходы триггеров явля-

ются парафазными, т.е. каждый триггер имеет прямой выход и инверсный: A

и A, B и B , C и C , D и D (как показано на рис. 1). Выход схемы обозначен

Рис. 1

буквой f.

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

1)триггеры B и C находятся в состояниях единицы, т.е. B = C = 1, а триггеры A и D – в состояниях нуля, т.е. A = D = 0;

2)триггеры B и D находятся в состояниях нуля: B = D = 0;

3)состояния триггеров B и C: B = C = 0;

4)состояния триггеров A, B и D: A = 0, B = D = 1;

5)триггеры B, C и D находятся в состояниях единицы;

6)состояния триггеров A, B и D: A = D = 1, B = 0;

Для контроля указать, сколько в схеме элементов И, сколько элементов ИЛИ и сколько всего букв в минимальной форме булевой функции, описывающей работу схемы.

Решение.

1) согласно первому условию: B = C = 1 и A = D = 0. Запишем буквы в алфавитном порядке. Тогда соответствующие им значения образуют набор значений переменных 0110:

A B C D

0 1 1 0

На этом наборе выходной сигнал комбинационной схемы должен быть

равным единице: B

f (0,1,1,0) = 1.

В соответствии с этим в таблице 1 на пересечении колонки f со строкой 6 ставим единицу;

2) во втором условии говорится, что f = 1 при B = D = 0. Триггеры A и C не упоминаются. Следовательно, получаем четыре набора:

A B C D

0 0 0 0

0 0 1 0

1 0 0 0

1 0 1 0

так как переменные A и C могут принимать следующие значения:

A = 0, C = 0; A = 0, C = 1; A = 1, C = 0; A = 1, C = 1.

Переводим двоичные коды 0000, 0010, 1000, 1010 в десятичную систему: 0, 2, 8, 10 соответственно. В таблице на пересечении колонки f c этими числами ставим единицы;

Таблица 1

			A		В C			D			f
	0		0		0	0	0		1
	1		0		0	0	1		1
	2		0		0	1	0		1
	3		0		0	1	1		0
	4		0		1	0	0		0
	5		0		1	0	1		1
	6		0		1	1	0		1
	7		0		1	1	1		1
	8		1		0	0	0		1
	9		1		0	0	1		1
	10		1		0	1	0		1
	11		1		0	1	1		1
	12		1		1	0	0		0
	13		1		1	0	1		0
	14		1		1	1	0		0
	15		1		1	1	1		1
			A
						1
					1	1	1				D
		1			1		1
		1			1	1	1

C

Рис. 2

1

1

1

1

1

Рис. 3

3)по аналогии с предыдущим случаем получаем ещё четыре набора, на которых f = 1: 0000, 0001, 1000, 1001. В десятичной системе: 0, 1, 8, 9 соответственно. Отмечаем в таблице эти наборы.

Встроках 0 и 8 (в колонке f) единицы уже стоят, вторично их не ставим, отмечаем только строки 1

и 9;

4)согласно четвёртому условию A = 0, B = D = 1. Триггер C в условии не упоминается, следовательно, функция f принимает единичное значение на двух наборах: 0101 и 0111, т.е. 5 и 7. В строках 5 и 7 ставим единицы;

5)пятое условие: f = 1, если B = C = D = 1. Триггер A не упоминается, поэтому в таблице отмечаем два набора: 0111 и 1111, т.е. 7 и 15. В строке 7 единица уже стоит, вторично её не ставим;

6)в последнем условии не упоминается триггер C. Соответственно получаем два набора, на которых f = 1: 9 и 11. В строке 9 единица уже стоит. Отмечаем только строку 11. A &Таким образом, таблица заполнена следующим образом: f = 1 на набо-

рах: 0, 1, 2, 5, 6, 7, 8, 9, 10, 11, 15. Все остальные наборы, не удовлетворяю-

B

щие ни одному из заданных условий, в колонке f отмечаем нулями.

B

&

Согласно таблице СДНФ искомой функции имеет вид:

C

f(A,B,C,D) = (0, 1, 2, 5, 6, 7, 8, 9, 10, 11, 15).

1

A

Наносим её на карту Вейча (рис. 2) и минимизируем. Минимальная

&

f

ДНФ имеет вид

C

f AB

B C ACD BCD A CD.

Эта форма содержит 13 вхождений переменных.

&

Находим минимальную КНФ. Для этого сначала строим карту Вейча

для инверсии той же функции (рис. 3). Система расположения букв вокруг

этой карты не указана. Она такая же, как на рис. 2. По этой карте находим

&

минимальную форму для функции f :

f

ABC

AB

D

BC

D

BCD A

B

CD.

Инвертируем полученное выражение по теореме де Моргана и нахо-

дим минимальную КНФ:

Рис.

4

&

1

f (A B C)(A B D)(B C D)(B C D)(A B C D).

&

Эта форма также содержит 13 вхождений переменных. Поскольку обе

формы (ДНФ и КНФ) по числу вхождений букв одинаковы, то, как было

&

условлено выше, схему строим на основе минимальной ДНФ.

Схема приведена на рис. 4. Согласно этому рисунку в комбинационной

схеме 5 элементов И, один элемент ИЛИ, а минимальная форма содержит 13

&

вхождений переменных. Логические элементы могут содержать различное

число входов. Например, на рис. 4 два элемента И содержат по два входа и

три элемента – по три входа. Однако в данной работе при подсчёте числа

&

элементов на число входов схем И и ИЛИ внимания не обращаем.

Схему, приведённую на рис. 4, можно изобразить в более компактном

представлении, так, как она изображена на рис. 5.

Ответ: 5, 1, 13 (т.е. схема содержит пять элементов И, один элемент

Рис. 5

ИЛИ; в минимальную ДНФ входит 13 букв).

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

1)A = B = 1, C = 0 (триггеры A и B находятся в состоянии единицы, а триггер C – в состоянии нуля;

2)C = D = 0, B = 1 (триггеры C и D находятся в состоянии нуля, а триггер D – в состоянии единицы);

3)A = C = D = 1, B = 0 (триггеры A, C и D находится в единичном состоянии, а триггер B – в нулевом);

4)A = C = 1, B = D = 0 (триггеры A и C находятся в состоянии единицы, а триггеры B и D – в состоянии нуля);

5)A = B = D = 0, C = 1 (триггеры A, B и D находятся в состоянии нуля, а триггера C – в состоянии единицы).

Решение.

1) как и в предыдущем примере, буквы располагаем в алфавитном порядке. В первом условии триггер D не упоминается, следовательно, его состояние является безразличным. В соответствии с этим получаем два набора, на которых f = 1: 1100 и 1101, Это числа 12 и 13. В таблице 2 на пересечении колонки f и строк с номерами 12 и 13 ставим единицы;

2)согласно второму условию получаем также два набора, на которых f = 1: 0100 и 1100, т.е. 4

и12. Эти строки в таблице 2 отмечаем единицами;

3)в третьем условии представлен только один двоичный набор: 1011, в десятичной системе – число 11. Отмечаем его в таблице;

4)четвёртое условие также даёт один набор: 1010. Это десятичное число 10;

5)последнее (пятое) условие даёт ещё один набор: 0010. В десятичной

системе – это число 2.																																								Таблица 2
	СДНФ искомой функции имеет вид:
																																									A	В C		D	f
f = (2, 4, 10, 11, 12, 13).
																																								0	0	0	0	0	0
	Находим минимальную ДНФ (рис. 6):
																																								1	0	0	0	1	0
f ABC B C D ABC BCD.
																																								2	0	0	1	0	1
	В этом выражении 12 букв.
																																								3	0	0	1	1	0
																																								4	0	1	0	0	1
																																								5	0	1	0	1	0
																										1										1	&
																																								6	0	1	1	0	0
																																								7	0	1	1	1	0
	1				1						1			1												1			&							1				8	1	0	0	0	0
	1										1			1		1
																																				1				9	1	0	0	1	0
	1										1			1		1										1														10	1	0	1	0	1
																																								11	1	0	1	1	1
	1		1								1					1
																																Рис. 9								12	1	1	0	0	1
																										Рис. 8
	Рис. 6											Рис. 7
																																								13	1	1	0	1	1
																																								14	1	1	1	0	0
	Находим СДНФ инверсии найденной функции, наносим её на																																							15	1	1	1	1	0
карту Вейча и минимизируем (рис. 7):

f BC AD BC .

Применив теорему де Моргана к выражению f , получаем минимальную КНФ.

f(B C )(A D)(B C).

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

Ответ: 1, 3, 6 (т.е. комбинационная схема содержит один элемент И, три элемента ИЛИ; в минимальную КНФ входит шесть букв).

11.3. Синтез комбинационного преобразователя кодов

На вход комбинационного преобразователя (рис. 1) при помощи триггеров A, B, C, D подаются десятичные цифры в виде двоичных кодов. Эти цифры по заданному закону преобразуются в двоичные числа и поступают на выход преобразователя, представленного булевыми функциями f1,

f2, f3, f4. Требуется найти и минимизировать функции f1, f2, f3																													и f4, где f1				соответствует старшему
разряду, и построить логическую схему преобразователя.
			Пример 1. Построить комбинационную схему, преобразующую десятич-
																																				A				Комби-
ные цифры в выходные числа по закону: 3, 6, 8, 13, 9, 5, 4, 1, 7, 12, где первому
																																								наци-
выходному числу соответствует входная цифра 0, второму – 1, третьему – 2 и так																																								онный
																																								преоб-
далее до числа 12, которому соответствует входная цифра 9. Для контроля найти
																																								разова-
число вхождений переменных для каждой из четырёх функций f1, f2, f3 и f4, пред-																																									тель
ставленных в минимальных ДНФ.
			Решение. Сначала установим соответствие между входными и выходны-
ми кодами. Для этого пронумеруем, начиная с нуля, все коды выходной последовательности:
0					1						2	3		4	5					6			7	8							9 – десятичные цифры,													(1)
3					6						8	13		9	5					4			1	7							12 – выходные числа,													(2)
где в (1) приведены десятичные цифры, а в (2) – соответствующие им выходные числа.
			Все числа, входные и выходные, необходимо представить в																														Таблица 1
двоичном виде, так как преобразователь работает в двоичной системе.
Соответствие между ними зададим таблицей (табл. 1). Буквой Д в таб-
																																	Д	A	В C		D			f1		f2	f3		f4
лице обозначена колонка с десятичными цифрами. В колонках A, B, C,																																	0	0	0	0	0		0			0	1		1
D записаны входные двоичные числа, а в колонках																							f1, f2, f3, f4 приведе-										1	0	0	0	1		0			1	1		0
ны выходные коды.																																	2	0	0	1	0		1			0	0		0
			Рассматривая								таблицу как				таблицу					истинности				для					четырёх				3	0	0	1	1		1			1	0	1
функций, зависящих от одних и тех же переменных A,																								B, C, D, нахо-									4	0	1	0	0		1			0	0	1
																																	5	0	1	0	1		0			1	0	1
дим СДНФ этих функций:
																																	6	0	1	1	0		0			1	0	0
			f1 = (2, 3, 4, 9);
																																	7	0	1	1	1		0			0	0	1
			f2 = (1, 3, 5, 6, 8, 9);
																																	8	1	0	0	0		0			1	1	1
			f3 = (0, 1, 8); f4 = (0, 3, 4, 5, 7, 8).																														9	1	0	0	1		1			1	0	0
			Во всех колонках f1, f2, f3, f4											в строках 10–15 крестиками отмече-																			10	1	0	1	0		×			×	×	×
ны неопределённые состояния. С их учётом минимальные ДНФ имеют																																	11	1	0	1	1		×			×	×	×
вид (карты Вейча приведены на рис. 2–5):																																	12 1 1 0 0						×			×	×	×
																																	13	1	1	0	1		×			×	×	×
f BC D BC AD; f													A BCD CD BD;										f3	A B C AD;
												2																					14 1 1 1 0 ×									× × ×
1
f4	C			D			BD CD;																										15 1 1 1 1 ×									× × ×

Схема преобразователя кодов изображена на рис. 6.

Ответ: 7, 8, 5, 6 (т.е. первая функция содержит 7 вхождений переменных, вторая – 8, третья – 5 и четвёртая – 6).

× ×

1

× ×

1

× ×

× ×

1

× ×

× ×

1

× ×

× ×

1

1

1 ×

1

1 ×

1

1

f3

=

×

1

f4

=

×

1

f1 =

×

1

f2 =

1 ×

1 ×

1

1 ×

1

Рис. 2

Рис. 3

Рис. 4

Рис. 5

Пример 2. Построить схему, преобразующую

&

1

&

1

десятичные цифры в выходные числа по зако-

&

ну: 13, 9, 11, 6, 2, 4, 15, 5, 3, 8. Для контроля

&

&

&

1

1

найти число вхождений переменных для каж-

&

дой из четырёх функций f1, f2, f3

и f4.

&

&

1

Решение. Как и в первом примере, сначала устанавливаем соот-																																		Таблица 2
ветствие между входными десятичными цифрами и выходными
																																		Д	A В C D				f1		f2		f3		f4
кодами:
																																		0	0	0	0	0	1		1		0		1
								0 12 3 4 56 78 9 – десятичные цифры,
																																		1	0	0	0	1	1		0		0		1
								13 9 11 6 2 4 15 5 3 8 – выходные числа.
																																		2	0	0	1	0	1		0		1		1
		Строим таблицу истинности (табл. 2). Неопределёнными
																																		3	0	0	1	1	0		1		1		0
остаются те же состояния, что и в таблице 1.
																																		4	0	1	0	0	0		0	1		0
		Находим СДНФ функций f1, f2, f3 и f4:																																5	0	1	0	1	0		1	0		0
								f1 = (0, 1, 2, 6, 9);																										6	0	1	1	0	1		1	1		1
								f2 = (0, 3, 5, 6, 7);																										7	0	1	1	1	0		1	0		1
								f3 = (2, 3, 4, 6, 8);																										8	1	0	0	0	0		0	1		1
																																		9	1	0	0	1	1		0	0		0
								f4 = (0, 1, 2, 6, 7, 8).
																																		10	1 0 1 0				×		×	×		×
		Минимизируем их в классе ДНФ:
																																		11	1	0	1	1	×		×	×		×
														f2 BD BC CD A B C D;
f1 CD			A B C AD;																															12	1 1 0 0 ×						× × ×
																																		13	1	1	0	1	×		×	×		×
f3 A D BC BD;														f4 B D BC A B C.
																																	14		1 1 1 0				×	×		×		×
		На основе этих функций строим комбинационный преобра-
																																	15		1	1	1	1	×	×		×		×

зователь. В отличие от первого примера в данном случае система

функций содержит повторяющиеся конъюнкции: и четвёртая функции). При построении схемы их вать по два раза.

Ответ: 7, 10, 6, 7.

A B C (первая и четвёртая функции), BC (третья можно изобразить по одному разу, а использо-

12.2. Синтез синхронных автоматов на T-триггерах

Триггер типа T имеет три входа: R и S и вход T. Входы R и S являются установочными. На них подаются уровни напряжения: при R = 0 и S = 1 триггер переходит в нулевое состояние, при R = 1 и S = 0 – в единичное. Состояние R = S = 1 – это режим хранения информации. Состояние R = S = 0 является запрещённым. По входу T, называемому счётным входом, триггер меняет свои состояния под действием отрицательных фронтов входных прямоугольных импульсов.

В схеме синхронного автомата, состоящего из нескольких триггеров, тактовый импульс непосредственно управляет каждым триггером, как показано на рис. 1. Тактовые импульсы поступают на один из входов элементов И, выходы которых подключены к счетным входам триггеров А1, А2, … , Аn. Ко вторым входам схем И присоединены выходы комбинационной схемы, представляющей собой преобразователь входного двоичного кода в выходной код, разряды которого обозначены символами f1, f2, … , fn. Буквой Y обозначена шина установки автомата в нулевое состояние.

&

ТТ

	схема
ТТ	Комбинационная
ТТ

Зафиксируем какой-либо момент времени между тактовыми импульсами, когда G = 0. Триггеры находятся в некоторых состояниях. Им соответствует определенный набор значений аргументов А1, А2, … , Аn. На этом наборе выходы f1, f2, … , fn комбинационной схемы образуют набор высоких и низких уровней напряжения. Низкими уровнями соответствующие схемы И будут заперты, высокими – открыты (по своим входам). Когда на вход G поступит импульс, он пройдет только через открытые схемы И, и соответствующие триггеры сменят свои состояния.

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

								Пример.
	Таблица 1							Построить схему, меняющую свои состояния по замкнутому
								циклу в последовательности
							10, 1, 8, 9, 0, 3, 12, 2, 6, 7, 14, 4, 15, 11, 5, 13.
	Дес. A B C D		fA fB		fC	fD
								Для контроля указать, сколько букв содержится в минималь-
10		1 0 1 0	1	0	1	1
								ных ДНФ каждой из функций, описывающих работу комбинацион-
1		0 0 0 1	1	0	0	1
								ной схемы.
8		1 0 0 0	0	0	0	1
9		1 0 0 1	1	0	0	1		Решение.
0		0 0 0 0	0	0	1	1		Так как всего состояний 16, то для построения схемы необхо-
3		0 0 1 1	1	1	1	1		димо четыре триггера. Обозначим их буквами А, B, C, D и составим
12		1 1 0 0	1	1	1	0		таблицу, в которой отразим все переходы автомата из одного состо-
2		0 0 1 0	0	1	0	0		яния в другое (табл. 1).
6		0 1 1 0	0	0	0	1		В левой части таблицы, где расположены колонки, озаглав-
7		0 1 1 1	1	0	0	1		ленные буквами А, В, С, D, перечислены двоичные состояния авто-
14		1 1 1 0	1	0	1	0		мата согласно заданной последовательности. В колонке, обозначен-
4		0 1 0 0	1	0	1	1		ной «Дес.», указаны те же состояния, но в десятичной системе.
15		1 1 1 1	0	1	0	0		Правая часть таблицы содержит четыре колонки, озаглавлен-
11		1 0 1 1	1	1	1	0		ные знаками: fA, fB, fC, fD. Это функции, описывающие состояния
5		0 1 0 1	1	0	0	0		входов триггеров A, B, C и D.
13		1 1 0 1	0	1	1	1		Заполняется правая часть следующим образом. В верхней

строке в левой части записано двоичное число 1010, т.е. А = С = 1, В = D = 0. Под действием входного импульса (точнее – по его отрицательному фронту) автомат должен перейти в состояние 0001, согласно двоичному числу, записанному слева во второй строке. Это произойдет в том случае, если тактовый импульс поступит на вход триггера A, на вход триггера C, и на вход триггера D, но не пройдёт на вход триггера B. В связи с этим в строке с кодом 1010 в правой части таблицы записываем 1011.

Предположим, что после первого тактового импульса автомат перешел в состояние 0001. Второй импульс должен пройти только на входы триггеров A и D. Под действием этого импульса триггер A перейдет в единицу, триггер D – в нуль, а триггеры B и C останутся в прежних состояниях, т.е. в нулевых. В результате автомат окажется в состоянии 1000, и так далее до конца таблицы.

Когда автомат дойдёт до состояния 1101 (это десятичное число 13), следующий тактовый импульс переведёт его в состояние 1010 и начнётся повтор того же цикла работы автомата.

			A											A										A											A
B		1	1				1				B		1								B		1	1				1				B					1	1
						1	1			D			1	1						D			1								D			1			1				D
		1	1			1	1							1			1							1			1							1			1	1
fA =											fB =										fC =											fD =
			1														1							1				1						1 1				1
					C											C										C										C
				Рис. 2.											Рис. 3.										Рис. 4.											Рис. 5.

Находим минимальные ДНФ булевых функций

fA, fB, fC, fD (карты Вейча приведены на рис. 2–5 соот-

fA

ветственно):

fA G

ТТ

fB

fA BD AD ACD BC D;

fB ABC

ACD ABC;

fB G

ТТ

fC ABC BCD ACD A C D;

D A

fD AC

B

D

A

B

C

ACD ABD

.

Каждое из этих выражений необходимо умно-

fC G

ТТ

жить на букву G, обозначающую генератор синхроим-

пульсов. Тогда получим:

TA (

fD

BD AD ACD BC D)G;

ТТ

fD G

TB (ABC ACD ABC)G;

fC

TC ( ABC

BCD ACD A C D)G;

D A

TD (AC

B

D

A

B

C

ACD ABD

)G.

Это окончательный список всех тех булевых

функций, в соответствии с которыми работает разра-

ботанный автомат. Полная схема его приведена на рис.

Рис.

6.

Согласно условию задачи необходимо определить, сколько вхождений переменных содержится в каждой из четырёх булевых функций, описывающих работу комбинационной схемы, но без учёта импульсов генератора. Без учёта генератора G функция fA состоит из 10 букв, функция fB

– из 9, fC – из 12 и функция fD – из 15.

Ответ: 10, 9, 12, 15.

13.КОМБИНАТОРИКА

13.1.Задачи на применение основных формул комбинаторики

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

Правило произведения:

если один элемент некоторого множества можно выбрать n способами, а второй после него – m способами, то выбор двух элементов в заданном порядке возможен mn способами.

При помощи этого правила выводятся основные формулы для комбинаторных конфигураций, где учитывается порядок записи элементов:

1) число перестановок без повторений:

Pn = n!,

где n – число элементов, из которых состоят перестановки; 2) число перестановок с повторениями:

	n!		(n1	n2	n3	nk )!		,
Pn = n1!n2!n3! nk ! =				n1!n2!n3! nk !

где ni – число неразличимых элементов (i = 1, 2, 3, …, k), n – число всех элементов, участвующих в перестановках, k – число групп элементов, в которых элементы неразличимы;

3) число размещений без повторений из n элементов по m:

Am	n!		;
n	(n m)!

4) число размещений с повторениями из n элементов по m:

Anm nm .

Кроме них в комбинаторике рассматриваются ещё две формулы для комбинаторных конфигураций, где порядок записи элементов значения не имеет:

5) число сочетаний без повторений из n элементов по m:

Cm	n!	.
n	(n m)!m!

6) число сочетаний с повторениями из n элементов по m:

Cnm Cnm m 1 Cnn m1 1.

Примеры.

Пример 1. Сколько существует четырёхзначных восьмеричных чисел, в каждом из которых сначала идут цифры, кратные двум (не менее одной), а затем цифры, кратные трём (также не менее одной), если числа с нуля не начинаются и возможны повторы цифр?

Решение. Кратными двум являются восьмеричные цифры 0, 2, 4, 6, а кратными трём – 0, 3, 6. Разобьём задачу на ряд подзадач:

а) пусть кратной двум является только первая цифра, тогда после неё идут три цифры, кратные трём. Так как с нуля числа не начинаются, то на первое место можно поставить одну цифру из трёх: 2, 4, 6. Повторы разрешены, следовательно, на каждом из остальных трёх мест можно ставить по одной из трёх цифр: 0, 3, 6. По правилу произведения: 3·33 = 81;

б) теперь пусть кратные двум цифры занимают два первых разряда. На первое место можно поставить одну цифру из трёх, а на второе – одну цифру из четырёх, так как нулю запрещено стоять только на первом месте. На третье и четвёртое места можно ставить по одной цифре из трёх. Следовательно, получаем 3·4·32 = 108;