Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 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
,:,
Ζ
Ρ
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 +2 m,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}.

        Пример 3. На плоскости Ρ выбрана некоторая декартова прямо-
угольная система координат. На Ρ заданы три отношения эквивалентно-
сти:
              ρ1 ={((a1 , a 2 ), (b1 , b2 ))∈Ρ ×Ρ : a1 =b1 , a 2 −b2 ∈Ζ };
              ρ2 ={((a1 , a2 ), (b1 , b2 ))∈Ρ ×Ρ : a1 −b1 ∈Ζ , a 2 −b2 ∈Ζ };
              ρ3 ={((a1 , a2 ), (b1 , b2 ))∈Ρ ×Ρ : a1 −b1 +a 2 −b2 ∈Ζ }.
Найдите фактор-множества для данных отношений эквивалентности.
        Решение. Построим фактор-множество для отношения ρ1 . Класс эк-
вивалентности, порожденный произвольным элементом (a1 , a2 )∈Ρ , име-
ет вид
[(a1 , a2 )] ={(x, y )∈Ρ : ((a1 , a2 ), (x, y ))∈ρ1}={(x, y )∈Ρ : x =a1 , a2 −y ∈Ζ }=
={(x , y )∈Ρ : ∃k ∈Ζ x =a1 , a2 −y =k }=
={(x, y )∈Ρ : ∃k ∈Ζ x =a1 , y =a 2 −k}=