2Дискретка / Задачники / 1.Теория множеств(задачи)

2.ТЕОРИЯ МНОЖЕСТВ

1.Задать множества перечислением их элементов и найти B IC ,

A U B , ( A U B) IC , A I B IC A I B IC , если:

1)A – множество делителей числа 12; B = {1;5} ; C – множество

нечетных чисел x таких, что 2 < x <13;

2) A – множество четных чисел x таких, что 3 < x <10; B – множество делителей числа 21; C – множество простых чисел, меньших 12.

2. Изобразить на координатной прямой множества A U B , A I B

иA I B , если:

1)A = (−1,0] и B = [0,2), 2) A = (−∞,1] и B = (−∞,−3),

3) A = {x x ¡ и − 5 ≤ x < 2} и B = {x x ¡ и 1< x ≤ 4},

4) A = {x x Ρ и x < 5} и B = {x x Ρ и x ³ -7}.

3. Дать геометрическую интерпретацию множества A I B \ C , если

A = {(x, y) x, y Ρ и x £ 4, y £ 4};

B= {(x, y) x, y Ρ и x2 + y2 £ 25};

C= {(x, y) x, y ¡ и y > 0}.

4.Определить множества:

1){x x = 5y, y ΢} \{x x =10y, y ΢};

2){x x = 4n + 2,nΥ}I{x x = 3n,nΥ};

3){x x = 2y, y ¢}I{x x = 3y, y ¢};

4){x x = 2y, y ΢}U{x x = 3y, y ΢}.

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

	1) A A;	3) A I B A A U B ;
		4) A I B B	A U B ;
	2) если A B и B C , то A C ;
		5) A \ B A .
	4

6. Какой знак из множества											{							}	можно поставить вместо
												=, ¹, É, Ì
символа «?», чтобы полученное утверждение было верным.
1)	{1,3} ? {1,2,3} ,										5)		{(	)		(	3,2			)}	?	{(		)	,	(	2,3		)}			,
														2,1 ,								1,2
2)	{2,3,4}		? {1,2,3} ,								6)		{{ }		,	{				}}	?	{(		)		(		2,3		)}		,
3)			?				x делитель 6 ,							1,2				2,3					2,1 ,
	1,2,3				x								{{ }			{				}}		{{ }				{			}			{ }}
	{	}		{						}	7)				,						?												,
														1,2				2,3					2,1 ,					3,2			, 1,3
4)	{{ }		{		}}			?	{	}	8) ? { } .
	1,2	,	2,3						1,2,3 ,

7.Какие из утверждений верны для всех A , B и C ?

1)Если AÎ B и B ÎC , то AÎC ,

2)Если A Ì B и B ÎC , то AÎC ,

3)Если A I B C и A UC B , то A IC = ,

4)Если A ¹ B и B ¹ C , то A ¹ C ,

5)Если A (B UC) и B ( A UC), то B = .

8. Даны			два	произвольных	множества	A	и	B	такие,	что
A I B = . Определить множества A \ B и B \ A.
9. Даны			два	произвольных	множества	A	и	B	такие,	что
A I		= . Определить множества A I B и A U B .
	B

10.Дано произвольное множество A . Найти множества

A I A, A U A, A \ A.

11.Существуют ли такие множества A , B и C , что

A I B ¹ Æ , A IC = Æ , (A I B) \ C = Æ?

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

A B A U B = B A I B = A A \ B = A U B = U.

13. Опишите множества, соответствующие закрашенной части

диаграммы Венна:
1)	2)

5

3)

5)

14.Доказать, что

1)A \ (B UC) = ( A \ B) I( A \ C) ,

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

3)A \ ( A \ B) = A I B ,

4)A \ B = A \ ( A I B),

5)A I(B \ C) = ( A I B) \ ( A IC) ,

6)( A I B) \ ( A IC) = ( A I B) \ C ,

7)A I(B \ C) = ( A I B) \ C ,

8)( A \ B) \ C = ( A \ C) \ (B \ C),

9)A U B = A U(B \ A) ,

10)( A I B) U(A I B)= A,

11)( A U B)I(A U B)= A,

12)(A U B)I A = A I B ,

13)( A U B) \ C = (A \ C) U(B \ C),

14)A \ (B \ C) = (A \ B)U(A IC),

15)A \ (B UC) = (A \ B) \ C ,

16)A U B Ì C Û A Ì C и B Ì C ,

17)A Ì B IC Û A Ì B и A Ì C ,

4)

6)

18)A Ì B UC Û A I B Ì C ,

19)A Ì B Þ C \ B Ì C \ A,

20)A Ì B Þ B Ì A,

21)A U B = A I B Þ A = B ,

22)A= B Û AIB =Æ и AUB =U ,

23)A ¸ (B ¸ C) = (A ¸ B) ¸ C ,

24)A ¸ (A ¸ B) = B ,

25)A U B = A ¸ B ¸ ( A I B),

26)A U B = (A ¸ B) U( A I B),

27)A \ B = A ¸ ( A I B),

28)A ¸ B = Æ Û A = B ,

29)A I B = Æ Þ A U B = A ¸ B ,

30)A I B Ì С Û A Ì B UC

31)AU(BIC) = (AUB)I(AUC),

32)( A U B) I A = ( A I B) U A = A ,

33)A I(B \ A) = Æ,

34)(A I B) U(C I D) =

=( AUC) I(BUC)I(AUD)I(BUD)

.

6

15. Доказать следующие тождества:
1) UUAkt =UU Akt					,	5)	U(B I Ak	æ	ö	,
k K t T		t T k K						) = B Iç UAk ÷
2) IIAkt = II Akt					,		k K	è k K	ø
						6)		æ	ö	,
k K t T		t T k K					I(B U Ak ) = B Uç IAk ÷
3)		= I		,				è k K	ø
	U Ak
			Ak			7)	k K
k K		k K					U Ak U UBk = U(Ak U Bk ),
4)		= U		,
	I Ak
			Ak				k K k K	k K
k K		k K				8)	UIAkt Ì IU Akt .
							k K t T	t T k K

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

1)UAi есть наименьшее множество, содержащее все множества Ai ;

i I

2) IAi есть наибольшее множество, содержащееся во всех мно-

i I

жествах Ai .

17.Найти булеаны множеств {x}, {1,2}, {1,2,3} , , {Æ} , {Æ,{Æ}}.

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

1)P(A I B) = P(A)IP(B),

2) P(A U B) = {A1 U B1 A1 ÎP(A) и B1 ÎP(B)},

æ	ö	= IP(Ai ),
3) PçIAi ÷
è i I	ø		i I
æ	ö	=	ì		Bi ÎP(Ai			ü
4) PçUAi ÷			íUBi					)ý.
è i I	ø	{	îi I			{	}	þ
			}	, B =
19. Пусть A = 1,2,3							a,b . Определить множества
1) A× B , 2) B × A , 3)						A× A , 4) B × B , 5) A× , 6) × B .

20. Пусть A – множество точек отрезка [0,1]; B – множество точек отрезка [2,3]; C = {4,5,6}; D – множество точек квадрата с вершинами в точках (0,0), (0,1), (1,0), (1,1). Найти геометрическую интерпрета-

цию множеств:
1) A× B ,	3) C × B ,	5) C × D ,
2) A×C ,	4) A× D ,	6) D × B .

7

21.	Доказать, что существуют A ,			B и C такие, что:
1)		A´ B ¹ B ´ A ,	3)	A´(B ´C) = ( A´ B)´C ,
2)		A´ B = B ´ A,	4)	A´(B ´C) ¹ ( A´ B)´C .
22.	Доказать, что		( A´ B) U(C ´ D) Ì ( A UC)´(B U D). При каких

A , B , C , D включение можно заменить равенством?

23.Доказать, что для произвольных множеств A , B , C , D

1)( A U B)´C = ( A´C ) U(B ´C) ,

2)( A \ B)´C = ( A´C ) \ (B ´C),

3)A´(B \ C ) = ( A´ B) \ ( A´C),

4)( A I B)´(C I D) = ( A´C) I(B ´ D) ,

5)A´ B = ( A´ D) I(C ´ B), где A Ì C и B Ì D.

24. Пусть A ¹ Æ, B ¹ Æ и ( A´ B) U(B ´ A) = C ´ D . Доказать, что в этом случае A = B = C = D.

25.Задать отношение P перечислением его элементов или мат-

рицей отношения, если P Ì A2 , A = {1,2,3,4,5,6,7,8,9}

1)P = {(x, y) (x +1) делитель (x + y)};

2)P = {(x, y) x ¹1 и x делитель (x + y)}.

26.Задать отношение P Ì A2 , A = {1,3,5,7} перечислением его

элементов и определить			P	и P−1 , если
1) P = {(x, y)		x + 2 = y};			3) P = {(x, y)		x + y -1Î A};
2) P = {(x, y)		(x + y)/ 2Î A};			4) P = {(x, y)		2y + x Î A}.

27. Составить матрицы отношений P , P и P−1 , если P Ì (P( A))2 ,

A = {a,b,c} .

1)	P = {(X ,Y )		X Ì Y, X ¹ Y};	3)	P = {(X ,Y )		X IY ¹ Æ};
2)	P = {( X ,Y )		X Ì Y};	4)	P = {(X ,Y )		X =		}.
								Y

8

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

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

если 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)}.

29.Найти 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}.

30.Пусть отношения P и S определены на множестве людей следующим образом: P = {(x, y) x дочь y}, S = {(x, y) x отец y}. Опре-

делить следующие отношения:

1) P2 , 2) S2 , 3) P oS 4) S o P , 5) S−1 oS−1 , 6) P−1 o P−1 , 7) S o P−1 , 8) P−1 oS , 9) P−1 oS −1 , 10) S−1 o P .

31. Пусть	P = {(x, y)		x, y ¡ и y = x4 +1},	S = {(x, y)		x, y ¡ и y =7x3}.
Определить отношения P oS , S o P , P−1 ,				S−1 . Найти образ и прообраз
множества [2,10) относительно отношений P и S .
32. Пусть	P = {(x, y)		x, y ¡ и y > x4 +1},	S = {(x, y)		x, y ¡ и y ≤7x3} .

Найти P(X ), P−1 ( X ), S ( X ), S−1 (X ), где X = (2,10].

9

33. Пусть P = {(x, y) x, y ¥ и x делит y}. Найти δP , ρP , P−1 ,

P−1 o P , P o P−1 , P o P , P(A), P−1 (B), если

1) A = {x x ¥ и x ≤ 7}, B = {x x ¥ и 5 ≤ x ≤10};

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

34. Найти

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,

11)P = {(x,

12)P = {(x,

			δP , ρP , P−1 , P−1oP ,				P o P−1 ,
для отношений:
)			x, y Î ¡ и x + y £ 0},			13)	P = {(x, y)
)			x, y Î ¡ и x + y > 0},			14)	P = {(x, y)
)			x, y Î ¡ и x + y ³ 2},			15)	P = {(x, y)
)			x, y Î ¡ и x + y < 7},			16)	P = {(x, y)
)			x, y Î ¡ и x - y < 0},			17)	P = {(x, y)
)			x, y Î ¡ и x - y ³ 0},			18)	P = {(x, y)
)			x, y Î ¡ и x - y £ 9},			19)	P = {(x, y)
)			x, y Î ¡ и x - y > 3},			20)	P = {(x, y)
)			x, y Î ¡ и xy < -5},			21)	P = {(x, y)
y)					x, y Î ¡ и xy > -5},	22)	P = {(x, y)
y)					x, y Î ¡ и xy < 20},	23)	P = {(x, y)
y)					x, y Î ¡ и xy > 20},	24)	P = {(x, y)

P o P , P([−5,−1)),

x, y Î ¡ и 3x - 5y < 0} , x, y Ρ и 7x - 4y ³ 0}, x, y Î ¡ и 2x - 3y > 5}, x, y Î ¡ и 9x - 5y £ 2}, x, y Ρ и 2x + 5y ³ 0}, x, y Ρ и 7x + 3y < 2}, x, y Î ¡ и x2 - y < 0}, x, y Î ¡ и x2 - y > 0}, x, y Î ¡ и x2 + y < 0}, x, y Î ¡ и x2 + y > 0}, x, y Î ¡ и x3 > y2},

x, y Î ¡ и x2 > y + 2}.

35. Найти δP ,

ρP , P−1 , P−1 o P , P o P−1 , P o P , P(A), P−1 (B), если

1)

P = {(x, y)

x, y Î ¡+ и ln x < y}, A = B = (1,3];

2)

P = {(x, y)

x, y Î ¡ и ex > y},

A = B = (1,3];

3)

{(

)

}

(

]

,

[

)

;

P =

x, y

x, y Î ¡ и

x

< y ,

A =

-2,5

B = 1,7

4)

P = {(x, y)

x, y Î ¡ и

x

> y},

A = (-3,7

],

B = [2,9);

5) P = {(x, y)

x, y Î[-p/ 2,p/ 2] и sin x £ y} ,

A = B = (0,p / 2].

10

36. Доказать, что если P1 P2 , то
1) Q o P1 Q o P2 ,					2) P1 oQ P2 oQ ,	3) P−1	P−1.
						1	2
37. Доказать, что для любых бинарных отношений:
1) (P1 I P2 )−1 = P1−1 I P2−1 ,					5) P1 o(P2 U P3 ) = (P1 o P2 )U(P1 o P3 ),
		= (		)−1 ,
2)	P−1				6) (P1 U P2 )o P3 = (P1 o P3 )U(P2 o P3 ),
			P

3) P1 o(P2 o P3 ) = (P1 o P2 )o P3 , 7) P1 o(P2 I P3 ) (P1 o P2 )I(P1 o P3 ),
4) (P1 o P2 )−1 = P2−1 oP1−1 ,	8) (P1 I P2 )o P3 (P1 o P3 )I(P2 o P3 ).

38. Определить, какими свойствами обладает отношение 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 = {( в) P = {(

г) P = {(

x, y)				x − y четно}, б) P = {(x, y)						x + y четно},
x, y)						}	,
				(x +1) делитель (x + y)
							}
x, y	)			x ¹1 и x делитель	(	x + y	)	;

11

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 =

};

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)

x2 + y2 = 4},

б) P = {(x, y)

x ³ y},

ж) P = {(x, y)

x2 + y2 < 4},

в) P = {(x, y)

y

<

x

},

з) P = {(x, y)

x2 − y2 = 0},

г) P = {(x, y)

x = y},

и) P = {(x, y)

x − y

M5};

д) P = {(x, y)

x +1 = y},

к) P = {(x, y)

x + yM7}.

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}?

12

39. Какими свойствами обладают следующие отношения?

P1		a b c				P2		a b c				P3		a b c				P4		a b c
a		0	1	0		a		1	0	1		a		1	0	1		a		1	0	1
b		1	0	1		b		0	0	0		b		0	1	0		b		0	1	0
c		0	1	0		c		1	0	1		c		1	0	1		c		1	0	0

40. Построить отношения S1 oS2 ,															S2 oS1, P1 o P2 ,							P2 oP1. Определить
свойства исходных и полученных отношений.
	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

41. Пусть X = {1,2,3,4,5},

P = {(1,1),(1,2),(2,3),(2,4),(3,5),(5,4),(3,2)}.

Определить следующие множества:

1)наименьшее рефлексивное отношение на множестве X ;

2)наименьшее симметричное отношение на X , содержащее P ;

3)наименьшее симметричное и рефлексивное отношение на X , содержащее P ;

4)наибольшее симметричное отношение на X , содержащееся в P ;

5)наименьшее транзитивное отношение на X , содержащее P .

42.Доказать, что если отношения P и S рефлексивны, то реф-

лексивны и отношения: 1) P U S ,		2)	P I S ,	3)	P−1 , 4)	P oS .
43.	Доказать, что если отношение P и S иррефлексивны, то ир-
рефлексивны и отношения: 1) P U S ,			2) P I S ,		3) P−1 .
44.	Доказать, что если отношения P и S			симметричны, то сим-
метричны и отношения: 1) P U S ,		2)	P I S ,	3)	P−1 , 4)	P o P−1 .

45.Доказать, что если отношения P и S антисимметричны, то антисимметричны и отношения: P I S , P−1 .

46.Доказать, что если отношения P и S транзитивны, то отно- шение P I S транзитивно.

13