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


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


<== предыдущая страница | Следующая страница ==>

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

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

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

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

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

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

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

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

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

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 |

При использовании материала ссылка на сайт Конспекта.Нет обязательна! (0.036 сек.)