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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

делится на

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

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

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

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

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

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