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

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

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

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

 

 

 

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

 

 

 

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

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

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

 

 

 

 

 

 

 

 

 

 

Выполнил: студент «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}.  
Иногда инверсию называют обратным отношением. 
 
Пример: