Главная > Математика > Дискретная математика. Алгоритмы и программы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.4. Отношение эквивалентности

Бинарное отношение определенное на множестве называется отношением эквивалентности, если оно удовлетворяет свойствам рефлексивности, симметричности и транзитивности:

Все элементы из множества эквивалентные данному элементу образуют множество которое называется классом эквивалентности. Два различных класса эквивалентности не могут иметь какого-либо общего элемента, в противном случае такие классы совпадают, что следует из свойств 1—3. Таким образом, определенное на множестве отношение эквивалентности выполняет разложение его на непересекающиеся классы эквивалентности, т.е. где

Пример. Пусть множество треугольников. Определим на бинарное отношение. Будем считать, что для треугольников Да, выполняется отношение если они подобные. Ясно, данное отношение является отношением эквивалентности, так как свойства 1—3 выполняются для подобных треугольников. Введенное отношение разбивает множество треугольников на классы эквивалентности подобных треугольников.

Пример. Пусть множество -мерных векторов. Определим на бинарное отношение. Будем полагать, что для выполняется отношение а если они колинеарные. Данное отношение является отношением эквивалентности, так как свойства 1—3 выполняются для колинеарных векторов. Множество векторов под действием введенного отношения разбивается на классы эквивалентности колинеарных векторов.

Пример. Пусть Определим на бинарное отношение. Будем полагать, что для выполняется отношение если они имеют одинаковые остатки от деления на целое положительное число Данное отношение является отношением эквивалентности. Множество под действием введенного отношения разбивается на классы эквивалентности чисел с одинаковыми остатками от деления на

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

<< Предыдущий параграф Следующий параграф >>
Оглавление