Алиев Ф.К., Юров И.А. Курс лекций по математической логике и теории алгоритмов

Учебное пособие. М.: МИФИ, 2003. – 199 с.
В настоящем учебном пособии изложены основы теории двоичных функций, исчисления предикатов, теории моделей, элементов теории алгоритмов и теории сложности вычислительных задач.
Книга предназначена для студентов, специализирующихся в областях, связанных с информационной безопасностью, а также для преподавателей дискретной математики.
В книге 18 лекций.
Содержание.
Введение
Основные способы задания двоичных функций.
Основные способы задания двоичных функций (продолжение)
Полнота и замкнутость. Критерий полноты системы.
Псевдобулевы функции. Функции k-значной логики
Минимизация двоичных функций. Геометрическая интерпретация минимизации ДНФ.
Метод Квайна— Мак-Класки нахождения сокращенной ДНФ двоичной функции. Метод нахождения тупиковых ДНФ. Метод Петрика нахождения тупиковых ДНФ
Алгебраические системы
Алгебры высказываний. Предикаты и операции над ними
Исчисление предикатов
Понятие о теории моделей
Элементы теории алгоритмов
Частично рекурсивные функции и их вычислимость
Нумерация наборов чисел и слов
Нормальные алгоритмы
Нумерация алгоритмов
Алгоритмически неразрешимые проблемы
Характеристики сложности вычислений
Характеристика сложности вычислительных задач
Список литературы