Мат. логика·Курс
Математическая логика и теория алгоритмов
Курс по математической логике: исчисление предикатов, теоремы Гёделя, теория вычислимости, машины Тьюринга и сложность алгоритмов
5
Модулей
15
Статей
~2 ч
Чтения
IV
CLOs
§ 01 — Программа
5 модулей.
Каждый модуль — отдельный блок. Большинство читается по порядку — но опытный читатель может начать с любого.
- M IПропозициональная логикаСинтаксис, семантика, нормальные формы и алгоритм DPLL3 статей
18 минОткрыть → - M IIЛогика предикатов первого порядкаПредикаты, кванторы, структуры и теорема Гёделя о полноте3 статей
18 минОткрыть → - M IIIТеория вычислимостиМашины Тьюринга, разрешимость и теорема Черча-Тьюринга3 статей
18 минОткрыть → - M IVТеория доказательствНатуральный вывод, секвенциальное исчисление и теорема об устранении сечений3 статей
18 минОткрыть → - M VТеория моделейМодели, элементарная эквивалентность, типы и теорема Лёвенхейма-Сколема3 статей
18 минОткрыть →
§ 02 — Результаты обучения
4 результата.
CLO I
Логические исчисления
Работать с исчислением высказываний и предикатов, строить формальные доказательства
CLO II
Теоремы Гёделя
Понимать теоремы о неполноте и их следствия для математики
CLO III
Теория вычислимости
Анализировать машины Тьюринга, разрешимость и неразрешимость
CLO IV
Сложность алгоритмов
Классифицировать задачи по сложности, понимать классы P и NP
§ 03 — Практики