Отношения

ot.jpg

Способы задания отношений. При составлении отношений с числовыми множествами удобным инструментом их задания является формула. Например, пусть отношение Q задано следующим образом:Q = {(x,y)ÎR½ y = x2}, т. е. пара (х,у) для х и у, являющихся действительными числами, связана отношением y = x2.
Для нечисловых множеств используется способ задания отношений спис­ком, т. е. перечислением всех пар элементов, для которых данное отношение выполняется. Например, пусть заданы два множества. А – множество видов транспорта, связывающих два населенных пункта А = {автобус, ж.-д. транспорт, речной транспорт}; В – стоимость проезда В = {20, 10, 7}. Тогда отношение Q = {(автобус, 20), (ж.-д. транспорт, 10), (речной транспорт, 7)} Ì А´В ставит в соответствие виду транспорта стоимость проезда на нем.
Рассмотрим еще три формы представления бинарных отношений: матричное представление и два графических представления. В качестве носителя отношения для иллюстрирующих примеров будем использовать множество X = {a, b, c, d, e}.
Начертим пару взаимно перпендикулярных осей (OX — горизонтальная ось, а OY — вертикальная ось) и на каждой отметим точки, представляющие элементы множества X (рис. 1).

external image IMG00002.GIF

Рис. 1. Координатная сетка
Считая метки a, b, c, d, e координатами точек на горизонтальной и вертикальной осях, отметим на плоскости точки с координатами (x, y) такими, что (x, y) . На рисунке 2 изображено множество точек, соответствующее отношению a= {(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)}.

external image IMG00003.GIF

Рис. 2. Бинарное отношение a
Другой широко распространенный способ представления отношений основан на использовании ориентированных графов. При таком представлении элементы множества X изображаются вершинами графа (точками плоскости), а элементы (x, y) отношенияa дугами (стрелками), соединяющими первую компоненту x отношения со второй компонентой y. Граф бинарного отношения aизображен на рисунке 3.

external image IMG00004.GIF

Рис. 3. Граф бинарного отношения
Для бинарных отношений, определенных на конечных множествах, часто используется матричный способ задания. Пусть на некотором конечном множестве X задано отношение a. Упорядочим каким-либо образом элементы множества X = {x1, x2, …,xn} и определим матрицу отношения A = [aij] следующим образом:

external image IMG00005.GIF

Таким образом, матрица отношения a, представленного графом на рисунке 3, имеет вид

external image IMG00006.GIF

Перечислим основные свойства бинарных отношений, определенных на одном множестве.

1. Рефлексивность: формула хРх реализуется или имеет значение «истина» (например, отношение х£х истинно для любых действительных чисел).
2. Антирефлексивность: формула хРх не реализуется или имеет значение «ложь» (например, отношение х<х ложно для любых действительных чисел).
3. Симметричность: из хРу Þ уРх (например, отношение х = у симметрично для любых действительных чисел).
4. Антисимметричность: если истинно хРу и уРх, то х = у (например, отношение х£ у антисимметрично для любых действительных чисел).
5. Несимметричность: если хРу истинно, то уРх ложно (например, отношение х<у несимметрично для любых действительных чисел).
6. Транзитивность: из истинности хРу и уРz Þ истинность хРz (например, отношение х<у транзитивно для любых действительных чисел из х<у и у<z Þ х<z).

Рассмотрим основные типы бинарных отношений, определенных на одном множестве.

Бинарное отношение a на множестве X называется отношением эквивалентности на X, если a рефлексивно, симметрично и транзитивно. Отношение эквивалентности часто обозначают символами ~,external image Image49.gif.
Отношение эквивалентности является обобщением отношения равенства.
Отношение эквивалентности R разбивает множество M на непересекающиеся подмножества так, что любые элементы одного подмножества находятся в отношении R, а любые элементы разных подмножеств не находятся в отношении R . Данные подмножества называются классами эквивалентности, а их количество – индексом разбиения.

Отношение эквивалентности лежит в основе всевозможных классификаций. При классификации некоторого множества в нем задают одно или несколько отношений эквивалентности и рассматривают классы эквивалентности, связанные с этими отношениями. При иерархической классификации все множество разлагается на классы эквивалентности, после чего каждый класс разлагается на классы эквивалентности по другому отношению и т. д. Такая классификация применяется, например, в биологии (царства живых существ, типы, классы, отряды, роды, виды). В математике иерархическая классификация используется, например, при классификации линий второго порядка. Другой вид классификации основан на том, что указывается несколько свойств (например форма, цвет, размер и т. д.), каждое из которых может принимать несколько значений (например, квадрат, круг, шестиугольник или красный зеленый, синий и т. д.). После этого каждый класс характеризуется значениями, принимаемыми на нем данными свойствами (например, зеленые маленькие квадраты). В библиотеках множество всех книг разбивают на книги по математике, физике, химии, истории и т. д. Далее книги по математике делят на книги по алгебре, геометрии, математическому анализу и т. д. В математике такой вид классификации используется, например, при классификации многоугольников, с одной стороны, по числу сторон, а с другой — по признаку правильности или неправильности.

Бинарное отношение R на множестве M называется отношением нестрогого порядка, если оно
• рефлексивно,
• антисимметрично,
• транзитивно.

Примеры:

1) отношение ≤ на множестве действительных чисел;
2) отношение «быть не старше» на множестве людей.

Бинарное отношение R на множестве M называется отношением строгого порядка, если оно
• антирефлексивно,
• антисимметрично,
• транзитивно.

Примеры:

1) отношение < на множестве действительных чисел;
2) отношение «быть начальником» на множестве сотрудников организации.

Отношения строгого и нестрогого порядка называются отношениями порядка.
Элементы a,b∈ M называются сравнимыми по отношению порядка R , если aRb или bRa . Множество M называется полностью упорядоченным множеством, если любые два элемента в нем сравнимы по некоторому отношению порядка R .

Примеры:

1) множество действительных чисел по отношениям <,≤,=,≥,> ;
2) отношение «быть не старше» на множестве людей.

Множество M называется частично упорядоченным множеством, если в нем есть хотя бы два элемента, несравнимые по некоторому отношению порядка R .

Примеры:

1) множество комплексных чисел отношениям <,≤,≥,> ;
2) отношение «быть начальником» на множестве сотрудников организации.

Полезные ресурсы:
http://www.smolensk.ru/user/sgma/MMORPH/N-3-html/1.htm
Математические статьи http://naotlichno.by/kombinatorika/20-binarnye-otnosheniya.html
Справочник математических формул, примеры и задачи с решениями http://www.pm298.ru/reshenie/deistv.php
Основные тезисы дискретной математики http://www.mami.ru/kaf/vmat/diskrmat.pdf

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *