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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

(
)
{
}
Ζ
Ρ
∈
∈
−
=
kkaa :,
21
.
Таким образом, в класс эквивалентности, порожденный элементом
(
)
Ρ
∈
21
, aa 10,
21
<
≤
∈
aRa , попадают вместе с элементом
(
)
Ρ
∈
21
, aa
элементы, у которых первая координата равна
1
a , а вторая координата от-
личается от
2
a
на целое число. Классы эквивалентности, порожденные
элементами с 10,
21
<
≤
∈
aRa , не пересекаются и в объединении дают
все множество
Ρ
. Следовательно, фактор-множество
1
/
ρ
Ρ
можно запи -
сать в виде
(
)
[
)
{
}
1,0,:}:,{/
1
∈
∈
∈
+
=
β
α
β
α
ρ
Rkk
Ζ
Ρ
.
Фактор-множество для отношений
32
,
ρ
ρ
постройте самостоятель-
но.
Пример 4. Придумайте минимальное (по числу элементов) отноше-
ние эквивалентности
ρ
на множестве
{
}
5,4,3,2,1
=
Α
так, чтобы
(
)
ρ
∈
2,1 и
(
)
ρ
∈
3,2 .
Решение. Отношение эквивалентности рефлексивно, поэтому дан-
ному отношению обязательно должны принадлежать пары
(
)
1,1
,
(
)
2,2
,
(
)
3,3
,
(
)
4,4 ,
(
)
5,5 . Отношение эквивалентности симметрично, поэтому на-
ряду с парами
(
)
2,1
,
(
)
3,2
данному отношению обязаны принадлежать пары
(
)
1,2
,
(
)
2,3
. В силу транзитивности отношения
ρ
ему обязана принадле-
жать вместе с парами
(
)
2,3 ,
(
)
1,2 пара
(
)
1,3 ( и, следовательно,
(
)
3,1 ). Та -
ким образом, минимальное отношение эквивалентности, которое мы мо-
жем построить, имеет вид
{
}
3113233212215544332211 ,,,,,,,,,,,,,,,,,,,,,
=
ρ
.
Пример 5. Докажите, что
{
}
{
}
{
}
{
}
{
}
7643521 ,,,,,,
=
Μ
- разбиение мно-
жества
{
}
7654321 ,,,,,,
=
Α
и перечислите все элементы отношения эквива -
лентности
ρ
, соответствующего разбиению
Μ
.
Решение.
Μ
является разбиением множества
Α
, поскольку множе-
ства , являющиеся элементами множества
Μ
, не пересекаются и при объе-
динении дают все множество
Α
. Отношение эквивалентности,
соответствующее данному разбиению , строится по правилу
(
)
ρ
∈
yx , тогда
и только тогда, когда
x
и
y
принадлежат одному подмножеству
разбиения, т.е.
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
()()()()()
=
3,3,6,7,7,6,4,7,7,4
,4,6,6,4,7,7,6,6,4,4,2,5,5,2,5,5,2,2,1,1
ρ .
Пример 6. Покажите, что объединение двух отношений эквивалент-
ности может не являться отношением эквивалентности.
Решение. На множестве
{
}
5,4,3,2,1
=
Α
рассмотрим два отношения
эквивалентности 
={(a1 , a 2 −k )∈Ρ : k ∈Ζ }.
Таким образом, в класс эквивалентности, порожденный элементом
(a1 , a 2 )∈Ρ a1 ∈R , 0 ≤a 2 <1 , попадают вместе с элементом (a1 , a2 )∈Ρ
элементы, у которых первая координата равна 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} и перечислите все элементы отношения эквива-
лентности ρ , соответствующего разбиению Μ .
       Решение. Μ является разбиением множества Α , поскольку множе-
ства, являющиеся элементами множества Μ , не пересекаются и при объе-
динении дают все множество Α . Отношение эквивалентности,
соответствующее данному разбиению, строится по правилу (x, y )∈ ρ тогда
и только тогда, когда x и y принадлежат одному подмножеству
             (1,1), (2,2 ), (5,5), (2,5), (5,2 ), (4, 4), (6,6 ), (7,7 ), (4,6 ), (6,4 ),�
разбиения,� т.е.
       ρ =�                                                                                � .
           � (4,7 ), (7, 4), (6,7 ), (7,6 ), (3,3)                                          �

      Пример 6. Покажите, что объединение двух отношений эквивалент-
ности может не являться отношением эквивалентности.
      Решение. На множестве Α ={1, 2,3,4,5} рассмотрим два отношения
эквивалентности

Страницы