Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 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
Ζ
Ζ
элемента сравнимы, т.е. для любых x, y ∈Χ выполнено либо x ≤ y , либо
 y ≤ x , называется отношением линейного порядка. Множество Χ с задан-
ным на нем частичным (линейным) порядком называется частично (линей-
но) упорядоченным.
Пусть Χ - непустое конечное множество, на котором задано отношение
частичного порядка. Запишем x < y , если x ≤ y и x ≠ y . Говорят, что эле-
мент y покрывает элемент x , если x < y и не существует такого элемента
u , что x

Страницы