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

Министерство  Образование и науки РК

Западно-Казахстанский Инженерно  Гуманитарный Университет

Институт Евразия

 

 

 

Деканат Информатики  и ВТ

 

 

 

               КУРСОВАЯ РАБОТА

                     по дисциплине «Дискретная математика»

на тему «Основные свойства бинарных отношений»

 

 

 

 

 

 

 

 

 

 

Выполнил: студент «922 группы» Уахитов Каирхан

Проверила: Жанысова А.Б

 

 

 

 

г. Уральск 2013

Содержание

Введение

1)Бинарные  отношения

2)Свойства бинарного  отношения

3)Инверсия и композиция  бинарных отношений

4)Функциональные отношения

5)Виды функциональных  отношений 

6)Теорема

7)Доказательство

         

                           

 

 

 

 

                         Бинарные отношения

 

    Бинарные отношения служат простым и удобным аппаратом  для весьма широкого круга задач. Язык бинарных и n-арных отношений используется во многих прикладных (для математики) областях, например, таких как математическая лингвистика, математическая биология, математическая теория баз данных. Широкое использование языка бинарных отношений легко объясняется – геометрический аспект теории бинарных отношений есть попросту теория графов. Бинарным отношением, определенным на паре множеств X и Y, называется любое подмножество прямого произведения множеств X x Y. 
    Если x связан с y отношением R, то это обозначают как xRy или (x, y) R.  
    Бинарное отношение может задаваться своим множеством R={(x,y)| xRy}.  
Поскольку бинарные отношения являются множествами, то имеет смысл говорить о действиях над бинарными отношениями как над множествами, т.е. возможно найти объединение пересечение и разность бинарных отношений. 
 
Пример:

•  - бинарное отношение заданное с помощью характеристического свойства;
• Пусть X = {a, b, c, d}, Y = {1, 2, 3, 4, 5}. Тогда множество R={(a, 1), (b, 2), (c, 3), (d, 4)} является бинарным отношением, заданным на паре X×Y.

 

    Область определения бинарного  отношения R – это множество  
                                                                   X = {x |  y (x, y) R}. 
    Область значений бинарного отношения R – это множество Y = {y |  x (x, y) R}. 
Хорошо известными примерами отношений из школьного курса математики являются:

• на множестве целых чисел Z отношения «делится», «делит», «равно», «больше», «меньше», «взаимно просты»;
• на множестве прямых пространства отношения «параллельны», «взаимно перпендикулярны», «скрещиваются», «пересекаются», «совпадают»;
• на множестве окружностей плоскости «пересекаются», «касаются», «концентричны».

 

   Рассмотрим еще два графических представления бинарных отношений. В качестве носителя отношения для иллюстрирующих примеров будем использовать множество X = {a, b, c, d, e}.  
    Вначале рассмотрим метод, восходящий к аналитической геометрии. Начертим пару взаимно перпендикулярных осей (OX – горизонтальная ось, а OY – вертикальная ось) и на каждой отметим точки, представляющие элементы множества X  
 
 
    Считая метки a, b, c, d, e координатами точек на горизонтальной и вертикальной осях, отметим на плоскости точки с координатами (x, y). На рисунке 2 изображено множество точек, соответствующее отношению R= {(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)}.  
 
 
    Другой широко распространенный способ представления отношений основан на использовании ориентированных графов. При таком представлении элементы множества X изображаются вершинами графа (точками плоскости), а элементы (x, y) отношения R ребрами (стрелками), соединяющими первую компоненту xотношения со второй компонентой y. Граф бинарного отношения R изображен на рисунке.  
  
 
 

Свойства бинарного отношения 
 
    Пусть задано бинарное отношение R на паре множеств X, Y. Бинарное отношение может обладать следующими свойствами, каждое из которых определяется своей аксиомой.

• Рефлексивность

(

x X) xRx или ( x X) (x, x) R 
    Граф рефлексивного бинарного отношения содержит петли около каждой вершины.

• Антирефлексивности

(

x X)  xRx или ( x X) (x, x) R  
    Граф антирефлексивного бинарного отношения не содержит ни одной петли.

• Симметричность

(

x, y X) xRy   yRx или ( x, y X) (x, y) R   (y, x) R  
    Граф симметричного бинарного отношения содержит только неориентированные ребра или петли. График симметричного отношения симметричен относительно биссектрисы I-III координатных углов.

• Антисимметричность

(

x, y X) xRy /\ yRx   x=y или ( x, yмX) (x, y) R /\ (y, x) R   x=y

• Транзетивность

(

x, y, z X) xRy /\ yRz   xRz или ( x, y, z X) (x, y) R /\ (y, z) R   (x, z) R

• Связанность

(vx, y

X) x≠y   xRy \/ yRx или (vx, y X) x≠y v (x, y) R \/ (y, x) R  
Примеры:

• Бинарное отношение задано своим множеством, определите его свойства, постройте граф и график   на множестве  .

 
Проверим все свойства отношения

• Рефлексивность

(

x А) (x, x) R – это ложное высказывание 
    Можно привести контр пример, х=3, пара (3,3) не принадлежит множеству R. Бинарное отношение не является рефлексивным.

• Антирефлексивности

(

x А) (x, x) R – это ложное высказывание 
    Можно привести контр пример, х=1, пара (1,1) принадлежит множеству R. Бинарное отношение не является антирефлексивным.

• Симметричность

(

x, y А) (x, y) R   (y, x) R – это ложное высказывание 
    Можно привести контр пример, х=1, y=2 пара (1,2) принадлежит множеству R, а пара (2, 1) не принадлежит множеству R. Бинарное отношение не является симметричным.

• Антисимметричность

(

x, y А) (x, y) R /\ (y, x) R   x=y – это истинное высказывание 
    Контр пример подобрать невозможно. Бинарное отношение является антисимметричным.

• Транзитивность

(

x, y, z А) (x, y) R /\ (y, z) R   (x, z) R – это ложное высказывание 
    Можно привести контр пример, х=1, y=2, z=3 пара (1,2) принадлежит множеству R и пара (2,3) принадлежит множеству R, а пара (1, 3) не принадлежит множеству R. Бинарное отношение не является транзитивным.

• Связанность

(

x, y A) x≠y   (x, y) R \/ (y, x) R – это ложное высказывание 
    Можно привести контр пример, х=3, y=4, 3≠4 пара (3,4) не принадлежит множеству R и пара (4,3) не принадлежит множеству R. Бинарное отношение не является связанным. 
 
Вывод: заданное бинарное отношение обладает только одним свойством антисимметричности. 
 
Построим граф и график

Граф

График

• Перечислите все элементы бинарного отношения  , заданное на множестве  . Определите, какими свойствами обладает данное отношение. Постройте граф и график.

 

    Зададим бинарное отношение R своим  множеством, перечислим все возможные  пары (х,у), элементы которых удовлетворяют  равенству  . 
  
 
Проверим все свойства отношения

• Рефлексивность

(

x А) x-2х=1 – это ложное высказывание 
    Можно привести контр пример, х=3, пара (3,3) не принадлежит множеству R. Бинарное отношение не является рефлексивным.

• Антирефлексивности

(

x А) x-2х≠1 – это ложное высказывание 
    Можно привести контр пример, х=-1, пара (-1,-1) принадлежит множеству R. Бинарное отношение не является антирефлексивным.

• Симметричность

(

x, y А) x-2у=1   у-2х=1 – это ложное высказывание 
    Можно привести контр пример, х=1, y=0 пара (1,0) принадлежит множеству R, а пара (0, 1) не принадлежит множеству R. Бинарное отношение не является симметричным.

• Антисимметричность

(

x, y А) x-2у=1 /\ у-2х=1   x=y – это истинное высказывание 
    Контр пример подобрать невозможно. Бинарное отношение является антисимметричным.

• Транзитивность

(

x, y, z А) x-2у=1 /\ у-2z=1   x-2z=1  – это ложное высказывание 
    Можно привести контр пример, х=3, y=1, z=0 пара (3,1) принадлежит множеству R и пара (1,0) принадлежит множеству R, а пара (3, 0) не принадлежит множеству R. Бинарное отношение не является транзитивным.

• Связанность

(

x, y A) x≠y v (x, y) R \/ (y, x) R – это ложное высказывание 
    Можно привести контр пример, х=3, y=4, 3≠4 пара (3,4) не принадлежит множеству R и пара (4,3) не принадлежит множеству R. Бинарное отношение не является связанным. 
 
Вывод: заданное бинарное отношение обладает только одним свойством антисимметричности. 
 
 
Построим граф и график

Граф

График

• Бинарное отношение   определенно на множестве действительных чисел R, выясните, какими свойствами оно обладает и какими не обладает. Постройте график.

Проверим все свойства отношения

• Рефлексивность

(

x R)   – очевидно, это истинное высказывание 
    Бинарное отношение является рефлексивным, свойство антирефлексивности проверять не имеет смысла.

• Симметричность

(

x, y R)       – очевидно, это истинное высказывание 
    Бинарное отношение является симметричным, но свойство антисимметричности будем проверять.

• Антисимметричность

(

x, y А)   /\   " x=y – это ложное высказывание 
    Можно привести контр пример, х=1, y=-1. Бинарное отношение не является антисимметричным.

• Транзитивность

(

x, y, z R)   /\   "    – это истинное высказывание 
    Бинарное отношение является транзитивным.

• Связанность

(

x, y R) x≠y     \/   – это ложное высказывание 
    Можно привести контр пример, х=3, y=4, 3≠4 пара (3,4) не принадлежит множеству R и пара (4,3) не принадлежит множеству R. Бинарное отношение не является связанным. 
 
Вывод: заданное бинарное отношение обладает свойствами рефлексивности, симметричности и транзитивности, такое отношение называется отношением эквиваленции. 
 
 
Построим график 
 

 

Инверсия и композиция бинарных отношений 
 
    Инверсией бинарного отношения R, заданного на паре множеств Х,Y, называется бинарное отношение R-1={(y,x)| (x,y)

R}.  
Иногда инверсию называют обратным отношением. 
 
Пример:

• Бинарное отношение задано своим множеством 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 сразу следует из двух доказанных выше при их одновременном выполнении. 
 
Теорема доказана.