1.09 Композиция отношений
Пусть даны три множества: Х, Y и Z и два отношения: АÌХ
Y и ВÌYZ. Тогда Композиция отношений А и В есть отношение С, состоящее из всех тех пар (Х, Z)ÌXZ, для которых существует такой Y Î Y, что пары (Х, у) Î А и (У, Z) Î В.
Композицию С отношений А и В записывают в виде: С = В. А.
Если отношения А и В заданы соответствующими матрицами, то матрицу композиции С можно получить как произведение матриц отношений В и А, которое выполняется по обычному правилу умножения прямоугольных матриц с последующей заменой отличных от нуля элементов в результирующей матрице на единицы.
Пример: Пусть Х = {Х1; х2; х3}; Y = {У1; у2; у3; у4}; Z = {Z1; Z2; Z3; Z4; Z5}; отношения Х А у и У А Z заданы матрицами
|
Xi Yj |
X1 |
X2 |
X3 |
Xi Zj |
Y1 |
Y2 |
Y3 |
Y4 | |
|
Y1 |
1 |
Z1 |
1 |
1 | |||||
|
Y2 |
1 |
1 |
Z2 |
1 |
1 | ||||
|
Y3 |
1 |
Z3 |
1 |
1 | |||||
|
Y4 |
1 |
1 |
Z4 |
1 |
1 | ||||
|
Z5 |
1 |
1 |
1 |
Матрица А Матрица В
Найдем матрицу композиции С =B . А. Строка I матрицы В умножается на столбец J матрицы А, и результат записывается в клетку с номером Ij:
СIj = bi1 a1j + bi2 a2j + ... + bin amj .
|
0 |
1 |
1 |
0 | |||||||
|
1 |
1 |
0 |
0 |
1 |
0 |
0 | ||||
|
C = |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 | ||
|
1 |
0 |
1 |
0 |
0 |
1 |
0 | ||||
|
1 |
0 |
1 |
1 |
0 |
1 |
1 | ||||
|
B |
A |
В итоге имеем:
С11 = 0 1 + 1 1 + 1 0 + 0 0 = 1.
С12 = 0 1 + 1 0 + 1 1 + 0 1 = 1. первая строка С1
С13 = 0 0 + 1 1 + 1 0 + 0 1 = 1.
С21 = 1 1 + 1 1 + 0 0 + 0 0 = 2.
С22 = 1 0 + 1 0 + 0 1 + 0 1 = 0. вторая строка С1
С23 = 1 0 + 1 1 + 0 0 + 0 1 = 1.
С31 = 0 1 + 1 1 + 0 0 + 1 0 = 1.
С32 = 0 0 + 1 0 + 0 1 + 1 1 = 1. третья строка С1
С33 = 0 0 + 1 1 + 0 0 + 1 1 = 2.
С41 = 1 1 + 0 1 + 1 0 + 0 0 = 1.
С42 = 1 0 + 0 0 + 1 1 + 0 1 = 1. четвертая строка С1
С43 = 1 0 + 0 1 + 1 0 + 0 1 = 0.
С51 = 1 1 + 0 1 + 1 0 + 1 0 = 1.
С52 = 1 0 + 0 0 + 1 1 + 1 1 = 2. пятая строка С1
С53 = 1 0 + 0 1 + 1 0 + 1 1 = 1.
В результате получили матрицу С1 (5 3) вида:
|
1 |
1 |
1 | |
|
2 |
0 |
1 | |
|
С1 = |
1 |
1 |
2 |
|
1 |
1 |
0 | |
|
1 |
2 |
1 |
Заменяем двойки на единицы и получаем матрицу композиции С отношений А и В :
|
1 |
1 |
1 | |
|
1 |
0 |
1 | |
|
С = |
1 |
1 |
1 |
|
1 |
1 |
0 | |
|
1 |
1 |
1 |
Итак, имеем результирующую матрицу:
|
Xi Zj |
X1 |
X2 |
X3 |
|
Z1 |
1 |
1 |
1 |
|
Z2 |
1 |
1 | |
|
Z3 |
1 |
1 |
1 |
|
Z4 |
1 |
1 | |
|
Z5 |
1 |
1 |
1 |
Исследуя эту матрицу, можно заметить, что Сечения отношения С по Xi Совпадают с сечениями отношения В По подмножеству А(Xi) Ì Y, т. е. С (Xi) = В(А(Xi)).
· С (X1) = {Z1; Z2; Z3; Z4; Z5 } = В(А(X1)).
А(X1) = {У1; у2};
С (X1) = В(У1; у2) = В(У1)
В(У2)
В(У1) = {Z2; Z4; Z5}; В(У2) = {Z1; Z2; Z3}.
Объединение В(У1)В(У2) = В(У1; у2) = С (X1) = {Z1; Z2; Z3; Z4; Z5}.
· С (X2) = {Z1; Z3; Z4; Z5} = В(А(X2)).
А(X2) = {У3; у4};
С (X2) = В(У3; у4) = В(У3) В(У4);
В(у3) = {Z1; Z4; Z5}; В(У4) = {Z3; Z5}.
С (X2) = В(У3; у4) = {Z1; Z3; Z4; Z5 }.
· С (X3) = {Z1; Z2; Z3; Z5 } = В(А(X3)).
А(X3) = {У2; у4};
С (X3) = В(У2; у4) = В(У2) В(У4);
В(У2) = {Z1; Z2; Z3}; В(У4) = {Z3; Z5}.
С (X3) = В(У2; у4) = {Z1; Z2; Z3; Z5}.
| < Предыдущая | Следующая > |
|---|
