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

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

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

Определение. Говорят, что на множестве 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.