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

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

Определение бинарного отношения

Определение. Говорят, что на множестве X задано бинарное отношение R, если задано подмножество декартова произведения (т.е. ).

Пример 2. Пусть Зададим на Х следующие отношения:

– отношение равенства;

– отношение предшествования;

делится на – отношение делимости.

Все эти отношения заданы с помощью характеристического свойства. Ниже перечислены элементы этих отношений:

Тот факт, что пара (x, y) принадлежит данному отношению R,будем записывать: или xRy. Например, для отношения Q запись 4 Q 2 означает, что 4делится на 2 нацело, т.е.

Областью определения бинарного отношения R называется мно-жество

Областью значений называется множество

Так, для отношения Р из примера 2 областью определения является множество , а областью значений – .

Бинарное отношение можно задать, указав характеристическое свойство или перечислив все его элементы. Существуют и более наглядные способы задания бинарного отношения: график отношения, схема отношения, граф отношения, матрица отношения.

График отношения изображается в декартовой системе координат; на горизонтальной оси отмечается область определения, на вертикальной – область значений отношения; элементу отношения (х,у) соответствует точка плоскости с этими координатами. На рис. 1.7, а приведен график отношения Q примера 2.

Схема отношения изображается с помощью двух вертикальных прямых, левая из которых соответствует области определения отношения, а правая – множеству значений отношения. Если элемент (х,у) принадлежит отношению R, то соответствующие точки из и соединяются прямой. На рис. 1.7, б приведена схема отношения Q из примера 2.

Граф отношения строится следующим образом. На плоскости в произвольном порядке изображаются точки – элементы множества Х. Пара точек х и у соединяется дугой (линией со стрелкой) тогда и только тогда, когда пара (х,у) принадлежит отношению R. На рис. 1.8, а приведен граф отношения Q примера 2.

Матрица отношения – это квадратная таблица, каждая строка и столбец которой соответствует некоторому элементу множества Х. На пересечении строки х и столбца у ставится 1, если пара ; все остальные элементы матрицы заполняются нулями. Элементы матрицы нумеруются двумя индексами, первый равен номеру строки, второй - номеру столбца. Пусть . Тогда матрица отношения имеет n строк и n столбцов, а ее элемент определяется по правилу:

На рис.1.8, б приведена матрица отношения Q примера 2.

Бинарные отношения делятся на типы в зависимости от свойств, которыми они обладают. Рассмотрим следующие отношения на множестве

делится на

Отношение R на множестве Х называется рефлексивным, если для всех выполняется условие . Среди приведенных выше отношений рефлексивными являются отношение L (т.к. неравенство справедливо при всех ) и отношение М (т.к. разность делится на 3, значит, пара принадлежит отношению М при всех ).

Отношение R на множестве Х называется антирефлексивным, если условие не выполняется ни при одном . Примером антирефлексивного отношения является отношение G (неравенство не выполняется ни при каких значениях х, следовательно, ни одна пара не принадлежит отношению G). Отметим, что отношение К не является рефлексивным и не является антирефлексивным .

Отношение R на множестве Х называется симметричным, если из условия следует . Симметричными являются отношения М (если делится на 3, то и делится на 3) и К (если , то и ).

Отношение R на множестве Х называется несимметричным, если для любых из условия следует . Несимметричным является отношение G, т.к. условия и не могут выполняться одновременно (только одна из пар или принадлежит отношению G).

Отношение R на множестве Х называется антисимметричным, если для любых из условия и следует . Антисимметричным является отношение L, т.к. из одновременного выполнения и следует .

Отношение R на множестве Х называется транзитивным, если для любых из одновременного выполнения условий и следует . Отношения G, L, M являются транзитивными, а отношение К нетранзитивно: если то и , но , то есть выполняются условия и , но .

Дата добавления: 2014-12-07