Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления

Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления. М., 2002. 2-е издание, стереотипное. — 288 с.
Книга написана по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В ней рассказывается об основных понятиях математической логики (логика высказываний, языки первого порядка, выразимость, исчисление высказываний, разрешимые теории, теорема о полноте, начала теории моделей). Изложение рассчитано на учеников математических школ, студентов-математиков и всех интересующихся математической логикой. Книга включает в себя около 200 задач различной трудности.
Оглавление
Предисловие 5
1. Логика высказываний 9
1.1. Высказывания и операции....................9
1.2. Полные системы связок........................18
1.3. Схемы из функциональных элементов ... 25
2. Исчисление высказываний 47
2.1. Исчисление высказываний (ИВ)..............47
2.2. Второе доказательство теоремы о полноте 56
2.3. Поиск контрпримера и исчисление секвенций........................................63
2.4. Интуиционистская пропозициональная логика............................................69
3. Языки первого порядка 87
3.1. Формулы и интерпретации ..................87
3.2. Определение истинности......................93
3.3. Выразимые предикаты........................96
3.4. Выразимость в арифметике.........100
3.5. Невыразимые предикаты: автоморфизмы . 104
3.6. Элиминация кванторов............108
3.7. Арифметика Пресбургера..........119
3.8. Теорема Тарского-Зайденберга......123
3.9. Элементарная эквивалентность.......136
3.10. Игра Эренфойхта...............142
3.11. Понижение мощности.............149
4. Исчисление предикатов 156
4.1. Общезначимые формулы...........156
4.2. Аксиомы и правила вывода.........158
4.3. Корректность исчисления предикатов . . . 166
4.4. Выводы в исчислении предикатов......169
4.5. Полнота исчисления предикатов ......178
4.6. Переименование переменных ........188
4.7. Предварённая нормальная форма......191
4.8. Теорема Эрбрана...............195
4.9. Сколемовские функции............198
5. Теории и модели 203
5.1. Аксиомы равенства..............203
5.2. Повышение мощности.............206
5.3. Полные теории.................211
5.4. Неполные и неразрешимые теории.....225
5.5. Диаграммы и расширения..........234
5.6. Ультрафильтры и компактность......243
5.7. Нестандартный анализ............252
Литература 270
Предметный указатель 274
Указатель имён 284

Created using FlowPaper Flipbook Maker ↗