Дискретная математика. Азарнова Т.В - 23 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Теория множеств
23
Фактор-множество для отношений
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 ). Таким образом,
минимальное отношение эквивалентности, которое мы можем построить,
имеет вид
()( )()( )( )()()( )( )()(){}
3,1,1,3,2,3,3,2,1,2,2,1,5,5,4,4,3,3,2,2,1,1
=
ρ
.
Задача 5
. Докажите, что
{}{ }{}{ }{}
7,6,4,3,5,2,1
=
Μ
ΜΜ
Μ
- разбиение
множества
{}
7,6,5,4,3,2,1
=
Α
ΑΑ
Α
и перечислите все элементы отношения
эквивалентности
ρ
, соответствующего разбиению
Μ
ΜΜ
Μ
.
Решение.
Μ
ΜΜ
Μ
является разбиением множества
Α
ΑΑ
Α
, поскольку
множества, являющиеся элементами множества
Μ
ΜΜ
Μ
, не пересекаются и при
объединении дают все множество
Α
ΑΑ
Α
. Отношение эквивалентности,
соответствующее данному разбиению, строится по правилу
()
ρ
∈
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
=
Α
ΑΑ
Α
рассмотрим два отношения
эквивалентности
()()()()()()(){}
1,22,1,5,5,4,4,3,3,2,2,1,1
1
=
ρ
;
()()()()()()(){}
3,22,3,5,5,4,4,3,3,2,2,1,1
1
=
ρ
.
Объединение данных отношений эквивалентности
()()()()()()()()(){}
3,2,2,3,1,22,1,5,5,4,4,3,3,2,2,1,1
21
=∪
ρ
ρ
не является отношением эквивалентности, так как для него не выполнено
свойство транзитивности (
()
21
2,3
ρ
∪∈
,
()
21
1,2
ρ
ρ
∪∈
, а
()
21
1,3
ρ
ρ
∪∉
).
Задача 7
. Докажите , что отношение
(){}
yxRRyx
≤×∈=
:,
ρ
является
отношением порядка на множестве
R
, является ли это отношение
отношением линейного порядка. 
                                             23
Теория множеств
       Фактор-множество для отношений ρ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} рассмотрим два отношения
эквивалентности
      ρ1 ={(1,1), (2,2 ), (3,3), (4,4 ), (5,5), (1,2 )(2,1)};
      ρ1 ={(1,1), (2,2 ), (3,3), (4,4 ), (5,5), (3,2 )(2,3)}.
Объединение данных отношений эквивалентности
      ρ1 ∪ ρ2 ={(1,1), (2,2 ), (3,3), (4,4 ), (5,5), (1,2 )(2,1), (3,2 ), (2,3)}
не является отношением эквивалентности, так как для него не выполнено
свойство транзитивности ( (3,2 )∈ ρ1 ∪ ρ2 , (2,1)∈ ρ1 ∪ ρ2 , а (3,1)∉ ρ1 ∪ ρ2 ).

     Задача 7. Докажите, что отношение ρ ={(x, y )∈ R ×R : x ≤ y} является
отношением порядка на множестве R , является ли это отношение
отношением линейного порядка.

Страницы