Типы соответствий

Пусть R = <X,Y,G_R>, где G_R XY и G_R = {(x,у)| хХ, yY, хRy}.

Определение: Если множество G_R (график соответствия R между элементами множеств X и Y) совпадает с множеством , то это соответствие называется полным.

Пример: X = {1,2,3} Y = {5,7,8}. R(x; y): х < y.

ХY = {(1,5),(1,7),(1,8),(2,5),(2,7),(2,8),(3,5),(3,7),(3,8)}

G_R = {(1,5),(1,7),(1,8),(2,5),(2,7),(2,8),(3,5),(3,7),(3,8)}.

Тогда G_R = . Следовательно, R - полное соответствие.

Определение: Если график соответствия R между элементами множеств Х и Y -есть пустое множество (G_R = Ǿ }, то такое соответствие называется пустым.

Пример: X = {1,2,3} Y = {5,7,8}. R(x; y): х > y.

Очевидно, G_R = Ǿ = > R - пустое соответствие.

Определение: Соответствия F и R между элементами множеств X и Y называется противоположными, если их графики являются дополнениями друг друга до множества ХY, то есть G_FG_R = Ǿ и G_FG_R = ХY => F и R - противоположные.

Если соответствие F задано предикатом F(x,у), то противоположное ему соответствие задаётся предикатом, который есть отрицание предиката F(x,у).

Пример: X = {1,2,3}, Y = {5,7,8}.

Пусть F(x,у): х < y. Тогда : х y – противоположное ему соответствие. Очевидно, G = Ǿ, а G = {(1,5),(1,7),(1,8),(2,5),(2,7),(2,8),(3,5),(3,7),(3,8)}. Они являются противоположными соответствиями.

Определение: Соответствия F и R между элементами множеств Х и Y называются несовместимыми, если G_F∩G_R = Ǿ.

Это значит, что нет ни одной пары (х,у), для которой одновременно выполняются условия хFy и хRy.

Ясно, что противоположные соответствия, можно называть несовместимыми, а наоборот - нельзя.

Определение: Если график соответствия F между элементами множеств Х и Y является подмножеством графика соответствия R между элементами множеств Х и Y (то есть G_FG_R), то соответствие R называется следствием соответствия F.

Пример 1: Х - множество треугольников плоскости.

F: ∆ х = ∆у.

R: ∆ х ~ ∆y.

G_F G_R => R - следствие соответствия F.

Пример 2: X = {1, 2, 3}

Y = {2, 3, 5}

F: х y. Тогда G_F = {(1,2),(1,3),(1,5),(2,2),(2,3),(2,5),(3,5)}.

R: х < y. G_R = {(1,2),(1,3),(1,5),(2,3),(2,5),(3,5)}.

G_R G_F => F - следствие соответствя R.

Определение: Обратным к соответствию R = <X,Y,G_R> между элементами множеств X и Y называется такое соответствие между элементами множеств Y и X, при котором тогда и только тогда, когда .

Граф обратного соответствия получается из графа данного соответствия путём замены стрелок на противоположные.

Пусть G_R – график данного соответствия между элементoв множества Х и Y, тогда, чтобы построить график обратного соответствия R^-1 между элементoв множества Y и Х, надо поменять местами компоненты пар.

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