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

UptoLike

элемента сравнимы, т.е. для любых
Χ
y
x
,
выполнено либо
y
x
, либо
x
y
, называется отношением линейного порядка . Множество
Χ
с задан-
ным на нем частичным (линейным ) порядком называется частично (линей-
но) упорядоченным .
Пусть
Χ
- непустое конечное множество, на котором задано отношение
частичного порядка . Запишем
y
x
<
, если
y
x
и
y
x
. Говорят , что эле-
мент
y
покрывает элемент
x
, если
y
x
<
и не существует такого элемента
u
, что
y
u
x
<
<
. Для
y
x
<
можно записать yxxxx
n
=
<
<
<
=
...
21
, где
1+i
x покрывает
i
x .
Частично упорядоченные множества можно изображать с помощью
так называемых диаграмм Хассе. На диаграмме Хассе элементы частично
упорядоченного множества изображаются точками на плоскости, и если
элемент
y
покрывает элемент
x
, то точки
x
и
y
соединяются отрезком,
причем точку , соответствующую
x
, располагают ниже
y
.
Пример 1. Доказать, что бинарное отношение на множестве целых
чисел
(
)
{
}
yxyx
=
×
=
:,
Ζ
Ζ
является отношением эквивалентности, и построить соответствующее
ему фактор-множество
ρ
/
Ζ
.
Решение. Проверку рефлексивности, симметричности и транзитив-
ности данного бинарного отношения выполните самостоятельно. Постро -
им классы эквивалентности для данного отношения эквивалентности.
Класс эквивалентности, порожденный любым элементом
Ζ
x
, имеет
вид
[
]
{
}
{
}
{
}
xyxyyxyx
=
=
=
=
::
Ζ
Ζ
.
Таким образом , для данного отношения эквивалентности класс эквива -
лентности, порожденный элементом
Ζ
x
, состоит только из этого эле-
мента
x
и фактор-множество
ρ
/
Ζ
имеет вид
{
}
{
}
Ζ
Ζ
=
xx :/
.
Пример 2. Пусть
m
- некоторое натуральное число. Проверить, яв -
ляется ли отношением эквивалентности следующее бинарное отношение
на множестве целых чисел:
(
)
{
}
mнаделитсяyxyx
×
=
:,
Ζ
Ζ
.
Построить фактор-множество
ρ
/
Ζ
.
Решение. Проверим три основных свойства для отношения эквива -
лентности.
1. Рефлексивность.
Для произвольного
Ζ
x
разность
(
)
=
=
xxmxx ,00 .
2. Симметричность.
Пусть
(
)
(
)
.,,
ρ
ρ
=
=
xymkxykmkyxkyx
Ζ
Ζ