Введение в математическую логику. Учебное пособие

Предисловие
Глава 1. Миссия математической логики
§ 1. Логика
§ 2. Математика
§ 3. Софизмы и парадоксы
§ 4. Математическая логика
Задачи
Глава 2. Краткая история логики
§ 1. Становление логики
§ 2. Начала математической логики
§ 3. Математическая логика в своем блеске и
великолепии
Геттингенская программа
Теоремы Геделя
Неклассическая логика
Эра компьютеров
Бурба ки
Теория вычислительной сложности
Глава 3. Основы теории множеств
§ 1. Интуитивная теория множеств
§ 2. Операции над множествами. Диаграммы Эйлера
- Венна
Индексированные семейства множеств
§ 3. Отношения
§ 4. Эквивалентность и порядок
§ 5. Функции
§ 6. Мощность множеств
Задачи
Глава 4. Пропозициональная логика
§ 1. Высказывания и высказывательные формы
Простые высказывания
Именные и высказывательные формы
Сложные высказывания и логические операции
Логические операции для автореферентных
высказываний
§ 2. Язык логики высказываний
«Криминальные» задачи
Задачи о рыцарях и лжецах
§ 3. Тавтологии и равносильности
§ 4. Логическое следование
§ 5. Булевы алгебры
Определение булевых алгебр и их интерпретации
Булевы функции
Полные системы булевых функций Задачи
Глава 5. Языки первого порядка
§ 1. Предикаты и кванторы
Применение логического языка в теории множеств
§ 2. Термы и формулы
§ 3. Интерпретация формул
§ 4. Формулы общезначимые, выполнимые и
логически эквивалентные
Выразимость
Логическое следование
§ 5. Перевод с естественного языка на логический
и обратно
Правила для перевода
«Многоэтажные» кванторы. Дополнительные
ограничения Единственность и неединственность
Задачи_
Глава 6. Аксиоматические теории
§ 1. Предварительные понятия и простые примеры
§ 2. Формальные аксиоматические теории
Определение формальной аксиоматической теории
Выводимость
Интерпретация, модель
Полнота, независимость и разрешимость
§ 3. Исчисление высказываний
Полнота, разрешимость и непротиворечивость
исчисления высказываний Другие аксиоматизации
исчисления высказываний
§ 4. Аксиоматизация геометрии § 5. Теории первого
порядка
Синтаксические свойства истинности теорий с
языками первого порядка. Определение теорий
первого порядка
§ 6. Аксиоматика Пеано
§ 7. Аксиоматика Цермело - Френкеля Задачи
Глава 7. Математическое доказательство § 1.
Индукция
§ 2. Математическая индукция
Парадоксы и софизм при математической индукции
Математическая индукция по построению
§3. Различные виды доказательств в математике
§ 4. Компьютерные доказательства
Задачи
Глава 8. Неформально о вычислимости
s 1. Понятие алгоритма и неформальная
вычислимость
§ 2. Перечислимые и разрешимые множества
§ з. Универсальные функции и неразрешимые
множества
Глава 9. Формализации вычислимости
§ 1. Частично-рекурсивные функции
Определения
Примеры рекурсивности
§ 2. Машины Тьюринга
§ 3. Ламбда-исчисление
Значение ламбда-исчисления
Синтаксис и семантика ламбда-исчисления
Вычисление ламбда-выражений
Нормальные формы
Комбинаторы
Задачи
Глава 10. Алгоритмически неразрешимые проблемы
§ 1. Ламбда-определимые функции
Истинностные значения и условное выражение
Пары и кортежи
Тест на ноль, предшествование, вычитание и
сравнение
Рекурсия
Функции с несколькими аргументами
Представление вычислимых функций
§ 2. Тезис Чёрча и алгоритмическая
неразрешимость
Диофантовы уравнения
Задачи
Глава 11. Теоремы Гёделя о неполноте
§ 1. Гёделева нумерация
§ 2. Первая теорема Гёделя о неполноте:
семантическая версия
§ 3. Первая теорема Гёделя о неполноте:
синтаксическая версия
§ 4. Обобщения и вторая теорема Гёделя
§ 5. Теорема Гудстейна