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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Решение.
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Докажите, что каждое из следующих отношений является отношением
эквивалентности, и найдите классы эквивалентности:
1)
(
)
(
)
(
)
{
}
yxyx =×∈= :, ΑΡΑΡρ ,
{
}
3,2,1
=
Α
;
2)
(
)
(
)
(
)
{
}
cbdadcba +=+×∈= :,,,
22
ΝΝρ ;
3)
(
)
{
}
;:,
22
yxRRyx =×∈= ρ
4)
(
)
(
)
(
)
{
}
множествоконечноеyxyx
−
+
×
∈
=
:,
Α
Ρ
Α
Ρ
ρ
,
Α
∀
;
2. На множестве
задано бинарное отношение по следующему правилу :
(
)
ρ
∈
yx ,
тогда и только тогда, когда последняя цифра в десятичной запи -
си числа
x
совпадает с последней цифрой в десятичной записи числа
y
.
Докажите, что данное отношение является отношением эквивалентности.
Сколько элементов в фактор-множестве
ρ
/
?
3. На
R
задано бинарное отношение
(
)
{
}
yyxxRRyx +=+×∈=
22
:, ρ .
Докажите, что
ρ
- отношение эквивалентности. Сколько элементов может
содержать класс эквивалентности? Существует ли класс эквивалентности,
состоящий из одного элемента?
4. Покажите, что пересечение отношений эквивалентности, определенных
на некотором множестве
Α
, является отношением эквивалентности.
5. Докажите, что если
ρ
- отношение эквивалентности, то
1−
ρ
- также от -
ношение эквивалентности.
6. Какие из следующих подмножеств множества
(
)
R
Ρ
образуют разбиение
R
? Для каждого разбиения задайте соответствующее отношение эквива -
лентности:
{1,2,3}
{1,3}
{1}{2}
{2,3}
{3}
{1,2}
30
10
2
1
15
6
5
3
1. 2.
.
Решение.

                                 {1,2,3}                                     30


   {2,3}                   {1,2}           {1,3}       15                6        10

                           {3}
                                                                         5

           {2}                              {1}                                   2
                                                            3

                                                                             1
                          1.                                        2.



                                 ЗАДАЧИ И УПРАЖНЕНИЯ

1. Докажите, что каждое из следующих отношений является отношением
эквивалентности, и найдите классы эквивалентности:
         1) ρ ={(x, y )∈Ρ (Α )×Ρ (Α ) : x = y }, Α ={1, 2,3};

                       {
                 2) ρ = ((a, b ), (c, d ))∈Ν 2 ×Ν 2 : a +d =b +c ;   }
                 3) ρ ={(x , y )∈ R ×R : x   2
                                                      }
                                                   =y2 ;
                 4) ρ ={(x, y )∈Ρ (Α )×Ρ (Α ): x +y −конечное множество}, ∀Α ;
2. На множестве Ν задано бинарное отношение по следующему правилу:
(x, y )∈ρ тогда и только тогда, когда последняя цифра в десятичной запи-
си числа x совпадает с последней цифрой в десятичной записи числа y .
Докажите, что данное отношение является отношением эквивалентности.
Сколько элементов в фактор-множестве Ν / ρ ?

                                                                {
3. На R задано бинарное отношение ρ = (x , y )∈ R ×R : x 2 +x = y 2 +y .               }
Докажите, что ρ - отношение эквивалентности. Сколько элементов может
содержать класс эквивалентности? Существует ли класс эквивалентности,
состоящий из одного элемента?
4. Покажите, что пересечение отношений эквивалентности, определенных
на некотором множестве Α , является отношением эквивалентности.
5. Докажите, что если ρ - отношение эквивалентности, то ρ −1 - также от-
ношение эквивалентности.
6. Какие из следующих подмножеств множества Ρ (R ) образуют разбиение
R ? Для каждого разбиения задайте соответствующее отношение эквива-
лентности:

Страницы