Предисловие к третьему изданию... 3
Глава первая.
Множества, функции, отношения... 4
1.1. Множества и операции над ними... 4
1.2. Соответствия и функции.... 15
1.3. Отношения.... 27
Глава вторая.
Элементы общей алгебры.... 35
2.1. Операции на множествах и их свойства... 35
2.2. Полугруппы, группы, решетки... 41
Глава третья.
Введение в логику..... 50
3.1. Логические функции (функции алгебры логики)... 50
3.2. Булева алгебра .... 56
3.3. Полнота и замкнутость.... 71
3.4. Язык логики предикатов ... 82
Глава четвертая.
Графы..... 91
4.1. Основные понятия.... 91
4.2. Пути и связность в неориентированных графах... 99
4.3. Пути и связность в ориентированных графах... 107
4.4. Деревья..... 114
4.5. Пространство циклов.... 118
4.6. Двудольные и планарные графы... 125
4.7. Раскраски, устойчивость, покрытия... 132
4.8. Оптимизационные задачи на графах... 137
Глава пятая.
Теория алгоритмов .... 151
5.1. Предварительное обсуждение... 151
5.2. Машины Тьюринга.... 163
5.3. Рекурсивные функции.... 188
5.4. Вычислимость и разрешимость... 211
5.5. Вычислительная сложность и NP-трудные задачи ... 227
Глава шестая.
Формальные системы.... 240
6.1. Формальные теории (логические исчисления). Исчисление высказываний... 242
6.2. Исчисление предикатов
и теории первого порядка... 254
6.3. Метатеория логических исчислений... 265
6.4. Абстрактные формальные системы... 274
Глава седьмая.
Языки и грамматики.... 291
7.1. Формальные грамматики и их свойства... 293
7.2. Операции над языками.... 315
7.3. О семантике формальных языков ... 324
Глава восьмая.
Автоматы..... 328
8.1. Основные понятия.... 328
8.2. Распознавание множеств автоматами... 347
8.3. Сети из автоматов, их анализ и синтез... 366
8.4. Программная реализация
логических функций и автоматов ... 383
Рекомендуемая литература.... 388
Основная литература.... 388
Дополнительная литература... 389
Предметный указатель.... 390