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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

25
Решение. На множестве
{
}
5,4,3,2,1
=
A
рассмотрим два отношения
частичного порядка
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
3,1,3,2,2,1,5,5,4,4,3,3,2,2,1,1
1
=
r
;
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
2,1,2,5,5,1,5,5,4,4,3,3,2,2,1,1
2
=
r
.
Однако композиция
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
2,1,2,5,5,1,3,2,2,1,3,1,5,5,4,4,3,3,2,2,1,1
12
=
r
r
o
не является отношением частичного порядка, так как для него нарушено
свойство транзитивности (
(
)
12
2,5
r
r
o
Î
,
(
)
12
3,2
r
r
o
Î
,
(
)
12
3,5
r
r
o
Ï
).
Пример 9. Для следующих двух отношений частичного порядка по-
строить диаграммы Хассе.
1.
{
}
3,2,1
=
A
,
(
)
(
)
(
)
{
}
yxyx
Í
´
Î
=
:,
1
A
R
A
R
r
.
2.
{
}
30,15,10,6,5,3,2,1
=
A
,
(
)
{
}
xнаделитсяyyx :,
2
A
A
´
Î
=
r
.
Решение.
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Докажите, что каждое из следующих отношений является отноше-
нием эквивалентности, и найдите классы эквивалентности:
1)
(
)
(
)
(
)
{
}
yxyx
=
´
Î
=
:,
A
A
r
,
{
}
3,2,1
=
A
;
2)
(
)
(
)
(
)
{
}
cbdadcba +=+´Î= :,,,
22
NNr
;
3)
(
)
{
}
;:,
22
yxRRyx =´Î=
r
4)
(
)
(
)
(
)
{
}
множествоконечноеyxyx
-
+
´
Î
=
:,
A
R
A
R
r
,
A
"
.
2. На множестве
N
задано бинарное отношение по следующему
правилу:
(
)
r
Î
yx, тогда и только тогда, когда последняя цифра в десятич-
ной записи числа
x
совпадает с последней цифрой в десятичной записи
{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,4,5� рассмотрим два отношения
частичного порядка
      �1 � ��1,1�, �2,2 �, �3,3�, �4,4 �, �5,5�, �1,2 �, �2,3�, �1,3�� ;
      � 2 � ��1,1�, �2,2 �, �3,3�, �4,4 �, �5,5�, �1,5�, �5,2 �, �1,2 �� .
     Однако композиция
      � 2 � �1 � ��1,1�, �2,2 �, �3,3�, �4,4 �, �5,5�, �1,3�, �1,2 �, �2,3�, �1,5�, �5,2�, �1,2 ��
не является отношением частичного порядка, так как для него нарушено
свойство транзитивности ( �5,2 � � � 2 � �1 , �2,3� � � 2 � �1 , �5,3� � � 2 � �1 ).

     Пример 9. Для следующих двух отношений частичного порядка по-
строить диаграммы Хассе.
     1. � � �1,2,3�, �1 � �� x, y � � � �� � � � �� � : x � y� .
     2. � � �1,2,3,5,6,10,15,30�, � 2 � �� x, y � � � � � : y делится на x�.
     Решение.

                              {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 �� � � � � : a � d � b � c�;
                                            2             2


       3) � � �� x, y � � R � R : x � y �;
                                        2             2

     4) � � �� x, y � � � �� � � � �� � : x � y � конечное множество� , �� .
     2. На множестве � задано бинарное отношение по следующему
правилу: � x, y � � � тогда и только тогда, когда последняя цифра в десятич-
ной записи числа x совпадает с последней цифрой в десятичной записи

                                                              25

Страницы