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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

18
(
)
( )
( ) ( ) ( )
1
,
,
,,.
,
симметричность
xy
xyyx
xy
jf
j
jfjf
f
-
Îì
ï
ÞÞÎÇÞÎÇ
í
Î
ï
î
Пусть
f
j
,
– антисимметричные отношения, докажем, что
1
-
Ç
fj
–
антисимметричное отношение. Пусть
( ) ( )
( )
( )( )
Þ
î
í
ì
Î
Î
Þ
î
í
ì
ÇÎ
ÇÎ
Þ
ï
î
ï
í
ì
ÇÎ
ÇÎ
-
-
f
j
fj
fj
fj
fj
xyyx
xyyx
yx
xy
xy
yx
,,,
,,,
,
,
,
,
1
1
yx
ричностьантисиммет
=Þ
fj
,
.
1. Докажем требуемое включение. Пусть
Þ
Ï
Î
Þ
Î
c
f
c
j
c
f
c
j
o
o
o
o
yxyxyx ,,,\,
( )
( )
( )
( )
( )
( )
( )
( )
Þ
î
í
ì
Î
Î
$Þ
ï
î
ï
í
ì
Ï
Î
Î
$Þ
ï
ï
î
ï
ï
í
ì
ê
ë
é
Ï
Ï
"
î
í
ì
Î
Î
$
Þ
fj
c
f
j
c
f
c
j
c
\,
,
,
,
,
,
,
,
,
yz
zx
z
yz
yz
zx
z
yz
zx
z
yz
zx
z
c
f
j
o
\,
Î
Þ
yx
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Пусть
{
}
´
*
=
C
, . Перечислите все элементы множеств
43
CC , .
2. Найдите геометрическую интерпретацию множества
B
´
A
, где
A
– множество точек отрезка
1,0 , а
B
– множество точек квадрата с вер-
шинами в точках
(
)
(
)
(
)
(
)
11011000 ,,,,,,, .
3. Доказать, что
M
B
K
A
M
K
B
A
È
´
È
Í
´
È
´
. При каких
M
K
B
A
,
,
,
включение можно заменить равенством.
4. Доказать, что для произвольных множеств
K
B
A
,
,
:
1)
;
K
B
K
A
K
B
A
´
È
´
=
´
È
2)
;\\
K
B
K
A
K
B
A
´
´
=
´
3)
K
A
B
A
K
B
A
´
´
=
´
\\ .
5. Пусть
Æ
¹
B
Æ
¹
A
,
и
M
K
A
B
B
A
´
=
´
È
´
. Доказать, что в
этом случае
M
K
B
A
=
=
=
.
6. Перечислите все элементы бинарного отношения
r
и нарисуйте
его граф:
1)
{
}
yxyx
<
=
:,
r
на множестве
{
}
5,4,3,2,1
=
C
;
2)
{
}
1:,
+
=
=
xyyx
r
на множестве
{
}
10,9,8,7,6,5,4,3,2,1
=
C
. 
                                ��� x, y � � �
                                                � � x , y � � � � � � � y , x � � �� � � � .
                                                                                                �1
     �симметричность � ,� �
                                 �� x, y � � �
     Пусть � , � – антисимметричные отношения, докажем, что �� � � � –
                                                                                                   �1

антисимметричное отношение. Пусть
     ��� x, y � � �� � � ��1            �� y, x � � � � �       �� x, y �, � y, x � � �
      �                            �    �                     � �                         �
      ��� y, x � � �� � � ��1           �� x, y � � � � �       �� x, y �, � y, x � � �
     � антисимметричность � ,� x � y .
     1. Докажем требуемое включение. Пусть
     � x, y � � �� � � � \ �� � � � � � x, y � � � � � , � x, y � � � � � �
           �        �� x, z � � �
           � �z     �                            �� x, z � � �
           �        �� z , y � � �               �                        �� x, z � � �
     ��                              � �z �� z , y � � � � �z �                                �
           ��z      � � x , z � � �              �� z , y � � �           �  � z , y � � � \ �
                    �                            �
           �
           �        �� z , y � � �
     � � x, y � � �� \ � � � �


                              ЗАДАЧИ И УПРАЖНЕНИЯ

        1. Пусть � � ��,��. Перечислите все элементы множеств � 3 , � 4 .
        2. Найдите геометрическую интерпретацию множества � � � , где
� – множество точек отрезка �0,1� , а � – множество точек квадрата с вер-
шинами в точках �0,0 �, �0,1�, �1,0 �, �1,1� .
        3. Доказать, что �� � � � � �� � � � � �� � � � � �� � � � . При каких
� , � , � , � включение можно заменить равенством.
        4. Доказать, что для произвольных множеств � , � , � :
        1) �� � � � � � � �� � � � � �� � � �;
        2) �� \ � � � � � �� � � � \ �� � � �;
        3) � � �� \ � � � �� � � � \ �� � � � .
        5. Пусть � � �, � � � и �� � � � � �� � � � � � � � . Доказать, что в
этом случае � � � � � � � .
        6. Перечислите все элементы бинарного отношения � и нарисуйте
его граф:
        1) � � �� x, y � : x � y� на множестве � � �1,2,3,4,5� ;
        2) � � �� x, y � : y � x � 1� на множестве � � �1,2,3,4,5,6,7,8,9,10�.



                                                 18

Страницы