double arrow

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



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

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

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

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

Имеем исходное множество Х = {А, В, С}. Далее из элементов множества Х составим упорядоченные пары:
(А, В), (В, А), (А, С), (В, С). Это множество пар и описывает связи между элементами множества 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.

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

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

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

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

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

a б

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

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



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

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

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

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

0, если (xi, yj) Ï 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) | х, у Î Х; х2 + у2 £ 20}.

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

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

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

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



Сейчас читают про: