Page 22 - 4570

21

Відношення SR можна ще знайти інакше, якщо записати відношення R та S
у вигляді підмножин відповідно декартових добутків A  B та B  C:
R = {(a 1, b 2), (a 1, b 4), (a 2, b 1), (a 2, b 3), (a 3, b 2), (a 3, b 3), (a 3, b 4), (a 5, b 1), (a 5, b 3)};
S = {(b 1, c 2), (b 1, c 3), (b 2, c 2), (b 3, c 2), (b 3, c 4), (b 4, c 1), (b 4, c 3)}.
Тоді
SR = (a 1, c 1), (a 1, c 2), (a 1, c 3), (a 2, c 2), (a 2, c 3), (a 3, c 1), (a 3, c 2), (a 3, c 3), (a 5, c 2), (a 5,
c 3).
У правильності відповіді переконаємося за допомогою задання відношення
стрілками:

Композицію двох відношень S та R можна знайти ще й у такий спосіб:
 b 1 b 2 b 3 b   a 1 a 2 a 3 a 4 a 5 
4
    

c
c
    ,c 2 c c 2       ,b b 3   , ,b b b 4   , ,b b b 4    ,b b 4 
4  
1
3
2
2
3
1
1
1
 
 S R x R   x

 a 1 a 2 a 3 a 4 a 5 
  

  ,c c 3   ,c c 3   , ,c c c 3    , ,c c c 3 
2
1
2
1
2
2
   x
SR
Отже,
SR = {(x, z)  A  C | якщо y  B, такий, що (x, y)  R та (y, z)  S}.
Перевіримо, чи виконується визначення (1.1), наприклад, для перерізу a =
a 1. У лівій частині формули дістанемо:
(SR)(a 1) = {c 1, c 2, c 3}.
Оскільки R(a 1) = {b 2, b 4}, то у правій частині формули (1.1) при a = a 1,
матимемо:
S(b 2, b 4) = S(b 2)  S(b 4) = {c 2}  {c 1, c 3} = { c 1, c 2, c 3}.
Ліва та права частини збігаються.
n-степенем відношення R на множині A називається його n-разова
композиція з самим собою, тобто:
n
R  R R  ... R .

n
2. Обернене відношення
Визначимо ще одну додаткову унарну операцію над відношеннями, яка не
має аналогів у загальному випадку серед теоретико-множинних операцій, що
розглядалися раніше. Це операція обернене відношення.