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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

17
В качестве примера рассмотрим некоторые композиции рассматри-
ваемых бинарных отношений:
(
)
(
)
(
)
{
}
=
Î
Î
$
=
1221
,,,:,
r
r
r
r
yzzxzyx
o
(
)
{
}
(
)
{
}
2:,,2:,
22
£+==£+$= yxyxyzzxzyx ;
(
)
(
)
(
)
{
}
=
Î
Î
$
=
2112
,,,:,
r
r
r
r
yzzxzyx
o
( )
{ }
( )
=
ï
þ
ï
ý
ü
ï
î
ï
í
ì
ê
ê
ë
é
£+-
£+
³=£+=$=
2
2
,0:,2,:,
2
yx
yx
xyxyzzxzyx
(
)
{
}
2,0:, £+-³= yxxyx ;
(
)
(
)
(
)
{
}
=
Î
Î
$
=
2332
,,,:,
r
r
r
r
yzzxzyx
o
(
)
{
}
=
£
+
Î
+
$
=
2,:, yzzxzyx
(
)
{
}
(
)
{
}
RRyxkkyxyzkzxzyx
´
=
£
+
-
Î
$
=
£
+
Î
=
+
$
=
2:,2,:,
(
)
(
)
(
)
{
}
=
Î
Î
$
=
3223
,,,:,
r
r
r
r
yzzxzyx
o
(
)
{
}
RRyzzxzyx
´
=
Î
+
£
+
$
=
,2:, .
Остальные композиции постройте самостоятельно.
Пример 10. Пусть
C
– произвольное множество, обозначим симво-
лом
C
I
отношение на множестве
C
вида
(
)
{
}
(
)
{
}
C
I
C
Î
=
=
=
xxxyxyx :,:, .
Докажите, что для любого бинарного отношения
r
между элемен-
тами множеств
A
и
B
выполняются равенства:
r
r
r
r
=
=
AB
I
I
o
o
, .
Решение.
(
)
(
)
(
)
{
}
=
Î
Î
Î
$
´
Î
=
BB
I
B
B
A
I
yzzxzyx ,,,:,
r
r
o
(
)
(
)
{
}
(
)
(
)
{
}
;,:,,,:,
r
r
r
=
Î
´
Î
=
=
Î
Î
$
´
Î
=
yxyxyzzxzyx
B
A
B
B
A
(
)
(
)
(
)
{
}
=
Î
Î
Î
$
´
Î
=
r
r
yzzxzyx ,,,:,
AA
I
A
B
A
I
o
(
)
(
)
{
}
(
)
(
)
{
}
.,:,,,:,
r
r
r
=
Î
´
Î
=
Î
=
Î
$
´
Î
=
yxyxyzzxzyx
B
A
A
B
A
Пример 11. Пусть
c
f
j
,
,
бинарные отношения, определенные на
множестве
C
. Докажите следующие утверждения:
1) если
f
j
,
– симметричные (антисимметричные) отношения, то
(
)
1
-
Ç
fj
– симметричное (антисимметричное) отношение;
2)
(
)
(
)
(
)
c
f
c
j
c
f
j
o
o
o
\\
Ê
.
Решение. 1. Пусть
f
j
,
– симметричные отношения, докажем, что
(
)
1
-
Ç
fj
– симметричное отношение. Пусть
( ) ( ) ( )
(
)
( )
Þ
î
í
ì
Î
Î
ÞÇÎÞÇÎ
-
f
j
fjfj
xy
xy
xyyx
,
,
,,
1
     В качестве примера рассмотрим некоторые композиции рассматри-
ваемых бинарных отношений:
     �1 � � 2 � �� x, y � : �z � x, z � � � 2 , � z , y � � �1� �
          �                                    � �
        � � x, y � : �z x � z � 2, z � y 2 � � x, y � : x � y 2 � 2 ;    �
        � 2 � �1 � �� x, y � : �z � x, z � � �1 , � z , y � � � 2 � �
                                                    ��                  � x � y � 2 ��
          �                                    �
        � � x, y � : �z x � z 2 , z � y � 2 � �� x, y � : x � 0, �                   ��
                                                     ��                 �� x � y � 2��
          �
        � � x, y � : x � 0, � x � y � 2 ;  �
        � 2 � � 3 � �� x, y � : �z � x, z � � � 3 , � z , y � � � 2 � �
        � �� x, y � : �z x � z � � , z � y � 2� �
        � �� x, y � : �z x � z � k � � , z � y � 2� � �� x, y � : �k � � k � x � y � 2� � R � R

       � 3 � � 2 � �� x, y � : �z � x, z � � � 2 , � z , y � � � 3 � �
       � �� x, y � : �z x � z � 2, z � y � � � � R � R .
       Остальные композиции постройте самостоятельно.

      Пример 10. Пусть � – произвольное множество, обозначим симво-
лом � � отношение на множестве � вида
                            � � � �� x, y � : x � y� � �� x, x � : x � � � .
      Докажите, что для любого бинарного отношения � между элемен-
тами множеств � и � выполняются равенства:
                                 � � � � � �,         � ��� � �.
      Решение. � � � � � �� x, y � � � � � : �z � � � x, z � � � , � z , y � � � � � �
      � �� x, y � � � � � : �z � � � x, z � � � , z � y� � �� x, y � � � � � : � x, y � � � � � � ;

        � � � � � �� x, y � � � � � : �z � � � x, z � � � � , � z , y � � � � �
        � �� x, y � � � � � : �z � � x � z , � z , y � � � � � �� x, y � � � � � : � x, y � � � � � � .

    Пример 11. Пусть � , � , � бинарные отношения, определенные на
множестве � . Докажите следующие утверждения:
    1) если � , � – симметричные (антисимметричные) отношения, то
�� � � ��1 – симметричное (антисимметричное) отношение;
      2) �� \ � � � � � �� � � � \ �� � � � .
       Решение. 1. Пусть � , � – симметричные отношения, докажем, что
�� � � ��1 – симметричное отношение. Пусть
                                                 �� y, x � � �
      � x, y � � �� � � ��1 � � y, x � � � � � � �             �
                                                 �� y, x � � �
                                                   17

Страницы