Лекции по дискретной математике

ПО ДИСКРЕТНОЙ
МАТЕМАТИКЕ
Электронное издание
2021

УДК 519.1
ББК 22.176
Л43
Рукопись подготовлена в рамках грантового проекта НИУ ВШЭ 
по изданию авторских учебников
Рецензент: 
доктор физико-математических наук, профессор факультета математики 
Национального исследовательского университета «Высшая школа экономики» В. А. Тиморин
Авторы:
М. Вялый, В. Подольский, А. Рубцов, Д. Шварц, А. Шень
Л43
Лекции по дискретной математике / М. Н. Вялый, В. В. Подольский, А. А. Рубцов, Д. А. Шварц и др. ; 
Нац. исслед. ун-т «Высшая школа экономики». — Эл. изд. — 1 файл pdf : 496 с. — Москва : Изд. дом Высшей 
школы экономики, 2021. — (Учебники Высшей школы экономики). — Систем. требования: Adobe Reader 
XI либо Adobe Digital Editions 4.5 ; экран 10". — Текст : электронный.
ISBN 978-5-7598-2212-7
Учебник написан по материалам курса «Дискретная математика», который читается студентам младших курсов 
факультета компьютерных наук НИУ ВШЭ. Темы этого курса являются частью базовой математической культуры и 
необходимы будущим математикам, программистам и специалистам в области анализа данных, но не входят в традиционно сложившиеся курсы начального математического цикла (математический анализ, алгебра, линейная алгебра). В 
книге излагаются начальные сведения из перечислительной комбинаторики, теории графов, теории чисел, теории множеств, теории вероятностей, теории игр, теории вычислимости. Не претендуя на полноценный охват какой-либо из 
упомянутых теорий, учебник дает введение в эти области, с одной стороны, достаточное для студентов соответствующих 
специальностей, а с другой — позволяющее читать специализированную литературу.
Книга будет полезной студентам младших курсов, изучающим курс дискретной математики; преподавателям этой 
дисциплины; а также более широкому кругу любителей математики.
УДК 519.1 
ББК 22.176
Электронное издание на основе печатного издания: Лекции по дискретной математике / М. Н. Вялый, В. В. Подольский, А. А. Рубцов, Д. А. Шварц и др. ; Нац. исслед. ун-т «Высшая школа экономики». — Москва : Изд. дом Высшей 
школы экономики, 2021. — 496 с. — (Учебники Высшей школы экономики). — ISBN 978-5-7598-1782-6. — Текст : непосредственный.
В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.
ISBN 978-5-7598-2212-7
© 
Национальный исследовательский университет 
«Высшая школа экономики», 2021

СОДЕРЖАНИЕ
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
Часть I. Начальные примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
Лекция 1. Математическая индукция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
1.1. Задача о раскраске плоскости .........................................
15
1.2. Общая схема доказательств по индукции ..............................
18
1.3. Варианты рассуждений по индукции ...................................
21
1.3.1. С чего начинать? .................................................
21
1.3.2. Сведение к меньшим ............................................. 22
1.3.3. Переформулировка: принцип наименьшего числа ................
24
1.4. Как не надо ............................................................
24
1.5. Как догадаться, что доказывать? .......................................
27
1.6. Доказательства по индукции и без индукции ...........................
30
1.7. Индукция и рекурсия ................................................... 33
1.8. Доказательства неравенств по индукции ...............................
36
1.8.1. Неравенство Бернулли ...........................................
36
1.8.2. Среднее арифметическое и среднее геометрическое ............. 37
1.9. Пример из алгебры: системы однородных уравнений ................... 40
1.10. Коды Грея ............................................................. 43
1.11. Теорема Холла о представителях ...................................... 46
1.12. Задачи для самостоятельного решения ................................ 48
Лекция 2. Подсчёты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
2.1. Правило суммы ......................................................... 50
2.2. Рекуррентное соотношение: пример .................................... 54
2.3. Рекуррентное соотношение: число путей ...............................
57
2.4. Слова и правило произведения ......................................... 59
2.5. Выбор с ограничениями ................................................
63
2.6. Подсчёты с кратностью ................................................
65
2.7. Подмножества и числа сочетаний ......................................
68
2.8. Ещё о числах сочетаний ................................................ 70
2.8.1. Симметрия .......................................................
71
2.8.2. Сумма чисел в строке ............................................ 72
2.8.3. Знакочередующаяся сумма ......................................
72
2.8.4. Снова о включениях и исключениях .............................
74
2.8.5. Пути, подмножества, слова ......................................
75
2.8.6. Соседние числа в строке ........................................
77
2.8.7. Монеты и перегородки ...........................................
78
2.9. Бином Ньютона и производящие функции .............................. 80
2.10. Числа Каталана .......................................................
89
2.10.1. Правильные последовательности скобок ........................
89
2.10.2. Рекуррентная формула .........................................
91
2.10.3. Вычисление с помощью отражений .............................
93

Содержание
2.10.4. Вычисление с производящей функцией .........................
95
2.10.5. Вычисление с теорией вероятностей и поворотами .............. 97
2.10.6. Доказательство по индукции с дробными параметрами .........
98
2.10.7. Неассоциативные произведения, триангуляции и стековый калькулятор ......................................................... 99
2.11. Что дальше? .......................................................... 103
Лекция 3. Графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.1. Примеры ............................................................... 105
3.1.1. Граф авиарейсов ................................................. 105
3.1.2. Перестановка коней ............................................. 106
3.1.3. Эйлер и мосты в Кёнигсберге .................................... 108
3.1.4. Рукопожатия ..................................................... 109
3.1.5. Задачи и решения ............................................... 110
3.1.6. Разбор контрольной ............................................. 111
3.1.7. Знакомые и незнакомые ......................................... 113
3.2. Неориентированные графы ............................................. 116
3.2.1. Определение ..................................................... 116
3.2.2. Соседи. Степени вершин ......................................... 117
3.2.3. Связные компоненты ............................................. 120
3.2.4. Расстояния. Простые пути ....................................... 128
3.2.5. Деревья ......................................................... 131
3.2.6. Полное бинарное дерево ........................................ 134
3.3. Ориентированные графы ............................................... 135
3.3.1. Определение ..................................................... 135
3.3.2. Степени вершин ................................................. 136
3.3.3. Пути и достижимость ............................................ 137
3.3.4. Достижимость и разрезы ........................................ 138
3.3.5. Компоненты сильной связности и ациклические графы .......... 139
3.3.6. Графы преобразований .......................................... 142
3.4. Эйлеровы циклы ....................................................... 144
3.4.1. Определение ..................................................... 144
3.4.2. Критерий существования ........................................ 145
3.4.3. Последовательности де Брёйна .................................. 146
3.4.4. Гамильтоновы циклы ............................................. 147
3.5. Двудольные графы ..................................................... 148
3.5.1. Определение ..................................................... 148
3.5.2. Двудольные графы и раскраска в два цвета ..................... 149
3.5.3. Степени вершин ................................................. 150
3.5.4. Паросочетания ................................................... 151
3.6. Клики и независимые множества ....................................... 153
Лекция 4. Арифметика остатков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
4.1. Чётные и нечётные числа ............................................... 156
4.2. Деление на 3 и остатки ................................................ 157
4.3. Деление с остатком .................................................... 158
4.4. Сравнения по модулю .................................................. 161
4.5. Таблицы сложения и умножения по модулю N ......................... 163
4.6. Обратимые остатки по модулю N ...................................... 165
6

Содержание
4.7. Обратимые элементы и диофантовы уравнения ........................ 168
4.8. Алгоритм Евклида ...................................................... 169
4.9. Алгоритм Евклида и диофантовы уравнения ........................... 171
4.10. Однозначность разложения на множители ............................ 174
4.11. Китайская теорема об остатках ....................................... 176
4.12. Малая теорема Ферма ................................................ 178
4.13. Функция Эйлера и теорема Эйлера ................................... 180
4.14. Что дальше? .......................................................... 182
Часть II. Основные конструкции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
Лекция 5. Множества и логика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
5.1. Основные свойства множеств и операции с множествами .............. 187
5.2. Теоретико-множественные тождества .................................. 193
5.3. Логические переменные, логические связки ............................ 195
5.4. Наблюдения ............................................................ 199
5.5. Какие связки необходимы? ............................................. 202
5.5.1. Полнота дизъюнкции, конъюнкции и отрицания .................. 204
5.5.2. Полнота конъюнкции и отрицания ................................ 205
5.5.3. Алгебраическое доказательство полноты ........................ 206
5.6. Формула включений-исключений ....................................... 207
5.6.1. Первое доказательство .......................................... 208
5.6.2. Второе доказательство .......................................... 209
5.6.3. Формула для симметрической разности ......................... 209
Лекция 6. Функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
6.1. Пример ................................................................. 211
6.2. Функции и связанные с ними понятия .................................. 212
6.2.1. Терминология и обозначения ..................................... 212
6.2.2. Образ множества, полный прообраз ............................. 214
6.3. Декартово произведение множеств и графики функций ................ 218
6.4. Инъекции, сюръекции и биекции ....................................... 222
6.4.1. Определения ..................................................... 222
6.4.2. Биекции и сравнение множеств .................................. 224
6.5. Композиции функций ................................................... 227
6.5.1. Определение ..................................................... 227
6.5.2. Ассоциативность ................................................. 229
6.5.3. Обратная функция ............................................... 229
6.5.4. Степени композиций ............................................. 232
6.6. Подсчёты .............................................................. 233
6.7. Задачи для самостоятельного решения ................................. 235
Лекция 7. Отношения и их графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
7.1. Отношения в естественном языке ...................................... 238
7.2. Отношения с точки зрения математики ................................. 239
7.3. Свойства бинарных отношений ......................................... 241
7.4. Графы, матрицы и бинарные отношения ................................ 243
7.5. Отношения эквивалентности ............................................ 244
7.6. Композиция отношений ................................................. 247
7.7. Отношения: что дальше? ............................................... 250
7

Содержание
7.8. Задачи для самостоятельного решения ................................. 251
Лекция 8. Мощность множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
8.1. Равномощные множества ............................................... 253
8.1.1. Определение равномощности .................................... 253
8.1.2. Свойства равномощности ........................................ 254
8.1.3. Примеры равномощных множеств ................................ 255
8.2. Счётные множества .................................................... 257
8.2.1. Определение и простейшие примеры ............................ 257
8.2.2. Свойства счётных множеств ..................................... 259
8.3. Несчётные множества .................................................. 263
8.3.1. Интервал и отрезок равномощны ................................ 263
8.3.2. Добавление счётного множества ................................. 264
8.3.3. Числа и последовательности ..................................... 265
8.3.4. Отрезок и квадрат ............................................... 266
8.4. Диагональный аргумент Кантора и сравнение мощностей .............. 267
8.4.1. Несчётность отрезка ............................................. 267
8.4.2. Сравнение мощностей ........................................... 270
8.5. Что дальше? ........................................................... 274
Лекция 9. Упорядоченные множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
9.1. Отношения порядка .................................................... 276
9.1.1. Отношения строгого частичного порядка ......................... 276
9.1.2. Строгие и нестрогие порядки .................................... 277
9.2. Примеры ............................................................... 278
9.3. Операции над частично упорядоченными множествами ................. 280
9.4. Какие порядки считать «одинаковыми»? ............................... 282
9.5. Конечные линейные порядки ........................................... 284
9.6. Порядки и индукция .................................................... 284
9.7. Антицепи ............................................................... 286
Лекция 10. Вероятность: первые шаги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
10.1. Элементарная теория вероятностей: определения ..................... 290
10.2. Вероятность объединения событий .................................... 299
10.3. Вероятностный метод ................................................. 302
10.4. Условные вероятности ................................................ 304
10.5. Случайная величина, математическое ожидание ....................... 312
10.6. Частота орлов при подбрасывании монеты и биномиальные коэффициенты ................................................................ 321
10.7. Большие уклонения: неравенство Чернова ............................ 325
10.8. Подробности для любознательных .................................... 327
10.8.1. Ещё одна элементарная оценка отношения биномиальных коэффициентов ................................................... 327
10.8.2. Другое доказательство неравенства Чернова ................... 328
Лекция 11. Комбинаторные игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
11.1. Позиции ............................................................... 331
11.2. Стратегии ............................................................. 335
11.3. Разбор с конца ........................................................ 338
11.4. Симметричные стратегии .............................................. 343
8

Содержание
11.5. Ним ................................................................... 346
11.6. Сумма игр и функция Шпрага –
– Гранди ............................... 350
Часть III. Вычислимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
Лекция 12. Разрешающие деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
12.1. Задача об угадывании числа. Деление пополам. Мощностная нижняя
оценка ................................................................ 359
12.2. Формализация модели ................................................ 361
12.3. Угадывание числа, неадаптивный вариант задачи ..................... 362
12.4. Ограниченные модели разрешающих деревьев. Сортировка, взвешивания, булевы функции ............................................... 363
12.5. Рассуждение с противником .......................................... 367
Лекция 13. Булевы схемы и формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
13.1. Булевы схемы ......................................................... 372
13.2. Формулы .............................................................. 383
Лекция 14. Алгоритмическая неразрешимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
14.1. Игра FRACTRAN ...................................................... 389
14.2. Что утверждается? .................................................... 390
14.3. Отступление о процессорах ........................................... 391
14.4. Кодирование .......................................................... 392
14.5. Класс вычислимых функций ........................................... 393
14.6. Определение вычислимости? .......................................... 394
14.7. Компромисс ........................................................... 395
14.8. Композиция вычислимых функций ..................................... 396
14.9. Не все функции вычислимы ........................................... 397
14.10. Неразрешимость проблемы остановки ................................ 398
14.11. Самоприменимость ................................................... 400
14.12. Перечисление останавливающихся программ ......................... 401
14.13. Как доказать неразрешимость? ...................................... 402
14.14. Язык программирования для доказательства теоремы Конвея ........ 403
14.15. Сведение проблемы остановки: от программ к пасьянсам ............ 407
Лекция 15. Вычислимые функции, разрешимые и перечислимые множества . . 410
15.1. Примеры вычислимых функций ........................................ 413
15.2. Не все функции вычислимы (повторение) ............................. 417
15.3. Разрешимые множества ............................................... 419
15.4. Перечислимые множества ............................................. 420
15.5. Вычислимость и конечные объекты .................................... 427
15.6. Универсальная вычислимая функция .................................. 429
15.7. Главная универсальная функция ...................................... 434
15.8. Теорема Райса –
– Успенского .......................................... 439
15.9. Теорема о неподвижной точке ......................................... 443
15.10. Решения задач ....................................................... 446
Лекция 16. Машины Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
16.1. Определения .......................................................... 451
16.2. Тезис Чёрча –
– Тьюринга ............................................... 455
16.3. Машины Тьюринга и свойства вычислимых функций ................... 456
9

Содержание
16.4. Использование машин Тьюринга в доказательствах ................... 458
16.5. Композиция функций, вычислимых по Тьюрингу, и «уборка мусора» .. 459
16.6. Многоленточные машины Тьюринга ................................... 462
16.7. Моделирование многоленточной МТ на одноленточной ................ 465
16.8. Универсальная машина Тьюринга ..................................... 468
16.9. Универсальная трёхленточная машина для одноленточных машин ..... 470
16.10. Соответствие между абстрактной теорией алгоритмов и МТ .......... 473
16.11. Машины Тьюринга в доказательствах неразрешимости ............... 477
16.11.1. Задача достижимости на графе подстановок слов ............. 477
16.11.2. Неразрешимость задачи достижимости для графа подстановок слов ........................................................ 479
16.12. Решения задач ....................................................... 482
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493
Об авторах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
10