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

Рефлексивность. Пусть отношение b задано на множестве B. Тогда отношение b называется рефлексивным, если "B Î B Þ B B B, то есть в множестве B любой его элемент находится в отношении b сам с собой.

Противоположным свойству рефлексивности бинарного отношения является свойство антирефлексивности. Оно предполагает, что ни один элемент множества B не находится в отношении b сам с собой.

Очевидно, что бинарное отношение может быть не рефлексивным и не антирефлексивным, если часть элементов множества B находится в отношении b сами с собой, а часть – нет.

Симметричность. Бинарное отношение b на множестве B называется симметричным, если "B, C Î B (B B C Þ C B B), то есть с каждой упорядоченной парой элементов множества B оно содержит и упорядоченную пару с переставленными элементами. Очевидно, что в случае симметричного отношения выполняется равенство b = b–1.

Противоположным свойству симметричности является свойство асимметричности. Бинарное отношение b асимметрично, если "B, C Î B ((B, C) Î b Þ (C, B) Ï b), то есть, если любая упорядоченная пара элементов (B, C) множества B принадлежит отношению b, то пара элементов с переставленными элементами (C, B) этому отношению не принадлежит. Ясно, что асимметричное отношение b не имеет с обратным отношением b–1 ни одной общей пары, что можно записать в виде свойства b Ç b–1 = Æ.

Если бинарное отношение b удовлетворяет более слабому свойству "B, C Î B (B B C & C B B Þ C = B), чем асимметричность, то оно называется антисимметричным. Таким образом, упорядоченная пара элементов с переставленными компонентами может принадлежать исходному бинарному отношению, но только в том случае, когда элементы пары одинаковы.

В любом бинарном отношении g можно выделить симметричную часть бинарного отношения gS = g Ç g–1 и асимметричную часть gA = g \ gS.

Транзитивность. Отношение b на множестве B называется транзитивным, если "B, C, D Î B (B B C & C B D Þ B B D), то есть если оно содержит произведение любых двух примыкающих пар, принадлежащих отношению.

Отметим, что обратное отношение b–1 транзитивного бинарного отношения b транзитивно. Действительно, в транзитивном отношении b для любых двух примыкающих пар (B, C), (C, D) существует и пара элементов (B, D), принадлежащая этому же отношению. А это означает, что в обратном отношении b–1 любые две примыкающие пары отношения B всегда порождают две примыкающие пары элементов с переставленными компонентами и измененным порядком следования пар: (D, C), (C, B). Таким образом, произведение двух примыкающих пар в отношении b–1 имеет те же элементы, что и произведение примыкающих пар в отношении b, но с измененным порядком следования. Следовательно, отношение b–1 транзитивно и все его упорядоченные пары элементов получены путем перестановки элементов в парах исходного бинарного отношения b, то есть в соответствии с операцией обращения отношений.

Примерами транзитивных отношений являются отношения >, ³, <, £ на множествах целых или действительных чисел.

Линейность. Если для бинарного отношения b на множестве B и любых элементов B и C множества B выполняется условие "B, C Î B Þ B B C È C B B, то отношение называется линейным. Другими словами, если для любой неупорядоченной пары элементов (B, C) множества B выполняется B B C Или C B B, то отношение b является линейным. Примерами линейных отношений являются отношения ³ и £ на множествах целых и действительных чисел.

Ацикличность. Пусть задано бинарное отношение b на множестве B. Последовательность элементов B1, B2, ¼, Bl Î B таких, что B1 b B2 b ¼ b Bl = B1 называется циклом длины L по бинарному отношению b. Минимальное число L, при котором существует такая последовательность элементов, называется минимальной длиной цикла бинарного отношения b. Бинарное отношение называется ацикличным, если ни для какого L > 1 не существует цикла длиной L. В тех случаях, когда необходимо оперировать длинами циклов ацикличных бинарных отношений, минимальную длину цикла принимают равной бесконечности. Граф ацикличного бинарного отношения не имеет циклов (или контуров), то есть последовательностей

B1 R12 B2 R23 B3, ¼, Bl–1 Rl–1, l, Bl rl1 B1,

Где B1, B2, B3, ¼, Bl–1, Bl – последовательность вершин графа, причем все вершины графа различны; L – число вершин графа;

R12, R23, ¼, Rl–1, L, Rl, 1 – последовательность различных направленных ребер графа, причем ребро Rkj (K = 1, 2, ¼, L; J = 2, 3, ¼, L, 1) соединяет вершины K и J и направлено от вершины K к вершине J.

< Предыдущая		Следующая >