- •1. Множества и бинарные отношения
- •Множества
- •Определения и примеры
- •1.1.1 Множество
- •Операции над множествами
- •Элементы комбинаторики
- •Бинарные отношения
- •Определения и примеры
- •2.1.2 Отображения
- •Операции над отношениями
- •Выполнение операций над отношениями
- •Свойства отношений
- •Эквивалентность и толерантность
- •2.4.1 Эквивалентность
- •2.4.3 Толерантность
- •2.4.6 Задача о наименьшем покрытии (ЗНП)
- •Алгоритм решения ЗНР
- •Отношения порядка
- •Строгий порядок
- •Свойства строгого порядка
- •Некоторые свойства дерева
- •Анализ отношений порядка
- •2.5.8 Решетки
- •2.5.10 Решетка
- •2.5.11 Булева решетка
- •Нормированные булевы решетки
- •Модели нормированной булевой решетки
- •Булевы функции (БФ)
- •Определения и примеры
- •Равенство булевых функций
- •3.3.1 СДНФ
- •3.3.3 СКНФ
- •3.3.5 Представление формул в СДНФ и СКНФ
- •Минимизация булевых функций
- •3.4.1 Импликанта
- •Полные системы булевых функций
- •2. Математическая логика
- •Логика высказываний
- •Основные понятия
- •4.1.7 Логическое следствие
- •4.1.8 Теоремы о логическом следствии
- •Логика предикатов
- •5.0.13 Связанные и свободные переменные
- •Предваренная нормальная форма
- •Стандартная нормальная форма
- •Подстановки и унификация
- •Метод резолюций для логики первого порядка
- •Исчисление высказываний
- •3. Графы
- •Определения и примеры
- •Определения графа
- •Части графа
- •Изоморфизм графов
- •Задание графов с помощью матриц
- •Матрица инциденций
- •Матрица соседства вершин
- •Матрица смежности
- •Типы графов
- •Обыкновенные графы
- •Графы Бержа
- •Помеченные и взвешенные графы
- •Другие способы задания графа
- •Связность графов
- •Маршруты, цепи, циклы
- •Число маршрутов
- •Компоненты связности
- •Нахождение компонент и бикомпонент
- •Кратчайшие цепи
- •Алгоритм Форда
- •Алгоритм Дейкстры
- •Обходы графа
- •Поиск в глубину на графе
- •Поиск в ширину на графе
- •Эйлеровы цепи и циклы
- •Эйлеровы пути
- •Гамильтоновы цепи и циклы
- •Цикломатика графов
- •Цикломатическое число
- •Деревья
- •Свойства дерева
- •Каркасы
- •Алгоритм нахождения каркаса графа.
- •Кратчайший каркас графа.
- •Алгоритм Прима.
- •Теорема о хорде каркаса.
- •Число каркасов графа.
- •Разрезы
- •Пространства суграфов
- •Пространство циклов
- •Пространство разрезов.
- •Потоки в сетях
- •Задача о максимальном потоке
- •Постановка задачи
- •Экстремальные части графа
- •Основные понятия
- •Покрытия
- •Задача о наименьшем покрытии
- •Паросочетания
- •Раскраска вершин графа
- •Хроматическое число
- •Оценки хроматического числа
- •Точные алгоритмы раскраски вершин
Оглавление |
1 |
|
|
|
|
Оглавление
1. Множества и бинарные отношения |
7 |
1. Множества |
8 |
1.1 Определения и примеры . . . . . . . . . . . . . . . . |
8 |
1.1.1Множество . . . . . . . . . . . . . . . . . . . 8
1.1.2 Универсальное множество . . . . . . . . . 11
1.1.3Представление множеств . . . . . . . . . . 12
1.1.4Диаграммы Эйлера–Венна . . . . . . . . . . 14
1.1.5Мощность множества . . . . . . . . . . . . . 15
1.1.6Мощность булеана множества . . . . . . . 16
1.2 Операции над множествами . . . . . . . . . . . . . 21
1.2.1Алгебраические свойства операций . . . . 25
1.2.2Булева алгебpа и алгебpа множеств . . . . 27
1.2.3Декартово произведение множеств . . . . 37
1.3Элементы комбинаторики . . . . . . . . . . . . . . . 38
2. Бинарные отношения |
43 |
2.1Определения и примеры . . . . . . . . . . . . . . . . 43
2.1.1Способы задания бинарного отношения . 44
2.1.2Отображения . . . . . . . . . . . . . . . . . . 47
2.2Операции над отношениями . . . . . . . . . . . . . 51
2.2.1Выполнение операций над отношениями . 54
2.2.2Алгебраические свойства операций . . . . 60
2.3Свойства отношений . . . . . . . . . . . . . . . . . . 65
2.4Эквивалентность и толерантность . . . . . . . . . . 68
2.4.1Эквивалентность . . . . . . . . . . . . . . . . 68
2 |
Оглавление |
|
|
2.4.2Эталоны и эквивалентность . . . . . . . . . 71
2.4.3Толерантность . . . . . . . . . . . . . . . . . 73
2.4.4Классы толератнтности . . . . . . . . . . . . 74
2.4.5Число разбиений . . . . . . . . . . . . . . . . 74
2.4.6Задача о наименьшем покрытии (ЗНП) . . 76
2.4.7Алгоритм решения ЗНР . . . . . . . . . . . . 78
2.5Отношения порядка . . . . . . . . . . . . . . . . . . . 81
2.5.1 Строгий порядок . . . . . . . . . . . . . . . . 81
2.5.2Свойства строгого порядка . . . . . . . . . . 82
2.5.3Нестрогий порядок . . . . . . . . . . . . . . 86
2.5.4Редукция отношения . . . . . . . . . . . . . 88
2.5.5Древесный порядок . . . . . . . . . . . . . . 90
2.5.6Некоторые свойства дерева . . . . . . . . . . 92
2.5.7 Анализ отношений порядка . . . . . . . . . 94
2.5.8Решетки . . . . . . . . . . . . . . . . . . . . . 95
2.5.9Диаграммы Хассе . . . . . . . . . . . . . . . 96
2.5.10Решетка . . . . . . . . . . . . . . . . . . . . . 97
2.5.11Булева решетка . . . . . . . . . . . . . . . . 100
2.5.12 Векторная решетка . . . . . . . . . . . . . 101
2.5.13Нормированные булевы решетки . . . . . . 102
2.5.14Модели нормированной булевой решетки . 102
3. Булевы функции (БФ) |
105 |
3.1Определения и примеры . . . . . . . . . . . . . . . . 105
3.1.1Булевы функции . . . . . . . . . . . . . . . . 105
3.1.2Табличное представление БФ . . . . . . . . 107
3.1.3Геометрическое представление БФ . . . . 109
3.1.4Представление БФ формулами . . . . . . . 110
3.2Равенство булевых функций . . . . . . . . . . . . . 112
3.2.1Фиктивные переменные . . . . . . . . . . . 112
3.2.2Равносильные формулы . . . . . . . . . . . 113
3.2.3Двойственные функции . . . . . . . . . . . 115
3.3Разложение функции по переменным . . . . . . . 116
3.3.1 СДНФ . . . . . . . . . . . . . . . . . . . . . . 118
3.3.2Построение СДНФ по таблице истинности119
3.3.3 СКНФ . . . . . . . . . . . . . . . . . . . . . . 120
Оглавление |
3 |
|
|
|
|
3.3.4Построение СКНФ по таблице истинности120
3.3.5Представление формул в СДНФ и СКНФ 121
3.3.6Представление БФ полиномами Жегал-
кина . . . . . . . . . . . . . . . . . . . . . . . . 123
3.4Минимизация булевых функций . . . . . . . . . . . 125
3.4.1Импликанта . . . . . . . . . . . . . . . . . . . 125
3.4.2Минимизация БФ . . . . . . . . . . . . . . . 126
3.4.3Алгоритм Квайна – МакКласки . . . . . . 127
3.4.4Алгоритм Блейка – Порецкого . . . . . . . 129
3.4.5 Таблица Квайна . . . . . . . . . . . . . . . . 130
3.5Полные системы булевых функций . . . . . . . . . 131
3.5.1Замкнутые классы булевых функций . . . 132
3.5.2Критерий Поста . . . . . . . . . . . . . . . . 134
2. Математическая логика |
138 |
4. Логика высказываний |
139 |
4.1 Основные понятия . . . . . . . . . . . . . . . . . |
. . 139 |
4.1.1Высказывания и формулы . . . . . . . . . . 139
4.1.2 Интерпретация формул . . . . . . . . . . . 141
4.1.3Общезначимость и противоречивость . . 142
4.1.4Эквивалентность формул . . . . . . . . . . 143
4.1.5Нормальные формы . . . . . . . . . . . . . . 145
4.1.6Приведение формул к нормальным фор-
мам . . . . . . . . . . . . . . . . . . . . . . . . . 146
4.1.7Логическое следствие . . . . . . . . . . . . . 147
4.1.8Теоремы о логическом следствии . . . . . 147
4.1.9Методы доказательства теорем . . . . . . . 149
4.1.10Метод резолюций . . . . . . . . . . . . . . 150
4.1.11 Стратегии очищения |
. . . . . . . . . . . . 155 |
5. Логика предикатов |
158 |
5.0.12Термы, предикаты, формулы . . . . . . . 158
5.0.13Связанные и свободные переменные . . 161
5.1 |
Интерпретация формул . . . . . . |
. . |
. . . . |
. . . |
. 164 |
5.2 |
Предваренная нормальная форма |
. . |
. . . . |
. . . |
. 166 |
4 |
Оглавление |
|
|
5.2.1Приведение формул к предваренной нормальной форме. . . . . . . . . . . . . . . . 170
5.3Стандартная нормальная форма . . . . . . . . . . . 171
5.4Подстановки и унификация . . . . . . . . . . . . . . 175
5.5Метод резолюций для логики первого порядка . 180
5.6Исчисление высказываний . . . . . . . . . . . . . . 182
5.6.1Формальные теории . . . . . . . . . . . . . . 182
5.6.2Классическое исчисление высказываний (КИВ) . . . . . . . . . . . . . . . . . . . . . . . . 184
3. Графы |
191 |
6. Определения и примеры |
192 |
6.1Определения графа . . . . . . . . . . . . . . . . . . . 192
6.1.1Граф как бинарное отношение . . . . . . . 192
6.1.2Определение Бержа . . . . . . . . . . . . . . 192
6.1.3Определение Зыкова . . . . . . . . . . . . . 193
6.1.4 Части графа . . . . . . . . . . . . . . . . . . . 195
6.1.5 Изоморфизм графов . . . . . . . . . . . . . . 197
6.2Задание графов с помощью матриц . . . . . . . . . 199
6.2.1 Матрица инциденций . . . . . . . . . . . . . 199
6.2.2Матрица соседства вершин . . . . . . . . . . 200
6.2.3Матрица смежности . . . . . . . . . . . . . . 202
6.3Типы графов . . . . . . . . . . . . . . . . . . . . . . . 203
6.3.1Обыкновенные графы . . . . . . . . . . . . . 205
6.3.2Графы Бержа . . . . . . . . . . . . . . . . . . . 207
6.3.3Двудольные графы . . . . . . . . . . . . . . . 209
6.3.4Помеченные и взвешенные графы . . . . . 210
6.4Другие способы задания графа . . . . . . . . . . . . 211
7. Связность графов |
214 |
7.1Маршруты, цепи, циклы . . . . . . . . . . . . . . . . 214 7.1.1 Число маршрутов . . . . . . . . . . . . . . . . 215
7.2 Теорема К¨енига . . . . . . . . . . . . . . . . . . . . 220
7.3Компоненты связности . . . . . . . . . . . . . . . . . 222 7.3.1 Нахождение компонент и бикомпонент . . 224
Оглавление |
5 |
|
|
|
|
7.4Кратчайшие цепи . . . . . . . . . . . . . . . . . . . . 224
7.4.1Алгоритм нахождения кратчайших цепей между заданными вершинами . . . . . . . . 225
7.4.2Кратчайшая цепь между заданными вершинами (взвешенный граф) . . . . . . . 226
7.4.3Алгоритм Форда . . . . . . . . . . . . . . . . . 226
7.4.4 Алгоритм Дейкстры . . . . . . . . . . . . . . 229
7.4.5Кратчайшие маршруты между всеми парами вершин. Алгоритм Флойда . . . . . 231
7.5 Обходы графа . . . . . . . . . . . |
. . . . . . . . . . . 234 |
|
7.5.1 |
Поиск в глубину на графе |
. . . . . . . . . . 234 |
7.5.2 |
Поиск в ширину на графе |
. . . . . . . . . . 236 |
7.5.3Эйлеровы цепи и циклы . . . . . . . . . . . . 237
7.5.4 Эйлеровы пути . . . . . . . . . . . . . . . . . 240
7.5.5Гамильтоновы цепи и циклы . . . . . . . . . 241
8. Цикломатика графов |
245 |
|
8.1 |
Цикломатическое число |
. . . . . . . . . . . . . . . . 245 |
8.2 |
Деревья . . . . . . . . . . |
. . . . . . . . . . . . . . . . 247 |
8.2.1Свойства дерева . . . . . . . . . . . . . . . . . 248
8.3Каркасы . . . . . . . . . . . . . . . . . . . . . . . . . . 249
8.3.1Алгоритм нахождения каркаса графа. . . . 250
8.3.2Кратчайший каркас графа. . . . . . . . . . . 251
8.3.3Алгоритм Прима. . . . . . . . . . . . . . . . . 252
8.3.4Теорема о хорде каркаса. . . . . . . . . . . . 256
8.3.5Число каркасов графа. . . . . . . . . . . . . . 257
8.3.6Разрезы . . . . . . . . . . . . . . . . . . . . . . 257
8.4 Пространства суграфов . . . . . . . . . . . . . . . . 258
8.4.1Пространство циклов . . . . . . . . . . . . . . 260
8.4.2Пространство разрезов. . . . . . . . . . . . . 261
9. Потоки в сетях |
266 |
9.1Задача о максимальном потоке . . . . . . . . . . . . 266
9.1.1Постановка задачи . . . . . . . . . . . . . . . 266
9.1.2Теорема о максимальном потоке и минимальном разрезе . . . . . . . . . . . . 267
9.1.3Алгоритм Форда – Фалкерсона . . . . . . . 270
6 |
Оглавление |
|
|
|
|
10.Экстремальные части графа |
275 |
|
10.1 Основные понятия . . |
. . . . . . . . . . . . . . . . . 275 |
|
10.2Покрытия . . . . . . . . . . . . . . . . . . . . . . . . . 277 10.2.1 Задача о наименьшем покрытии . . . . . . . 280
10.3Паросочетания . . . . . . . . . . . . . . . . . . . . . . 282
11Раскраска. вершин графа |
287 |
11.1Хроматическое число . . . . . . . . . . . . . . . . . . 287
11.2Оценки хроматического числа . . . . . . . . . . . . 288
11.3Точные алгоритмы раскраски вершин . . . . . . . 289
Часть 1