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

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

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

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

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

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