В книге изложены основные классические исчисления математической логики: исчисление высказываний и исчисление предикатов; имеется краткое изложение основных понятий теории множеств и теории алгоритмов. Ряд разделов книги — теория моделей и теория доказательств — изложены более подробно, чем это предусмотрено программой. Для студентов математических специальностей вузов. Может служить пособием для специальных курсов.
Author(s): Ершов Ю.Л., Палютин Е.А.
Edition: 6-е
Publisher: Физматлит
Year: 2011
Language: Russian
Pages: 357
City: Москва
Tags: Математика;Математическая логика;
Предисловие к шестому изданию ......Page 6
Предисловие к первому изданию ......Page 7
Введение ......Page 9
§ 1.1. Множества и слова ......Page 14
§ 1.2. Язык исчисления высказываний ......Page 18
§ 1.3. Система аксиом и правил вывода ......Page 23
§ 1.4. Эквивалентность формул ......Page 30
§ 1.5. Нормальные формы ......Page 33
§ 1.6. Семантика исчисления высказываний ......Page 39
§ 1.7. Характеризация доказуемых формул ......Page 44
§ 1.8. Исчисление высказываний гильбертовского типа ......Page 47
§ 1.9. Консервативные расширения исчислений ......Page 51
§2.1. Предикаты и отображения ......Page 61
§2.2. Частично упорядоченные множества ......Page 66
§2.3. Фильтры булевой алгебры ......Page 76
§2.4. Мощность множества ......Page 81
§2.5. Ординалы и кардиналы ......Page 82
§2.6. Аксиоматическая теория множеств ZF и аксиома выбора ......Page 88
§3.1. Алгебраические системы ......Page 94
§3.2. Формулы сигнатуры Σ ......Page 100
§3.3. Теорема компактности ......Page 108
§4.1. Аксиомы и правила вывода ......Page 115
§4.2. Эквивалентность формул ......Page 123
§4.3. Нормальные формы ......Page 127
§4.4. Теорема о существовании модели ......Page 129
§4.5. Исчисление предикатов гильбертовского типа ......Page 136
§4.6. Чистое исчисление предикатов ......Page 140
§5.1. Элементарная эквивалентность ......Page 145
§5.2. Аксиоматизируемые классы ......Page 153
§5.3. Скулемовские функции ......Page 162
§5.4. Механизм совместности ......Page 164
§5.5. Счетная однородность и универсальность ......Page 176
§5.6. Категоричность ......Page 183
§5.7. RQ-формулы и Σ-формулы ......Page 192
§5.8. Формульная определимость ......Page 203
§ 5.9. Позитивные формулы и монотонные операторы ......Page 210
§6.1. Генценовская система G ......Page 216
§6.2. Обратимость правил ......Page 221
§6.3. Сравнение исчислений ИП^Σ и G ......Page 226
§6.4. Теорема Эрбрана ......Page 233
§6.5. Исчисления резольвент ......Page 246
§7.1. Понятие алгоритма ......Page 252
§7.2. Σ-предикаты и Σ-функции на Ω ......Page 253
§7.3. Σ-определимость истинности Σ-формул на Ω ......Page 266
§7.4. Универсальные Σ-предикаты, универсальные частичные Σ-функции ......Page 278
§ 7.5. Теорема Чёрча и теорема Гёделя о неполноте ......Page 284
§7.6. Машины Тьюринга ......Page 295
§7.7. Рекурсивные функции ......Page 298
§8.1. Разрешимость теории одноместных предикатов ......Page 301
§8.2. Элиминация кванторов и разрешимость теории алгебраически замкнутых полей ......Page 304
§8.3. Элиминация кванторов и разрешимость теории вещественно замкнутых полей ......Page 309
§8.4. Разрешимые теории абелевых групп ......Page 312
§8.5. Теории декартовых произведений ......Page 329
§8.6. Неразрешимые теории ......Page 333
Предметный указатель ......Page 344
Указатель обозначений ......Page 353
ОБ АВТОРАХ......Page 357
