Отношения

Основные понятия отношений

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

Рассмотрим пример, иллюстрирующий понятие отношения (рис 3.1):

Предположим, что $$P$$ - множество программ; $$D$$ - конечное множество данных; $$R$$ - множество результатов.

Если мы выберем конкретное значение из $$D$$, то оно может использоваться в некоторых программах из $$P$$ и для каждой программы из $$P$$ существует совокупность значений из $$D$$, которые в ней используются. Таким образом, мы имеем соответствие между значениями данных и программами, и, следовательно, существуют элементы $$D \times P$$, представляющие интерес. Аналогично, если мы сведем рассмотрение к $$p \in P$$, то $$p$$ связывает соответствующие данные из $$D$$ с результатами из $$R$$.

Можно рассматривать данные, приводящие к остановке, или результаты, которые не могут быть получены из $$p$$. Следовательно, мы приходим к подмножеству $$D \times R$$.

Определение. $$n$$ -местным отношением $$R$$ на множествах $$A_ , ..., A_n$$ называется подмножество прямого произведения $$A_1 \times...\times A_n$$.

Другими словами, элементы $$x_1, ..., x_n$$ (где $$x_1\in A_1, ......, x_n\in A_n$$ ) связаны отношением $$R$$ тогда и только тогда, когда $$(x_1, x_2, …..., x_n)\in R$$, а ( $$x_1, x_2, …..., x_n$$ ) - упорядоченный набор из $$n$$ элементов.

Наиболее часто встречаются отношения при $$n = 2$$ ; в этом случае они называются бинарными отношениями. Следовательно, бинарные отношения между множествами $$A$$ и $$B$$ являются просто подмножеством $$A \times B$$. Если эти множества эквивалентны (скажем, равны $$A$$ ), то будем говорить, что подмножество $$A^2$$ определяет отношения на $$A$$.

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

Пример 1. Пусть $$A = \left\{ {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} \right\}$$.

Тогда $$R = \left\{(x, y): x, y \in A, \mbox{где x - делитель y и x \le 5}\right\}$$.

В явном виде$$\begin{array}{l} R = \left\{ {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6),(1, 7), (1, 8), (1, 9), (1, 10), (2, 2), (2, 4), (2, 6),\\ (2, 8), (2, 10), (3, 3), (3, 6), (3, 9), (4, 4), (4, 8), (5, 5), (5, 10)} \right\} \\ \end{array}.$$

Пример 2 (шахматы). Пусть $$F = \left\{ {a, b, c, d, e, f, g, h } \right\}, R = \left\{ {1, 2, 3, 4, 5, 6, 7, 8 } \right\}$$ и пусть $$S = F \times R$$.

Таким образом, $$S$$ - множество всех клеток, обозначаемых парами $$(x, y)$$, где $$x \in F, y \in R$$.

Определим бинарное отношение $$C$$ для ладьи на множестве $$S$$ так, что $$(s, t) \in C$$ тогда и только тогда, когда $$s$$ и $$t$$ - элементы $$S$$ и ладья может пройти от $$s$$ к $$t$$ одним ходом на пустой доске.

Напомним, что ладья может изменять либо горизонтальную координату, либо вертикальную, но не обе одновременно.

В общем случае ряд различных отношений на множестве $$A$$ зависит от $$\left| A \right|$$. Большая часть этих отношений не представляет интереса, но отдельные оказываются полезными.

Определение 1. Для любого множества $$A$$ определим тождественное отношение $$I_A$$ и универсальное отношение $$U_A$$ следующим образом:

Таким образом, $$U_A = A^2$$. Так как $$\emptyset \subseteq A^2$$, то $$\emptyset$$ является отношением на $$A$$ и называется пустым отношением.

Пусть отношение $$R$$ определено в соответствии с изображением на рис 3.2. Свяжем с каждым бинарным отношением $$R$$ между $$A$$ и $$B$$ - область определения $$D(R)$$ и область значений $$\Re (R)$$. Они определяются следующим образом.

Определение 2. Область определения - это множество значений $$x$$, таких, что пара $$(x, y)$$ принадлежит отношению $$R: D(R) = \left\{ x : (x, y) \in R \right\}$$, а область значений $$\Re (R)$$ это множество значений $$y$$, таких, что пара $$(x, y)$$ принадлежит отношению $$R: \Re (R) = \left\{ y : (x, y) \in R \right\}$$.

Пример 3. Пусть отношение $$R$$ такое же, как и в примере 1, $$R = \left\{(x, y): x, y \in A, \mbox{где x - делитель y и x \le 5}\right\}$$. В явном виде $$\begin{array}{l} R = \left\{ {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (2, 2), (2, 4), (2, 6),\\ (2, 8), (2, 10), (3, 3), (3, 6), (3, 9), (4, 4), (4, 8), (5, 5), (5, 10)} \right\}\\ \end{array}$$.

Тогда $$D (R) = \left\{ {1, 2, 3, 4, 5 } \right\}$$, т. е. $$\Re (R) = A$$.

Хотя каждое отношение является множеством и может быть обозначено прописной буквой, иногда отношения обозначаются строчными греческими буквами: $$\rho ,\tau ,\sigma $$.

Например:

a) $$(a, b) \in \rho $$, т. е. $$(a, b)$$ находится в $$\rho$$ ;

б) $$a \rho b: a$$ связано с $$b$$ отношением $$\rho$$ ;

в) $$b \in \rho (a)$$.

Определение 3. Пусть $$R$$ - бинарное отношение. Определим обратное отношение $$R^{-1}$$ следующим образом:

Таким образом, $$R^{-1}$$ связывает те же пары элементов, что и $$R$$, но "в другом порядке". Следовательно, если $$R \subseteq A \times B$$, то $$R^{-1} \subseteq B \times A, D(R^{-1}) = \Re (R)$$ и $$\Re (R^{-1}) = D(R)$$.

Можно $$D(R)$$ писать $$D_R$$ и $$\Re (R)$$ как $$R_R$$.

Графические представления отношений

Записанные в виде множества упорядоченных пар отношения иногда нелегко расшифровываются.

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

Координатный метод

Пусть дано множество $$X = \left\{ {a, b, c, d, e} \right\}$$ и отношения:

тождественное $$I_x$$, универсальное $$U_x$$ и некоторое отношение $$R = \left\{ {(a, b), (a, c), (b, d), (c, e), (e, b)} \right\}$$.

Координатный метод относится к традиционной аналитической геометрии (рис 3.3).

Основной недостаток этого метода заключается в том, что при увеличении мощности $$\left| X \right|$$ трудно увидеть элементы в области и установить соответствие с точками, обозначающими отношения.

Линейно-координатный метод

Для преодоления недостатка предыдущего метода можно опустить точки и соединить стрелкой $$x \in D$$ и $$y \in R$$, когда $$(x, y)$$ принадлежат отношению. Иллюстрация предыдущего примера линейно-координатным методом показана на рис 3.4.

Диаграмма $$U_x$$ получилась довольно запутанной, зато отношения $$I_x$$ и $$R$$ получились наглядными.

Линейный метод

Используя параллельные вертикальные линии для $$D$$ и $$R$$ получаем диаграммы, в которых стрелки не требуются в принципе, так как мы двигаемся слева направо (рис 3.5).

Графовый метод

Элементы множества, на котором строится отношение, представлены вершинами графа, а сами отношения - дугами графа (рис 3.6). Так как точки $$a, b, c, d, e$$ в областях $$D$$ и $$R$$ одни и те же, их можно объединить.