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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

12
графом бинарного отношения мы понимаем схему, в которой элементы
множества
C
изображаются точками на плоскости, элементы
C
Î
y
x
,
,
такие, что пара
(
)
r
Î
yx, соединяются стрелкой, направленной от
x
к
y
,
пары
(
)
r
Î
xx, изображаются петлей вокруг точки
x
. Под декартовой диа-
граммой понимают изображение пар
(
)
r
Î
yx, в декартовой прямоуголь-
ной системе координат.
Областью определения бинарного отношения
называется множество
(
)
{
}
r
Î
$
Î
=
yxyxD ,:
C
.
Областью значений бинарного отношения
называется множество
(
)
{
}
r
Î
$
Î
=
yxxyR ,:
U
.
Бинарное отношение
на множестве
C
называется рефлексивным,
если для любого
C
Î
x
пара
(
)
r
Î
xx, . Если
C
– конечное множество, то
рефлексивность бинарного отношения
означает, что на графе данного
бинарного отношения вокруг каждой точки
x
из
C
есть петля. Если
=
C
, то рефлексивность бинарного отношения
с точки зрения декар-
товой диаграммы означает, что в число изображенных точек войдут все
точки прямой
x
x
y
=
)
(
.
Бинарное отношение
на множестве
C
называется симметричным,
если для любых
C
Î
y
x
,
из принадлежности пары
(
)
yx, отношению
следует принадлежность этому отношению также пары
(
)
xy, . Если
C
–
конечное множество, то симметричность бинарного отношения
означа-
ет, что на графе данного бинарного отношения все присутствующие стрел-
ки двусторонние. Если
=
C
, то симметричность бинарного отношения
с точки зрения декартовой диаграммы означает, что изображенное мно-
жество симметрично относительно прямой
x
x
y
=
)
(
.
Бинарное отношение
на множестве
C
называется антисиммет-
ричным, если для любых
C
Î
y
x
,
из принадлежности пар
(
)
yx, и
(
)
xy, от-
ношению
следует
y
x
=
. Если
C
– конечное множество, то антисим-
метричность бинарного отношения
означает, что на графе данного би-
нарного отношения все присутствующие стрелки односторонние.
Бинарное отношение
на множестве
C
называется транзитивным,
если для любых
C
Î
z
y
x
,
,
из принадлежности пар
(
)
yx, и
(
)
zy, отноше-
нию
следует принадлежность этому отношению также пары
(
)
zx, .
Обратным отношением для
называется отношение
(
)
(
)
{
}
rr
Î=
-
xyyx ,:,
1
.
Композицией отношений
1
r
и
2
r
называется отношение
(
)
(
)
(
)
{
}
2112
r
r
r
r
Î
Î
$
=
yzzxzyx ,,,:,
o
. 
графом бинарного отношения мы понимаем схему, в которой элементы
множества � изображаются точками на плоскости, элементы x, y � � ,
такие, что пара � x, y � � � соединяются стрелкой, направленной от x к y ,
пары � x, x � � � изображаются петлей вокруг точки x . Под декартовой диа-
граммой понимают изображение пар � x, y � � � в декартовой прямоуголь-
ной системе координат.
      Областью определения бинарного отношения � называется множество
                             D � � �x � � : �y � x, y � � � �.
      Областью значений бинарного отношения � называется множество
                           R � � �y �� : �x � x, y � � � �.
      Бинарное отношение � на множестве � называется рефлексивным,
если для любого x � � пара � x, x � � � . Если � – конечное множество, то
рефлексивность бинарного отношения � означает, что на графе данного
бинарного отношения вокруг каждой точки x из � есть петля. Если
� � R , то рефлексивность бинарного отношения � с точки зрения декар-
товой диаграммы означает, что в число изображенных точек войдут все
точки прямой y ( x) � x .
      Бинарное отношение � на множестве � называется симметричным,
если для любых x, y � � из принадлежности пары � x, y � отношению �
следует принадлежность этому отношению также пары � y, x � . Если � –
конечное множество, то симметричность бинарного отношения � означа-
ет, что на графе данного бинарного отношения все присутствующие стрел-
ки двусторонние. Если � � R , то симметричность бинарного отношения
� с точки зрения декартовой диаграммы означает, что изображенное мно-
жество симметрично относительно прямой y ( x) � x .
      Бинарное отношение � на множестве � называется антисиммет-
ричным, если для любых x, y � � из принадлежности пар � x, y � и � y, x � от-
ношению � следует x � y . Если � – конечное множество, то антисим-
метричность бинарного отношения � означает, что на графе данного би-
нарного отношения все присутствующие стрелки односторонние.
      Бинарное отношение � на множестве � называется транзитивным,
если для любых x, y, z � � из принадлежности пар � x, y � и � y, z � отноше-
нию � следует принадлежность этому отношению также пары � x, z � .
      Обратным отношением для � называется отношение
                             � �1 � �� x, y � : � y , x � � � �.
      Композицией отношений � 1 и � 2 называется отношение
                 � 2 � � 1 � �� x, y � : �z � x, z � � � 1 , � z , y � � � 2 �.
                                             12

Страницы