Оглавление
Авторское предисловие 3
Глава 1. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ
1. Начальные понятия теории множеств 5
2. Операции над множествами. Диаграммы Венна 9
3. Отношения 13
4. Функции 17
5. Эквивалентность 21
6. Порядок 24
Глава 2. ЛОГИКА ВЫСКАЗЫВАНИЙ
1. Зачем мы изучаем математическую логику? 27
2. Высказывания 30
3. Логические связки 31
4. Формулы логики высказываний 35
5. Равносильность формул 38
6. Тождественно-истинные формулы 41
7. Нормальные формы формул 43
8. Разрешимость для логики высказываний 49
Глава 3. БУЛЕВЫ АЛГЕБРЫ
1. Абстрактное определение булевой алгебры 52
2. Булевы функции. Теорема о нормальной булевой форме 56
3. Полные системы булевых функций 60
4. Переключательные элементы 61
Глава 4. ЛОГИКА ПРЕДИКАТОВ
1. Формулы логики предикатов 67
2. Интерпретации 71
3. Выполнимость и общезначимость 74
Глава 5. ИСЧИСЛЕНИЯ
1. Формальные аксиоматические теории 79
2. Исчисление высказываний 82
3. Исчисление предикатов 90
4. Логический вывод 93
5. Метод резолюций 97
6. Неполнота математики 104
Глава 6. ТЕОРИЯ АЛГОРИТМОВ
1. Понятие алгоритма и неформальная вычислимость 108
2. Частично-рекурсивные функции 110
3. Ламбда-исчисление 115
4. Машины Тьюринга 125
5. Тезис Чёрча 129
6. Некоторые алгоритмически неразрешимые проблемы 130
7. Сложность алгоритмов 132
Глава 7. ЛОГИЧЕСКИЕ ПАРАДОКСЫ 143
Глава 8. МНОГОЗНАЧНЫЕ ЛОГИКИ 148
Решения логических задач 153
Решения упражнений 163
Литература 173