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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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