Зюзьков В.М. Математическая логика и теория алгоритмов

Учебное пособие. — Томск: Эль Контент, 2015. — 236 с. — ISBN: 978-5-4332-0197-2Учебное пособие содержит теоретический материал, изучение которого предусмотрено программой курса «Математическая логика и теория алгоритмов» направлений подготовки бакалавров «Информатика и вычислительная техника» и «Управление в технических системах». См. также учебно-методическое пособие В.М. Зюзькова «Математическая логика и теория алгоритмов».Миссия математической логики
Логика
Математика
Софизмы и парадоксы
Математическая логика
Краткая история логики
Становление логики
Начало математической логики
Математическая логика в своем блеске и великолепии
Основы теории множеств
Интуитивная теория множеств
Операции над множествами. Диаграммы Эйлера—Венна
Отношения
Эквивалентность и порядок
Функции
Мощность множеств
Пропозициональная логика
Высказывания и высказывательные формы
Язык логики высказываний
Тавтологии и равносильности
Логическое следствие
Языки первого порядка
Предикаты и кванторы
Термы и формулы
Интерпретация формул
Формулы общезначимые, выполнимые, логически эквивалентные
Перевод с естественного языка на логический и обратно
Аксиоматический метод
Предварительные понятия и простые примеры
Формальные аксиоматические теории
Исчисление высказываний
Аксиоматизация геометрии
Теории первого порядка
Аксиоматика Пеано
Аксиоматика Цермело-Френкеля
Математическое доказательство
Индукция
Математическая индукция
Различные виды доказательств в математике
Компьютерные доказательства
Алгоритмы и вычислимые функции
Понятие алгоритма и неформальная вычислимость
Частично рекурсивные функции
Машины Тьюринга
Тезис Чёрча
Некоторые алгоритмически неразрешимые проблемы
Сложность вычислений
Асимптотические обозначения
Алгоритмы и их сложность
Сложность задач