Предисловие

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

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

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

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

• 2.1. Формулы сигнатуры . Истинность формулы на алгебраической системе (141мин.)
• 2.2. Секвенциальное исчисление предикатов (121мин.)
• 2.3. Эквивалентность формул в ИПC (40мин.)
• 2.4. Нормальные формы (40мин.)
• 2.5. Теорема о существовании модели (101мин.)
• 2.6. Исчисление предикатов гильбертовского типа (61мин.)
• 2.7. Скулемизация алгебраических систем (40мин.)
• 2.8. Метод резолюций в исчислении предикатов (182мин.)
• 2.9. Логические программы (81мин.)
• Задачи и упражнения (101мин.)
• Тест:  Логика и исчисления предикатов (96мин.)

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

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

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

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

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

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

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

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

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

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

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