2.20.2. Задание отношений в виде графа
Существует
ещё и другой важный способ задания
бинарных отношений, заданных на конечных
множествах. Изобразим элементы конечного
множества
точками на плоскости. Если выполнено
соотношение
(или
),
то проведём стрелку от
к
.
Если выполняется
(или
),
то нарисуем петлю, выходящую из
и входящую в эту же точку. Такая фигура
называется ориентированным графом, а
сами точки – вершинами графа (рис.
2.19.).
При графическом способе задания бинарных отношений пустому отношению соответствует граф без стрелок и петель. Диагональное отношение изображается графом, в котором присутствуют только петли. Полное отношение изображается полным графом, где каждая его вершина соединена со всеми другими вершинами, в том числе и сама с собой. Граф есть геометрическое изображение бинарного отношения аналогично тому, как график есть геометрическое изображение функции. Геометрический язык полезен лишь тогда, когда граф достаточно прост. Изучать же сложные графы с большим числом вершин удобнее в терминах отношений.
2.20.3. Задание отношений с помощью фактор множества
Прежде, чем изложить способ задания бинарных отношений с помощью фактор множества, введём понятие окрестности единичного радиуса. Рассмотрим множество с заданным на нём бинарным отношением .
Определение
Окрестностью
единичного радиуса элемента
называется множество
,
задаваемое следующей высказывательной
формой:
.
Является бесспорным, что окрестность единичного радиуса представляет собой не что иное, как образ элемента носителя бинарного отношений.
Определение
Множество
окрестностей единичного радиуса, взятых
для всех элементов носителя
бинарного отношения
,
называется фактор множеством множества
по отношению
и обозначается
.
Таким
образом, фактор множество
можно представить как объединение
окрестностей единичного радиуса, взятых
для всех элементов множества
:
.
Фактор множество
полностью определяет отношение
.
2.21. Свойства бинарных отношений
Рассмотрим свойства, которыми могут обладать бинарные отношения. Допустим, что на некотором множестве как на носителе задано бинарное отношение , . Произвольное бинарное отношение может обладать следующими свойствами.
1.
Свойство рефлексивности
,
т.е. любой элемент из множества
находится сам с собой в отношении
.
Свойство рефлексивности можно записать
в форме соотношений: в инфиксной форме
,
в префиксной форме
,
в постфиксной форме
.
2.
Свойство антирефлексивности
т.е. любой элемент из множества
не
может находиться сам с собой в отношении
.
Или в форме соотношений:
в
инфиксной форме 
,
в
префиксной форме 
,
в
постфиксной форме 
.
2. Свойство симметричности
,
т.е. если элемент носителя
находится в отношении
с элементом носителя
,
то и элемент
находится в отношении
с элементом
.
В форме соотношений это свойство можно
записать:
в
инфиксной форме 
,
в
префиксной форме 
,
в
постфиксной форме 
.
3. Свойство антисимметричности
,
т.е. если элемент
находится
в отношении
с элементом
и одновременно элемент
находится в отношении
с элементом
,
то эти элементы совпадают. В форме
соотношений это свойство выглядит
следующим образом:
в
инфиксной форме 
,
в
префиксной форме 
,
в
постфиксной форме 
.
4. Свойство несимметричности
,
т.е. если элемент
находится в отношении
с элементом
,
то элемент
не находится в отношении
с элементом
.
В форме соотношений это свойство можно
записать:
в
инфиксной форме
,
в префиксной форме
,
в постфиксной
форме
.
5. Свойство транзитивности
,
т.е. для любых элементов
,
и
из множества
если элемент
находится
в отношении
с элементом
,
а элемент
находится в отношении
с элементом
,
то элемент
находится
в отношении
с элементом
.
В форме соотношений это свойство выглядит
следующим образом:
в инфиксной форме
,
в префиксной форме
,
в постфиксной
форме
.
6. Свойство антитранзитивности
,
или в форме соотношений:
в инфиксной форме
,
в префиксной форме
.
Перечисление свойств бинарных отношений совсем не означает, что все бинарные отношения ими обладают. В зависимости от присущих бинарным отношениям свойств они подразделяются на виды, которые будут рассмотрены далее.
Отношение толерантности
Рассмотрим бинарное
отношение
,
.
Это отношение носит название отношения
толерантности (или сходства), если оно
рефлексивно и симметрично, т.е. если
выпорняются свойства:
–
или
;
–
или
.
Отношение толерантности не обладает свойством транзитивности, поэтому его нельзя принимать за отношение эквивалентности. Пренебрежение к отсутствию свойства транзитивности и ошибочное принятие отношения толерантности за отношение эквивалентности может привести к неприятностям.
Пример 2.19
Множество состоит из четырёхбуквенных слов – нарицательных существительных в именительном падеже. Будем называть такие слова сходными, если они отличаются не более чем на одну букву. Известная задача превращения мухи в слона формулируется следующим образом. Найти такую последовательность слов, начинающуюся словом «муха» и оканчивающуюся словом «слон», любые два соседних слова в которой сходны.
Изобразим эту последовательность.
Муха→мура→тура→тара→кара→каре→кафе→кафр→каюр→
каюк→крюк→крок→срок→сток→стон→слон.
Множество с заданным на нём отношением толерантности называется пространство толерантности.