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

23
???? = ????
1
⋃????
2
⋃ … ⋃ ????
????
;
????
????
⋂????
????
=  для ∀ ???? ≠ ????, ????, ???? ≤ ????.
Каждое из подмножеств ????
1
, ????
2
, … , ????
????
разбиения называется классом эквивалентно-
сти.
Теорема 2. Если на множестве ???? задано отношение эквивалентности ????, то оно порождает разбиение множества ???? на классы эквивалентности, такое, что:
▪ любые два элемента одного класса находятся в отношении ????;
▪ любые два элемента разных классов не находятся в отношении ????.
Пример
1. Разбиение многоугольников на группы по числу вершин. Классы эквивалентности
– множество треугольников, множество четырехугольников и т. п.
2. Разбиение треугольников по свойствам углов. Классы эквивалентности – множе- ство остроугольных треугольников, множество прямоугольных треугольников, множество тупоугольных треугольников.
3. Разбиение студентов по академическим группам. Каждый класс эквивалентности – группа студентов.
Определение 1.26. Фактор-множеством называется множество всех классов эквива- лентности по данному отношению ???? на множестве ????, обозначается ????/????. Мощность фак- тор-множества называется индексом разбиения множества ????, обозначается
????????????(
????/????
)
Отметим, что при обозначении класса эквивалентности можно указать в квадратных скобках одного из его представителей. Например, если множество
{????, ????, ????, ????, ????, ????}
– это класс эквивалентности некоторого отношения, то обозначить его можно как
[????]
,
[????] и т.д.
Пример
1. Рассмотрим отношение равенства площадей треугольников на множестве треуголь- ников ????:
???? = {(????, ????)| ????
????
= ????
????
, ????, ???? ∈ ????}.
Докажем, что отношение R является отношением эквивалентности:
1)
∀???? ∈ ????
????
????
= ????
????
, ⟹ ???? рефлексивно;
2)
????
????
= ????
????
⟺
????
????
= ????
????
, ⟹ ???? симметрично;
3)
????
????
= ????
????
и
????
????
= ????
????
⟹
????
????
= ????
????
, ⟹ ???? транзитивно.
Все три условия выполняются, значит, R – отношение эквивалентности. Следова- тельно, оно разбивает множество ???? на классы эквивалентности.

24
Каждый класс ????
????
, ???? = 1, … , ∞, – это множество всех треугольников с одинаковой пло- щадью. Очевидно, что элементов в каждом классе и самих классов эквивалентности беско- нечное число.
Совокупность классов
{
????
1
, ????
2
, … , ????
????
, …
}
– это фактор-множество множества
???? по отношению ???? (т. е. по отношению равенства площадей треугольников).
2.
Рассмотрим отношение «иметь общий остаток от деления на 7» на множестве
????
. Оно является отношением эквивалентности:
1) любое натуральное число имеет общий остаток от деления на 7 с самим собой;
2) если одно натуральное число имеет со вторым натуральным числом общий остаток от деления на 7, то и второе число имеет с первым числом общий остаток от деления на 7;
3) если одно натуральное число имеет со вторым общий остаток от деления на 7, а второй – с третьим, то и первый со вторым также имеют общий остаток от деления на 7.
Классами эквивалентности являются:
[7] = {7, 14, 21, … } – множество чисел, имеющих в остатке 0;
[15] = {8, 15, 22, … } – множество чисел, имеющих в остатке 1;
[30] = {9, 16, 23, . . . }
– множество чисел, имеющих в остатке 2;
[24] = {10, 17, 24, … } – множество чисел, имеющих в остатке 3;
[11] = {11, 18, 25, … }
множество чисел, имеющих в остатке 4;
[40] = {12, 19, 26, … } множество чисел, имеющих в остатке 5;
[13] = {13, 20, 27, … } множество чисел, имеющих в остатке 6.
Фактор-множеством будет следующее разбиение множества
????
:
????/???? = {[7], [15], [30], [24], [11], [40], [13]}, а индексом разбиения – ????????????(????/????) = 7.
1.3.2. Отношения порядка
Понятие частично упорядоченного множества является фундаментальным для совре- менной математики и встречается во многих прикладных вопросах. Важность понятия упо-
рядочение возрастает в связи с тем фактом, что множество любой мощности можно совер- шенно упорядочить. Это верно для любого конечного множества. По индукции оно верно для множества целых чисел. Поскольку множество целых чисел счетно, то и любое другое счетное множество можно совершенно упорядочить.
Поскольку имеется возможность двоякого введения упорядочивания (как в случае не- строго неравенства £, так и строгого неравенства <), то имеются отношения строгого и не- строгого порядка. Оба типа отношений называются отношениями порядка.

25
Определение 1.27. Бинарное отношение ???? на множестве ???? называется отношением
нестрогого порядка (или частичным порядком), если оно рефлексивно, антисимметрично и транзитивно.
Пример
Пусть ???? – произвольное множество. Тогда отношение включения ???? на булеане
????(????)
есть тривиальное отношение порядка:
1)
∀???? ∈ ????(????) ???? ⊆ ????, ⟹ ???? рефлексивно;
2)
???? ⊆ ???? и ???? ⊆ ???? ⟹ ???? = ????, ⟹ ???? антисимметрично;
3)
???? ⊆ ???? и ???? ⊆ ???? ⟹ ???? ⊆ ????, ⟹ ???? транзитивно.
Определение 1.28. Бинарное отношение ???? на множестве ???? называется отношением
строгого порядка (или полным порядком), если оно антирефлексивно и транзитивно.
Пример
На множестве ???? дано отношение строгого неравенства:
???? = {(????, ????)|???? < ????, ????, ???? ∈ ????}
Проверим свойства этого отношения:
1)
∀???? ∈ ???? ???? ≮ ????, ⟹ ???? антирефлексивно;
2)
???? < ???? и ???? < ????, ⟹ ???? < ???? ⟹ ???? транзитивно.
Определение 1.29. Пусть дано бинарное отношение ???? на множестве ???? . Элементы
????, ???? ∈ ???? называются сравнимыми, если выполняется
????????????
или
????????????.
Определение 1.30. Частичный порядок???? на множестве ???? называется отношением ли-
нейного порядка (или линейным порядком), если любые два элемента из множества
????
срав- нимы.
Пример
Отношение нестрогого неравенства ≤ на числовом множестве является частичным порядком (проверить самим). Любые два элементы множества ????сравнимы между собой: относительно любых двух натуральных чисел ???? и ???? всегда можно сказать, что
???? ≤ ????
или
???? ≤ ????.
Поэтому отношение
≤ является линейным порядком.
Определение 1.31. Множество ???? с заданным на нем частичным порядком называется
частично упорядоченным, обозначается
(
????, ≼
)
. Здесь знак
≼
обозначает любой частичный порядок.
Определение 1.32. Множество A с заданным на нем линейным порядком называется
линейно упорядоченным.

26
Любое частично упорядоченное множество может быть представлено в виде диа-
граммы Хассе, в которой каждый элемент изображается как точка на плоскости, и если ????
≼
????, и не существует такого элемента
????
, для которого ????
≼ ???? ≼
????, то ???? и ???? соединяются отрез- ком, идущим вверх от элемента ???? к элементу ????.
Пример
Рассмотрим частично упорядоченное множество, где
≼
– отношение делимости:
???? =
(
{
2,3,4,6,7,12,16,18
}
, ≼
)
Диаграмма Хассе этого множества представлена на рисунке 1.7:
16 12 18
Рисунок 1.7 – Диаграмма Хассе
Определение 1.32. Пусть
(
????, ≼
)
– частично упорядоченное множество.
▪ Элемент
???? ∈ ????
называется максимальным, если не существует элемента ????, такого что
???? ≺ ????.
▪ Элемент
???? ∈ ????
называется минимальным, если не существует элемента ????, такого что
???? ≺ ????.
Максимальные и минимальные элементы в частично упорядоченных множествах мо- гут существовать, а могут и не существовать, их может быть несколько.
Минимальные и максимальные элементы конечного частично упорядоченного мно- жества легко можно увидеть на диаграмме Хассе: нижние точки – это минимальные эле- менты, верхние – максимальные.
Пример
1. (
????, ≤) – множество вещественных чисел с естественным порядком. В этом множе- стве нет ни максимального, ни минимального элементов.
2. Во множестве
([0,1], ≤) минимальный есть элемент
???? = 0
и максимальный эле- мент
???? = 1
Во множестве (
(0,1], ≤) есть максимальный, но нет минимального элемента.
Во множестве (
[0,1), ≤) есть минимальный, но нет максимального элемента.
3. В приведенном примере (рис. 1.7) по диаграмме Хассе определяем, что 2, 3, 7 – это минимальные элементы; 7, 12, 16, 18 – максимальные элементы.
4 2
6 3
7

27
Определение 1.33. Пусть
(
????, ≼
)
– частично упорядоченное множество.
▪ Элемент
???? ∈ ????
называется наибольшим, если ∀???? ∈ ???? ????
≼
????.
▪ Элемент
???? ∈ ????
называется наименьшим, если ∀???? ∈ ???? ????
≼ ????
Пример
1. Во множестве (
????, ≤) нет ни наибольшего, ни наименьшего элементов.
2. Во множествах ([0,1], ≤), ((0,1], ≤), ([0,1), ≤) наибольшие и наименьшие эле- менты совпадают соответственно с максимальными и минимальными элементами.
3. В частично упорядоченном множестве
???? = ({2, 3, 6, 9, 12, 18, 24, 36},
≼
)
, где
≼
– отношение делимости, 36 – максимальный и наибольший элемент; 2 и 3 – минимальные элементы, наименьшего элемента нет. (Нарисуйте диаграмму Хассе и убедитесь в этом.)
Определение 1.35. Пусть
(
????, ≼
)
– частично упорядоченное множество.
▪ Верхней гранью подмножества ???? ⊆ ???? называется любой элемент
???? ∈ ????
, такой, что
???? ≤ ????
для
∀
???? ∈ ????.
▪ Нижней гранью подмножества ???? ⊆ ???? называется любой элемент
???? ∈ ????
,такой, что
????
≤ ????
для
∀
???? ∈ ????.
Определение 1.36. Пусть
(
????, ≼
)
– частично упорядоченное множество.
▪ Точной верхней гранью подмножества ???? ⊆ ???? называется наименьшая верхняя грань для ????; обозначается sup ????.
▪ Точной нижней гранью подмножества ???? ⊆ ???? называется наибольшая нижняя грань для ????; обозначается inf ????.
Пример
1. В частично упорядоченном множестве
(????, ≤)
для подмножества
???? =
{
4, 5, 6, 7, 8
}
: нижние грани – это числа 1, 2, 3; inf ???? = 3; верхние грани – все натуральные числа, начиная с 9; sup ???? = 9.
2. В частично упорядоченном множестве
???? = ({2, 3, 6, 9, 12, 18, 24, 36}, ≤), где ≤ – это отношение делимости, для подмножества
???? =
{
12,18
}
по диаграмме Хассе (рис. 1.8) определим: нижние грани – это числа 2, 3, 6; inf ???? = 6; верхняя грань – это число 36; sup ???? = 36.

28
Определение 1.37. Линейно упорядоченное множество
(
????, ≼
)
называется вполне упо- рядоченным, если каждое непустое подмножество множества ???? имеет наименьший эле- мент.
Пример
Линейно упорядоченное множество
(????, ≤)
является вполне упорядоченным, так как любое подмножество множества
????
будет иметь наименьший элемент.
Определение 1.38. Бинарное отношение ???? на множестве ???? называется предпорядком, если оно рефлексивно и транзитивно.
Пример
Отношение делимости на множестве целых чисел не является порядком. Но оно ре- флексивно и транзитивно, значит, является предпорядком.
Контрольные вопросы
1. Какими свойствами обладает отношение эквивалентности?
2. Что такое разбиение множества?
3. Как называются подмножества, образующие разбиение?
4. Если задано отношение эквивалентности R на множестве A, то, что можно сказать о разбиении множества A по отношению R?
5. Что такое фактор-множество, и каков минимально возможный индекс фактор- множества?
6. Как можно обозначать классы эквивалентности?
7. Какими свойствами обладают отношение частичного порядка, отношение стро- гого порядка?
8. Какие элементы называются сравнивыми по данному отношению?
Рисунок
1.8 –
Диаграмма Хассе
24
12
18
9 2
6 3
36

29 9. Какому условию должен удовлетворять частичный порядок, чтобы быть линей- ным порядком?
10. Что такое частично упорядоченное множество?
11. Чем отличается частично упорядоченное множество от линейно упорядоченного множества?
12. Как будет выглядеть диаграмма Хассе линейно упорядоченного множества?
13. Чем отличается максимальный элемент от наибольшего элемента, минимальный от наименьшего элемента в упорядоченном множестве?
14. Что такое верхние и нижние грани, sup и inf подмножества упорядоченного мно- жества?
15. Как по диаграмме Хассе можно определить минимальный, максимальный, наименьший, наибольший элементы упорядоченного множества?
16. Как по диаграмме Хассе можно определить верхние и нижние грани, sup и inf не- которого его подмножества упорядоченного множества?
17. Чем будет характеризоваться диаграмма Хассе упорядоченного множества, в ко- тором имеются наибольший и наименьший элементы?

30

31
????: ???? ⟶ ????; или, если ???? ∈ ????, ???? ∈ ???? и (????, ????) ∈ ????:
????: ???? ↦ ????.
Если ???? – функция, то вместо выражения (???? ????, ) ∈ ???? пишут ???? = ????(????) и говорят, что ????
– образ элемента ????; а ???? – прообраз элемента ????.
Пример
Пусть ???? = {−1, 0, 1}. Дана функция:
????: ???? ⟶ ????:
????: ???? ↦ ????
3
Рисунок 1.10 показывает отображение элементов левого множества в элементы пра- вого множества:
1 ↦ 1 3
= 1; 0 ↦ 0 3
= 0; −1 ↦ (−1)
3
= −1.
Рисунок 1.10 – Графическая интерпретация функции ????: ???? ↦ ????
3
Поскольку функция является отношением, то имеют место понятия области опреде- ления и области значений. Однако следует заметить, что обратная функция может суще- ствовать не для любой функции. Следующий пример иллюстрирует данный факт.
Пример
Пусть ???? = {−1, 0, 1}
Функция
????: ???? ⟶ ???? задано следующим образом (рис. 1.11 а):
????: ???? ↦ ????
2
Эта функция не имеет обратной функции, поскольку ????
−1
(1) ∈ {1, 1} (рис. 1.11 б).
1 0
- 1 1
0
- 1
А
А