5.2. Операции над соответствиями
Для соответствий действительны все операции, определенные для множеств и отношений, т.е. объединение, пересечение, разность, инверсия, композиция.
Объединением соответствий Г = <X, Y, F> и = <W, Z, P> является соответствие: Г = <X W, Y Z, F P>.
Пересечением соответствий Г и является соответствие: Г = <X W, Y Z, F P>.
Разностью соответствий Г и является соответствие: Г = <X \ W, Y \ Z, F \ P>.
Инверсией соответствия Г является соответствие Г-1, такое, что множество Y является областью отправления соответствия Г-1; множество X является областью прибытия соответствия Г-1, а график соответствия F-1 является инверсией графика F соответствия Г.
Композицией соответствий Г1 = <X, Y, F> и Г2 = <W, Z, P> является соответствие, такое, что его областью отправления является область отправления соответствия Г1, областью прибытия - область прибытия соответствия Г2, а графиком - композиция графиков F и P: Г1 • Г2 = <X, Z, F • P>.
В случае, если Y W = , то результатом композиции соответствий будет соответствие с пустым графиком.
Соответствие называется инверсией соответствия Г, если область отправления Г равна области прибытия и график Г является инверсией графика .
Четная инверсия оставляет соответствие самим собой, а нечетная — инвертирует. То есть (Г-1)-1 = Г, а ((Г-1)-1)-1 = Г-1. Соответствие Г-1 = Г тогда и только тогда, когда график соответствия симметричен G = G-1, а область отправления соответствия совпадает с областью прибытия. Например, Г = <G, X, X>, Х = {1, 2, 3}, G = {< 1, 1 >, < 2, 2 >}. На рис. 5.4 приведено графическое представление этого соответствия.
Рис. 5.4. Графическое представление соответствия
Для соответствия так же, как для отношений и множеств справедлива операция композиции. Композиция соответствий определяется через композицию их графиков. Композиция соответствий не является пустой, если существует хотя бы один элемент y Y & y Z. Пусть заданы соответствия Г1 = <G, X, Y>, Г2 = <H, Z, U>. Тогда Г1•Г2 = <G•H, X, U> - определяет композицию двух соответствий.
Например, пусть заданы множества Х = {a, b}, Y = {c, d}, Z = {d,e}, U = <k, l>. Для получения непустого результата композиции соответствий множество Z должно частично или полностью совпадать с множеством Y.
Зададим произвольные графики G = { < a, c >, < b, d > }, и H = { < d,k >, < d,e >, < e,k > }. Тогда композиция графиков G•H = { < b, k >, < b, e > } и композиция соответствий запишется Г1•Г2 = < {< b, k >, < b, e >}, X, U >. Графическое представление композиции соответствий Г1 и Г2 показано на рис. 5.5.
Рис. 5.5. Пример графического представления композиции соответствий
Для любых трех соответствий существует следующее правило композиции:
(Г1•Г2)•Г3 = Г1•(Г2•Г3).
Докажем это тождество.
1) Докажем необходимость. Предположим, что
<a, b> (Г1•Г2)•Г3 <a, x> Г1•Г2 <x, b> Г3 <a, x1> Г1 <x1, x> Г2 <x, b> Г3 <a, x1> Г1 <x1, b> Г2•Г3 <a, b> Г1•(Г2•Г3).
Первая часть доказана.
2) Теперь докажем вторую часть, т.е. достаточность.
Пусть <a, b> Г1•(Г2•Г3) <a, x> Г1 <x, b> Г2•Г3 <a, x> Г1 <x, z> Г2 <z, b> Г3 <a, x> Г1 <x, z> Г2 <z, b> Г3 <a, z> Г1•Г2 <z, b> Г3 <a, b> (Г1•Г2)•Г3, что и требовалось доказать. Следовательно, тождество справедливо.
ПРИМЕРЫ:
Пример 5.5. Заданы соответствия Г1 = <X, Y, F>; X = {1, 2, 3}; Y = {a, b, c, d}; F = {<1, a>; <1, c>; <2, b>; <2, c>; <3, d>}; Г2 = <W, Z, P>; W = {2, 4, 5, 6}; Z = {a, c, d, e}; P = {<2, a>; <2, e>; <4, a>; <4, d>; <5, c>; <5, e>; <6, c>; <6, d>}. Найдем их пересечение, объединение и разность.
Ответ: Пересечение, объединение и разность соответствий Г и , изображены соответственно на рис. 5.6, а - в.
Рис. 5.6, а-в. Результаты операций объединении, пересечения и разности соответствий Г1 и Г2
Пример 5.6. Для соответствий Г1 и Г2, заданных в предыдущем примере, найти инверсию соответствия Г2 и композицию соответствий Г1 • Г2-1.
Ответ: Инверсия соответствия Г2 изображена на рис.5.7, а композиция соответствий Г1 и Г2-1 - на рис.5.8.
Рис. 5.7. Результат операции инверсии соответствия Г2
Рис. 5.8. Результат операции композиции соответствий Г1 и Г2-1