ВУЗ:
Составители:
Рубрика:
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
принадлежат одному подмно-
жеству разбиения. С другой стороны, всякое отношение эквивалентности
12. Покажите, что равенство � � � � � � � верно не для любых бинар- ных отношений. 13. Докажите, что для любого бинарного отношения � выполняются условия: D � �1 � R � и R � �1 � D � . 14. Пусть � , � , � – бинарные отношения, определенные на некото- ром множестве. Докажите следующие утверждения: 1) �� \ � � � � �1 \ � �1 ; �1 2) �� � � � � � � �� � � � � �� � � � ; 3) �� � � � �1 � � �1 � � �1 ; 4) �� � � � � � �1 � � �1 ; �1 5) �� � � � � � � �� � � � � �� � � � . 15. Приведите примеры бинарных отношений: 1) рефлексивных и транзитивных, но не антисимметричных; 2) транзитивных и симметричных, но не рефлексивных; 3) рефлексивных и симметричных, но не транзитивных; 4) рефлексивных и транзитивных, но не симметричных. 16. Докажите, что если � – транзитивное и симметричное бинарное отношение на множестве � , область определения которого совпадает с � , то � рефлексивно. 1.3 Специальные бинарные отношения Рефлексивное, симметричное и транзитивное отношение � на мно- жестве � называется отношением эквивалентности на множестве � . Для отношения эквивалентности вместо записи � x, y � � � часто используют за- пись x � y (читается: x эквивалентен y ). Классом эквивалентности, порожденным элементом x , называется подмножество множества � , состоящее из тех элементов y � � , для ко- торых � x, y � � � . Класс эквивалентности, порожденный элементом x , обо- значается через �x� : �x� � �y � � : � x, y � � ��. Разбиением множества � называется совокупность попарно непере- секающихся подмножеств � таких, что каждый элемент множества � принадлежит одному и только одному из этих подмножеств. Всякое раз- биение множества � определяет на � отношение эквивалентности � : � x, y � � � тогда и только тогда, когда x и y принадлежат одному подмно- жеству разбиения. С другой стороны, всякое отношение эквивалентности 20
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »