Відношення. Властивості відношень

1. Нехай M = {1,2,3,4,5}. Для заданого відношення R на множині M визначити Pr₁ R, Pr₂ R, R ^-1, R ° R, R ° R ^-1, R ^-1° R і R ⁽³⁾:

(а) R = {(1,2),(1,4),(2,3),(2,4),(4,1),(4,3),(4,4)};

(б) R = {(1,2),(2,3),(3,5),(4,1),(5,4)};

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

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

2. Для заданого відношення R на множині N

(а) R = { (m,n) | m ділиться на n };

(б) R = { (m,n) | n ділиться на m };

(в) R = { (m,n) | m - n ділиться на k, k Î N };

(г) R = { (m,n) | m < n }

визначити Pr₁ R, Pr₂ R, R ^-1, R ° R, R ° R ^-1, R ^-1° R, .

3. Відношення R на множині N натуральних чисел задано рекурентно

1) (1,1)Î R; 2) якщо (m, n)Î R, то (m +1, n)Î R і (m, n +1)Î R.

Довести, що R = N ´ N.

4. Відношення R на множині N натуральних чисел задано рекурентно

1) (1,1)Î R;

2) якщо (m, n)Î R, то (m +1, n)Î R, (m +1, n +1)Î R і (m +1, n +2)Î R.

Описати відношення R.

5. Нехай на множині всіх людей P означені відношення:

F = {(x, y) ½ x, y Î P і x є батьком y };

D = {(x, y) ½ x, y Î P і x є донькою y }.

Описати такі відношення:

(а) F ° F; (г) D ° F; (є) F ^-1° D ^-1;

(б) D ° D; (д) D ° F ^-1; (ж) D ^-1° F;

(в) F ° D; (е) F ^-1° D; (з) D ^-1° D ^-1.

6. На множині M = {1,2,3,4} задано відношення

R ₁ = {(1,1),(1,3),(2,3),(2,4),(3,1),(3,3),(4,1)},

R ₂ = {(1,2),(1,3),(1,4),(2,2),(3,1),(3,4),(4,2)}.

Знайти відношення X на множині M (або довести, що таке відношення X не існує), для якого виконується

(а) R ₁° X = R ₂; (в) R ₂° X = R ₁; (д) (R ₁° R ₂)° X = R ₁;

(б) X ° R ₁ = R ₂; (г) X ° R ₂ = R ₁; (е) (R ₂° R ₁)° X = R ₁.

7. На множині M = {1,2,3,4} задано відношення R = {(1,1),(1,2),(2,3),(3,3),(3,4),(4,4)}. Знайти такі два відношення T і S на M, що T ¹ S і R ° T = R ° S = {(1,1),(1,2),(1,4)}.

8. Довести, що для довільного відношення R на множині M виконується

(а) Pr₁ R = Æ Û R = Æ Û Pr₂ R = Æ;

(б) Pr₂ R = Pr₁ R ^-1;

(в) Pr₁ R = Pr₂ R ^-1;

(г) Pr₁ R = M Û i_M Í R ° R ^-1;

(д) Pr₂ R = M Û i_M Í R ^-1° R.

9. Довести, що для будь-яких відношень виконується

(а) R È R = R Ç R = R; (д) (R ₁ \ R ₂)^-1 = R ₁^-1 \ R ₂^-1;

(б) (R ^-1)^-1 = R; (е) ^-1;

(в) (R ₁È R ₂)^-1 = R ₁^-1È R ₂^-1; (є) ( R_i)^-1 = R_i ^-1;

(г) (R ₁Ç R ₂)^-1 = R ₁^-1Ç R ₂^-1; (ж) ( R_i)^-1 = R_i ^-1.

10. Довести, що для довільних відношень виконується

(а) R ₁° (R ₂° R ₃) = (R ₁° R ₂)° R ₃;

(б) (R ₁° R ₂)^-1 = R ₂^-1° R ₁^-1;

(в) ( R_i)° Q = (R_i ° Q);

(г) Q ° ( R_i) = (Q ° R_i);

(д) R ₁° R ₂ = Æ Û Pr₂ R ₁ÇPr₁ R ₂ = Æ.

11. Довести, що для довільних відношень R_i, i Î I та Q на множині M

(а) ( R_i)° Q Í (R_i ° Q); (б) Q ° ( R_i) Í (Q ° R_i)

і знак включення не можна замінити на знак рівності.

12. Навести приклад відношень R ₁ і R ₂ на множині M = {1,2,3} таких, що відношення R ₁° R ₂ і R ₂° R ₁ не збігаються.

13. Нехай R ₁ і R ₂ - відношення на множині M. Довести або спростувати таку рівність: = ₁° ₂.

14. Знайти всі відношення X на множині M такі, що для довільного відношення R на M виконується рівність R ° X = X ° R.

15. Нехай R - відношення на множині M. Довести, що R ° R ₁= R ₁° R = R ₁ для довільного відношення R ₁ на множині M тоді і тільки тоді, коли R = i_M.

16. Довести, що співвідношення R ° H = H ° R = H виконується для довільного відношення R тоді і тільки тоді, коли H= Æ.

17. Для яких відношень виконується R ^-1 = ?

18. Довести, що коли R ₁Í R ₂, тоді для довільного відношення Q виконується

(а) Q ° R ₁ Í Q ° R ₂; (б) R ₁° Q Í R ₂° Q; (в) R ₁^-1Í R ₂^-1.

19. На множині M = {1,2,3,4} задано відношення

R ₁ = {(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)};

R ₂ = {(1,1),(2,2),(2,3),(2,4),(3,1),(3,3),(4,1),(4,4)};

R ₃ = {(1,3),(1,4),(2,1),(1,2),(3,1),(3,3),(4,1)};

R ₄ = {(1,1),(1,2),(1,4),(2,2),(2,4),(3,3),(3,4),(4,2),(4,3),(4,4)};

R ₅ = {(1,2),(1,3),(2,3),(2,4),(4,1),(4,3)}.

Визначити, які з цих відношень є

(а) рефлексивними;

(б) антирефлексивними;

(в) симетричними;

(г) антисиметричними;

(д) транзитивними.

Побудувати графіки, графи та матриці заданих відношень.

20. Дайте інтерпретацію властивостей відношень за допомогою їхніх матриць, графіків і діаграм.

21. На множині Z задано відношення:

(m,n)Î R ₁Û m-n парне число;

(m,n)Î R ₂Û m+n парне число;

(m,n)Î R ₃Û m-n £ 100;

(m,n)Î R ₄Û m-n непарне число;

(m,n)Î R ₅Û m+n непарне число;

(m,n)Î R ₆Û m/n парне число;

(m,n)Î R ₇Û m/n непарне число;

(m,n)Î R ₈Û m* n парне число;

(m,n)Î R ₉Û m* n непарне число;

(m,n)Î R ₁₀Û m-n є степенем числа 2;

(m,n)Î R ₁₁ Û m і n є взаємно простими;

(m,n)Î R ₁₂ Û m £ n;

(m,n)Î R ₁₃ Û m ділить n;

(m,n)Î R ₁₄ Û m / n є степенем числа 2.

Визначити, які з цих відношень є

(а) рефлексивними;

(б) антирефлексивними;

(в) симетричними;

(г) антисиметричними;

(д) транзитивними;

(е) толерантними.

22. Нехай R ₁ і R ₂ - деякі відношення на скінченній множині M, а C ₁ і C ₂ матриці цих відношень. Визначити матрицю C для відношення

(а) R ₁È R ₂; (г) R ₁D R ₂; (є) ;

(б) R ₁Ç R ₂; (д) R ₁° R ₂; (ж) i_M È R ₁;

(в) R ₁\ R ₂; (е) R ₁^-1; (з) R ₁\ i_M.

23. Довести, що для довільних рефлексивних відношень R ₁ і R ₂ відношення R ₁È R ₂, R ₁Ç R ₂, R ₁^-1 і R ₁° R ₂ будуть також рефлексивними.

24. Довести, що для довільного рефлексивного відношення R і для будь-якого k =0,1,2,... відношення R ^{( k )} є рефлексивним.

25. Довести, що для довільних рефлексивних відношень R ₁ і R ₂ виконується R ₁È R ₂Í R ₁° R ₂.

26. Нехай R - відношення на множині M. Довести або спростувати таке твердження: якщо R ° R - рефлексивне, то і R рефлексивне.

27. Довести, що відношення R на множині M є рефлексивним тоді і лише тоді, коли

(а) i_M Í R; (б) i_M Ç R = i_M; (в) i_M È R = R.

28. Нехай R_i, i Î I - відношення на множині M. Довести або спростувати таке твердження:

(а) R_i - рефлексивне тоді і тільки тоді, коли кожне R_i рефлексивне, i Î I;

(б) R_i - рефлексивне тоді і тільки тоді, коли кожне R_i рефлексивне, i Î I;

(в) R_i ° R_j - рефлексивне тоді і тільки тоді, коли R_i і R_j рефлексивні, i, j Î I;

(г) R_i^{- 1} - рефлексивне тоді і тільки тоді, коли R_i рефлексивне.

29. Нехай R - відношення на скінченній множині M (| M | = n). Довести або спростувати таке твердження:

(а) якщо R рефлексивне, то | R |³ n;

(б) якщо | R |³ n, то R рефлексивне.

30. Рефлексивним замиканням відношення R на множині M назвемо найменше рефлексивне відношення на M, яке містить R; позначимо його r (R).

Довести, що для довільного відношення R на множині M виконується

(а) r (R)= R È i_M;

(б) якщо R Í R¢ і R¢ - рефлексивне, то r (R)Í R¢.

31. Довести, що коли відношення R ₁ і R ₂ антирефлексивні, тоді антирефлексивними є і відношення R ₁È R ₂, R ₁Ç R ₂, R ₁^-1.

32. Довести, що композиція R ₁° R ₂ двох антирефлексивних відношень R ₁ і R ₂ може не бути антирефлексивним відношенням.

33. Нехай R_i, i Î I - відношення на множині M. Довести або спростувати таке твердження:

(а) R_i - антирефлексивне тоді і тільки тоді, коли кожне R_i антирефлексивне, i Î I;

(б) R_i - антирефлексивне тоді і тільки тоді, коли кожне R_i антирефлексивне, i Î I;

(в) R_i ° R_j - антирефлексивне тоді і тільки тоді, коли R_i і R_j антирефлексивні, i, j Î I;

(г) R_i^{- 1} - антирефлексивне тоді і тільки тоді, коли R_i антирефлексивне.

34. Навести приклад двох антирефлексивних відношень R ₁ і R ₂ на множині M = {1,2,3}, композиція R ₁° R ₂ яких буде рефлексивним відношенням.

35. Довести, що для симетричних відношень R ₁і R ₂ будуть симетричними і відношення R ₁È R ₂, R ₁Ç R ₂, R ₁^-1, R ₁° R ₁^-1.

36. Довести, що для довільного симетричного відношення R і для будь-якого k =0,1,2,... відношення R ^{( k )} є симетричним.

37. Довести, що відношення R є симетричним тоді і тільки тоді, коли

(а) R = R ^-1; (б) R ^-1Í R; (в) R Í R ^-1.

38. Симетричним замиканням відношення R на множині M назвемо найменше симетричне відношення на M, яке містить R; позначимо його s (R).

Довести, що для довільного відношення R на множині M виконується

(а) s (R)= R È R ^-1;

(б) якщо R Í R¢ і R¢ - симетричне, то s (R)Í R¢.

39. Довести, що відношення R на множині M не є симетричним тоді і тільки тоді, коли R Ç R ^-1=Æ.

40. Довести, що для симетричного відношення R виконується Pr₁ R =Pr₂ R.

41. Спростувати таке твердження: якщо для деякого відношення R виконується Pr₁ R = Pr₂ R, то відношення R є симетричним.

42. Довести, що відношення R симетричне, тоді і тільки тоді, коли симетричним є відношення

(а) R ^-1; (б) .

43. Побудувати два симетричних відношення R ₁ і R ₂на множині M ={1,2,3,4}, композиція яких R ₁° R ₂не буде симетричним відношенням.

44. Нехай R ₁ і R ₂ - симетричні відношення на множині M. Довести, що коли R ₁° R ₂Í R ₂° R ₁, то R ₁° R ₂ = R ₂° R ₁.

45. Довести, що композиція R ₁° R ₂ симетричних відношень R ₁ і R ₂ є симетричним відношенням тоді і тільки тоді, коли R ₁° R ₂ = R ₂° R ₁.

46. Довести, що композиція R ₁° R ₂ симетричних відношень R ₁ і R ₂ є симетричним відношенням тоді і тільки тоді, коли R ₂° R ₁Í R ₁° R ₂.

47. Нехай R_i, i Î I - відношення на множині M. Довести або спростувати таке твердження:

(а) R_i - симетричне тоді і тільки тоді, коли кожне R_i симетричне, i Î I;

(б) R_i - симетричне тоді і тільки тоді, коли кожне R_i симетричне, i Î I;

(в) R_i ° R_j - симетричне тоді і тільки тоді, коли R_i і R_j симетричні, i, j Î I;

(г) R_i^{- 1} - симетричне тоді і тільки тоді, коли R_i симетричне.

28. Довести, що для антисиметричних відношень R ₁ і R ₂ відношення R ₁Ç R ₂ і R ₁^-1 будуть також антисиметричними.

48. Довести, що відношення R на множині M є антисиметричним тоді і тільки тоді, коли R Ç R ^-1Í i_M.

49. Довести, що об’єднання R ₁È R ₂ антисиметричних відношень R ₁ і R ₂ на множині M буде антисиметричним відношенням тоді і тільки тоді, коли R ₁Ç R ₂^-1Í i_M.

50. Нехай R_i, i Î I - відношення на множині M. Довести або спростувати таке твердження:

(а) R_i - антисиметричне тоді і тільки тоді, коли кожне R_i антисиметричне, i Î I;

(б) R_i - антисиметричне тоді і тільки тоді, коли кожне R_i антисиметричне, i Î I;

(в) R_i ° R_j - антисиметричне тоді і тільки тоді, коли R_i і R_j антисиметричні, i, j Î I;

(г) R_i^{- 1} - антисиметричне тоді і тільки тоді, коли R_i антисиметричне.

51. Нехай R - антисиметричне відношення на скінченній множині M (| M | = n). Яким є найбільше значення для величини | R |? Для скількох антисиметричних відношень R на M це найбільше значення досягається?

52. Довести, що відношення R на множині M є транзитивним тоді і тільки тоді, коли R ° R Í R.

53. Довести, що рефлексивне відношення R є транзитивним тоді і тільки тоді, коли R ° R = R.

54. Довести, що транзитивне і антирефлексивне відношення R є антисиметричним.

55. Довести, що відношення R транзитивне тоді і тільки тоді, коли відношення R ^-1транзитивне.

56. Довести, що перетин транзитивних відношень є транзитивним відношенням.

57. Довести, що для довільного транзитивного відношення R і для будь-якого k =0,1,2,... відношення R ^{( k )} є транзитивним.

58. Навести приклад транзитивних відношень R ₁ і R ₂ на множині M ={1,2,3,4} таких, що

(а) R ₁° R ₂ - нетранзитивне; (г) R ₁° R ₁= R ₁;

(б) R ₁° R ₂ - транзитивне; (д) R ₁È R ₂ - нетранзитивне;

(в) R ₁° R ₁¹ R ₁; (е) R ₁È R ₂ - транзитивне.

59. Довести, що композиція R ₁° R ₂ транзитивних відношень R ₁ і R ₂ є транзитивним відношенням, якщо R ₁° R ₂ = R ₂° R ₁.

60. Довести, що об’єднання R ₁È R ₂ транзитивних відношень R ₁ і R ₂ буде транзитивним відношенням тоді і тільки тоді, коли R ₁° R ₂ È R ₂° R ₁ Í R ₁È R ₂.

61. Нехай R_i, i Î I - відношення на множині M. Довести або спростувати таке твердження:

(а) R_i - транзитивне тоді і тільки тоді, коли кожне R_i транзитивне, i Î I;

(б) R_i - транзитивне тоді і тільки тоді, коли кожне R_i транзитивне, i Î I;

(в) R_i ° R_j - транзитивне тоді і тільки тоді, коли R_i і R_j транзитивні, i, j Î I;

(г) R_i^{- 1} - транзитивне тоді і тільки тоді, коли R_i транзитивне.

62. Довести, що для рефлексивного й транзитивного відношення R виконується R ° R = R. Чи справедливе обернене твердження?

63. Знайти помилку в наведених міркуваннях. Якщо R симетричне і транзитивне відношення на множині M, то R - рефлексивне, оскільки з того, що (a,b)Î R послідовно випливає (b,a)Î R і (a,a)Î R.

64. Навести приклад відношення R на множині M = {1,2,3,4}, яке

(а) не є рефлексивним, але й не є антирефлексивним;

(б) не є симетричним, але й не є антисиметричним.

65. Побудувати відношення R на множині M = {1,2,3}, яке є симетричним і антисиметричним одночасно.

66. Побудувати відношення

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

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

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

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

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

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

(є) несиметричне, неантисиметричне;

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