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

О з н а ч е н н я 2.11. Відношення R називається рефлексивним, якщо для будь-якого .

Відношення «бути схожими», «бути не старшим» є рефлексивними, «бути братом», «бути старшим» – не рефлексивні.

В матриці рефлексивного відношення на головній діагоналі знаходяться одиниці, тобто матриця така, що якщо . Граф рефлексивного відношення обов’язково має петлі у вершинах. Для верхнього й нижнього розрізів справедливо , для всіх x Î W.

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

В матриці антирефлексивного відношення на головній діагоналі знаходяться нулі, тобто якщо . Граф рефлексивного відношення не має петель у вершинах, і верхні та нижні розрізи задовольняють умові , для всіх x Î W.

Прикладами антирефлексивних відношень будуть відношення «більше», «менше», «бути старшим».

О з н а ч е н н я 2.13. Відношення R називається симетричним, якщо .

Матриця симетричного відношення симетрична, тобто для всіх i, j. У графі всі дуги парні. Для розрізів має місце рівність для всіх x Î W.

Симетричними є відношення рівності, «бути схожим», «вчитися в одній групі».

О з н а ч е н н я 2.14. Відношення R називається асиметричним, якщо (тобто з двох виразів x R y та y R x хоча б один не вірний).

У матриці симетричного відношення для всіх i, j. Тобто з двох симетричних елементів і хоча б один обов’язково дорівнює 0.

Асиметричними, наприклад, є відношення «більше» та «менше».

Зауважимо, що антирефлексивність є обов’язковою умовою асиметричності.

О з н а ч е н н я 2.15. Відношення R називається антисиметричним, якщо x R y та y R x можуть бути вірні одночасно тоді і тільки тоді, коли x = y.

Для матриці антисиметричного відношення справедливо , якщо .

Прикладами антисиметричних відношень будуть відношення «більше або дорівнює», «не більше», «не гірше».

О з н а ч е н н я 2.16. Відношення R називається транзитивним, якщо (якщо з та випливає ).

Прикладами транзитивних відношень є відношення «більше або дорівнює», «менше», «бути старшим», «вчитися в одній групі».

Умова дає зручний спосіб перевірки транзитивності відношення. Якщо відношення задано матрицею для цього необхідно обчислити матрицю відношення (тобто піднести в квадрат матрицю вихідного відношення) і перевірити умову. Якщо для всіх i, j –­ відношення транзитивне. Якщо ж умову порушено хоча б для однієї пари індексів i, j –­ відношення не буде транзитивним.

О з н а ч е н н я 2.17. Відношення R називається ациклічним, якщо , тобто з ..., випливає, що .

Це означає, що граф такого відношення не містить циклів.

О з н а ч е н н я 2.18. Відношення R називається від’ємно транзитивним, якщо його доповнення транзитивне.

О з н а ч е н н я 2.19. Відношення R називається сильно транзитивним, якщо воно водночас транзитивне та від’ємно транзитивне.

Властивості ациклічності та транзитивності особливо важливі у теорії прийняття рішень, тому що вони виражають природні взаємозв’язки між об’єктами. Дійсно, якщо об’єкт х в деякому сенсі не гірше за об’єкт y, а об’єкт y в тому ж сенсіне гірше за об’єкт z, то природно чекати, що об’єкт x буде не гіршим за об’єкт z (транзитивність), і у всякому разі z не краще за x (ациклічність).

П р и к л а д 2.10. Визначити властивості даного відношення

Розв’язування

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

Для перевірки транзитивності даного відношення знайдемо добуток даного відношення на себе.

Оскільки , дане відношення не є транзитивним.