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

© 2011-2024 Контрольные работы по математике и другим предметам!