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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

24
Решение.
M
является разбиением множества
A
, поскольку множе-
ства, являющиеся элементами множества
M
, не пересекаются и при объе-
динении дают все множество
A
. Отношение эквивалентности, соответст-
вующее данному разбиению, строится по правилу
(
)
r
Î
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
r
.
Пример 6. Покажите, что объединение двух отношений эквивалент-
ности может не являться отношением эквивалентности.
Решение. На множестве
{
}
5,4,3,2,1
A
рассмотрим два отношения
эквивалентности
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
1,22,1,5,5,4,4,3,3,2,2,1,1
1
r
;
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
3,22,3,5,5,4,4,3,3,2,2,1,1
1
r
.
Объединение данных отношений эквивалентности
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
3,2,2,3,1,22,1,5,5,4,4,3,3,2,2,1,1
21
È
r
r
не является отношением эквивалентности, так как для него не вы-
полнено свойство транзитивности
12
3,2,
(
rr

12
2,1,
rr

а
(
)
21
1,3
r
r
È
Ï
).
Пример 7. Докажите, что отношение
(
)
{
}
yxRRyx
Î
:,
r
явля-
ется отношением порядка на множестве
R
, является ли это отношение от-
ношением линейного порядка.
Решение. Для доказательства проверим три свойства данного отно-
шения: рефлексивность, антисимметричность, транзитивность.
1. Рефлексивность.
(
)
r
Î
Þ
Î
"
xxxxRx , .
2. Антисимметричность.
Пусть
(
)
r
Î
yx, и
( )
yx
xy
yx
xy =Þ
î
í
ì
£
ÞÎ
r
, .
3. Транзитивность.
Пусть
(
)
r
Î
yx, и
( ) ( )
rr
ÎÞ£Þ
î
í
ì
£
ÞÎ zxzx
zy
yx
zy ,, .
Данное отношение является отношением линейного порядка, так как
для любых
R
y
x
Î
,
выполнено либо
y
x
, либо
x
y
.
Пример 8. Покажите, что композиция двух отношений частичного
порядка может не являться отношением частичного порядка. 
      Решение. � является разбиением множества � , поскольку множе-
ства, являющиеся элементами множества � , не пересекаются и при объе-
динении дают все множество � . Отношение эквивалентности, соответст-
вующее данному разбиению, строится по правилу � 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 , является ли это отношение от-
ношением линейного порядка.
      Решение. Для доказательства проверим три свойства данного отно-
шения: рефлексивность, антисимметричность, транзитивность.
      1. Рефлексивность.
      �x � R x � x � � x, x � � � .
      2. Антисимметричность.
                                          �x � y
      Пусть � x, y � � � и � y, x � � � � �       � x � y.
                                          �y � x
      3. Транзитивность.
                                          �x � y
      Пусть � x, y � � � и � y, z � � � � �       � x � z � � x, z � � � .
                                          � y � z
      Данное отношение является отношением линейного порядка, так как
для любых x, y � R выполнено либо x � y , либо y � x .

     Пример 8. Покажите, что композиция двух отношений частичного
порядка может не являться отношением частичного порядка.


                                          24

Страницы