Клини С.К. Математическая логика. - М., 1973.- 480 с.
Имя одного из крупнейших современных специалистов в области математической логики С. К. Клини знакомо по русскому переводу его фундаментального труда «Введение в метаматематику» (ИЛ, 1957), ставшего настольной книгой для всех, кто занимается математической логикой, рекурсивными, функциями и основаниями математики. Данная книга представляет собой существенно усовершенствованный, расширенный и приближенный к нуждам университетского преподавания вариант «чисто логической» части этой всемирно известной монографии. Тщательно продуманные иллюстративные упражнения помогают читателю усвоить излагаемый, материал.Книга может быть использована,как учебное пособие по курсу математической логики в университетах и пединститутах; таким образом, она адресована прежде всего преподавателям, аспирантам и студентам.
ОГЛАВЛЕНИЕ
Предисловие к русскому изданию..................5
Предисловие.................................7
Часть I. ЭЛЕМЕНТАРНАЯ МАТЕМАТИЧЕСКАЯ ЛОГИКА
Глава I. Исчисление высказываний.........................11
§ 1. Лингвистические соображения; формулы..................11
§ 2. Теория моделей; таблицы истинности, общезначимость ......17
§ 3. Теория моделей; правило подстановки, совокупность общезначимых формул........................................23
§ 4. Теория моделей; импликация и эквивалентность..........28
§ 5. Теория моделей; цепи эквивалентностей..................31
§ 6. Теория моделей; двойственность.............- 34
§ 7. Теория моделей; отношение следования..................37
§ 8. Теория моделей; сокращенные таблицы истинности .... 41
§ 9. Теория доказательств; доказуемость и выводимость .... 46
§ 10. Теория доказательств; теорема о дедукции................54
§11. Теория доказательств; непротиворечивость, правила введения и удаления..........................................58
§ 12. Теория доказательств; полнота ..........................61
§ 13. Теория доказательств; употребление выводимых правил .... 67
§ 14. Применения к естественному языку; анализ рассуждений .... 76
§ 15. Применения к естественному языку; неполные рассуждения ... 86
Глава II. Исчисление предикатов..............................93
§ 16. Лингвистические соображения; формулы, свободные и связанные вхождения переменных............................93
§ 17. Теория моделей; предметные области, общезначимость ..... 104
§ 18. Теория моделей; основные результаты об общезначимости ..... 116
§ 19. Теория моделей; дальнейшие результаты об общезначимости.... 120
§ 20. Теория моделей; следование..............................126
§ 21. Теория доказательств; доказуемость и выводимость . . . 132
§ 22. Теория доказательств; теорема о дедукции.......138
§ 23. Теория доказательств; непротиворечивость, правила введения и удаления.......143
§ 24. Теория доказательств; замена, цепи эквивалентностей . . 148
§ 25. Теория доказательств; изменения кванторов, предваренная форма ...............153
§ 26. Применения к естественному языку; множества, аристотелевские категорические силлогизмы......................162
§ 27. Применения к естественному языку; еще о переводе слов символами ..............170
Глава III. Исчисление предикатов с равенством................177
§ 28. Функции, термы . ............................177
§ 29. Равенство ....................................180
§ 30. Равенство как эквивалентность; экстенсиональность ...... 188
§ 31. Описательные определения . . ....................199
Часть II. МАТЕМАТИЧЕСКАЯ ЛОГИКА И ОСНОВАНИЯ МАТЕМАТИКИ
Глава IV. Основания математики..............................206
§ 32. Счетные множества......................................206
§ 33. Канторовский диагональный метод ................212
§ 34. Абстрактные множества..................................216
§ 35. Парадоксы...................................221
§ 36. Математика аксиоматическая и математика интуитивная ....228
§ 37. Формальные системы, метаматематика....................237
§ 38. Формальная арифметика................................242
§ 39. Некоторые другие формальные системы....... .259
Глава V. Вычислимость и разрешимость........................270
§ 40. Разрешающие и вычислительные процедуры..............270
§ 41. Машина Тьюринга, тезис Чёрча..........................280
§ 42. Теорема Чёрча (в терминах машин Тьюринга)............291
§ 43. Применения к формальной арифметике; неразрешимость
(теорема Чёрча) и неполнота- (теорема Гёделя)............297
§ 44. Применения к формальной арифметике; доказательства непротиворечивости (вторая теорема Гёделя)................306
§ 45. Применения к исчислению предикатов (Чёрч, Тьюринг) .... 312
§ 46. Степени неразрешимости (Пост), иерархии (Клини, Мостовский)....................318
§ 47. Теоремы о неразрешимости и неполноте, использующие лишь простую непротиворечивость (Россер) ........327
Глава VI. Исчисление предикатов (дополнительные разделы) ...... 339
§ 48. Теорема Гёделя о полноте; введение......................339
§ 49. Теорема Гёделя о полноте; основной результат............353
§ 50. Теорема Гёделя о полноте для формальных систем генце-
новского типа; теорема Лёвенгейма—Скулема............365
§ 51. Теорема Гёделя о полноте для формальных систем гильбертовского типа ..........373
§ 52. Теорема Гёделя о полноте и теорема Лёвенгейма—Скулема
для исчисления предикатов с равенством..................376
§ 53. Парадокс Скулема и нестандартные модели арифметики ...... 383
§ 54. Теорема Генцена..........................................394
§ 55. Перестановочность;' теорема Эрбрана......................404
§ 56. Интерполяционная теарема Крейга ......................418
§ 57. Теорема Бета об определимости; теорема Робинсона о непротиворечивости .............432
Приложения. Г. Е. Минц
Приложение 1. Нормализация доказательств . . ...............442
Приложение 2. Функциональная форма. Теорема Эрбрана для непредваренных формул............448
Список литературы...... ............................451
Список теорем и лемм.........................466
Список постулатов............................................467
Символы и обозначения ........................468
Авторский и предметный указатель........................470
