Каверин С.В. Лекции по математической логике и теории алгоритмов

Тольятти, 2002Алгебра логики.
Определение булевой функции.
Элементарные булевы функции.
Задание булевых функций посредством элементарных.
Существенные и несущественные переменные.
Таблицы истинности.
Эквивалентные функции.
Основные эквивалентности.
Функциональная полнота.
Булева алгебра.
Нормальные формы.
Совершенные нормальные формы.
Минимизация ДНФ методом Квайна.
Карты Карно.
Алгебра Жегалкина.
Высказывания. Предикаты.
Высказывания.
Предикаты. Логические операции над предикатами.
Кванторы, их свойства.
Формальные теории.
Определение формальной теории.
Исчисление высказываний.
Теорема о дедукции. Полнота исчисления высказываний.
Автоматическое доказательство теорем.
Метод резолюций в исчислении высказываний.
Элементы теории алгоритмов.
Определение алгоритма.
Машина Тьюринга.
Рекурсивные функции.
Алгоритмически неразрешимые задачи.
Алгоритмы и их сложности.