Page 40 - 2589

Композиція відношень. Нехай дано три множини X, У, Z та
два відношення A  X  Y , B  Y  Z . Композиція відношень A і

B є відношенням С, що складається з усіх тих пар  xy,  X  Z ,

Y
для яких існує таке y , що  yx,  A і  yx,  B .
Композицію відношень позначається символом «». Тоді
формалізований запис визначення композиції відношень має

вигляд:
B  A  C    x, z  X  Z : y  Y   x, y  A  zy,  B .

Можна легко показати, що переріз відношення C за x
збігається з перерізом відношення B за підмножиною  xA  Y ,

тобто   BxC  A  x .
Властивості композиції:
- B  A  A B , – не виконується закон комутативності;

-D  B  A  D  B  A  D  B  A, – виконується закон
асоціативності;

1


1
1 
- B  A   A  B .

Приклад 3.8: Нехай на множинах X   ,xx , x , xx  і
1 2 3 4 5
Y   , yy , y , y  задані відношення A і B:
1 2 3 4
A    x ,y   ,, x y   ,, x y   ,, x y   ,, x y   ,, x y   ,, x y   ,, x y ,
1 1 1 3 2 1 2 3 3 1 3 2 3 4 5 2
 , yx   ,, x y   ,, x y   ,, x y   ,, x y ,
4 3 5 4 5 2 4 3 5 4
B    , zy   ,, y z   ,, y z   ,, y z   ,, y z ,
1 2 2 1 2 2 3 3 4 3
тоді:
- композиція відношень A з B :
C  B  A    x ,z   ,, x z   ,, , x z   ,, , x z   ,, , x z   ,, , x z   ,, , x z , ,
1 2 1 3 2 2 2 3 3 1 3 2 3 3
 , zx   ,, , x   ,, , z x   ,, , z x z ;
4 3 5 1 5 2 5 3

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

Матриця композиції відношень C  B  A утворюється як
добуток матриць відношень B і A з подальшою заміною
відмінних від нуля елементів одиницями.

Приклад 3.9: Для композиції відношень A та B із прикладу
3.8 матриця композиції відношень C  B  A формується
наступним чином:

40