ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 2331
Скачиваний: 10
менты упорядоченного множества имеет лишь такое множество, которое
упорядочено рефлексивным отношением
ϕ
.
Отношения
≤
и
≥
для чисел являются отношениями нестро-
гого порядка, а отношения
<
и
>
— отношениями строгого по-
рядка. Оба отношения полностью упорядочивают множества
R
и
N
.
Отношение включения
⊆
на множестве всех подмножеств Б
(
A
)
некоторого множества
A
задает нестрогий частичный порядок. Отноше-
ние строгого включения
⊂
задает строгий частичный порядок.
В качестве
A
рассмотрим множество
E
n
упорядоченных наборов
длины
n
из нулей и единиц. Введем отношение предшествования:
набор
(
α
1
, . . . , α
n
)
∈
E
n
предшествует набору
(
β
1
, . . . , β
n
)
∈
E
n
, записыва-
ется как
(
α
1
, . . . , α
n
)
(
β
1
, . . . , β
n
)
, если
α
i
≤
β
i
для всех
i
= 1
, n
.
Построенное отношение является отношением нестрогого порядка на
частично упорядоченном множестве
E
n
.
§ 6. Рекомендации к решению задач
При доказательстве равенств и включений для отношений можно
пользоваться методикой, разработанной в главе 1,
§
7
для множеств.
При этом следует учитывать, что элементами отношения на множестве
A
являются упорядоченные пары
(
x, y
)
,
x
∈
A
,
y
∈
A
.
Пример 1.
Докажем справедливость равенства
(
ϕ
◦
ψ
)
−
1
=
ψ
−
1
◦
ϕ
−
1
.
Решение. Пусть
(
x, y
)
∈
(
ϕ
◦
ψ
)
−
1
⇐⇒
(
y, x
)
∈
(
ϕ
◦
ψ
)
⇐⇒ ∃
z
такое, что
(
y, z
)
∈
ϕ
и
(
z, x
)
∈
ψ
⇐⇒ ∃
z
(
z, y
)
∈
ϕ
−
1
и
(
x, z
)
∈
ψ
−
1
⇐⇒
(
x, y
)
∈
ψ
−
1
◦
ϕ
−
1
.
Пример 2.
Пусть
ϕ
1
,
ϕ
2
,
ψ
1
,
ψ
2
— отношения на множестве
A
,
тогда из включений
ϕ
1
⊆
ϕ
2
,
ψ
1
⊆
ψ
2
следует включение
ϕ
−
1
1
∩
ψ
1
⊆
ϕ
−
1
2
∩
ψ
2
.
Действительно, имеет место следующая последовательность утвер-
ждений:
(
x, y
)
∈
ϕ
−
1
1
∩
ψ
1
⇐⇒
(
x, y
)
∈
ϕ
−
1
1
и
(
x, y
)
∈
ψ
1
⇐⇒
⇐⇒
(
y, x
)
∈
ϕ
1
и
(
x, y
)
∈
ψ
1
=
⇒
(
y, x
)
∈
ϕ
2
и
(
x, y
)
∈
ψ
2
⇐⇒
⇐⇒
(
x, y
)
∈
ϕ
−
1
2
и
(
x, y
)
∈
ψ
2
⇐⇒
(
x, y
)
∈
ϕ
−
1
2
∩
ψ
2
,
которая завершает доказательство.
21
При решении задач на построение отношений с заданными свойства-
ми и на исследование свойств заданных отношений следует иметь в виду,
что то или иное свойство имеет место, если его характеристика, например
(
x, x
)
/
∈
ϕ
в случае антирефлексивности, должна выполняться для всех
элементов
x
множества
A
. Отсутствие того или иного свойства можно
доказать, указав по крайней мере один элемент или пару элементов из
A
, для которых характеристика свойства не имеет места.
Пример 3.
Пусть на множестве
A
=
{
α, β, γ
}
задано отношение
ϕ
=
{
(
α, β
)
,
(
β, γ
)
,
(
γ, α
)
}
. Это отношение не является рефлексивным,
так как
(
α, α
)
/
∈
ϕ
; оно антирефлексивно:
(
α, α
)
/
∈
ϕ
,
(
β, β
)
/
∈
ϕ
,
(
γ, γ
)
/
∈
ϕ
; не симметрично
(
α, β
)
∈
ϕ
, но
(
β, α
)
/
∈
ϕ
; антисимметрично:
(
α, β
)
∈
ϕ
и
(
β, α
)
/
∈
ϕ
,
(
β, γ
)
∈
ϕ
и
(
γ, β
)
/
∈
ϕ
,
(
γ, α
)
∈
ϕ
и
(
α, γ
)
/
∈
ϕ
;
не транзитивно:
(
α, β
)
∈
ϕ
,
(
β, γ
)
∈
ϕ
, но
(
α, γ
)
/
∈
ϕ
.
Пример 4.
Покажем, что отношение
ϕ
на
R
:
(
x, y
)
∈
ϕ
⇐⇒
x
−
y
∈
Q
,
(2
.
2)
является отношением эквивалентности.
Действительно, отношение (2.2.) рефлексивно, так как
(
x, x
)
∈
ϕ
⇐⇒
x
−
x
= 0
∈
Q
,
симметрично:
(
x, y
)
∈
ϕ
⇐⇒
x
−
y
∈
Q
⇐⇒
y
−
x
∈
Q
⇐⇒
(
y, x
)
∈
ϕ
и транзитивно:
(
x, y
)
∈
ϕ
и
(
y, z
)
∈
ϕ
⇐⇒
x
−
y
∈
Q
и
y
−
z
∈
Q
=
⇒
=
⇒
x
−
z
∈
Q
⇐⇒
(
x, z
)
∈
ϕ.
§ 7. Задачи и упражнения для самостоятельной работы
2.1. Приведите примеры бинарных отношений на множестве целых
чисел
Z
. Найдите для них дополнение, объединение, пересечение, раз-
ность и произведение. Постройте соответствующее множество на плос-
кости.
2.2. Для следующих бинарных отношений, определенных на множе-
стве
R
, найти область определения, область значений и изобразить на
плоскости это отношение:
1)
ϕ
=
{
(
x, y
)
|
x, y
∈
R
, x
2
y
= 1
}
;
2)
ϕ
=
{
(
x, y
)
|
x, y
∈
R
, x
+
y
= 1
, x
≤
0
, y
≥
0
}
;
3)
ϕ
=
{
(
x, y
)
|
x, y
∈
R
, x
= 1
,
−
5
< y <
5
}
;
22
4)
ϕ
=
{
(
x, y
)
|
x, y
∈
R
, x
2
+
y
2
= 4
}
;
5)
ϕ
=
{
(
x, y
)
|
x, y
∈
Z
, x
+
y <
5
, x
≥
0
, y
≤
0
}
.
2.3. Построить таблицу отношения
ψ
=
{
(
m, n
)
|
m
+
n
= 10
, m, n
∈ {
1
,
2
,
3
,
4
,
5
,
6
}}
.
Каким из свойств: рефлексивность, антирефлексивность, симметричность,
антисимметричность, транзитивность — обладает это отношение?
2.4. Построить на множестве чисел
{
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
}
отношение
эквивалентности, соответствующее следующему разбиению этого мно-
жества на классы: а)
A
1
=
{
1
,
2
,
3
}
,
A
2
=
{
4
,
5
}
,
A
3
=
{
6
,
7
,
8
}
; б)
A
1
=
{
1
,
3
,
5
,
7
}
,
A
2
=
{
2
,
4
,
6
,
8
}
; в)
A
i
=
{
i
}
, i
= 1
,
8
.
2.5. Изобразить графы следующих отношений:
1)
ϕ
1
=
{
(
a, b
)
,
(
a, c
)
,
(
a, d
)
,
(
b, c
)
,
(
b, d
)
,
(
b, e
)
,
(
e, b
)
,
(
d, a
)
,
(
e, e
)
}
;
2)
ϕ
2
=
{
(1
,
2)
,
(1
, a
)
,
(
a, b
)
,
(
b, a
)
,
(
a,
4)
,
(3
, b
)
}
.
2.6. Показать, что
ϕ
◦
ψ
6
=
ψ
◦
ϕ
, если
ϕ
=
{
(0
,
1)
,
(1
,
0)
,
(
b,
0)
,
(
a,
1)
}
,
ψ
=
{
(0
,
0)
,
(0
,
1)
}
.
2.7. На множестве
M
=
{
a, b, c, d,
1)
}
заданы отношения
ϕ
1
,
ϕ
2
,
ϕ
3
,
ϕ
4
, графы которых изображены на рисунках 9, 10, 11, 12, соответ-
ственно. Построить
ϕ
−
1
1
,
ϕ
−
1
4
,
ϕ
1
◦
ϕ
1
,
ϕ
1
◦
ϕ
4
,
ϕ
1
◦
ϕ
−
1
1
,
ϕ
2
◦
ϕ
−
1
4
,
ϕ
2
◦
ϕ
3
,
ϕ
−
1
2
◦
ϕ
3
,
ϕ
−
1
2
◦
ϕ
4
,
ϕ
−
1
2
◦
ϕ
−
1
3
,
ϕ
2
◦
ϕ
−
1
3
,
ϕ
4
◦
ϕ
−
1
3
.
Рис. 9:
ϕ
1
Рис. 10:
ϕ
2
Рис. 11:
ϕ
3
Рис. 12:
ϕ
4
23
2.8. Построить бинарное отношение:
1) рефлексивное, симметричное, не транзитивное;
2) рефлексивное, антисимметричное, не транзитивное;
3) рефлексивное, не симметричное, транзитивное;
4) не рефлексивное, антисимметричное, транзитивное;
5) не рефлексивное, симметричное, транзитивное.
2.9. Какими свойствами обладают следующие отношения:
1)
ϕ
1
=
{
(
α, α
)
,
(
β, γ
)
,
(
γ, δ
)
,
(
β, β
)
,
(
δ, β
)
}
;
2)
ϕ
2
=
{
(
α, α
)
,
(
β, β
)
,
(
γ, γ
)
,
(
δ, δ
)
,
(
β, δ
)
,
(
α, β
)
}
;
3)
ϕ
3
=
{
(
γ, δ
)
,
(
δ, γ
)
,
(
β, β
)
,
(
β, γ
)
,
(
γ, β
)
,
(
α, β
)
}
;
4)
ϕ
4
=
{
(
α, α
)
,
(
γ, δ
)
,
(
δ, β
)
,
(
β, δ
)
,
(
δ, γ
)
}
;
5)
ϕ
5
=
{
(
α, α
)
,
(
β, γ
)
,
(
γ, δ
)
,
(
β, β
)
,
(
δ, β
)
}
.
2.10. Сколько существует бинарных отношений на множестве
A
,
если мощность
A
равна
n
?
2.11. Для каких бинарных отношений справедливо равенство
ϕ
−
1
=
ϕ
(по определению
ϕ
=
A
2
\
ϕ
).
2.12. Бинарным отношением между элементами множеств
A
и
B
называется любое подмножество
ϕ
множества
A
×
B
:
ϕ
⊆
A
×
B
.
Сколько существует таких бинарных отношений, если
A
и
B
— конеч-
ные множества мощности
n
и
m
соответственно?
2.13. Пусть
ϕ
1
,
ϕ
2
и
ψ
— произвольные бинарные отношения на
множестве
A
. Показать, что имеют место равенства:
1)
ψ
◦
(
ϕ
1
∪
ϕ
2
) = (
ψ
◦
ϕ
1
)
∪
(
ψ
◦
ϕ
2
)
;
2)
(
ϕ
2
◦
ϕ
1
)
∪
ψ
= (
ϕ
1
∪
ψ
)
◦
(
ϕ
2
∪
ψ
)
;
3)
(
ϕ
1
∪
ϕ
2
)
◦
ψ
= (
ϕ
1
◦
ψ
)
∪
(
ϕ
2
◦
ψ
)
;
4)
ϕ
∩
ϕ
=
ϕ
∪
ϕ
=
ϕ
;
5)
(
ϕ
−
1
)
−
1
=
ϕ
;
6)
(
ϕ
1
∩
ϕ
2
)
−
1
=
ϕ
−
1
1
∩
ϕ
−
1
2
.
2.14. Пусть
ϕ
1
,
ϕ
2
и
ψ
— произвольные бинарные отношения на
множестве
A
. Доказать, что имеют место включения:
1)
(
ϕ
1
∩
ϕ
2
)
◦
ψ
⊆
(
ϕ
1
◦
ψ
)
∩
(
ϕ
2
◦
ψ
)
;
2)
ψ
◦
(
ϕ
1
∩
ϕ
2
)
⊆
(
ψ
◦
ϕ
1
)
∩
(
ψ
◦
ϕ
1
)
.
Можно ли в этих выражениях знак включения заменить знаком ра-
венства?
2.15. Доказать, что если
ϕ
1
и
ϕ
2
симметричны, то симметричны и
отношения
ϕ
1
∪
ϕ
2
,
ϕ
1
∩
ϕ
2
.
2.16. Доказать, что любое отношение
ϕ
, симметричное и антисим-
метричное одновременно, является транзитивным.
2.17. Доказать, что если
ϕ
1
⊆
ϕ
2
, то
ϕ
−
1
1
⊆
ϕ
−
1
2
(
ϕ
1
и
ϕ
2
— бинар-
ные отношения).
24
2.18. Доказать, что если
ϕ
1
и
ϕ
2
— антирефлексивны, то
ϕ
1
∩
ϕ
2
— антирефлексивно.
2.19. Доказать, что если
ϕ
1
⊆
ϕ
2
, то
ϕ
−
1
1
⊆
ϕ
−
1
2
.
2.20. Доказать, что если
ϕ
1
и
ϕ
2
— симметричные, то
(
ϕ
1
∩
ϕ
2
)
−
1
— симметрично.
2.21. Доказать, что если
ϕ
1
и
ϕ
2
— рефлексивные, то
(
ϕ
1
∩
ϕ
2
)
−
1
— рефлексивно.
2.22. Доказать, что если
ϕ
1
и
ϕ
2
— рефлексивные, то
ϕ
1
∩
ϕ
2
—
рефлексивно.
2.23. Доказать, что если
ϕ
1
и
ϕ
2
— антирефлексивны, то
(
ϕ
1
∩
ϕ
2
)
−
1
— антирефлексивно.
2.24. Показать, что отношение включения
⊆
на множестве всех под-
множеств исходного множества
A
является отношением нестрого поряд-
ка. Построить для этого отношения транзитивное замыкание.
2.25. Что является транзитивным замыканием отношений
быть
отцом
,
быть сыном
?
2.26. Показать, что отношение предшествования на множестве
E
n
является отношением нестрогого порядка. Что является транзитивным
замыканием этого отношения?
2.27. Показать, что если
ϕ
— отношение эквивалентности, то
ϕ
−
1
также отношение эквивалентности.
2.28. Показать, что пересечение любой системы отношений эквива-
лентности на некотором множестве является отношением эквивалентно-
сти на этом множестве.
25