Дискретная математика | Диаграммы Хассе
- Рефлексивность → p
п 
п 
B - Антисимметричный → p q и q p тогда и только тогда, когда p = q
- Транзитивность → если p q и q r, затем p р
Пример-1: Нарисуйте диаграмму Хассе для (<3, 4, 12, 24, 48, 72>, /)
Объяснение. В соответствии с приведенным выше вопросом сначала мы должны найти посет для делимости.
Пусть набор — A.
A = <(3 
12), (3 24), (3 48), (3 72), (4 12), (4 24), (4 48), (4 72), (12 24), (12 48), (12 72), (24 48), (24 72)>
Итак, теперь диаграмма Хассе будет:
На диаграмме выше 3 и 4 находятся на одном уровне, потому что они не связаны друг с другом и меньше других элементов в наборе. Следующим последующим элементом для 3 и 4 является 12, то есть 12 делится как на 3, так и на 4. Тогда 24 делится на 3, 4 и 12. Следовательно, он помещается над 12. 24 делит как 48, так и 72, но 48 не делит. разделить 72. Следовательно, 48 и 72 не соединяются.
Мы можем видеть транзитивность на нашей диаграмме по мере увеличения уровня.
Пример-2: Нарисуйте диаграмму Хассе для (D 
, /)
Пояснение — Здесь D означает набор натуральных чисел, делителей 12.
Итак, D = <1, 2, 3, 4, 6, 12>
poset A = <(1 2), (1 3), (1 4), (1 6), (1
12), (2 4), (2 6), (2 12), (3 6), (3 12), (4 12), (6 12)>
Итак, теперь диаграмма Хассе будет:
На диаграмме выше 1 — единственный элемент, который делит все остальные элементы, и самый маленький. Следовательно, он находится внизу. Тогда элементы в нашем наборе — это 2 и 3, которые не делят друг друга, поэтому они размещаются на одном уровне отдельно, но делятся на 1 (оба соединены на 1). 4 делится на 1 и 2, а 6 делится на 1, 2 и 3, следовательно, 4 соединяется на 2, а 6 соединяется на 2 и 3. 12 делится на все элементы, следовательно, на 4 и 6 соединяется не на все элементы, потому что мы уже соединили 4 и 6 с меньшими элементами соответственно.
- Максимальный элемент — это элемент POSET, который не меньше любого другого элемента POSET. Или мы можем сказать, что это элемент, не связанный ни с каким другим элементом. Верхние элементы диаграммы Хассе.
- Пример. На диаграмме выше мы можем сказать, что 4,2,3,6,1 связаны с 12 (упорядочены по делению, например (4, /)), но 12 не связаны ни с каким другим. (Поскольку диаграмма Хассе направлена вверх).
- Минимальный элемент — это элемент POSET, который не больше любого другого элемента POSET. Или мы можем сказать, что никакой другой элемент не связан с этим элементом. Нижние элементы диаграммы Хассе.
- Пример. На диаграмме выше мы можем сказать, что 1 относится к 2,3,4,6,12 (упорядочено по делению, например (4, /)), но ни один элемент не связан с 1 (поскольку диаграмма Хассе направлена вверх. ).
- Наибольший элемент (если он существует) — это элемент, следующий за всеми остальными элементами.
- Наименьший элемент — это элемент, который предшествует всем остальным элементам.
Примечание. Наибольший и наименьший элементы на диаграмме Хассе — это только один.
В Примере-1
Максимальные элементы — 48 и 72, поскольку они следуют за всеми элементами.
Минимальные элементы — 3 и 4, поскольку они предшествуют всем элементам.
Наибольший элемент не существует, поскольку нет ни одного элемента, который предшествовал бы всем элементам.
Наименьшего элемента не существует, поскольку нет ни одного элемента, предшествующего всем элементам.
В Примере-2
Максимальный и наибольший элемент — 12, а минимальный и наименьший элемент — 1.
ПРИМЕЧАНИЕ: элемент может быть как максимальным, так и минимальным.
Диаграмма Хассе частично упорядоченного множества
Напомним, что ориентированным графом называется пара (V,A), состоящая из множества V и подмножества AÍV´V. Элементы из A называются стрелками, а из V – вершинами. Для стрелки (u,v) вершина u называется началом, а из v – концом.
Пусть (X,£) – частично упорядоченное множество. Множество ]x,y[ = называется открытым интервалом с концами x и y.
Определение 1.Диаграммой Хассе называется ориентированный граф (V,A) с V=X и A=<(u,v): u<v и ]u,v[ = Æ>.
Пример 1. На рис. 5.1 показана диаграмма Хассе множества P(<0,1,2>) подмножеств множества , упорядоченное отношением Í.
Рис. 5.1. Диаграмма Хассе множества подмножеств
Предполагаются, что ребра направлены сверху вниз.
Пример 2. Для целого неотрицательного числа n³0 будем обозначать через [n] множество , с отношением 0 < 1< ∙ ∙ ∙ < n. Его диаграммой Хассе будет ориентированный граф, приведенный на рис. 5.2.
Рис. 5.2. Диаграмма Хассе
Частично упорядоченные множества (X, £) и (Y, £) называются изоморфными, если существуют неубывающие отображения f: X®Y и g: Y®X такие, что f(g(y))=y и g(f(x))=x ("xÎX, "yÎY).
В этом случае f называется изоморфизмом, а g – обратным отображением для f.
Рассмотрим множество делителей (Dn, | ) натурального числа n³1, упорядоченное отношением делимости a | b Û a – делитель числа b (в этом случае говорят, что a – делит b).
Пример 3. Пусть p и q – различные простые числа, большие единицы. Диаграмма Хассе множества ( Dn, | ) с n=p 2 q показана на рисунке 5.3.
Рис. 5.3. Диаграмма Хассе множества делителей
В общем случае диаграмма Хассе частично упорядоченного множества (Dn ,| ) состоит из ребер m-мерного параллелепипеда, где m – число различных простых делителей числа n.
Теорема 1. Пусть n>0 – положительное натуральное число, n = — его разложение в произведение попарно не равных простых множителей pi>1. Тогда частично упорядоченное множество ( Dn , | ) будет изоморфно декартовому произведению [a1]´ [a2]´ ××× ´ [am] линейно упорядоченных множеств.
Доказательство. Каждый делитель числа n= будет равен числу , для некоторых 0£b1£a1, 0£b2£a2 , × × ×, 0£bm£am . Изоморфизм определяется как отображение, ставящее в соответствие числу элемент (b1, b2, × × ×, bm).
Функция Мебиуса
Пусть (X, £) – конечное частично упорядоченное множество. Рассмотрим последовательность функций P n : X´X® Z, определенных при n=0 и n=1 по формулам:
Определение 1. Функцией Мебиуса m : X´X®Z называется функция, определенная по формуле
Определение 2. Пусть X=< x1 , x2 , ××× , xn> – конечное частично упорядоченное множество, матрицей смежности называется матрица A, имеющая коэффициенты
Лемма 1. Пусть X=< x1 , x2 , ××× , xn> – конечное частично упорядоченное множество, A – матрица смежности. Тогда матрица M, коэффициенты которой равны значениям m(xi, xj), будет обратной к матрице A.
Доказательство. Пусть Id – единичная матрица. Положим Q=A-Id. Тогда A=Id+Q. Откуда
A -1 = Id — Q + Q 2 — Q 3 + ××× = .
Легко видеть, что коэффициенты матрицы Q k равны P k (xi,xj) , откуда , в силу . Что и требовалось доказать.
Пример 1. X=[n].
Отсюда получаем m(i,i)=1, m(i,i+1)=-1. Остальные значения функции Мебиуса равны 0.
Формула обращения
Теорема 1. Пусть (X, £) – конечное частично упорядоченное множество. Тогда для любых функций f, g : X® R равносильны следующие свойства
Доказательство. Пусть A – матрица смежности частично упорядоченного множества (X, £). Тогда выполнение равенства (1) равносильно соотношениям g(xi)=Sj aij f(xj). Поскольку это равносильно равенству g=Af, эквивалентного равенству f=A -1 g , то получаем, что (1) верно тогда и только тогда, когда верно (2).
Рассматривая частично упорядоченное множество с двойственным отношением порядка, получаем следующую теорему.
Теорема 2. Пусть (X, £) – конечное частично упорядоченное множество. Тогда для любых функций f , g : X® R равносильны следующие свойства
Теорема о произведении
Теорема 1. Пусть (X,£) и (Y,£) – конечные частично упорядоченные множества, mX: X´X® Z и mY: Y´Y® Z – их функции Мебиуса. Тогда, для любых x1, x2 Î X и
Доказательство. Введем дзета-функцию zX : X´X® Z, с помощью формулы
где da,b – символ Кронекера. Вычислим левую часть доказываемой формулы
Получили, что она равна правой части. Что и требовалось доказать.
Пример 1. Вычислим в частично упорядоченном множестве делителей числа n ≥ 1. По доказанной теореме, в случае разложения n = в произведение степеней различных простых чисел pi>1, будет иметь место соотношение . Поскольку
m(1,n) = 0, если существует i такой, что ai >1 ,
Упражнения
Диаграмма Хассе
1. Нарисовать диаграмму Хассе множества подмножеств из <0,1,2,3>, упорядоченное отношением включения.
2. Нарисовать диаграмму Хассе множества делителей числа 1000, упорядоченного отношением делимости.
3. Нарисовать диаграмму Хассе множества делителей числа 360, упорядоченного отношением делимости.
4. Нарисовать диаграмму Хассе множества P3 разбиений множества <1,2,3>.
5. Нарисовать диаграмму Хассе множества P4 разбиений множества <1,2,3,4>.
6. Нарисовать диаграмму Хассе произведения P3 ´[1].
Функция Мебиуса
1. Вычислить значения m(0, x) непосредственно из определения функции Мебиуса для следующих частично упорядоченных множеств, заданных с помощью диаграмм Хассе, приведенных на рис. 5.4.
Рис. 5.4. Примеры диаграмм Хассе
2. Вычислить значения функции Мебиуса для множества P(<1,2, ××× , n>), упорядоченного отношением Í .
3. Пусть a – произвольный элемент частично упорядоченного множества. Доказать, что . Найти значения функций Мебиуса для задачи 1 с помощью этой формулы.
РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ
Задача 1. Найти множество X, предполагая множества A, B и C известными. Предполагается, что все множества являются подмножествами некоторого универсума U. При каких условиях заданное уравнение обладает по крайней мере одним решением?
Пример решения задачи 1
Задача. Найти множество X, удовлетворяющее уравнению при заданных A, B и C известными. Все множества являются подмножествами некоторого универсума U. При каких условиях заданное уравнение обладает по крайней мере одним решением?
1 шаг. Уравнение равносильно следующему равенству
Пользуясь формулой , приходим к уравнению
С помощью правил де Моргана и соотношения преобразуем это уравнение к следующему
2 шаг. Обозначим операцию объединения Èзнаком сложения, а операцию пересечения Ç — знаком умножения. Получим уравнение
Преобразуем его с помощью закона дистрибутивности (P+Q)R=PR+QR. Приходим к уравнению
Равенства и XX = X , вместе с соотношениями , и приводят к уравнению
3 шаг. Полученное уравнение равносильно системе двух уравнений
Из первого уравнения получаем , а из второго . Эти соотношения приводят к соотношениям включения .
Ответ: , при условии .
Задача 2.Задано отношение R на множестве E = с помощью матрицы rij , где
Представить данное отношение с помощью ориентированного графа, вершинами которого являются элементы множества E. Вершины i и j соединяются стрелкой, если .
Выписать матрицы, соответствующие отношениям
Является ли это отношение R
6) отношением порядка,
7) отношением эквивалентности.
| 1) | 2) | 3) |
| 4) | 5) | 6) |
| 7) | 8) | 9) |
| 10) | 11) | 12) |
| 13) | 14) | 15) |
| 16) | 17) | 18) |
| 19) | 20) | 21) |
| 22) | 23) | 24) |
| 25) | 26) | 27) |
| 28) | 29) | 30) |
Пример решения задачи 2.
Задание. Выполнить действия, указанные в условии задачи 2, если отношение R на множестве E = задано с помощью матрицы
имеющей коэффициенты rij = 1 при (i,j)ÎR, и rij = 0 в других случаях.
Представим отношение с помощью ориентированного графа (рис.6.1), с множеством вершин E= . Вершины i и j соединяются стрелкой, если .
Рис. 6.1. Ориентированный граф, соответствующий отношению R
R — 1 = , RÇ R -1 = ,
Ответим на вопросы.
Рефлексивность выполняется, поскольку rii=1 влечет (i,i)ÎR, для всех iÎE.
Иррефлексивность не выполняется, ибо существуют iÎE, для которых (i,i)ÎR .
(например i=1).
Симметричность имеет место, ибо для всех i, j ÎE выполнено rij= rji .
Антисимметричность не выполняется, так как (1,3)ÎR и (3,1)ÎR, но 1¹3.
Транзитивность вытекает из R°R Í R.
Отношение не является отношением порядка, ибо оно не антисимметрично.
Отношение является отношением эквивалентности, поскольку оно рефлексивно, симметрично и транзитивно.
КОНТРОЛЬНАЯ РАБОТА
Задача 1. Найти количество подмножеств.
Варианты заданий
1. Сколько подмножеств множества <1, 2, . , 1000>не содержат чисел ни кратных 6 , ни кратных 4?
2. Сколько подмножеств множества <1, 2, . 1000>содержат по крайней мере одно число кратное 5 и ни одного – кратного 7 ?
3. Сколько существует подмножеств множества <1, 2, 3, . , 1000>имеющих по крайней мере одно число, кратное трем или четырем.
4. Сколько подмножеств множества <1, 2, . , 1000>не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 7 ?
5. Сколько подмножеств из <1,2,3, …, 300>состоят из чисел, делящихся на 4, и не содержат ни одного числа, делящегося на 3?
6. Сколько подмножеств множества <1,2,3, … , 1000>содержат по крайней мере одно число кратное 4, но ни одного кратного 7?
7. Сколько подмножеств множества <1, 2, . , 1000>не содержат чисел ни кратных 6 , ни кратных 15?
8. Сколько подмножеств множества <1, 2, . 1000>содержат по крайней мере одно число кратное 5 и ни одного – кратного 18 ?
9. Сколько существует подмножеств множества <1, 2, 3, . , 1000>имеющих по крайней мере одно число, кратное 15 или 21.
10. Сколько подмножеств множества <1, 2, . , 1000>не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 21 ?
11. Сколько подмножеств из <1,2,3, …, 300>состоят из чисел, делящихся на 6, и не содержат ни одного числа, делящегося на 7?
12. Сколько подмножеств множества <1, 2, . , 1000>не содержат чисел ни кратных 8 , ни кратных 6?
13. Сколько подмножеств множества <1, 2, . 1000>содержат по крайней мере одно число кратное 12 и ни одного – кратного 13 ?
14. Сколько существует подмножеств множества <1, 2, 3, . , 1000>имеющих по крайней мере одно число, кратное 6 или 11.
15. Сколько подмножеств множества <1, 2, . , 1000>не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 17 ?
16. Сколько подмножеств из <1,2,3, …, 300>состоят из чисел, делящихся на 7, и не содержат ни одного числа, делящегося на 3?
17. Сколько подмножеств множества <1, 2, . , 1000>не содержат чисел ни кратных 6 , ни кратных 9?
18. Сколько подмножеств множества <1, 2, . 1000>содержат по крайней мере одно число кратное 11 и ни одного – кратного 7 ?
19. Сколько существует подмножеств множества <1, 2, 3, . , 1000>имеющих по крайней мере одно число, кратное 12 или 13.
20. Сколько подмножеств множества <1, 2, . , 1000>не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 23 ?
21. Сколько подмножеств из <1,2,3, …, 1000>состоят из чисел, делящихся на 7, и не содержат ни одного числа, делящегося на 12?
22. Сколько подмножеств множества <1, 2, . , 1000>не содержат чисел ни кратных 6 , ни кратных 10?
23. Сколько подмножеств множества <1, 2, . 1000>содержат по крайней мере одно число кратное 12 и ни одного – кратного 7 ?
24. Сколько существует подмножеств множества <1, 2, 3, . , 1000>имеющих по крайней мере одно число, кратное 11 или четырем.
25. Сколько подмножеств множества <1, 2, . , 1000>не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 11 ?
26. Сколько подмножеств из <1,2,3, …, 300>состоят из чисел, делящихся на 2, и не содержат ни одного числа, делящегося на 3?
27. Сколько подмножеств множества <1, 2, . , 1000>не содержат чисел ни кратных 10 , ни кратных 4?
28. Сколько подмножеств множества <1, 2, . 1000>содержат по крайней мере одно число кратное 4 и ни одного – кратного 7 ?
29. Сколько существует подмножеств множества <1, 2, 3, . , 1000>имеющих по крайней мере одно число, кратное 3 или 8.
30. Сколько подмножеств множества <1, 2, . , 1000>не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 5 ?
Примеры решения задачи 1
Пример 1. Сколько подмножеств множества A= <1, 2, . 1000>не содержат ни чисел кратных 8, ни чисел кратных 12 ?
Решение. Для произвольного действительного числа x обозначим через [x] его целую часть. (Например [2.5]=2, [1/2]=0, [3]=3.) Пусть 12A – подмножество множества A состоящее из чисел кратных 12, A\12A Í A – подмножество чисел не кратных 12. Элементы, не кратные ни 12 ни 8, составляют множество (A\12A)\8A. Нам нужно найти число подмножеств этого множества. Поскольку число элементов этого множества равно
то количество его подмножеств равно
Пример 2. Сколько подмножеств множества A= <1, 2, . 1000>содержат по крайней мере одно число кратное 8 и ни одного – кратного 12 ?
Решение. Пусть 12A – подмножество множества A состоящее из чисел кратных 12, A\12A Í A – подмножество чисел не кратных 12. Элементы, не кратные ни 12 ни 8, составляют множество (A\12A)\8A.
Каждое подмножество из A\12A может быть одного из следующих типов:
1) оно не содержит ни одного элемента кратного 8,
2) оно содержит хотя бы один элемент, кратный 8.
Отсюда количество подмножеств множества A\12A равно сумме количеств подмножеств первого и второго типа. Подмножества первого типа – это в точности подмножества не содержащие ни элементов кратных 12, ни элементов, кратных 8. Нам нужно найти количество подмножеств второго типа.
Следовательно, искомое число равно
Пример 3. Сколько подмножеств множества A= <1, 2, . 1000>содержат по крайней мере одно число кратное 8 или 12 ?
Решение. Каждое подмножество множества A обладает одним из следующих взаимоисключающих свойств:
1) оно не содержит ни чисел кратных 8, ни чисел кратных 12,
2) оно содержит по крайней мере одно число, кратное 8 или 12.
Отсюда число подмножеств второго типа (которое как раз нам нужно найти) равно
Задача 2. Найти число разложений заданного числа в сумму слагаемых. Разложения, отличающиеся перестановкой слагаемых, считаются различными.
Варианты заданий
1. Слагаемые состоят из чисел 3 и 4, сумма равна 50.
2. Слагаемые состоят из чисел 3 и 5, сумма равна 50.
3. Слагаемые состоят из чисел 2 и 5, сумма равна 50.
4. Слагаемые состоят из чисел 3 и 4, сумма равна 52.
5. Слагаемые состоят из чисел 3 и 5, сумма равна 52.
6. Слагаемые состоят из чисел 2 и 5, сумма равна 52.
7. Слагаемые состоят из чисел 3 и 4, сумма равна 54.
8. Слагаемые состоят из чисел 3 и 5, сумма равна 54.
9. Слагаемые состоят из чисел 2 и 5, сумма равна 54.
10. Слагаемые состоят из чисел 3 и 4, сумма равна 51.
11. Слагаемые состоят из чисел 3 и 5, сумма равна 51.
12. Слагаемые состоят из чисел 2 и 5, сумма равна 51.
13. Слагаемые состоят из чисел 3 и 4, сумма равна 49.
14. Слагаемые состоят из чисел 3 и 5, сумма равна 49.
15. Слагаемые состоят из чисел 2 и 5, сумма равна 49.
16. Слагаемые состоят из чисел 3 и 4, сумма равна 55.
17. Слагаемые состоят из чисел 3 и 5, сумма равна 55.
18. Слагаемые состоят из чисел 2 и 5, сумма равна 55.
19. Слагаемые состоят из чисел 3 и 4, сумма равна 46.
20. Слагаемые состоят из чисел 3 и 5, сумма равна 46.
21. Слагаемые состоят из чисел 2 и 5, сумма равна 46.
22. Слагаемые состоят из чисел 3 и 4, сумма равна 48.
23. Слагаемые состоят из чисел 3 и 5, сумма равна 48.
24. Слагаемые состоят из чисел 2 и 5, сумма равна 48.
25. Слагаемые состоят из чисел 3 и 4, сумма равна 53.
26. Слагаемые состоят из чисел 3 и 5, сумма равна 53.
27. Слагаемые состоят из чисел 2 и 5, сумма равна 53.
28. Слагаемые состоят из чисел 3 и 4, сумма равна 47.
29. Слагаемые состоят из чисел 3 и 5, сумма равна 47.
30. Слагаемые состоят из чисел 2 и 5, сумма равна 47.
Пример решения задачи 2
Задание. Найти число разложений заданного числа в сумму слагаемых. Разложения, отличающиеся перестановкой слагаемых, считаются различными. Слагаемые состоят из чисел 3 и 5, сумма равна 40.
Решение. Найдем сначала число слагаемых, равных 3, и число слагаемых, равных 5, дающих в сумме число 40. С этой целью решим уравнение в целых числах
Первое решение x=0, y=8. Чтобы найти другие решения, будем прибавлять по 5 к числу x и вычитать по 3 из числа y. Получим решения;
Число последовательностей чисел, состоящих из x троек и y пятерок, равно . Отсюда находим числа разложений:
при x = 0, y=8 — ,
при x = 5, y=5 — ,
при x = 10, y=2 — .
Сумма этих чисел будет искомым числом разложений.
Задача 3. Перечисление функций. Для заданных m и n найти число:
Варианты заданий
| 1. m = 4 , n = 5 | 2. m = 6 , n = 8 | 3. m = 3 , n = 7 | 4. m = 2 , n = 10 | 5. m = 7 , n = 9 |
| 6. m = 5 , n = 6 | 7. m = 5 , n = 8 | 8. m = 2 , n = 7 | 9. m = 3 , n = 10 | 10. m = 8 , n = 9 |
| 11.m = 4, n = 11 | 12. m = 4 , n = 8 | 13. m = 2,n = 11 | 14. m = 4,n = 10 | 15. m = 6 , n = 9 |
| 16. m = 5, n = 9 | 17. m = 3 , n = 8 | 18. m = 4 , n = 6 | 19. m = 5, n = 10 | 20.m = 5, n = 11 |
| 21. m = 4, n = 9 | 22. m = 2 , n = 8 | 23. m = 3 , n = 6 | 24. m = 6, n = 10 | 25. m = 3, n = 9 |
| 26. m = 6, n = 7 | 27. m = 2, n = 6 | 28. m = 7, n = 10 | 29. m = 2, n = 9 | 30. m = 5, n = 7 |
Пример решения задачи 3
Задание. При m=6, n=11 найти число:
Решение. Обозначим Ln = <1,2,3, …, n>. Искомые числа вычисляются с помощью таблицы 7.1, в каждой клетке которой указано число функций Lm®Ln с заданными свойствами.
| функций Lm®Ln | Неубывающих функций Lm®Ln | |
| Всех | n m | |
| Инъективных | ||
| Сюръективных | n! S(m,n) | |
| Биективных | n!, если m=n, иначе 0 | 1, если m=n, иначе 0 |
Возрастающие функции – это в точности неубывающие инъективные функции.
Число S(11,6) вычислим с помощью значений чисел Стирлинга второго рода, приведенных в таблице 7.2.
Получим 6!S(11,6) =6!179487.
Задача 4. Найти производящую функцию последовательности.
Варианты заданий
| 1. 2 n n(n+1) 2. 2 n /n 3. 2 n n 2 4. 2 n /(n(n+1)) 5. 3 n sin(2n) 6. 3 n cos(2n) 7. 4 n n(n+1) 8. 4 n /n 9. 4 n n 2 10. 4 n /(n(n+1)) | 11. 6 n /n 12. 3 n sin(4n) 13. 3 n cos(4n) 14. 7 n n(n+1) 15. 7 n /n 16. 7 n n 2 17. 7 n /(n(n+1)) 18. sin(7n) 19. cos(7n) 20. 5 n n(n+1) | 21. 5 n /n 22. 6 n n 2 23. 5 n n 2 24. 5 n /(n(n+1)) 25. 5 n sin(5n) 26. 5 n cos(5n) 27. 3 n n(n+1) 28. 3 n /n 29. 3 n n 2 30. 3 n /(n(n+1)) |
Пример решения задачи 4
Задание. Найти производящую функцию последовательности an = 10 n /(n(n+1).
Упорядоченные множества
Множество вместе с заданным на нем отношением порядка называют упорядоченным множеством .
Отношение порядка будем, как правило, обозначать и т.п., похожими на с заданным на нем отношением порядка . Записывая , мы будем говорить, что элемент .
Каждому отношению порядка можно сопоставить следующие отношения.
1. Отношение, которое будем обозначать для любых тогда и только тогда, когда и . Записывая , мы будем говорить, что элемент . Из определения следует, что отношение , т.е. оно является отношением строгого порядка.
Двойственный порядок
2. Двойственный порядок . Это бинарное отношение на множестве , называемое также и отношением, двойственным к отношению порядка , обратное к отношению условие равносильно тому, что . Можно без труда доказать, что отношение , мы будем говорить, что элемент . Отношение строгого порядка, ассоциированное с , если и .
Отношение доминирования
3. Отношение доминирования. Для двух элементов , по определению, тогда и только тогда, когда и не существует такого элемента . Отношение называют отношением доминирования (или просто доминированием), ассоциированным с отношением порядка , то говорят, что элемент доминирует над элементом
Пример 1.15. а. Рассмотрим множество действительных чисел с естественным числовым порядком. Пусть найдется такое , но, конечно, неверно, что б. На множестве всех подмножеств трехэлементного множества , где в качестве отношения порядка взято отношение теоретико-множественного включения , подмножество доминирует над подмножествами и , но не доминирует над пустым множеством. В свою очередь, все множество доминирует над любым своим двухэлементным подмножеством, но не доминирует над одноэлементным и над пустым.
в. По отношению делимости на множестве натуральных чисел 15 доминирует над 3 и 5, но 20 не доминирует над 5, так как существует „промежуточный" элемент — 10, делитель 20, который делится на 5, но не равен ни 20, ни 5.
Упорядоченное подмножество
Рассмотрим упорядоченное множество и его произвольное непустое подмножество . Упорядоченное множество , где — ограничение отношения упорядоченным подмножеством упорядоченного множества .
Таким образом, можно переносить отношения порядка на непустые подмножества исходного упорядоченного множества. Как правило, вместо будем писать просто на подмножестве с индуцированным порядком", понимая под этим порядок .
Элементы упорядоченного множества называют сравнимыми по отношению порядка или . В противном случае элементы называются несравнимыми.
Упорядоченное множество, все элементы которого попарно сравнимы, называют линейно упорядоченным, а соответствующее отношение — отношением линейного порядка (или просто линейным порядком). Бели индуцированный порядок на подмножестве упорядоченного множества является линейным, то это линейно упорядоченное подмножество называют цепью. Любое подмножество попарно не сравнимых элементов данного упорядоченного множества называют антицепью.
Замечание 1.5. Обратим внимание на то, что термину "упорядоченное множество" (в смысле приведенного определения) отвечает термин "частично упорядоченное множество", а то, что мы называем линейно упорядоченным множеством, называется просто упорядоченным множеством. Терминология этого выпуска более принята в алгебраической литературе и литературе по дискретной математике. Употребление термина "частично упорядоченное множество" мотивировано желанием подчеркнуть, что в общем случае в упорядоченном множестве существуют не сравнимые элементы.
Пример 1.16. а. Отношение естественного числового порядка на множестве имеет место или неравенство , или неравенство .
б. Отношение делимости (см. пример 1.13.г) на множестве и отношение включения на (см. пример 1.13,д) не являются линейными порядками, за исключением случая, когда
Наибольший, наименьший и максимальный, минимальный элементы множества
Пусть — упорядоченное множество. Элемент называют наибольшим элементом множества .
Элемент , или наименьший и минимальный элементы упорядоченного множества, а именно: наименьший элемент упорядоченного множества для каждого .
Покажем, что наибольший (наименьший) элемент множества, если он существует, является единственным. Действительно, полагая, что — наибольшие элементы и , откуда ввиду антисимметричности любого отношения порядка следует, что Замечание 1.6. Поскольку на одном и том же множестве могут быть определены разные отношения порядка (например, на множестве натуральных чисел — естественный числовой порядок и отношение делимости), то, когда это необходимо, мы будем говорить о наибольших, наименьших (соответственно максимальных и минимальных) элементах по данному отношению порядка, уточняя тем самым, о каком отношении порядка идет речь.
Следующие примеры показывают, что максимальных (минимальных) элементов может быть сколько угодно. Но заметим, что если у множества есть наибольший (соответственно наименьший) элемент, то он является единственным максимальным (соответственно минимальным) элементом данного множества.
Пример 1.17. Рассмотрим множество точек плоскости с некоторой фиксированной прямоугольной декартовой системой координат. Координаты каждой точки плоскости задаются упорядоченной парой действительных чисел. Отношение порядка на множестве точек плоскости определим следующим образом: , если и только если (рис. 1.11, а). Точка с координатами является наименьшим элементом этого множества. Максимальными элементами являются все точки, лежащие на стороне
Верхняя и нижняя грань множества
Пусть — упорядоченное множество и называется верхней (соответственно нижней) гранью множества ).
Наименьший элемент множества всех верхних граней (соответственно наибольший элемент множества всех нижних граней) множества .
Множество всех верхних (нижних) граней множества (соответственно ).
В отличие от наибольшего и наименьшего элементов множества и Пример 1.18. а. Рассмотрим множество (рис. 1.11, б) с заданным в примере 1.17 отношением порядка. Точка б. На числовой прямой с "выколотой" точкой множество верхних граней есть , но точной верхней грани нет.
Вполне упорядоченные множества
Упорядоченное множество называют вполне упорядоченным , если его любое непустое подмножество имеет наименьший элемент.
Множество натуральных чисел с отношением естественного числового порядка вполне упорядоченное. Множество целых чисел не вполне упорядоченное, поскольку оно не имеет наименьшего элемента. Аналогично множества рациональных и действительных чисел не являются вполне упорядоченными.
Можно показать, что справедлив принцип двойственности для упорядоченных множеств. Пусть — произвольное упорядоченное множество. Тогда любое утверждение, доказанное для порядка 1) порядок и наоборот.
Например, если для некоторого мы доказали, что при заданном отношении порядка, то для двойственного порядка .
Говорят также и о взаимно двойственных определениях: если в любом определении, связанном с упорядоченным множеством, произвести взаимные замены согласно принципу двойственности, то получится новое определение, называемое двойственным к исходному. Так, определение наибольшего (максимального) элемента множества двойственно к определению наименьшего (минимального) элемента, и наоборот. Часто употребляют оборот речи: "двойственным образом…" (или "двойственно…"), понимая под этим переход к утверждению или определению, которое двойственно к исходному.
Способы наглядного представления упорядоченных множеств
Рассмотрим теперь некоторые способы наглядного представления упорядоченных множеств.
Конечное упорядоченное множество можно графически изобразить в виде так называемой диаграммы Хассе. На этой Диаграмме элементы множества изображаются кружочками. При этом если элемент
На рис. 1.13 приведена диаграмма Хассе для упорядоченного множества всех подмножеств трехэлементного множества по отношению включения (см. пример 1.13.д).
Последовательность элементов упорядоченного множества называют неубывающей, если для каждого справедливо неравенство .
Элемент а упорядоченного множества называют точной верхней гранью последовательности если он есть точная верхняя грань множества всех членов последовательности. Другими словами, точная верхняя грань последовательности есть точная верхняя грань области ее значений как функции натурального аргумента.
Точная нижняя грань последовательности
Двойственно определяется точная нижняя грань последовательности.
Упорядоченное множество называют индуктивным, если:
Например, множество всех подмножеств некоторого множества по отношению включения будет индуктивным. Наименьший элемент — пустое множество, а точной верхней гранью произвольной неубывающей последовательности множеств будет объединение всех членов этой последовательности (наименьшее по включению множество, содержащее в качестве подмножества любой член последовательности).
Определение 1.5. Пусть и — индуктивные упорядоченные множества. Отображение одного индуктивного упорядоченного множества в другое называют непрерывным, если для любой неубывающей последовательности элементов множества образ ее точной верхней грани равен точной верхней грани последовательности образов , т.е. справедливо равенство
Определение 1.6. Отображение упорядоченных множеств и называют монотонным, если для любых из следует .
Теорема 1.6. Всякое непрерывное отображение одного индуктивного упорядоченного множества в другое монотонно.
Пусть — непрерывное отображение индуктивного упорядоченного множества в индуктивное упорядоченное множество . Пусть и . Образуем последовательность , где , а . Эта последовательность неубывающая. Для нее . В силу непрерывности отображения
откуда следует, что .
Заметим, что функция , непрерывная в смысле определений математического анализа, не обязана быть монотонным отображением упорядоченных множеств числовой прямой с естественным числовым порядком на себя. Это отображение не является монотонным в смысле данного выше определения 1.6, поскольку, например, , однако неравенство не выполняется.
В общем случае монотонное в смысле определения 1.6 отображение не является непрерывным в смысле определения 1.5. Приведем пример, показывающий, что утверждение, обратное теореме 1.6, неверно.
Пример 1.19. Рассмотрим множество всех точек отрезка числовой прямой с порядком, индуцированным естественным числовым порядком. Это множество индуктивно: его наименьший элемент — 0, а любая неубывающая последовательность элементов ограничена сверху и по признаку Вейерштрасса имеет предел, который и будет ее точной верхней гранью. Любая кусочно-непрерывная (но не непрерывная!) и монотонная в смысле обычных определений из курса математического анализа функция, отображающая этот отрезок на любой отрезок с порядком, индуцированным естественным числовым порядком, дает пример монотонного в смысле определения 1.6, но не непрерывного в смысле определения 1.5 отображения между индуктивными частично упорядоченными множествами. Например, пусть функция имеет вид
Это отображение монотонно. Для последовательности , точная верхняя грань равна . Точная верхняя грань последовательности равна , a . Следовательно, отображение не является непрерывным в смысле определения 1.5.
Не следует путать отображение, монотонное в смысле определения 1.6, с монотонными функциями из курса математического анализа. Функция будет монотонной в смысле определения 1.6 тогда и только тогда, когда она является неубывающей.
Для приложений особенно важны непрерывные отображения индуктивного упорядоченного множества в себя.
Диаграммы Хассе
Диаграмма Хассе – это графическое изображение конечных частично или линейно упорядоченных множеств.
Пусть М – упорядоченное множество и элементы x, yÎM, причем x<y. Говорят, что y покрывает x, если не существует элемента zÎM такого, что x £ z £y.
На диаграмме Хассе элементы множества М изображаются в виде точек. Две точки x и y соединяются отрезком прямой в том и только том случае, когда y покрывает x. При этом точку x рисуют ниже точки y.
1) M = < 1, 2, 3, 4, 5, 6 >упорядочено отношением £. Тогда его диаграмма выглядит так, как показано на рисунке 8. Такая диаграмма характерна для линейно упорядоченных множеств.
3) M = < 1, 3, 5, 7, 15, 21, 35, 105 >упорядочено отношением P=< (x, y) : y делится на x >. Его диаграмма Хассе изображена на рисунке 10 и совпадает с предыдущей диаграммой с точностью до обозначения элементов. Между элементами этих множеств можно установить биективное отображение, сохраняющее имеющуюся упорядоченность элементов. Говорят, что такие множества изоморфны (подобны) между собой относительно заданных на них отношений порядка.