Дискретная математика. Элементы теории, задачи и упражнения. Часть 1. Булгакова И.Н. - 23 стр.

UptoLike

Составители: 

23
Пример 3. На плоскости
R
выбрана некоторая декартова прямоуголь-
ная система координат. На
R
заданы три отношения эквивалентности:
(
)
(
)
(
)
{
}
Z
R
R
Î
-
=
´
Î
=
221121211
,:,,, bababbaa
r
;
(
)
(
)
(
)
{
}
Z
Z
R
R
Î
-
Î
-
´
Î
=
221121212
,:,,, bababbaa
r
;
(
)
(
)
(
)
{
}
Z
R
R
Î
-
+
-
´
Î
=
221121213
:,,, bababbaa
r
.
Найдите фактор-множества для данных отношений эквивалентности.
Решение. Построим фактор-множество для отношения
1
r
. Класс экви-
валентности, порожденный произвольным элементом
(
)
R
Î
21
, aa , имеет вид
(
)
[
]
(
)
(
)
(
)
(
)
{
}
(
)
{
}
Î
Î
Î
Î
Z
R
R
yaaxyxyxaayxaa
2112121
,:,,,,:,,
r
(
)
{
}
=
=
-
=
Î
$
Î
=
kyaaxkyx
21
,:,
Z
R
(
)
{
}
=
-
=
=
Î
$
Î
=
kayaxkyx
21
,:,
Z
R
(
)
{
}
Z
R
Î
Î
-
=
kkaa :,
21
.
Таким образом, в класс эквивалентности, порожденный элементом
(
)
R
Î
21
, aa 10,
21
<
£
Î
aRa , попадают вместе с элементом
(
)
R
Î
21
, aa
элементы, у которых первая координата равна
1
a , а вторая координата от-
личается от
2
a на целое число. Классы эквивалентности, порожденные
элементами с 10,
21
<
£
Î
aRa , не пересекаются и в объединении дают
все множество
R
. Следовательно, фактор-множество
1
/
r
R
можно запи-
сать в виде
(
)
[
)
{
}
1,0,:}:,{/
1
Î
Î
Î
+
=
b
a
b
a
r
Rkk
Z
R
.
Фактор-множество для отношений
32
,
r
r
постройте самостоятельно.
Пример 4. Придумайте минимальное (по числу элементов) отноше-
ние эквивалентности
r
на множестве
{
}
5,4,3,2,1
=
A
так, чтобы
(
)
r
Î
2,1 и
(
)
r
Î
3,2 .
Решение. Отношение эквивалентности рефлексивно, поэтому дан-
ному отношению обязательно должны принадлежать пары
1,1,
(
)
2,2 ,
3,3,
(
)
4,4 ,
(
)
5,5 . Отношение эквивалентности симметрично, поэтому на-
ряду с парами
(
)
2,1 ,
(
)
3,2 данному отношению обязаны принадлежать пары
(
)
1,2 ,
(
)
2,3 . В силу транзитивности отношения
r
ему обязана принадле-
жать вместе с парами
(
)
2,3 ,
(
)
1,2 пара
(
)
1,3 ( и, следовательно,
(
)
3,1 ). Таким
образом, минимальное отношение эквивалентности, которое мы можем
построить, имеет вид
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
3113233212215544332211 ,,,,,,,,,,,,,,,,,,,,,
=
r
.
Пример 5. Докажите, что
{
}
{
}
{
}
{
}
{
}
7643521 ,,,,,,
=
M
разбиение мно-
жества
{
}
7654321 ,,,,,,
=
A
и перечислите все элементы отношения эквива-
лентности
r
, соответствующего разбиению
M
.