Дискретная математика. Элементы теории, задачи и упражнения. Часть 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
принадлежат одному подмно-
жеству разбиения. С другой стороны, всякое отношение эквивалентности 
     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

Страницы