ДМ Практикум

1.14a) ((B ∩C ) (A ∩ B) (A ∩C )) ∩((A ∩ B) (B ∩C )) = ,

b)(A \ B) (B \ A) = (B \ A) (A \ B).

1.15a) (A \ B) (B \C ) (C \ A) = (A B C) (A ∩ B ∩C) ,

b)B ∩C A ∩C , если B A .

1.16a) A ∩(B C) = ( A ∩ B) ( A ∩C),

b) ( A ∩ B) C = A ∩(B C), если C A.

1.17a) (C ∩ B) (B ∩ A) (B ∩C ) (A ∩ B) (A ∩C ) =U ,

b)(A ∩ B) C = A ∩(B C ) , если C A.

1.18a) A \ (B C ) = (A\ B) ∩(A\C ),

b)P Q , если P = (A\ B) \C, Q = A\ (B \C ).

1.19

a)(A\ (B C)) (B \ (A C)) (C \ (A B)) = A B C (A ∩B ∩C),

b)((A B) \C) ((A B C) \ (A ∩B ∩C)).

1.20a) A B = (A B) (A B),

b)(A \C ) (B \C ) , если A B .

1.21a) (A B) (B A) = (A ∩ B) (A B),

b)(A B) ∩(B C ) (A C ).

1.22a) A B = (A\ B) (B \ A),

b)(C \ B) (C \ A) , если A B .

1.23a) (A\ B) ((A C ) ∩B) = (A\C ) ((A B) ∩C ),

b)(A B) ∩C = A (B ∩C ) , если A C .

1.24a) (A (A\ B)) ∩(U \ B) = ,

b)((A\C ) (B \ A)) (A B).

1.25a) (A ∩ B) (B C) = (A\ B) C,

b)A B и B C , если A B C .

1.26a) A B = A B (A ∩ B).

b)A ∩ B (A ∩ X) (B ∩ X).

1.27a) A B C = A B C,

b)A = B , если A B = A ∩ B .

111

1.28a) A B = (A B) (A ∩ B),

b)A B , если B A.

1.29a) A (B C) =U ∩(A B C),

b) ( A ∩C) (B ∩C) A B, если A ∩ B ∩C = .

1.30a) A (B C) = (A B C) (A ∩(B C)),

b)(A B) C A ∩ B ∩C.

2Для отношения R M × M , М={1,2,3,4,5,6,7} построить матрицу отноше-

ния, найти область определения Dom(R), область значений Im(R), дополне- ние R , обратное отношение R−1 . Определить, выполняются ли для данного отношения свойства рефлексивности, антирефлексивности, симметричности, антисимметричности, транзитивности.

2.1R = {(x, y) | 2x > y};

2.2R = {(x, y) | (x + y) четно;

2.3R = {(x, y) | x - y ³ 0} ;

2.4R = {(x, y) | x , y имеют один и тот же остаток от деления на 2};

2.5R = {(x, y) | x £ y};

2.6R = {(x, y) | (x + 2 y) четно;

2.7R = {(x, y) | (x + y) делится на 3;

2.8R = {(x, y) | x - y < 0} ;

2.9R = {(x, y) | (x + y) £ 7} ;

2.10R = {(x, y) | x и y взаимно просты;

2.11R = {(x, y) | x - y = 2};

2.12R = {(x, y) | x делитель y} ;

2.13R = {(x, y) | x = y +1} ;

2.14R = {(x, y) | x × y £ 25) ;

2.15R = {(x, y) | x делится на y} ;

2.16R = {(x, y) | (x + y) нечетно};

2.17R = {(x, y) | x + 2 = y};

2.18R = {(x, y) | x > y + 3};

2.19R = {(x, y) | x × y ³ 20};

112

2.20R = {(x, y) | (x + 3y) четно};

2.21R = {(x, y) | x , y имеют один и тот же остаток от деления на 3};

2.22R = {(x, y) | (x + y) делится на 3} ;

2.23R = {(x, y) | x - y < 4};

2.24R = {(x, y) | x , y имеют общий делитель, отличный от 1};

2.25R = {(x, y) | x × y < 30};

2.26R = {(x, y) || x - y |= 2} ;

2.27R = {(x, y) | x × y делится на 4 };

2.28R = {(x, y) || x - y |= 3};

2.29R = {(x, y) | (x + y) делится на 4};

2.30R = {(x, y) || x - y |£ 2}.

3Для булевой функции F (A,B,C) построить таблицу истинности, по таблице истинности

найти СДНФ и СКНФ. Упростить СДНФ, по упрощенной СДНФ построить релейно- контактную схему. Построить многочлен Жегалкина, выяснить принадлежность функции F классамT0,T1,S,L, M .

3.1		(														)													3.2			(														)
	F =			(A → B ) C													B .													F = (A B) →													C				B .
3.3	F = (B								)								C.														=
																																														.
								A					C
		(													)														3.4	F		(A				B)C						A
3.5																													3.6
																														F = A (B → C ) B .
	F = A → (B C ) A																					.
3.7																													3.8
	F = (A B) B → C.																													F = (A C) →											(													)
																																										B				A								.
3.9	F = (A C) (B →																							).					3.10
																				A										F = A → C (B																						) .
																																																	A
																																				(											)
3.11	F = (AB C) → (B																									).			3.12			(								)							(															)	.
																							C							F = A → ABC
																																									→ AB BC
3.13	F = (A B																					→ B ).							3.14	F = (A BC ) (B →																												).
										C		) (A																																									AC
3.15	F		A			C					(BC											AC					)		3.16
																														F = A → (B C ) BC .
		= (						)									→											.
3.17																													3.18						BC) (A → B ).
	F = A (B → C ) B .
																														F = (AC
3.19					(												)												3.20	F =B (							→ (B																		)).
	F = A					BC A									→ B									.												AC															A

113

3.21	(				(B C)										)												3.22	(					)
	F = A									ABC								C → A.											F = AB (B → C) → AC															.
3.23	(						)				(												)				3.24
																													F = (A C) →B (A → C).
	F = C → B							→ ABC												AC				.
3.25																											3.26
	(									)	(											)							F = AB → C (C													).
	F = BC					→ CA					→ B							C					→ A.																	A
3.27																											3.28		F = (AB
																					.													AC ) (B → AC ).
	F = A (B C ) → ABC
3.29	f = (ab (c a)) → abc																										3.30														)
																													(ab c)			→ (a b							c

4Орграф задан матрицей смежности A(G) . Требуется:

а) нарисовать граф; б) выделить компоненты сильной связности;

в) в ассоциированном графе найти эйлерову цепь (или цикл).

	1	1	0	0
1		0	0	0
	0	0	1	1
4.1	0	0	1	0
	0	0	0	1
	1	0	1	0
	0	1	0	0
1		0	0	0
	0	0	0	1
4.4	0	0	1	1
	0	1	0	1
	0	0	0	0

	1	0	0	1
0		0	1	0
	0	1	1	0
4.7	1	0	0	0
	0	0	0	1
	1	0	1	0

0	0					0	1	0	0
0	0				1		1	0	0
1	0			4. 2		0	0	0	1
1	0	.				0	0	1	0
0	0					0	0	0	1
1	1					0	1	1	0
0	0					1	1	0	0
0	0				1		0	0	0
0	0			4.5		0	0	1	1
1	0	.				0	0	0	0
0	0					0	0	1	1
1	1					1	0	1	1
1	0					1	0	1	0
0	0				0		0	0	1
0	0			4. 8		1	0	1	0
1	0		.			0	1	0	1
0	0					0	0	0	1
1	1					1	0	0	0

0	0		1 0 1 0 0 0
0	0		0 1 1 1 1 0
1	0			1 1 0 0 0 0
1	0	.	4.3	0 1 0 0 1 0		.
0	0			0 0 0 1 0 0
1	1			1 1 0 0 1 1
0	1		1 1 0 0 0 0
0	0		1 0 0 0 0 0
1	0			0 0 1 1 0 1
1	0	.	4.6	0 0 1 0 0 1		.
0	0			1 0 1 0 1 1
0	1			0 0 0 1 0 0
0	0		0 0 0 1 0 0
0	0		0 0 0 0 1 0
1	0				1 0 1 1 0 0
1	0	.	4. 9		1 0 1 0 0 0		.
0	0				0 1 0 0 1 0
1	1				1 0 1 0 1 1

114

1 0 1 0 1 1								1 0 0
0 0 0 0 0 1								0 0 1
	0	0	1	1	1	0			0	1	1
4.10	0	0	1	0	1	0	.	4.11	1	0	0
	0	0	0	1	0	0			0	1	0
	0	1	0	0	0	1			1	0	1
1 0 0 0 0 1								0 1 0
1 1 1 0 1 0								1 0 0
	0	0	1	1	1	0			0	0	0
4.13	0	0	1	0	1	0	.	4.14	0	0	1
	0	0	0	1	0	0			0	0	1
	1	0	0	0	0	0			1	0	1
1 1 0 0 0 0								1 0 0
1 0 0 0 0 0								0 0 0
	0	0	1	0	1	1			0	1	1
4.16	1	0	1	1	1	0	.	4.17	0	1	0
	0	0	0	0	0	1			0	0	1
	0	0	1	0	1	1			0	1	0
0 0 0 1 1 0								1 0 1
0 0 0 1 0 0								0 0 0
	1	1	0	0	0	1			1	0	0
4.19	0	1	0	0	0	1	.	4.20	1	0	1
	1	0	0	0	0	0			0	0	0
	0	1	1	1	0	1			1	1	1
0 0 1 0 0 0								0 1 1
0 1 0 0 0 0								0 1 0
	0	0	0	0	1	1			0	0	0
4.22	0	1	0	1	1	1	.	4.23	0	0	0
	0	1	0	1	1	0			0	0	0
	1	0	0	0	1	1			1	1	0

1	0	0		1 0 0 0 1 0
0	1	0		0 0 0 1 0 0
0	1	0			0		1	1	1	0	0
0	0	0	.	4.12	0		1	1	0	0	0	.
0	0	0			1		0	0	0	0	0
0	1	1			1		1	1	0	0	1
0	0	0		0 1 0 0 0 0
0	0	0		1 0 0 0 0 0
1	0	0			1		0	1	0	1	1
1	1	0	.	4.15	0		0	0	0	1	1	.
1	1	1			0		0	0	1	0	0
0	1	1			0		0	0	1	1	1
0	0	1		0 0 0 0 1 1
0	0	1		0 0 0 0 1 0
1	0	0			1		1	1	0	0	0
1	0	1	.	4.18	1		0	1	0	0	1	.
0	0	0			0		1	0	0	0	0
1	1	1			1		0	1	1	1	0
1	0	0		0 1 1 0 0 1
0	0	0		0 1 0 0 0 0
0	1	1				0 0 0 1 1 1
0	1	0	.	4. 21		0 0 0 1 0 1							.
0	1	1				0 0 0 0 1 0
0	1	0				1 1 0 1 0 1
0	0	0		0 1 1 0 0 0
0	0	0		0 1 0 0 0 0
1	1	1			1		0	0	1	1	0
0	0	1	.	4.24	0		0	0	1	0	0	.
1	1	0			1		1	0	1	0	1
1	1	0			0		0	0	0	1	0

115

0 0 0 1					1 0			1 0 0 1					1 0			1 1 0 1 0 1
1		0 1 0 0 1						0 0 0 0 0 0								0 0 0 0 0 0
	0	0	0	1	0	0			0	0	1	0	0	1			1	0	1	1	1	0
4.25	0	0	1	0	0	1	.	4.26	1	0	1	0	1	0	.	4.27	1	0	0	1	0	0	.
	1	0	0	0	0	0			1	0	1	0	0	1			0	0	0	0	1	0
	0	1	1	1	0	1			1	1	1	0	1	0			1	1	1	0	0	0
0 0 0 1					0 0			0 0 1 0 0 1								1 1			1	0 0 0
0 1			0 0 0 0					1		0 0 1			1 1			0 1			0 0 0 0
	0	1	1	0	1	1			0	1	0	1	1	0			1	0	1	0	1	1
4.28	0	0	0	0	1	1	.	4.29	0	1	0	0	0	0	.	4.30	0	0	0	1	1	0	.
	0	1	1	0	1	0			0	0	0	1	1	0			1	1	0	1	1	1
	1	0	0	0	1	1			0	0	0	0	0	1			0	0	0	0	0	1

5Нагруженный граф задан матрицей весов Wk (G) . Требуется:

а) найти остовное дерево минимального веса;

б) найти кратчайшие пути от вершины vi до остальных вершин графа, ис-

пользуя алгоритм Дейкстры;

в) задать раскраску вершин графа.

5.1	W1(G) , i = 1.	5.2	W1(G) , i = 2 .	5.3	W1(G) , i = 3.
5.4	W1(G) , i = 4 .	5.5	W1(G) , i = 5 .	5.6	W1(G) , i = 6 .
5.7	W2(G) , i = 1.	5.8	W2(G) , i = 2 .	5.9	W2(G) , i = 3.

5.10	W2(G) , i = 4 .		5.11 W2(G) , i = 5 .			5.12	W2(G) , i = 6 .
5.13	W3	(G) , i = 1.	5.14	W3(G) , i = 2 .		5.15	W3	(G) , i = 3.
5.16	W3	(G) , i = 4 .	5.17	W3(G) , i = 5 .		5.18 W3		(G) , i = 6 .
5.19	W4	(G) , i = 1.	5.20	W4	(G) , i = 2 .	5.21 W4		(G) , i = 3.
5.22	W4	(G) , i = 4 .	5.23	W4	(G) , . i = 5 .	5.24	W4	(G) , i = 6 .
5.25	W5	(G) , i = 1.	5.26	W5(G) , i = 2 .		5.27	W5	(G) , i = 3.
5.28	W5	(G) , i = 4 .	5.29	W5(G) , i = 5 .		5.30 W5		(G) , i = 6 .

116

04∞

W1(G) = 2

3∞

0∞∞

W3(G) = 2

34

023

W5(G) = ∞

1∞

4	∞	2	3	∞
0	1	1	∞	2
			∞
1	0	5		3
1	5	0	4	∞ ;
∞	∞	4	0	1
		∞
2	3		1	0
∞	∞	2	3	4
0	3	∞	1	2
			∞
3	0	5		1
∞	5	0	4	1	;
1	∞	4	0	∞
2	1	1	∞	0
2	3	∞	1	∞
0	1	1	∞	4
			∞	∞
1	0	5
					.
1	5	0	4	2
∞	∞	4	0	3
4	∞	2	3	0

		0	5	2	2	∞	3
		5	0	∞	3	4	∞
			∞			∞
		2		0	6		4
W (G) =								;
2		2	3	6	0	5	∞
		∞	4	∞	5	0	2
			∞		∞
	3			4		2	0
		0	8	∞	4	6	∞
		8	0	2	2	∞	4
		∞				∞
			2	0	9		6
W (G) =								;
4		4	2	9	0	8	∞
		6	∞	∞	8	0	1
		∞	4	6	∞	1	0

6Построитьконечныйдетерминированныйавтомат(определитьмножества S, X,Y , по- строитьтаблицуидиаграммуМура), построитьканоническуютаблицу, канонические уравнения. Нарисоватьсхемуустройства, используялогическиеэлементы«И», «ИЛИ», «НЕ».

Вовсехзадачах x (t) ,y (t) B, B = {0,1}, t = 1,2, 3….

6.1y (t) = x (t) → x (2) , t ≥ 2, y (1) = 1.

6.2y (t) = x (t −1) → x (t), t ≥ 2, y (1) = 0.

6.3y (t) = x1 (t −1) x2 (t), t ≥ 2, y (1) = 1.

6.4Y = 101101101...

6.5y (t) = x (t) & x (1).

6.6y (t) = x1 (t −1) x2 (t), t ≥ 2, y (1) = 1.

117

6.7y (t) = x (t −1), t ≥ 2, y (1) = 1.

6.8y (t) = x (t) x (t −1), t ≥ 2, y (1) = 1.

6.9y (t ) = x1 (t −1) & x2 (t ), t ≥ 2, y (1) = 0.

6.10Y = 110110110….

6.11y (t) = x (t) | x (t −1), t ≥ 2, y (1) = 0.

6.12y (t) = x1 (t −1) x2 (t), t ≥ 2, y (1) = x1(1).

6.13y (t ) = x (t ) → x (t −1), t ≥ 2, y (1) = 1.

6.14y (t) = x (t) x (t −1), t ≥ 2, y (1) = 1.

6.15y (t) = x1 (t −1) & x2 (t), t ≥ 2, y (1) = 0.

6.16y (t) = x1 (1) x1 (t).

6.17y (t) = x (t ) x (t −1), t ≥ 2, y (1) = 0.

6.18y (t) = x1 (t −1) x2 (t), t ≥ 2, y (1) = x2(1).

6.19y (t) = x (t) x (1).

6.20y (t) = x1 (t −1) → x2 (t), t ≥ 2, y (1) = 1.

6.21y (t) = x (t) x (2), t ≥ 2, y (1) = 0.

6.22y (t) = x2 (t ) → x1 (t −1), t ≥ 2, y (1) = 1.

6.23y (t) = x (1) → x (t), t ≥ 2, y (1) = 0.

6.24y (t) = x1 (t −1) ↓ x2 (t), t ≥ 2, y (1) = 0.

6.25y (t) = x (t −1) x (t), t ≥ 2, y (1) = x (1) 1.

6.26y (t) = x (2) x (t), t ≥ 2, y (1) = 0.

6.27y (t) = x (t) x (2), t ≥ 2, y (1) = 1.

6.28y (t) = x1 (t −1) x2 (t), t ≥ 2, y (1) = x2(1).

6.29y (t) = x (t −1) x (t), t ≥ 2, y (1) = 0.

6.30Y = 100100100….

118

ОТВЕТЫИУКАЗАНИЯ

Глава I. Множества и операции над ними.

1.8а) {b;c} ; б) {a;b;c;e} ; в) {a;b} ; г) {e} ; д) {b} ; е) {b;e} ; ж) {a;b;c;d; f } ;

з) {b} ; и) U .

1.9а) {1;3;5;7;9} ; б) {6;7;8;9;10} ; в) {2;4;5;6;7;8;9;10} ; г) {4;5} ; д) {1;3;5} ;

е) {5;7;9} ; ж) {1;2;3;6;7;8;9;10} ; з) {2;5;7;9} ; и) {1;2;3;4;5;7;9};

к)

2;4;7;9 ;

{

}

л) {6;7}.

1.10 а)

(

−∞;0

)

(

5;

) ;

б)

(

−∞;−2

]

[

3;

) ;

в) [2;5] ;

г)

(

2;7) ;

(

+∞

(

)

+∞

)

[

)

−

д)

−2;0

)

; е)

(

5;7

)

; ж)

−2;2

[

3;7

)

; з)

(

) (

5;

; и)

0; 2

.

−∞;3

+∞

1.12а) I AÇB (x) = (0100)T ; б) I ( A\C ) B =(11001110)T ;

в) I ( A C ) ( B∩C ) ( D A) =(1011101111011111)T ; г) I A B = (1110)T ; д) I ( A\C )\ B = (00000010)T ; е) I ( A C ) B =(10010110)T .

1.16а) P( ) = { } ; б) P({ }) = { ;{ }} ; в) P({x}) ={ ;{x}} ;

г) P ({x, y}) = { ;{ x} ;{ y} ;{x, y}} .

1.17а).

1.18в).

1.19а).

1.20а).

1.21б).

1.22б).

1.23г).

1.24г).

1.25г).

Глава II. Отношения и функции

2.10 а){(x, x);(x, y);(x, z);( y, x);( y, y);( y, z)} ; б)

б){(x, x);(x, y);( y, x);( y, y);(z, x);(z, y)} ;

в){(x, x);(x, y);( y, x);( y, y)} ;

(x, x, x);(x, y, x);(x, z, x);( y, x, x);( y, y, x);( y, z, x); г) (x, x, y);(x, y, y);(x, z, y);( y, x, y);( y, y, y);( y, z, y) .

119

	0	1	1	1			1	1			1	0	1	0	1			0	1	1	1	1	1	1
													0 1					0	0	1	1	1	1	1
	0	0	1	1		1		1		0 1					0
							1	0			1	0	1	0	1			0	0	0	1	1	1	1
2.12 а)	0	0	0	1		; б)				; в)							; г)	0	0	0	0	1	1	1	.
							1	1			0	1	0	1	0		0 0 0 0 0 1 1
0		0	0	0														0	0	0	0	0	0	1
						0		0		1		0	1	0	1			0	0	0	0	0	0	0

2.13а) Dom(R)= {1;2;3;4}, Im(R)= {1;2;3;4},

R ={(1;2),(1;3),(1;4),(2;3),(2;4),(3;4)},

R−1 ={(1;1),(2;1),(2;2),(3;1),(3;2),(3;3),(4;1),(4;2),(4;3),(4;4)};

б) Dom(R)= {x | x [0;2]}, Im(R)={y | y [−1;1]},
				={(x, y) | x [0,3], y [−1, 2], x2 +4 y2 > 4},
	R
R−1 ={(x, y) | x [−1;2], y [0;3],4x2 + y2 ≤4};
в) Dom(R)= {x | x [0;1]}, Im(R)={y | y [0;1]},
				={(x, y) | x Î[0,1], y Î[0, 4], x3 ¹ y} ,												R−1 ={(x, y) | x Î[0, 4], y Î[0,1], y = 3						};
		R																			x
г) Dom(R)= { ,{x},{y},{x; y}}, Im(R)= { ,{x},{y},{x; y}},
				=		{		(a;b) | b a, a,b P({x; y}) , R								−1 =	{	(a;b) | b a, a,b P({x; y})		;.
		R
															}				}
				1				0	0	0	0	0	0	0
				1				1	0	0	0	0	0	0
				1 1 1 0 0 0 0 0
2.14 а) 1								1	1	1	0	0	0	0	; б) Dom(R)={1;2;3;4;5;6;7;8};
				1				1	1	1	1	0	0	0
				1				1	1	1	1	1	0	0
				1 1 1 1 1 1 1 0
				1 1 1 1 1 1 1 1
в) Im(R)={1;2;3;4;5;6;7;8}; г) R(2) ={1;2}, R(5) ={1;2;3;4;5};
д) R ({2,5}) ={1;2;3;4;5}, R ({2,3}) ={1;2;3};
е) R−1 (2) = {2;3;4;5;6;7;8}, R−1 (5) = {5;6;7;8} ;
ж) R−1 ({2,5}) = {2;3;4;5;6;7;8} , R−1 ({2,3,5}) ={2;3;4;5;6;7;8};
з)							={(x; y) | x < y,							x, y M } , R−1 = {(x; y) | x £ y,					x, y Î M } .
					R

2.15б) рефлексивно, антисимметрично, транзитивно;

в) антирефлексивно, транзитивно;

г) антирефлексивно, симметрично;

д) антирефлексивно, антисимметрично;

е) рефлексивно, симметрично, транзитивно;

ж) рефлексивно, симметрично, транзитивно.

120