1. Нехай M = {1,2,3,4,5}. Для заданого відношення R на множині M визначити Pr1 R, Pr2 R, 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 }
визначити Pr1 R, Pr2 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),(1,3),(2,3),(2,4),(3,1),(3,3),(4,1)},
R 2 = {(1,2),(1,3),(1,4),(2,2),(3,1),(3,4),(4,2)}.
Знайти відношення X на множині M (або довести, що таке відношення X не існує), для якого виконується
(а) R 1° X = R 2; (в) R 2° X = R 1; (д) (R 1° R 2)° X = R 1;
(б) X ° R 1 = R 2; (г) X ° R 2 = R 1; (е) (R 2° R 1)° X = R 1.
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 виконується
(а) Pr1 R = Æ Û R = Æ Û Pr2 R = Æ;
(б) Pr2 R = Pr1 R -1;
(в) Pr1 R = Pr2 R -1;
(г) Pr1 R = M Û iM Í R ° R -1;
(д) Pr2 R = M Û iM Í R -1° R.
9. Довести, що для будь-яких відношень виконується
(а) R È R = R Ç R = R; (д) (R 1 \ R 2)-1 = R 1-1 \ R 2-1;
(б) (R -1)-1 = R; (е) 
-1;
(в) (R 1È R 2)-1 = R 1-1È R 2-1; (є) (
Ri)-1 = Ri -1;
(г) (R 1Ç R 2)-1 = R 1-1Ç R 2-1; (ж) (
Ri)-1 = Ri -1.
10. Довести, що для довільних відношень виконується
(а) R 1° (R 2° R 3) = (R 1° R 2)° R 3;
(б) (R 1° R 2)-1 = R 2-1° R 1-1;
(в) ( Ri)° Q = (Ri ° Q);
(г) Q ° ( Ri) = (Q ° Ri);
(д) R 1° R 2 = Æ Û Pr2 R 1ÇPr1 R 2 = Æ.
11. Довести, що для довільних відношень Ri, i Î I та Q на множині M
(а) ( Ri)° Q Í (Ri ° Q); (б) Q ° ( Ri) Í (Q ° Ri)
і знак включення не можна замінити на знак рівності.
12. Навести приклад відношень R 1 і R 2 на множині M = {1,2,3} таких, що відношення R 1° R 2 і R 2° R 1 не збігаються.
13. Нехай R 1 і R 2 - відношення на множині M. Довести або спростувати таку рівність: 
= 1° 2.
14. Знайти всі відношення X на множині M такі, що для довільного відношення R на M виконується рівність R ° X = X ° R.
15. Нехай R - відношення на множині M. Довести, що R ° R 1= R 1° R = R 1 для довільного відношення R 1 на множині M тоді і тільки тоді, коли R = iM.
16. Довести, що співвідношення R ° H = H ° R = H виконується для довільного відношення R тоді і тільки тоді, коли H= Æ.
17. Для яких відношень виконується R -1 = ?
18. Довести, що коли R 1Í R 2, тоді для довільного відношення Q виконується
(а) Q ° R 1 Í Q ° R 2; (б) R 1° Q Í R 2° Q; (в) R 1-1Í R 2-1.
19. На множині M = {1,2,3,4} задано відношення
R 1 = {(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)};
R 2 = {(1,1),(2,2),(2,3),(2,4),(3,1),(3,3),(4,1),(4,4)};
R 3 = {(1,3),(1,4),(2,1),(1,2),(3,1),(3,3),(4,1)};
R 4 = {(1,1),(1,2),(1,4),(2,2),(2,4),(3,3),(3,4),(4,2),(4,3),(4,4)};
R 5 = {(1,2),(1,3),(2,3),(2,4),(4,1),(4,3)}.
Визначити, які з цих відношень є
(а) рефлексивними;
(б) антирефлексивними;
(в) симетричними;
(г) антисиметричними;
(д) транзитивними.
Побудувати графіки, графи та матриці заданих відношень.
20. Дайте інтерпретацію властивостей відношень за допомогою їхніх матриць, графіків і діаграм.
21. На множині Z задано відношення:
(m,n)Î R 1Û m-n парне число;
(m,n)Î R 2Û m+n парне число;
(m,n)Î R 3Û m-n £ 100;
(m,n)Î R 4Û m-n непарне число;
(m,n)Î R 5Û m+n непарне число;
(m,n)Î R 6Û m/n парне число;
(m,n)Î R 7Û m/n непарне число;
(m,n)Î R 8Û m* n парне число;
(m,n)Î R 9Û m* n непарне число;
(m,n)Î R 10Û m-n є степенем числа 2;
(m,n)Î R 11 Û m і n є взаємно простими;
(m,n)Î R 12 Û m £ n;
(m,n)Î R 13 Û m ділить n;
(m,n)Î R 14 Û m / n є степенем числа 2.
Визначити, які з цих відношень є
(а) рефлексивними;
(б) антирефлексивними;
(в) симетричними;
(г) антисиметричними;
(д) транзитивними;
(е) толерантними.
22. Нехай R 1 і R 2 - деякі відношення на скінченній множині M, а C 1 і C 2 матриці цих відношень. Визначити матрицю C для відношення
(а) R 1È R 2; (г) R 1D R 2; (є) 
;
(б) R 1Ç R 2; (д) R 1° R 2; (ж) iM È R 1;
(в) R 1\ R 2; (е) R 1-1; (з) R 1\ iM.
23. Довести, що для довільних рефлексивних відношень R 1 і R 2 відношення R 1È R 2, R 1Ç R 2, R 1-1 і R 1° R 2 будуть також рефлексивними.
24. Довести, що для довільного рефлексивного відношення R і для будь-якого k =0,1,2,... відношення R ( k ) є рефлексивним.
25. Довести, що для довільних рефлексивних відношень R 1 і R 2 виконується R 1È R 2Í R 1° R 2.
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. Довести, що коли відношення R 1 і R 2 антирефлексивні, тоді антирефлексивними є і відношення R 1È R 2, R 1Ç R 2, R 1-1.
32. Довести, що композиція R 1° R 2 двох антирефлексивних відношень R 1 і R 2 може не бути антирефлексивним відношенням.
33. Нехай Ri, i Î I - відношення на множині M. Довести або спростувати таке твердження:
(а) Ri - антирефлексивне тоді і тільки тоді, коли кожне Ri антирефлексивне, i Î I;
(б) Ri - антирефлексивне тоді і тільки тоді, коли кожне Ri антирефлексивне, i Î I;
(в) Ri ° Rj - антирефлексивне тоді і тільки тоді, коли Ri і Rj антирефлексивні, i, j Î I;
(г) Ri- 1 - антирефлексивне тоді і тільки тоді, коли Ri антирефлексивне.
34. Навести приклад двох антирефлексивних відношень R 1 і R 2 на множині M = {1,2,3}, композиція R 1° R 2 яких буде рефлексивним відношенням.
35. Довести, що для симетричних відношень R 1і R 2 будуть симетричними і відношення R 1È R 2, R 1Ç R 2, R 1-1, R 1° R 1-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 виконується Pr1 R =Pr2 R.
41. Спростувати таке твердження: якщо для деякого відношення R виконується Pr1 R = Pr2 R, то відношення R є симетричним.
42. Довести, що відношення R симетричне, тоді і тільки тоді, коли симетричним є відношення
(а) R -1; (б) 
.
43. Побудувати два симетричних відношення R 1 і R 2на множині M ={1,2,3,4}, композиція яких R 1° R 2не буде симетричним відношенням.
44. Нехай R 1 і R 2 - симетричні відношення на множині M. Довести, що коли R 1° R 2Í R 2° R 1, то R 1° R 2 = R 2° R 1.
45. Довести, що композиція R 1° R 2 симетричних відношень R 1 і R 2 є симетричним відношенням тоді і тільки тоді, коли R 1° R 2 = R 2° R 1.
46. Довести, що композиція R 1° R 2 симетричних відношень R 1 і R 2 є симетричним відношенням тоді і тільки тоді, коли R 2° R 1Í R 1° R 2.
47. Нехай Ri, i Î I - відношення на множині M. Довести або спростувати таке твердження:
(а) Ri - симетричне тоді і тільки тоді, коли кожне Ri симетричне, i Î I;
(б) Ri - симетричне тоді і тільки тоді, коли кожне Ri симетричне, i Î I;
(в) Ri ° Rj - симетричне тоді і тільки тоді, коли Ri і Rj симетричні, i, j Î I;
(г) Ri- 1 - симетричне тоді і тільки тоді, коли Ri симетричне.
28. Довести, що для антисиметричних відношень R 1 і R 2 відношення R 1Ç R 2 і R 1-1 будуть також антисиметричними.
48. Довести, що відношення R на множині M є антисиметричним тоді і тільки тоді, коли R Ç R -1Í iM.
49. Довести, що об’єднання R 1È R 2 антисиметричних відношень R 1 і R 2 на множині M буде антисиметричним відношенням тоді і тільки тоді, коли R 1Ç R 2-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. Навести приклад транзитивних відношень R 1 і R 2 на множині M ={1,2,3,4} таких, що
(а) R 1° R 2 - нетранзитивне; (г) R 1° R 1= R 1;
(б) R 1° R 2 - транзитивне; (д) R 1È R 2 - нетранзитивне;
(в) R 1° R 1¹ R 1; (е) R 1È R 2 - транзитивне.
59. Довести, що композиція R 1° R 2 транзитивних відношень R 1 і R 2 є транзитивним відношенням, якщо R 1° R 2 = R 2° R 1.
60. Довести, що об’єднання R 1È R 2 транзитивних відношень R 1 і R 2 буде транзитивним відношенням тоді і тільки тоді, коли R 1° R 2 È R 2° R 1 Í R 1È R 2.
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. Побудувати відношення
(а) симетричне, транзитивне, нерефлексивне;
(б) рефлексивне, симетричне, нетранзитивне;
(в) рефлексивне, антисиметричне, нетранзитивне;
(г) рефлексивне, симетричне, транзитивне;
(д) рефлексивне, несиметричне, транзитивне;
(е) антисиметричне, транзитивне, нерефлексивне;
(є) несиметричне, неантисиметричне;
(ж) нерефлексивне, неантирефлексивне, несиметричне, транзитивне.
