Математическая логика и теория алгоритмов, Самохин А.В., 2003

Математическая логика и теория алгоритмов, Самохин А.В., 2003.
   Имеет ли отношение математическая логика к тому, что необходимо знать специалисту по ЭВМ?
Мы надеемся, что в результате изучения этого курса слушатель убедится. что имеет, и самое непосредственное. Так, главы III и IV имеют отношение к алгоритмическому проектированию электронных схем; главы V и VI — к автоматическому порождению синтаксически правильных текстов, т.е. к специальному программированию; остаток книги посвящен основам теории алгоритмов: здесь обсуждаются, какие задачи вообще являются алгоритмически разрешимыми и какова сложность соответствующих алгоритмов. В главах I и II собран материал по началам теории множеств, необходимый для понимания остального текста (как, впрочем, и почти всей математики).

Вполне упорядоченные множества.
Фундированные линейно упорядоченные множества называются вполне упорядоченными, а соответствующие порядки — полными. Для линейных порядков понятия наименьшего и минимального элемента совпадают, так что во вполне упорядоченном множестве всякое непустое подмножество имеет наименьший элемент.
Заметим, что частично упорядоченное множество, в котором всякое непустое подмножество имеет наименьший элемент, автоматически является линейно упорядоченным (в самом деле, всякое двухэлементное множество имеет наименьший элемент, поэтому любые два элемента сравнимы).
Содержание
Предисловие
Глава I. Множества и мощности
§1. Множества
§2. Число элементов
§3. Равномощные множества
§4. Счётные множества
§5. Теорема Кантора-Бернштейна
§6. Теорема Кантора
§7. Функции
§8. Операции над мощностями
Глава II. Упорядоченные множества
§1. Отношения эквивалентности и порядка
§2. Изоморфизмы
§3. Фундированные множества
§4. Вполне упорядоченные множества
Глава III. Логика высказываний
§1. Высказывания и операции
§2. Полные системы связок
§3. Схемы из функциональных элементов
Глава IV. Исчисление высказываний
§1. Исчисление высказываний
§2. Второе доказательство теоремы о полноте
§3. О женской логике
Глава V. Языки первого порядка
§1. Формулы и интерпретации
§2. Определение истинности
§3. Выразимые предикаты
§4. Выразимость в арифметике
§5. Невыразимые предикаты: автоморфизмы
Глава VI. Исчисление предикатов
§1. Общезначимые формулы
§2. Аксиомы и правила вывода
§3. Корректность исчисления предикатов
§4. Выводы в исчислении предикатов
4.1. Примеры выводимых формул
4.2. Выводимость из посылок
4.3. Переменные и константы
§5. Полнота исчисления предикатов
§6. О выводах и доказательствах
Глава VII. Вычислимые функции, разрешимые и перечислимые множества
§1. Вычислимые функции
§2. Разрешимые множества
§3. Перечислимые множества
§4. Перечислимые и разрешимые множества
§5. Перечислимость и вычислимость
Глава VIII. Универсальные функции и неразрешимость
§1. Универсальные функции
§2. Диагональная конструкция
§3. Перечислимое неразрешимое множество
Глава IX. Нумерации и операции
§1. Главные универсальные функции
§2. Вычислимые последовательности вычислимых функций
§3. Главные универсальные множества
§4. Множества номеров
Глава X. Теорема о неподвижной точке
§1. Неподвижная точка и отношения эквивалентности
§2. Программа, печатающая свой текст
§3. Несколько замечаний
3.1. Бесконечное множество неподвижных точек
3.2. Неподвижная точка с параметром
3.3. Неподвижная точка для перечислимых множеств
3.4. Пример использования
Глава XI. Машины Тьюринга
§1. Зачем нужны простые вычислительные модели?
§2. Машины Тьюринга: определение
§3. Машины Тьюринга: обсуждение
Глава XII. Арифметичность вычислимых функций
§1. Программы с конечным числом переменных
§2. Машины Тьюринга и программы
§3. Арифметичность вычислимых функций
§4. Теоремы Тарского и Гёделя
§5. О непостижимой эффективности математики
Глава XIII. Рекурсивные функции
§1. Примитивно рекурсивные функции
§2. Примеры примитивно рекурсивных функций
§3. Примитивно рекурсивные множества
§4. Другие виды рекурсии
§5. Машины Тьюринга и примитивно рекурсивные функции
§6. Частично рекурсивные функции
§7. Оценки скорости роста. Функция Аккермана
Задачи
§1. Алгебра высказываний
1.1. Таблицы истинности
1.2. Порядок действий и упрощённая запись формул
1.3. Равносильные преобразования и упрощение формул
§2. Двойственность в алгебре высказываний
§3. Нормальные формы: ДНФ, КНФ. СДНФ, СКНФ
§4. Релейно-контактные схемы и схемы из функциональных элементов
4.1. Задачи синтеза
4.2. Анализ схем
§5. Предикаты, кванторы, множества и отображения
5.1. Предикаты, кванторы, множества
5.2. Отображения
§6. Функции алгебры логики
§7. Машина Тьюринга
Список литературы.