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

Изложение рассчитано на учеников математических школ, студентов-математиков и всех интересующихся математической логикой. Книга включает в себя около 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



Читать онлайн
скачать бесплатно


Теги:
теория алгоритмов, Верещагин математическая логика, конспект лекций по математической логике

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