Предисловие................... 5 Введение...................... 9 Глава 1. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ....... 13 § 1. Множества и слова.............. 16 § 2. Язык исчисления высказываний......... 23 § 3, Система аксиом и правил вывода......... 27 § 4. Эквивалентность формул............ 34 § 5. Нормальные формы.............. 37 § 6. Семантика исчисления высказываний....... 45 § 7. Характенизация доказуемых формул...... 51 § 8. Исчисление высказываний гильбертовского типа... 55 § 9. Консервативные расширения исчислений...... 69 Глава 2. ТЕОРИЯ МНОЖЕСТВ............ 69 § 10. Предикаты и отображения........... 69 § 11. Частично упорядоченные множества........ 74 § 12. Фильтры булевой алгебры........... 83 § 13. Мощность множества............. 88 § 14. Аксиома выбора............... 96 Глава 3. ИСТИННОСТЬ НА АЛГЕБРАИЧЕСКИХ СИСТЕМАХ 103 § 15. Алгебраические системы...........103 § 16. Формулы сигнатуры 2-.............110 § 17. Теорема-компактности............ 119 Глава 4. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ.......... 127 § 18. Аксиомы и правила вывода........... 127 § 19. Эквивалентность формул........... 137 § 20. Нормальные формы.............. 141 § 21. Теорема о существовании модели........ 144 § 22. Исчисление предикатов гильбертовского типа.... 152 § 23. Чистое исчисление предикатов........... 157 Глава 5. ТЕОРИЯ МОДЕЛЕЙ.............1S3 § 24. Элементарная эквивалентность.........163 § 254 Аксиоматизируемые классы.......... § 26. Скулемовские функции..... ....... 181 § 27. Механизм совместности,........... 184 § 28. Счетная однородность й универсальность.....199 Глава 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
|