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

Оскільки відношення є множиною, то усі операції для множин можна робити і над відношеннями.

Приклад 4.1. На декартовому добутку множин A ={1, 2, 3} та В ={1, 2, 3, 4} визначені відношення та з А в B:

R₁ ={(1,1), (2,2), (3,3)}, ₂={(1,1), (1,2), (1,3), (1,4)}.

Тоді

={(1,1), (1,2), (1,3), (1,4), (2,2), (3,3)},

={(1,1)},

\ {(2,2), (3,3)},

\ ={(1,2), (1,3), (1,4)}. ▲

Якщо відношення A і B задані булевою матрицею, то для того, щоб знайти булеву матрицю об’єднання чи перетину цих відношень, необхідно знайти диз'юнкцію чи кон’юнкцію булевих матриць A і B.

,

.

Означення 4.1. Диз'юнкція булевих mхn матриць Р та Q – це mхn матриця Z = Р Q, елементи якої , де i =1,..., m, j=1,..., n.

Кон'юнкція булевих mхn матриць Р та Q – це mхn матриця Z = Р Q, елементи якої , де i=1,…,m, j=1,…,n.

Для бінарних відношень існує особлива операція, якої не визначено для множин – композиція.

Означення 4.2. Нехай – відношення із множини А в множину В, а S – відношення із множини B в множину С. Композицією відношень та S називають відношення, яке складається зі всеможливих упорядкованих пар (а, с), де а А, с С, і для яких існує елемент b В такий, що (а, b) , (b, с) S. Композицію відношень та S позначають через S .

Приклад 4.2. Знайдемо композицію відношень та S, де –відношення із множини А ={1, 2, 3} в множину В ={1, 2, 3, 4}: R ={(1,1), (1,4), (2,3), (3,1), (3,4)};

S – відношення із множини В в множину С ={0, 1, 2}:

S ={(1,0), (2,0), (3,1), (3,2), (4,1)}.

Композицію S будують, використовуючи всі впорядковані пари з та з S такі, що другий елемент пари з збігається з першим елементом пари з S. Наприклад, пари (2,3) та (3,1) S породжують пару (2,1) S . Виконуючи описані дії, отримаємо:

S ={(1,0), (1,1), (2,1), (2,2), (3,0), (3,1)}. ▲

Нехай – відношення на множині А. Степінь , n =1, 2, 3..., визначають індуктивнo:

, .

Отже, зокрема

, .

Приклад 4.3. Нехай на множині А ={1, 2, 3, 4} задано відношення ={(1,1), (2,1), (3,2), (4,3)}. Знайдемо , n =2,3,4,5. За означенням послідовно отримаємо:

{(1,1), (2,1), (3,1), (4,2)},

{(1,1), (2,1), (3,1), (4,1)},

{(1,1), (2,1), (3,1), (4,1)},

. Можна переконатись, . ▲

Якщо відношення A і B задані булевою матрицею, то для того, щоб знайти булеву матрицю композиції цих відношень, необхідно знайти булевий добуток булевих матриць A і B.

Означення 4.3. Нехай Р – mхn матриця, Q – kxn матриця. Тоді булевий добуток – це mхn матриця Z =[ ], i=1,…,m, j=1,…,n, де

, або .Булевий добуток матриць асоціативний.

Булевий степінь для булевих m х n матриць (позначають через , r – натуральне) визначають так:

За означенням покладають , де – одинична m х n матриця. Операції над відношеннями легко виразити через матриці, які ці відношення задають:

,

.

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

Означення 4.4. Нехай відношення задано на множині A. Транзитивним замиканням ^* називається таке відношення, що складається з кортежів (x,y), для яких виконується: або кортеж (x,y) , або знаходиться скінченна послідовність елементів , така, що всі кортежі належать відношенню R. Очевидно, що .

Приклад 4.4. Нехай визначена множина людей {Ігор, Павло, Марія, Олена, Оксана}, і відомі такі факти:

Ігор є нащадком Павла,

Марія є нащадком Павла,

Олена є нащадком Марії,

Оксана є нащадком Олени,

Володя є нащадком Ігора.

Цю інформацію можна подати у вигляді відношення : “Є нащадком”.

Тоді факти можна представити таким чином: Ігор Павло, Марія Павло,Олена Марія, Оксана Олена.

Знайдемо транзитивне замикання відношення ^*.

R^* ={(Ігор, Павло), (Марія, Павло), (Олена, Марія), (Оксана, Олена), (Олена, Павло), (Оксана, Павло) }.▲