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

На отношения переносятся основные операции над множествами, но они могут выполняться только на одной и той же области задания.

Объединением отношений φ ₁ и φ ₂ на множестве М называется отношение φ ₃:

φ ₁ φ ₂ = φ ₃, φ ₁ = < Ф₁, M>, φ ₂ = < Ф₂, M>.

φ ₃ = < Ф₁ Ф₂, M>,

< a, b> Ф₁ Ф₂ < a, b> Ф₁ < a, b> Ф₂ & a, b M.

Например, пусть имеем два отношения: φ ₁ = < Ф₁, M>, φ ₂ = < Ф₂, M>, M = {2, 3, 4}, Ф₁ = {< 2, 1>, < 2, 2>, < 2, 4> }, Ф₂ = {< 2, 1>, < 2, 3>, < 4, 4> }

Тогда объединение этих отношений φ ₃ = < Ф₃, M>, Ф₃ = Ф₁ Ф₂ = {< 2, 1>, < 2, 2>, < 2, 4>, < 2, 3>, < 4, 4> }.

Отметим, что для операции объединения над отношениями справедлива следующая запись:

x(φ ₁ φ ₂)y x φ ₁ y x φ ₂y

Пересечением отношений φ ₁ и φ ₂ на множестве М называется отношение φ ₃:

φ ₁ φ ₂ = φ ₃, φ ₁ = < Ф₁, M>, φ ₂ = < Ф₂, M>.

φ ₃ = < Ф₁ Ф₂, M>,

< a, b> Ф₁ Ф₂ < a, b> Ф₁& < a, b> Ф₂ & a, b M.

Например, пусть имеем два отношения: φ ₁ = < Ф₁, M>, φ ₂ = < Ф₂, M>, M = {1, 2}, φ ₁= < {< 1, 1>, < 1, 2> }, {1, 2}>, φ ₂ = < {< 1, 2>, < 2, 2> }, {1, 2}>

Тогда пересечение этих отношений φ ₃ = < Ф₃, M> = < {< 1, 2> }, {1, 2}>.

Отметим, что для операции пересечения над отношениями справедлива следующая запись:

x(φ ₁ φ ₂)y x φ ₁ y& x φ ₂y

Операции объединения и пересечения также, как и для множеств применимы для любого числа отношений.

Отношение φ ₃ называется разностью отношений φ ₁ и φ ₂, если

φ ₁ = < Ф₁, M>, φ ₂ = < Ф₂, M>.

φ ₃ = φ ₁\ φ ₂ = < Ф1\Ф2, M>,

< a, b> Ф₁\Ф₂ < a, b> Ф₁& < a, b> Ф₂ & a, b M.

Например, пусть имеем два отношения: φ ₁ = < Ф₁, M>, φ ₂ = < Ф₂, M>, M = {1, 2, 3}, Ф₁= {< 2, 2>, < 1, 2>, < 3, 3> }, Ф₂ = {< 1, 1>, < 2, 2>, < 3, 3> }

Тогда разность этих отношений φ ₃ = < Ф₃, M> = < {< 1, 2> }, {1, 2, 3}>.

Отметим, что для операции разности над отношениями справедлива следующая запись:

x(φ ₁\φ ₂)y x φ ₁ y& x φ ₂’ y

Над отношениями выполняются также операции инверсии и композиции.

Если φ = < Ф, М>, то инверсия φ ^-1 = < Ф^-1, М >.

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

х φ ^-1у уφ х.

Например, для отношения φ =< Ф, М>, М={1, 2, 3}, Ф={< 1, 1>, < 1, 2>, < 1, 3> }, инверсия φ ^-1= < Φ ^-1, М> и Φ ^-1= {< 1, 1>, < 2, 1>, < 3, 1>).

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

φ ₁ = < Ф₁, M>, φ ₂ = < Ф₂, M>.

φ ₁ φ ₂ = < Ф₁ Ф₂, M>

Например, пусть имеем два отношения: φ ₁ = < Ф₁, M>, φ ₂ = < Ф₂, M>, M = {1, 2, 3}, Ф₁= {< 1, 1>, < 1, 2>, < 1, 3>, < 3, 3> }, Ф₂ = {< 1, 1>, < 2, 3>, < 3, 1>, < 3, 2> }

Тогда композиция графиков этих отношений равна Ф₃ = Ф₁ Ф₂ = {< 1, 1>, < 1, 3>, < 1, 2>, < 3, 2>, < 3, 1> }.

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

Введем операцию, меняющую область задания отношений.

Пусть φ =< Ф, М>, и А М, тогда сужением отношения φ на множестве А называется новое отношение

φ ₁ = < Ф A², A>

Например, φ =< Ф, М>, М={ 1, 2, 3}, Ф = {< 1, 1>, < 1, 2>, < 1, 3> }, A = {1, 2}. Тогда φ ₁ = < {< 1, 1>, < 1, 2> }, {1, 2}>.