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

Так как бинарные отношения являются множествами, то к ним применимы все понятия, которые вводятся для множеств: понятие равенства, включения, а также операции пересечения, объединения и дополнения. В этом разделе мы будем считать, что все отношения заданы на одном и том же множестве X.

Пусть a и b - два бинарных отношения на множестве X. Каждому из них соответствует некоторое множество пар (подмножества и ).

Определение 2.1. Пересечением отношений a и b, заданных на множестве X, называется отношение такое, что:

Пример 2.1. Пересечением отношений "не меньше" и "не равно", определенных на множестве действительных чисел R, является отношение "строго больше":

.

Определение 2.2. Объединением отношений a и b, заданных на множестве X, называется отношение, такое, что:

является отношение "быть ребенком".

Определение 2.3. Разностью отношений a и b, заданных на множестве X, называется отношение a\b, такое, что:

Пример 2.3. Разностью отношений "не меньше" и "не больше" на R является отношение "больше":

.

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

Определение 2.4. Дополнением отношения a, определенного на множестве X, называется отношение, определяемое подмножеством пар из X x X, не входящих в:

x y .

Пример 2.5. Дополнением отношения "не меньше" на R является отношение "не меньше":

.

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

Кроме теоретико-множественных операций для отношений вводятся некоторые дополнительные операции, которые связаны с их специфической структурой. Мы рассмотрим две такие операции.

Определение 2.5. Если в каждой упорядоченной паре, принадлежащей отношению a, поменять местами первую и вторую компоненты, то получим новое отношение, которое называется обратным для отношения a и обозначается через a^-1:

.

Пример 2.6. Обратным для отношения "не меньше" на множестве действительных чисел R является отношение "меньше":

.

Пример 2.7. Обратным для отношения "быть родителем" на множестве людей является отношение "быть ребенком".

Граф отношения a^-1 получается из графа отношения переориентацией всех дуг (рис. 4).

(а) Отношение a (б) Отношение a^-1

Рис. 4. Графы отношений a и a^-1

Если отношение задано с помощью булевой матрицы, то, поменяв в ней местами строки и столбцы, получим булеву матрицу отношения a^-1 (рис 5).

(а) Матрица отношения a (б) Матрица отношения a^-1

Рис. 5. Матрицы отношений a и a^-1

Определение 2.6. Произведением или композицией отношений a и b, заданных на множестве X, называется отношение a°b, состоящее из таких кортежей (x, z), для которых существует элемент , удовлетворяющий условию и :

.

Пример 2.8. Произведением отношений "быть братом" и "быть отцом" является отношение "быть братом одного из родителей", т. е. "быть дядей".

Если отношения a и b на некотором множестве X заданы с помощью графов, то принадлежность пары (x, z) к отношению a °b означает, что из вершины x в вершину z можно попасть точно за два шага, причем первый из них делается по дуге отношения a, а второй - по дуге отношения b.

На рисунке 6 изображены графы, представляющие отношения a (точечные дуги) и b (пунктирные дуги), и графы, представляющие произведения отношений a°b и b°a.

(а) Графы отношений a и b (б) Граф отношения a°b

(в) Граф отношения a°b

Рис. 6. Пример произведения отношений (a°b b°a)

Пример, приведенный на рисунке 6, показывает, что для произведения отношений коммутативный закон не выполняется.

Для выражения матрицы произведения двух отношений a и b, заданных булевыми матрицами и , введем понятие "булево сложение" , определив его следующим образом:

0 0 = 0, 0 1 = 1, 1 0 = 1, 1 1 = 1.

Если теперь

M = (a_ij), M = (b_jk), (i, j, k = 1, 2, …, n),

то

M a°b = (c_ik),

где

c_ik = a_i1 b_1k … a_in b_nk

Матрица M a°b называется булевым произведением матриц M a и M b. Легко проверить, что M a°b является булевой матрицей произведения a°b.

Пример 2.9. Вычислим матрицы произведений a°b и b°a отношений a и b, представленных графами на рисунке 6.

Для этого перемножим соответствующие матрицы M a и M b (строки и столбцы матриц упорядочены в соответствии с алфавитным порядком букв a, b, c, d, обозначающих вершины графа).

Определим еще одну унарную операцию над отношением.

Определение 2.7. Транзитивным замыканием отношения a называется бинарное отношение такое, что x y тогда и только тогда, когда существует такая цепочка элементов из X:

z₀ = x, z₁, z₂,..., z_n = y,

что между соседями в этой цепочке выполнено отношение a:

z₀ a z₁, z₁ a z₂,..., z_n-1 a z_n.

Пример 2.10. На рисунке 7 изображены графы, представляющие отношение a и его транзитивное замыкание .

Рис. 7. Транзитивное замыкание отношения a

В матричной форме операция транзитивного замыкания отношения a выражается через объединение степеней матрицы M a отношения a:

В приведенной формуле объединение матриц понимается следующим образом:

.