Дискретная математика. Элементы теории, задачи и упражнения. Часть 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
элементов. 
числа y . Докажите, что данное отношение является отношением эквива-
лентности. Сколько элементов в фактор-множестве � / � ?
                                                    �
      3. На R задано бинарное отношение � � � x, y � � R � R : x 2 � x � y 2 � y .  �
Докажите, что � – отношение эквивалентности. Сколько элементов может
содержать класс эквивалентности? Существует ли класс эквивалентности,
состоящий из одного элемента?
      4. Покажите, что пересечение отношений эквивалентности, опреде-
ленных на некотором множестве � , является отношением эквивалентно-
сти.
      5. Докажите, что если � – отношение эквивалентности, то � �1 – так-
же отношение эквивалентности.
      6. Какие из следующих подмножеств множества � � R � образуют раз-
биение R ? Для каждого разбиения задайте соответствующее отношение
эквивалентности:
      1) ��x � R : x � 0�, �x � R : x � 0��;
      2) ��x � R : x � 0�, �x � R : x � 0�, �0��;
      3) ��n, n � 1� : n � � �;
      4) ��n, n � 1� : n � � �;
      5) ��n, n � 1� : n � � � .
      7. Пусть � 1 � ��1 , �2 ,..., �n �, � 2 � �� 1 , � 2 ,..., � n � – два разбиения
множества � . Докажите, что множество всех непустых подмножеств вида
� i � � j также является разбиением множества K . Какое отношение эк-
вивалентности соответствует этому разбиению, если разбиению � 1 соот-
ветствует отношение �1 , а разбиению � 2 – отношение � 2 ?
      8. Докажите, что отношение �   x, y   � � � : y делится на x яв-
ляется отношением порядка. Является ли это отношение отношением ли-
нейного порядка? Является ли аналогичное отношение отношением поряд-
ка, если его рассматривать на множестве � ?
      9. Докажите, что отношение � � �� x, y � � N � N : x делится на y или
x � y� является отношением линейного порядка.
       10. На множестве всевозможных разбиений данного множества рас-
смотрим отношение: �� 1 , � 2 � � � , если для любого � � � 1 существует
множество � � � 2 такое, что � � � . Докажите, что рассматриваемое от-
ношение является отношением порядка. Является ли оно линейным поряд-
ком?
       11. Перечислите всевозможные линейные порядки на множестве
�1,2�, на множестве �1,2,3� . Выскажите предположение о числе линейных
порядков на множестве из n элементов.

                                         26

Страницы