Рабочая программа. Математическая логика и теория алгоритмов

### Рабочая программа курса

1. Логические исчисления.

- Логика высказываний.
- Понятие формальной теории.
- Определение исчисления высказываний (ИВ).
- Выводимость в ИВ. Теорема дедукции.
- Полнота и непротиворечивость ИВ.
- Метод Куайна.
- Метод редукции.
- Метод резолюций.
- Понятие предиката.
- Кванторы. Логические эквивалентности с кванторами.
- Термы и формулы в исчислении предикатов (ИП).
- Аксиомы и правила вывода в ИП.
- Теоремы об ИП первого порядка.
- Предваренная форма.

2. Машина Тьюринга.

- Понятие машины Тьюринга (МТ).
- Внешний и внутренний алфавиты МТ.
- Программа МТ.
- Вычисление функций на МТ.
- Тезис Тьюринга.

3. Частично рекурсивные функции.

- Базовые функции.
- Определение примитивно рекурсивной функции, частично рекурсивной функции.
- Операции суперпозиции, примитивной рекурсии, минимизации.
- Тезис Черча.
- Алгоритмически неразрешимые задачи.
- Характеристики сложности алгоритмов. Классы сложности P и NP.