50. Отношения эквивалентности, толерантности и порядка

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

Отношение эквивалентности. Отношением эквивалентности b на множестве B называется рефлексивное симметричное транзитивное бинарное отношение.

Отношением эквивалентности являются отношения равенства чисел и множеств. Конгруэнтность треугольников является отношением эквивалентности на множестве треугольников (два треугольника называются конгруэнтными, если они переводятся друг в друга путем смещения и вращения, или, другими словами, если они равны).

Отношение эквивалентности тесно связано с понятием разбиения множества.

Конечную или бесконечную систему непустых подмножеств {B1, B2, ¼} множества B называют разбиением множества B, если

B = B1 È B2 È ¼

И

Bk Ç Bl = Æ при K ¹ L.

Сами подмножества B1, B2, ¼ при этом называются классами разбиений.

Пусть {B1, B2, ¼} разбиение множества B и r отношение на B такое, что для любой пары элементов (B, C) множества B Выполняется (B, C) Î r только в случае, если пара элементов B, C Принадлежит одному классу разбиения. Тогда отношение r является отношением эквивалентности на множестве B.

Соответствие между отношением эквивалентности r на произвольном множестве B и разбиением этого множества на классы является взаимно-однозначным. Поэтому справедливо следующее утверждение.

Пусть на множестве B задано некоторое отношение эквивалентности r. Сформируем для каждого элемента B Î B подмножество Bb = {C | C Î B & C r B}, то есть подмножество, состоящее только из тех элементов множества B, которые находятся в отношении эквивалентности r с элементом B. Тогда семейство подмножеств {Bb}B Î B множества B является разбиением этого множества.

Пусть r является отношением эквивалентности на множестве B, тогда фактормножеством B | r множества M по эквивалентности r называется множество классов эквивалентности.

Отношение толерантности. Отношение эквивалентности определяет свойство одинаковости объектов. Действительно, рефлексивность выражает неразличимость любого объекта с самим собой, симметричность – указывает на то, что свойство одинаковости двух объектов не зависит от порядка их сопоставления. Наконец, транзитивность указывает на то, что если некоторый объект A одинаков с объектами B и C, то объекты B и C одинаковы между собой.

Есть отношение, в котором при наличии свойств рефлексивности и симметричности свойство транзитивности отсутствует. Поэтому может быть, что объект A схож с объектом B и схож с объектом C, но объекты B и C друг с другом не схожи.

Отношение b на множестве B называется Отношением толерантности (сходства), если оно рефлексивно и симметрично.

Пример 5.1. Рассмотрим в качестве примера отношение толерантности преобразование "мухи" в "слона" известного лингвиста Ю. А. Шрейдера. В этом случае множество B состоит из четырехбуквенных слов – нарицательных существительных русского языка в именительном падеже. Слова называются сходными, если они отличаются не более чем на одну букву. Требуется найти последовательность слов, которая начинается словом "муха" и оканчивается словом "слон" и в которой любые два соседних слова сходны.

Решение имеет вид: муха – мура – тура – тара – кара – каре – кафе – кафр – каюр – каюк – крюк – крок – срок – сток – стон – слон.

Вместо множества четырехбуквенных слов можно рассматривать множество четырехразрядных двоичных чисел. При этом считать, что числа сходны, если отличаются не более чем одним разрядом. Последовательность чисел 0000 – 0001 – 0011 – 0111 – 1111 переводит число "0000" в число "1111" и при этом каждая пара соседних двоичных отличается только одним разрядом.

Отношения порядка. Отношение b на множестве B называется отношением квазипорядка (или квазипорядком, или предпорядком), если оно рефлексивно и транзитивно.

Пример 5.2. Пусть задано множество B, состоящее из Q Объектов, каждый из которых характеризуется N числовыми признаками Ki, . Если отношение b на множестве B вводится следующим образом

" B, C Î B ((B, C) Î b Þ Ki(B) ³ Ki(C), ),

То оно является отношением квазипорядка.

Действительно, для вещественных чисел отношение ³ является рефлексивным и транзитивным, поэтому и рассматриваемое отношение будет рефлексивным и транзитивным.

Отношением порядка (частичного порядка) называется отношение квазипорядка обладающее свойством асимметричности.

Множество B, на котором введено отношение порядка b называют упорядоченным (частично упорядоченным) и обозначают (B , b).

Примером упорядоченного множества может служить множество действительных чисел, упорядоченных естественным образом. Граф отношения порядка (частичного порядка) имеет петли, транзитивен (если граф содержит ребра (A, B) и (B, C), то он обязательно содержит и ребро (A, C)), любые две вершины в графе соединены не более чем одним ребром. Пример графа для некоторого отношения порядка приведен на рис. 5.2.

Рис. 5.2. Пример графа, задающего некоторое отношение порядка

Отношением строгого порядка или Строгим порядком B на множестве B называется отношение, обладающее свойствами антирефлексивности и транзитивности.

Иногда в определении отношения строгого порядка включают и свойство асимметричности, однако это свойство определяется свойствами антирефлексивности и транзитивности.

Теорема 5.1. Если отношение b обладает свойствами антирефлексивности и транзитивности, то оно и асимметрично.

Доказательство. Свойство асимметричности предполагает выполнение соотношения b Ç b–1 = Æ. Предположим противное, что это свойство не выполняется, тогда существует по крайней мере одна пара элементов A, B Î B таких, что A B B и B B A. В силу свойства транзитивности отсюда получаем A B A, однако это противоречит свойству антирефлексивности. Следовательно, допущение b Ç b–1 ¹ Æ не является верным и отношение b на множестве B является асимметричным.

Граф отношения строгого порядка не имеет петель, транзитивен и не имеет контуров.

Напомним, что контуром или циклом в ориентированном графе называется последовательность B1 R12 B2 R23 B3, ¼, Bl–1 Rk–1, L, Bl Rlk Bk вершин B1, B2, B3, ¼, Bk–1, Bk и направленных ребер R12, R23, ¼, Rk–1, L, Rl, K, их соединяющих, причем Bk = B1, а все остальные вершины и ребра различны.

Отношением совершенно строгого порядка b на множестве B называется отношение строгого порядка, если для каждой пары не совпадающих элементов Bj, Bi Î B, Bj ¹ Bi выполняется или Bj b Bi или Bi b Bj. Другими словами, если в отношении строгого порядка нет несравнимых элементов, то оно является отношением совершенно строгого порядка.

Отношения >, < на множестве натуральных или действительных чисел являются примерами отношений совершенно строгого порядка.

Граф отношения совершенно строгого порядка b на конечном множестве B = { B1, B2, B3, ¼, Bk–1, Bk} можно представить в виде вертикальной линии. Если элементами множества B являются возрастающие в соответствии с номером индекса действительные числа (Bk > Bk – 1 > ¼ > B2 > B1) и используется отношение >, то такой граф (рис. 5.3) очень наглядно демонстрирует преимущество (доминирование) элемента Bk над всеми остальными, а также положение любого элемента множества b среди остальных.

Рис. 5.3. Граф отношения совершенно строгого порядка

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

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