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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

22
Пример 2. Пусть
m
– некоторое натуральное число. Проверить, яв-
ляется ли отношением эквивалентности следующее бинарное отношение
на множестве целых чисел:
(
)
{
}
mнаделитсяyxyx
-
´
Î
=
:,
Z
Z
r
.
Построить фактор-множество
r
Z
.
Решение. Проверим три основных свойства для отношения эквива-
лентности.
1. Рефлексивность.
Для произвольного
Z
Î
x
разность
(
)
r
Î
Þ
×
=
=
-
xxmxx ,00 .
2. Симметричность.
Пусть
(
)
(
)
.,,
r
r
Î
Þ
×
-
=
-
Î
$
Þ
×
=
-
Î
$
Þ
Î
xymkxykmkyxkyx
Z
Z
3. Транзитивность.
Пусть
(
)
(
)
Þ
×
=
-
×
=
-
Z
Î
$
Þ
Î
Î
mnzy,mkyxn,kz,y,y,x
r
r
(
)
(
)
(
)
r
Î
Þ
×
=
-
Z
Î
+
=
$
Þ
×
+
=
-
Z
Î
$
Þ
z,xmrzxmkrmnkzxn,k
.
Итак, исследуемое бинарное отношение является отношением экви-
валентности. Построение классов эквивалентности начнем с класса экви-
валентности, порожденного
Z
Î
0
[
]
{
}
{
}
=
-
Î
=
»
Î
=
mнаделитсяyyyy 0:0:0
Z
Z
{
}
{
}
=
×
-
=
Î
$
Î
=
×
=
-
Î
$
Î
=
mkykymkyky
Z
Z
Z
Z
:0:
{
}
,...,,...,3,3,2,2,,,0 kmkmmmmmmm
-
-
-
-
=
.
Если
1
=
m
, то данный класс эквивалентности
[
]
Z
=
0 , других клас-
сов эквивалентности просто не существует, и
[
]
{
}
0/
=
r
Z
. Если
1
>
m
, то
существуют элементы, не попавшие в построенный класс, например, эле-
мент 1. Построим класс эквивалентности, порожденный 1
[
]
{
}
{
}
=
-
Î
=
»
Î
=
mнаделитсяyyyy 1:1:1
Z
Z
{
}
{
}
=
×
-
=
Î
$
Î
=
×
=
-
Î
$
Î
=
mkykymkyky 1:1:
Z
Z
Z
Z
{
}
,...1,1,...,31,31,21,21,1,1,1 kmkmmmmmmm
+
-
+
-
+
-
+
-
=
.
При
2
=
m
построенные два класса эквивалентности при объедине-
нии дают все множество
,
Ζ
и поэтому построение классов эквивалентно-
сти закончено, в противном случае существует элемент, например 3, не
попавший ни в один из этих классов эквивалентности, и нужно перейти к
построению класса эквивалентности, порожденного 2. Продолжая данный
процесс, при любом
m
мы построим классы эквивалентности
[
]
[
]
[
]
1,...,1,0
-
m ,
которые не пересекаются и при объединении дают все множество
Z
. Та-
ким образом,
{
}
{
}
1,...,2,1:,...,,...,,,/
-
=
+
-
+
-
=
mnkmnkmnmnmnn
r
Z
. 
      Пример 2. Пусть m – некоторое натуральное число. Проверить, яв-
ляется ли отношением эквивалентности следующее бинарное отношение
на множестве целых чисел:
                            � � �� x, y � � � � � : x � y делится на m� .
      Построить фактор-множество � / � .
      Решение. Проверим три основных свойства для отношения эквива-
лентности.
      1. Рефлексивность.
      Для произвольного x � � разность x � x � 0 � 0 � m � � x, x � � � .
      2. Симметричность.
      Пусть
      � x , y � � � � �k � � x � y � k � m � � k � � y � x � � k � m � � y , x � � � .
      3. Транзитивность.
      Пусть
      � x , y � � � , � y , z � � � � �k , n � � x � y � k � m , y � z � n � m �
      � �k , n � � x � z � �k � n � � m � �r � �k � m� � � x � z � r � m � � x , z � � � .
      Итак, исследуемое бинарное отношение является отношением экви-
валентности. Построение классов эквивалентности начнем с класса экви-
валентности, порожденного 0 � �
      �0� � �y � � : 0 � y� � �y � � : 0 � y делится на m� �
      � �y � � : �k � � 0 � y � k � m� � �y � � : �k � � y � � k � m� �
      � �0, m,� m,2m,�2m,3m,�3m,..., km,�km,...� .
      Если m � 1 , то данный класс эквивалентности �0� � � , других клас-
сов эквивалентности просто не существует, и � / � � ��0��. Если m � 1 , то
существуют элементы, не попавшие в построенный класс, например, эле-
мент 1. Построим класс эквивалентности, порожденный 1
      �1� � �y � � : 1 � y� � �y � � : 1 � y делится на m� �
      � �y � � : �k � � 1 � y � k � m� � �y � � : �k � � y � 1 � k � m� �
      � �1,1 � m,1 � m,1 � 2m,1 � 2m,1 � 3m,1 � 3m,...,1 � km,1 � km,...�.
      При m � 2 построенные два класса эквивалентности при объедине-
нии дают все множество Ζ , и поэтому построение классов эквивалентно-
сти закончено, в противном случае существует элемент, например 3, не
попавший ни в один из этих классов эквивалентности, и нужно перейти к
построению класса эквивалентности, порожденного 2. Продолжая данный
процесс, при любом m мы построим классы эквивалентности
                                               �0�, �1�,..., �m � 1� ,
которые не пересекаются и при объединении дают все множество � . Та-
ким образом,
                � / � � ��n, n � m, n � m,..., n � km, n � km,...� : n � 1,2,..., m � 1�.


                                           22

Страницы