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

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

Будемо говорити, що відношення строго включено у , якщо й . Рівність відношень реалізується так само як і рівність множин.

Для матричного задавання відношень буде вірним таке правило: якщо , то , .

П р и к л а д 2.3. – відношення «» на множині дійсних чисел, – відношення «<» на множині дійсних чисел. Тоді .

О з н а ч е н н я 2.5. Відношення називається доповненням відношення , тоді і тільки тоді, коли воно виконується лише для тих пар елементів, для яких не виконується відношення .

Очевидно, що

. (2.3)

Тому у матричному запису , .

У графі присутні ті й тільки ті дуги, які відсутні у графі .

Для розрізів відношення справедливо: , .

П р и к л а д 2.4. Нехай R – відношення «» на множині дійсних чисел, тоді – відношення «<» на множині дійсних чисел.

О з н а ч е н н я 2.6. Перерізом відношення та (записується ) називається відношення, яке визначено перерізом відповідних підмножин з .

В матричному записі це означає, що

, .

О з н а ч е н н я 2.7. Об’єднанням відношень та (позначається ) називається відношення, що визначено об’єднанням відповідних підмножин з .

В матричному записі це можна записати, як

, .

О з н а ч е н н я 2.8. Зворотним до відношення називається відношення , яке визначається такою умовою:

. (2.4)

Для матриць відношень та буде мати місце

П р и к л а д 2.5. Нехай R – відношення «» на множині дійсних чисел. Тоді – відношення «» на множині дійсних чисел.

П р и к л а д 2.6. Нехай відношення R на множині задано матрицею:

Побудувати відповідні йому зворотне відношення та доповнення.

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

Згідно означення 2.5. Для доповнення відношення R маємо:

Зворотне відношення будуємо за означенням 2.8:

О з н а ч е н н я 2.9. Добутком (або композицією)відношень та (позначається ) називається відношення, яке визначається за правилом:

, якщо існує елемент , такий що та .

П р и к л а д 2.7. – відношення «менше», – відношення «більше», та подані на W. Пара чисел , якщо існує z такий, що та , тобто – це повне відношення на W (таке, яким пов’язані усі елементи множини W).

П р и к л а д 2.8. Нехай на множині подано два відношення та .

Визначити їх композицію.

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

Згідно означення 2.9 , якщо існує , такий що та . У матричному записі це означає, що

,

де п порядок матриці.

Тобто композиція відношень обчислюється як максимінний добуток відповідних їм матриць.

Тоді маємо:

О з н а ч е н н я 2.10. Відношення називається звуженням відношення на множину W, якщо та Звуження відношення на множину називають також відношенням на множині .

П р и к л а д 2.9. Відношення «>» на множині натуральних чисел є звуженням відношення «>» на множині дійсних чисел.