Реферат

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

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 22.11.2024



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

Бинарные отношения служат простым и удобным аппаратом для весьма широкого круга задач. Язык бинарных и n-арных отношений используется во многих прикладных (для математики) областях, например, таких как математическая лингвистика, математическая биология, математическая теория баз данных. Широкое использование языка бинарных отношений легко объясняется - геометрический аспект теории бинарных отношений есть попросту теория графов.

Введем необходимые определения.

Определение 1.1Декартовым произведением множеств X и Y называется множество XxY всех упорядоченных пар (xy) таких, что xhttp://www.smolensk.ru/user/sgma/MMORPH/N-3-html/Image56.gif Xyhttp://www.smolensk.ru/user/sgma/MMORPH/N-3-html/Image57.gifY.

Определение 1.2Соответствием между множествами X и Y (или соответствием из X в Y) называется любое подмножество декартова произведения XxY. Если множества X и Y совпадают, то соответствие между множествами X и Y называют также бинарным отношением на множестве X.

Пример 1.1. Пусть X = {abcd}, Y = {12345}. Тогда множество кортежей a={(a1), (b2), (c3), (d4)} являются соответствием из X в Y.

Отметим, что обычно соответствия задаются не путем указания подмножества a декартова произведения XxY, а путем указания свойства пар (xy), принадлежащих этому подмножеству

a. Например, отношение a= {(44), (33), (22), (42)} на множестве X = {432} можно определить как свойство "Делится" на этом подмножестве целых чисел.

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

Факт принадлежности кортежа (xy) соответствию a, часто обозначают с помощью так называемой инфиксной формы записи: xay. Типичными примерами таких записей из курса математики являются: x > ya = b8http://www.smolensk.ru/user/sgma/MMORPH/N-3-html/Image39.gif4m||lahttp://www.smolensk.ru/user/sgma/MMORPH/N-3-html/Image58.gif b и т. п.

Отношения могут задаваться формулами:
  • формулы

y = x2 +5x - 6  или  http://www.smolensk.ru/user/sgma/MMORPH/N-3-html/Image10.gif

задают бинарные отношения на множестве действительных чисел;
  • формула

y = любовь,

задает бинарное отношение на множестве людей. Этому отношению принадлежит любая пара людей, между которыми существует любовь.

Задание отношений в виде формул достаточно широко распространено. Об этом свидетельствуют многочисленные надписи на деревьях заборах или стенах домов типа:

"Вася + Таня = любовь",

увековечивающие принадлежность конкретной пары (Вася, Таня) отношению "любовь".

Рассмотрим еще три формы представления бинарных отношений: матричное представление и два графических представления. В качестве носителя отношения для иллюстрирующих примеров будем использовать множество X = {abcde}.

Вначале рассмотрим метод, восходящий к аналитической геометрии. Начертим пару взаимно перпендикулярных осей (OX - горизонтальная ось, а OY - вертикальная ось) и на каждой отметим точки, представляющие элементы множества X (рис. 1).

http://www.smolensk.ru/user/sgma/MMORPH/N-3-html/IMG00002.GIF

Рис. 1. Координатная сетка

Считая метки abcde координатами точек на горизонтальной и вертикальной осях, отметим на плоскости точки с координатами (xy) такими, что (xy)  . На рисунке 2 изображено множество точек, соответствующее отношению a= {(ab), (ac), (bd), (ce), (e,b), (ee)}.

http://www.smolensk.ru/user/sgma/MMORPH/N-3-html/IMG00003.GIF

Рис. 2. Бинарное отношение a

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

http://www.smolensk.ru/user/sgma/MMORPH/N-3-html/IMG00004.GIF

Рис. 3. Граф бинарного отношения

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

http://www.smolensk.ru/user/sgma/MMORPH/N-3-html/IMG00005.GIF

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

http://www.smolensk.ru/user/sgma/MMORPH/N-3-html/IMG00006.GIF

Часто матрицу отношения называют булевой, чтобы подчеркнуть, что ее элементами являются только нули и единицы.



1. Реферат Галилей основание современной науки
2. Сочинение на тему Сочинения на свободную тему - Встречи вне времени эссе
3. Курсовая Виды и состав бухгалтерской отчетности бюджетных учреждений
4. Реферат на тему Fossil Fuel Consumption CO2 And Its Impact
5. Реферат Однодворцы
6. Кодекс и Законы Учёт затрат на производство и калькулирование продукции кормовых культур
7. Реферат Основные тенденции мирового развития на современном этапе
8. Доклад на тему Великая Отечественная война 1941 1945 гг
9. Статья Открытые вопросы в массовых исследованиях
10. Реферат на тему Хронический левосторонний гнойный гайморит стадия обострения