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

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, имеет вид

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

еще рефераты
Еще работы по логике