Дискретная математика. Азарнова Т.В - 24 стр.

UptoLike

Теория множеств
24
Решение. Для доказательства проверим три свойства данного
отношения: рефлексивность, антисимметричность, транзитивность.
1. Рефлексивность.
()
ρ
=
xxxxRx
,
.
2. Антисимметричность.
Пусть
()
ρ
yx
,
и
()
yx
xy
yx
xy =
ρ
,.
3. Транзитивность.
Пусть
()
ρ
yx
,
и
() ()
ρρ
zxzx
zy
yx
zy
,,.
Данное отношение является отношением линейного порядка, так как
для любых
Ryx
, выполнено либо
yx
, либо
xy
.
Задача 8.
Покажите, что композиция двух отношений частичного
порядка может не являться отношением частичного порядка.
Решение. На множестве
{}
5,4,3,2,1
=
Α
ΑΑ
Α
рассмотрим два отношения
частичного порядка
()()()()()()()(){}
3,1,3,2,2,1,5,5,4,4,3,3,2,2,1,1
1
=
ρ
;
()()()()()()()(){}
2,1,2,5,5,1,5,5,4,4,3,3,2,2,1,1
2
=
ρ
.
Однако композиция
()()()()()()()()()()(){}
2,1,2,5,5,1,3,2,2,1,3,1,5,5,4,4,3,3,2,2,1,1
12
=
ρ
ρ
ο
не является отношением частичного порядка, так как для него нарушено
свойство транзитивности (
()
12
2,5
ρ
ρ
ο
,
()
12
3,2
ρ
ρ
ο
,
()
12
3,5
ρ
ρ
ο
).
Задача 9.
Для следующих двух отношений частичного порядка
построить диаграммы Хассе.
1.
{}
3,2,1
=
Α
ΑΑ
Α
,
( ) () (){}
yxyx
×=
:,
1
Α
ΑΑ
ΑΡ
ΡΡ
ΡΑ
ΑΑ
ΑΡ
ΡΡ
Ρ
ρ
.
2.
{}
30,15,10,6,5,3,2,1
=
Α
ΑΑ
Α
,
(){}
xнаделитсяyyx
:,
2
Α
ΑΑ
ΑΑ
ΑΑ
Α
×=
ρ
.
Решение.
{1,2,3}
{1,3}
{1}{2}
{2,3}
{3}
{1,2}
30
10
2
1
15
6
5
3
1.
2.