Дискретная математика. Элементы теории, задачи и упражнения. Часть 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
. 
         Пример 3. На плоскости � выбрана некоторая декартова прямоуголь-
ная система координат. На � заданы три отношения эквивалентности:
          �1 � ���a1 , a 2 �, �b1 , b2 �� � � � � : a1 � b1 , a 2 � b2 � � � ;
          � 2 � ���a1 , a 2 �, �b1 , b2 �� � � � � : a1 � b1 � � , a 2 � b2 � � �;
          � 3 � ���a1 , a 2 �, �b1 , b2 �� � � � � : a1 � b1 � a 2 � b2 � � �.
         Найдите фактор-множества для данных отношений эквивалентности.
         Решение. Построим фактор-множество для отношения �1 . Класс экви-
валентности, порожденный произвольным элементом �a1 , a 2 � � � , имеет вид
          ��a1 , a2 �� � �� x, y � � � : ��a1 , a2 �, � x, y �� � �1� � �� x, y � � � : x � a1 , a2 � y � � � �
          � �� x, y � � � : �k � � x � a1 , a 2 � y � k � �
          � �� x, y � � � : �k � � x � a1 , y � a 2 � k � �
          � ��a1 , a 2 � k � � � : k � � � .
         Таким образом, в класс эквивалентности, порожденный элементом
�a1 , a 2 � � � a1 � R, 0 � a 2 � 1 , попадают вместе с элементом �a1 , a 2 � � �
элементы, у которых первая координата равна a1 , а вторая координата от-
личается от a 2 на целое число. Классы эквивалентности, порожденные
элементами с a1 � R, 0 � a 2 � 1 , не пересекаются и в объединении дают
все множество � . Следовательно, фактор-множество � / �1 можно запи-
сать в виде
                             � / �1 � �{�� , � � k � : k � � } : � � R, � � �0,1�� .
         Фактор-множество для отношений � 2 , � 3 постройте самостоятельно.

        Пример 4. Придумайте минимальное (по числу элементов) отноше-
ние эквивалентности � на множестве � � �1,2,3,4,5� так, чтобы �1,2 � � � и
�2,3� � � .
        Решение. Отношение эквивалентности рефлексивно, поэтому дан-
ному отношению обязательно должны принадлежать пары 1,1, �2,2 � ,
3,3, �4,4 � , �5,5� . Отношение эквивалентности симметрично, поэтому на-
ряду с парами �1,2� , �2,3� данному отношению обязаны принадлежать пары
�2,1� , �3,2� . В силу транзитивности отношения � ему обязана принадле-
жать вместе с парами �3,2� , �2,1� пара �3,1� ( и, следовательно, �1,3� ). Таким
образом, минимальное отношение эквивалентности, которое мы можем
построить, имеет вид
        � � ��1,1�, �2 ,2�, �3,3�, �4 ,4�, �5 ,5�, �1,2�, �2 ,1�, �2 ,3�, �3,2�, �3,1�, �1,3�� .

     Пример 5. Докажите, что � � ��1�, �2 ,5�, �3�, �4 ,6 ,7�� – разбиение мно-
жества � � �1,2 ,3,4 ,5 ,6 ,7� и перечислите все элементы отношения эквива-
лентности � , соответствующего разбиению � .

                                                      23

Страницы