3290
.pdfнарного отношения мы понимаем схему, в которой элементы
множества |
изображаются точками на плоскости, |
элементы |
|||||||
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 |
|
пара 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 . |
|||||
Для любых бинарных отношений выполняются следую- |
||||||||||||
щие свойства: |
|
|
|
|
|
|
|
|
|
|
||
1. |
1 |
1 |
|
; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
||
2. |
|
|
|
1 |
1 |
|
1 . |
|
|
|
|
|
2 |
1 |
|
|
|
|
|
|
|||||
|
|
|
1 |
|
2 |
|
|
|
|
|
||
Пример 1. На множестве |
|
|
5,6,7,8,9,10,11,12,13,14,15 |
|||||||||
задано бинарное отношение |
|
x, y : x делится на y . |
Нарисуйте граф данного бинарного отношения.
Решение. Расположим на плоскости точки множества . Точки x, y , для которых пара x, y , соединим
стрелкой, направленной от x к |
y . Пары |
x, x |
изобра- |
||
зим петлей вокруг точки |
x . Результатом такого построения |
||||
будет граф |
|
|
|
|
|
5 |
6 |
7 |
8 |
9 |
|
10 |
11 |
12 |
13 |
14 |
Пример 2. Для следующего бинарного отношения, определенного на множестве R , найдите область определения, область значений и нарисуйте декартову диаграмму
x, y : x2 y .
Решение. В соответствии с определением
D |
x |
R : |
y |
x, y |
R . |
R |
y |
: x |
|
x, y |
R 0 . |
Декартова диаграмма для данного отношения имеет вид
y
x
Пример 3. Для каждого из следующих бинарных отношений выясните, какими свойствами (рефлексивность, симметричность, антисимметричность, транзитивность) оно обладает и какими не обладает.
1) 1,2 , (2,1), 1,1 , 1,3 , 3,2 , 3,3 на множестве
1,2,3 ;
2) |
x, y : x |
y |
на множестве |
R ; |
3) |
x, y : 2x |
3y на множестве |
; |
|
4) |
x, y : x |
y |
на множестве |
. |
|
Решение. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
1) Данное отношение не является рефлексивным, по- |
||||||||||||||||
скольку для точки |
2 |
пара |
2,2 |
|
; не является сим- |
||||||||||||
метричным, поскольку, например, пара |
|
1,3 |
|
, |
а |
пара |
|||||||||||
3,1 |
|
; не является антисимметричным, поскольку, напри- |
|||||||||||||||
мер, |
пары |
1,2 и |
2,1 |
принадлежат |
, но 1 |
2 ; не является |
|||||||||||
транзитивным, поскольку, например |
3,2 |
|
|
, |
2,1 |
, а |
|||||||||||
3,1 |
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2) |
Данное отношение является рефлексивным, поскольку |
|||||||||||||||
для |
любой |
точки |
x |
R |
разность |
|
x |
x |
0 |
|
, |
т.е. |
|||||
x, x R ; |
является симметричным, поскольку |
принадлеж- |
|||||||||||||||
ность |
любой |
пары |
x, y |
отношению |
|
|
|
означает |
|||||||||
x |
y |
k |
|
, |
но |
тогда |
y |
x |
k |
|
|
, т.е. пара |
|||||
y, x |
|
; не является антисиммеричным, |
поскольку, напри- |
||||||||||||||
мер, |
пары |
|
1.2,3.2 |
|
и 3.2,1.2 |
, но |
3.2 |
1.2 ; явля- |
|||||||||
ется транзитивным, поскольку для любых |
x, y, z |
R принад- |
|||||||||||||||
лежность |
пар |
x, y |
и |
y, z |
отношению |
|
|
означает |
|||||||||
x |
y |
k |
|
и |
y |
z |
n |
, |
но тогда x |
z |
|
k |
n |
, |
|||
т.е. |
x, z |
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3) Данное отношение не является рефлексивным, по- |
||||||||||||||||
скольку из всех пар |
x, x , x |
|
только пара |
0,0 |
|
, |
ведь |
||||||||||
для всех остальных x |
не выполнено равенство 2x |
3x ; |
|||||||||||||||
не является симметричным, поскольку, например, |
пара |
||||||||||||||||
3,2 |
|
|
( 2 3 |
3 2 ), а пара 2,3 |
|
( 2 2 |
3 3); явля- |
||||||||||
ется |
|
антисимметричным, |
поскольку |
для |
|
любых |
пар |
x, y |
, y, x |
одновременно выполняются равенства
2x |
3y |
и 2 y |
3x , |
т.е. |
9x |
4x |
и 4 y |
9 y , но это может |
|||||
быть только в том случае, если x |
y |
0 ; не является транзи- |
|||||||||||
тивным, |
поскольку, например, пара |
9,6 |
( 2 9 |
3 6 ), |
|||||||||
пара |
6,4 |
|
( 2 6 |
3 4 ), но пара |
9,4 |
( 2 9 |
3 4 ). |
||||||
|
|
4) Данное отношение не является рефлексивным, по- |
|||||||||||
скольку |
для |
|
|
|
пересечение |
|
, |
т.е. |
|||||
|
, |
|
; |
является симметричным, поскольку принадлеж- |
|||||||||
ность любой пары x, y |
отношению |
означает x |
y |
, |
|||||||||
но тогда |
y |
x |
, |
т.е. пара y, x |
|
; не является транзи- |
|||||||
тивным, |
поскольку, |
например, |
|
пара |
1,2 , 2,3 |
|
|||||||
( |
1,2 |
2,3 |
|
2 |
) |
и |
пара |
2,3 , 3,6,7 |
|
||||
( |
2,3 |
3,6,7 |
3 |
|
), но пара |
1,2 , 3,6,7 |
, |
так |
|||||
как |
1,2 |
3,6,7 |
. |
|
|
|
|
|
|
|
|||
|
|
Пример 4. Пусть на множестве R заданы следующие би- |
|||||||||||
нарные отношения: |
|
|
|
|
|
|
|
|
|||||
|
|
|
1 |
|
x, y : x y 2 ; |
2 |
|
x, y : x y 2 ; |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
3 |
|
x, y : x |
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Найдите обратные к данным бинарным отношениям и всевозможные композиции этих бинарных отношений.
Решение. Вначале выпишем обратные отношения:
1
1
1
2
1
3
x, y : y, x x, y : y, x x, y : y, x
1
2
3
x, y : y |
x2 |
; |
|
x, y : y |
x |
2 |
2 ; |
x, y : y |
x |
|
3 . |
В качестве примера рассмотрим некоторые композиции рассматриваемых бинарных отношений:
|
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 : z x z2 , z y 2 |
x, y : x 0, |
x |
|
|
y |
2 |
|
||||||||||
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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 |
|||||||||
, 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 . |
|
|
|||||||||||||
|
Остальные композиции постройте самостоятельно. |
|
|||||||||||||||
|
Пример 5. Пусть |
|
- произвольное множество, обозна- |
|
|||||||||||||
чим символом |
|
отношение на множестве |
|
вида |
|
|
|||||||||||
|
|
|
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 |
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
Пример 6. |
Пусть |
, , бинарные отношения, опреде- |
|
ленные на множестве |
. Докажите следующие утверждения: |
||
1) |
если , |
- симметричные (антисимметричные) отно- |
|
шения, |
то |
1 - симметричное (антисимметричное) от- |
ношение; |
|
|
|
|
|
|
|
|
|
2) |
\ |
|
|
|
\ |
. |
|
|
|
Решение. 1. |
Пусть , |
- симметричные отношения, |
до- |
||||||
кажем, что |
|
|
|
1 - симметричное отношение. Пусть |
|
|
|||
x, y |
|
|
1 |
y, x |
|
y, x |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
y, x |
|
|
|||
|
|
|
|
|
|
|
|
||
симметричность |
, |
x, y |
x, y |
y, x |
1 |
; |
|||
x, y |
|||||||||
|
|
|
|
|
|
|
|||
Пусть |
|
, |
|
- антисимметричные отношения, докажем, |
|||||
что |
|
1 - |
|
антисимметричное отношение. Пусть |
x, y
y, x
1 |
y, x |
x, y , y, x |
|
||
1 |
x, y |
x, y , y, x |
|
|
|
антисимметричность , x |
y . |
1. |
Докажем требуемое включение. Пусть |
|
||||
x, y |
\ |
|
x, y |
, x, y |
|
|
z |
x, z |
|
x, z |
|
|
|
z, y |
|
|
x, z |
|
||
|
z |
z, y |
z |
|
||
|
x, z |
z, y |
\ |
|||
z |
|
z, y |
|
|||
z, y |
|
|
|
|
||
|
|
|
|
|
|
x, y |
\ |
ЗАДАЧИ И УПРАЖНЕНИЯ
1.Перечислите все элементы бинарного отношения
и нарисуйте его граф: |
|
|
|
|
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 . |
|
|
|
|
2. |
Для каждого из следующих бинарных отноше- |
|||
ний, определенных на множестве R , |
найдите область опреде- |
|||
ления, область значений и нарисуйте декартову диаграмму: |
||||
1) |
x, y : x |
y ; |
|
|
2) |
x, y : x |
y ; |
|
|
3) |
x, y : x2 |
4 y 2 |
1 ; |
|
4) |
x, y : x2 |
y 2 ; |
|
|
5) |
x, y : y |
log2 x ; |
|
|
6) |
x, y : y |
sin x . |
|
|
3.Даны бинарные отношения между элементами
множеств |
и |
, найдите область определения и область |
|||||
значений для данных бинарных отношений: |
|
|
|||||
1) |
1,2,3,4,5 , |
1 , 1,2 , 2,5 , 3 |
, |
x, y |
|
: x y ; |
|
2) |
, |
Q, |
a, b , c |
|
: c |
a |
; |
|
b |
||||||
|
|
|
|
|
|
|
|
3) |
, |
Q, |
x, y |
: x y 1 ; |
|
|
|
4) |
, |
Q, |
x, y |
: b 2a . |
|
|
4. Для каждого из следующих бинарных отношений выясните, какими свойствами (рефлексивность, симметричность, антисимметричность, транзитивность) оно обладает и какими не обладает:
1)
2)
3)
4)
5)
6)
7)
8)
9)
5.
1
2
3
4
x, y R R : x2 |
|
y 2 ; |
|
|||||
x, y R R : x2 |
|
y 2 |
1 ; |
|
||||
x, y |
R |
R : x |
y 1 ; |
|
||||
x, y |
R |
R : y |
|
x |
|
; |
|
|
|
|
|
|
|||||
x, y R R : x x2 |
y y 2 ; |
|
||||||
x, y |
|
: x |
|
y |
1 ; |
|
||
x, y |
|
: 3 делится на x |
y ; |
|||||
x, y |
|
( ) |
( ) : x y ; |
|
||||
x, y |
|
( ) |
( ) : x y |
. |
Пусть |
|
|
|
|
x, y |
R |
R : x |
y 2 |
; |
x, y |
R |
R : x |
y |
5 ; |
x, y |
R |
R : x3 |
y ; |
|
x, y |
R |
R : y |
sin x . |
Найдите всевозможные композиции i k i, k 1,2,3,4.
6. |
Покажите, что равенство |
верно не |
для любых бинарных отношений.
7.Докажите, что для любого бинарного отношения
выполняются условия: |
D |
1 R и R 1 D . |
||
8. |
Пусть |
, |
, |
- бинарные отношения, опреде- |
ленные на некотором множестве. Докажите следующие утверждения:
1) |
\ |
1 |
1 \ |
1; |
|
2) |
|
|
|
|
; |
3) |
|
1 |
1 |
1 ; |
|
4) |
|
1 |
1 |
1; |
|
5) |
|
|
|
|
. |
10.Приведите примеры бинарных отношений:
1)рефлексивных и транзитивных, но не антисимметрихчных;
2)транзитивных и симметричных, но не рефлексивных;
3)рефлексивных и симметричных, но не транзитивных;
4)рефлексивных и транзитивных, но не симметричных.
11.Докажите, что если |
- транзитивное и симметричное |
||
бинарное отношение на множестве |
, область определения |
||
которого совпадает с |
, то |
рефлексивно. |
1.3 Специальные бинарные отношения
Рефлексивное, симметричное и транзитивное отношение
на множестве |
называется отношением эквивалентно- |
сти на множестве |
. Для отношения эквивалентности вместо |
записи x, y |
часто используют запись x y (читается : |
x эквивалентен y )
Классом эквивалентности, порожденным элементом x, на-
зывается подмножество множества |
, |
состоящее из тех эле- |
|||
ментов y |
, для которых |
x, y |
|
. Класс эквивалентно- |
|
сти, порожденный элементом x, обозначается через x : |
|||||
|
x |
y |
: |
x, y |
. |
Разбиением множества |
называется совокупность по- |
||
парно непересекающихся подмножеств |
таких, что каждый |
||
элемент множества |
принадлежит одному и только одному |