Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Поскольку бинарные отношения - это множества, для них определены рассмотренные выше операции над множествами (объединение, пересечение, разность, дополнение). Необходимо заметить:
а) для бинарного отношения 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}.
Граф транзитивно - рефлексивного замыкания отношения легко получить из графа транзитивного замыкания отношения добавлением в каждой вершине дуги-петли, которая связывает вершину саму с собой.
Дата публикования: 2014-12-08; Прочитано: 590 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!