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

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

Определение 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).

2.2. Свойства бинарных отношений

Пусть бинарное отношение Р задано на непустом множестве А, т. е. Р  А².

Определение 2.9. Бинарное отношение P на множестве А называется рефлексивным, если для любого элемента х из множества А пара (х, х)  Р.

Другими словами, отношение P рефлексивно тогда и только тогда, когда каждая вершина графа имеет петлю.

Примерами рефлексивных отношений являются отношение делимости на множестве целых чисел; отношение включения на булеане непустого множества; отношение быть одинаково направленными на множестве всех направленных лучей.

Пример 2.8. Выяснить обладает ли отношение R = {(m, n), (m, k), (m, m), (n, n), (k, n)}, заданный на множестве А = {m, n, k}, свойством рефлексивности.

Решение. Данное бинарное отношение R  А², не будет рефлескивным так как для k  A пара (k, k)  R.

Определение 2.10. Бинарное отношение P на множестве А называется антирефлексивным, если  х  А : (х, х)  Р.

Отношение антирефлексивно тогда и только тогда, когда ни одна вершина графа не имеет петли.

Например, отношение неравенства на некотором числовом множестве, отношение перпендикулярности на множестве всех прямых евклидовой плоскости являются антирефлексивными.

Пример 2.9. Выяснить обладает ли отношение R = {(x, y) | x, y  R : x + y = 2}, свойствами рефлексивности и антирефлексивности.

Решение. Имеем пара (1, 1)  R и (2, 2)  R, следовательно данное бинарное отношение R, не является рефлескивным и не является антирефлексивным.

Определение 2.11. Бинарное отношение P на множестве А называется симметричным, если  х, y  А из того что пара (х, y)  Р следует (y, x)  Р.

Отношение симметрично тогда и только тогда, когда всякий раз вместе с ребром (х, y) граф содержит ребро (y, x).

Примерами симметричных отношений являются отношение равенства на некотором числовом множестве, отношение параллельности на множестве всех прямых евклидовой плоскости, отношение перпендикулярности на множестве всех прямых евклидовой плоскости.

Пример 2.10. Выяснить обладает ли отношение R = {(1, 2), (1, 3), (1, 1), (2, 3), (3, 1)}, заданное на множестве А = {1, 2, 3}, свойством симметричности.

Решение. Данное бинарное отношение R  А², не будет симметричным так как для пары (2, 3)  R пара (3, 2)  R.

Определение 2.12. Бинарное отношение P на множестве А называется антисимметричным, если  х, y  А из того, что пара (х, y)  Р и (y, x)  Р следует что x = y.

Отношение антисимметрично тогда и только тогда, когда вместе с каждым ребром (х, y) граф не содержит ребро (y, x). Граф антисимметричного отношения может содержать петли.

Примерами антисимметричных отношений являются отношение меньше (<) на множестве действительных чисел, отношение включения на булеане непустого множества.

Замечание 2.1. Если отношение не является симметричным, то это не означает, что оно антисимметрично. Например, отношение R = {(a, b), (b, a), (a, c)} на множестве A = {a, b, c} не симметрично, поскольку (a, c)  R, а (c, a)  R, и не антисимметрично, так как (a, b)  R и (b, a)  R, но a  b. Диагональ непустого множества А (id_A) является примером симметричного и антисимметричного отношения. Вообще, любое подмножество id_A обладает одновременно свойствами симметричности и антисимметричности.

Определение 2.13. Бинарное отношение P на множестве А называется асимметричным, если  х, y А если пара (х, y)  Р, то (y, х)  Р.

Отношение асимметрично тогда и только тогда, когда если граф содержит ребро (х, y), то он не содержит ребра (y, x).

Примерами асимметричных отношений являются отношение быть меньше (<) на числовом множестве. Отношение параллельности (||) на множестве прямых плоскости не является асимметричным, так как если а || b, то b || a и оно является симметричным.

Определение 2.14. Бинарное отношение P на множестве А называется транзитивным, если  х, y, z  А из того, что пара (х, y)  Р и (y, z)  Р следует что (х, z)  Р.

Отношение транзитивно тогда и только тогда, когда вместе с каждой парой ребер (х, y) и (y, z) граф содержит ребро (х, z).

Например, отношение параллельности на множестве всех прямых евклидовой плоскости, отношение включения на булеане непустого множества являются транзитивными.

Утверждение 2.2. Пусть A ≠  и P  A². Тогда справедливы следующие соотношения:

1. P – рефлексивно  id_A  P;

2. P – антирефлексивно  P  id_A = ;

3. P – симметрично  P = P^–1;

4. P – антисимметрично  P  P^–1  id_A;

5. P – транзитивно  PP  P.