ОГЛАВЛЕНИЕ
Предисловие................... 3
Введение..................... 9
Глава 1. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИИ....... 16
§ 1. Множества и слова.............. 16
§ 2. Язык исчисления высказываний......... 23
§ 3. Систем!! аксиом и правил вывода......... 27
§ 4. Эквивалентность формул............ 34
§ 5. Нормальные формы .............. 37
§ 6. Семантика исчисления высказываний . . . . . . .45
§ 7. Характеризация доказуемых формул....... 51
§'8. Исчисление высказываний гильбертовского типа . . . 55
§ 9. Консервативные расширения исчислений...... 6Э
Глава 2. ТЕОРИЯ МНОЖЕСТВ............ 69
§ 10. Предикаты и отображения........... 69
§ 11. Частично упорядоченные множества....... 74
§ 12. Фильтры булевой алгебры........... 83
§ 13. Мощность множества............. 88
§ 14. Аксиома выбора............... 96
Рлава 3. ИСТИННОСТЬ НА АЛГЕБРАИЧЕСКИХ СИСТЕМАХ ЮЗ
§ 15. Алгебраические системы............103
§ 16. Формулы сигнатуры S........... .110
§ 17. Теорема компактности........... . 119
Глава 4. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ.........127
§ 18. Аксиомы и правила вывода........... 127
§ 19. .Эквивалентность формул . ..........137
§ 20. Нормальные формы............. 141
§ 21. Теорема о существовании модели........144
§ 22. Исчисление предикатов гильбертовского типа . . . .152 § 23. Чистое исчисление предикатов • . . /......157,
Глава 5. ТЕОРИЯ МОДЕЛЕЙ............. 133
§ 24. Элементарная эквивалентность......... 163
§ 25, Аксиоматизируемые классы .......... !7Й
§ 26. Скулемовские функции............ 181
§ 27. Механизм совместности............ 184
§ 28. Счетная однородность и универсальность..... 199
§ 29, Категоричность , .... ( . i ....... 207
4 \ ОГЛАВЛЕНИЕ
\
Глава 6. ТЕОРИЯ ДОКАЗАТЕЛЬСТВ ..........217
§ 30. Генценовская система G........-. . . . 217
§ 31. Обратимость правил.............222
§ 32. Сравнение исчислений ИП2 и О.........231
§ 33. Теорема Эрбрана..............238
§ 34. Исчисления резольвент............247
Глава 7. АЛГОРИТМЫ И РЕКУРСИВНЫЕ ФУНКЦИИ ... 254 § 35. Нормальные алгорифмы и машины Тьюринга . . . 254
§ 36. Рекурсивные функции ............266
§ 37. Рекурсивно перечислимые предикаты.......284
§ 38. Неразрешимость исчисления предикатов и теорема Гё-
деля о неполноте.........•.....298
Предметный указатель.......,........ 314
Указатель обозначений ............... , 319
ПРЕДИСЛОВИЕ
Настоящая книга представляет собой си* стематическЪе изложение ряда разделов со-временной математической логики и теории алгоритмов. Написана она в целью использования ее в преподавании как в качестве учебника по математической логике для университетов, так и в качестве учебиого пособия при чтении спецкурсов.
Разделы, соответствующие обязательной программе (§§ 1—9 в главе 1 (без мелкого шрифта), §§ 10—11 в главе 2, §§ 15—-16 в главе 3, §§ 18—20, 22—23 в главе 4 и § 35 в главе 7), написаны более тщательно и подробно, чем разделы, относящиеся к более специальным вопросам.
Изложение исчисления высказываний и исчисления предикатов не является традиционным и начинается с изучения секвенциальных вариантов исчислений натурального вывода (хотя традиционные исчисления также появляются здесь под названием гильбертовских). Основанием к этому являются:
1) возможность хорошего объяснения смысла всех правил вывода;
2) возможность более быстрого приобретения навыка формальных доказательств;
3) практическая возможность проделать все необходимые в курсе формальные доказа* тельства для таких исчислений.
Цена: 150руб.
