48. Операции над бинарными отношениями

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

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

Отношение b содержится в отношении g (или отношение g включает отношение b), если каждая упорядоченная пара элементов (Ai, Bj) отношения b принадлежит и отношению g: b Ì g, если (Ai, Bj) Î b Þ (Ai, Bj) Î g.

Два отношения b и g равны, если каждое из них включает другое отношение: b = g, если b Ì g и g Ì b. Другими словами, отношения равны, если они состоят из одних и тех же упорядоченных пар элементов.

Операции объединения, пересечения, разности и дополнения над произвольными бинарными отношениями b и g вводятся так же, как операции над множествами, только при этом под X понимают упорядоченную пару элементов, принадлежащих бинарному отношению:

Объединение

B È g = {X | X Î b Ú X Î g};

Пересечение

B Ç g = {X | X Î b & X Î g};

Разность

B \ g = {X | X Î b & X Ï g};

Дополнение

= {X | X Ï b}.

Таким образом, объединение бинарных отношений b, g подразумевает новое отношение, которое состоит из всех упорядоченных пар элементов, принадлежащих хотя бы одному из бинарных отношений. Пересечение бинарных отношений предполагает, что новое отношение состоит только из тех упорядоченных пар, которые принадлежат обоим отношениям. Разность бинарных отношений r = b \ g состоит из тех элементов отношения b, которые не являются элементами отношения g. Операция дополнения подразумевает наличие некоторого универсума U. Если b является бинарным отношением, введенным между элементами множеств C и D, то в качестве универсума обычно берут декартово произведение этих множеств: U = C × D, и дополнением к бинарному отношению b называют разность C × D \ b.

Операции пересечения и объединения бинарных отношений допускают обобщение на пересечение и объединение произвольных семейств отношений. Пусть J – некоторое множество элементов, которые используются в качестве индексов для обозначения элементов семейства бинарных отношений (bJ)JÎJ и пусть для каждого J Î J бинарное отношение bJ Известно. Тогда

.

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

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

Умножение отношений. Пусть A, B, C – множества, b1 и b2 – отношения, соответственно, из A в B и из C В B, b1 Ì A × B и b2 Ì B × C. Умножением или композицией отношений b1 и b2 называется отношение g = b1 × b2, g Ì A × C определяемое следующим образом:

G = {(A, C) | A Î A & C Î C & $ B Î B, A B1 B & B B2 C},

Т. е. для любой упорядоченной пары элементов (A, C) нового отношения g существуют упорядоченные пары элементов (A, B) и (B, C) соответственно в отношениях b1 и b2. Таким образом, произведение отношений b1 × b2 порождается парами элементов, у которых второй элемент первой упорядоченной пары, принадлежащей первому отношению b1, одновременно является первым элементом упорядоченной пары второго отношения b2. Рассматриваемые пары элементов вида (A, B) и (B, C) соответственно отношений b1 и b2 называют примыкающими. Произведением двух примыкающих пар (A, B) и (B, C) называется упорядоченная пара (A, C).

Из определения произведения двух бинарных отношений следует, что операция умножения двух бинарных отношений в общем случае не коммутативна, однако ассоциативна, т. е. для любых трех бинарных отношений a, b, g выполняется равенство a×(b × g) = (a × b) × g.

Если произведение бинарных отношений содержит N сомножителей и они все равны, например, b, то это приводит к N-кратному произведению отношения b на самого себя или N-кратной степени bN отношения b.

Обращение отношений. Эта операция в каждой упорядоченной паре отношения b меняет местами первый и второй элемент. При этом получается новое бинарное отношение, которое обозначают b–1 и называют обратным отношению b. Если бинарное отношение b задано ориентированным графом, то обратное отношение b–1 получается переориентацией всех ребер графа на противоположное направление.

< Предыдущая		Следующая >