Операции над бинарными отношениями

Так как отношения на Х задаются подмножествами rНXґY, для них определимы те же операции, что и над множествами:

1. Объединение r1Иr2: r1Иr2={(х, у)| (х, у)Оr1 или (х, у)Оr2}.

2. Пересечение r1Зr2: r1Зr2={(х, у)| (х, у)Оr1 и (х, у)Оr2}.

3. Разность r1\r2: r1\r2={(х, у)| (х, у)Оr1 и (х, у)Пr2}.

4. Дополнение : '.

5. Обратное отношение r ^-1: х r ^-1 у тогда и только тогда, когда уrх, r ^-1={(x, y)| (y, x)Оr}.

Пример 13.

Если r - «быть моложе», то r ^-1 – «быть старше».

6. Составное отношение (композиция) r1 · r2. Пусть заданы множества М1, М2 и М3 и отношения R1 Н М1 ґ М2 и R2 Н М2 ґ М3. Составное отношение действует из М1 в М2 посредством R1, а затем из М2 в М3 посредством R2, то есть (a, b) О R1·R2, если существует такое с О М2, что (а, с) О R1 и (a, c) О R2.

7. Транзитивное замыкание r°. Транзитивное замыкание состоит из таких и только таких пар элементов а и b из М, то есть (a, b)Оr°, для которых в М существует цепочка из (k+2) элементов М, kі 0, что а, с1, с2, …ck, b, между соседними элементами которой выполняется r. Другими словами а r с1, с1 r с2, …, сk r b.

Пример 14. Для отношения «быть сыном» транзитивным замыканием является отношение «быть прямым потомком по мужской линии».