Введение в математическую логику

В книге Э.Мендельсона "Введение в математическую логику" даётся доступное для начинающего читателя и достаточно полное изложение основных разделов современной математической логики и многих её приложений. Наряду с такими разделами, как логика высказываний, исчисление предикатов, формальная арифметика и теория алгоритмов, в ней освещены также теория моделей и аксиоматическая теория множеств, отсутствующие в книге С.К. Клинин "Введение в математику", которая до настоящего времени служила наиболее полным пособием по математической логике. Следует однако отметить, что в отличие от книги С.К. Клини в этой книге по существу не затрагиваются интуиционистское и конструктивное направления математической логике. Изложение материала в книге ясное и лаконичное. Основной текст перемежается с большим числом примеров и упражнений. В упражнения автор вынес также некоторые результаты, используемые затем в основном тексте. Это, наряду с лаконичностью изложения, способствовало сокращению размеров книги [...]при весьма обширном содержании. открыть Оглавление От редактора перевода 5 Предисловие 6 Введение 7 Глава 1. Исчисление высказываний 19 § 1. Пропозициональные связки. Истинностные таблицы 19 § 2. Тавтологии 24 § 3. Полные системы связок 31 § 4. Система аксиом для исчисления высказываний 36 § 5. Независимость. Многозначные логики 46 § 6. Другие аксиоматизации 48 Глава 2. Теории первого порядка 53 § 1. Кванторы 53 § 2. Интерпретации. Выполнимость и истинность. Модели 57 § 3. Теории первого порядка 64 § 4. Свойства теорий первого порядка 67 § 5. Теоремы о полноте 71 § 6. Некоторые дополнительные метатеоремы 81 § 7. Правило С 83 § 8. Теории первого порядка с равенством 86 § 9. Введение новых функциональных букв и предметных констант 93 § 10. Предваренные нормальные формы 96 § 11. Изоморфизм интерпретаций. Категоричность теорий 102 § 12. Обобщенные теории первого порядка. Полнота и разреши- разрешимость 104 Глава 3. Формальная арифметика 115 § 1. Система аксиом 115 § 2. Арифметические функции и отношения 132 § 3. Примитивно рекурсивные и рекурсивные функции 135 § 4. Арифметизация. Геделевы номера 151 § 5. Теорема Гёделя для теории S 158 § 6. Рекурсивная неразрешимость. Теорема Тарского. Система Робинсона 167 Глава 4. Аксиоматическая теория множеств 177 § 1. Система аксиом 177 § 2. Порядковые числа 188 § 3. Равномощность. Конечные и счетные множества 199 § 4. Теорема Хартогса. Начальные порядковые числа. Арифметика порядковых чисел 207 § 5. Аксиома выбора. Аксиома ограничения 217 Глава 5. Эффективная вычислимость 228 § 1. Нормальные алгорифмы Маркова 228 S 2. Алгорифмы Тьюринга 251 § 3. Вычислимость по Эрбрану-Гёделю. Рекурсивно перечислимые множества 261 § 4. Неразрешимые проблемы 278 Дополнение. Доказательство непротиворечивости формальной арифметик и 282 Литература 296 Алфавитный указатель 310 Символы и обозначения 318 В книге Э.Мендельсона "Введение в математическую логику" даётся доступное для начинающего читателя и достаточно полное изложение основных разделов современной математической логики и многих её приложений. Наряду с такими разделами, как логика высказываний, исчисление предикатов, формальная арифметика и теория алгоритмов, в ней освещены также теория моделей и аксиоматическая теория множеств, отсутствующие в книге С.К. Клинин "Введение в математику", которая до настоящего времени служила наиболее полным пособием по математической логике. Следует однако отметить, что в отличие от книги С.К. Клини в этой книге по существу не затрагиваются интуиционистское и конструктивное направления математической логике. Изложение материала в книге ясное и лаконичное. Основной текст перемежается с большим числом примеров и упражнений. В упражнения автор вынес также некоторые результаты, используемые затем в основном тексте. Это, наряду с лаконичностью изложения, способствовало сокращению размеров книги при весьма обширном содержании. открыть [b]Оглавление От редактора перевода 5 Предисловие 6 Введение 7 [u] Глава 1. Исчисление высказываний [/u] 19 § 1. Пропозициональные связки. Истинностные таблицы 19 § 2. Тавтологии 24 § 3. Полные системы связок 31 § 4. Система аксиом для исчисления высказываний 36 § 5. Независимость. Многозначные логики 46 § 6. Другие аксиоматизации 48 [u] Глава 2. Теории первого порядка [/u]53 § 1. Кванторы 53 § 2. Интерпретации. Выполнимость и истинность. Модели 57 § 3. Теории первого порядка 64 § 4. Свойства теорий первого порядка 67 § 5. Теоремы о полноте 71 § 6. Некоторые дополнительные метатеоремы 81 § 7. Правило С 83 § 8. Теории первого порядка с равенством 86 § 9. Введение новых функциональных букв и предметных констант 93 § 10. Предваренные нормальные формы 96 § 11. Изоморфизм интерпретаций. Категоричность теорий 102 § 12. Обобщенные теории первого порядка. Полнота и разреши- разрешимость 104 [u]Глава 3. Формальная арифметика[/u] 115 § 1. Система аксиом 115 § 2. Арифметические функции и отношения 132 § 3. Примитивно рекурсивные и рекурсивные функции 135 § 4. Арифметизация. Геделевы номера 151 § 5. Теорема Гёделя для теории S 158 § 6. Рекурсивная неразрешимость. Теорема Тарского. Система Робинсона 167 [u] Глава 4. Аксиоматическая теория множеств [/u] 177 § 1. Система аксиом 177 § 2. Порядковые числа 188 § 3. Равномощность. Конечные и счетные множества 199 § 4. Теорема Хартогса. Начальные порядковые числа. Арифметика порядковых чисел 207 § 5. Аксиома выбора. Аксиома ограничения 217 [u]Глава 5. Эффективная вычислимость[/u] 228 § 1. Нормальные алгорифмы Маркова 228 S 2. Алгорифмы Тьюринга 251 § 3. Вычислимость по Эрбрану-Гёделю. Рекурсивно перечислимые множества 261 § 4. Неразрешимые проблемы 278 [u]Дополнение. Доказательство непротиворечивости формальной арифметик[/u] и 282 Литература 296 Алфавитный указатель 310 Символы и обозначения 318[/b]