Реферат

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

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

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

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

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

от 25%

Подписываем

договор

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

Скидка 25% при заказе до 8.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. Контрольная работа на тему Права и свободы человека и гражданина 3
2. Реферат Иконографический образ Троицы
3. Реферат на тему Bowfishing Essay Research Paper The Art Of
4. Контрольная работа Трудовые затраты как потенциальная будущая выгода предприятия
5. Реферат Фундаментальный анализ валютного рынка
6. Диплом на тему Методы бухгалтерского учета с использованием средств автоматизации в ЗАО ххх
7. Реферат Курсовая сущность и функции денежных расчетов
8. Реферат История и архитектурный ансамбль Новгородского Свято-Юрьева монастыря
9. Реферат на тему Hiding From Destiny Essay Research Paper Hiding
10. Реферат Возникновение и развитие концепции маркетинга