Часть I. Логика

Глава 1. Классическая логика

• 1.1. Логика высказываний
  • 1.1.1. Высказывания
  • 1.1.2. Основные законы логики
  • 1.1.3. Логический парадокс Рассела
  • 1.1.4. Алгебра (логика) высказываний
  • 1.1.5. Релейно-контактные схемы
  • 1.1.6. Равносильные формулы
  • 1.1.7. Алгебра Буля
  • 1.1.8. Истинные и общезначимые формулы
  • 1.1.9. Проблема разрешимости
  • 1.1.10.Логическое следствие
  • 1.1.11.Силлогизмы
• 1.2. Логика предикатов
  • 1.2.1. Предикаты и формулы
  • 1.2.2. Интерпретации
  • 1.2.3. Истинность и выполнимость формул. Модели, общезначимость, логическое следствие
  • 1.2.4. Готлоб Фреге
  • 1.2.5. Сколемовские функции и сколемизация формул
• 1.3. Метод резолюций
  • 1.3.1. Метод резолюций в логике высказываний
  • 1.3.2. Метод резолюций в логике предикатов

Глава 2. Формальные теории (исчисления)

• 2.1. Определение формальной теории, или исчисления
  • 2.1.1. Доказательство. Непротиворечивость теории. Полнота теории
• 2.2. Исчисление высказываний
  • 2.2.1. Язык и правила вывода исчисления высказываний
  • 2.2.2. Пример доказательства теоремы
  • 2.2.3. Полнота и непротиворечивость исчисления высказываний
• 2.3. Исчисление предикатов
  • 2.3.1. Язык и правила вывода исчисления предикатов
  • 2.3.2. Полнота и непротиворечивость исчисления предикатов
• 2.4. Формальная арифметика
  • 2.4.1. Эгалитарные теории
  • 2.4.2. Язык и правила вывода формальной арифметики
  • 2.4.3. Непротиворечивость формальной арифметики. Теорема Генцена
  • 2.4.4. Теорема Геделя о неполноте
  • 2.4.5. Курт Гедель
• 2.5. Автоматический вывод теорем
  • 2.5.1. С.Ю. Маслов
• 2.6. Логическое программирование
  • 2.6.1. Логическая программа
  • 2.6.2. Языки логического программирования

Глава 3. Неклассические логики

• 3.1. Интуиционистская логика
• 3.2. Нечеткая логика
  • 3.2.1. Нечеткие подмножества
  • 3.2.2. Операции над нечеткими подмножествами
  • 3.2.3. Свойства множества нечетких подмножеств
  • 3.2.4. Нечеткая логика высказываний
  • 3.2.5. Нечеткие релейно-контактные схемы
• 3.3. Модальные логики
  • 3.3.1. Типы модальности
  • 3.3.2. Исчисления I и Т (Фейса-фон Вригта)
  • 3.3.3. Исчисления S4, S5 и исчисление Брауэра
  • 3.3.4. Означивание формул
  • 3.3.5. Семантика Крипке
  • 3.3.6. Другие интерпретации модальных знаков
• 3.4. Георг фон Вригт
• 3.5. Временные логики
  • 3.5.1. Временная логика Прайора
  • 3.5.2. Временная логика Леммона
  • 3.5.3. Временная логика фон Вригта
  • 3.5.4. Приложение временных логик к программированию
  • 3.5.5. Временная логика Пнуели
• 3.6. Алгоритмические логики
  • 3.6.1. Принципы построения алгоритмической логики
  • 3.6.2. Чарльз Хоар
  • 3.6.3. Алгоритмическая логика Хоара

Часть II. Алгоритмы

Глава 4. Алгоритмы

• 4.1. Понятие алгоритма и вычислимой функции
• 4.2. Рекурсивные функции
  • 4.2.1. Примитивно рекурсивные функции
  • 4.2.2. Частично рекурсивные функции
  • 4.2.3. Тезис Чёрча
• 4.3. Машина Тьюринга-Поста
  • 4.3.1. Вычисления функций на машине Тьюринга-Поста
  • 4.3.2. Примеры вычислений
  • 4.3.3. Тезис Тьюринга
  • 4.3.4. Универсальная машина Тьюринга-Поста
• 4.4. Алан Тьюринг
• 4.5. Эмиль Пост
• 4.6. Эффективные алгоритмы
• 4.7. Алгоритмически неразрешимые проблемы

Глава 5. Сложность алгоритмов

• 5.1. Понятие о сложности алгоритмов
• 5.2. Классы задач P и NP
  • 5.2.1. Класс задач P
  • 5.2.2. Класс задач NP
  • 5.2.3. Недетерминированная машина Тьюринга
• 5.3. О понятии сложности
  • 5.3.1. Три типа сложности
  • 5.3.2. Четыре категории чисел по Колмогорову
  • 5.3.3. Тезис Колмогорова
• 5.4. А.Н. Колмогоров

Глава 6. Алгоритмы реальности

• 6.1. Генератор виртуальной реальности
• 6.2. Принцип Тьюринга
• 6.3. Логически возможные среды Кантгоуту

Литература