Способы задания бинарных отношений

Для задания бинарных отношений можно использовать любые способы задания множеств (например, список пар, для которых данное отношение выполняется).

Бинарные отношения, определяемые на конечном множестве обычно задаются списком (пар элементов), бинарной матрицей, или ориентированным графом.

Матрица бинарного отношения, заданного на множестве  это квадратная матрица С порядка n, в которой  (где i – номер строки, j - номер столбца) определяется так:

Для любого множества М отношение Е, заданное единичной матрицей, в которой по главной диагонали стоят “1”, а остальные “0” – называется отношением равенства.

Поскольку отношения на М задаются подмножествами множества , для них можно определить те же операции, что и над множествами.

Например, отношение “находиться на разном расстоянии от начала координат” является дополнением отношения “находиться на одинаковом расстоянии от начала координат”. Отношение “ ” является объединением отношений “<” и “=”.

Определим еще одну операцию над множествами.

Отношение называется обратным к отношению R, если

.

Например, отношение “ ” обратное к отношению “ ”.

Из определения следует, что .

Свойства бинарных отношений

Отношение R на М называется рефлексивным, если для любого  выполняется . Главная диагональ матрицы такого отношения содержит только единицы.

Отношение R на М называется антирефлексивным, если ни для какого  не выполняется. Главная диагональ матрицы отношения содержит только нули.

Отношение R на М называется симметричным, если для любой пары  из aRb следует bRa (иначе говоря, для любой пары отношение R выполняется в обе стороны или не выполняется вообще). Матрица симметричного отношения – симметрична относительно главной диагонали:  для всех i, j, т.е.

Отношение R на М называется антисимметричным, если из того, что (из aRb следует bRa) следует  (т. е. ни для каких различных элементов множества М отношение R не выполняется). Матрица антисимметричного отношения не имеет ни одного симметричного относительно главной диагонали единичного элемента.

R симметрично тогда и только тогда, когда .

Отношение R на М называется транзитивным, если для любых a, b, c из множества М из того, что выполняется aRb и bRcследует, чтоaRc.

Для любого отношения R отношение , называемое транзитивным замыканием R, определяется следующим образом:

, если в М существует цепочка из n элементов , в которой между соседними элементами выполнено отношение R:

Если R – транзитивно, то по определению транзитивного замыкания: .

Отношение эквивалентности

Отношение R на М называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Равенство – это минимальное отношение эквивалентности в том смысле, что при удалении любой пары из Е (т. е. любой единицы на диагонали матрицы Е) оно перестает быть рефлексивным и, следовательно, уже не является эквивалентным.

Пусть на множестве М задано отношение эквивалентности R. Осуществим построение классов эквивалентности, на которые разбивается множество М этим отношением.

Выберем элемент  и образуем класс (подмножество М) , состоящий из  и всех элементов, эквивалентных ; затем выберем элемент , и образуем класс , состоящий из  и всех элементов, эквивалентных  и т. д. Получится система классов  (возможно бесконечная) такая, что любой элемент из М входит хотя бы в один класс, т. е. .

Эта система обладает свойствами:

1) она образует разбиение, т. е. классы попарно не пересекаются;

2) любые два элемента из одного класса эквивалентны;

3) любые два элемента из разных классов неэквивалентны.

Мощность системы классов эквивалентности называется индексом разбиения.

С другой стороны, любое разбиение М на классы определяет некоторое отношение эквивалентности.

Отношение порядка

Отношение называется отношением нестрогогопорядка, если оно рефлексивно, антисимметрично, транзитивно.

Отношение называется отношением строгого порядка, если оно антирефлексивно, антисимметрично, транзитивно.

Оба типа таких отношений называются отношениями порядка.

Элементы a и b сравнимы по отношению порядка R, если выполняется aRb или bRa.

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

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