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

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

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

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

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

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

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

Пример 13.

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

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

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

Пример 14.

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