Просолупов Е.В. Конспект курса: Основы дискретной математики
Подождите немного. Документ загружается.
Конспект курса: Основы дискретной математики
Е.В. Просолупов.
25th May 2008
Содержание
1 Элементы теории множеств. Комбинаторика. 4
1.1 Введение. Примеры задач. . . . . . . . . . . . . . . . . . . 4
1.1.1 Знакомство. . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Задача о расположении конвертов . . . . . . . . . . 4
1.1.3 Задача о Ханойской башне . . . . . . . . . . . . . . 9
1.2 Основы теории множеств . . . . . . . . . . . . . . . . . . . 13
1.2.1 Базовые обозначения . . . . . . . . . . . . . . . . . . 13
1.2.2 Правило суммы и правило произведения . . . . . . 14
1.2.3 Понятие множества . . . . . . . . . . . . . . . . . . 15
1.2.4 Парадокс Рассела . . . . . . . . . . . . . . . . . . . . 16
1.2.5 Подмножества . . . . . . . . . . . . . . . . . . . . . 17
1.2.6 Операции над множествами . . . . . . . . . . . . . . 17
1.2.7 Диаграммы Эйлера-Венна . . . . . . . . . . . . . . . 20
1.2.8 Прямое произведение множеств . . . . . . . . . . . . 20
1.3 Бинарные отношения и функции . . . . . . . . . . . . . . . 22
1.3.1 Бинарные отношения . . . . . . . . . . . . . . . . . 22
1.3.2 Функции . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.3.3 Отношение эквивалентности . . . . . . . . . . . . . 27
1.3.4 Отношение порядка . . . . . . . . . . . . . . . . . . 29
1.3.5 Лексикографический порядок . . . . . . . . . . . . . 33
1.4 Перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.4.1 Понятие перестановки . . . . . . . . . . . . . . . . . 36
1.4.2 Группа перестановок . . . . . . . . . . . . . . . . . . 37
1
1.4.3 Циклы перестановки . . . . . . . . . . . . . . . . . . 38
1.4.4 Тип перестановки . . . . . . . . . . . . . . . . . . . . 43
1.5 Выборки с повторениями и без повторений . . . . . . . . . 46
1.5.1 Размещения и сочетания . . . . . . . . . . . . . . . . 46
1.5.2 Треугольник Паскаля . . . . . . . . . . . . . . . . . 49
1.5.3 Связь сочетаний и (0,1)-векторов . . . . . . . . . . . 51
1.5.4 Перебор сочетаний . . . . . . . . . . . . . . . . . . . 52
1.5.5 Бином Ньютона . . . . . . . . . . . . . . . . . . . . . 53
1.5.6 Мультимножества . . . . . . . . . . . . . . . . . . . 58
1.5.7 Связь мультимножеств и (0,1)-векторов . . . . . . . 61
1.5.8 Полином Ньютона . . . . . . . . . . . . . . . . . . . 62
1.5.9 Разбиения множеств. . . . . . . . . . . . . . . . . . . 63
1.5.10 Приложение: программа перебора сочетаний . . . . 66
1.6 Разложения и разбиения натуральных чисел . . . . . . . . 69
1.6.1 Разложения натуральных чисел . . . . . . . . . . . 69
1.6.2 Разбиения натуральных чисел . . . . . . . . . . . . 71
1.7 Принцип включения-исключения . . . . . . . . . . . . . . . 75
1.7.1 Принцип включения-исключения . . . . . . . . . . . 75
1.7.2 Задача о беспорядках . . . . . . . . . . . . . . . . . 76
1.7.3 Мощность объединения множеств . . . . . . . . . . 78
1.7.4 Число целочисленных решений системы неравенств 79
2 Математическая логика 86
2.1 Булева алгебра. Функции алгебры логики. . . . . . . . . . 86
2.1.1 Булевы функции . . . . . . . . . . . . . . . . . . . . 86
2.1.2 Формулы . . . . . . . . . . . . . . . . . . . . . . . . 88
2.1.3 Основные тождества . . . . . . . . . . . . . . . . . . 93
2.1.4 Разложение функции по переменным . . . . . . . . 95
2.1.5 Дизъюнктивная и конъюнктивная нормальные формы 97
2.1.6 Полином Жегалкина . . . . . . . . . . . . . . . . . . 101
2.1.7 Полнота системы функций . . . . . . . . . . . . . . 106
2.1.8 Функции, сохраняющие ноль . . . . . . . . . . . . . 111
2.1.9 Функции, сохраняющие единицу . . . . . . . . . . . 111
2.1.10 Двойственность . . . . . . . . . . . . . . . . . . . . . 112
2.1.11 Монотонность . . . . . . . . . . . . . . . . . . . . . . 117
2
2.1.12 Линейность . . . . . . . . . . . . . . . . . . . . . . . 120
2.1.13 Критерий полноты системы функций . . . . . . . . 124
2.2 Исчисление высказываний . . . . . . . . . . . . . . . . . . . 126
2.2.1 Пример задачи логики высказываний . . . . . . . . 126
2.2.2 Формальные теории . . . . . . . . . . . . . . . . . . 128
2.2.3 Формальная теория исчисление высказываний . . . 130
2.2.4 Теоремы исчисления высказываний . . . . . . . . . 132
2.2.5 Теорема о полноте исчисления высказываний . . . . 135
2.2.6 Независимость аксиом исчисления высказываний . 140
2.3 Исчисление предикатов . . . . . . . . . . . . . . . . . . . . 144
2.3.1 Пример задачи логики предикатов . . . . . . . . . . 144
2.3.2 Формальная теория исчисление предикатов . . . . . 147
2.3.3 Интерпретация . . . . . . . . . . . . . . . . . . . . . 149
3 Теория алгоритмов 155
3.1 Машины Тьюринга . . . . . . . . . . . . . . . . . . . . . . . 155
3.1.1 Понятие алгоритма . . . . . . . . . . . . . . . . . . . 155
3.1.2 Машина Тьюринга . . . . . . . . . . . . . . . . . . . 155
3.1.3 Способы записи машины Тьюиринга . . . . . . . . . 158
3.1.4 Стандартные конфигурации . . . . . . . . . . . . . . 160
3.1.5 Вычислимые функции . . . . . . . . . . . . . . . . . 161
3.1.6 Алгоритмически неразрешимые задачи . . . . . . . 165
3.2 Теория NP -полных задач . . . . . . . . . . . . . . . . . . . 171
3.2.1 Сложность алгоритма . . . . . . . . . . . . . . . . . 171
3.2.2 Полиномиальная сводимость . . . . . . . . . . . . . 175
3.2.3 Классы задач в форме распознавания свойств . . . 180
3.2.4 Отношение между классами P и NP . . . . . . . . 184
3.2.5 NP -полные задачи . . . . . . . . . . . . . . . . . . . 185
Литература 188
3
1 Элементы теории множеств. Комбинаторика.
1.1 Введение. Примеры задач.
На первом занятии познакомимся с примерами задач, которые входят в
рассмотрение дискретной математики.
1.1.1 Знакомство.
Знакомство.
Списки групп студентов.
Обмен адресами (prosolupov@inbox.ru).
Обмен номерами телефонов.
Список литературы.
Сайт (http://prosolupov.newmail.ru/)
1.1.2 Задача о расположении конвертов
Рассмотрим задачу, для решения которой не потребуется знания
специальной теории. Многие достаточно подготовленные читатели могут
еще в процессе рассуждений догадаться, каков ответ на задачу, но мы
все-таки пройдем все стадии, чтобы лучше понять сам процесс решения.
Задача 1.1.1 . Имеется n квадратных конвертов разного размера
(нет двух одинаковых конвертов). Все конверты находятся в
ящике, причем одни конверты можно вкладывать в другие. Сколько
существует способов размещения конвертов в ящике без учета их
пространственного положения?
Пример 1.1.1 . Пусть имеется три конверта размера l
1
, l
2
и l
3
,
причем 0 < l
3
< l
2
< l
1
. На рисунке 1 изображены все возможные
расположения трех конвертов. Всего их оказывается шесть.
Русский язык, как и любой другой разговорный язык, допускает
различные понимания одной и той же последовательности слов
(символов). Этим он плох для формулировки задачи. Необходимо
поставить задачу формально (строго).
4
1
2 3
4
5
6
Рисунок 1: Все возможные относительные расположения трех конвертов в ящике
Пусть 0 — ящик. Упорядочим конверты по убыванию размера и
сопоставим 1 самому большому конверту, 2 — следующему и так далее.
Самый маленький конверт получит номер n. Тогда любому размещению
конвертов в ящике можно сопоставить пару (n, A), где n ∈ N — число
конвертов, а A некоторое множество пар (i, j), i ∈ N
0
= N ∪ {0},
j ∈ N, i, j ≤ n. Если (i, j) ∈ A, то конверт j при нашем размещении
непосредственно вложен в конверт i.
Пример 1.1.2 . Например размещению 2 на рисунке 1 соответствует
множество A = {(0, 1), (1, 2), (2, 3)}, а размещению 6 того же рисунка
— множество A = {(0, 1), (0, 2), (2, 3)}.
Не любому множеству пар A соответствует некоторое размещение
конвертов. Введем дополнительные ограничения на A:
1) i ∈ N, i ≤ n ⇒ |{(k, i) : (k, i) ∈ A}| = 1 — любой конверт
непосредственно вложен ровно в один другой конверт или ящик.
2) (i, j) ∈ A ⇒ i < j — меньший конверт вкладывается в больший.
Задача 1.1.2 . Найти функцию натурального аргумента n ∈ N
f(n) = |{A : A ⊆ {0, 1, ..., n − 1} × {1, 2, ..., n},
5
A удовлетворяет условиям 1) и 2)}|
Итак, мы сформулировали строгую постановку задачи и знаем, что
нам нужно найти. Тем не менее ответить на поставленный вопрос сразу
не так просто. Даже если мы угадаем ответ сейчас, его доказательство
может оказаться достаточно сложным для понимания. Чтобы избежать
необходимости непосредственно выяснять количество возможных пар
(n, A), сопоставим каждой такой паре графическое изображение -
возрастающее дерево.
Пример 1.1.3 . Пусть у нас есть некоторое расположение (n, A) =
(5, {(0, 1), (0, 2), (0, 4), (1, 3), (1, 5)}). Сопоставим ему возрастающее
дерево (рис. 2): {0, 1, 2, 3, 4, 5} — множество вершин (узлов), 0 —
корень, стрелки — ориентированные ребра (дуги), 1 — внутренний узел,
2, 3, 4, 5 — листья. Узел 0 называют родительским (или отцом) для
узлов 1, 2 и 4, которые называют детьми (сыновьями) узла 0. Узел 1
в свою очередь является отцом узлов 3 и 5.
0
4
2
1
3
5
Рисунок 2: Пример возрастающего дерева
Особенности возрастающих деревьев: 1) В любой узел из корня можно
попасть двигаясь по стрелкам и притом единственным образом; 2) при
движении от корня по стрелкам номера узлов только возрастают.
6
Формально возрастающее дерево можно определить следующим
образом:
Определение 1.1.1 . 1) Пусть x — некоторый узел, помеченный
числом n
x
. Тогда можно говорить, что x возрастающее дерево,
состоящее из одного узла, и узел x является корнем этого дерева.
2) Пусть x — некоторый узел, помеченный числом n
x
, и T
1
, T
2
,..., T
k
— возрастающие деревья с корнями соответственно x
1
, x
2
, ..., x
k
; узел
x
i
помечен числом n
x
i
, i = 1, k. Если n
x
< n
x
i
для любого i = 1, k,
то можно построить возрастающее дерево x(T
1
, T
2
, ..., T
k
) с корнем x и
поддеревьями T
1
, T
2
,..., T
k
.
Пример 1.1.4 . Возрастающее дерево с рисунка 2 можно записать
0(4, 2, 1(5, 3)).
Нетрудно видеть, что любому возрастающему дереву T с узлами
{0, 1, ..., n} соответствует некоторое размещение n конвертов (n, A), где
A состоит из пар (i, j) соединенных в дереве T стрелкой из i в j. Верно
и обратное: по размещению конвертов можно построить возрастающее
дерево, как это сделано в примере 1.1.3.
Таким образом, наша задача эквивалентна следующей:
Задача 1.1.3 . Найти число возрастающих деревьев с n вершинами.
Для определенности будем считать, что все дети одного родительского
узла расположены в графическом изображении возрастающего дерева
по убыванию слева направо. Так на рисунке 2 вершины 4, 2 и 1
могли бы быть изображены в другом порядке, структура дерева бы не
изменилась. Чтобы не путать разные изображения одного дерева, вводим
это ограничение.
Рассмотрим еще один способ описания возрастающего дерева —
последовательность из n + 1 различных элементов из множества
{0, 1, ..., n}.
Определение 1.1.2 . Назовем перестановкой чисел {1, 2, ..., n}
произвольную упорядоченную последовательность π из n различных
7
чисел 1, 2, ..., n:
π ∈ {(k
1
, k
2
, ..., k
n
) | k
i
∈ {1, 2, ..., n}, i = 1, n; k
i
6= k
j
, при i 6= j}
Рассмотрим слово τ начинающееся с 0 и продолжающееся некоторой
перестановкой чисел {1, 2, ..., n}: τ = (0, k
1
, k
2
, ..., k
n
).
Пример 1.1.5 . Пусть τ = (0, 4, 2, 1, 5, 3). Строим по τ возрастающее
дерево T . Каждое число в τ — узел дерева T ; 0 — корень.
Пусть i 6= 0 — элемент τ . Пусть j ближайший к i слева элемент
τ, такой что j < i. Тогда j — отец узла i. Нетрудно убедиться, что
полученное таким образом по τ дерево T совпадает с деревом на рисунке
2.
Итак, чтобы получить по некоторому возрастающему дереву T
соответствующее слово τ, нужно каждому листу i сопоставить запись
τ
i
= i, а каждому родительскому узлу j с детьми i
1
, i
2
, ..., i
k
, i
1
≥ i
2
≥
... ≥ i
k
, сопоставить запись:
τ
j
= j, τ
i
1
, τ
i
2
, ..., τ
i
k
,
где τ
i
l
— запись для узла i
l
.
Нетрудно видеть, что, поскольку номер любого сына больше номера
родительского узла, а номера узлов i
1
, i
2
, ..., i
k
, упорядочены по
убыванию, то просматривая список влево от любого i
l
мы правильно
определим его родителя — j. Тогда τ = τ
0
и есть искомое представление
дерева T .
Пример 1.1.6 . Построим указанным способом слово τ для
возрастающего дерева на рисунке 2. Считаем записи для листьев:
τ
3
= 3, τ
5
= 5, τ
2
= 2, τ
4
= 4. Теперь можно получить записи для
родительских узлов: τ
1
= 1, τ
5
, τ
3
= 1, 5, 3, τ
0
= 0, τ
4
, τ
2
, τ
1
= 0, 4, 2, 1, 5, 3.
Мы получили, что τ = (0, 4, 2, 1, 5, 3), что соответствует слову τ из
примера 1.1.5.
Таким образом, по дереву T мы однозначно строим слово τ,
состоящее из нуля с последующей перестоновкой чисел {1, 2, ..., n}. С
другой стороны по слову τ однозначно восстанавливается дерево T
8
способом, описанным в примере 1.1.5. Этим мы показали, что каждому
возрастающему дереву T взаимнооднозначно соответствует некоторая
перестановка чисел {1, 2, ..., n}, а наша задача сводится к следующей:
Задача 1.1.4 . Найти число переставновок чисел {1, 2, ..., n}.
Последнее число равно n!, что нетрудно доказать, например, по
индукции.
Итак, на примере задачи о расположении конвертов мы разобрали
следующие стадии решения задачи:
1) формулировка задачи из предметной области;
2) формализация условий задачи и построение математической модели;
3) последовательное сведение исходной задачи к вспомогательным
задачам;
4) получение ответа путем решения вспомогательной задачи.
1.1.3 Задача о Ханойской башне
Рекомендуемая литература: [2]
Рассмотрим еще одну интересную задачу и отметим на ее примере
некоторые другие этапы решения.
1
2
3
Рисунок 3: Ханойская башня
Известная головоломка ханойская башня изображена на рисунке 3.
Головоломка состоит из трех колышков и некоторого числа дисков
9
разного диаметра. Каждый диск имеет в середине отверстие для
надевания на колышки.
В исходный момент все диски нанизаны на один из колышков в порядке
уменьшения размера. Диски можно перемещать с колышка на колышек
при соблюдении двух условий: за один раз можно перенести только один
диск и больший диск нельзя помещать на меньший. Задача состоит в
том, чтобы, при соблюдении правил перемещения, перенести все диски с
исходного на какой-нибудь другой колышек.
Довольно быстро можно убедиться, что задача разрешима. Поставим
вопрос, какой способ решения головоломки является оптимальным.
Задача 1.1.5 . Каково наименьшее число перекладываний T
n
, которое
необходимо совершить, чтобы переместить в рамках задачи о
ханойской башне пирамиду из n дисков с одного колышка на другой.
Рассмотрим крайние случаи. Довольно часто ответ на задачу легко
находится в частных случаях, при малых значениях аргумента. Такие,
казалось бы, очевидные случаи могут помочь лучше понять общие
закономерности. Так, совершенно очевидно, что T
1
= 1, и не сложно
убедиться, что T
2
= 3. Так же можно положить T
0
= 0, поскольку для
перемещения пирамиды из 0 дисков не требуются перекладывания.
Теперь попытаемся понять, как же переместить пирамиду в общем
случае. Если предположить, что изначально диски находятся на колышке
с номером 1, для двух дисков нам требуется переложить меньший диск
на колышек 2, затем больший на колышек 3 и наконец меньший диск с
колышка 2 на колышек 3.
Для трех дисков задача усложняется, но идея остается той же. Мы
можем переложить, как мы уже умеем, два диска на колышек номер 2,
затем переложить большой диск на колышек 3 и в завершение переложить
два меньших диска с колышка 2 на колышек 3.
Итак мы можем переместить пирамиду любой высоты n, если
воспользуемся следующим алгоритмом: 1) переложить верхние n − 1
дисков на второй колышек; 2) переложить диск n на третий колышек;
3) переложить n −1 меньший диск со второго колышка на третий. Таким
образом, для перемещения n дисков нам достаточно T
n−1
+ 1 + T
n−1
10