Лекции по математической логике и теории алгоритмов

Description

https://www.mccme.ru/shen/Книга написана по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В ней рассказывается об основных понятиях математической логики (логика высказываний, языки первого порядка, выразимость, исчисление высказываний, разрешимые теории, теорема о полноте, начала теории моделей). Изложение рассчитано на учеников математических школ, студентов-математиков и всех интересующихся математической логикой. Книга содержит около 200 задач различной трудности. Предыдущее издание книги вышло в 2012 г. https://www.mccme.ru/shen/ Предисловие 1. Логика высказываний 1.1. Высказывания и операции 1.2. Полные системы связок 1.3. Схемы из функциональных элементов 2. Исчисление высказываний 2.1. Исчисление высказываний (ИВ) 2.2. Второе доказательство теоремы о полноте 2.3. Поиск контрпримера и исчисление секвенций 2.4. Интуиционистская пропозициональная логика 3. Языки первого порядка 3.1. Формулы и интерпретации 3.2. Определение истинности 3.3. Выразимые предикаты 3.4. Выразимость в арифметике 3.5. Невыразимые предикаты: автоморфизмы 3.6. Элиминация кванторов 3.7. Арифметика Пресбургера 3.8. Теорема Тарского--Зайденберга 3.9. Элементарная эквивалентность 3.10. Игра Эренфойхта 3.11. Понижение мощности 4. Исчисление предикатов 4.1. Общезначимые формулы 4.2. Аксиомы и правила вывода 4.3. Корректность исчисления предикатов 4.4. Выводы в исчислении предикатов 4.5. Полнота исчисления предикатов 4.6. Переименование переменных 4.7. Предварённая нормальная форма 4.8. Теорема Эрбрана 4.9. Сколемовские функции 5. Теории и модели 5.1. Аксиомы равенства 5.2. Повышение мощности 5.3. Полные теории 5.4. Неполные и неразрешимые теории 5.5. Диаграммы и расширения 5.6. Ультрафильтры и компактность 5.7. Нестандартный анализ Литература Предметный указатель Указатель имён