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

UptoLike

4)
(
)
11
1
−−
=∪ φϕφϕ ;
5)
(
)
(
)
(
)
χ
φ
χ
ϕ
χ
φ
ϕ
ooo
=
.
15. Приведите примеры бинарных отношений:
1) рефлексивных и транзитивных , но не антисимметричных;
2) транзитивных и симметричных , но не рефлексивных;
3) рефлексивных и симметричных , но не транзитивных;
4) рефлексивных и транзитивных , но не симметричных .
16. Докажите, что если
ρ
- транзитивное и симметричное бинарное от -
ношение на множестве
Α
, область определения которого совпадает
с
Α
, то
ρ
рефлексивно.
1.3 Специальные бинарные отношения
Рефлексивное, симметричное и транзитивное отношение
ρ
на мно-
жестве
Χ
называется отношением эквивалентности на множестве
Χ
.
Для отношения эквивалентности вместо записи
(
)
ρ
yx , часто использу -
ют запись
x
(читается :
x
эквивалентен
)
Классом эквивалентности, порожденным элементом
x
, называется
подмножество множества
Χ
, состоящее из тех элементов
Χ
, для ко-
торых
(
)
ρ
yx , . Класс эквивалентности, порожденный элементом
x
,
обозначается через
[
]
x
:
[
]
(
)
{
}
.,:
ρ
=
yxyx
Χ
Разбиением множества
Χ
называется совокупность попарно непе -
ресекающихся подмножеств
Χ
таких, что каждый элемент множества
Χ
принадлежит одному и только одному из этих подмножеств. Всякое раз-
биение множества
Χ
определяет на
Χ
отношение эквивалентности
ρ
:
(
)
ρ
yx , тогда и только тогда, когда
x
и
принадлежат одному подмно-
жеству разбиения. С другой стороны, всякое отношение эквивалентности
ρ
определяет разбиение множества
Χ
на классы эквивалентности отно-
сительно этого отношения.
Совокупность классов эквивалентности элементов множества
Χ
по отношению эквивалентности
ρ
называется фактор-множеством множе-
ства
Χ
по отношению
ρ
и обозначается
ρ
/
Χ
.
Рефлексивное, антисимметричное и транзитивное отношение на-
зывается отношением частичного порядка на множестве
Χ
и вместо запи -
си
(
)
ρ
yx , для данного отношения часто используют запись
x
. От-
ношение частичного порядка на множестве
Χ
, для которого любые два