12. Формула включений и исключений

1. В группе 25 студентов, 15 занимаются лыжами, 12 – коньками, 8 и тем, и другим. Сколько студентов не занимается этими видами спорта?

2. (Обобщение) Проверьте, что если A и B – конечные множества, то Здесь - число элементов множества A.

3. В группе 15 студентов занимаются футболом, 13 – волейболом, 12 – баскетболом, 10 – футболом и волейболом, 11 – волейболом и баскетболом, 12 – футболом и баскетболом, 8 – всеми тремя видами спорта. Сколько студентов занимается хотя бы одним из этих видов спорта?

4. (Обобщение). Докажите, что для конечных множеств A,B,C справедлива формула

.

5. Как выглядит аналог формул из упражнений 1.1.2 и 1.1.4 для n множеств?

Ответ.

.

Указание. Один из способов доказательства: проверьте, что каждый элемент учтен в правой части в общей сложности один раз. Для этого предположите, что и воспользуйтесь формулой из задачи 1.1.2.

6. Сколько существует перестановок чисел 1,2,…,n, в которых

А) число 1 расположено на своем месте?

B) числа 1 и 2 расположены на своих местах?

C) числа 1,2,…,k расположены на своих местах?

D) хотя бы одно из чисел расположено на своем месте?

E) ни одно из чисел не расположено на своем месте (беспорядки)?

7. Пусть D_n – число беспорядков среди перестановок чисел 1,2,…,n. Найдите . Ответ несколько неожиданный: 1/e. Таким образом, при больших n ПОЛНЫЕ беспорядки составляют примерно треть всех перестановок. Одно из объяснений того, почему в мире так много беспорядка!

13. Комбинаторные величины при больших значениях параметров

1. Докажите, что при n≥2.

2. Докажите, что биномиальные коэффициенты возрастают при возрастании k от 0 до и убывают при возрастании k от до n.

3. Проверьте, что .

Эти результаты показывают, что комбинаторные величины растут очень быстро при больших значениях параметров. Формула Стирлинга утверждает, что , где . Поразительно, что в эту формулу входит число   отношение длины окружности на евклидовой плоскости к диаметру!

2. Множества и функции

1. Множества и простейшие операции над ними

С понятием множества каждый сталкивается постоянно. Для нас это первичное понятие, стало быть, дать множеству формальное определение нельзя, можно только пояснить, что имеется в виду. Множество состоит из элементов. Множества мы будем обозначать большими латинскими буквами, элементы – малыми. Здесь есть некоторая несогласованность, поскольку множество может быть и элементом некоторого множества. Множество задано, если про любой объект в мире можно сказать, является он элементом множества или нет. Первое отношение обозначается aA, второе – aA.

Таким образом, понятие множества имеет двойственную природу: с одной стороны, это нечто единое, с другой состоит из элементов. Важно отметить, что множество ПОЛНОСТЬЮ характеризуется набором своих элементов. Множества совпадают, если каждый элемент одного является элементом другого. Обозначение стандартное: A=B. Если всякий элемент множества A является элементом множества B, то A называется подмножеством B, обозначение: AB. Обычно множества изображаются в виде областей на плоскости.

Таким образом, равенство A=B равносильно тому, что одновременно AB и BA. Роль числа 0 в алгебре множеств (см. далее) играет пустое множество , т.е. множество, в котором нет элементов. Мы полагаем, что Здесь использован знак , который в математической логике называется квантором всеобщности (читается «для каждого»). Наряду с квантором всеобщности используется квантор существования (читается «существует»). Происхождение этих необычных знаков очень простое: это просто перевернутые первые буквы английских слов All (каждый) и Exist (существует).

Множество может задаваться перечислением его элементов. Обозначается это так: {a.b,c} – множество, состоящее из трех записанных букв. Подчеркнем, что элементы множества должны различаться и поэтому {a.b,a}={a.b}. Как уже отмечалось, множество определяется набором элементов, поэтому, например, {a.b,c}={c,a.b}. Следует различать одноэлементное множество и сам этот элемент. Например, про множество {2} нельзя сказать, что оно четное, а про его единственный элемент, число 2 – можно.

Если известно некоторое более обширное множество, то можно выделить подмножество элементов с некоторым свойством. Поясним это на примере. Используем стандартное обозначение множества натуральных чисел N. {aN: bN (a=2b)} это множество четных натуральных чисел.

Напомним определения простейших операций над множествами.

Объединением множеств A и B называется множество AB, , состоящее из элементов, каждый из которых принадлежит хотя бы одному из множеств A,B. Иначе говоря, AB={a: aA или aB}.

Пересечением множеств A и B называется множество AB, состоящее из элементов, каждый из которых принадлежит обоим множествам A,B, т.е. AB={a: aA и aB}. Иногда путают знаки объединения и пересечения. Запомнить их легко, если заметить, что знак объединения похож на букву U – первую букву английского слова Union – союз, объединение.

Объединение множеств также называется суммой множеств, а пересечение – произведением. Однако аналогия с числами полной не является, как будет видно далее.

Разностью множеств A и B называется множество A\B, образованное элементами, каждый из которых входит в A и не входит в B, т.е. A\B={a: aA, aB}.

Еще одна операция, которая достаточно широко используется  симметрическая разность AB=(A\B)(B\A)=(AB)\(AB). Докажите последнее равенство! Полезное свойство симметрической разности состоит в том, что AB= тогда и только тогда, когда A=B.

Часто вводится в рассмотрение универсальное множество или универсум U. Это в некотором смысле наша вселенная. Для нас не существуют элементы, не входящие в U, т.е. все рассматриваемые множества являются подмножествами U. В этом случае дополнением множества A называется множество Дополнение является аналогом логической операции отрицания.

Введенные операции на множествах обладают рядом алгебраических свойств. Приведем их.

1. (Коммутативность) AB=BA, AB=BA. Эти свойства очевидны.

2. (Ассоциативность) (AB)С=A(BС). Эти свойства также очевидны. Они позволяют опускать скобки, не опасаясь разночтений.

3. (Дистрибутивность объединения относительно пересечения) (AB)С=(AС)(BС). Это свойство не столь очевидно. Приведем формальное рассуждение. Пусть a(AB)С. По определению пересечения, одновременно aAB и aС. Возможны два случая: aA, aA. В первом случае aA и aС. Отсюда, aAС, т.е. a(AС)(BС). Во втором случае из соотношений aAB и aA следует, что aB. Отсюда аналогично a BС, т.е. a(A С)(BС). Тем самым ВСЕГДА a(AС) (BС). Вопрос. Доказано ли нужное свойство? Ответ. Нет. Пока лишь доказано, что (AB)С(AС)(BС). Для доказательства обратного включения рассмотрим элемент a(AС)(BС). Возможны два случая: a(AС) и a(AС). В первом случае одновременно aA (откуда aAB) и aС. Следовательно, в этом случае a(AB)С. Во втором случае аналогично предыдущему вытекает принадлежность aB (т.е. aAB), откуда a(AB)С. Теперь равенство доказано. Далее формальными рассуждениями мы будем пользоваться редко. Обычно будем пользоваться графической иллюстрацией.

Д

ля графического доказательства множества изобразим на плоскости. Весьма тонким является следующий вопрос. Множества могут иметь различную природу. Верно ли, что рассмотрения множеств на плоскости достаточно для доказательства общих утверждений о множествах? Можно доказать, что для анализа простейших свойств, которые мы сейчас рассматриваем, это так. Надо только множества изображать в общем виде, т.е. так (подобные рисунки иногда называют диаграммами Эйлера – это замечательное имя нам еще встретится!).

Затем на двух экземплярах такого рисунка следует отметить левую и правую части равенства и убедиться, что множества совпадают.

Свойства 1-3 имеют аналоги для чисел. Но в законе дистрибутивности для чисел знаки сложения и умножения нельзя поменять местами (убедитесь в этом!) А для множеств такой закон справедлив!

4. (Дистрибутивность объединения относительно пересечения) (AB)С=(AС)(BС). Докажите это свойство, используя графическое представление.

5. AA=AA=A. Эти свойства также не имеют числовых аналогов.

6. A=AU=A, A=, AU= U. Отсюда видно, что пустое множество в алгебре множеств выполняет функции числа 0, универсальное множество U числового аналога не имеет.

7. - правило двойного дополнения, в логике его аналог называется правилом двойного отрицания.

8. Законы де Моргана (аналогичны одноименным законам логики). . Эти формулы легче всего проверить на рисунках. Очень наглядно получается! Особенно, если множества расположить так.

9. . Эти законы являются фундаментальными в логике Аристотеля. Первый называется законом исключенного третьего (по латыни «терциум нон датур» – третьего не дано).

10. (Законы поглощения) A(AB)=A(AB)=A. Проверьте эти формулы с помощью рисунка! Здесь интересно то обстоятельство, что хотя в левых частях формально присутствует множество B, от него ничего не зависит.