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

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

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

Бинарные отношения

Пусть среди трех людей: Андрей (А), Василий (В) и Сергей (С) двое знакомы друг с другом (Андрей и Василий) и знают третьего – Сергея, но Сергей их не знает. Как описать отношения между этими людьми?

Имеем исходное множество Х = {А, В, С}. Далее из элементов множества Х составим упорядоченные пары:
(А, В), (В, А), (А, С), (В, С). Это множество пар и описывает связи между элементами множества X. Кроме того, множество этих пар есть подмножество декартова произведения X ´ X.

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

Пример 1. Пусть X = {1, 2, 3, 4}. Зададим на X следующие отношения:

Т = {(х, у) | х, у Î Х; х = у} – отношение равенства;

Р = {(х, у) | х, у Î Х; х = у - 1} – отношение

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

Q = {(х, у) | х, у Î Х; х делится на у} – отношение

делимости.

Все эти отношения заданы с помощью характеристического свойства. Перечислим элементы этих отношений для заданного множества X = {1,2,3,4}:

Т = {(1,1), (2,2), (3,3), (4,4)};

P = {(1,2), (2,3), (3,4) };

Q = {(4,4), (4,2), (4,1), (3,3), (3,1), (2,2), (2,1), (1,1)}.

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

Областью определения D_r бинарного отношения R называется мно­жество D_R = {x | (х, у) Î R}.

Областью значений Е_R бинарного отношения R называется множество Е_R = {у| (х, у) Î R}.

В примере для отношения Р областью определения является мно­жество D_R = {1,2,3}, а областью значений является мно­жество Е_R = {2,3,4}.

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

График отношения изображается в декартовой системе координат: на горизонтальной оси отмечается область определения, на вертикальной - об­ласть значений отношения. Элементу отношения (х, у) соответствует точка плоскости с этими координатами.

a б

Рис. 1.8. График отношения Q (а) и схема отношения Q (б)

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

Граф отношения R Ì X ´ X строится следующим образом. На плоско­сти в произвольном порядке изображаются точки - элементы множества X. Пара точек х и у соединяется дугой (линией со стрелкой) тогда и только тогда, когда пара (х, у) принадлежит отношению R.

Матрица отношения R Ì X ´ X – это квадратная таблица, каждая строка и столбец которой соответствует некоторому элементу множества X. На пересечении строки х и столбца у ставится 1, если пара (х, у) Î R; все остальные элементы матрицы заполняются нулями. Элементы матрицы нуме­руются двумя индексами, первый равен номеру строки, второй – номеру столбца.

Пусть X = {х₁, х₂, …, х_n} . Тогда матрица отношения
R Ì X ´ X имеет n строк и n столбцов, а ее элемент r_ij определяется по правилу:

rij =

1, если (x_i, y_j) Î R, где i = l, 2, ..., n; j = l, 2, ..., n.

0, если (x_i, y_j) Ï R.

 

 

Рис. 1.9. Граф отношения Q (а) и матрица отношения Q (б)

1. Отношение R на множестве X называется рефлексивным, если для всех х Î X выполняется условие (х, х) Î R. Отношение R на множестве Х называется нерефлексивным, если ус­ловие (х, х) Î R не выполняется хотя бы при одном х Î X .

2. Отношение R на множестве X называется симметричным, если из усло­вия (х, у) Î R следует
(у, х) Î R. Отношение R на множестве X называется несимметричным, если для любых х, у Î X из условия (х, y) Î R следует (у, х) Ï R.

3. Отношение R на множестве X называется транзитивным, если для лю­бых х, у, z Î R из одновременного выполнения условий (x, y) Î R и (у, z) Î R следует (х, z) Î R .

Пример. Рассмотрим следующие отношения на множестве X = {1,2,3,4,5,6,7}:

G = {(x, y) | х, у Î Х; х > у};

L = {(х, у) | х, у Î Х; х £ у};

M = {(x, y) | х, у Î X; (х - у) делится на 3};

К = {(х, y) | х, у Î Х; х² + у² £ 20}.

Исследуем, какими свойствами они обладают.

Среди приведенных в примере отношений рефлексивнымиявляются отношение L (т. к. х £ х справедливо при всех х Î X) и отношение М (т. к. х - х = 0 делится на 3, поэтому пара (х, х) принадлежит отношению М при всех х Î X).

Симметричными являются отношения М (если х - у делится на 3, то и у - х делится на 3) и К (если х² + у² £ 20, то и у² + х² £ 20).

Транзитивными являются отношения G, L, М.