Page 24 - 4570

23

1. Бінарне відношення R на множині А називається рефлексивним, якщо
будь-який елемент цієї множини знаходиться у відношенні R з самим собою,
тобто (а, а)  R для всіх а  А (інакше aRa для всіх a  A).
2. Відношення R на множині А називається антирефлексивним, якщо з (а,
b)  R випливає а ≠ b (тобто ¬aRa, що є одне й те саме, що aRb ≠ bRa).
З визначення антирефлексивності випливає, що якщо умова
рефлексивності не виконується для жодного елементу з множини А, то
відношення R буде антирефлексивним.
Якщо умова рефлексивності виконується не для всіх елементів множини А,
то говорять, що відношення R є нерефлексивне.
3. Відношення R на множині А називається симетричним, якщо для
кожної пари елементів а та b, які належать до А, з того, що (а, b)  R, випливає
(b, а)  R (тобто для  a, b  A з aRb  bRa).
4. Бінарне відношення R на множині А називається антисиметричним,
якщо для всіх а та b, які належать до А, з належності (а, b) та (b, а) до
відношення R випливає а = b (тобто якщо aRb та bRa  a = b).
5. Бінарне відношення R на множині А називається транзитивним, якщо
для будь-яких трьох елементів а, b та с, які належать до множини А, з того, що
(а, b)  R та (b, с)  R, випливає, що (а, с)  R (тобто з того, що aRb та bRc 
aRc).
6. Бінарне відношення R на множині А називається повним, якщо для всіх
елементів а та b, які належать до А, або a = b, або (а, b)  R, або (b, а)  R
(тобто, або a = b, або aRb, або bRa).
Приклади 1.30:
1) відношення, яке позначене знаком « = »− рефлексивне;
2) відношення «бути сином» − антирефлексивне;
3) відношення «жити в одному місті» − симетричне;
4) відношення «бути начальником» − антисиметричне;
5) відношення «бути братом» − транзитивне.
Зауваження:
1. При задаванні відношення R (R  A  A) матрицею:
 відношення є рефлексивне, якщо всі елементи головної діагоналі
матриці дорівнюють 1 (тобто І  R);
 відношення є антирефлексивне, якщо немає жодної одиниці на
головній діагоналі (тобто R  I = );
 відношення є симетричне, якщо матриця є симетрична щодо
-1
головної діагоналі (тобто R = R );
 відношення є антисиметричне, якщо немає жодної пари одиниць
симетричної головної діагоналі (окрім одиниць на самій діагоналі)
-1
тобто R  R = I;
2. Транзитивність бінарного відношення R на множині А перевіряється
простим перебиранням всіх елементів множини А (на А повинно виконуватися
включення RR  R);
-1
3. Відношення є повне, якщо R  R  I = U.