Композиция отношений

Отношения

Пусть заданы два множества А и В. Найдем А ´ В.

Подмножество kА ´ В называется отношением из множества А во множество В.

Отношения задаются знаками =, <, >, £, ³ и т.д.

Пример:

А = {2,3,4}, B ={1,4,3}.

A ´ B = {(2,1),(2,4),(2,3),(3,1),(3,4),(3,3),(4,1),(4,4),(4,3)}.

Выделим отношения больше (>): k ₁ = {(2,1),(3,1),(4,1),(4,3)}

и меньше (<): k ₂ = {(2,4),(2,3),(3,4)}.

Рис.11. Отношение >

Пусть отношение k ₁ А ´ С и отношение k ₂ С ´ В.

Композицией этих отношений является отношение k = k ₁ k ₂, где k A ´ B.

Композицией отношений из А в В называется множество пар (а, b) таких, что, аА, bB и существует такое сС, что (а, с) k ₁ и (с, b) k ₂.

Пример:

А = {2,3,4},

B = {1,4,3}, С = {2,5}

A ´ В = {(2,1),(2,4),(2,3),(3,1),(3,4),(3,3),(4,1),(4,4),(4,3)},

A ´ C = {(2,2),(2,5),(3,2),(3,5),(4,2),(4,5)},

C ´ B = {(2,1),(5,1),(2,4),(5,4),(2,3),(5,3)}.

Определим отношение >:

k ₁ A ´ C = {(3,2),(4,2)}

и отношение <

k ₂ C ´ B = {(2, 4), (2, 3)}.

Возьмем пару (3,2) k ₁. В k ₂есть пары, начинающиеся с 2. Это пары (2,4) и (2,3). Значит пары (3, 4) и (3, 3) войдут в композицию k.

Берем пару (4,2) k ₁. В k ₂есть пары, начинающиеся с 2. Это те же пары (2,4) и (2,3). Значит пары (4, 4) и (4, 3) войдут в k.

Получим k = k ₁ k ₂ = (k A ´ B) = {(3, 4), (3, 3), (4, 4), (4, 3)}.

Таким образом, для элемента (2,4) А ´ В, в k войдут {(2,х), (у,4)}, где (2, х) k ₁, а (у, 4) k ₂для всех х и y.

Дата добавления: 2014-01-06