Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

§ 19. Теория естественного вывода 137 § 20. Приложения дедуктивных теорий 140 Вопросы и темы для самопроверки 142 Упражнения 143 ГЛАВА 5. ТЕОРИЯ АЛГОРИТМОВ 146 § 1. Неформальное понятие алгоритма 146 § 2. Алфавит, слова, алгоритм в алфавите. Вполне эквивалентные ал­ горитмы 147 § 3. Нормальный алгоритм (алгоритм А.А.Маркова) 14 8 § 4. Функции частично вычислимые и вычислимые по Маркову 15 1 § 5. Замыкание, распространение нормального алгоритма 152 § 6. Операции над нормальными алгоритмами 15 3 § 7. Машина Тьюринга 157 § 8. Задание машины Тьюринга 159 § 9. Алгоритм Тьюринга. Вычислимость по Тьюрингу 16 0 § 10. Связь между машинами Тьюринга и нормальными алгоритмами 1 61 §11. Основная гипотеза теории алгоритмов (принцип нормализации ^ или тезис Черча) § 12. Проблема алгоритмической неразрешимости 165 § 13. Примитивно рекурсивные и обш,ерекурсивные функции 16 9 § 14. Примитивно рекурсивность некоторых функций. Частично р е­ курсивные функции 170 § 15. Ламбда-исчисление 173 § 17. Основные результаты 176 Вопросы и темы для самопроверки 178 Упражнения 178 Глава 6. НЕКЛАССИЧЕСКИЕ ЛОГИКИ 187 § 1. Трёхзначные логики 187 § 2. Многозначные логики 190 § 3. Понятие нечёткого подмножества 192 § 4. Нечёткая логика 197 § 5. Обобш,ения операций отрицания, конъюнкции, дизъюнкции и импликации 200 § 6. Понятие о нечёткой лингвистической логике 202 § 7. Модальные логики 205 § 8. Модели Кринке 208 § 9. Временные (темпоральные) логики 209 § 10. Приложения неклассических логик 212 263