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

Дата добавления: 2014-11-24 | Просмотров: 1572

Dom T = {x | ($y)((x, y)ÎT)} – область определения Т;

Im T = {y | ($x)((x, y)ÎT)} – область значений Т; Dom T È Im T – область отношения Т.

Композиция отношений: = {(x, y) | ($z)((x, z)ÎT Ù (z, y)ÎS)}.

– инверсия отношения Т; = {(x, y) | (y, x)ÎT}.

Известно, что ; ; .

Отношение Т на множестве М ¹ Æ называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Отношение эквивалентности Т разбивает множество М на Т-эквивалентные классы элементов (фактор-множество ).

Обратно, если множество М разбито на непересекающиеся подмножества, то можно так определить на нем отношение эквивалентности Т, что совпадет с исходным разбиением множества.

Поэтому легко решаются задачи типа: на М = {a,b,c,d} определите все отношения эквивалентности.

Исходя из произвольного разбиения М = {a}È{b,c}È{d}, строим соответствующую этому разбиению эквивалентность: Т = {(a,a), (b,b), (c,c), (b,c), (c,b), (d,d)}. Перебрав все возможные разбиения М и строя соответствующую разбиению эквивалентность, мы получим все эквивалентности, которые могут быть заданы на М.