Математическая логика и теория алгоритмов

Зюзьков Валентин Михайлович, профессор кафедры "Компьютерные системы в управлении и проектировании" ТУСУР. Кандидат физ.-мат. наук, старший научный сотрудник. Хабибулина Надежда Юрьевна, доцент кафедры "Компьютерные системы в управлении и проектировании" ТУСУР. Кандидат тех. наук.

Томский государственный университет систем управления и радиоэлектроники (ТУСУР)

При решении прикладных задач часто появляется необходимость переводить информацию с содержательного языка на математический, оттуда на язык численных методов и алгоритмов, а с него на конкретный язык программирования, и обратно. Знание мощных и простых способов преобразования математических предложений, предоставляемых математической логикой, понадобятся каждому, кто хочет начать заниматься исследованиями или создавать эффективные программы.
Наряду с рассмотрением сложных вопросов на достаточно строгом уровне, курс содержит множество примеров и пояснений, которые помогут усвоить трудные понятия и проблемы.

Программа

Глава 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. Сложность задач

Ключевые слова

Математика, логика, теория множеств, пропозициональная логика, математическое доказательство, аксиоматический метод, теория алгоритмов