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