Материал: Prak_alg
16
пара
( )
r
Î
3
,
1
,
а
пара
( )
r
Ï
1
,
3
;
не
является
антисимметричным
,
поскольку
,
например
,
пары
( )
2
,
1
и
( )
1
,
2
принадлежат
r
,
но
2
1
¹
;
не
является
транзи
-
тивным
,
поскольку
,
например
( )
( )
r
r
Î
Î
1
,
2
,
2
,
3
,
а
( )
r
Ï
1
,
3
.
2)
Данное
отношение
является
рефлексивным
,
поскольку
для
любой
точки
R
x
Î
разность
Z
Î
=
-
0
x
x
,
т
.
е
.
( )
R
x
x
Î
,
;
является
симметричным
,
поскольку
принадлежность
любой
пары
( )
y
x
,
отношению
r
означает
Z
Î
=
-
k
y
x
,
но
тогда
Z
Î
-
=
-
k
x
y
,
т
.
е
.
пара
( )
r
Î
x
y
,
;
не
является
ан
-
тисиммеричным
,
поскольку
,
например
,
пары
(
)
r
Î
2
.
3
,
2
.
1
и
(
)
r
Î
2
.
1
,
2
.
3
,
но
2
.
1
2
.
3
¹
;
является
транзитивным
,
поскольку
для
любых
R
z
y
x
Î
,
,
принад
-
лежность
пар
( )
y
x
,
и
( )
z
y
,
отношению
r
означает
Z
Î
=
-
k
y
x
и
Z
Î
=
-
n
z
y
,
но
тогда
Z
Î
+
=
-
n
k
z
x
,
т
.
е
.
( )
r
Î
z
x
,
.
3)
Данное
отношение
не
является
рефлексивным
,
поскольку
из
всех
пар
( )
Z
Î
x
x
x
,
,
только
пара
( )
r
Î
0
,
0
,
ведь
для
всех
остальных
Z
Î
x
не
выполнено
равенство
x
x
3
2
=
;
не
является
симметричным
,
поскольку
,
на
-
пример
,
пара
( )
r
Î
2
,
3
(
2
3
3
2
×
=
×
),
а
пара
( )
r
Ï
3
,
2
(
3
3
2
2
×
¹
×
);
является
антисимметричным
,
поскольку
для
любых
пар
( )
( )
r
r
Î
Î
x
y
y
x
,
,
,
одно
-
временно
выполняются
равенства
y
x
3
2
=
и
x
y
3
2
=
,
т
.
е
.
x
x
4
9
=
и
y
y
9
4
=
,
но
это
может
быть
только
в
том
случае
,
если
0
=
=
y
x
;
не
являет
-
ся
транзитивным
,
поскольку
,
например
,
пара
( )
r
Î
6
,
9
(
6
3
9
2
×
=
×
),
пара
( )
r
Î
4
,
6
(
4
3
6
2
×
=
×
),
но
пара
( )
r
Ï
4
,
9
(
4
3
9
2
×
¹
×
).
4)
Данное
отношение
не
является
рефлексивным
,
поскольку
для
( )
Z
R
Î
Æ
пересечение
Æ
=
Æ
Ç
Æ
,
т
.
е
.
(
)
r
Ï
Æ
Æ
,
;
является
симметрич
-
ным
,
поскольку
принадлежность
любой
пары
( )
y
x
,
отношению
r
означа
-
ет
Æ
¹
Ç
y
x
,
но
тогда
Æ
¹
Ç
x
y
,
т
.
е
.
пара
( )
r
Î
x
y
,
;
не
является
транзи
-
тивным
,
поскольку
,
например
,
пара
{ } { }
(
)
r
Î
3
,
2
,
2
,
1
(
{ } { } { }
Æ
¹
=
Ç
2
3
,
2
2
,
1
)
и
пара
{ } {
}
(
)
r
Î
7
,
6
,
3
,
3
,
2
(
{ } {
} { }
Æ
¹
=
Ç
3
7
,
6
,
3
3
,
2
),
но
пара
{ } {
}
(
)
r
Ï
7
,
6
,
3
,
2
,
1
,
так
как
{ } {
}
Æ
=
Ç
7
,
6
,
3
2
,
1
.
Пример
9
.
Пусть
на
множестве
R
заданы
следующие
бинарные
от
-
ношения
:
( )
{
}
;
:
,
2
1
y
x
y
x
=
=
r
( )
{
}
;
2
:
,
2
£
+
=
y
x
y
x
r
( )
{
}
3
,
:
.
x y x y
r
=
+ Î Z
Найдите
обратные
к
данным
бинарным
отношениям
и
всевозможные
композиции
этих
бинарных
отношений
.
Решение
.
Вначале
выпишем
обратные
отношения
:
( ) ( )
{
} ( )
{
}
2
1
1
1
:
,
,
:
,
x
y
y
x
x
y
y
x
=
=
Î
=
-
r
r
;
( ) ( )
{
} ( )
{
}
2
2
1
2
2
:
,
,
:
,
r
r
r
=
£
+
=
Î
=
-
x
y
y
x
x
y
y
x
;
( ) ( )
{
} ( )
{
}
3
3
1
3
:
,
,
:
,
r
r
r
=
Î
+
=
Î
=
-
Z
x
y
y
x
x
y
y
x
.
17
В
качестве
примера
рассмотрим
некоторые
композиции
рассматри
-
ваемых
бинарных
отношений
:
( )
( )
( )
{
}
=
Î
Î
$
=
1
2
2
1
,
,
,
:
,
r
r
r
r
y
z
z
x
z
y
x
o
( )
{
}
( )
{
}
2
:
,
,
2
:
,
2
2
£
+
=
=
£
+
$
=
y
x
y
x
y
z
z
x
z
y
x
;
( )
( )
( )
{
}
=
Î
Î
$
=
2
1
1
2
,
,
,
:
,
r
r
r
r
y
z
z
x
z
y
x
o
( )
{
}
( )
=
ïþ
ï
ý
ü
ïî
ï
í
ì
ê
ê
ë
é
£
+
-
£
+
³
=
£
+
=
$
=
2
2
,
0
:
,
2
,
:
,
2
y
x
y
x
x
y
x
y
z
z
x
z
y
x
( )
{
}
2
,
0
:
,
£
+
-
³
=
y
x
x
y
x
;
( )
( )
( )
{
}
=
Î
Î
$
=
2
3
3
2
,
,
,
:
,
r
r
r
r
y
z
z
x
z
y
x
o
( )
{
}
=
£
+
Î
+
$
=
2
,
:
,
y
z
z
x
z
y
x
Z
( )
{
} ( )
{
}
R
R
y
x
k
k
y
x
y
z
k
z
x
z
y
x
´
=
£
+
-
Î
$
=
£
+
Î
=
+
$
=
2
:
,
2
,
:
,
Z
Z
( )
( )
( )
{
}
=
Î
Î
$
=
3
2
2
3
,
,
,
:
,
r
r
r
r
y
z
z
x
z
y
x
o
( )
{
}
R
R
y
z
z
x
z
y
x
´
=
Î
+
£
+
$
=
Z
,
2
:
,
.
Остальные
композиции
постройте
самостоятельно
.
Пример
10
.
Пусть
C
–
произвольное
множество
,
обозначим
симво
-
лом
C
I
отношение
на
множестве
C
вида
( )
{
} ( )
{
}
C
I
C
Î
=
=
=
x
x
x
y
x
y
x
:
,
:
,
.
Докажите
,
что
для
любого
бинарного
отношения
r
между
элемен
-
тами
множеств
A
и
B
выполняются
равенства
:
r
r
r
r
=
=
A
B
I
I
o
o
,
.
Решение
.
( )
( )
( )
{
}
=
Î
Î
Î
$
´
Î
=
B
B
I
B
B
A
I
y
z
z
x
z
y
x
,
,
,
:
,
r
r
o
( )
( )
{
} ( )
( )
{
}
;
,
:
,
,
,
:
,
r
r
r
=
Î
´
Î
=
=
Î
Î
$
´
Î
=
y
x
y
x
y
z
z
x
z
y
x
B
A
B
B
A
( )
( )
( )
{
}
=
Î
Î
Î
$
´
Î
=
r
r
y
z
z
x
z
y
x
,
,
,
:
,
A
A
I
A
B
A
I
o
( )
( )
{
} ( )
( )
{
}
.
,
:
,
,
,
:
,
r
r
r
=
Î
´
Î
=
Î
=
Î
$
´
Î
=
y
x
y
x
y
z
z
x
z
y
x
B
A
A
B
A
Пример
11
.
Пусть
c
f
j
,
,
бинарные
отношения
,
определенные
на
множестве
C
.
Докажите
следующие
утверждения
:
1)
если
f
j
, –
симметричные
(
антисимметричные
)
отношения
,
то
(
)
1
-
Ç
f
j
–
симметричное
(
антисимметричное
)
отношение
;
2)
(
)
(
) (
)
c
f
c
j
c
f
j
o
o
o
\
\
Ê
.
Решение
.
1.
Пусть
f
j
, –
симметричные
отношения
,
докажем
,
что
(
)
1
-
Ç
f
j
–
симметричное
отношение
.
Пусть
( ) (
)
( )
( )
( )
Þ
î
í
ì
Î
Î
Þ
Ç
Î
Þ
Ç
Î
-
f
j
f
j
f
j
x
y
x
y
x
y
y
x
,
,
,
,
1
18
( )
( )
( )
( ) (
)
1
,
,
,
,
.
,
симметричность
x y
x y
y x
x y
j f
j
j f
j f
f
-
Î
ìï
Þ
Þ
Î Ç Þ
Î
Ç
í
Î
ïî
Пусть
f
j
, –
антисимметричные
отношения
,
докажем
,
что
(
)
1
-
Ç
f
j
–
антисимметричное
отношение
.
Пусть
( ) (
)
( ) (
)
( )
( )
( ) ( )
( ) ( )
Þ
î
í
ì
Î
Î
Þ
î
í
ì
Ç
Î
Ç
Î
Þ
ïî
ï
í
ì
Ç
Î
Ç
Î
-
-
f
j
f
j
f
j
f
j
f
j
x
y
y
x
x
y
y
x
y
x
x
y
x
y
y
x
,
,
,
,
,
,
,
,
,
,
1
1
y
x
ричность
антисиммет
=
Þ
f
j
,
.
1.
Докажем
требуемое
включение
.
Пусть
( ) (
) (
) ( )
( )
Þ
Ï
Î
Þ
Î
c
f
c
j
c
f
c
j
o
o
o
o
y
x
y
x
y
x
,
,
,
\
,
( )
( )
( )
( )
( )
( )
( )
( )
( )
Þ
î
í
ì
Î
Î
$
Þ
ï
î
ï
í
ì
Ï
Î
Î
$
Þ
ï
ï
î
ï
ï
í
ì
ê
ë
é
Ï
Ï
"
î
í
ì
Î
Î
$
Þ
f
j
c
f
j
c
f
c
j
c
\
,
,
,
,
,
,
,
,
,
y
z
z
x
z
y
z
y
z
z
x
z
y
z
z
x
z
y
z
z
x
z
( ) (
)
c
f
j
o
\
,
Î
Þ
y
x
ЗАДАЧИ
И
УПРАЖНЕНИЯ
1.
Пусть
{ }
´
*
=
C
, .
Перечислите
все
элементы
множеств
4
3
C
C
,
.
2.
Найдите
геометрическую
интерпретацию
множества
B
´
A
,
где
A
–
множество
точек
отрезка
[ ]
1
,
0 ,
а
B
–
множество
точек
квадрата
с
вер
-
шинами
в
точках
( ) ( ) ( ) ( )
1
1
0
1
1
0
0
0
,
,
,
,
,
,
,
.
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)
( )
{
}
y
x
y
x
<
=
:
,
r
на
множестве
{
}
5
,
4
,
3
,
2
,
1
=
C
;
2)
( )
{
}
1
:
,
+
=
=
x
y
y
x
r
на
множестве
{
}
10
,
9
,
8
,
7
,
6
,
5
,
4
,
3
,
2
,
1
=
C
.
19
7.
Для
каждого
из
следующих
бинарных
отношений
,
определенных
на
множестве
R
,
найдите
область
определения
,
область
значений
и
нари
-
суйте
декартову
диаграмму
:
1)
( )
{
}
;
:
,
y
x
y
x
£
=
r
2)
( )
{
}
;
:
,
y
x
y
x
=
=
r
3)
( )
{
}
;
1
4
:
,
2
2
£
+
=
y
x
y
x
r
4)
( )
{
}
;
:
,
2
2
y
x
y
x
=
=
r
5)
( )
{
}
;
log
:
,
2
x
y
y
x
=
=
r
6)
( )
{
}
x
y
y
x
sin
:
,
=
=
r
.
8.
Даны
бинарные
отношения
r
между
элементами
множеств
A
и
B
,
найдите
область
определения
и
область
значений
для
данных
бинарных
отношений
:
1)
{
}
{ } { } { } { }
{
}
( )
{
}
;
:
,
,
3
,
5
,
2
,
2
,
1
,
1
,
5
,
4
,
3
,
2
,
1
y
x
y
x
Î
´
Î
=
=
=
B
A
B
A
r
2)
( )
(
)
;
:
,
,
,
,
þ
ý
ü
î
í
ì
=
´
Î
=
=
´
=
b
a
c
c
b
a
Q
B
A
B
Z
Z
A
r
3)
( )
{
}
;
1
:
,
,
,
=
×
´
Î
=
=
=
y
x
y
x
Q
B
A
B
Z
A
r
4)
( )
{
}
a
b
y
x
Q
2
:
,
,
,
=
´
Î
=
=
=
B
A
B
Z
A
r
.
9.
Для
каждого
из
следующих
бинарных
отношений
выясните
,
каки
-
ми
свойствами
(
рефлексивность
,
симметричность
,
антисимметричность
,
транзитивность
)
оно
обладает
и
какими
не
обладает
:
1)
( )
{
}
;
:
,
2
2
y
x
R
R
y
x
=
´
Î
=
r
2)
( )
{
}
;
1
:
,
2
2
=
+
´
Î
=
y
x
R
R
y
x
r
3)
( )
{
}
;
1
:
,
>
×
´
Î
=
y
x
R
R
y
x
r
4)
( )
{
}
;
:
,
x
y
R
R
y
x
=
´
Î
=
r
5)
( )
{
}
;
:
,
2
2
y
y
x
x
R
R
y
x
+
=
+
´
Î
=
r
6)
( )
{
}
;
1
:
,
+
£
´
Î
=
y
x
y
x
Z
Z
r
7)
( )
{
}
;
3
:
,
y
x
на
делится
y
x
+
´
Î
=
Z
Z
r
8)
( )
{
}
;
:
)
(
)
(
,
y
x
y
x
Í
´
Î
=
Z
R
Z
R
r
9)
( )
{
}
.
:
)
(
)
(
,
Æ
=
Ç
´
Î
=
y
x
y
x
Z
R
Z
R
r
10.
Пусть
1)
( )
{
}
2
1
:
,
y
x
R
R
y
x
=
´
Î
=
r
;
( )
{
}
5
:
,
2
£
+
´
Î
=
y
x
R
R
y
x
r
;
2)
( )
{
}
y
x
R
R
y
x
=
´
Î
=
3
3
:
,
r
;
( )
{
}
x
y
R
R
y
x
sin
:
,
4
=
´
Î
=
r
.
11.
Найдите
всевозможные
композиции
.
4
,
3
,
2
,
1
,
=
k
i
k
i
r
r
o
20
12.
Покажите
,
что
равенство
j
f
f
j
o
o
=
верно
не
для
любых
бинар
-
ных
отношений
.
13.
Докажите
,
что
для
любого
бинарного
отношения
r
выполняются
условия
:
r
r
R
D
=
-
1
и
r
r
D
R
=
-
1
.
14.
Пусть
c
f
j
,
,
–
бинарные
отношения
,
определенные
на
некото
-
ром
множестве
.
Докажите
следующие
утверждения
:
1)
(
)
1
1
1
\
\
-
-
-
=
f
j
f
j
;
2)
(
)
(
) (
)
c
f
c
j
c
f
j
o
o
o
Ç
Í
Ç
;
3)
(
)
1
1
1
-
-
-
=
j
f
f
j
o
o
;
4)
(
)
1
1
1
-
-
-
È
=
È
f
j
f
j
;
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
Î
y
x
,
часто
используют
за
-
пись
y
x
»
(
читается
:
x
эквивалентен
y
).
Классом
эквивалентности
,
порожденным
элементом
x
,
называется
подмножество
множества
C
,
состоящее
из
тех
элементов
C
Î
y
,
для
ко
-
торых
( )
r
Î
y
x
,
.
Класс
эквивалентности
,
порожденный
элементом
x
,
обо
-
значается
через
[ ]
x
:
[ ]
( )
{
}
.
,
:
r
Î
Î
=
y
x
y
x
C
Разбиением
множества
C
называется
совокупность
попарно
непере
-
секающихся
подмножеств
C
таких
,
что
каждый
элемент
множества
C
принадлежит
одному
и
только
одному
из
этих
подмножеств
.
Всякое
раз
-
биение
множества
C
определяет
на
C
отношение
эквивалентности
r
:
( )
r
Î
y
x
,
тогда
и
только
тогда
,
когда
x
и
y
принадлежат
одному
подмно
-
жеству
разбиения
.
С
другой
стороны
,
всякое
отношение
эквивалентности