Оглавление

Авторское предисловие 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