2. Операции над отношениями
Так как бинарные отношения являются множествами, то к ним применимы все понятия, которые вводятся для множеств: понятие равенства, включения, а также операции пересечения, объединения и дополнения. В этом разделе мы будем считать, что все отношения заданы на одном и том же множестве X.
Пусть и - два бинарных отношения на множестве X. Каждому из них соответствует некоторое множество пар (подмножества и ).
Определение 2.1. Пересечением отношений и , заданных на множестве X, называется отношение такое, что:
Пример 2.1. Пересечением отношений "не меньше" и "не равно", определенных на множестве действительных чисел R, является отношение "строго больше":
.
Определение 2.2. Объединением отношений и , заданных на множестве X, называется отношение , такое, что:
является отношение "быть ребенком".
Определение 2.3. Разностью отношений и , заданных на множестве X, называется отношение \, такое, что:
Пример 2.3. Разностью отношений "не меньше" и "не больше" на R является отношение "больше":
.
Пример 2.4. Разностью отношений "быть ребенком" и "быть дочерью", определенных на множестве всех людей, является отношение "быть сыном".
Определение 2.4. Дополнением отношения , определенного на множестве X, называется отношение, определяемое подмножеством пар из XxX, не входящих в :
x y .
Пример 2.5. Дополнением отношения "не меньше" на R является отношение "не меньше":
.
Отметим, что приведенные выше определения являются просто перефразировками соответствующих определений для обычных множеств и все свойства теоретико-множественных операций пересечения, объединения и дополнения, имеющие место для произвольных множеств, выполняются и для отношений.
Кроме теоретико-множественных операций для отношений вводятся некоторые дополнительные операции, которые связаны с их специфической структурой. Мы рассмотрим две такие операции.
Определение 2.5. Если в каждой упорядоченной паре, принадлежащей отношению , поменять местами первую и вторую компоненты, то получим новое отношение, которое называется обратным для отношения и обозначается через -1:
.
Пример 2.6. Обратным для отношения "не меньше" на множестве действительных чисел R является отношение "меньше":
.
Пример 2.7. Обратным для отношения "быть родителем" на множестве людей является отношение "быть ребенком".
Граф отношения -1 получается из графа отношения переориентацией всех дуг (рис. 4).
(а) Отношение (б) Отношение -1
Рис. 4. Графы отношений и -1
Если отношение задано с помощью булевой матрицы, то, поменяв в ней местами строки и столбцы, получим булеву матрицу отношения -1 (рис 5).
(а) Матрица отношения (б) Матрица отношения -1
Рис. 5. Матрицы отношений и -1
Определение 2.6. Произведением или композицией отношений и , заданных на множестве X, называется отношение °, состоящее из таких кортежей (x, z), для которых существует элемент , удовлетворяющий условию и :
.
Пример 2.8. Произведением отношений "быть братом" и "быть отцом" является отношение "быть братом одного из родителей", т. е. "быть дядей".
Если отношения и на некотором множестве X заданы с помощью графов, то принадлежность пары (x, z) к отношению ° означает, что из вершины x в вершину z можно попасть точно за два шага, причем первый из них делается по дуге отношения , а второй - по дуге отношения .
На рисунке 6 изображены графы, представляющие отношения (точечные дуги) и b (пунктирные дуги), и графы, представляющие произведения отношений ° и °.
(а) Графы отношений и (б) Граф отношения °
(в) Граф отношения °
Рис. 6. Пример произведения отношений (°°)
Пример, приведенный на рисунке 6, показывает, что для произведения отношений коммутативный закон не выполняется.
Для выражения матрицы произведения двух отношений и , заданных булевыми матрицами и , введем понятие "булево сложение" , определив его следующим образом:
0 0 = 0, 0 1 = 1, 10 = 1, 11 = 1.
Если теперь
M = (aij), M = (bjk), (i, j, k = 1, 2 , …, n),
то
M° = (cik),
где
cik = ai1 b1k … ain bnk
Матрица M° называется булевым произведением матриц M и M. Легко проверить, что M° является булевой матрицей произведения °.
Пример 2.9. Вычислим матрицы произведений ° и ° отношений и , представленных графами на рисунке 6.
Для этого перемножим соответствующие матрицы M и M (строки и столбцы матриц упорядочены в соответствии с алфавитным порядком букв a, b, c, d, обозначающих вершины графа).
Определим еще одну унарную операцию над отношением.
Определение 2.7. Транзитивным замыканием отношения называется бинарное отношение такое, что xy тогда и только тогда, когда существует такая цепочка элементов изX:
z0 = x, z1, z2, ..., zn = y,
что между соседями в этой цепочке выполнено отношение :
z0 az1, z1a z2, ..., zn-1 azn.
Пример 2.10. На рисунке 7 изображены графы, представляющие отношение и его транзитивное замыкание .
Рис. 7. Транзитивное замыкание отношения
В матричной форме операция транзитивного замыкания отношения выражается через объединение степеней матрицы M отношения :
В приведенной формуле объединение матриц понимается следующим образом:
.