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

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

Определение 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 называется множество PQ = {(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)}, то PQ = {(a, d), (b, a), (b, c), (a, c)} и QP = {(c, b), (c, d), (d, a)}.

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

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

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

3. (PQ)R = P(QR).