Галиев Ш. И. Математическая логика и теория алгоритмов. - Казань: Издательство КГТУ им. А. Н. Туполева. 2002. - 270 с.
Пособие содержит следующие разделы. Логику высказываний и предикатов с приложениями, в том числе метод резолюций и элементы его реализации в языке ПРОЛОГ. Классические исчисления (высказываний и предикатов) и элементы неклассических логик: трёхзначные и многозначные логики, модальную, временную и нечеткую логики. Теорию алгоритмов: нормальные алгоритмы, машины Тьюринга, рекурсивные функции и их взаимосвязи. Понятие о сложности вычислений, различные (по сложности) классы задач и примеры таких задач.
Все главы снабжены контрольными вопросами и упражнениями, приведены варианты типовых заданий и тесты для самоконтроля усвоения материала.
Пособие предназначено студентам технических вузов по специальности 2201 направления «Информатика и вычислительная техника» и может быть использовано для специальности 2202 и других специальностей данного направления.
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ 7
Глава 1. ЛОГИКА ВЫСКАЗЫВАНИЙ 11
§ 1. Высказывание. Логические операции 11
§ 2. Пропозициональные буквы, связки и формы (формулы логики
высказываний). Построение таблиц истинности 15
§ 3. Упрощения в записях пропозициональных форм 17
§ 4. Тавтологии (общезначимые формулы). Противоречия 19
§ 5. Равносильность пропозициональных форм 21
§ 6. Важнейшие пары равносильных пропозициональных форм 22
§ 7. Зависимости между пропозициональными связками 23
§ 8. Нормальные формы 25
§ 9. Совершенные нормальные формы 28
§ 10. Булева (переключательная) функция 30
§ 11. Приложение алгебры высказываний к анализу и синтезу
контактных (переключательных) схем 31
§ 12. Приложение алгебры высказываний к анализу и синтезу схем
из функциональных элементов 33
§ 13. Вопросы и темы для самопроверки 36
§ 14. Упражнения 37
Глава 2. ЛОГИКА ПРЕДИКАТОВ 45
§ 1. Понятие предиката 45
§ 2. Кванторы 47
§ 3. Формулы логики предикатов 50
§ 4. Интерпретация. Модель 52
§ 5. Свойства формул в данной интерпретации 54
§ 6. Логически общезначимые формулы. Выполнимые и
равносильные формулы 56
§ 7. Правила перенесения отрицания через кванторы 57
§ 8. Правила перестановки кванторов 60
§ 9. Правила переименования связанных переменных 61
§ 10. Правила вынесения кванторов за скобки. Предваренная
нормальная форма 63
§ 11. Вопросы и темы для самопроверки 67
§ 12. Упражнения 67
Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ 77
§ 1. Логическое следствие и проблема дедукции в логике
высказываний 77
§ 2. Резольвента дизъюнктов логики высказываний 79
§ 3. Метод резолюции в логике высказываний 80
§ 4. Метод насыщения уровня 81
§ 5. Стратегия вычёркивания 83
§ 6. Лок-резолюция 84
§ 7. Метод резолюции для хорновских дизъюнктов 86
§ 8. Преобразование формул логики предикатов. Сколемовская
стандартная форма 87
§ 9. Унификация 90
§ 10. Метод резолюции в логике предикатов 93
§ 11. Приложение метода резолюций для анализа силлогизмов Аристотеля 95
§ 12. Использование метода резолюций в языке ПРОЛОГ 98
§ 13. Введение и использование правил в ПРОЛОГе 101
§ 14. Рекурсивное задание правил в ПРОЛОГе 102
§ 15. Особенности ПРОЛОГа 105
§ 16. Вопросы и темы для самопроверки 107
§ 17. Упражнения 108
Глава 4. ДЕДУКТИВНЫЕ ТЕОРИИ 113
§ 1. Понятие об эффективных и полуэффективных процессах
(методах) 113
§ 2. Дедуктивные теории 114
§ 3. Свойства дедуктивных теорий 116
§ 4. Пример полуформальной аксиоматической теории - геометрия 117
§ 5. Формальные аксиоматические теории 121
§ 6. Свойства выводимости 122
§ 7. Исчисление высказываний 123
§ 8. Некоторые теоремы исчисления высказываний 124
§ 9. Эквивалентность двух определений непротиворечивости 127
§ 10. Производные (доказуемые) правила вывода в исчислении
высказываний 128
§ 11. Свойства исчисления высказываний 130
§ 12. Другие аксиоматизации исчисления высказываний 136
§ 13. Теории первого порядка 137
§ 14. Формальная арифметика (теория S) 139
§ 15. Свойства теорий первого порядка 141
§ 16. Значение аксиоматического метода 144
§ 17. Теория естественного вывода 145
§ 18. Вопросы и темы для самопроверки 148
§ 19. Упражнения 149
Глава 5. НЕКЛАССИЧЕСКИЕ ЛОГИКИ 151
§ 1. Трёхзначные логики 151
§ 2. Многозначные логики 155
§ 3. Понятие нечёткого множества 157
§ 4. Нечёткие высказывания и максиминные операции над ними 162
§ 5. Понятие о нечёткой лингвистической логике 166
§ 6. Модальные логики 169
§ 7. Временные (темпоральные) логики 171
§ 8. Вопросы и темы для самопроверки 173
§ 9. Упражнения 173
Глава 6. ТЕОРИЯ АЛГОРИТМОВ 177
§ 1. Неформальное понятие алгоритма 177
§ 2. Алфавит, слова, алгоритм в алфавите. Вполне эквивалентные
алгоритмы 178
§ 3. Нормальный алгоритм (алгоритм А.А.Маркова) 179
§ 4. Функции частично вычислимые и вычислимые по Маркову 183
§ 5. Замыкание, распространение нормального алгоритма 184
§ 6. Операции над нормальными алгоритмами 185
§ 7. Машина Тьюринга 189
§ 8. Задание машины Тьюринга 191
§ 9. Алгоритм Тьюринга. Вычислимость по Тьюрингу 192
§ 10. Связь между машинами Тьюринга и нормальными алгоритмами 193
§ 11. Основная гипотеза теории алгоритмов (принцип нормализации
или тезис Черча) 196
§ 12. Проблема алгоритмической неразрешимости 197
§ 13. Примеры алгоритмически неразрешимых массовых проблем 200
§ 14. Сведения любого преобразования слов в алфавите к вычислению значений целочисленных функций 201
§ 15. Примитивно рекурсивные и общерекурсивные функции 203
§ 16. Примитивно рекурсивность некоторых функций. Частично рекурсивные функции 205
§ 17. Ламбда исчисление 207
§ 18. Основные результаты 210
§ 19. Вопросы и темы для самопроверки 211
§ 20. Упражнения 212
Глава 7. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ АЛГОРИТМОВ 221
§ 1. Понятие о сложности вычислений 221
§ 2. Временная сложность вычислений (алгоритма) 223
§ 3. Полиномиальные алгоритмы и задачи. Класс Р 225
§ 4. NP класс 228
§ 5. NP-полные и NP-трудные задачи 231
§ 6. Класс Е 232
§ 7. Емкостная (ленточная) сложность алгоритма 233
§ 8. Вопросы и темы для самопроверки 234
§ 9. Упражнения 235
ЛИТЕРАТУРА 237
ПРИЛОЖЕНИЯ 239
Варианты типового задания 239
Тесты для самоконтроля 250
Тест по логике высказываний (тест № 1) 250
Тест по логике предикатов (тест № 2) 251
Тест по логическому следствию и методу резолюций (тест № 3) 253
Тест по дедуктивным теориям (тест № 4) 254
Тест по теории алгоритмов (тест № 5) 257
Тест по неклассическим логикам и сложности вычислений (тест 259 № 6)
Ответы к тестам самоконтроля 262
