Программа курса

Глава 1. Миссия математической логики

1. Что такое логика
2. Что такое математика
3. Софизмы и парадоксы
4. Математическая логика
5. Становление логики
6. Начало математической логики
7. Математическая логика в своем блеске и великолепии

Глава 2. Основы теории множеств

1. «Интуитивная» теория множеств
2. Операции над множествами
3. Отношения
4. Специальные свойства отношений
5. Эквивалентность и порядок
6. Функции (отображения)

Глава 3. Пропозициональная логика

1. Высказывания и высказывательные формы
2. Пропозициональные логические связки
3. Язык логики высказываний
4. Тавтологии
5. Равносильности

Глава 4. Языки первого порядка

1. Предикаты и кванторы
2. Термы и формулы
3. Интерпретация формул
4. Формулы общезначимые, выполнимые, логически эквивалентные
5. Перевод с естественного языка на логический и обратно
6. Примеры перевода с естественного языка на логический и обратно

Глава 5. Аксиоматический метод

1. Аксиоматическое построение математических теорий
2. Формальные аксиоматические теории
3. Исчисление высказываний
4. Теории первого порядка
5. Примеры формальных аксиоматических теорий

Глава 6. Математическое доказательство

1. Индуктивное рассуждение
2. Математическая индукция
3. Различные виды доказательств в математике
4. Компьютерные доказательства

Глава 7. Теория алгоритмов

1. Неформальная вычислимость и машины Тьюринга
2. Частично-рекурсивные функции
3. Тезис Черча
4. Некоторые алгоритмически неразрешимые проблемы
5. Асимптотические обозначения
6. Алгоритмы и их сложность
7. Сложность задач