Операции над отношениями

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

Объединением отношений и на множестве А называется отношение

Например, для отношений и , где A = {1, 2, 3} их объединением будет отношение

= .

Пересечением отношений и на множестве А называется отношение

Пересечением отношений из предыдущего примера будет отношение

Разностью отношений и на множестве А является отношение

Разность отношений и из предыдущего примера будет иметь вид

Инверсией отношения называется новое отношение , в котором элементы множества значений (графика) Ф^{- 1} являются инверсиями элементов графика Ф.

Например, для отношения инверсией будет отношение

Операция композиции может рассматриваться в тех случаях, когда заданы три множества А, В, и С. Тогда композицией отношений и называется новое отношение в котором каждый элемент (кортеж) графика получается по правилу

(5)

Здесь для обозначения операции композиции используется символ «» (кружок), а для всех кортежей, входящих в правило (5), должны выполняться условия: и .

В частных случаях возможно , тогда должно выполняться условие

Рассмотрим пример выполнения операции композиции для отношения строгого порядка, определяемого треугольно матрицей (4). Для удобства выполнения операции композиции все элементы отношения строгого порядка, задаваемые матрицей (4), запишем в одну строку

Тогда, пользуясь правилом (5), получим

Напомним, что при получении композиции элементы, встречающиеся многократно, входят в композицию, являющуюся множеством, только один раз.

Рассмотрим другой пример построения композиции отношения, но не с самим собой. Пусть Тогда

Рассматриваемые до сих пор операции над отношениями выполнялись на одной и той же области определения. Но возможны случаи отношений с разными областями определения. Для таких случаев вводится операция, меняющая область определения. Она называется операцией сужения отношения и формулируется следующим образом. Пусть задано отношение на множестве А, и имеется другое множество Тогда операция сужения отношения на множество В определяет новое отношение

Например, пусть = и Тогда