Книга известных американских математиков, являющаяся в настоящее время одной из наиболее известных в США книг по математической логике, выдержавшая там три издания (1974, 1980, 1989 гг.). В ней содержатся начала и некоторые дополнительные главы математической логики, последовательно и строго излагаются классические теоремы о неразрешимости логики предикатов и разрешимости некоторых ее фрагментов, знаменитые теоремы Гёделя о полноте, нестандартные модели и многое другое. Материал дополнен упражнениями.
Для всех, кто интересуется математической логикой, а также информатикой, философией и лингвистикой.
Author(s): Булос Дж., Джеффри Р.
Publisher: Мир
Year: 1994
Language: Russian
Pages: 396
City: Москва
Предисловие редактора перевода ......Page 6
Предисловие ......Page 10
Предисловие к третьему изданию ......Page 12
Гл. 1. Счетность ......Page 13
Гл. 2. Диагонализация ......Page 26
Гл. 3. Машины Тьюринга ......Page 37
Гл. 4. Невычислимость в контексте проблемы усердного бобра ......Page 56
Гл. 5. Неразрешимость в контексте диагонализации ......Page 67
Гл. 6. Функции, вычислимые на абаке, вычислимы по Тьюрингу ......Page 79
Гл. 7. Рекурсивные функции вычислимы на абаках ......Page 101
Гл. 8. Вычислимые по Тьюрингу функции рекурсивны ......Page 124
Гл. 9. Логика первого порядка: напоминание ......Page 132
Гл. 10. Логика первого порядка неразрешима ......Page 153
Гл. 11. Формализация логики первого порядка: выводы и корректность ......Page 168
Гл. 12. Полнота формализации; компактность ......Page 181
Гл. 13. Теорема Лёвенгейма-Сколема ......Page 201
Гл. 14. Представимость в Q ......Page 214
Гл. 15. Неразрешимость, неопределимость и полнота ......Page 229
Гл. 16. Предикаты доказуемости и недоказуемость непротиворечивости ......Page 243
Гл. 17. Нестандартные модели арифметики ......Page 254
Гл. 18. Логика второго порядка ......Page 262
Гл. 19. Об определимой арифметической истине ......Page 275
Гл. 20. Определимость в арифметике и вынуждение ......Page 282
Гл. 21. Разрешимость арифметики со сложением, но без умножения ......Page 291
Гл. 22. Диадическая логика неразрешима: элиминация имен и функциональных символов ......Page 301
Гл. 23. Интерполяционная лемма Крейга ......Page 309
Гл. 24. Два применения леммы Крейга ......Page 320
Гл. 25. Монадическая логика в сравнении с диадической ......Page 329
Гл. 26. Теорема Рамсея ......Page 341
Гл. 27. Доказуемость, рассматриваемая средствами модальной логики ......Page 351
Гл. 28. Неразрешимые предложения ......Page 372
Гл. 29. Нестандартные модели теории Z нерекурсивны ......Page 380
Именной указатель ......Page 389
Предметный указатель ......Page 390
