1.07 Представление отношения
Конечное отношение можно представить в виде прямоугольной матрицы. Ее столбцы соответствуют первым координатам, а строки – вторым координатам. На пересечении I-го столбца и J-й строки ставится 1, если выполнено отношение Xi А Yj. Если отношение не выполнено, то в соответствующей клетке ставится 0, либо она остается пустой. Такая матрица содержит всю информацию об отношении А.
Пример: Х = { 2; 3 }; Y = { 3; 4; 5; 6}.
А) Пусть А – «делить нацело». Тогда A = {(2; 4), (2; 6), (3; 3), (3; 6)}.
A = {(Х1; у2), (Х1; у4), (Х2; у1), (Х2; у4)}.
|
Xi Yj |
X1 |
X2 |
|
Y1 |
1 | |
|
Y2 |
1 | |
|
Y3 | ||
|
Y4 |
1 |
1 |
Б) Пусть А – отношение «равно». Тогда А={(3; 3)}. А={(Х2; у1)}.
|
Xi Yj |
X1 |
X2 |
|
Y1 |
1 | |
|
Y2 | ||
|
Y3 | ||
|
Y4 |
В) Пусть А – отношение «больше». Таких пар нет. Матрица отношения состоит из нулей (или пустых клеток).
Ненулевые элементы I-го столбца, представляющие собой элементы YkÎY, для которых выполняется отношение А называются сечением по Xi Отношения А. Обозначается сечение
А(Х1) = {У1; у2; у4}; А(Х1) = {У2; у5}; А(Х1) = {У3; у5}.
|
Xi Yj |
X1 |
X2 |
X3 |
|
Y1 |
1 | ||
|
Y2 |
1 |
1 | |
|
Y3 |
1 | ||
|
Y4 |
1 | ||
|
Y5 |
1 |
1 |
Множество всех сечений отношения А называют Фактор – мноЖеством множества Y по отношению А. Оно обозначается YА:
YА = {(У1; у2; у4), (У2; у5), (У3; у5)}.
Если ВÌХ есть некоторое подмножество с элементами В = {ХK, хM, хN}, то сечением А по В является объединение сечений отношения А по элементам ХK, хM, хN:
А(В) = 
(Х), т. е. А(ХK, хM, хN) = А(ХK) 
А(ХM) А(ХN).
Для нашего Примера: А(Х1, х2, х3) = А(Х1) А(Х2) А(Х3) = (У1; у2; у4) (У2; у5) (У3; у5) = { У1; у2; у3; у4; у5 }.
· Если матрица отношения А состоит из одних единиц, то такое отношение называется Полным. Сечения А по всем Xi Î Х в этом случае одинаковы и тождественно равны множеству Y.
· Если матрица отношения А состоит из одних нулей, то такое отношение называется Пустым.
· Если матрица отношения А является квадратной и все элементы, кроме элементов главной диагонали, нулевые, то такое отношение называется Тождественным. В этом случае Xi А Yj выполняется, только если I=J. Все сечения по Xi состоят из одного элемента Yj :
А(Xi) = {Yj}, где: I = 1, 2, ... , 6.
|
Xi Yj |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
|
Y1 |
1 | |||||
|
Y2 |
1 | |||||
|
Y3 |
1 | |||||
|
Y4 |
1 | |||||
|
Y5 |
1 | |||||
|
Y6 |
1 |
| < Предыдущая | Следующая > |
|---|
