Операції над відношеннями

Усі бінарні відношення є підмножина декартового добутку двох множин. Тому для відношень необхідно визначити операції: об’єднання, перетинання, вирахування, тощо.

Для визначення операцій над множинами використаємо відношення R₁, R₂, R₃

1. Об’єднання :

В цьому випадку “або” розуміються не в виключному сенсі, а як додаток одного до іншого.

2. Перетинання :

Результатом перетинання відношень є така пара елементів для яких вірно і відношення R₁, і відношення R_2.

3. Різниця:

4. Доповнення:

5. Зворотне відношення R^-1

тоді і тільки тоді, якщо

Приклад: R – бути сином, R^-1 – бути батьком,

R – бути боржником, R^-1 – бути кредитором

6 композиція: (згортання або добуток відношень) R_l°R₂

Нехай задані множини М₁, М₂, М₃ та відношення та . Складне відношення діє з М₁ в М₂ за допомогою R₁ , а потім з М₂ в М₃ за допомогою R₂, таким чином , якщоіснує таке , що та . На рис. 2.8 показані множини М₁, М₂, М₃ у них – зони визначення D(R_X), D(R₂) та зони визначення Q(R_X) та Q(R₂), що заштриховані в різних напрямках для R_l та R2. Сегменти з двійною штриховою на М₁, М₂, М₃ є D(R₁oR₂), Q(R₁)Ç D(R₂) та Q(R₁°R₂) відповідно. Зокрема, якщо відношення R визначено на множині М, , тоді складне відношення

Приклад 1.Якщо R – «бути сином», тоді R°R – «бути онуком».

Приклад 2. Нехай задано , , де N – множина натуральних чисел, причому та , тоді

Приклад 3. Також доцільно використовувати графи для завдання композиції відношень

, , тоді

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

Властивість	Визначення
рефлексивність	Бінарне відношення називається рефлексивним, якщо виконується для будь-якого
антирефлексивність	Бінарне відношення називається антирефлексивним, якщо для будь-якого виконується , тобто не виконується .
симетричність	Відношення називається симетричним, якщо для усіх , якщо тоді
антисиметричність	Відношення називається антисиметричними якщо для усіх з того, що і – істинне обов’язково .
транзитивність	Відношення називається транзитивним, якщо для усіх з того, що і – істина обов’язково також істина
нетранзитивність	Відношення називають нетранзитивними якщо для усіх з того що і – істина

Бінарне відношення називається рефлексивним, якщо виконується для будь-якого . Наприклад, “жити в одному місці”, “належати до однієї групи”

Бінарне відношення називається антирефлексивним, якщо для будь-якого виконується , тобто не виконується . Наприклад, “бути сином”, “бути меншим за зростом або за віком”

Відношення називається симетричним, якщо для усіх , якщо тоді (група). Наприклад, належати до однієї студентської групи.

Відношення називається антисиметричними якщо для усіх з того, що і – істинне обов’язково . Наприклад, “бути сином”, “бути начальником”

Відношення називається транзитивним, якщо для усіх з того, що і – істина обов’язково також істина. Наприклад, „бути молодшим за віком”

Відношення називають нетранзитивними якщо для усіх з того що і – істина . Наприклад,

Відношення називають еквівалентним, якщо воно рефлексивне, симетричне, та транзитивне. Наприклад, “бути родичем”, “бути студентом однієї групи”