Математическая логика и теория алгоритмов: Учебное пособие

Description

Учебное пособие состоит из двух разделов: исчисления и алгоритмы. Теоретический материал сопровождается примерами решения задач и упражнениями. Для студентов механико-математического факультета и факультета компьютерных наук и информационных технологий, а также магистров и аспирантов. Обложка Предисловие Введение Раздел 1. ИСЧИСЛЕНИЯ Глава 1. Исчисление высказываний 1.1. Алгебра высказываний 1.2. Приложения алгебры высказываний 1.2.1. Функции алгебры высказываний (булевы функции) 1.2.2. Полнота и замкнутость систем булевых функций 1.2.3. Метод синтеза релейно – контактных схем 1.2.4. Приложение в теории множеств 1.3. Аксиоматическая система в исчислении высказываний Глава 2. Исчисление предикатов 2.1. Предикаты 2.2. Система аксиом в исчислении предикатов 2.3. Формальная арифметика Раздел 2. АЛГОРИТМЫ Глава 1. Алгоритмы и вычислимые функции 1.1. Машина Тьюринга 1.2. Частично рекурсивные функции 1.2.1. Класс примитивно рекурсивных функций 1.2.2. Рекурсивно перечислимые множества и предикаты 1.2.3. Порожденные множества 1.2.4. Функции на n-ках 1.2.5. Рекурсия 2-й ступени 1.2.6. Универсальные функции 1.2.7. Универсальные частично рекурсивные функции Глава 2. Приложения теории алгоритмов 2.1. Теоремы о рекурсии и неполноте 2.2. Разрешимость и неразрешимость формальных систем Глава 3. Сложность вычислений 3.1. Меры сложности 3.2. Теорема об ускорении 3.3. Классы сложности. Элементарные функции Список рекомендуемой литературы Оглавление