Дискретная математика

УДК 519.95 (075.8)
ББК 22.18
Р 33

Р е д ь к и н Н. П. Дискретная математика. — М.: ФИЗМАТЛИТ,
2009. — 264 с. — ISBN 978-5-9221-1093-8.

В учебнике представлен основной материал обязательного курса
«Дискретная математика», читающегося на механико-математическом
факультете МГУ с 1998 г. В сжатой форме он содержит для первоначального ознакомления ряд важных разделов дискретной математики:
комбинаторный анализ, графы и сети, важнейшие классы управляющих
систем, тесты, алгоритмы, кодирование, дискретные экстремальные
задачи. К каждой главе приведены задачи, самостоятельное решение
которых будет способствовать более глубокому усвоению теоретического материала и лучшей подготовке к экзамену.
Для студентов и аспирантов.
Рекомендовано УМО по классическому университетскому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям подготовки 010100 «Математика»,
010200 «Математика. Прикладная математика», 011000 «Механика.
Прикладная математика».

ISBN 978-5-9221-1093-8

c⃝ ФИЗМАТЛИТ, 2009

c⃝ Н. П. Редькин, 2009

ОГЛАВЛЕНИЕ

Предисловие . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
7

Г л а в а I.
Элементы комбинаторики . . . . . . . . . . . . . . . . . . . .
9
§ 1. Комбинаторные объекты и комбинаторные числа . . . . . . . .
9
§ 2. Формула включения-исключения. Производящие функции
и возвратные последовательности . . . . . . . . . . . .. . . . . . . . .
12

Г л а в а II.
Графы и сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
§ 1. Элементы графа. Подграфы. Способы задания графов . . . .
19
§ 2. Геометрическая реализация графов. Верхняя оценка числа
неизоморфных графов с m рёбрами . . . . . . . . . . . . . . . . . . .
22
§ 3. Деревья. Характеристические свойства деревьев . . . .. . . . .
23
§ 4. Верхняя оценка числа неизоморфных корневых деревьев с
m рёбрами . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .
26
§ 5. Теорема Кэли о числе деревьев с занумерованными вершинами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
§ 6. Двудольные графы. Паросочетания и трансверсали. Теорема Холла. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
29
§ 7. Сети. Потоки в сетях. Теорема Форда–Фалкерсона . . . . . .
32

Г л а в а III.
Булевы функции и формулы . . . . . . . . . . . . . . . .
40
§ 1. Булевы функции. Элементарные булевы функции. . . . . . . .
40
§ 2. Формулы и функции, реализуемые формулами. Простейшие
эквивалентности . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .
42
§ 3. Разложение булевых функций. Дизъюнктивные нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
§ 4. Полнота систем булевых функций. Представление булевых
функций полиномами Жегалкина . . . . . . . . . . . . . . . . . . . .
47
§ 5. Функции k-значной логики . . . . . . . . . . . . . . . . . . . . . . . .
49

Оглавление

Г л а в а IV.
Предикаты. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
§ 1. Высказывания,
предикаты,
кванторы.
Геометрический
смысл кванторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
§ 2. Модель, сигнатура модели, формулы в модели. Свободные
и связанные переменные . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
§ 3. Истинность формулы в модели, на множестве. Тождественно истинные формулы . . . . . . . . . . . . . . . . . .. . . . . . . . . . . .
56
§ 4. Эквивалентность формул. Правила преобразования формул
с кванторами. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .
57
§ 5. Приведённые формулы . . . . . . . . . . . . . . . .. . . . . . . . . . . .
60
§ 6. Нормальные формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63

Г л а в а V.
Схемы из функциональных элементов. Синтез и
оценки сложности схем. . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
§ 1. Схемы из функциональных элементов в базисе {&, ∨,− } . .
65
§ 2. Синтез схем с использованием совершенных д.н.ф. . . . .. . .
69
§ 3. Метод Шеннона . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .
70
§ 4. Асимптотически оптимальный метод синтеза схем (метод
Лупанова) . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
72
§ 5. Мощностной метод получения нижней оценки для сложности схем . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
75

Г л а в а VI.
Тесты. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
§ 1. Полные диагностические тесты для таблиц. Оценки длины
тестов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
§ 2. Тесты для схем. Построение минимальных тестов методом
Яблонского . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
§ 3. Верхние оценки длины единичных тестов для схем . . . . .. .
88
§ 4. Синтез легкотестируемых схем . . . . . . . . . . . .. . . . . . . . . .
89

Г л а в а VII.
Ограниченно-детерминированные
функции
и
реализация их автоматами . . . . . . . . . . . . . . . . . . . . . . . . .
92
§ 1. Детерминированные
и
ограниченно-детерминированные
функции . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
92
§ 2. Способы задания ограниченно-детерминированных функций. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . .
97
§ 3. Схемы автоматов из функциональных элементов и элементов задержки . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .
99

Оглавление
5

Г л а в а VIII.
Алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
§ 1. Алгоритмы. Машины Тьюринга. Задание машины системой
команд . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
§ 2. Композиции машин. Тезис Тьюринга . . . . . . . . . . . . . . . . . 105
§ 3. Проблема самоприменимости. Теорема о самоприменимости 106

Г л а в а IX.
Кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
§ 1. Алфавитное кодирование. Разделимые коды. Свойство префикса . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 109
§ 2. Неравенство Крафта–Макмиллана. . . . . . . . . . .. . . . . . . . . 112
§ 3. Коды с минимальной избыточностью. Оптимальное кодирование Хаффмена . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 115
§ 4. Самокорректирующиеся коды. Коды Хэмминга. . . . . . . . . . 120
§ 5. Геометрические свойства
самокорректирующихся кодов.
Оценки Хэмминга и Гильберта . . . . . . . . . . . . . . . . . . . . . . 123

Г л а в а X.
Дискретные экстремальные задачи . . . . . . . . . . . . 127
§ 1. Задача на покрытие. Точное решение задачи на покрытие
127
§ 2. Градиентный алгоритм поиска приближённого решения.
Оценка сложности градиентного покрытия. . . . . . . . .. . . . . . 129
§ 3. Задача о минимальном остовном дереве. . . . . . . . .. . . . . . . 133
§ 4. Поиск кратчайшего и надёжного путей в графе . . . . . . . . . 135
§ 5. Точное решение задачи на покрытие методом динамического программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
§ 6. Приближённое решение задачи об упаковке в контейнеры
141
§ 7. Классы P и NP. Полиномиальная сводимость задач . . . . . 143

Зaдачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
К главе I. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 151
К главе II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
К главе III. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 155
К главе IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
К главе V . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 160
К главе VI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
К главе VII . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 164
К главе VIII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
К главе IX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
К главе X . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 171

Оглавление

Ответы, указания, решения . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
К главе I. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 175
К главе II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
К главе III. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 186
К главе IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
К главе V . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 203
К главе VI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
К главе VII . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 224
К главе VIII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
К главе IX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
К главе X . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 254

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

Светлой памяти моего учителя
Олега Борисовича Лупанова
посвящается

Предисловие

Эта книга возникла на основе годового обязательного курса
лекций по дискретной математике, читающегося автором на механико-математическом факультете Московского государственного университета им. М. В. Ломоносова для студентов четвёртого курса отделения механики. Главная задача курса — обучение
характерным для дискретной математики методам решения основных задач и соответствующему мышлению. Необходимость
такого обучения диктуется научно-техническим прогрессом, поставившим перед математиками две крупные проблемы, которые
часто оказываются взаимосвязанными. Одна из них — изучение
сложных управляющих систем, разработка методов анализа и
синтеза таких систем. Другая проблема — необходимость решения ряда новых задач, главной спецификой которых является
дискретность. Такие задачи в настоящее время сплошь и рядом
возникают как в теории, так и на практике — в экономике,
технике, исследовании операций и т. п., а решение их даже с
использованием мощной вычислительной техники часто наталкивается на принципиальные, порой непреодолимые затруднения,
связанные с неприемлемо большими затратами машинного времени и памяти.
Вошедший в курс материал достаточно условно можно разбить на две части. Одну из них составляют основные понятия,
описания изучаемых объектов и доказательства ключевых фактов, теорем, ставших большей частью уже классическими. Сюда
относятся: элементы комбинаторики, графы и сети, булевы функции и формулы, предикаты, алгоритмы, кодирование, частично —
дискретные экстремальные задачи. Эта часть составляет основу
того математического аппарата, владение которым в настоящее

Предисловие

время представляется совершенно необходимым для выпускников математических факультетов.
В другой части представлены важнейшие классы управляющих систем — схемы из функциональных элементов и автоматы,
а также типовые задачи, связанные с синтезом и диагностикой
состояния этих систем, и основные способы решения таких задач; здесь часто используются понятия, математические модели
и теоремы из первой части. Приведены и типичные, наиболее
известные дискретные экстремальные задачи, точные и приближенные решения этих задач, примеры получения оценок качества
приближенных решений.
Успешное, пусть даже начальное изучение дискретной математики вряд ли возможно без приобретения навыков решения
подходящих задач, связанных с основными математическими моделями и теоремами. Для приобретения таких навыков освоение
теоретического материала должно сопровождаться практическими занятиями. Для занятий к каждой главе книги прилагаются
задачи различной степени трудности. Решение этих, а также,
возможно, и других подходящих задач необходимо для глубокого
и прочного усвоения теоретического материала.
Содержание данной книги, стиль изложения материала в значительной степени определяются научно-педагогической школой
кафедры дискретной математики механико-математического факультета МГУ им. М. В. Ломоносова, основателем и бессменным
руководителем которой на протяжении четверти века был выдающийся математик и педагог, академик РАН Олег Борисович
Лупанов.

Г л а в а I

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

§ 1. Комбинаторные объекты и комбинаторные числа

В комбинаторном анализе изучаются различные объекты, порождаемые элементами из конечного множества A = {a1, ... , an},
и числовые характеристики этих объектов. Часто рассматриваются, например, упорядоченные или неупорядоченные подмножества множества A, подмножества с повторяющимися элементами
из множества A и т. п. Вместе с классами таких комбинаторных объектов естественным образом вводятся и так называемые
комбинаторные числа, задающие число объектов в том или ином
классе и зависящие от некоторых параметров, например, от мощностей исходного множества A и рассматриваемых подмножеств
множества A.
Размещения элементов. Пусть A = {a1, ... , an}. Размещением элементов из A по k (или размещением из n элементов
по k) называется упорядоченное подмножество из k элементов
множества A.
Для A = {a1, a2, a3, a4} размещениями из A по 3 будут, например, {a1, a3, a4}, {a3, a4, a1}, {a2, a3, a4}.
Обозначим число размещений из n элементов по k через (n)k.
При построении конкретного размещения первым элементом в
нём можно взять любой из n элементов множества A, вторым
элементом — любой из n − 1 оставшихся в A элементов и т. д.
Поэтому

(n)k = n(n − 1) ... (n − k + 1) при 1 ⩽ k ⩽ n.

При k > n не существует размещений из n по k, следовательно,
(n)k = 0 при k > n; при k = 0 полагаем (0)0 = (n)0 = 1. Нетрудно
заметить, что для чисел (n)k выполняются тождества:

(n)k =n(n − 1)k−1,
(n)k =(n)k−1 · (n − k + 1).

Гл. I. Элементы комбинаторики

Перестановки элементов. Перестановками элементов множества A = {a1, ... , an} (или перестановками из n элементов)
называются всевозможные упорядоченные множества из n элементов a1, ... , an.
Для A = {a1, a2, a3} перестановками будут, например, {a1, a3,
a2}, {a2, a1, a3}, {a2, a3, a1}.
Перестановки из n элементов — частный случай размещений
из n элементов по n. Поэтому

(n)n = n(n − 1) ... 2 · 1 = n!

Как обычно, полагаем 0! = 1.
Сочетания элементов. Сочетанием элементов из A = {a1, ...
... , an} по k (или сочетанием из n элементов по k) называется
неупорядоченное подмножество из k элементов множества A.
Для A = {a1, a2, a3} всевозможными сочетаниями по 2 элемента будут {a1, a2}, {a1, a3}, {a2, a3}.
В сочетании, в отличие от размещения, порядок следования
элементов не учитывается. Поэтому из одного сочетания (из n
элементов по k) получается k! размещений. Отсюда для числа
n
k
сочетаний из n элементов по k получается формула
n
k

= (n)k

k!
= n(n − 1) ... (n − k + 1)

k!
=
n!

k!(n − k)!

(0 ⩽ k ⩽ n; вместо
n
k
часто используется также обозначение Ck
n). Из последней формулы следует
0
0

=
n
0

=
n
n

= 1 и
n
k

=
n
n − k

.

Для случая k > n полагаем
n
k
= 0, поскольку при k > n не существует сочетаний из n элементов по k.
Числа
n
k
фигурируют в функциональном тождестве, называемом формулой для бинома Ньютона:

(1 + x)n =
n
0

+
n
1

x + ... +
n
k

xk + ... +
n
n

xn.
(1)

В правой части данного тождества коэффициент при xk есть количество способов, которыми можно выбрать из k скобок (1 + x)
переменную x, а из остальных скобок 1, что даёт ровно
n
k
слагаемых.

§ 1. Комбинаторные объекты и комбинаторные числа
11

Полагая в (1) x = 1, получим тождество
n
0

+
n
1

+ ... +
n
k

+ ... +
n
n

= 2n;
(2)

при x = −1 получим
n
0

−
n
1

+ ... + (−1)n
n
n

= 0.
(3)

Из соотношений (2) и (3) следуют тождества
n
0

+
n
2

+ ... +
n
n

=
n
1

+
n
3

+ ... +
n
n − 1

= 2n−1

при чётном n и
n
0

+
n
2

+ ... +
n
n − 1

=
n
1

+
n
3

+ ... +
n
n

= 2n−1

при нечётном n.
Сочетания с повторениями элементов. Сочетанием с повторениями элементов из A = {a1, ... , an} по k (или сочетанием
с повторениями из n элементов по k) называется неупорядоченный набор из k элементов множества A, в котором элементы
могут повторяться.
Для A = {a1, a2, a3} всевозможными сочетаниями с повторениями по 2 элемента будут (a1, a1), (a1, a2), (a1, a3), (a2, a2),
(a2, a3), (a3, a3).
Обозначим через Hk
n число сочетаний с повторениями из n
элементов по k; найдём это число.
Пусть a — произвольное сочетание с повторениями элементов
из A = {a1, ... , an} по k. Этому сочетанию поставим в соответствие набор α(a) длины n + k − 1 из n − 1 нулей и k единиц.
В наборе α(a) число единиц, находящихся между (i − 1)-м и i-м
нулями (i = 2, ... , n − 1), равно числу элементов ai, входящих
в сочетание a, а число единиц, стоящих перед первым нулём (после последнего нуля), равно числу элементов a1 (соответственно
элементов an), входящих в сочетание a. Указанное соответствие
между сочетаниями a и наборами α(a) взаимно однозначно.
Различных наборов длины n + k − 1, содержащих n − 1 нулей
и k единиц, имеется ровно
n+k−1
k
штук, поскольку каждому
такому набору можно взаимно однозначно сопоставить сочетание
из n + k − 1 элементов по k. В итоге получаем

Hk
n =
n + k − 1
k

.