Математическая логика и теория алгоритмов — Учебное пособие создано в соответствии с Федеральным государственным образовательным стандартом по направлениям подготовки "Информатика и вычислительная техника", "Информационные системы", "Фундаментальная информатика и информационные технологии" (квалификация "бакалавр"). Изложены основные понятия математической логики, а также качественной и количественной теории алгоритмов. Рассмотрены элементы теории множеств, логика высказываний, исчисление высказываний, логика предикатов, элементарные языки, исчисление предикатов, элементарные теории, теория моделей, начальные понятия теории алгоритмов, начала алгоритмической теории множеств, машины Тьюринга и связанный с ними подход к формализации понятия алгоритма, нормальные алгоритмы, рекурсивные функции, наиболее известные результаты об алгоритмической неразрешимости, формальная арифметика, метод резолюций, интуиционистская логика, элементы теории сложности вычислений. Для студентов учреждений высшего профессионального образования. Может быть полезно широкому кругу читателей, интересующихся основами математической логики и теории вычислимости.
Название: Математическая логика и теория алгоритмов Автор: Крупский В. Н., Плиско В. Е. Издательство: Академия Год: 2013 Страниц: 418 Формат: PDF Размер: 30,49 МБ Качество: Отличное
Содержание:
Глава 1. Элементы теории множеств 1.1. Множества 1.2. Соответствия и функции 1.3. Бинарные отношения 1.4. Числовые множества 1.5. Эквивалентные множества 1.6. Парадоксы теории множеств 1.7. Аксиоматическая система теории множеств 1.8. Программа Гильберта Глава 2. Логика высказываний 2.1. Высказывания и логические операции 2.2. Алфавит, буква, слово 2.3. Пропозициональные формулы 2.4. Истинностные таблицы 2.5. Тавтологии 2.6. Равносильные формулы 2.7. Принцип двойственности 2.8. Нормальные формы в логике высказываний 2.9. Выполнимость и логическое следование в логике высказываний Глава 3. Исчисление высказываний 3.1. Общее понятие исчисления 3.2. Классическое исчисление высказываний 3.3. Теорема о дедукции и допустимые правила вывода 3.4. Корректность и полнота исчисления высказываний 3.5. Секвенциальное исчисление высказываний Глава 4. Логика предикатов 4.1. Высказывательные формы и кванторы 4.2. Понятие предиката 4.3. Предикатные формулы 4.4. Выполнимость и общезначимость 4.5. Равносильные формулы Глава 5. Элементарные языки 5.1. Определение элементарного языка 5.2. Примеры элементарных языков 5.3. Языки второго порядка 5.4. Подстановка 5.5. Алгебраические системы 5.6. Предваренные формулы Глава 6. Исчисление предикатов 6.1. Логическое следование 6.2. Аксиомы и правила вывода классического исчисления предикатов 6.3. Теорема о дедукции и другие допустимые правила вывода 6.4. Непротиворечивые расширения 6.5. Теорема Гёделя о полноте 6.6. Секвенциальное исчисление предикатов Глава 7. Элементарные теории и модели 7.1. Аксиоматические теории 7.2. Элементарные теории с равенством 7.3. Изоморфизмы и элементарная эквивалентность 7.4. Аксиоматизируемые классы Глава 8. Начальные понятия теории алгоритмов 8.1. Неформальное понятие алгоритма 8.2. Конструктивные объекты 8.3. Алгоритмический процесс 8.4. Вычислимые функции 8.5. Сигнализирующее множество Глава 9. Алгоритмическая теория множеств 9.1. Разрешимые множества 9.2. Полуразрешимые множества 9.3. Перечислимые множества 9.4. Равнообъемность понятий перечислимости и полуразрешимости 9.5. Теорема о графике 9.6. Эффективно аксиоматизируемые теории Глава 10. Машины Тьюринга 10.1. Одноленточная машина Тьюринга 10.2. Вычисление функций на машинах Тьюринга 10.3. Синтез машин Тьюринга 10.4. Тезис Тьюринга 10.5. Универсальная машина Тьюринга 10.6. Теорема о компиляции 10.7. Многоленточные машины Тьюринга Глава 11. Другие формализации вычислимости 11.1. Рекурсивные функции 11.2. Нормальные алгорифмы Глава 12. Неразрешимые алгоритмические проблемы 12.1. Нумерации вычислимых числовых функций 12.2. Нумерации, порожденные машинами Тьюринга 12.3. Примеры невычислимых функций 12.4. Теорема Успенского — Райса 12.5. Десятая проблема Гильберта 12.6. Проблема равенства слов в полугруппах Глава 13. Формальная арифметика 13.1. Аксиомы Пеано 13.2. Нестандартные модели арифметики 13.3. Арифметические множества и функции 13.4. Теорема о неподвижной точке 13.5. Теорема Тарского 13.6. Теорема Гёделя о неполноте 13.7. Формальная система арифметики 13.8. Тождественно истинные предикатные формулы 13.9. О логике второго порядка Глава 14. Метод резолюций 14.1. Скулемовская форма высказываний 14.2. Дизъюнктная форма высказываний 14.3. Теорема Эрбрана 14.4. Метод резолюций для логики высказываний 14.5. Алгоритм унификации 14.6. Метод резолюций для элементарных языков 14.7. Хорновские дизъюнкты 14.8. Логические программы Глава 15. Интуиционистская логика 15.1. Что такое интуиционизм 15.2. Интуиционистская логика высказываний 15.3. Интуиционистская логика предикатов 15.4. Рекурсивная реализуемость Глава 16. Элементы теории сложности вычислений 16.1. Предварительные сведения 16.2. Меры сложности вычислений 16.3. Класс Р 16.4. Класс NP 16.5. Примеры заведомо трудных задач
