Главная Учебники - Разные Лекции (разные) - часть 50
1. Бинарные отношения
Бинарные отношения служат простым и удобным аппаратом для весьма широкого круга задач. Язык бинарных и n-
арных отношений используется во многих прикладных (для математики) областях, например, таких как математическая лингвистика, математическая биология, математическая теория баз данных. Широкое использование языка бинарных отношений легко объясняется - геометрический аспект теории бинарных отношений есть попросту теория графов. Введем необходимые определения. Определение 1.1
. Декартовым произведением
множеств X
и Y
называется множество X
xY
всех упорядоченных пар (x
, y
) таких, что x
Определение 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
} можно определить как свойство "Делится" на этом подмножестве целых чисел. Хорошо известными примерами отношений из школьного курса математики являются: Факт принадлежности кортежа (x
, y
) соответствию a, часто обозначают с помощью так называемой инфиксной формы записи: x
ay
. Типичными примерами таких записей из курса математики являются: x
> y
, a
= b
, 8
Отношения могут задаваться формулами: 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, имеет вид
|