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

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

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

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

Операции над отношениями - student2.ru

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

Операции над отношениями - student2.ru .

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

Операции над отношениями - student2.ru

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

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

Операции над отношениями - student2.ru

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

Операции над отношениями - student2.ru .

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

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

x Операции над отношениями - student2.ru y Операции над отношениями - student2.ru Операции над отношениями - student2.ru .

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

Операции над отношениями - student2.ru .

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

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

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

Операции над отношениями - student2.ru .

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

Операции над отношениями - student2.ru .

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

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

Операции над отношениями - student2.ru

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

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

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

Операции над отношениями - student2.ru Операции над отношениями - student2.ru

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

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

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

Операции над отношениями - student2.ru .

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

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

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

Операции над отношениями - student2.ru

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

Операции над отношениями - student2.ru

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

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

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

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

0 Операции над отношениями - student2.ru 0 = 0, 0 Операции над отношениями - student2.ru 1 = 1, 1 Операции над отношениями - student2.ru 0 = 1, 1 Операции над отношениями - student2.ru 1 = 1.

Если теперь

M = (aij), M = (bjk), (i, j, k = 1, 2 , …, n),

то

Ma°b = (cik),

где

cik = ai1 b1k Операции над отношениями - student2.ruОперации над отношениями - student2.ru ain bnk

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

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

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

Операции над отношениями - student2.ru

Операции над отношениями - student2.ru

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

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

z0 = x, z1, z2, ..., zn = y,

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

z0 az1, z1a z2, ..., zn-1 azn.

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

Операции над отношениями - student2.ru

Рис. 7. Транзитивное замыкание Операции над отношениями - student2.ru отношения a

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

Операции над отношениями - student2.ru

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

Операции над отношениями - student2.ru .

Наши рекомендации