Конспект лекций для экзамена по курсу Математическая логика

Теория алгоритмов.
Различные подходы к определению алгоритма:
Машина с неограниченными регистрами (МНР).
Машина Тьюринга - Поста.
Нормальные алгоритмы Маркова.
Реализация функции натурального переменного.
Эквивалентность трех подходов к понятию алгоритма.
Булевы функции.
Основные определения.
Дизъюнктивные нормальные формы.
Логические исчисления.
Исчисление высказываний (ИВ).
Правило одновременной подстановки.
Критерий выводимости в ИВ.
Формальные исчисления.
Предикаты и кванторы.
Определение предиката.
Понятие квантора.
Геометрическая интерпретация навешивания кванторов.