Введение

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

1. Логика высказываний
2. Понятие формальной теории
3. Исчисление высказываний (ИВ)
4. Теорема дедукции
5. Непротиворечивость и полнота ИВ
6. Методы проверки выводимости формул ИВ
7. Контрольные вопросы
8. Понятие предиката
9. Логические эквивалентности с кванторами
10. Термы и формулы в исчислении предикатов (ИП)
11. Аксиомы и правила вывода в ИП
12. Теоремы об ИП первого порядка
13. Контрольные вопросы

II. Элементы теории алгоритмов и рекурсивных функций

1. Понятие алгоритма
2. Машина Тьюринга (МТ)
3. Вычисление функций на МТ
4. Алгоритмически неразрешимые задачи
5. Примитивно рекурсивные функции
6. Частично рекурсивные функции
7. Характеристики сложности алгоритмов
8. Классы сложности P и NP
9. Контрольные вопросы

Предметный указатель