Основные свойства бинарных отношений

• Бинарное отношение задано своим множеством R={(1,2), (2,4), (3,1), (3,4)}. Найдите инверсию отношения R.

       R-1={(2,1), (4,2), (1,3), (4,3)} – поменяли местами  компоненты пар.

• Бинарное отношение задано с помощью характеристического свойства   на множестве действительных чисел. Найдите инверсию отношения R. 
   – поменяли местами переменные x и y. 
   
  Симметричное бинарное отношение совпадает со своей инверсией, т.е. R-1=R. 
   
       Пусть заданы бинарные отношения R на паре множеств Х,Y и S на паре множеств Y,Z. Композицией бинарных отношений S и R называется бинарное отношение  
  S°R= {(x, z) |   y Y (x, y) R /\ (y, z) S}.  
   
   
   
  Пример:
• Бинарные отношения заданы своими множествами R={(1,2), (2,4), (3,1), (3,4)} и S={(2,2), (3,4), (3,1), (2,4)}. Найдите композиции S°R и R°S.

S°R={(1,2), (1,4)}, R°S={(3,2), (2,4)}.

• Бинарные отношения заданы с помощью характеристических свойств   и  на множестве действительных чисел. Найдите композиции S°R и R°S.

    Воспользуемся определением композиции  
S°R= {(x, z) |   y Y (x, y) R /\ (y, z) S},  
тогда S°R= {(x, z) |   y R  /\ y+3z=5}={(x, z) |   y R  /\ y=5-3z} 
S°R= {(x, z) |  }.   
R°S = {(x, z) |   y R x+3y=5/\   }={(x, z) |   y R x+3y=5/\   } 
S°R= {(x, z) |  }.    
 
Функциональные отношения 
 
    Пусть задано бинарное отношения R на паре множеств Х,Y. Отношение R называется функциональным, если:  
( x X)(  y1, y2 Y)  (xRy1) /\ (xRy2) -> (y1 = y2). 
    Функциональное отношение часто называют функцией или отображением. Будем обозначать тот факт, что элемент x связан с элементом y функциональным отношением следующим образом y=f(x). 
 
Виды функциональных отношений 
 
Отображение называется инъективным или инъекцией, если  
( x1,x2 X) f(x1) = f(x2) -> (x1 = x2). 
 
 
Отображение называется сюрьективным или сюръекцией, если 
( y Y) ( x X) y=f(x). 
 
 
Отображение называется биективным или биекцией, если оно является и инъективным и сюрьективным.  
  
 
Пример:  
X={1,2,3}, Y={a,b,c} 
 
Перечислим все иньективные отображения X->Y

 
 
В данной задаче все отображения  иньюктивны и сюръективны, а следоватльно биективны. 
 
Определение: 
Пусть F: X->Y, F называется обратимым, если   такое, что: 
1.   
2.   
Отображение G называется обратным к отображению F (G: ) 
 
Теорема: 
    Критерий обратимости отображения 
Отображение   обратимо тогда и только тогда, когда оно биективно. 
Доказательство. Необходимость. Пусть отображение    биективно. Так как оно сюръективно, то   есть хотя бы один прообраз из Х. Но в силу инъективности все элементы имеют разные образы. Поэтому y0 имеет единственный прообраз х0. Сопоставив каждому элементу y из Y его единственный прообраз, получим отображение   такое, что если  , то  . При этом получим  х Х  , т.е.  ;    , т.е.  . 
Коммутация сообщений Под коммутацией сообщений понимается передача единого блока данных между транзитными компьютерами сети с временной буферизацией этого блока на диске каждого компьютера . Сообщение в отличие от пакета имеет произвольную длину, которая определяется не технологическими соображениями, а содержанием информации, составляющей сообщение. Например, сообщением может быть текстовый документ, файл с кодом программы, электронное письмо. 
 
Достаточность. Пусть отображение   - обратимое и   -- обратное к f.  Пусть  . Применим к данному равенству отображение j:  . Таким образом, f -- инъективно. 
 
Пусть   . Найдём прообраз х0, такой, что . Имеем: 
, 
  где  . Тем самым, ¦ -- сюръективно. 
     
Следствие.  
Если f -- биективно, то и f1 также биективно. 
Соотношение, характеризующее зависимость между координатами х и у точек кривой называется уравнением этой кривой. Например: у+2х-1=0 - уравнение прямой, х2+у2=4 - уравнение окружности. Координаты любой точки, лежащей на кривой, удовлетворяют уравнению кривой, а координаты точек, на кривой не лежащей, уравнению не удовлетворяют. Например, проверим лежит ли точка А (1,2) и В (0,1) на прямой у+2х-1=0. Для этого подставим координаты каждой точки в уравнение прямой. 1) А(1,2)-2+2-1 0, вывод: точка А не принадлежит прямой. 2) В(0,1)-1-1=0, вывод: точка В лежит на прямой.

 
Теорема:  
Если X, Y и Z – произвольные непустые множества и определены отображения: f:X->Y, g:Y->Z, тогда верны следующие утверждения: 
1) Если отображения f и g являются инъективными, то композиция f°g так же инъективна; 
2) Если отображения f и g являются сюръективными, то композиция f°g так же сюръективна; 
3) Если отображения f и g являются биективными, то композиция f°g так же биективна; 
 
Доказательство: 
1) Пусть нам даны инъективные отображения f и g. Докажем, что композиция fog инъективна. Рассмотрим f(g(x1))=z и f(g(x2))=z. Поскольку отображение f инъективно, то g(x1)=z и g(x2)=z. По инъективности g можно сказать, что x1=x2. Значит, композиция отображений fog инъективна. 
 
2) Пусть нам даны сюръективные отображения f и g. Докажем, что композиция fog сюръективна. Возьмем произвольный элемент z из множества Z. Понятно, что независимо от выбора, z=g(y) по сюръективности g. Однако, f тоже является сюръективным отображением, значит, для любого y из Y выполнено: y=f(x). Таким образом, z=g(y)=g(f(x))=fog. Сюръективность композиции fog доказана. 
 
3) Пункт 3 сразу следует из двух доказанных выше при их одновременном выполнении. 
 
Теорема доказана.