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

UptoLike

(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
1,22,1,5,5,4,4,3,3,2,2,1,1
1
=
ρ
;
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
3,22,3,5,5,4,4,3,3,2,2,1,1
1
=
ρ
.
Объединение данных отношений эквивалентности
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
3,2,2,3,1,22,1,5,5,4,4,3,3,2,2,1,1
21
=
ρ
ρ
не является отношением эквивалентности, так как для него не выполнено
свойство транзитивности (
(
)
21
2,3
ρ
ρ
,
(
)
21
1,2
ρ
ρ
, а
(
)
21
1,3
ρ
ρ
).
Пример 7. Докажите, что отношение
(
)
{
}
yxRRyx
×
=
:,
ρ
явля-
ется отношением порядка на множестве
R
, является ли это отношение от -
ношением линейного порядка .
Решение. Для доказательства проверим три свойства данного отно-
шения: рефлексивность, антисимметричность, транзитивность.
1. Рефлексивность.
(
)
ρ
=
xxxxRx , .
2. Антисимметричность.
Пусть
(
)
ρ
yx , и
()
yx
xy
yx
xy =⇒
⇒∈ ρ, .
3. Транзитивность.
Пусть
(
)
ρ
yx , и
()()
ρρ ≤⇒
⇒∈ zxzx
zy
yx
zy ,, .
Данное отношение является отношением линейного порядка , так как
для любых
R
x
,
выполнено либо
x
, либо
x
.
Пример 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
=
ρ
ρ
o
не является отношением частичного порядка , так как для него нарушено
свойство транзитивности (
(
)
12
2,5
ρ
ρ
o
,
(
)
12
3,2
ρ
ρ
o
,
(
)
12
3,5
ρ
ρ
o
).
Пример 9. Для следующих двух отношений частичного порядка по -
строить диаграммы Хассе.
1.
{
}
3,2,1
=
Α
,
(
)
(
)
(
)
{
}
yxyx
×
=
:,
1
Α
Ρ
Α
Ρ
ρ
.
2.
{
}
30,15,10,6,5,3,2,1
=
Α
,
(
)
{
}
xнаделитсяyyx :,
2
Α
Α
×
=
ρ
.