Дискретная математика. Элементы теории, задачи и упражнения. Часть 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. Покажите, что композиция двух отношений частичного
порядка может не являться отношением частичного порядка.

Страницы