Ершов Ю.Л., Палютин Е.А.Математическая логика: Учеб. пособие для вузов. - М., 1987. - 336 с.
В книге изложены основные классические исчисления математической логики: исчисление высказываний и исчисление предикатов; имеется краткое изложение основных понятий теории множеств и теории алгоритмов. Ряд разделов книги — теория моделей и теория доказательств — изложены более подробно, чем это предусмотрено программой.
Для студентов математических специальностей вузов. Может служить пособием для спецкурсов.
ОГЛАВЛЕНИЕ
Предисловие ко второму изданию 5
Предисловие к первому изданию................6
Введение 9
Глава 1. Исчисление высказываний......15
§ 1. Множества и слова.........15
§ 2. Язык исчисления высказываний......22
§ 3. Система аксиом и правил вывода.....25
§ 4. Эквивалентность формул........32
§ 5. Нормальные формы .........36
§ 6. Семантика исчисления высказываний .... 43
§ 7. Характеризация доказуемых формул .... 48
§ 8. Исчисление высказываний гильбертовского типа ...... 52
§ 9. Консервативные расширения исчислений ........ 56
Глава 2. Теория множеств . . .......65
§ 10. Предикаты и отображения .......65
§ 11. Частично упорядоченные множества .... 70
§ 12. Фильтры булевой алгебры.......78
§ 13. Мощность множества .........82
§ 14. Аксиома выбора .........90
Глава 3. Истинность на алгебраических системах ... 96
§ 15. Алгебраические системы.......96
§ 16. Формулы сигнатуры........103
§ 17. Теорема компактности........111
Глава 4. Исчисление предикатов..........119
§ 18. Аксиомы и правила вывода.......119
§ 19. Эквивалентность формул.......128
§ 20. Нормальные формы . .......132
§ 21. Теорема о существовании модели.....135
§ 22. Исчисление предикатов гильбертовского типа .......142
§ 23. Чистое исчисление предикатов .......... 147
Глава 5. Теория моделей.........152
§ 24. Элементарная эквивалентность......152
§ 25. Аксиоматизируемые классы.......161
§ 26. Скулемовские функции........169
§ 27. Механизм совместности........172
§ 28. Счетная однородность и универсальность .......... 186
§ 29. Категоричность 193
Глава 6. Теория доказательств........204
§ 30. Генценовская система G.......204
§ 31. Обратимость правил .........209
§ 32. Сравнепие исчислений ИП2 и G.....214
§ 33. Теорема Эрбрана..........222
§ 34. Исчисления резольвент........233
Глава 7. Алгоритмы и рекурсивные функции ...... 241
§ 35. Нормальные алгорифмы и машины Тьюринга ..... 241
§ 36. Рекурсивные функции ....... 251
§ 37. Рекурсивно перечислимые предикаты ....... 268
§ 38. Неразрешимость исчисления предикатов и теорема
Гёделя о неполноте . .......281
§ 39. Разрешимые теории.........296
§ 40. Неразрешимые теории........318
Предметный указатель .............335
