Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Операции над соответствиями
|
|
Поскольку соответствия можно считать множествами, то все операции над множествами (пересечение, объединение, разность, дополнение и т.д.) можно применить и к соответствиям. Заметим, что, говоря о дополнении соответствия из А в В, мы имеем в виду дополнение до универсального соответствия из А в В, т.е. до декартова произведения А× В. Естественно, что и равенство соответствий можно трактовать как равенство множеств.
Объединением соответствий Γ 1 = < X, Y, F> и Γ 2 = < W, Z, P> называют соответствие Γ 1 
Γ 2 = < X W, Y Z, F P>.
Пересечением соответствий Γ 1 = < X, Y, F> и Γ 2 = < W, Z, P> называют соответствие Γ 1 
Γ 2 = < X W, Y Z, F P>.
Разностью соответствий Γ 1 = < X, Y, F> и Γ 2 = < W, Z, P> называют соответствие Γ 1\Γ 2 = < X\W, Y\Z, F\P>
Инверсией соответствия Γ = < X, Y, F> является соответствие Г-1, такое, что множество Y является областью отправления соответствия Г-1; множество X является областью прибытия соответствия Г-1, а график соответствия F-1 является инверсией графика F соответствия Г.
Композицией (произведением) соответствий Γ 1 = < X, Y, F> и Γ 2 = < W, Z, P> называют соответствие Γ 1·Γ 2 = < X, Z, F·P>. Поясним построение композиции двух соответствий. Областью отправления является область отправления Γ 1, областью прибытия – область прибытияΓ 2, а графиком – композиция графиков 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 > }. Графическое представление этого соответствия:
Для соответствия так же, как для отношений и множеств справедлива операция композиции. Композиция соответствий определяется через композицию их графиков. Композиция соответствий не является пустой, если существует хотя бы один элемент у 
Y& у Z. Пусть заданы соответствия Γ 1 = < G, X, Y> и Γ 2 = < H, Z, U>. Тогда Γ 1·Γ 2= < G·H. X, U> - определяет композицию двух соответствий.
Например, пусть заданы множества X = {a, b}, Y = {с, d} Z = {d, е} U = < k, l>. Для получения непустого результата композиции соответствий множество Z должно частично или полностью совпадать с множеством Y
Для любых трех соответствий существует следующее правило композиции:
(Γ 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, z> Γ 1·Γ 2 & < z, b> Γ 3→ < a, b> (Γ 1·Γ 2)·Γ 3.
3. Следовательно, тождество справедливо.
|
|