Файл: С. Д. Данилова С. С. Михайлова УланУдэ 2022дискретнаяматематика.pdf

13
Пусть ???? ∈ ???? ∪ (????\????), тогда по определению объединения ???? ∈ ???? или ???? ∈ ????\????.
Если ???? ∈ ????, то ???? ∈ ???? ∪ ????.
Если ???? ∈ ????\???? , то по определению разности множеств имеем ???? ∈ ???? и ????  ???? .
Так как ???? ∈ ???? , то скажем, что ???? ∈ ???? ∪ ????.
Контрольные вопросы
1. Что такое множество?
2. Как обозначаются множества и элементы множеств?
3. Какие существуют способы задания множеств?
4. Что такое мощность множества, и как она обозначается?
5. Что означает понятие пустого множества?
6. Что такое универсальное множество, и от чего зависит его содержимое?
7. Сколько элементов содержат пустое множество и универсальное множество?
8. Что называется подмножеством, собственным подмножеством множества?
9. Чем различаются отношения включения и строгого включения?
10. На чем основано равенство множеств?
11. Что такое булеан множества, и как он обозначается?
12. Какова мощность булеана?
13. Какие операции выполняются над множествами?
14. Какими свойствами обладают теоретико-множественные операции?
15. Что такое теоретико-множественное тождество, и на чем основывается его дока- зательство?

14

15
1.2.2. n-арные и бинарные отношения
Часто в вычислениях необходимо выбирать элементы множеств, которые удовлетво- ряют некоторому «отношению». Это понятие довольно общее, поэтому широко приме- нимо. При соответствующем выборе отношения его аргументы могут быть связаны какой- либо формулой, иногда достаточно простой, если возможно найти удачное описание.
Предположим, что ????– множество программ; ???? – конечное множество данных.
Если мы выберем конкретное значение из множества ????, то оно может использоваться в некоторых программах из множества ????. Или же каждая программа из ???? использует неко- торую совокупность данных из ????. Это показывает наличие отношения между данными и программами, которое можно интерпретировать как элементы декартова произведения
???? × ????.
Определение 1.13. n-арным отношением ????на множествах ????
1
, … , ????
????
называется любое подмножество декартового произведения ????
1
× … × ????
????
Другими словами, элементы
????
1
∈ ????
1
, … , ????
????
∈ ????
????
связаны отношением
???? тогда и только тогда, когда (????
1
, … , ????
????
) ∈ ????.
Наиболее часто встречаются отношения при ???? = 2; в этом случае они называются би- нарными отношениями.
Определение 1.15. Бинарным отношением ???? на множествах ???? и ???? называется любое подмножество декартового произведения ???? × ????. Если ???? = ????, то говорят, что бинарное от- ношение ???? задано на множестве ????.
Пример
Пусть ???? = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. На множестве ???? задано отношение:
???? = {(????, ????)|???? – делитель ????, ???? ≤ 5}.
Представим это отношение в явном виде, т. е. перечислим его элементы:
???? = {
(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10),
(2,2), (2,4), (2,6), (2,8), (2,10), (3,3), (3,6), (3,9), (4,4), (4,8), (5,5), (5,10)
}.
Из примера видим, что бинарные отношения можно представлять разными способами задания множеств: отношение R в первом случае задано описанием его свойств, во втором
– перечислением.
Кроме того, конечные бинарные отношения можно задавать матрицей и различными графическими способами, в том числе в виде ориентированного графа.
Матрица бинарного отношения на множестве ???? – это квадратная матрица ????(???? × ????), в которой элемент ????
????????
определяется следующим образом:
????
????????
= {
1,
если (????
????
, ????
????
) ∈ ????;
0,
в противном случае.

16
Пример
На множестве ???? = {1, 2, 3, 4, 5} отношение ???? задано описанием свойств его элемен- тов:
???? = {(????, ????)|???? < ????, ????, ???? ∈ ????}.
В виде перечисления это отношение имеет вид:
???? = {(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)}.
Матрица отношения ???? имеет вид:
Отношение ???? в виде ориентированного графа представлено на рисунке 1.6.
2
Рисунок 1.6 – Граф бинарного отношения
Определение 1.16. Для любого множества ???? определим тождественное отношение
????
????
и универсальное отношение
????
????
следующим образом:
????
????
= {(????, ????)|???? ∈ ????}; ????
????
= {(????, ????)| ???? ???? ∈ ????}.
Последнее выражение показывает, что ????
????
= ????
2
Поскольку  ∈ ????
2
,
то  является отношениемна множестве ???? и называется пустым
отношением.
Примечание:
Хотя любое отношение является множеством и обозначается прописной буквой, ино- гда возможно обозначение отношенийстрочными греческими буквами: ????, ????, ????, …
1 3
2 5
4 0
1 1
1 1
1 0
1 0
1 1
2 0
0 0
1 1
3 1
0 0
0 4
0 0
0 0
0 5
0
С
=
1 3
4 5

17
1.2.3. Области определения и значений бинарного отношения.
Обратное отношение
Определение 1.17. Областью определения ????
????
бинарного отношения
???? называется множе- ство значений ????, таких, что пара (????, ????) принадлежит отношению ????:
????
????
= {????| ???? такое, что (????, ????) ∈ ????}.
Определение 1.18. Областью значений ????
????
бинарного отношения
???? называется множе- ство значений ????, таких, что пара(????, ????) принадлежит отношению ????:
????
????
= {????|???? такое, что (????, ????) ∈ ????}.
Пример
Дано бинарное отношение:
???? = {(????, ????)|???? = ????
2
, ????, ???? ∈ ????}.
Тогда:
????
????
= ????
, ????
????
= {1, 4, 5, 9, 16, … }
Определение 1.19. Пусть ???? – бинарное отношение. Обратным отношением????
−1
для отно- шения ???? называется множество:
????
−1
= {(????, ????)|(????, ????) ∈ ????}.
Таким образом, ????
−1
связывает те же пары элементов, что и
????
,
но «в другом порядке».
Следовательно, если ???? ⊆ ???? × ????, то:
????
−1
⊆ ???? × ????;
????
????
−1
= ????
????
;
????
????
−1
= ????
????
Пример
Для отношения из предыдущего примера имеем:
????
−1
= {(????, ????)|???? = ????
2
, ????, ???? ∈ ????}.
????
????
−1
= {1, 4, 5, 9, 16, … };
????
????
−1
= ????.

18
1.2.4. Свойства бинарных отношений
Определение 1.20. Бинарное отношение ???? на множестве ???? называется рефлексивным, если:
∀???? ∈ ???? (????, ????) ∈ ????, и антирефлексивным, если:
∀???? ∈ ???? (????, ????) ∉ ????.
Пример
1. Дано отношение:
???? = {(????, ????)|???? = ????, ????, ???? ∈ ????}.
Оно рефлексивно, так как:
∀???? ∈ ???? ???? = ????.
2. Отношение «быть сыном» на множестве людей антирефлексивно, так как любой человек не является сыном самого себя.
3. Дано отношение:
???? = {(????, ????)|???? = ????
2
, ????, ???? ∈ ????}.
Это отношение не рефлексивно, так как для всех натуральных чисел кроме 1:
???? ≠ ????
2
Оно также не антирефлексивно, так как имеется число 1, для которого:
???? = ????
2
Таким образом, данное отношение показывает, что отношение может быть нерефлек- сивным и неантирефлексивным.
Определение 1.21. Бинарное отношение ???? на множестве ???? называется симметрич-
ным, если:
(????, ????) ∈ ????  (????, ????) ∈ ????
,
и антисимметричным, если:
(????, ????) ∈ ???? и (????, ????) ∈ ????  ???? = ????

19
Пример
1. Отношение
???? = {(????, ????)|???? = ????, ????, ???? ∈ ????} симметрично:
???? = ????  ???? = ????
В то же время это отношение антисимметрично: если ???? = ???? и ???? = ????  ???? = ????
Следовательно, мы видим, что отношение может быть одновременно и симметрич- ным, и антисимметричным.
2. Отношение «быть другом» на некотором множестве людей симметрично:
«если ???? является другом ????, то и ???? – друг ????».
Но оно не является антисимметричным, так как из того, что « ???? – друг y» и
«???? – друг x» не следует, что ???? = ????, т.е. речь не идет об одном и том же человеке.
3. Отношение
???? = {(????, ????)|???? = ????
2
, ????, ???? ∈ ????} несимметрично, так как неверно, что:
???? = ????
2
 ???? = ????
2
Но оно является антисимметричным, так как: если ???? = ????
2
и ???? = ????
2
 ???? = ????.
Определение 1.22. Бинарное отношение ???? на множестве ???? называется транзитивным, если:
(????, ????) ∈ ???? и (????, ????) ∈ ????  (????, ????) ∈ ????
Пример
1. Отношение
???? = {(????, ????)|???? = ????, ????, ???? ∈ ????} транзитивно: если ???? = ???? и ???? = ????  ???? = ????
2. Отношение
«быть не старше» на множестве людей транзитивно:
«если ???? не старше ???? и ???? не старше ????, то и ???? не старше ????».
3. Отношение
«быть сыном» на множестве людей не транзитивно:
«если первый человек является сыном второго, второй – сыном третьего, то первый не яв- ляется сыном третьего человека».

20
1.2.5. Композиция отношений
Определение 1.22. Композицией (произведением) отношений ????
1
⊆ ???? × ???? и ????
2
⊆ ???? ×
???? называется отношение:
????
1
∘ ????
2
= {(????, ????)| ∃????, такое, что (????, ????) ∈ ????
1
и (????, ????) ∈ ????
2
}.
Пример
1. Даны множества:
???? = {1,2,3}
,
???? = {2,3}
,
???? = {0,1}
На этих множествах заданы отношения:
????
1
⊆ ???? × ????: ????
1
= {(1,2), (1,3), (2,2), (3,2)};
????
2
⊆ ???? × ????: ????
2
= {(2,0), (2,1), (3,0)}.
Тогда:
????
1
∘ ????
2
= {(1,0), (1,1), (2,0), (2,1), (3,0), (3,1)}.
2. Пусть даны отношения на множестве действительных чисел:
????
1
⊆ ???? × ????:
???? = ????
3
;
????
2
⊆ ???? × ????:
???? = sin ????.
Для нахождения композиции по определению в первой формуле вместо переменной
???? подставляем ????, а во второй – вместо ???? подставляем ????, что дает нам систему уравнений:
{
???? = ????
3
???? = ???????????? ????
Решение полученной системы даст нам композицию:
????
1
∘ ????
2
:
???? = sin ????
2
Аналогичным образом получаем композиции:
????
2
∘ ????
1
:
???? = sin
3
???? ;
????
1 2
:
???? = ????
9
????
2 2
:
???? = sin sin ????

21
Контрольные вопросы
1. Что такое декартово произведение множеств?
2. Какова мощность декартова произведения множеств?
3. На скольких множествах задается декартова степень?
4. Что такое n-арное и бинарное отношения?
5. Что такое бинарное отношение, заданное на множестве A?
6. Какими способами можно представлять n-арные и бинарные отношения?
7. Как изображается граф бинарного отношения?
8. Как определяются область определения и область значений бинарного отношения?
9. Сколько можно построить бинарных отношений на n-элементном множестве?
10. Какие существуют свойства бинарных отношений?
11. Если отношение не рефлексивно, является ли оно антирефлексивным?
12. Если отношение не симметрично, является ли оно антисимметричным?
13. Как выглядят матрица и граф рефлексивного отношения?
14. Как выглядят матрица и граф симметричного отношения?
15. Как выглядят матрица и граф транзитивного отношения?
16. Как определяется композиция отношений?

22
Тема 1.3. Отношения эквивалентности и порядка
1.3.1. Отношение эквивалентности и разбиение множества
Отношение эквивалентности является обобщением понятия равенства. Эквивалент- ность можно рассматривать как совпадение элементов только по части существенных при- знаков, так как полностью тождественных объектов в природе не бывает. Важнейшее зна- чение эквивалентности заключается в том, что это отношение определяет признак, который позволяет исследуемое множество объектов определенным образом классифицировать.
Например, отношение «проживать в одном доме» во множестве жителей города является эквивалентностью и разбивает это множество на подмножества людей – соседей по дому.
Определение 1.23. Бинарное отношение ???? на множестве ???? называется отношением
эквивалентности, если оно обладает свойствами рефлексивности, симметричности и тран- зитивности.
Пример
Дано отношение:
???? = {(????, ????)|???? = ????, ????, ???? ∈ ????}
Проверим это отношение на свойства рефлексивности, симметричности и транзитив- ности:
1)
∀???? ∈ ???? ???? = ????, ⟹ ???? рефлексивно;
2)
???? = ???? ⟺ ???? = ????, ⟹ ???? симметрично;
3)
???? = ???? и ???? = ???? ⟹ ???? = ????, ⟹ ???? транзитивно.
Все три свойства доказаны, значит, отношение равенства является отношением экви- валентности.
Без доказательства приведем еще некоторые примеры отношения эквивалентности
(доказать самим):
1. Отношение «иметь тот же возраст» на множестве всех людей.
2. Отношение «иметь один и тот же остаток при делении на 3» на множестве нату- ральных чисел.
3. Отношение параллельности на множестве всех прямых.
Можно привести и другие примеры. Все они наводят на мысль, что если на множестве задано отношение эквивалентности, то все его элементы можно разбить на непересекаю- щиеся подмножества. Все элементы в любом из таких подмножеств эквивалентны друг другу. Таким образом, любому отношению эквивалентности соответствует некоторое раз- биение множества, на котором это отношение задано.
Определение 1.25. Разбиением множества ???? называется такая совокупность непу- стых подмножеств ????
1
, ????
2
, … , ????
????
множества
???? , которая удовлетворяет следующим усло- виям: