5.2 Операции над соответствиями

Поскольку соответствия можно считать множествами, то все операции над множествами (пересечение, объединение, разность, дополнение и т.д.) можно применить и к соответствиям. Заметим, что, говоря о дополнении соответствия из А в В, мы имеем в виду дополнение до универсального соответствия из А в В, т.е.

Объединением соответствий Γ1 = и Γ2 = называют соответствие Γ1Γ2 = .

Пересечением соответствий Γ1 = и Γ2 = называют соответствие Γ1Γ2 = .

Разностью соответствий Γ1 = и Γ2 = называют соответствие Γ1\Γ2 =

Инверсией соответствия Γ= является соответствие Г-1, такое, что множество Y является областью отправления соответствия Г-1; множество X является областью прибытия соответствия Г-1, а график соответствия F-1 является инверсией графика F соответствия Г.

Композицией (произведением) соответствий Γ1 = и Γ2 = называют соответствие Γ1·Γ2 = . Поясним построение композиции двух соответствий. Областью отправления является область отправления Γ1, областью прибытия – область прибытияΓ2, а графиком – композиция графиков F и P.

В случае, если YW = O, то результатом композиции соответствий будет соответствие с пустым графиком.

Соответствие Ω называется инверсией соответствия Г, если область отправления Г равна области прибытия Ω и график Г является инверсией графика Ω.

Четная инверсия оставляет соответствие самим собой, а нечетная – инвертирует. То есть (Г-1)-1= Г, а ((Г-1)-1)-1 = Г-1. Соответствие Г-1= Г тогда и только тогда, когда график соответствия симметричен G=G-1, а область отправления соответствия совпадает с областью прибытия.

Пример. Г =, X = {1,2, 3}, G = {< 1,1>< 2, 2 >}. Графическое представление этого соответствия:

Для соответствия так же, как для отношений и множеств справедлива операция композиции. Композиция соответствий определяется через композицию их графиков. Композиция соответствий не является пустой, если существует хотя бы один элемент уY& уZ. Пусть заданы соответствия Γ1 = и Γ2 = . Тогда Γ1·Γ2= - определяет композицию двух соответствий.

Например, пусть заданы множества X = {a, b}, Y = {с, d} Z = {d, е} U = . Для получения непустого результата композиции соответствий множество Z должно частично или полностью совпадать с множеством Y

Для любых трех соответствий существует следующее правило композиции:

(Γ1·Γ2)·Γ3=Γ1· (Γ2·Γ3)

Докажем это тождество.

1. Необходимость: (Γ1·Γ2)·Γ3 → Γ1·Γ2 &Γ3Γ1 &Γ2 &Γ3 →Γ1 &Γ2·Γ3→Γ1· (Γ2·Γ3).

2. Достаточность: Γ1· (Γ2·Γ3)→Γ1 &Γ2·Γ3→Γ1 &Γ2 &Γ3 → Γ1·Γ2 &Γ3→(Γ1·Γ2)·Γ3.

3. Следовательно, тождество справедливо.