Скачать .docx | Скачать .pdf |
Реферат: Бинарные отношения
1. Бинарные отношения
Бинарные отношения служат простым и удобным аппаратом для весьма широкого круга задач. Язык бинарных и n- арных отношений используется во многих прикладных (для математики) областях, например, таких как математическая лингвистика, математическая биология, математическая теория баз данных. Широкое использование языка бинарных отношений легко объясняется - геометрический аспект теории бинарных отношений есть попросту теория графов.
Введем необходимые определения.
Определение 1.1 . Декартовым произведением множеств X и Y называется множество X xY всех упорядоченных пар (x , y ) таких, что x X , y Y .
Определение 1.2 . Соответствием между множествами X и Y (или соответствием из X в Y ) называется любое подмножество декартова произведения X xY . Если множества X и Y совпадают, то соответствие между множествами X и Y называют также бинарным отношением на множестве X .
Пример 1.1 . Пусть X = {a , b , c , d }, Y = {1 , 2 , 3 , 4 , 5 }. Тогда множество кортежей a={(a , 1 ), (b , 2 ), (c , 3 ), (d , 4 )} являются соответствием из X в Y .
Отметим, что обычно соответствия задаются не путем указания подмножества a декартова произведения X xY , а путем указания свойства пар (x , y ), принадлежащих этому подмножеству
a. Например, отношение a= {(4 , 4 ), (3 , 3 ), (2 , 2 ), (4 , 2 )} на множестве X = {4 , 3 , 2 } можно определить как свойство "Делится" на этом подмножестве целых чисел.
Хорошо известными примерами отношений из школьного курса математики являются:
- на множестве целых чисел Z отношения "делится", "делит", "равно", "больше", "меньше", "взаимно просты";
- на множестве прямых пространства отношения "параллельны", "взаимно перпендикулярны", "скрещиваются", "пересекаются", "совпадают";
- на множестве окружностей плоскости "пересекаются", "касаются", "концентричны".
Факт принадлежности кортежа (x , y ) соответствию a, часто обозначают с помощью так называемой инфиксной формы записи: x ay . Типичными примерами таких записей из курса математики являются: x > y , a = b , 8 4 , m ||l , a b и т. п.
Отношения могут задаваться формулами:
- формулы
y = x2 +5x - 6 или
задают бинарные отношения на множестве действительных чисел;
- формула
x + y = любовь,
задает бинарное отношение на множестве людей. Этому отношению принадлежит любая пара людей, между которыми существует любовь.
Задание отношений в виде формул достаточно широко распространено. Об этом свидетельствуют многочисленные надписи на деревьях заборах или стенах домов типа:
"Вася + Таня = любовь",
увековечивающие принадлежность конкретной пары (Вася, Таня) отношению "любовь".
Рассмотрим еще три формы представления бинарных отношений: матричное представление и два графических представления. В качестве носителя отношения для иллюстрирующих примеров будем использовать множество X = {a , b , c , d , e }.
Вначале рассмотрим метод, восходящий к аналитической геометрии. Начертим пару взаимно перпендикулярных осей (OX - горизонтальная ось, а OY - вертикальная ось) и на каждой отметим точки, представляющие элементы множества X (рис. 1).
Рис. 1. Координатная сетка
Считая метки a , b , c , d , e координатами точек на горизонтальной и вертикальной осях, отметим на плоскости точки с координатами (x , y ) такими, что (x , y ) . На рисунке 2 изображено множество точек, соответствующее отношению a= {(a , b ), (a , c ), (b , d ), (c , e ), (e ,b ), (e , e )}.
Рис. 2. Бинарное отношение a
Другой широко распространенный способ представления отношений основан на использовании ориентированных графов. При таком представлении элементы множества X изображаются вершинами графа (точками плоскости), а элементы (x , y ) отношения a дугами (стрелками), соединяющими первую компоненту x отношения со второй компонентой y . Граф бинарного отношения a изображен на рисунке 3.
Рис. 3. Граф бинарного отношения
Для бинарных отношений, определенных на конечных множествах, часто используется матричный способ задания. Пусть на некотором конечном множестве X задано отношение a. Упорядочим каким-либо образом элементы множества X = {x1 , x2 , ..., xn } и определим матрицу отношения A = [aij ] следующим образом:
Таким образом, матрица отношения a, представленного графом на рисунке 3, имеет вид
Часто матрицу отношения называют булевой, чтобы подчеркнуть, что ее элементами являются только нули и единицы.