Министерство
Образование и науки РК
Западно-Казахстанский Инженерно
Гуманитарный Университет
Институт Евразия
Деканат Информатики
и ВТ
КУРСОВАЯ РАБОТА
по дисциплине «Дискретная математика»
на тему «Основные свойства бинарных
отношений»
Выполнил: студент «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}.
Иногда инверсию называют обратным отношением.
Пример: