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

UptoLike

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

26
числа
y
. Докажите, что данное отношение является отношением эквива-
лентности. Сколько элементов в фактор-множестве
r
/
N
?
3. На
R
задано бинарное отношение
(
)
{
}
yyxxRRyx +=+´Î=
22
:,
r
.
Докажите, что
r
отношение эквивалентности. Сколько элементов может
содержать класс эквивалентности? Существует ли класс эквивалентности,
состоящий из одного элемента?
4. Покажите, что пересечение отношений эквивалентности, опреде-
ленных на некотором множестве
A
, является отношением эквивалентно-
сти.
5. Докажите, что если
r
отношение эквивалентности, то
1-
r
так-
же отношение эквивалентности.
6. Какие из следующих подмножеств множества
(
)
R
образуют раз-
биение
R
? Для каждого разбиения задайте соответствующее отношение
эквивалентности:
1)
{
}
{
}
{
}
;0:,0:
<
Î
>
Î
xRxxRx
2)
{
}
{
}
{
}
{
}
;0,0:,0:
<
Î
>
Î
xRxxRx
3)
(
)
{
}
;:1,
Z
Î
+
nnn
4)
[
]
{
}
;:1,
Z
Î
+
nnn
5)
(
]
{
}
Z
Î
+
nnn :1, .
7. Пусть
{
}
{
}
nn
B
B
B
M
A
A
A
M
,...,,,,...,,
212211
=
=
два разбиения
множества
K
. Докажите, что множество всех непустых подмножеств вида
ji
B
A
Ç
также является разбиением множества
.
K
Какое отношение эк-
вивалентности соответствует этому разбиению, если разбиению
1
M
соот-
ветствует отношение
1
r
, а разбиению
2
M
отношение
2
r
?
8. Докажите, что отношение
,:xyy
делитсяна x
r

N´N
яв-
ляется отношением порядка. Является ли это отношение отношением ли-
нейного порядка? Является ли аналогичное отношение отношением поряд-
ка, если его рассматривать на множестве
Z
?
9. Докажите, что отношение
(
)
{
,:xyx
делитсяна y или
r
=δNN
}
xy
<
является отношением линейного порядка.
10. На множестве всевозможных разбиений данного множества рас-
смотрим отношение:
(
)
r
Î
21
,
M
M
, если для любого
1
M
A
Î
существует
множество
2
M
B
Î
такое, что
B
A
Í
. Докажите, что рассматриваемое от-
ношение является отношением порядка. Является ли оно линейным поряд-
ком?
11. Перечислите всевозможные линейные порядки на множестве
{
}
2,1 , на множестве
{
}
3,2,1 . Выскажите предположение о числе линейных
порядков на множестве из
n
элементов.