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

UptoLike

3. Транзитивность.
Пусть
(
)
(
)
=
=
Ζ
mnzy,mkyxn,kz,y,y,x
ρ
ρ
(
)
(
)
(
)
ρ
=
Ζ
+
=
+
=
Ζ
z,xmrzxmkrmnkzxn,k
Итак, исследуемое бинарное отношение является отношением экви-
валентности. Построение классов эквивалентности начнем с класса экви-
валентности, порожденного
Ζ
0
[
]
{
}
{
}
=
=
=
mнаделитсяyyyy 0:0:0
Ζ
Ζ
{
}
{
}
=
=
=
=
=
mkykymkyky
Ζ
Ζ
Ζ
Ζ
:0:
{
}
,...,,...,3,3,2,2,,,0 kmkmmmmmmm
=
.
Если
1
=
m
, то данный класс эквивалентности
[
]
Ζ
=
0
, других классов эк-
вивалентности просто не существует , и
[
]
{
}
0/
=
ρ
Ζ
. Если
1
>
m
, то суще-
ствуют элементы, не попавшие в построенный класс, например, элемент 1.
Построим класс эквивалентности, порожденный 1
[
]
{
}
{
}
=
=
=
mнаделитсяyyyy 1:1:1
Ζ
Ζ
{
}
{
}
=
=
=
=
=
mkykymkyky 1:1:
Ζ
Ζ
Ζ
Ζ
{
}
,...1,1,...,31,31,21,21,1,1,1 kmkmmmmmmm
+
+
+
+
=
.
При
2
=
m
построенные два класса эквивалентности при объединении да-
ют все множество
Ζ
и поэтому построение классов эквивалентности за -
кончено, в противном случае существует элемент, например 3, не попав-
ший ни в один из этих классов эквивалентности, и нужно перейти к по -
строению класса эквивалентности, порожденного 2. Продолжая данный
процесс, при любом
m
мы построим классы эквивалентности
[
]
[
]
[
]
1,...,1,0
m
,
которые не пересекаются и при объединении дают все множество
Ζ
. Та -
ким образом,
{
}
{
}
1,...,2,1:,...,,...,,,/
=
+
+
=
mnkmnkmnmnmnn
ρ
Ζ
.
Пример 3. На плоскости
Ρ
выбрана некоторая декартова прямо-
угольная система координат. На
Ρ
заданы три отношения эквивалентно-
сти:
(
)
(
)
(
)
{
}
Ζ
Ρ
Ρ
=
×
=
221121211
,:,,, bababbaa
ρ
;
(
)
(
)
(
)
{
}
Ζ
Ζ
Ρ
Ρ
×
=
221121212
,:,,, bababbaa
ρ
;
(
)
(
)
(
)
{
}
Ζ
Ρ
Ρ
+
×
=
221121213
:,,, bababbaa
ρ
.
Найдите фактор-множества для данных отношений эквивалентности.
Решение. Построим фактор-множество для отношения
1
ρ
. Класс эк-
вивалентности, порожденный произвольным элементом
(
)
Ρ
21
, aa , име-
ет вид
(
)
[
]
(
)
(
)
(
)
(
)
{
}
(
)
{
}
=
=
=
=
Ζ
Ρ
Ρ
yaaxyxyxaayxaa
2112121
,:,,,,:,,
ρ
(
)
{
}
=
=
=
=
kyaaxkyx
21
,:,
Ζ
Ρ
(
)
{
}
=
=
=
=
kayaxkyx
21
,:,
Ζ
Ρ