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

Министерство образования и науки Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

С.Х. РОЯК, М.Э. РОЯК

СБОРНИК ЗАДАЧ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

Утверждено Редакционно-издательским советом университета

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

НОВОСИБИРСК

2013

УДК 519.1(076.1) Р 816

Рецензенты:

канд. техн. наук, доцент М.Г. Токарева; канд. физ.-мат. наук, доцент М.П. Тропин

Работа подготовлена на кафедре прикладной математики

Рояк С.Х.

Р 816 Сборник задач по дискретной математике / С.Х. Рояк, М.Э. Рояк. – Новосибирск : Изд-во НГТУ, 2013. – 87 с.

ISBN 978-5-7782-2171-0

Сборник включает подборку задач, используемых при изучении курсов «Дискретная математика», «Дискретная математика и математическая логика» Пособие может быть рекомендовано как для подготовки домашних заданий, так и для самостоятельного изучения курса в комплекте с конспектом лекций.

Предназначено для студентов I курса всех специальностей факультета при- кладной математики и информатики.

УДК 519.1(076.1)

ISBN 978-5-7782-2171-0	©Рояк С.Х., Рояк М.Э., 2013
	© Новосибирский государственный
	технический университет, 2013

ОГЛАВЛЕНИЕ

1.	Системы счисления ....................................................................................	4
	Ответы .....................................................................................................	63
2.	Теория множеств ..........................................................................................	5
	Ответы .....................................................................................................	63
3.	Булева алгебра ............................................................................................	28
	Ответы .....................................................................................................	76
4.	Исчисление высказываний .......................................................................	34
	Ответы .....................................................................................................	80
5.	Исчисление предикатов ............................................................................	46
	Ответы .....................................................................................................	83
ОТВЕТЫ И РЕШЕНИЯ ...............................................................................		63
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ........................................................		87

1. СИСТЕМЫ СЧИСЛЕНИЯ

1. Записать в десятичной системе счисления числа, записанные в Римской системе: IV, VIII, XIX, XL, CCCXC, MCMLXXXIX.

2. Записать в Римской системе счисления числа: 24, 46, 98, 176, 1963, 1998.

3.Какое самое большое 5-значное число в троичной, восьмеричной системах счисления?

4.Как изменится число 325006 если:

а) приписать справа один нуль, б) отбросить справа два нуля?

5.Записать в d-ичной системе числа d 2 , d 3 , …, d n .

6.В турнире участвовали 13 мальчиков и 54 девочки, всего 100 чело- век. В какой системе счисления сделаны эти записи?

7.Определить d , для которого:

а) 2d × 2d

= 10d ,

б) 4d × 4d

= 31d ,

в) 53d = 33,

г) 212d = 23.

8.

Какое из чисел больше:

а) 316

или 38 ,

б) 1416 или 148 ,

æ 1

ö

æ 1

ö

æ

1 ö

æ 1

ö

в) ç

÷

или ç

÷ , г)

ç

÷

или ç

÷ ,

д) 0,112

или 0,1116 ?

è 3

ø5

è 3

ø8

è

14 ø5

è14

ø8

9.

Записать в десятичной системе счисления числа:

1324, 10023, 31758,

21214, 7778,

55417.

10.

Записать числа 49, 57, 101, 196 в d -ичной системе счисления:

а) d = 3, б) d = 5, в) d = 7 .

11.

Перевести числа

1100010112, 10101001002, 1100000102, 100110012

в d -ичную систему счисления:

а) d = 4 ,

б) d = 8,

в) d = 16.

12.Перевести числа 5218, 6158, 4038, 1258 в двоичную систему счисления.

13.Перевести числа A3516, D2716, F4916, E8B516, С60116, 123B16, E457116

в d -ичную систему счисления:

а) d = 4 , б) d = 2 , в) d = 8.

14.Сколько существует n-значных чисел в d-ичной системе счисления?

15.Вычислить:

а) 101,11012 +11,10112 , б) 11101,112 +10011,12 , в) 101101,0112 +1111,1012 , г) 11,12 ×10,12 , д) 1001,112 ×1,112 , е) 0,10112 ×1,12 .

4

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

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

B IC , A U B , ( A U 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. Изобразить на координатной прямой множества AUB , AIB и AIB , если:

а) A = (-1,0] и B = [0,2),

б) A = (−∞,1] и B = (−∞,−3),

в) A = {x x Ρ и - 5 £ x < 2} и B = {x x Ρ и 1< x £ 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.Определить множества:

а) {x x = 5y, y ΢}\{x x =10y, y ΢},

б) {x x = 4n + 2, n ¥}I{x x = 3n, n ¥}, в) {x x = 2 y, y ¢}I{x x = 3y, y ¢},

г) {x x = 2 y, y ¢}U{x x = 3y, y ¢}.

5. Доказать, что:	3) A I B A A U B ;
1) A A;
2) если A B и B C , то A C ;	4)	A I B B A U B ;
	5)	A \ B A .

5

6. Какие знаки из множества {=, ¹, É, Ì,Î} можно поставить вместо символа «?», чтобы полученное утверждение было верным?

1)	{1,3} ? {1,2,3} ,								7)	{(			)		(	3,2	)}	?	{(		)	,		(	2,3		)}		,
											2,1 ,								1,2
2)	{2,3,4}		? {1,2,3} ,							{{ } {						}} {{					} { }}
									8)	1,2				,		2,3		?		3,2		,			2,1				,
	{	}		{	}
			?
3)	1,2,3				x		x делитель 6	,	9)	{{ }				,	{	}}		?	{(	)				(	2,3	)}			,
										1,2						2,3				2,1 ,
4)	{1,2,3} ? {x						x Î¥ и x < 4},		10)	{{ }				,	{ }}			?	{{ }				{		}			{ }}		,
										1,2						2,3				2,1 ,					3,2 ,				1,3
5)	{{1,2}, {2,3}} ? {1,2,3},								11)	Æ		?		Æ
													{			},
6) 1 ?		1 ,							12)	Æ ? {1,3}.
		{ }

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

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

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

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

4)Если A I B Ì C и A UC B , то A IC = .

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

8.Подобрать такие множества A, B и C , для которых выполняются следующие утверждения:

1)AÎ B , B ÎC , AÎC ;

2)A Ì B , B ÎC , AÎC ;

3)A ¹ B , B ¹ C , A ¹ C .

9.Дано произвольное множество A. Определить множества

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

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

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

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

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

13. Доказать эквивалентность пяти утверждений:

1) A Ì B ; 2) A U B = B ; 3) A I B = A; 4) A \ B = Æ ; 5) A U B = U.

6

14. Для заданных в левом столбце таблицы диаграмм Венна указать все соответствующие закрашенной части описания множеств из правого столбца:

I

II

III

IV

V

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

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

3)(( A UB UC) \ (C I(A UB)))U( A IB IC),

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

5)(B ÷ C) \ (A I B),

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

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

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

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

10)C U(( A IC) \ B)U((B IC) \ A),

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

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

13)(A U B UC)\ (C \ (A U B)).

7

15. Описать множества, соответствующие закрашенной части диаграм- мы Венна:

I

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

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) \ ( AIC) ;

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 ;

II

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(B IC) = (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(B UC )I(AUD)I(B UD).

8

17. Доказать следующие тождества:

1)

UUAkt

=UU Akt

;

U(B I Ak

)

=

æ

ö

5)

B Iç

UAk ÷ ;

k K t T

t T k K

2)

IIAkt

= II Akt

;

k K

è k K

ø

I(B U Ak

)

æ

ö

k K t T

t T k K

6)

= B Uç

IAk ÷

;

k K

è k K

ø

3)

U Ak = I Ak ;

7)

U Ak U UBk = U(Ak U Bk );

k K

k K

k K k K

k K

4)

U Ak = I Ak ;

8)

UIAkt Ì IU Akt .

k K

k K

k K t T

t T k K

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

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

i I

2) IAi – наибольшее множество, которое содержится во всех Ai .

i I

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

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

1)P(A I B) = P( A) IP(B), где P(A) – булеан множества A;

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

ü

4) PçUAi

÷

= íUBi

(Ai )ý.

è i I

ø

îi I

þ

21. Пусть A = {1,2,3},

B = {a,b}. Определить множества:

а) A× B ,

в) A× A,

д) A× ,

б) B × A,

г) B × B ,

е) × B .

22. Найти геометрическую интерпретацию множеств:

а) A× B ,

в) C × B ,

д) C × D ,

б) A×C ,

[

]

{

г) A× D ,

е) D × B ,

если A =

[

]

B =

}

– множество

точек квадрата

0,1 ,

2,3 , C =

4,5,6 , D

с вершинами в точках (0,0), (0,1), (1,0), (1,1).

9

23. Доказать, что существуют A, B и C такие, что:

а) A´ B ¹ B ´ A ,	в) A× (B ×C) = ( A× B) ×C ,
б) A× B = B × A ,	г) A´(B ´C) ¹ ( A´ B) ´C .

24.Какие из утверждений предыдущей задачи справедливы для неко- торых непустых множеств A, B и C ?

25.Доказать, что ( A× B) U(C × D) ( A UC) ×(B U D). Какие дополни-

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

26.Доказать, что для произвольных множеств 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 .

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

28. Пусть A = {1, 2, 3, 4, 5, 6}, P A2 . Составить матрицы отношений P , P и P−1 , если:

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

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

29.Составить матрицы отношений P и P−1 , если P Ì A2 , A = {1, 3, 5, 7}:

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)		2 y + x Î A}.

30. Составить матрицу отношения P , если P Ì (P(A))2 , A = {a,b}:

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 = A \ Y}.

10