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

Поскольку бинарные отношения - это множества, для них определены рассмотренные выше операции над множествами (объединение, пересечение, разность, дополнение). Необходимо заметить:

а) для бинарного отношения R универсальным множеством W всегда будет квадрат несущего множества М т.е операция "дополнение R" всегда определена;

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

Операция "прямое произведение" при ее формальном применении двум отношениям в результате даст отношение арности 4. Естественно потребовать, чтобы при выполнении этой операции арность результата не изменялась. Это достигается применением свойства транзитивности при выполнении операции перемножения отношений.

Пример: Пусть на несущем множестве M={a,b,c,d} заданы два бинарных отношения: R={ab,ac,ad} и Q={ac,ad,cd}. Произведением этих

отношений будет также бинарное отношение S, элементы которого являются подмножеством элементов, полученных в результате формального перемножения множеств R и Q (из всего множества четырех символьных цепочек необходимо отобрать только те, у которых средние элементы одинаковы (при записи средние элементы опускаются):

S = R x Q = {accd,dccd} = {ad,dd}.

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

Операцию "прямое произведение отношений" для двух отношений можно выполнить графически (на графах перемножаемых отношений) по следующему алгоритму: если на графе первого отношения есть дуга, соединяющая пару вершин (x,y), а на графе второго - дуга, соединяющая вершины (y,z), то на графе результирующего отношения изобразить дугу, соединяющую вершины (x,z); продолжать до исчерпания всех вариантов.

Конечный результат перемножения не зависит от способа выполнения операции (аналитический или графический).

Через прямое произведение отношений можно определить степени одного отношения: Q x Q = Q^2; Q x Q x Q = Q^3 и т.д.

Транзитивным замыканием отношения Q (обозначается Q+) называют объединение всех целых степеней отношения Q. Такое определение транзитивного замыкания отношения не дает эффективного алгоритма его построения для заданного отношения (по определению - это бесконечный процесс).

Аналитически это можно записать как объединение степеней мно-

жества:Q+=Q U Q^2 U Q^3 U Q^4 U... Q^n... или Q+=U Q^i (i ї N).

Для практического построения транзитивного замыкания заданного отношения используют следующий алгоритм: на графе заданного отношения добавляют дуги с использованием свойства транзитивности; процесс добавления дуг заканчивается, если на построенном таким образом графе нельзя уже добавить ни одной дуги (добавленные на предыдущих шагах дуги также участвуют в построении).

Транзитивно-рефлексивное замыкание отношения Q (обозначается Q*) - это объединение нулевой степени отношения Q и транзитивного

замыкания отношения Q: Q* = Q^0 U Q+. Нулевая степень любого отношения, построенного на несущем множестве М={a,b,c,d} имеет вид:

{aa, bb, cc, dd}.

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