Добавил:

vlacher39 vladymirchervyakov@gmail.com Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Сумский государственный университет

Предмет:

Дискретная математика

Файл:

Дискретный анализ и теория автоматов. Методические указания для самостоятельной работы студента

.pdf

Скачиваний:

Добавлен:

11.06.2020

Размер:

1.59 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 56 / 86 7 8 > Следующая >>>

4 КОНТРОЛЬНА РОБОТА

4.1 Розділ 1. Елементи теорії множин. Постановка завдань

Завдання 1

За діаграмою Венна виразити заштриховану множину формулою через операції алгебри множин.

Варі-	Діаграма Венна	Варі-	Діаграма Венна	Варі-	Діаграма Венна
ант	Діаграма Венна	ант	Діаграма Венна	ант	Діаграма Венна
ант		ант		ант
1		2		3

4		5		6

7		8		9

10		11		12

13		14		15

16		17		18

19		20		21

Варі-	Діаграма Венна	Варі-	Діаграма Венна	Варі-	Діаграма Венна
ант	Діаграма Венна	ант	Діаграма Венна	ант	Діаграма Венна
ант		ант		ант
22		23		24

25		26		27

28		29		30

31		32		33

34		35		36

			Завдання 2

Нехай А = {a1, a2, a3, …}, В = {b1, b2, b3, …}, С = {c1, c2, c3,…}. Відповідності F А В i

G В С задані (див. табл. 11) множинами упорядкованих пар F ={(…), (…),…}, G ={(…), (…),…}. Потрібно виконати наступне:

1.задати відповідності F і G матрицями та стрілковими діаграмами;

2.дослідити відповідності F і G на рефлексівність, антирефлексивність, симетричність, антисиметричність, транзитивність;

3.визначити відповідності:

F –1 і G –1, G F, G G –1, G –1 G, F –1 G –1.

Таблиця 11 – Варіативне задання вихідних даних

№	А	В	С	F	G
1	{1, 2, 3, 4, 5}	{6, 7, 8, 9}	{2, 6, 7, 8, 44}	{(1, 6), (1, 8), (2, 7),	{(6, 6), (7, 7),
				(4, 9), (5, 9)}	(8, 8)}
2	{1, 2, 3, 4, 5}	{2, 6, 7, 8, 9}	{2, 6, 8, 10,	{(1, 6), (1, 8), (2, 7),	{(2, 2), (6, 6),
			12}	(3, 9), (5, 2)}	(8, 8)}
3	{1, 2, 3, 4, 5}	{6, 8, 9, 17}	{2, 6, 7, 8, 17}	{(1, 6), (1, 8), (2, 8),	{(6, 6), (8, 8),
				(4, 9), (5, 17)}	(17, 17)}
4	{1, 2, 3, 4, 5}	{1, 5, 6, 7, 8, 9}	{2, 6, 7, 8, 9}	{(1, 6), (2, 8), (2, 9),	{(6, 6), (8, 8),
				(4, 9), (5, 1)}	(9, 9)}
			52

Продовження табл. 11

№	А	В	С	F	G
5	{1, 2, 3, 4, 5}	{6, 7, 8, 9, 10}	{2, 6, 7, 8, 12}	{(2, 6), (3, 7), (3, 8),	{(6, 6), (7, 7),
				(4, 9), (4, 10)}	(8, 8)}
6	{1, 2, 3, 4, 5,	{1, 2, 3, 4, 5, 6}	{1, 2, 3, 4, 5,	{(1, 6), (1, 4), (2, 4),	{(1, 6), (1, 4),
	6}		6}	(6, 1), (4, 1), (4, 2)}	(2, 4), (6, 2), (4, 6),
					(5, 2)}
7	{1, 2, 3, 4, 5,	{1, 2, 3, 4, 5, 6}	{1, 2, 3, 4, 5,	{(1, 3), (1, 4), (2, 5),	{(1, 6), (1, 2),
	6}		6}	(3, 1), (4, 1), (5, 2)}	(2, 3), (3, 1), (4, 1),
					(5, 2)}
8	{1, 2, 3, 4, 5,	{1, 2, 3, 4, 5, 6}	{1, 2, 3, 4, 5,	{(2, 6), (3, 4), (2, 4),	{(2, 6), (3, 5),
	6}		6}	(6, 2), (4, 3), (4, 2)}	(2, 4), (1, 2), (4, 3),
					(3, 2)}
9	{1, 2, 3, 4, 5,	{1, 2, 3, 4, 5, 6}	{1, 2, 3, 4, 5,	{(5, 6), (1, 4), (3, 4),	{(3, 6), (1, 4),
	6}		6}	(6, 5), (4, 1), (4, 3)}	(3, 5), (6, 5), (4, 2),
					(4, 3)}
10	{1, 2, 3, 4, 5,	{1, 2, 3, 4, 5, 6}	{1, 2, 3, 4, 5,	{(4, 6), (3, 4), (2, 5),	{(4, 5), (3, 5),
	6}		6}	(6, 4), (4, 3), (5, 2)}	(2, 6), (6, 4), (4, 3),
					(5, 2)}
11	{1, 2, 3, 4, 5}	{2, 6, 7, 8, 9,	{2, 6, 8, 10,	{(1, 1), (1, 8), (2, 7),	{(2, 2), (6, 6),
		11}	12}	(3, 9), (5, 11)}	(8, 12), (9, 2),
					(8, 10)}
12	{1, 2, 3, 4, 5}	{6, 8, 9, 17, 22,	{2, 6, 7, 8, 17}	{(1, 6), (1, 8), (2, 8),	{(6, 6), (8, 8), (17,
		30}		(4, 9), (5, 17)}	17), (30, 8),
					(22, 8)}
13	{1, 2, 3, 4, 5}	{1, 5, 6, 7, 8, 9}	{2, 6, 7, 8, 9}	{(1, 6), (2, 8), (2, 9),	{(1, 6), (8, 8),
				(4, 9), (5, 1)}	(9, 9), (7, 8), (5, 7)}
14	{1, 2, 3, 4, 5}	{6, 7, 8, 9, 10,	{2, 6, 7, 8, 12}	{(2, 6), (3, 7), (3, 8),	{(6, 6), (7, 7),
		15}		(4, 9), (4, 10)}	(8, 8), (7, 6),
					(15, 12)}
15	{1, 2, 3, 4, 5}	{6, 7, 8, 9, 10,	{2, 6, 7, 8, 12}	{(2, 6), (3, 7), (3, 9),	{(10, 6), (7, 7),
		11, 12}		(4, 9), (4, 12)}	(8, 8), (7, 2),
					(12, 12)}
16	{1, 2, 3, 4, 5}	{6, 7, 8, 9}	{2, 6, 7, 8, 44}	{(1, 6), (1, 8), (2, 7),	{(6, 6), (7, 7),
				(4, 9), (5, 9)}	(8, 8)}
17	{1, 2, 3, 4, 5}	{2, 6, 7, 8, 9}	{2, 6, 8, 10,	{(1, 6), (1, 8), (2, 7),	{(2, 2), (6, 6),
			12}	(3, 9), (5, 2)}	(8, 8)}
18	{1, 2, 3, 4, 5}	{6, 8, 9, 17}	{2, 6, 7, 8, 17}	{(1, 6), (1, 8), (2, 8),	{(6, 6), (8, 8),
				(4, 9), (5, 17)}	(17, 17)}
19	{1, 2, 3, 4, 5}	{1, 5, 6, 7, 8, 9}	{2, 6, 7, 8, 9}	{(1, 6), (2, 8), (2, 9),	{(6, 6), (8, 8),
				(4, 9), (5, 1)}	(9, 9)}
20	{1, 2, 3, 4, 5}	{6, 7, 8, 9, 10}	{2, 6, 7, 8, 12}	{(2, 6), (3, 7), (3, 8),	{(6, 6), (7, 7),
				(4, 9), (4, 10)}	(8, 8)}
21	{1, 2, 3, 4, 5,	{1, 2, 3, 4, 5, 6}	{1, 2, 3, 4, 5,	{(1, 6), (1, 4), (2, 4),	{(1, 6), (1, 4),
	6}		6}	(6, 1), (4, 1), (4, 2)}	(2, 4), (6, 2), (4, 6),
					(5, 2)}
22	{1, 2, 3, 4, 5,	{1, 2, 3, 4, 5, 6}	{1, 2, 3, 4, 5,	{(1, 3), (1, 4), (2, 5),	{(1, 6), (1, 2),
	6}		6}	(3, 1), (4, 1), (5, 2)}	(2, 3), (3, 1), (4, 1),
					(5, 2)}
23	{1, 2, 3, 4, 5,	{1, 2, 3, 4, 5, 6}	{1, 2, 3, 4, 5,	{(2, 6), (3, 4), (2, 4),	{(2, 6), (3, 5),
	6}		6}	(6, 2), (4, 3), (4, 2)}	(2, 4), (1, 2), (4, 3),
					(3, 2)}

Продовження табл. 11

№

{1, 2, 3, 4, 5,

{1, 2, 3, 4, 5, 6}

{1, 2, 3, 4, 5,

{(5, 6), (1, 4), (3, 4),

{(3, 6), (1, 4),

(6, 5), (4, 1), (4, 3)}

(3, 5), (6, 5), (4, 2),

(4, 3)}

{1, 2, 3, 4, 5,

{1, 2, 3, 4, 5, 6}

{1, 2, 3, 4, 5,

{(4, 6), (3, 4), (2, 5),

{(4, 5), (3, 5),

(6, 4), (4, 3), (5, 2)}

(2, 6), (6, 4), (4, 3),

(5, 2)}

{1, 2, 3, 4, 5}

{2, 6, 7, 8, 9,

{2, 6, 8, 10,

{(1, 1), (1, 8), (2, 7),

{(2, 2), (6, 6),

11}

12}

(3, 9), (5, 11)}

(8, 12), (9, 2),

(8, 10)}

{1, 2, 3, 4, 5}

{6, 8, 9, 17, 22,

{2, 6, 7, 8, 17}

{(1, 6), (1, 8), (2, 8),

{(6, 6), (8, 8), (17,

30}

(4, 9), (5, 17)}

17), (30, 8),

(22, 8)}

{1, 2, 3, 4, 5}

{1, 5, 6, 7, 8, 9}

{2, 6, 7, 8, 9}

{(1, 6), (2, 8), (2, 9),

{(1, 6), (8, 8),

(4, 9), (5, 1)}

(9, 9), (7, 8), (5, 7)}

{1, 2, 3, 4, 5}

{6, 7, 8, 9, 10,

{2, 6, 7, 8, 12}

{(2, 6), (3, 7), (3, 8),

{(6, 6), (7, 7),

15}

(4, 9), (4, 10)}

(8, 8), (7, 6),

(15, 12)}

{1, 2, 3, 4, 5}

{6, 7, 8, 9, 10,

{2, 6, 7, 8, 12}

{(2, 6), (3, 7), (3, 9),

{(10, 6), (7, 7),

11, 12}

(4, 9), (4, 12)}

(8, 8), (7, 2),

(12, 12)}

{1, 2, 3, 4, 5,

{1, 2, 3, 4, 5, 6}

{1, 2, 3, 4, 5,

{(2, 6), (3, 4), (2, 4),

{(2, 6), (3, 5),

(6, 2), (4, 3), (4, 2)}

(2, 4), (1, 2), (4, 3),

(3, 2)}

{1, 2, 3, 4, 5,

{1, 2, 3, 4, 5, 6}

{1, 2, 3, 4, 5,

{(5, 6), (1, 4), (3, 4),

{(3, 6), (1, 4),

(6, 5), (4, 1), (4, 3)}

(3, 5), (6, 5), (4, 2),

(4, 3)}

{1, 2, 3, 4, 5,

{1, 2, 3, 4, 5, 6}

{1, 2, 3, 4, 5,

{(4, 6), (3, 4), (2, 5),

{(4, 5), (3, 5),

(6, 4), (4, 3), (5, 2)}

(2, 6), (6, 4), (4, 3),

(5, 2)}

{1, 2, 3, 4, 5}

{2, 6, 7, 8, 9,

{2, 6, 8, 10,

{(1, 1), (1, 8), (2, 7),

{(2, 2), (6, 6),

11}

12}

(3, 9), (5, 11)}

(8, 12), (9, 2),

(8, 10)}

{1, 2, 3, 4, 5}

{6, 8, 9, 17, 22,

{2, 6, 7, 8, 17}

{(1, 6), (1, 8), (2, 8),

{(6, 6), (8, 8), (17,

30}

(4, 9), (5, 17)}

17), (30, 8),

(22, 8)}

{1, 2, 3, 4, 5}

{2, 6, 7, 8, 9}

{2, 6, 8, 10,

{(1, 6), (1, 8), (2, 7),

{(2, 2), (6, 6),

12}

(3, 9), (5, 2)}

(8, 8)}

Завдання 3

Які з функцій f: X→Y на множині R дійсних чисел (див. табл. 12) є сюр’єктивними,

ін’єктивними, бієктивними, взаємно однозначними, якщо x [a, b], y [c, d]?

Таблиця 12 - Варіативне задання вихідних даних

№

f1(x, y)

f2(x, y)

f3(x, y)

f4(x, y)

[a, b]

|cosx|

[–3, 3]

[–27, 27]

|sinx|

10+x

[–10, 10]

[0, 10000]

2x3

[–3, 3]

[–54, 54]

Продовження табл. 12

№	f1(x, y)	f2(x, y)	f3(x, y)	f4(x, y)	[a, b]	[c, d]

4	10	2x	2x3	cosx	[–2, 2]	[–16, 16]
5	x2	2x	20	\|sinx\|	[0, 10]	[0, 100]
6	\|cosx\|	x3	2x	5	[–2, 2]	[–8, 8]
7	10-x	2x	sinx	30	[–20, 20]	[–40, 40]
8	10	3x	2+sinx	5x	[0, 4]	[1, 81]
9	x2	10	\|cosx\|	2x3	[–2, 2]	[–16, 16]
10	\|sinx\|	x2	2	2x	[–2, 2]	[1/4, 4]
11	cosx	1	\|x3\|	2x	[–1, 1]	[1/2, 2]
12	10	10-x	2x2	\|sinx\|	[–2, 2]	[8, 12]
13	2x-1	sinx	3x	2	[0, 3]	[–1, 5]
14	2x3	10-x	10	sinx	[–1, 2]	[–2, 16]
15	2x	sinx	x2	20	[0, 5]	[2, 32]
16	cosx	2x	50	x3	[0, 5]	[0, 125]
17	30	sinx	10-x	2x3	[0, 5]	[0, 250]
18	\|x\|	20	sinx	3x	[–3, 3]	[1/27, 27]
19	2x3	cosx	10-x	10	[–2, 2]	[–16, 16]
20	2x-10	5x-1	20	x2-2	[–3, 5]	[–16, 24]
21	x3	2x	2	cosx	[–2, 2]	[–8, 8]
22	\|sinx\|	x2	10/x	10	[1, 2]	[5, 10]
23	3x	20	\|sinx\|	\|x\|	[–1, 3]	[1/3, 27]
24	5	x3	2x	5x-2	[–1, 2]	[–7, 8]
25	x2	2x	1	2x	[–2, 2]	[–4, 4]
26	2x	cosx	x3	5	[–2, 2]	[–8, 8]
27	sinx	10	10x-5	x4	[–2, 2]	[–25, 15]
28	5	5x-1	3x	sinx	[–2, 2]	[–11, 9]
29	5-x3	cosx	10	2x	[–2, 2]	[–3, 13]
30	2sinx	2x-5	x2	20	[0, 5]	[–4, 27]
31	x3	2x-1	1	\|cosx\|	[–1, 1]	[–1, 1]
32	\|sinx\|	2x-1	5	5-x	[0, 3]	[0, 7]
33	2x3	1	\|x\|	2x	[–1, 1]	[–2, 2]
34	2	x4	2x3	cosx	[–1, 1]	[–2, 2]
35	x2	2x	1	sinx	[–1, 1]	[–2, 2]
36	\|sinx\|	x4	10	10+x	[–10, 10]	[0, 10000]

Примітка. Аргументи тригонометричних функцій мають розмірність «радіан».

4.2 Розділ 2. Елементи математичної логіки. Постановка завдань

Завдання 1

1)скласти таблицю істинності для заданої (див. табл. 13) логічної функції f (x, y, z, u);

2)скласти контактну схему, яка технічно реалізує задану логічну функцію f (x, y, z, u);

3)замінити контактну схему комбінаційною схемою на логічних елементах у базисі

І-Або-Не.

	Таблиця 13 – Варіативне задання функції f (x, y, z, u)

№		f (x, y, z, u)	№		f (x, y, z, u)	№		f (x, y, z, u)
1			13			25
1	(x y + x y) u + y z + z		13	(x u + x y) z + x y z + z u		25	(xy+ x y ) u + y z u + yz

2			14			26
2	(x y + x z) u + yz + z		14	(xu+ x z) y + x y z + z u		26	(x y +yz) u + yzu + y z

3			15			27
3	(x z + x z) y + y z + u		15	(xy+ x z) u + x y u + z u		27	(xz+ x z) y + y z + zu

4			16			28
4	(x z + x y) z + y z + yu		16	(x y + x y) u + xy z + zu		28	(x z + x z) y + y zu + y z

5			17			29

	(x z + x y)z+ y (z+u) + x z			(xy+ x z) u + y z + y z			(x z + x y)u+ y ( x +z)+ x z

6			18			30
6	(xy+ x u ) z + y u z + xz		18	(x z + x z) u + x y z + y		30	(xu+ x u ) y + y z u + xz

7			19			31
7	(xy+ x z) u + y z + z u		19	(x z + x y) u + y zu + yz		31	(xy+ x z) u + y z u + z

8			20			32
8	(xy+ x z) u + y u z + yz		20	(xz+ x y) z+ y (z+u) + x z		32	(x y + x u) z + y z u + yz

9			21			33
9	(xz+ x u ) y + y z u +xyz		21	(xy+ x z) u + y z u + xy		33	(xz+ x y) u + y z u + xy

10			22			34

	(xz+ x u) y + y z u + xz			(xu+ x z) y + y z u + z u			(xy+ x u) z + xzu + y u

11			23			35
11	(xu+ x z) y + y z u + x z		23	(xy+ x z ) u + y z u + yz		35	(xu+ x y) z + y z u + x z

12			24			36
12	(x u + x z) y + y zu + x z		24	(x z + x u) u + y z u + yz		36	(x u + x y) z + x y z + z u

Завдання 2

1)cкласти контактну схему за заданими умовами ії роботи (див. табл. 14). Умови роботи зазначаються десятковими номерами всіх наборів (x1, x2, x3), на яких логічна функція f (x1, x2, x3), що реалізується контактною схемою, має значення 1);

2)замінити побудовану контактну схему комбінаційною схемою на логічних елементах у заданому базисі (Або – Не, І – Не).

Таблиця 14 – Варіативне задання умов роботи контактної та логічної схем і функціонального базису

№	Номер	Функціональ	№	Номер	Функціональ	№	Номер	Функціональ
	наборі	-ний базис		наборі	-ний базис		наборі	-ний базис
	в			в			в
1	1, 3, 4	І-Не	1	1, 2, 3	Або-Не	2	1, 2, 6	І-Не
			3			5
2	1, 2, 4	І-Не	1	1, 3, 6	Або-Не	2	1, 3, 5	І-Не
			4			6
3	1, 4, 5	І-Не	1	1, 5, 7	Або-Не	2	1, 4, 7	І-Не
			5			7
4	2, 3, 4	І-Не	1	2, 4,6	Або-Не	2	2, 4, 6	Або-Не
			6			8
5	2, 4, 5	І-Не	1	2, 3, 6	Або-Не	2	2, 3, 5	Або-Не
			7			9
6	2, 5, 6	І-Не	1	2, 5, 7	Або-Не	3	2, 6, 7	Або-Не
			8			0
7	3, 4, 5	І-Не	1	3, 6, 7	І-Не	3	1, 2, 7	Або-Не
			9			1
8	3, 5, 6	І-Не	2	3, 4, 6	І-Не	3	1, 3, 7	Або-Не
			0			2

9	3, 4, 7	І-Не	2	3, 5, 7	І-Не	3	1, 4, 6	Або-Не
			1			3
1	4, 5, 7	Або-Не	2	4, 5, 6	І-Не	3	1, 5, 7	Або-Не
0			2			4
1	1, 5, 6	Або-Не	2	1, 2, 5	І-Не	3	1, 2, 3	Або-Не
1			3			5
1	2, 4, 7	Або-Не	2	2, 3, 7	І-Не	3	1, 6, 7	Або-Не
2			4			6

Завдання 3

Логічну функцію f (x1, x2, x3) задано номерами всіх наборів (x1, x2, x3), на яких f (x1, x2, x3) = 1 (див. табл. 15). Потрібно виконати наступне:

1) побудувати таблицю істинності функції f (x1, x2, x3).

Таблиця 15 – Варіативне задання номерів усіх наборів, на яких f (x1, x2, x3) = 1

№	Номер	№	Номер	№	Номер	№	Номер
	наборів		наборів		наборів		наборів
1	1, 2, 6	10	1, 5, 7	19	3, 4, 5	28	2, 4,6
2	1, 3, 5	11	1, 2, 3	20	3, 5, 6	29	2, 3, 6
3	1, 4, 7	12	1, 6, 7	21	3, 4, 7	30	2, 5, 7
4	2, 4, 6	13	1, 3, 4	22	4, 5, 7	31	3, 6, 7
5	2, 3, 5	14	1, 2, 4	23	1, 5, 6	32	3, 4, 6
6	2, 6, 7	15	1, 4, 5	24	2, 4, 7	33	3, 5, 7
7	1, 2, 7	16	2, 3, 4	25	1, 2, 3	34	4, 5, 6
8	1, 3, 7	17	2, 4, 5	26	1, 3, 6	35	1, 2, 5
9	1, 4, 6	18	2, 5, 6	27	1, 5, 7	36	2, 3, 7

2) подати функцію f (x1, x2, x3) формулами в ДДНФ і ДКНФ.

Завдання 4

1) Логічну функцію f (x, y, z, u) (табл. 16) подати в ДДНФ і ДКНФ.

Таблиця 16 – Варіативне задання функції f(x,y,z,u)

№		f (x, y, z, u)	№		f (x, y, z, u)	№		f (x, y, z, u)

1	(xy+ x y ) u + y z u + yz		13	(x y + x y) u + y z + z		25	(x u + x y) z + x y z + z u

2	(x y +yz) u + yzu + y z		14	(x y + x z) u + yz + z		26	(xu+ x z) y + x y z + z u


3	(xz+ x z) y + y z + zu		15	(x z + x z) y + y z + u		27	(xy+ x z) u + x y u + z u


4	(x z + x z) y + y zu + y z		16	(x z + x y) z + y z + yu		28	(x y + x y) u + xy z + zu


5	(x z + x y) u + y ( x +z) + x z		17	(x z + x y) z + y (z+u) + x z		29	(xy+ x z) u + y z + y z


6	(xu+ x u ) y + y z u + xz		18	(xy+ x u ) z + y u z + xz		30	(x z + x z) u + x y z + y


7	(xy+ x z) u + y z u + z		19	(xy+ x z) u + y z + z u		31	(x z + x y) u + y zu + yz


8	(x y + x u) z + y z u + yz		20	(xy+ x z) u + y u z + yz		32	(xz+ x y) z+ y (z+u) + x z


9	(xz+ x y) u + y z u + xy		21	(xz+ x u ) y + y z u + xyz		33	(xy+ x z) u + y z u + xy


10	(xy+ x u) z + xzu + y u	22	(xz+ x u) y + y z u + xz	34	(xu+ x z) y + y z u + z u


11	(xu+ x y) z+ y z u + x z	23	(xu+ x z) y + y z u + x z	35	(xy+ x z ) u + y z u + yz


12	(x u + x y) z + x y z + z u	24	(x u + x z) y + y zu + x z	36	(x z + x u) u + y z u + yz

2)за методом Квайна мінімізувати в ДНФ одержану за п. 1) функцію fДДНФ (x, y, z, u);

3)за методом Квайна мінімізувати в КНФ одержану за п. 1) функцію fДКНФ (x, y, z, u).

Завдання 5

Логічну функцію f (x1, x2, x3, x4) задано номерами всіх наборів (x1, x2, x3, x4), на яких вона набуває значення 1 (табл. 17). Потрібно виконати наступне:

1)подати функцію f (x1, x2, x3, x4) формулою в ДДНФ;

2)за методом Вейча – Карно мінімізувати в ДНФ одержану в п.1) функцію f (x1, x2, x3, x4), з натурними позначеннями змінних із бази функції в розмітці граней таблиці на універсальній карті Карно.

Таблиця 17 – Варіативне задання десяткових номерів наборів, на яких f (x1, x2, x3, x4) = 1

№	Номери наборів	№	Номери наборів	№	Номери наборів
1	0, 1, 3, 4, 5, 6, 15	13	0, 1, 3, 4, 5, 6, 11	25	0, 1, 2, 3, 10, 12, 15
2	1, 2, 3, 4, 5, 9, 14	14	1, 2, 4, 7, 14, 15	26	0, 1, 3, 6, 9, 10, 11
3	1, 2, 3, 4, 7, 14	15	0, 1, 4, 5, 6, 10, 14	27	1, 5, 7, 10, 12, 14
4	0, 2, 4, 6, 10, 14	16	2, 3, 4, 7, 10, 12, 15	28	2, 4, 7, 10, 12, 15
5	2, 3, 5, 8, 10, 13	17	0, 2, 4, 5, 7, 11, 12	29	0, 2, 3, 6, 8, 9, 12
6	2, 6, 7, 9, 10, 11	18	0, 2, 5, 6, 7, 8, 9, 15	30	2, 5, 7, 10, 14, 15
7	1, 2, 7, 10, 12, 15	19	3, 4, 5, 7, 10, 12, 15	31	0, 3, 6, 7, 9, 10, 14
8	0, 1, 3, 7, 11, 12	20	3, 5, 6, 8, 9, 12, 13	32	0, 3, 4, 6, 9, 10, 11
9	1, 4, 6, 7, 8, 9, 15	21	0, 3, 4, 7, 9, 12, 13	33	3, 5, 7, 8, 9, 12, 14
10	0, 1, 5, 7, 9, 10, 14	22	4, 5, 7, 9, 12, 13	34	4, 5, 6, 7, 11, 12, 13
11	1, 2, 3, 4, 5, 6, 14	23	0, 1, 5, 6, 7, 11, 12	35	0, 1, 2, 5, 8, 10, 13
12	1, 6, 7, 8, 9, 12, 13	24	0, 2, 4, 7, 10, 12, 15	36	2, 3, 7, 8, 9, 12, 13

Завдання 6

Логічну функцію f (x1, x2, x3, x4) задано номерами всіх наборів (x1, x2, x3, x4), на яких вона приймає значення 1 (табл. 18). Потрібно виконати наступне:

1)подати функцію f (x1,x2,x3,x4) формулою в ДДНФ;

2)за методом Вейча – Карно мінімізувати в КНФ одержану в п.1) функцію f (x1, x2, x3, x4), з позначеннями змінних в узагальнених кодах під час розмітки граней таблиці на універсальній карті Карно.

Таблиця 18 - Варіативне задання десяткових номерів наборів, на яких f (x1, x2, x3, x4) =1

№	Номери наборів	№	Номери наборів	№	Номери наборів
1	1, 3, 4, 6, 15	13	0, 3, 4, 5, 11	25	0, 3, 10, 12, 15
2	1, 2, 4, 9, 14	14	1, 2, 7, 14, 15	26	0, 1, 9, 10, 11
3	1, 2, 4, 7, 14	15	0, 1, 6, 10, 14	27	5, 7, 10, 13, 14
4	0, 2, 3, 4, 10	16	2, 3, 4, 12, 15	28	2, 4, 10, 12, 15
5	3, 5, 10, 11, 13	17	0, 2, 7, 11, 12	29	0, 2, 8, 9, 12
6	2, 6, 7, 8, 15	18	0, 2, 8, 9, 15	30	2, 5, 7, 10, 14
7	1, 2, 9, 10, 14	19	5, 7, 10, 12, 15	31	6, 7, 9, 10, 14

8	0, 1, 3, 10,	12	20	6, 8, 9, 12, 13	32	0, 3, 4, 10, 11
9	1, 6, 7, 8, 11		21	0, 3, 4, 12, 13	33	3, 5, 9, 12, 14
10	0, 1, 7, 9, 14		22	4, 7, 9, 12, 13	34	4, 5, 6, 12, 13
11	1, 2, 3, 4,	5	23	5, 6, 7, 11, 12	35	2, 5, 8, 10, 13
12	1, 6, 7, 12,	13	24	0, 4, 7, 12, 15	36	2, 3, 7, 8, 13

4.3 Розділ 3. Елементи теорії графів. Постановка завдань

Завдання 1

Граф Gn,m = (V, E) з вершинами v1, v2,…, vn V і ребрами e1, e2,…, em E задано (варіативно за табл.19) переліком неорієнтованих ребер ei = (vi, vk). Цього достатньо для визначення всіх відношень суміжності та інцидентності в заданому графі. Потрібно виконати наступне:

1)накреслити діаграму графа та визначити, чи відповідає цей граф кожному з таких означень: скінченний, неорієнтований, орієнтований, змішаний, порожній, тривіальний, нуль-граф, повний, мультиграф, граф Бержа, псевдограф, простий, помічений, зважений;

2)визначити степені всіх вершин графа;

3)скласти список суміжностей вершин графа;

4)скласти список інциденцій ребер графа;

5)скласти матрицю суміжностей графа;

6)скласти матрицю інциденцій графа.

Таблиця 19 - Варіативне задання графа Gn,m = (V, E)

№	n	m	e1, . . ., em

1	5	8	(v1, v2), (v1, v3), (v2, v3), (v2, v4), (v3, v5), (v3, v3), (v4, v5), (v4, v5)
2	5	8	(v1, v3), (v1, v5), (v1, v5), (v2, v2), (v2, v3), (v2, v4), (v3, v4), (v4, v5)
3	5	9	(v1, v2), (v1, v3), (v1, v3), (v2, v2), (v2, v3), (v2, v5), (v3, v4), (v3, v5), (v4, v5)
4	5	8	(v1, v2), (v1, v4), (v1, v4), (v2, v3), (v2, v4), (v2, v5), (v3, v4), (v3, v5)
5	5	11	(v1, v2), (v1, v3), (v1, v4), (v1, v5), (v2, v2), (v2, v3), (v2, v4), (v3, v4), (v3, v5), (v3, v5), (v4, v5)
6	5	10	(v1, v2), (v1, v3), (v1, v5), (v2, v2), (v2, v3), (v2, v4), (v3, v4), (v3, v5), (v3, v5), (v4, v4)
7	5	9	(v1, v2), (v1, v2), (v1, v3), (v1, v4), (v2, v4), (v2, v5), (v3, v3), (v3, v4), (v4, v4)
8	5	9	(v1, v1), (v1, v3), (v1, v4), (v2, v3), (v2, v4), (v2, v2), (v2, v5), (v3, v4), (v3, v5)
9	5	10	(v1, v2), (v1, v3), (v2, v3), (v2, v4), (v2, v5), (v3, v3), (v3, v4), (v3, v5), (v4, v5), (v5, v5)
10	5	10	(v1, v3), (v1, v4), (v1, v5), (v1, v5), (v2, v3), (v2, v4), (v2, v5), (v3, v3), (v3, v4), (v4, v5)
11	6	10	(v1, v2), (v1, v3), (v2, v3), (v2, v6), (v2, v4), (v3, v5), (v3, v3), (v4, v5), (v4, v5), (v4, v6)
12	6	10	(v1, v3), (v1, v5), (v1, v5), (v1, v6), (v2, v2), (v2, v3), (v2, v4), (v2, v6), (v3, v4), (v4, v5)
13	6	11	(v1, v2), (v1, v3), (v1, v3), (v1, v6), (v2, v2), (v2, v3), (v2, v5), (v3, v4), (v3, v6), (v3, v5), (v4, v5)
14	6	10	(v1, v2), (v1, v4), (v1, v4), (v2, v3), (v2, v4), (v2, v5), (v2, v6), (v3, v4), (v3, v5), (v5, v6)
15	6	11	(v1, v2), (v1, v3), (v1, v4), (v1, v5), (v1, v6), (v2, v2), (v2, v3), (v2, v4), (v3, v4), (v3, v5), (v3, v6)
16	6	11	(v1, v2), (v1, v3), (v1, v5), (v2, v2), (v2, v3), (v2, v4), (v2, v6), (v3, v4), (v3, v5), (v3, v5), (v4, v6)
17	6	11	(v1, v2), (v1, v2), (v1, v3), (v1 v4), (v2, v4), (v2, v5), (v3, v3), (v3, v4), (v4, v4), (v4, v6), (v5, v6)
18	6	10	(v1, v1), (v1, v3), (v1, v4), (v1, v6), (v2, v4), (v2, v5), (v2, v6), (v3, v4), (v3, v5), (v3, v6)
19	6	10	(v1, v2), (v1, v3), (v2, v3), (v2, v4), (v2, v5), (v2, v6), (v3, v3), (v3, v4), (v3, v5), (v4, v5)
20	6	11	(v1, v3), (v1, v4), (v1, v5), (v1, v5), (v2, v3), (v2, v4), (v2, v5), (v3, v3), (v3, v4), (v3, v6), (v4, v5)
21	7	11	(v1, v2), (v1, v3), (v2, v3), (v2, v6), (v2, v7), (v3, v5), (v3, v3), (v4, v5), (v4, v5) ,(v4, v6), (v4, v7)
22	7	10	(v1, v3), (v1, v5), (v1, v5), (v1, v6), (v2, v2), (v2, v3), (v2, v4), (v2, v6), (v3, v4), (v4, v5)
23	7	11	(v1, v3), (v1, v3), (v1, v6), (v1, v7), (v2, v2), (v2, v3), (v2, v5), (v3, v4), (v3, v6), (v3, v7), (v4, v7)
24	7	11	(v1, v2), (v1, v4), (v1, v4), (v1, v7), (v2, v3), (v2, v4), (v2, v5), (v2, v6), (v3, v7), (v3, v5), (v5, v6)

25	7	11	(v1, v2), (v1, v3), (v1, v4), (v1, v5), (v1, v6), (v2, v2), (v2, v3), (v2, v4), (v2, v7), (v3, v4), (v3, v7)
26	7	11	(v1, v2), (v1, v3), (v1, v7), (v2, v2), (v2, v3), (v2, v4), (v2, v7), (v3, v4), (v3, v5), (v3, v7), (v4, v6)
27	7	11	(v1, v2), (v1, v2), (v1, v3), (v1 v4), (v2, v4), (v2, v5), (v3, v3), (v3, v4), (v4, v4), (v4, v6), (v5, v6)
28	7	10	(v1, v1), (v1, v4), (v1, v6), (v2, v3), (v2, v4), (v2, v7), (v2, v6), (v3, v4), (v3, v5), (v3, v7)
29	7	10	(v1, v2), (v1, v7), (v2, v3), (v2, v4), (v2, v6), (v3, v4), (v3, v7), (v4, v5), (v5, v5), (v6, v7)
30	7	11	(v1, v3), (v1, v4), (v1, v5), (v1, v5), (v2, v3), (v2, v4), (v2, v7), (v3, v7), (v3, v6), (v4, v5), (v4, v6)
31	8	11	(v1, v2), (v1, v3), (v2, v3), (v2, v6), (v2, v7), (v3, v8), (v4, v5), (v4, v5), (v4, v6), (v4, v7), (v4, v8)
32	8	10	(v1, v3), (v1, v5), (v1, v5), (v1, v8), (v2, v4), (v2, v8), (v3, v4), (v4, v5), (v4, v8), (v8, v8)
33	8	11	(v1, v2), (v1, v3) ,(v1, v3), (v1, v6), (v1, v7), (v1, v8), (v2, v5), (v3, v4), (v3, v8), (v3, v7), (v4, v7)
34	8	11	(v1, v2), (v1, v4), (v1, v4), (v1, v7), (v2, v3), (v2, v4), (v2, v6), (v3, v7), (v3, v5), (v5, v8), (v8, v8)
35	8	11	(v1, v3), (v1, v4), (v1, v5), (v1, v6), (v2, v2), (v2, v8), (v2, v4), (v2, v7), (v3, v4), (v3, v7), (v5, v8)
36	5	8	(v1, v3), (v1, v5), (v1, v5), (v2, v2), (v2, v3), (v2, v4), (v3, v4), (v4, v5)

Завдання 2

Орграф Gn,m = (V, E) з вершинами v1, v2, …, vn V і дугами e1, e2, …, em E задано (варіативно за табл.20) переліком дуг ei = (vi, vk), вагами вершин hi, i = 1, …, n та дуг pi, i = 1, …, m. Потрібно виконати наступне:

1)накреслити діаграму графа та визначити, чи відповідає цей граф кожному з таких означень: мультиграф, псевдо граф;

2)визначити степені, напівстепені виходу і заходу всіх вершин графа. Які з вершин графа є витоком та стоком (за наявності)?

3)вважаючи граф вершинно зваженим, скласти список суміжностей та ваг вершин

графа;

4)вважаючи граф реберно зваженим, скласти список інциденцій та ваг дуг графа;

5)скласти матрицю суміжностей графа;

6)скласти матрицю інциденцій графа;

7)вважаючи граф реберно зваженим, скласти матрицю ваг дуг графа;

8)вважаючи граф вершинно зваженим, скласти матрицю ваг вершин графа.

Таблиця 20 - Варіативне задання орграфа Gn,m = (V, E)

№	n	h1, …, hn	m	e1, ..., em	p1, …, pm
1	5	13, 27, 8,	7	(v1, v3), (v2, v3), (v2, v4), (v3, v1), (v3, v3), (v5, v2),	15, 9, 14, 26, 22, 17,
		37, 15		(v4, v5)	8
2	5	7, 12, 54,	7	(v1, v3), (v1, v5), (v1, v5), (v2, v2), (v3, v2),(v3, v4),	7, 12, 54, 23, 16, 32,
		23, 16		(v5, v4)	51
3	5	5, 12, 7, 9,	7	(v1, v3), (v1, v3),(v2, v3), (v2, v2), (v3, v4), (v4, v5),	5, 12, 7, 9, 10, 41, 25
		10		(v5, v2)
4	5	8, 5, 20, 12,	7	(v1, v2), (v1, v4), (v1, v4), (v2, v2), (v2, v5), (v3, v2),	8, 5, 20, 12, 15, 20,
		15		(v5, v3)	31
5	5	9, 12, 24,	7	(v1, v5), (v2, v2), (v2, v3), (v3, v4), (v3, v5), (v5, v3),	9, 12, 24, 16, 24, 14,
		16, 24		(v4, v5)	16
6	5	7, 21, 8, 15,	7	(v1, v2), (v1, v5), (v2, v2), (v2, v4), (v3, v1), (v3, v4),	7, 21, 8, 15, 10, 15,
		10		(v3, v5)	10
7	5	5, 7, 15, 10,	7	(v1, v2), (v1, v4), (v2, v4), (v2, v5), (v3, v3), (v3, v1),	5, 7, 15, 10, 6, 15, 10
		6		(v4, v5)
8	5	8, 9, 10, 6,	7	(v1, v1), (v1, v4), (v2, v3), (v2, v4), (v3, v2),(v3, v5),	8, 9, 10, 6, 11, 8, 12
		11		(v5, v1)
9	5	6, 8, 21, 15,	7	(v1, v2), (v1, v3), (v2, v2), (v2, v4), (v2, v4), (v5, v3),	6, 8, 21, 15, 10, 16,
		10		(v4, v5)	20
10	5	8, 9, 11, 16,	7	(v1, v3), (v1, v5), (v2, v3), (v2, v4), (v3, v1), (v3, v3),	8, 9, 11, 16, 7, 10, 15

<<< < Предыдущая 1 2 3 4 56 / 86 7 8 > Следующая >>>