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

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

21
r
определяет разбиение множества
C
на классы эквивалентности отно-
сительно этого отношения.
Совокупность классов эквивалентности элементов множества
C
по
отношению эквивалентности
r
называется фактор-множеством множества
C
по отношению
r
и обозначается
r
/
C
.
Рефлексивное, антисимметричное и транзитивное отношение назы-
вается отношением частичного порядка на множестве
C
и вместо записи
(
)
r
Î
yx, для данного отношения часто используют запись
y
£
. Отноше-
ние частичного порядка на множестве
C
, для которого любые два элемен-
та сравнимы, т.е. для любых
C
Î
y
,
выполнено либо
y
£
, либо
y
£
,
называется отношением линейного порядка. Множество
C
с заданным на
нем частичным (линейным) порядком называется частично (линейно) упо-
рядоченным.
Пусть
C
– непустое конечное множество, на котором задано отноше-
ние частичного порядка. Запишем
y
<
, если
y
£
и
y
x
¹
. Говорят, что
элемент
y
покрывает элемент
, если
y
<
, и не существует такого элемен-
та
u
, что
y
u
<
<
. Для
y
<
можно записать yxxxx
n
=
<
<
<
=
...
21
, где
1+i
x покрывает
i
x .
Частично упорядоченные множества можно изображать с помощью
так называемых диаграмм Хассе. На диаграмме Хассе элементы частично
упорядоченного множества изображаются точками на плоскости, и если
элемент
y
покрывает элемент
, то точки
и
y
соединяются отрезком,
причем точку, соответствующую
, располагают ниже
y
.
Пример 1. Доказать, что бинарное отношение на множестве целых
чисел
(
)
{
}
yxyx
=
´
Î
=
:,
Z
Z
r
является отношением эквивалентности, и построить соответствующее ему
фактор-множество
r
/
Z
.
Решение. Проверку рефлексивности, симметричности и транзитив-
ности данного бинарного отношения выполните самостоятельно. Постро-
им классы эквивалентности для данного отношения эквивалентности.
Класс эквивалентности, порожденный любым элементом
Z
Î
, имеет вид
[
]
{
}
{
}
{
}
xyxyyxyx
=
=
Î
=
»
Î
=
::
Z
Z
.
Таким образом, для данного отношения эквивалентности класс экви-
валентности, порожденный элементом
Z
Î
, состоит только из этого эле-
мента
,
x
и фактор-множество
r
/
Z
имеет вид
{
}
{
}
Z
Z
Î
=
xx :/
r
.

Страницы