Сборник задач по дискретке

5) Человек заходит в бар. Садится за столик, но не спешит делать заказ. Бармен подходит к нему и спрашивает:

–Что бы вы хотели выпить?

–Ничего. Я один раз попробовал спиртное – мне не понравилось. Вежливый бармен предлагает ему сигару.

–Спасибо, я не курю. Попробовал, но мне это не доставило удоволь-

ствия.

–Может, вы присоединитесь к играющим в карты джентльменам за соседним столиком? – не сдается бармен.

–Нет уж, увольте. Я не играю в карты. Однажды попробовал, но игра меня не увлекла. И вообще, если бы не обстоятельства, я бы не пошел

вбар. Но мы договорились встретиться здесь с сыном.

–Если я хоть что-то понимаю в жизни, это – ваш единственный ребенок, – с уверенностью предположил бармен.

39.Найти ошибку в доказательстве того, что все пирожки с мясом.

Для доказательства утверждения покажем, используя метод матема- тической индукции, что любые n пирожков с мясом. База индукции: n =1, испечем один пирожок с мясом. Для n = k предположим, что любые k пирожков с мясом. Испечем еще один пирожок с мясом. Получим k +1 пирожков с мясом. Таким образом, по индукции – все пирожки с мясом.

40.Найти ошибку в доказательстве того, что все лошади имеют одну

иту же масть.

Для доказательства утверждения покажем, что любые n лошадей имеют одну и ту же масть. При n =1 имеется одна лошадь, которая, есте- ственно, имеет такую же масть, как она сама. Для n = k предположим, что любые k лошадей имеют одинаковую масть. Предположим, что в загон помещены k +1 лошадь. Выведем из загона одну лошадь. Теперь в загоне k лошадей, поэтому они имеют одну и ту же масть. Вернем выведенную лошадь в загон и выведем другую лошадь. Опять в загоне k лошадей, поэтому все они имеют одну масть. Итак, все лошади имеют ту же масть, что и те лошади, которые были выведены. Поэтому все k +1 лошадь имеют одну и ту же масть. Таким образом, все лошади имеют од- ну и ту же масть.

61

41.Найти ошибку в рассуждениях.

1)Докажем, что если a = b + c , то a = b .

a = b + c Þ (a - b)a = (a - b)(b + c) Þ

Þ aa − ab = ab − bb + ac − bc Þ Þ aa − ab − ac = ab − bb − bc Þ

Þ a(a - b - c) = b(a - b - c) Þ a = b .

2) Докажем, что 1

> 1 .

4

2

sin π

= sin π

Þ lgsin π

= lgsin π

Þ 2lgsin

π

> lgsin π

Þ

6

6

6

p

6

pù

6

6

é

= lgsin

2

Þ ê2lgsin

6

ú Þ

ë

6 û

Þ lgsin2 π > lgsin

π

Þ sin2 π

> sin

π

Þ

1 >

1 .

6

6

6

6

4

2

3) Докажем, что 22 = 42 .

(

)

3

cos2 x = 1- sin2 x

Þ cos3 x =

1- sin2

x

Þ

2

2

æ

3

ö

2

Þ (cos3 x + 3)

= ç(1- sin2 x)

+ 3÷ .

2

è

ø

При x = π , получим требуемое равенство.

4) Докажем, что если 0o < a < 180o , то sin(a + 360o ) < sin a.

Пусть x = α2 , тогда 0o < x < 90o . Следовательно,

(		)		(			)
sin 180o + x				< sin x , cos 180o + x				< cos x .
Перемножив эти неравенства почленно, получим
(			)	(	)
sin 180o + x				cos 180o + x		< sin x cos x Þ
Þ 21 sin(360o	+ 2x)			< 12 sin(2x)	Þ sin(a + 360o )< sin a.

ОТВЕТЫ И РЕШЕНИЯ

Системы счисления

6. В 7-ричной.

8. а), в) – числа равны; б), г), д) – первое больше.

9. 30, 29, 511, 153, 1661, 1989.

10. 49 = 12113 = 1445 = 1007,	57 = 20103 = 2125 = 1117,
101 = 102023 = 4015 = 2037,	196 = 210213 = 12415 = 4007.

11. 1100010112 = 120234 = 6138 = 18B16, 10101001002 = 222104 = 12448 = 2A816, 1100000102 = 120024 = 6028 = 18216, 100110012 = 21214 = 2318 = 9916.

12. 1010100012, 1100011012, 1000000112, 10101012. 13. A3516 = 1010001101012 = 2203114 = 50658,

D2716 = 1101001001112 = 3102134 = 64478,

F4916 = 1111010010012 = 2210214 = 75118,

E8B516 = 11101000101101012 = 322023114 = 1642658, С60116 = 11000110000000012 = 301200014 = 1430018, 123B16 = 10010001111112 = 10203334 = 110778.

E457116 = 11 01 01 00 01 01 01 11 00 012 = 31101112014 = 32425618. 14. d n−1 (d −1) .

15. а) 1001,12 , б) 110001,012 , в) 1111012 , г) 1000,112 , д) 10001,00012 , е) 1,000012 .

Теория множеств

6. 1) Ì, ¹; 2) ¹; 3) Ì, ¹; 4) = , Ì, É ; 5) ¹; 6) Î, ¹; 7) ¹; 8) = , Ì, É ; 9) ¹; 10) Ì, ¹; 11) Î, Ì, ¹; 12) Ì, ¹.

7. Только 4.

9. A I A = , A U A = U, A \ A = A. 11. A I B = A, A U B = B .

12. Нет.

63

I

II

III

IV

V

14.

2) ( A I B IC) \ (C \ ( A U B)),

10) C U(( AIC) \ B)U((B IC) \ A), 13) (AU B UC)\ (C \ ( AU B));

3) ((A U B UC) \ (C I(A U B)))U(A I B IC),

6)(C ÷ ( A U B))U( A I B IC );

4)((B UC ) \ (C I B))\ ( A I B),

5)(B ÷C) \ ( AI B);

1) ((B \ C)U(C \ ( AI B)))U(A I B),

8)((B ÷ C ) \ ( A IC ))U( A I B IC ),

11)((B \ C)U(C \ ( A I B)))U( A I B IC);

7)((B UC )I A)U(C ÷ B),

9) ((B UC ) \ (B IC))U(A I(C U B)), 12) (A I(B UC))U(B ÷ C).

19. P({x}) = {,{x}},

P({x}) = {,{1},{2},{1,2}},

P({x}) = {,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}},

P({x}) = { },

P({x}) = { ,{ }},

P({x}) = {,{ },{{ }},{ ,{ }}}.

64

21. а) A× B = {(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)},
				б) B ×								A =		{(				)			(		a,2			)			,		(	a,3			)	,	(	)				(	b,2					)		,		(			b,3					)}	,
														{(		a,1 ,																			(			b,1 ,																									)	(		)		(				)}
				в)					A× A =								)		,	(		1,2			)	,		(			1,3		)	,				)		(	2,2			)		,			(		2,3							)	,	(							,							,
															1,1																					2,1 ,																								3,1 ,					3,2				3,3
				г) B × B = {(a,a),(a,b),(b,a),(b,b)},
				д), е) A× = × A = .
24. 1, 2, 4.																																																															2)
28.													1)
			P						1			2	3			4				5				6																							P							1 2 3 4 5 6
			1						1			0		1			0				1				0																						1							0						0			0		0		0			0
2									1			0		0			1				0				0																					2								0						1			0		1		0			1
3									1			0		0			0				1				0																					3								0						0			1		0		0			1
4									1			0		0			0				0				1																					4								0						0			0		1		0			0
5									1			0		0			0				0				0																					5								0						0			0		0		1			0
6									1			0		0			0				0				0																					6								0						0			0		0		0			1
							1 2 3 4 5 6																																																1					2		3			4	5			6
				P																																													P
		1						0				1		0			1				0				1																							1							1					1			1		1		1			1
2								0				1		1			0				1				1																							2							1					0			1		0		1			0
3								0				1		1			1				0				1																							3							1					1			0		1		1			0
4								0				1		1			1				1				0																							4							1					1			1		0		1			1
5								0				1		1			1				1				1																							5							1					1			1		1		0			1
6								0				1		1			1				1				1																							6							1					1			1		1		1			0
	P−1										1 2 3 4									5 6																									P−1												1			2 3 4 5 6
	1										1	1		1			1						1			1																				1											0				0		0		0			0		0
2											0	0		0			0						0			0																				2											0				1		0		0			0		0
3											1	0		0			0						0			0																						3									0				0		1		0			0		0
4											0	1		0			0						0			0																				4											0				1		0		1			0		0
5											1	0		1			0						0			0																				5											0				0		0		0			1		0
6											0	0		0			1						0			0																				6											0				1		1		0			0		1
																																						65

29.

1) P					1 3 5 7 P−1													1 3 5 7												2) P, P−1											1 3 5 7
		1				0			1		0	0			1			0	0				0		0										1						1	0	1			0
	3					0			0		1	0		3				1	0				0		0					3											0	1	0			1
	5					0			0		0	1		5				0	1				0		0					5											1	0	1			0
	7					0			0		0	0		7				0	0				1		0					7											0	1	0			1
3) P,P−1										1 3 5 7								4) P						1 3 5 7 P−1																1 3 5 7
																						1		1	1				0	0
			1							1	1	1		1																							1			1		1	1			0
	3									1	1	1		0					3					1	0				0	0							3			1		0	0			0
	5									1	1	0		0					5					1	0				0	0							5			0		0	0			0
30.	7									1	0	0		0					7					0	0				0	0							7			0		0	0			0
1)			P							{a} {b} {a,b}													2)					P					{a} {b} {a,b}
									0			1		1			1														1						1			1			1
	{ }								0			0		0			1								{ }						0						1			0			1
			a																									a
	{ }								0			0		0			1								{ }						0						0			1			1
			b			}																						b	}
	{						0					0		0			0								{						0						0			0			1
			a,b																								a,b
3)			P							{a} {b} {a,b}													4)					P					{a} {b} {a,b}
									0			0		0			0																0				0			0			1
	{ }								0			1		0			1								{ }								0				0			1			0
			a																									a
	{ }								0			0		1			1								{ }								0				1			0			0
			b			}																						b	}
	{							0				1		1			1								{								1				0			0			0
			a,b																									a,b
31.											2) P oS = {(1,10), (4,10), (4,11), (5,10), (5,11), (2,13)},
1) S o P = ,
3) T oS = ,											4) S oT = {(6,											), (6,W), (7,W), (8,*), (8,d)},
5), 6) (P o S )oT = P o(S oT ) = {(4,W), (5,W), (4,																																					), (5,					), (2,*), (2,W)},
7) S o S−1 = {(6,6), (7,7), (8,8)},																								8) S−1 o S = {(10,10), (11,11), (13,13)},

9), 10) (P o S )−1 = S−1o P−1 = {(10,1), (10,4), (11,4), (10,5), (11,5), (13,2)},

11) P−1 oS−1 = .

66

34. 1)

P oS = {(x, y)

y = ex + 2 },

S o P = {(x, y)

y = ex+2 };

2)

P oS = {(x, y)

y < ex + 2 },

S o P = {(x, y)

y < ex+2 };

3)

P oS = {(x, y)

y < ex + 2 },

S o P = {(x, y)

y < ex+2 };

4) P oS = S o P = ¡2 .

ù é

−1

35. 1)

P([2,10)) = [17,10001), P

([2,10)) = (− 3,

−1û U ë1, 3),

S([2,10)) = [16,2000), S−1 ([2,10)) = éë1, 35),

2)P([2,10)) = [17,+¥), P−1 ([2,10)) = (-3,3,),

S([2,10)) = (−∞,2000), S−1 ([2,10)) = [1,+∞) .

36. 1) δP = {1,2,3,5} , ρP = B = {{1},{1,2},{2,5},{3} }, 2) δP = A = ¢× (¢ \ {0}), ρP = B = ¤,

3) dP = ¢ \ {0} , rP = {y y =1 / x для некоторого x ΢ \ {0}},

4)δP = A = ¢, ρP = {y y = 2x длянекоторого x ¢},

5)δP = (1,10), ρP = [0,4.5).

37. P1 o P1 = {(x, y)

x = y4},

P1 o P2 = {(x, y)

y £5+

},

x

P1 o P3 = {(x, y)

x3 = y2},

P1 o P4

= {(x, y)

y = sin(±

)},

x

P2 o P1 = {(x, y)

x + y2 £5},

P2 o P2 = ¡2 ,

P2 o P3 = {(x, y)

x + 3

£5},

P2

o P4

= {(x, y)

y Î[-1,1]},

y

P3 o P1 = {(x, y)

x3 = y2},

P3 o P2 = {(x, y)

x3 + y ≤5},

P3 o P3

= {(x, y)

x9 = y},

P3 o P4

= {(x, y)

y = sin(x3 )},

P4 o P1

= {(x, y)

sin x = y2},

P4

o P2

= {(x, y)

sin x + y £5},

P3 o P3

= {(x, y)

sin x = 3

},

P4

o P4

= {(x, y)

y = sinsin x }.

y

67

38. δP = ρP = ¥,

P−1 = {( x, y)

x, y ¥ и y делит x},

P−1 o P = P o P−1 = ¥2 , P o P = P ,

1) P( A) = ¥, P−1 (B) = A = {x

x ¥ и x ≤ 10},

(

)

=

{

}

2) P

A

y

y делится хотя бы на одно из чисел 2, 3, 5 или 7

,

P−1

(

)

=

A =

{

}

B

x

x кратно 5 .

44. В таблице отмечены знаком «+» свойства, которыми обладает

данное отношение

Свойство

1

2

3

4

5

6

а

б

а

б

в

а

б

в

а

б

в

г

а

б

в

г

д

е

ж

а

б

в

г

Рефлексивность

+

+

+

+

+

+

+

+

+

+

Иррефлексивность

+

+

+

+

+

+

+

+

+

Симметричность

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

Антисимметричность

+

+

+

+

+

Транзитивность

+

+

+

+

+

+

+

+

+

+

+

+

+

Эквивалентность

+

+

+

+

+

+

+

Строгий порядок

+

+

Нестрогий порядок

+

+

+

Свойство

7

8

9

а

б

в

г

д

е

ж

з

а

б

в

г

д

е

ж

з

а

б

в

Рефлексивность

+

+

+

+

+

+

+

Иррефлексивность

+

+

+

+

+

+

+

Симметричность

+

+

+

+

+

+

+

+

+

Антисимметричность

+

+

+

+

+

+

Транзитивность

+

+

+

+

+

+

+

+

+

Эквивалентность

+

+

Строгий порядок

+

+

+

Нестрогий порядок

+

45. P1 – рефлексивно, симметрично, транзитивно; P2 – симметрично; P3 – иррефлексивно; P4 – симметрично, транзитивно.

68

46. S2 – рефлексивно; P2 – симметрично, иррефлексивно;

S1 o S2 – транзитивно; P1 o P2 – рефлексивно, транзитивно.

Для отношения S1 , P1 , S2 oS1 , P2 o P1 не выполняются все свойства.

S1 o S2		a b c d S2 oS1							a b c d P1 o P2							a b c d P2 o P1							a b c d
a		0	1	0	1		a		1	1	0	0		a		1	1	1	1		a		1	0	1	0
b		0	1	0	1		b		0	1	0	1		b		1	1	0	1		b		1	0	1	1
c		1	1	1	1		c		1	1	0	0		c		1	1	1	1		c		1	0	1	1
d		0	1	0	1		d		0	1	0	1		d		1	1	0	1		d		1	0	1	1

47. 1) а) Q = P U{(2,2),(3,3),(4,4),(5,5)}},

б) Q = P U{(2,1), (4,2), (5,3)},

в) Q = P U{(1,3), (1,4), (1,5), (2,2), (2,5),(3,3), (3,4)}, г) Q = P U{(2,2),(3,3),(4,4),(5,5),(2,1), (4,2), (5,3)}, д) Q = X 2 ;

2) а) Q = {(1,1), (2,3), (3,2)},

б) Q = {(1,1), (1,2), (3,5), (3,2)},

в) Q = {(1,1), (1,2), (2,3), (2,4), (3,5)}

или Q = {(1,1), (1,2), (2,4), (3,5), (3,2)}, г) Q = {(1,1)}, д) Q = {(1,1), (1,2), (3,5), (3,2)}.

54. 1) а) {1},{2}, {3}, б) {1, 2, 3};

2)а) {1,3,6}, {5,8}, {2}, {4}, {7}, б) {1,7}, {2,3,5}, {4}, {6}, {8} ;

3){-2,-1}, {4,5,6}.

55. 1

= 1,-1 ,

[

2

]

=

{

-2,2 ,

[

0

]

=

0 ,

é

-

1

ù

=

ì-

1

,

1

ü

,

[

4

]

=

4 .

ê

ú

ý

[ ]

{

}

}

{ }

2

í

2

2

{ }

ë

û

î

þ

59. 1)

f (X ) = {16}, f −1 ( X ) = {2,-2};

2)f (X ) = (16,81], f −1 (X ) = [-3,-2) U(2,3];

3)f (X ) = [0,81], f −1 ( X ) = [-3,3].

60. (-32,49]. 61. (-3,0)U(2,+¥). 69

64.	Если f		– иньекция.
68. Пусть		f	– не инъекция. Тогда существуют a,bδ f такие, что
			a ¹ b и f (a) = f (b) .
Положим A = {a}, B = {b} . Обратное очевидно.
73. Пусть		f	– некоторая функция, δ f и ρ f – ее область определения

и область значений соответственно. Тогда любая функция g : ρ f → σ f такая, что g (b) f −1 ({b}) для bρ f , есть инъекция.

75. Следует из задачи 74.4, так как A = B U( A \ B).

76. Мощность множества X не превышает мощность множества P( X ), так как «одноэлементные» подмножества из X образуют в P( X )

часть, эквивалентную множеству X .

Остается доказать, что мощности множеств X и P( X ) не совпадают. Действительно, пусть между X и P( X ) установлена биекция

a ↔ A , b ↔ B , …, t ↔ T ,… , где a,b,...,t,... X ; A, B,...,T,... P( X ).

Рассмотрим множество M = {t t X ,t T}, т.е. множество элементов X , не принадлежащих соответствующим им элементам P(X ). Так как M X , то M P( X ), а значит, ему в соответствие поставлен некоторый

элемент m X .

Согласно характеристике множества M , если:

1)m M , то его не надо включать в M , т.е. m M ;

2)m M , то его надо включать в M , т.е. m M .

Полученное противоречие показывает, что предположение об экви- валентности множеств X и P(X ) неверно.

77. Пусть M0 – бесконечное множество, значит,	M0 ¹ Æ .
Выбрав в M0 некоторый элемент a1 Î M0 и	удалив его из M0 ,
получим непустое (см. 75) множество M1 = M0 \{a1}.
70