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

31. Определить отношения:

1) S o P , 2) P oS , 3) T oS , 4) S oT , 5) (P o S ) oT , 6) P o(S oT ) , 7) S−1 oS 8) S o S−1 , 9) (P o S )−1 , 10) S−1 o P−1 , 11) P−1 o S−1 ,

если

T = {(11, ), (10,W), (13,*), (12,W), (13,d)}, P = {(1,7), (4,6), (5,6), (2,8)},

S= {(6,10), (6,11), (7,10), (8,13)}.

32.Определить P oS, (P oS )−1 , если:

1)X – множество точек плоскости, Y – множество окружностей,

Z – множество треугольников,

P = {(x, y)				x X , y Y и x − центр окружности y},
S = {(x, y)				x Y , y Z и окружность x вписана в треугольник y};

2)X – множество преподавателей института, Y – множество читаемых дисциплин,

Z – множество академических групп,

P ={(x, y) x X , y Y и преподаватель x ведет занятия по дисциплине y},

S ={(x, y) x Y , y Z и студенты группы y изучают дисциплину x};

3)X – множество мужчин, Y – множество людей, Z – множество женщин,

P = {(x, y) x X , y Y и x − отец y},

S = {(x, y) x Y , y Z и x − родитель y}.

33.Пусть L – множество людей, P L2 , S L2 ,

P = {(x, y)		x − дочь y},	S = {(x, y)		x − отец y}.
Определить следующие отношения:
1) P2 ;		2) S2 ;	3) P oS ;			4) S o P ;
5) S−1 o S−1 ;		6) P−1 o P−1 ;	7) S−1 o P−1 ;			8) P−1 o S−1 ;
9) S o P−1 ;		10) P−1 o S ;	11) P oS−1 ;			12) S−1 o P .

11

34. Определить отношения P oS , S o P , если P Ì ¡2 , S Ì ¡2 и:

1)	P = {(x, y)		y = ex }, S = {(x, y)		y = x + 2};
2) P = {(x, y)			y < ex }, S = {(x, y)		y = x + 2};
3)	P = {(x, y)		y < ex }, S = {(x, y)		y < x + 2};
4)	P = {(x, y)		y < ex }, S = {(x, y)		y > x + 2}.

35. Найти образ и прообраз множества [2,10) относительно отношений P и S , если P Ì ¡2 , S Ì ¡2 и:

1) P = {(x, y) y = x4 +1}, S = {(x, y) y =2x3};

2)P = {(x, y) y > x4 +1}, S = {(x, y) y £ 2x3}.

36.Найти область определения и область значений бинарного отноше- ния P , если P A× B :

1) A = {1, 2, 3, 4, 5}, B = {{1}, {1,2}, {2,5}, {3}}, P = {(x, y) x Î y};

	ì				a ü
2)	A = ¢× ¢, B = ¤, P = í((a,b),c)			c =		ý	;
	î				b þ
3)	A = ¢, B = ¤, P = {(x, y)		xy = 1};
4)	A = ¢, B = ¤, P = {(x, y)		y = 2x };

5) A = B = [0,10], P = {(x, y)

x > 2 y +1}.

37.

Найти все возможные композиции Pi o Pk , i,k =

, если i Pi ¡2 и

1,4

P1 = {(x, y)

x = y2},

P2

= {(x, y)

x + y £ 5},

P3 = {(x, y)

x3 = y},

P4

= {(x, y)

y = sin x}.

38.

Найти δP , ρP , P−1 , P−1 o P , P o P−1 , P o P , P(A), P−1 (B), если

P= {(x, y) x, y ¥ и x делит y}, P ¥2 :

1)A = {x x £ 7}, B = {x 5 £ x £10};

2)A = {x 1 < x £ 7}, B = {x x кратно 5}.

12

39.Для бинарного отношения P Ì ¡2 найти:

δP , ρP , P−1 , P−1oP , P o P−1 , P o P , P([-5,-1)), P−1 ((2,10]).

1)P = {(x, y

2)P = {(x, y

3)P = {(x, y

4)P = {(x, y

5)P = {(x, y

6)P = {(x, y

7)P = {(x, y

8)P = {(x, y

9)P = {(x, y

10)P = {(x, y

11)P = {(x, y

12)P = {(x, y

)

)

)

)

)

)

)

)

)

)

)

)

x + y £ 0}. x + y > 0}. x + y ³ 2}. x + y < 7}. x - y < 0}. x - y ³ 0}. x - y £ 9}. x - y > 3}. xy < -5}. xy > -5}. xy < 20}. xy > 20}.

13)P = {(x, y)

14)P = {(x, y)

15)P = {(x, y)

16)P = {(x, y)

17)P = {(x, y)

18)P = {(x, y)

19)P = {(x, y)

20)P = {(x, y)

21)P = {(x, y)

22)P = {(x, y)

23)P = {(x, y)

24)P = {(x, y)

3x - 5y < 0}.

7x - 4 y ³ 0}.

2x - 3y > 5}.

9x - 5y £ 2}.

2x + 5y ³ 0}.

7x + 3y < 2}. x2 - y < 0}. x2 - y > 0}. x2 + y < 0}. x2 + y > 0}. x3 > y2}.

x2 > y + 2}.

40.Для бинарного отношения P Ì ¡2 найти:

δP , ρP , P−1 , P−1oP , P o P−1 , P o P , P((-2,5]), P−1 ([1,7)).

1)P = {(x, y)

2)P = {(x, y)

3)P = {(x, y)

4)P = {(x, y)

x						< y}.	5)	P = {(x, y
x						> y}.	6)	P = {(x, y
y						£ x}.	7)	P = {(x, y
y						³ x}.	8)	P = {(x, y

)

)

)

)

ln x < y}.	9) P = {(x, y
ln x > y}.	10)	P = {(x, y
ln x £ y}.	11)	P = {(x, y
ln x ³ y}.	12)	P = {(x, y

)

)

)

)

ex < y}. ex > y}. ex £ y}. ex ³ y}.

ì		é	-	p	,
41. Для бинарного отношения P = í(x, y)		x, yÎê		2
î		ë

δP , ρP , P−1	, P−1oP , P o P−1	ææ	0,	pùö	,
		, P o P , Pçç		ú÷
		èè		2 ûø

pùú и sin 2 û

P−1 æçèæçè0,

x £ yü найти:

ý

þ

pùö.

ú÷

2 ûø

13

42.	Доказать, что если P1 P2 , то:
1) Q o P1 Q o P2 ;		2) P1 oQ P2 oQ ;	3) P−1	Ì P−1 .
			1	2
43.	Доказать, что для любых бинарных отношений:

1)(P1 I P2 )−1 = P1−1 I P2−1 ;

2)P−1 = (P)−1 ;

3)P1 o(P2 o P3 ) = (P1 o P2 )o P3 ;

4)(P1 o P2 )−1 = P2−1 o P1−1 ;

5)P1 o(P2 U P3 ) = (P1 o P2 )U(P1 o P3 );

6)(P1 U P2 )o P3 = (P1 o P3 )U(P2 o P3 );

7)P1 o(P2 I P3 ) Ì (P1 o P2 ) I(P1 o P3 );

8)(P1 I P2 )o P3 Ì (P1 o P3 )I(P2 o P3 ).

44. Определить, является ли отношение P Ì A2 рефлексивным, иррефлексивным, симметричным, антисимметричным, транзитивным, отношением строгого порядка, нестрогого порядка, эквивалентности.

1)	A – множество геометрических фигур:
	а) P = {(x, y)				фигура x конгруэнтна фигуре y},
	б) P = {(x, y)				фигура x имеет площадь меньше, чем фигура y};
2)	A – множество прямых:
	а) P = {(x, y)				x параллельна y},
	б) P = {(x, y)				x перпендикулярна y},
	в) P = {(x, y)				x и y пересекаются};
3)	A – множество точек действительной плоскости ¡2 :
	а) P = {(x, y)				x и y равноудалены от начала координат},

б) P = {(x, y) x и y находятся на разном расстоянии от начала координат},

в) P = {(x, y)						x и y равноудалены от оси ординат};
4) A = {1, 2, 3, 4, 5, 6, 7, 8, 9}:
а) P = {(x, y)						x − y четно},
б) P = {(x, y)						x + y четно},
в) P = {(x, y)						(x +1) − делитель (x + y)},
г) P = {(x, y)						x ¹1 и x - делитель (x + y)};

14

5)

A = ¥:

а) P = {(x, y)

x + y четно},

д) P = {(x, y)

(xy) M2},

б) P = {(x, y)

x + y нечетно},

е) P = {(x, y)

(x + y) M7},

в) P = {(x, y)

x кратно y},

ж) P = {(x, y)

x - y

M7};

г) P = {(x, y)

НОД(x, y) ¹ 1},

6)

A = P(M ), M = {a,b,c}:

а) P = {(X ,Y )

X Ì Y , X ¹ Y},

в) P = {(X ,Y )

X IY ¹ Æ},

б) P = {( X ,Y )

X Ì Y },

г) P = {( X ,Y )

X = A \ Y};

7)

A – множество людей:

а) P = {(x, y)

x моложе y},

г) P = {(x, y)

x − сестра y},

б) P = {(x, y)

x знаком с y},

д) P = {(x, y)

x − отец y},

в) P = {(x, y)

x похож на y},

е) P = {(x, y)

x - начальник y},

ж) P = {(x, y)

x состоит в браке с y},

з) P = {(x, y)

x живет в одном городе с y};

8)

A = ¡:

а) P = {(x, y)

x < y},

д) P = {(x, y)

x +1 = y},

б) P = {(x, y)

x ³ y},

е) P = {(x, y)

x2 + y2 = 4},

в) P = {(x, y)

y

<

x

},

ж) P = {(x, y)

x2 + y2 < 4},

г) P = {(x, y)

x = y},

з) P = {(x, y)

x2 − y2 = 0};

9)

A = ¢2 :

а) P = {((x, y),(u,v))

xv = yu},

б) P = {((x, y),(u,v))

x + u = y + v},

в) P = {((x, y),(u,v))

x + v = y + u}.

15

45. Какими свойствами обладают следующие отношения?
	P1		a b c				P2		a b c				P3		a b c				P4		a b c
	a		1	0	1		a		1	0	1		a		0	1	0		a		1	0	1
	b		0	1	0		b		0	1	0		b		1	0	0		b		0	0	0
	c		1	0	1		c		1	0	0		c		0	1	0		c		1	0	1

46. Построить						отношения						S1 o S2 , S2 oS1 ,							P1 o P2 ,			P2 o P1 .				Определить
свойства исходных и полученных отношений.
	S1		a b c d						S2		a b c d P1							a b c d					P2		a b c d
	a		0	1	0		0		a		1 0		1	0		a		1 0 1 1					a		0 1		0	1
	b		0	1		0	1		b		0	1	0	1		b		0	0	1	0		b		1	0	1	0
	c		1	1		0	0		c		0	0	1	0		c		0	0	1	1		c		1	1	0	1
	d		0	1		0	1		d		0	1	0	1		d		1	0	1	0		d		1	0	1	0

47. Пусть

X =

{

}

P =

{( ) (

)

,

(

2,3

)

,

(

2,4

)

,

(

3,5

)

,

(

3,2

)}

.

1, 2, 3, 4, 5 ,

1,1 , 1,2

Построить:

1) наименьшее отношение Q X 2 , P Q , являющееся:

а) рефлексивным,

б) симметричным,

в) транзитивным,

г) симметричным и рефлексивным,

д) симметричным и транзитивным;

2) наибольшее отношение Q P , являющееся:

а) симметричным,

б) транзитивным,

в) антисимметричным,

г) симметричным и транзитивным,

д) антисимметричным и транзитивным.

48. Пусть

X

– множество

студентов вашей

группы.

Упорядочим

список студентов по алфавиту и определим бинарное отношение

P = {(x, y)

x из первой половины списка, y − из второй}

(для нечетного числа студентов студент из середины списка входит и в первую, и во вторую половину). Определить, какими свойствами обла- дает отношение P , и построить:

1) наименьшее отношение Q X 2 , P Q , являющееся:

а) симметричным, б) транзитивным, в) симметричным и транзитивным;

2) наибольшее отношение Q P , являющееся:

а) симметричным, б) транзитивным, в) антисимметричным, г) симметричным и транзитивным, д) антисимметричным и транзитивным.

16

49.Доказать истинность следующих утверждений.

1)Если P рефлексивно, то P−1 рефлексивно.

2)Если P иррефлексивно, то P−1 иррефлексивно.

3)Если P симметрично, то P−1 симметрично.

4)Если P симметрично, то P o P−1 симметрично.

5)Если P антисимметрично, то P−1 антисимметрично.

6)Если P транзитивно, то P−1 транзитивно.

7)Если P – отношение порядка, то P−1 – отношение порядка.

8)Если P – отношение эквивалентности, то P−1 – отношение эквива- лентности.

50.Доказать, что:

1)P антисимметрично тогда и только тогда, когда P o P−1 idA ;

2)P транзитивно тогда и только тогда, когда P o P P .

51.Доказать истинность следующих утверждений.

1)	Если P и S рефлексивны, то P I S рефлексивно.
2)	Если P и S рефлексивны, то P U S рефлексивно.
3)	Если P и S рефлексивны, то P oS рефлексивно.
4)	Если P и S иррефлексивны, то P I S иррефлексивно.
5)	Если P и S иррефлексивны, то P U S иррефлексивно.
6)	Если P и S симметричны, то P I S симметрично.
7)	Если P и S симметричны, то P U S симметрично.

8)Если P и S симметричны, то P \ S симметрично.

9)Если P и S симметричны, то P ÷ S симметрично.

10)Если P и S антисимметричны, то P I S антисимметрично.

11)Если P и S транзитивны, то P I S транзитивно.

12)Если P и S – отношения эквивалентности, то P I S – отношение эквивалентности.

52.Привести примеры бинарных отношений P и S , для которых следующие утверждения ложны.

1)	Если P и S симметричны, то P oS симметрично.
2)	Если P и S антисимметричны, то P U S антисимметрично.
3)	Если P и S антисимметричны, то P \ S антисимметрично.
4)	Если P и S антисимметричны, то P oS антисимметрично.
5)	Если P и S антисимметричны, то P ÷ S антисимметрично.
6)	Если P и S транзитивны, то P U S транзитивно.
7)	Если P и S транзитивны, то P \ S транзитивно.
8)	Если P и S транзитивны, то P oS транзитивно.
9)	Если P и S транзитивны, то P ÷ S транзитивно.

17

53. Построить бинарное отношение, обладающее следующими свой- ствами, или доказать, что такого не существует:

№			Свойства
п/п	рефлек-	иррефлек-	симмет-	антисим-	транзи-
	сивность	сивность	ричность	метричность	тивность
1	+	–	–	–	–
2	–	+	–	–	–
3	–	–	–	–	–
4	+	–	–	–	+
5	–	+	–	–	+
6	–	–	–	–	+
7	+	–	+	–	–
8	–	+	+	–	–
9	–	–	+	–	–
10	+	–	+	–	+
11	–	+	+	–	+
12	–	–	+	–	+
13	+	–	–	+	–
14	–	+	–	+	–
15	–	–	–	+	–
16	+	–	–	+	+
17	–	+	–	+	+
18	–	–	–	+	+
19	+	–	+	+	–
20	–	+	+	+	–
21	–	–	+	+	–
22	+	–	+	+	+
23	–	+	+	+	+
24	–	–	+	+	+

Например, в первом варианте требуется построить рефлексивное, но не иррефлексивное, не симметричное, не антисимметричное, не тран- зитивное бинарное отношение.

18

54.Построить все классы эквивалентности по отношению P Ì A2 , если:

1)A = {1, 2, 3} :

а) P =	{(		)	(				2,2		)		,		(	3,3		)}				,
		1,1 ,		(						)				(			)							)				(			)		(			)		(			)			(				)			(			)}
б) P =	{(		)					2,2				,			1,2				,			(							3,3			,		2,3			,		3,2			,			1,3				,						;
		1,1 ,																					2,1 ,																														3,1
2) A = {1, 2, 3, 4, 5, 6, 7, 8}:																		)				(			)				(			)		(			)		(				)			(				)			ï
	ï(		)	(					2,2		)		,	(		3,3				,				4,4				,		5,5			,		6,6			,		7,7				,			8,8
а) P =	ì	1,1 ,																																																		,ü		,
	í		(1,3), (3,6), (5,8), (1,6), (6,1), (8,5), (6,3), (																																												3,1)						ý
	ï																																																				ï
	î		)	(							)			(				)				(			)				(			)		(			)		(				)			(					)		þ
	ï(								2,2				,			3,3				,				4,4				,		5,5			,		6,6			,		7,7				,			8,8						ï
б) P =	ì	1,1 ,																																																		,ü		;
	í	(1,7),							(2,3)					, (2,5), (3,5), (5,3), (5,2)																									, (3,2), (7,1)														ý
	ï																																																				ï
	î																																																				þ
3) A = {-2, -1, 4, 5, 6} , P = {(x, y)																											xy > 0};
4) A = ¥:
а) P = {(x, y)							x + y > 0},
б) P = {(x, y)								(x + y) - четное число},

в) P = {(x, y) x - y M5};

5)A = ¡ \ {0}, P = {(x, y) xy > 0};

6)A – множество компьютерных программ, написанных в НГТУ,

P = {(x, y) x и y написаны на одном языке программирования}.

55. Пусть P = {(x, y) x, y Î[-2,4] и x2=y2}. Доказать, что отношение P является отношением эквивалентности, и определить следующие классы

						[ ]			[			]		[		]			ê	ú			[		]
эквивалентности:							1 ,				2		,		0		,		é-	1ù		,		4		.
																				2û
					{											}			ë
																			. Определить отношение эквивалентности P ,
56. Пусть A= 1,2,3,4,5,6,7
разбивающее множество A следующим образом:																														} {				}}
1)	{{ }		{				}	{				}}		,												4)	{{								,
	1,7 ,			3,4,6 ,					2,5																		1,2,3,4 , 5,6,7
2)	{{							}}		,																5)	{{ }		{ }		{				}}		,
	1,2,3,4,5,6,7													{ }				{ }}									1,4	,	3,5 ,				6,2,7
3)	{{ }	{ }			{ }		{ }			{ }							,			,						6)	{{ }	,		{ }		{		}	,	{ }}		.
	1 ,	2		,	3 ,		4		,		5 ,			6					7								1,7			3,5 ,				2,4		6

19

57. Среди указанных отношений и обратных к ним найти функцио- нальные отношения. Для каждого функционального отношения:

а) указать область определения и область значений; б) определить, является ли оно инъекцией, сюръекцией, биекцией;

в) определить, является ли соответствующая функция всюду опреде- ленной или частично определенной.

1){(

2){(

3){(

4){(

5){(

6){(

7){(

8){(

9){(

10){(

11){(

12){(

13){(

14){(

x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y)

x, y ¡ x, y ¡ x, y ¡ x, y ¡+ x, y ¡+ x, y ¡+ x, y ¡ x, y ¡ x, y ¡ x, y ¡+ x, y ¡ x, y ¡ x, y ¡ x, y ¡

y = 5};

15) {(

x = 7};

16) {(

y = x

2

};

17)

{(

{(

y = x

2

};

18)

{(

y = x

2

+

4};

19)

{(

y = x2 − 9 ;

20)

}

y = x3};

21) {(

y = tg x};

22) {(

y = ln x};

23)

{(

y = ln x};

24)

{(

y =

}

;

x2

25)

{(

y = x +

};

x

26)

{(

y2 = x2 };

27)

{(

y = x[x]};

28)

{(

x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y) x, y)

x, y ¡ y = x (x −5)(x + 5)}; x, y ¡ y2 + x2 = 4};

x ¡, y ¡+ y2 + x2 = 4}; x ¡+ , y ¡ y2 + x2 = 4}; x, y ¡+ y2 + x2 = 4};

x, y ¡ y = 4 − x2 };

x ¡, y ¡+ y = 4 − x2 }; x ¡+ , y ¡ y = 4 − x2 }; x, y ¡+ y = 4 − x2 };

x, y ¡ y2 + x2 ≤ 4};

x, y ¡ y = cos(arcsin x)}; x, y [0;1] y = cos(arcsin x)}; x, y ¡ y = sin(arcsin x)}; x, y [0;1] y = sin(arcsin x)}.

58. Для функций f и g , заданных на множестве действительных чисел, найти f (g (x)) и g ( f (x)), если:

1) f (x) = x2 + 5, g (x) = x − 7 ;

2) f (x) = ln x , g (x) = x2 +1.

20