Отношение эквивалентности: «элементы х и у одинаковы»; «элементы х и у взаимозаменимы» и т.д.
Отношение эквивалентности определяется тремя свойствами:
а) каждый объект эквивалентен самому себе (рефлексивность);
б) если объект х эквивалентен объекту у, то и объект у эквивалентен объекту х (симметричность);
в) если объект х эквивалентен объекту у и объект у эквивалентен объекту z, то объект х, эквивалентен объекту z (транзитивность).
Существует и другое, более удобное для приложений определение:
Отношение R на множестве М называется отношением эквивалентности, если существует разбиение множества М на систему не пустых подмножеств (классов) таких, что
и соотношение xRy выполняется лишь в тех случаях, когда элементы х и у принадлежат одному общему классу разбиения.
Из этого определения, в частности, видно, что отношение эквивалентности является основой процедур анализа систем (разбиения целого на части, идентификации объектов и т.д.).
Примеры использования отношения эквивалентности: множество операций разбивается на классы завершенных и незавершенных к определенному сроку; множество исполнителей разбивается по бригадам, цехам и т.д.; множество решений разбивается на подмножества допустимых и недопустимых решений и т.д.
Если эквивалентность (одинаковость) обозначает их полную взаимозаменяемость в некоторой ситуации, то сходство – это частная взаимозаменяемость, т.е. возможность взаимной замены с некоторыми (допустимыми в данной ситуации) потерями, с допустимым риском.
Традиционный подход к изучению сходства состоит в том, чтобы сначала определить меру сходства, а затем исследовать взаимное расположение сходных объектов.
Так же, как переход от расплывчатого понятия “одинаковость” к точно определенному типу отношений сопровождался введением нового термина “эквивалентность”, математическое отношение, соответствующее нашему интуитивному представлению о сходстве получило название “толерантность”.
Отношение R на множестве М называется толерантностью, если оно рефлексивно и симметрично.
Естественность такого определения видна из того, что всякий объект заведомо схож сам с собой (рефлективность). Ясно также, что два объекта схожи или несхожи независимо от порядка, в котором мы их рассматриваем (симметричность).
(Поскольку одинаковость частный случай сходства, то эквивалентность – частный случай толерантности).
Пример 1. Множество М состоит из 4-х буквенных русских слов – нарицательных существительных в именительном падеже. Будем называть такие слова сходными, если они отличаются не более, чем на одну букву. Известная задача «Превращение мухи в слона» точных терминах формулируется так:
Найти такую последовательность слов, начинающуюся словом «муха» и кончающуюся словом «слон», любые два соседних слова в которой сходны (в смысле вышеприведенного определения).