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

UptoLike

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

20
12. Покажите, что равенство
j
f
f
j
o
o
=
верно не для любых бинар-
ных отношений.
13. Докажите, что для любого бинарного отношения
r
выполняются
условия:
r
r
RD
=
-1
и
r
r
DR
=
-1
.
14. Пусть
c
f
j
,
,
бинарные отношения, определенные на некото-
ром множестве. Докажите следующие утверждения:
1)
(
)
11
1
\\
--
=
fjfj
;
2)
(
)
(
)
(
)
c
f
c
j
c
f
j
o
o
o
Ç
Í
Ç
;
3)
(
)
11
1
--
=
jffj
o
o
;
4)
(
)
11
1
--
È=È
fjfj
;
5)
(
)
(
)
(
)
c
f
c
j
c
f
j
o
o
o
È
=
È
.
15. Приведите примеры бинарных отношений:
1) рефлексивных и транзитивных, но не антисимметричных;
2) транзитивных и симметричных, но не рефлексивных;
3) рефлексивных и симметричных, но не транзитивных;
4) рефлексивных и транзитивных, но не симметричных.
16. Докажите, что если
r
транзитивное и симметричное бинарное
отношение на множестве
A
, область определения которого совпадает с
A
,
то
r
рефлексивно.
1.3 Специальные бинарные отношения
Рефлексивное, симметричное и транзитивное отношение
r
на мно-
жестве
C
называется отношением эквивалентности на множестве
C
. Для
отношения эквивалентности вместо записи
(
)
r
Î
yx, часто используют за-
пись
y
x
»
(читается:
x
эквивалентен
y
).
Классом эквивалентности, порожденным элементом
x
, называется
подмножество множества
C
, состоящее из тех элементов
C
Î
y
, для ко-
торых
(
)
r
Î
yx, . Класс эквивалентности, порожденный элементом
x
, обо-
значается через
[
]
x :
[
]
(
)
{
}
.,:
r
Î
Î
=
yxyx
C
Разбиением множества
C
называется совокупность попарно непере-
секающихся подмножеств
C
таких, что каждый элемент множества
C
принадлежит одному и только одному из этих подмножеств. Всякое раз-
биение множества
C
определяет на
C
отношение эквивалентности
r
:
(
)
r
Î
yx, тогда и только тогда, когда
x
и
y
принадлежат одному подмно-
жеству разбиения. С другой стороны, всякое отношение эквивалентности