Типы отношений

Отношение эквивалентности: «элементы х и у одинаковы»; «элементы х и у взаимозаменимы» и т.д.

Отношение эквивалентности определяется тремя свойствами:

а) каждый объект эквивалентен самому себе (рефлексивностика);

б) если объект х эквивалентен объекту у, то и объект у эквивалентен объекту х (симметричность);

в) если объект х эквивалентен объекту у и объект у эквивалентен объекту z, то объект х, эквивалентен объекту z (транзитивность).

Существует и другое, более удобное для приложений определение:

Отношение R на множестве М называется отношением эквивалентности, если существует разбиение множества М на систему не пустых подмножеств (классов) таких, что

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

Из этого определения, в частности, видно, что отношение эквивалентности является основой процедур анализа систем (разбиения целого на части, идентификации объектов и т.д.).

Примеры использования отношения эквивалентности: множество операций разбивается на классы завершенных и незавершенных к определенному сроку; множество исполнителей разбивается по бригадам, цехам и т.д.; множество решений разбивается на подмножества допустимых и недопустимых решений и т.д.

Отношение толерантности

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

Традиционный подход к изучению сходства состоит в том, чтобы сначала определить меру сходства, а затем исследовать взаимное расположение сходных объектов.

Так же, как переход от расплывчатого понятия “одинаковость” к точно определенному типу отношений сопровождался введением нового термина “эквивалентность”, математическое отношение, соответствующее нашему интуитивному представлению о сходстве получило название “толерантность”.

Отношение R на множестве М называется толерантностью, если оно рефлексивно и симметрично.

Естественность такого определения видна из того, что всякий объект заведомо схож сам с собой (рефлективность). Ясно также, что два объекта схожи или несхожи независимо от порядка, в котором мы их рассматриваем (симметричность).

(Поскольку одинаковость частный случай сходства, то эквивалентность – частный случай толерантности).

Пример 1. Множество М состоит из 4-х буквенных русских слов – нарицательных существительных в именительном падеже. Будем называть такие слова сходными, если они отличаются не более, чем на одну букву. Известная задача «Превращение мухи в слона» точных терминах формулируется так:

Найти такую последовательность слов, начинающуюся словом «муха» и кончающуюся словом «слон», любые два соседних слова в которой сходны (в смысле вышеприведенного определения).

Отношение порядка

Речь идет о ситуациях, когда объекты некоторого множества соотносятся по взаимному старшинству, по важности, по «первичности» и т.д. подобные отношения, по видимому, не симметричны.

Поскольку имеется возможность двоякого введения упорядочивания (как в случае построчного неравенства <=, так и строчного неравенства <), то имеются отношения строчного и нестрочного порядка.

Отношение R на множестве М называется отношением строгого порядка, если оно антирефлексивно и транзитивно.

Отношение R строчного порядка:

Имеет интерпретации: «элемент х предпочтительнее у», «х больше у», «х предшествует у», «х включает в себя у».