Предисловие

• МОЖНО ЛИ ДОВЕРЯТЬ МАТЕМАТИКЕ? | IQ (0мин.)

Тема 1. Исчисления высказываний

• 1.1. Определение формального исчисления (62мин.)
• 1.2. Исчисление высказываний генценовского типа (104мин.)
• 1.3. Эквивалентность формул (42мин.)
• 1.4. Нормальные формы (42мин.)
• 1.5. Семантика исчисления секвенций (83мин.)
• 1.6. Исчисление высказываний гильбертовского типа (62мин.)
• 1.7. Алгоритмы проверки общезначимости и противоречивости в ИВ (166мин.)
• • 1.7.1. Алгоритм Квайна (21мин.)
  • 1.7.2. Алгоритм редукции (21мин.)
  • 1.7.3. Метод резолюций в ИВ (83мин.)
  • 1.7.4. Метод резолюций для хорновских дизъюнктов (21мин.)
• Задачи и упражнения (62мин.)
• Тест:  ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ (72мин.)

Тема 2. Логика и исчисления предикатов

• 2.1. Формулы сигнатуры S. Истинность формулы на алгебраической системе (21мин.)
• 2.1. Формулы сигнатуры ∑. Истинность формулы на алгебраической системе (145мин.)
• 2.2. Секвенциальное исчисление предикатов (125мин.)
• 2.3. Эквивалентность формул в ИПC∑ (42мин.)
• 2.4. Нормальные формы (42мин.)
• 2.5. Теорема о существовании модели (104мин.)
• 2.6. Исчисление предикатов гильбертовского типа (62мин.)
• 2.7. Скулемизация алгебраических систем (42мин.)
• 2.8. Метод резолюций в исчислении предикатов (187мин.)
• 2.9. Логические программы (83мин.)
• Задачи и упражнения (104мин.)
• Тест:  Логика и исчисления предикатов (96мин.)

Тема 3. Элементы теории моделей

• 3.1. Элементарная эквивалентность. Теоремы Лёвенгейма — Скулема (104мин.)
• 3.2. Элементарные теории (125мин.)
• 3.3. Типы. Основные классы моделей (166мин.)
• 3.4. Категоричность. Спектры моделей полных теорий (125мин.)
• 3.5. Система аксиом арифметики Пеано. Нестандартные модели арифметики (62мин.)
• Задачи и упражнения (42мин.)
• Тест:  ЭЛЕМЕНТЫ ТЕОРИИ МОДЕЛЕЙ (58мин.)

Тема 4. Элементы теории алгоритмов

• 4.1. Машины Тьюринга (145мин.)
• • 4.1.1. Определение и примеры (62мин.)
  • 4.1.2. Композиция машин Тьюринга (21мин.)
  • 4.1.3. Условные операторы (21мин.)
  • 4.1.4. Функции, вычислимые на машинах Тьюринга (42мин.)
• 4.2. Рекурсивные функции и отношения (166мин.)
• • 4.2.1. Примитивно рекурсивные функции (62мин.)
  • 4.2.2. Примитивно рекурсивные отношения (42мин.)
  • 4.2.3. Нумерации кортежей натуральных чисел (21мин.)
  • 4.2.4. Частично рекурсивные функции (42мин.)
• 4.3. Эквивалентность моделей алгоритмов (83мин.)
• • 4.3.1. Правильная вычислимость частично рекурсивных функций (21мин.)
  • 4.3.2. Частичная рекурсивность правильно вычислимых функций (42мин.)
• 4.4. Универсальные частично рекурсивные функции. Теорема Райса (104мин.)
• 4.5. Рекурсивно перечислимые отношения (83мин.)
• 4.6. Неразрешимость исчисления предикатов. Теорема Гёделя о неполноте. Разрешимые и неразрешимые теории (145мин.)
• 4.7. Характеристики сложности алгоритмов (42мин.)
• • 4.7.1. Определение и связь основных характеристик (21мин.)
  • 4.7.2. О верхней границе сложности вычислений (21мин.)
  • 4.7.3. О наилучших вычислениях (21мин.)
• 4.8. Переборные задачи (145мин.)
• 4.9. Алгоритмы сортировки (62мин.)
• 4.10. Конечные автоматы (62мин.)
• Задачи и упражнения (62мин.)
• Тест:  Элементы теории алгоритмов (110мин.)

Тема 5. Неклассические логики

• 5.1. Пропозициональные логики (228мин.)
• • 5.1.1. Интуиционистские логики (21мин.)
  • 5.1.2. Многозначные логики (21мин.)
  • 5.1.3. Нечеткие логики и нечеткие подмножества (83мин.)
  • 5.1.4. Модальные логики (62мин.)
  • 5.1.5. Временны́е (темпоральные) логики (42мин.)
• 5.2. Предикатные логики (62мин.)
• • 5.2.1. Многосортные логики первого порядка (21мин.)
  • 5.2.2. Слабая логика второго порядка (21мин.)
  • 5.2.3. Бесконечные логики (21мин.)
  • 5.2.4. Логика с новыми кванторами (21мин.)
• 5.3. Предикатные временные логики и их приложение к программированию (104мин.)
• 5.4. Алгоритмические логики (83мин.)
• Задачи и упражнения (21мин.)
• Тест:  Неклассические логики (40мин.)

Библиографический список

Приложение. Варианты типового расчета

Новые издания по дисциплине «Математическая логика и теория алгоритмов» и смежным дисциплинам

Завершение курса

• Тест:  Итоговое тестирование (40мин.)