Отношения

Отношения – один из способов задания взаимосвязей между элементами множеств. Чаще всего используются унарные и бинарные отношения.

Унарные (одноместные) отношения отражают наличие какого–то определенного признака R (свойства и т.п.) у элементов множества М (например, "быть четным" на множестве натуральных чисел). Тогда все такие элементы а из множества М,которые отличаются данным признаком R,образуют некоторое подмножество в М, называемое унарным отношением R,т.е. и .

Бинарные (двухместные) отношения используются для определения каких–то взаимосвязей между парами элементов множества М (так, на множестве людей могут быть заданы, например, следующие бинарные отношения: "жить в одном городе", "быть моложе", "быть сыном", "работать в одной организации" и т.п.). Тогда все пары (а, b)элементов из М,между которыми имеет место данное отношение R,образуют подмножество пар из множества всех возможных пар элементов = М ²,называемое бинарным отношением R,т.е. ,при этом .

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

Вот пример тернарного отношения “образовывать сумму” x + y = z и отношения для четверок –“находиться в отношении пропорциональности” x / y = z / v.

Под п–местным отношением понимают подмножество R прямого произведения п множеств: .

Говорят, что элементы а ₁, а ₂,..., а_n находятся в отношении R,если

Если n –местное отношение R задано на множестве М, т.е.

M ₁ = M ₂ =…= M_n = М, то

Рассмотрим детально бинарные отношения.

Итак, двухместным, или бинарным,отношением R называется подмножество пар прямого произведения ,т.е. . При этом по аналогии с соответствиями множество М ₁называют областью отправления отношения R,множество М ₂ – областью прибытия. Часто рассматривают отношения R между парами элементов одного и того же множества М,тогда . Если а и b находятся в отношении R, это записывается как аRb.

С отношениями связаны еще два понятия:

1) область определения D (R) и

2) область значений Q (R),

Эти понятия определяются соответственно, как и .

На рис. 6.1 приведен условный пример отношения .

Рисунок 6.1 – Пример отношения R

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

Отношения, определенные на конечных множествах, обычно задаются списком (перечислением) пар,для которых это отношение выполняется. Например, R = {(а, b), (а, с), (b, d)}.

Кроме такого представления, заимствованного у множеств, для отношений применяют также представление в виде матриц и графов.

Бинарному отношению ,где M = { а ₁, а ₂,..., а_п }, соответствует квадратная матрица порядка п,в которой элемент c_ij, стоящий на пересечении i– ойстроки и j –ого столбца, равен 1, если между элементами a_i и а_j имеет место отношение R,или 0, если оно отсутствует:

Если ,где M ₁= { а ₁, а ₂,..., а_п }, M ₂= { b ₁, b ₂,..., b_m }, то матрица получается прямоугольной с n строками и m столбцами.

бинарному отношению ,где M = { а ₁, а ₂,..., а_п },соответствует ориентированный граф (орграф), вершины которого взаимно однозначно соответствуют элементам множества М,а дуги соответствуют отношениям между элементами множества М. Например, дуга, соединяющая пару элементов а_i и а_j внаправлении от а_i к а_j,показываетналичие отношения а_iRа_j.

Если , где M ₁= { а ₁, а ₂,..., а_п }, M ₂= { b ₁, b ₂,..., b_m }, то граф получается двудольный (см. [16]): одна доля – множество вершин M ₁, другая доля – множество вершин M ₂, а дуги соответствуют отношениям а_iRb_j.

Введем следующие понятия:

Пустое отношение – отношение, которое не выполняется ни для одной пары элементов множества М. Обозначается это отношение символом .

Матрица этого отношения содержит только 0, а граф состоит только из вершин (нуль граф).

Полное отношение – отношение, которое выполняется для любой пары элементов множества М. Обозначается оно U = .

Матрица этого отношения содержит только 1. В графе этого отношения каждая вершина соединена дугой с каждой вершиной, включая ее самою (полный граф).

Диагональное отношение E (оно же тождественное отношение, оно же отношение равенства) – отношение aEb, которое выполняется только, если a и b это один и тот же элемент.

В матрице этого отношения элементы, расположенные на главной диагонали, равны 1, а остальные элементы равны 0. В графе этого отношения, кроме петель при каждой вершине, других дуг нет.

Так как отношения задаются подмножествами (или ,если М ₁= М ₂= М), то для них определимы те же операции, что и над множествами. Разберём эти операции более подробно.

Объединение :

или .

Отношение выполнено, если выполнено хотя бы одно из отношений и .

Определим объединение R ₁ и R ₂

{(1,2), (1,4), (2,1), (2,3), (2,4), (3,4), (4,1), (4,3), (4,4)};

Пересечение :

и .

Отношение выполнено, если одновременно выполнены отношения и .

Для отношений примера 1 находим

{(2,3), (2,4), (4,4)};

Дополнение : Дополнение множества R до полного множества U – это множество таких пар, что и , или множество пар U без множества пар R:

=U \ R,где U = M ₁ х М ₂ (или U = M ²).

В нашем случае

{(1,1), (1,3), (1,4), (2,1), (2,2), (3,1), (3,2), (3,3), (4,2), (4,3)};

{(1,1), (1,2), (1,3), (1,4), (2,2), (3,1), (3,2), (3,3), (3,4), (4,1), (4,2)}.

Разность R ₁\ R ₂:

R ₁\ R ₂= и ,

т.е. множество пар R ₁ без множества пар R ₂.

Для отношений примера 1 получаем

R ₁\ R ₂ = {(1,2), (1,4), (3,4), (4,1)}.

Симметрическая разность

R ₁ R ₂ = или , но }.

Это множество пар, принадлежащих или R ₁ или R ₂, но не принадлежащих R ₁ и R ₂ одновременно.

В нашем случае R ₁ R ₂ = {(1,2), (1,4), (2,1), (3,4), (4,1), (4,3)}.

Кроме этих операций, заимствованных у множеств, над отношениями определяют такие операции:

Обратное отношение R ^–1:

R ^–1 = .

Отношение bR ^–1 a выполняется тогда и только тогда, когда выполняется aRb.

Составное отношение (композиция, произведение) R ₁○ R ₂ (применяют и такое обозначение R ₁ R ₂).

Пусть заданы множества М ₁, М ₂, М ₃и отношения и . Составное отношение действует из М ₁в М ₂посредством R ₁, а затем из М ₂в М ₃посредством R ₂,т.е. R _l○ R ₂,если существует такое с М ₂, что (а, с) R ₁и (с, b) R ₂. На рис. 6.4 показаны множества М ₁, М ₂, М ₃, в них – области определений D (R ₁), D (R ₂) и области значений Q (R ₁)и Q (R ₂), заштрихованные в разных направлениях для R ₁и R ₂.Сегменты с двойной штриховкой на М ₁, М ₂, М ₃представляют собой D (R ₁○ R ₂), и Q (R ₁○ R ₂) соответственно.

Рисунок 6.4 – Пример, поясняющий формирование

составного отношения

В частности, если отношение R определено на множестве М, R М ², то составное отношение R ○ R= {(a, b):(a, c),(c, b) R }.

Например, если R – "быть сыном", то R ○ R – "быть внуком".

Прямое транзитивное замыкание R° состоит из таких и только таких пар элементов а, b из М,т.е. (a, b) R°,длякоторых в M существует цепочка из (k+ 2)элементов М, k 0: а, с ₁, с ₂,..., с_k, b,между соседними элементами которой выполняется отношение R: aRc ₁, c ₁ Rc ₂,..., c_kRb,т.е. R° = {(a, b): (a, c ₁),(c ₁, c ₂),...,(с_k, b) R }

Это правило справедливо, если цепочка состоит и из двух элементов. Следовательно, если выполнено aRb, то выполнено и aR°b, поэтому можно записать .

Если цепочка состоит из трех элементов, то можно записать aRс и сRb или aRRb, если цепочка состоит из четырех элементов, то aRRRb. Продолжая, можно заключить, что aR°b выполняется, если выполнено хотя бы одно отношение вида aRR… Rb. Этот факт можно записать формально в виде объединения степеней отношения R:

R° =

Например, для отношения R – "быть сыном" составное отношение (композиция) R ○ R = R ² – "быть внуком", R ○ R ○ R = R ³ – "быть правнуком" и т.д. Тогда объединение всех этих отношений есть транзитивное замыкание R° – "быть прямым потомком".

Степени отношения R определяются так же, как и R ○ R = R ² с учетом того, что Rⁿ = R^{n –1}○ R.

Аналогично может быть определено обратное транзитивное замыкание:

R^–° = {(d, a): (d, e_k),(e_{k -1}, e_{k- 2}),...,(e ₁, a) R ^-1}

R^–° =

Например, для отношения R ^–1 – "быть сыном" составное отношение (композиция) R ^–1○ R ^–1= R^{– 2} – "быть отцом", R ^–1○ R ^–1○ R ^–1= R^{– 3} – "быть дедушкой" и т.д. Тогда объединение всех этих отношений есть обратное транзитивное замыкание R^–° – "быть прямым предком (по мужской линии)".

Рефлексивное замыкание R*. Пусть тождественное отношение Е= {(а, а): а М }. Тогда R* = R° E.

Это прямое рефлексивное замыкание. Если вместо прямого транзитивного замыкания R ° использовать обратное транзитивное замыкание R ^–°, то получим обратное рефлексивное замыкание R ^–*.

Если R транзитивно и рефлексивно, то R* = R и R^–* = R ^–1.

Редукция R^r. Редукция применяется для отношений порядков. По смыслу эта операция обратна транзитивному замыканию. Редукцией отношения R называется отношение R^r, определяемое условием R^r = R \ R ².

Это означает, что отношение aR^rb выполняется в тех и только тех случаях, когда выполнено само отношение aRb, но не существует промежуточного элемента с такого, что aRс и сRb. Отношение aR^rb означает непосредственную связь элемента a с элементом b.