Файл: Дискретная математика- задания.pdf

11

c)  {(x, y) 

∈

 D

2

 | 0 

≤

 x 

≤

 1 або 0 

≤

 y 

≤

 1}; 

d)  {(x, y) 

∈

 D

2

 | 0 

≤

 x 

≤

 1 i 0 

≤

 y 

≤

 1}. 

28. Знайти R

2

 i R

-1

 для відношення R = {(x, y) | x, y 

∈

 N

+

 i x ділить у}. 

29. Довести, що для будь яких бінарних відношень мають місце нерівності: 

(R 

∪

 R

1

) 

–1

 = R

-1

∪

 R

1

-1

,   

(R

′

)

-1

 = (R

-1

)

′

. 

Довести, що коли бінарне відношення R на А: 

a)  симетричне, то R = R

-1

; 

b)  рефлексивне і транзитивне, то R

2

 = R; 

c)  рефлексивне і антисиметричне, то R 

∩

 R

-1

 = i. 

30. Навести приклад бінарного відношення, яке: 

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

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

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

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

31. Нехай A = {a, b, c, d, e}, a R = {(a, b), (a, c), (b, b), (c, c), (e, e), (d, d), (d, 

a), (d, b), (c, d), (e, d)} i R

1

 = {(a, d), (d, a), (c, d), (c, c), (b, b)} – бінарні ві-

дношення на множині А. 

Побудувати R

-1

, R 

∩

 R

1

, R 

∪

 R

1

, R \ R

1

, R 

÷

 R

1

. 

Чи буде відношення R, R 

∩

 R

1

, R 

÷

 R

1

, R 

∪

 R

1

, R \ R

1

 рефлексивним, симе-

тричним, транзитивним? 

Побудувати матриці відношень для R, R

1

, R 

∩

 R

1

, R 

∪

 R

1

, R

i

 R

s

, R

t

, R

1

∪

 R

s

, 

R

2

, R

3

. 

32. Яке  відношення  є  транзитивним  замиканням  відношення  “Х  –  прямий 

нащадок Y”? 

33. Нехай А = {2, 3, 5, 6, 11, 12, 14} та 

≤

 – відношення часткового порядку 

на А, таке, що х 

≤

 у 

⇔

 х ділить у. 

Побудувати множину відношення 

≤

 та упорядкувати множину А відносно 

цього порядку. 

34. Показати, що відношення 

⊆

 для множин є відношенням часткового порядку. 

Для яких множин А булеан В(А) буде лінійно упорядкованою множиною 

відносно відношення 

⊆

? 

12

35. Довести, що коли f – функція із А в В, fg – функція із В в С, то f * g є 

функцією із А в С. 

36. Довести, що для того щоб відображення R: A 

→

 B було взаємно одноз-

начним, необхідно і достатньо, щоб і

А

 = R * R

-1

, R

-1

 * R = i

B.

37. Довести, що коли f – довільна функція, то f(A 

∩

B) 

⊆

 f (A) 

∩

 f(B), (A 

⊆

⊆

 B) 

⇒

 f(A) 

⊆

 f(B). 

38. Встановити  взаємнооднозначну  відповідність  між  множинами  А 

×

  В   і  

В 

×

 А. 

39. Нехай F = {a, b, c, d, e, f, g, h}, R = {1, 2, 3, 4, 5, 6, 7, 8}. Тоді множиною 

шахових  кліток  буде  S  =  F 

×

  R.  Визначити  бінарне  відношення  С  – 

множину допустимих ходів для тури на множині S. 

40. Нехай X = {2, 4, 6, 8} i 

ς

 = {(x, y): x, y 

∈

 X i x 

<

 y};виписати усі елемен-

ти 

ς

 і 

ς

–1

41. Нехай 

ε

 = P ({a, b, c}). Знайти усі елементи 

⊂

 (включення). 

42. Задати відношення N на множині жителів однієї вулиці Н, таке що h

i

 і h

j

– сусіди (h

i

, h

j

, 

∈

 H) 

a)  символьне, 

b)  графічне, 

c)  у вигляді матриці. 

43. Нехай A = {a

1

, a

2

, a

3

, a

4

} побудувати бінарне відношення 

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

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

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

44. Перевірити властивості відношень 

a)   A = {1, 2, 3, 5} 

b)   

ς

 = {(a, b) a - b – чотне, для a, b 

∈

 A} 

c)   

ς

 = {(a, b) a + b – чотне, для a, b ( A} 

d)   P - множина людей 

ς

 = {(a, b) : a, b 

∈

 P, a і b мають загального предка} 

45. Нехай А - множина всіх прямих на площині.

Чи є еквівалентностями та-

кі відношення: рівнобіжність; перпендикулярність. 

46. На множині Q – раціональних чисел визначити відношення R у такий спо-

сіб, а R b 

⇔

 (a - b) – раціональне число. Довести, що R – еквівалентність. 

13

47. Нехай 

τ

 і 

π

 відношення на N

2

: 

a)  (a, b) 

τ

 (c, d) 

⇔

 a 

≤

 c   

і  

b 

≤

 d 

b)  (a, b) 

π

 (c, d) 

⇔

 a 

≤

 c  

і 

 b 

≥

 d 

Чи є 

τ

 і 

π

 відношеннями порядку. 

48. Нехай R і S визначені на Р - де Р - множина людей 

R = {(x, y) | x, y 

∈

 p і x - батько в}; 

S = {(x, y) | x, y 

∈

 p і x - дочка в}. 

Описати явно 

R

2

; 

S

2

; 

RS;  SR;  SR

1

; 

R

1

S;  R

1

S

1

;  S

1

R;  S

1

S

1

;  S

1

R

1

. 

49. Описати замикання R і S 

50. Зазначити  області  визначення  і  значення  для  відповідності  «Більше», 

якщо A = {2, 4, 6}; R = {1, 4, 6, 7} 

51. Скільки відповідностей можна встановити між елементами множин A = 

{k, m, n} і B = {B1, B2, B3}. Які з цих відповідностей є відображення-
ми? До яких типів ставляться приведені відповідності? 

52. Зазначити область визначення і значення відповідності «рівність», якщо 

A= {-4, 5}; B = {-2, 6, 8, 9} 

53. Нехай х 

∈

 Х и у 

∈

 Y і А - відношення між елементами множин X і Y. т. 

е. хАу. Зазначте, у яких випадках А можна розглядати як функцію: 

a)  Х  -  множина  студентів,  Y  -  множина  навчальних  дисциплін,  хАу  -  «х 

вивчає у» 

b)  Х - множина студентів, Y - ріст в одиницях довжини, хАу - «х має ріст у» 

c)  Х  -  множина  інтегральних  схем  друкарського  вузла,  Y  -  множина  дру-

карських вузлів, хАу - «х входить в у». 

54. Нехай А = {a, b, c, d}; B = {1, 2, 3} задати функцію з А в В 

a)  довільну; 

b)  ін’єктивну; 

c)  сюр’єктивну; 

d)  бієктивну. 

Т

ЕМА 

2

Е

ЛЕМЕНТИ КОМБІНАТОРНОГО АНАЛІЗУ

Приклади вирішення задач 

14

1.  Скількома способами на першості світу з футболу можуть розподілити-

ся медалі, якщо у фінальній частині грають 24 команди? 

Розв’язок.  Золоту  медаль  може  отримати  будь  яка  з  24-х  команд, 

тобто  маємо  24  можливості.  Срібну  медаль  може  виграти  одна  з  23-х ко-
манд, а бронзову – одна з 22-х команд. За основними правилами комбіна-
торики загальне число способів розподілу медалей:   

24  *  23  *  22  = 

12144. 

2.  Скільки тризначних чисел можна скласти з цифр 0, 1, 2, 3, 4, 5, якщо: 

a)  цифри можуть повторюватися; 

b)  ні одна з цифр повторюються двічі; 

c)  цифри непарні і можуть повторюватися. 

Розв’язок 

Варіант 1. Першою цифрою може бути одна із цифр 1, 2, 3, 4, 5, оскі-

льки 0 не може бути першою цифрою, бо в такому випадку число не буде 
тризначним. Якщо перша цифра вибрана, то друга може бути вибрана шіс-
тьма способами, як і третя цифра. Отже, загальне число тризначних цифр  

5 * 6 * 6 = 180. 

Варіант 2. Першою цифрою може бути одна з п’яти цифр – 1, 2, 3, 4, 

5, якщо перша цифра вибрана, то другою може бути теж одна з п’яти цифр 

(тут  враховується  0),  а  третя  може  бути  вибрана  чотирма способами  з чо-
тирма  способами  з  чотирьох  цифр,  що  залишилися.  Отже,  загальна  кіль-
кість таких тризначних чисел 5 * 5 * 4 = 100. 

Варіант  3.  Першою  цифрою  може  бути  одна  з  трьох  цифр:  1,  3,  5. 

Другою теж може бути одна з цих трьох цифр. Аналогічно і третя цифра 
може бути вибрана трьома способами. Таким чином, загальна кількість та-
ких чисел дорівнює 3 * 3 * 3 = 27. 

3.  Збірна  команда  університету  з  волейболу  налічує  15  чоловік.  Скільки 

різних  варіантів  повинен  розглянути  тренер  перед  грою,  щоб  заявити 
список гравців на гру? 

15

Розв’язок.  Число  гравців  волейбольної  команди    дорівнює  шести. 

Значить, число всіх можливих варіантів – це число різних підмножин, які 
складаються з шести елементів у множині з 15-ти елементів. Отже маємо: 

5005

11

13

7

5

1

2

3

4

5

6

10

11

12

13

14

15

9

6

15

6

15

=

=

=

=

*

*

*

*

*

*

*

*

*

*

*

*

*

!

!

!

С

4.  У  скількох  точках  перетинаються  діагоналі  випуклого  десятикутника, 

якщо ніякі три з них не перетинаються в одній точці. 

Розв’язок.  Кожній  точці  перетину  двох  різних  діагоналей  відпові-

дають  чотири  вершини  десятикутника,  а  кожним  чотирьом  вершинам  – 
одна  точка  перетину.  Таким  чином,  число  всіх  точок  перетину  дорівнює 
числу  способів,  якими  з  десяти  вершин  можна  вибрати  чотири  вершини, 

тобто  

210

2

3

4

7

8

9

10

6

4

10

4

10

=

=

=

*

*

*

*

*

!

!

!

С

точок перетину. 

5.  Скількома різними способами можна розмітити п’ять книжок на книж-

ковій полиці? 

Розв’язок. Шукане число розміщень є числом способів упорядкуван-

ня множин з п’яти елементів. Значить, це число дорівнює 

Р

5

 = 5 * 4 * 3 * 2 * 1 = 120. 

6.  Скількома способами можна упорядкувати n-елементну множину 

A = {1, 2, …, n} (n 

≥

 2) так, щоб останні два елементи були n – 1 i n? 

Розв’язок. Число способів буде P

n – 2

 = (n – 2)! 

7.  Скільки  різних  слів можна побудувати  перестановкою  букв  у  слові  “ла-

ваш”? 

Розв’язок. Слово “лаваш” містить по одному екземпляру букв л, в, ш 

і два екземпляри букв а, а загальна кількість букв 5. За формулою знаходимо 

60

3

4

5

1

1

1

2

5

=

−

*

*

!

!

!

!

!