Відношення. Властивості відношень
1. Нехай M = {1,2,3,4,5}. Для заданого відношення R на множині M визначити Pr1R, Pr2R, R -1, R °R, R °R -1, R -1°R і R(3):
(а) 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 }
визначити Pr1R, Pr2R, 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} задано відношення
R1 = {(1,1),(1,3),(2,3),(2,4),(3,1),(3,3),(4,1)},
R2 = {(1,2),(1,3),(1,4),(2,2),(3,1),(3,4),(4,2)}.
Знайти відношення X на множині M (або довести, що таке відношення X не існує), для якого виконується
(а) R1°X = R2; (в) R2°X = R1; (д) (R1°R2)°X = R1;
(б) X°R1 = R2; (г) X°R2 = R1; (е) (R2°R1)°X = R1.
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 виконується
(а) Pr1R = Æ Û R = Æ Û Pr2R = Æ;
(б) Pr2R = Pr1R -1;
(в) Pr1R = Pr2R -1;
(г) Pr1R=M Û iM Í R°R-1;
(д) Pr2R=M Û iM Í R-1°R.
9. Довести, що для будь-яких відношень виконується
(а) R È R = R Ç R = R; (д) (R1 \ R2)-1 = R1-1 \ R2-1;
(б) (R -1)-1 = R; (е) 
-1;
(в) (R1ÈR2)-1 = R1-1ÈR2-1; (є) ( 
Ri)-1 = Ri-1;
(г) (R1ÇR2)-1 = R1-1ÇR2-1; (ж) ( 
Ri)-1 = Ri-1.
10. Довести, що для довільних відношень виконується
(а) R1° (R2°R3) = (R1°R2)°R3;
(б) (R1°R2)-1 = R2-1°R1-1;
(в) ( Ri)°Q = (Ri °Q) ;
(г) Q ° ( Ri) = (Q °Ri);
(д) R1°R2 = Æ Û Pr2R1ÇPr1R2 = Æ.
11. Довести, що для довільних відношень Ri, iÎI та Q на множині M
(а) ( Ri)°Q Í (Ri°Q) ; (б) Q ° ( Ri) Í (Q °Ri)
і знак включення не можна замінити на знак рівності.
12. Навести приклад відношень R1 і R2 на множині M = {1,2,3} таких, що відношення R1°R2 і R2°R1 не збігаються.
13. Нехай R1 і R2 - відношення на множині M. Довести або спростувати таку рівність: 
= 1° 2.
14. Знайти всі відношення X на множині M такі, що для довільного відношення R на M виконується рівність R°X = X°R.
15. Нехай R - відношення на множині M. Довести, що R°R1=R1°R=R1 для довільного відношення R1 на множині M тоді і тільки тоді, коли R=iM .
16. Довести, що співвідношення R°H=H°R=H виконується для довільного відношення R тоді і тільки тоді, коли H= Æ.
17. Для яких відношень виконується R -1 = ?
18. Довести, що коли R1ÍR2, тоді для довільного відношення Q виконується
(а) Q °R1 Í Q °R2; (б) R1°Q Í R2°Q; (в) R1-1Í R2-1.
19. На множині M = {1,2,3,4} задано відношення
R1 = {(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)};
R2 = {(1,1),(2,2),(2,3),(2,4),(3,1),(3,3),(4,1),(4,4)};
R3 = {(1,3),(1,4),(2,1),(1,2),(3,1),(3,3),(4,1)};
R4 = {(1,1),(1,2),(1,4),(2,2),(2,4),(3,3),(3,4),(4,2),(4,3),(4,4)};
R5 = {(1,2),(1,3),(2,3),(2,4),(4,1),(4,3)}.
Визначити, які з цих відношень є
(а) рефлексивними;
(б) антирефлексивними;
(в) симетричними;
(г) антисиметричними;
(д) транзитивними.
Побудувати графіки, графи та матриці заданих відношень.
20. Дайте інтерпретацію властивостей відношень за допомогою їхніх матриць, графіків і діаграм.
21.На множині Z задано відношення:
(m,n)ÎR1Û m-n парне число;
(m,n)ÎR2Û m+n парне число;
(m,n)ÎR3Û m-n £ 100;
(m,n)ÎR4Û m-n непарне число;
(m,n)ÎR5Û m+n непарне число;
(m,n)ÎR6Û m/n парне число;
(m,n)ÎR7Û m/n непарне число;
(m,n)ÎR8Û m* n парне число;
(m,n)ÎR9Û m* n непарне число;
(m,n)ÎR10Û m-n є степенем числа 2;
(m,n)ÎR11 Û m і n є взаємно простими;
(m,n)ÎR12 Û m £ n;
(m,n)ÎR13 Û m ділить n;
(m,n)ÎR14 Û m / n є степенем числа 2.
Визначити, які з цих відношень є
(а) рефлексивними;
(б) антирефлексивними;
(в) симетричними;
(г) антисиметричними;
(д) транзитивними;
(е) толерантними.
22. Нехай R1 і R2 - деякі відношення на скінченній множині M, а C1 і C2 матриці цих відношень. Визначити матрицю C для відношення
(а) R1ÈR2; (г) R1DR2; (є) 
;
(б) R1ÇR2; (д) R1°R2; (ж) iM ÈR1;
(в) R1\R2; (е) R1-1; (з) R1\ iM.
23. Довести, що для довільних рефлексивних відношень R1 і R2 відношення R1ÈR2, R1ÇR2, R1-1 і R1°R2 будуть також рефлексивними.
24. Довести, що для довільного рефлексивного відношення R і для будь-якого k=0,1,2,... відношення R(k) є рефлексивним.
25. Довести, що для довільних рефлексивних відношень R1 і R2 виконується R1ÈR2ÍR1°R2.
26. Нехай R - відношення на множині M. Довести або спростувати таке твердження: якщо R°R - рефлексивне, то і R рефлексивне.
27. Довести, що відношення R на множині M є рефлексивним тоді і лише тоді, коли
(а) iM Í R; (б) iM ÇR = iM; (в) iM ÈR = R.
28. Нехай Ri, iÎI - відношення на множині M. Довести або спростувати таке твердження:
(а) 
Ri - рефлексивне тоді і тільки тоді, коли кожне Ri рефлексивне, iÎI;
(б) 
Ri - рефлексивне тоді і тільки тоді, коли кожне Ri рефлексивне, iÎI;
(в) Ri°Rj - рефлексивне тоді і тільки тоді, коли Ri і Rj рефлексивні, i,jÎI;
(г) Ri-1 - рефлексивне тоді і тільки тоді, коли Ri рефлексивне.
29. Нехай R - відношення на скінченній множині M (|M| = n). Довести або спростувати таке твердження:
(а) якщо R рефлексивне, то |R|³n;
(б) якщо |R|³n, то R рефлексивне.
30. Рефлексивним замиканням відношення R на множині M назвемо найменше рефлексивне відношення на M, яке містить R; позначимо його r(R).
Довести, що для довільного відношення R на множині M виконується
(а) r(R)=RÈiM;
(б) якщо RÍR¢ і R¢ - рефлексивне, то r(R)ÍR¢.
31. Довести, що коли відношення R1 і R2 антирефлексивні, тоді антирефлексивними є і відношення R1ÈR2, R1ÇR2, R1-1.
32. Довести, що композиція R1°R2 двох антирефлексивних відношень R1 і R2 може не бути антирефлексивним відношенням.
33. Нехай Ri, iÎI - відношення на множині M. Довести або спростувати таке твердження:
(а) Ri - антирефлексивне тоді і тільки тоді, коли кожне Ri антирефлексивне, iÎI;
(б) Ri - антирефлексивне тоді і тільки тоді, коли кожне Ri антирефлексивне, iÎI;
(в) Ri°Rj - антирефлексивне тоді і тільки тоді, коли Ri і Rj антирефлексивні, i,jÎI;
(г) Ri-1 - антирефлексивне тоді і тільки тоді, коли Ri антирефлексивне.
34. Навести приклад двох антирефлексивних відношень R1 і R2 на множині M = {1,2,3}, композиція R1°R2 яких буде рефлексивним відношенням.
35. Довести, що для симетричних відношень R1і R2 будуть симетричними і відношення R1ÈR2, R1ÇR2, R1-1, R1°R1-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 виконується Pr1R=Pr2R.
41. Спростувати таке твердження: якщо для деякого відношення R виконується Pr1R = Pr2R, то відношення R є симетричним.
42. Довести, що відношення R симетричне, тоді і тільки тоді, коли симетричним є відношення
(а) R-1; (б) 
.
43. Побудувати два симетричних відношення R1 і R2на множині M={1,2,3,4}, композиція яких R1°R2не буде симетричним відношенням.
44. Нехай R1 і R2 - симетричні відношення на множині M. Довести, що коли R1°R2ÍR2°R1, то R1°R2 = R2°R1.
45. Довести, що композиція R1°R2 симетричних відношень R1 і R2 є симетричним відношенням тоді і тільки тоді, коли R1°R2 = R2°R1.
46. Довести, що композиція R1°R2 симетричних відношень R1 і R2 є симетричним відношенням тоді і тільки тоді, коли R2°R1ÍR1°R2 .
47. Нехай Ri, iÎI - відношення на множині M. Довести або спростувати таке твердження:
(а) Ri - симетричне тоді і тільки тоді, коли кожне Ri симетричне, iÎI;
(б) Ri - симетричне тоді і тільки тоді, коли кожне Ri симетричне, iÎI;
(в) Ri°Rj - симетричне тоді і тільки тоді, коли Ri і Rj симетричні, i,jÎI;
(г) Ri-1 - симетричне тоді і тільки тоді, коли Ri симетричне.
28. Довести, що для антисиметричних відношень R1 і R2 відношення R1ÇR2 і R1-1 будуть також антисиметричними.
48. Довести, що відношення R на множині M є антисиметричним тоді і тільки тоді, коли R ÇR -1Í iM.
49. Довести, що об’єднання R1ÈR2 антисиметричних відношень R1 і R2 на множині M буде антисиметричним відношенням тоді і тільки тоді, коли R1ÇR2-1Í iM.
50. Нехай Ri, iÎI - відношення на множині M. Довести або спростувати таке твердження:
(а) Ri - антисиметричне тоді і тільки тоді, коли кожне Ri антисиметричне, iÎI;
(б) Ri - антисиметричне тоді і тільки тоді, коли кожне Ri антисиметричне, iÎI;
(в) Ri°Rj - антисиметричне тоді і тільки тоді, коли Ri і Rj антисиметричні, i,jÎI;
(г) Ri-1 - антисиметричне тоді і тільки тоді, коли Ri антисиметричне.
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. Навести приклад транзитивних відношень R1 і R2 на множині M={1,2,3,4} таких, що
(а) R1°R2 - нетранзитивне; (г) R1°R1=R1;
(б) R1°R2 - транзитивне; (д) R1ÈR2 - нетранзитивне;
(в) R1°R1¹R1; (е) R1ÈR2 - транзитивне.
59. Довести, що композиція R1°R2 транзитивних відношень R1 і R2 є транзитивним відношенням, якщо R1°R2 = R2°R1.
60. Довести, що об’єднання R1ÈR2 транзитивних відношень R1 і R2 буде транзитивним відношенням тоді і тільки тоді, коли R1°R2 È R2°R1 Í R1ÈR2.
61. Нехай Ri, iÎI - відношення на множині M. Довести або спростувати таке твердження:
(а) Ri - транзитивне тоді і тільки тоді, коли кожне Ri транзитивне, iÎI;
(б) Ri - транзитивне тоді і тільки тоді, коли кожне Ri транзитивне, iÎI;
(в) Ri°Rj - транзитивне тоді і тільки тоді, коли Ri і Rj транзитивні, i,jÎI;
(г) Ri-1 - транзитивне тоді і тільки тоді, коли Ri транзитивне.
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. Побудувати відношення
(а) симетричне, транзитивне, нерефлексивне;
(б) рефлексивне, симетричне, нетранзитивне;
(в) рефлексивне, антисиметричне, нетранзитивне;
(г) рефлексивне, симетричне, транзитивне;
(д) рефлексивне, несиметричне, транзитивне;
(е) антисиметричне, транзитивне, нерефлексивне;
(є) несиметричне, неантисиметричне;
(ж) нерефлексивне, неантирефлексивне, несиметричне, транзитивне.