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

Бинарные отношения – это множества упорядоченных пар. Следовательно, над ними можно выполнять любые теоретико-множественные операции, в частности, операции объединения и пересечения. Определим еще две операции над отношениями.

Определение 2.7. Обратным к отношению P Í A ´ B (или инверсией) называется множество P ^–1, подмножество прямого произведения B ´ A такое, что P ^–1 = {(y, x) | (x, y) Î P }.

Пример 2.6. Пусть P = {(a, 1), (b, 2), (c, 3), (d, 4), (e, 5)}. Тогда
P ^–1 = {(1, a), (2, b), (3, c), (4, d), (5, e)}.

Определение 2.8. Композицией (или суперпозицией)отношений P Í A ´ B и Q Í B ´ C называется множество P Q = {(x, y) | x Î A, y Î C, ($ z Î B): (x, z) Î P, (z, y) Î Q }, рис. 2.4.

Пример 2.7. Если P = {(a, b), (b, c), (b, d), (a, d), (c, a)}, Q = {(b, d), (c, a), (d, c)}, то P Q = {(a, d), (b, a), (b, c), (a, c)} и Q P = {(c, b), (c, d), (d, a)}.

Утверждение 2.1. Для любых бинарных отношений P, Q и R выполняются следующие свойства:

1) (P ^–1)^–1 = Р;

2) (P Q)^–1 = Q ^–1 P ^–1;

3) (P Q) R = P (Q R).