Самостоятельная работа

1. На множестве натуральных чисел заданы следующие отношения:

а) (a,b)  ρ₁  ; б) (a,b)  ρ₂  a < b. Выясните их свойства.

2. Выясните свойства следующего отношения, заданного на множестве всех точек плоскости: (А,В)  ρ  А и В симметричны относительно данной точки О.

3. На множестве всех прямых плоскости задано следующее отношение: (a,b)  ρ  a  b. Выясните свойства этого отношения.

4. Выясните свойства следующих отношений

а) {(x, y) | x, y  Z  x2 = y2}; б) {(x, y) | x, y  Z  x + y = 1};

в) {(x, y) | x, y  Z  }; г) {(x, y) | x, y  Z  x2 + y2 = 1}.

5. Докажите, что симметричное и антисимметричное бинарное отношение является транзитивным.

6. Докажите, что бинарное отношение асимметрично тогда и только тогда, когда оно антирефлексивно и антисимметрично.

7. Выясните свойства следующих отношений:

а) {(а,а), (b,b), (а,b)} на множестве {a,b}; б) {(а,а), (b,b), (а,b)} на множестве {a,b,c};

в) {(x, y) | x, y  N  x = y + 2}; г) {(а,b)} на множестве {a,b};

д) {(а,b)} на множестве {a,b,c};

е) {(А_i, A_k) | А_i, A_k - вершины правильного шестиугольника и угол А_iОA_k не превышает 120⁰;

ж) {(а₁,b₁), (a₂,b₂) | а_i, b_i  N, i = 1,2, а₁ + b₂  a₂ + b₁};

з) {(а₁,b₁), (a₂,b₂) | а_i  Z, b_i  N, а₁b₂  a₂b₁}.

Задачи повышенной трудности

Выясните свойства отношений:

1. {(x, y) / x, y  Z и x, y оба четны и x  y, или x, y оба нечетны и x  y или x четно, а y нечетно}.

2. Пусть отношение  симметрично и транзитивно. Будет ли оно в этом случае рефлексивным?

Тема 7. Операции над бинарными отношениями на множестве. Отношение эквивалентности

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)}. Перебрав все возможные разбиения М и строя соответствующую разбиению эквивалентность, мы получим все эквивалентности, которые могут быть заданы на М.