От вътрешната страна на обложката:
В книге систематически излагаются классические исчисления высказываний и предикатов, а также формальная система арифметики. Затрагиваются различные вопросы, относящиеся к основаниям математики.
Книга предназначена для лиц, впервые знакомящихся с математической логикой, и не требует от читателя никакой специальной подготовки. Последняя глава, посвященная элементарному доказательству непротиворечивости некоторой ограниченной части классической арифметики методом автора, может представлять интерес и для специалистов.
Серия «Математическая логика и основания математики» состоит из публикаций, посвященных вопросам теории математического доказательства, теории алгоритмов, логическим исчислениям (классическим и конструктивным), истории математической логики и оснований математики, а также приложениям математической логики к вопросам автоматики и лингвистики. В серию входят монографии, обзорные работы и сборники статей на определенную тему, принадлежащие перу как отечественных, так и зарубежных ученых. Они носят различный характер: некоторые из них рассчитаны на широкий круг научных работников, преподавателей и студентов, между тем как другие имеют в виду более узкие круги специалистов разных профилей
*
ОГЛАВЛЕНИЕ
Предисловие ко второму изданию 7
Введение 9
Глава I. Алгебра высказываний 36
§ 1. Логические операции (36). § 2. Равносильность формул (41). § 3. Закон двойственности (47). § 4. Проблема разрешения (49). § 5. Представление произвольной двузначной функции посредством формул алгебры высказываний (56). § 6. Совершенные нормальные формы (59).
Глава II. Исчисление высказываний 66
§ 1. Понятие формулы (66). § 2. Определение выводимых формул (72). § 3. Теорема дедукции (80). § 4. Некоторые правила исчисления высказываний (83). § 5. Монотонность (87). § 6. Эквивалентные формулы (90). § 7. Некоторые теоремы о выводимости (98). § 8. Связь между формулами алгебры высказываний и исчисления высказываний (104). § 9. Непротиворечивость исчисления высказываний (107). § 10. Полнота исчисления высказываний (109). § 11. Независимость аксиом исчисления высказываний (111).
Глава III. Логика предикатов 123
§ 1. Предикаты (123). § 2. Кванторы (128). § 3. Теоретико-множественный смысл предикатов (132). § 4. Аксиомы (136). § 5. Непротиворечивость и независимость аксиом (139). § 6. Взаимно одназначное соответствие областей (142). § 7. Изоморфизм областей и полнота систем аксиом (145). § 8. Аксиомы натурального ряда (149). § 9. Нормальные формулы и нормальные формы (155). § 10. Проблема разрешения (159). § 11. Логика предикатов с одной переменной (160). § 12. Конечные и бесконечные области (168). § 13. Разрешающие функции (функции Сколема) (172). § 14. Теорема Лёвенгейма (178).
Глава IV. Исчисление предикатов 183
§ 1. Формулы исчисления предикатов (183). § 2. Замена переменных в формулах (190). § 3. Аксиомы исчисления предикатов (192). § 4. Правила образования выводимых формул (193). § 5. Непротиворечивость исчисления предикатов (202). § 6. Полнота в узком смысле (209). § 7. Некоторые теоремы исчисления предикатов (213). § 8. Теорема дедукции (216). § 9. Дальнейшие теоремы исчисления предикатов (221). § 10. Эквивалентные формулы (230). §. 11. Закон двойственности (235). § 12. Нормальные формы (239). § 13. Дедуктивная эквивалентность (243). § 14. Нормальные формулы Сколема (244). § 15. Доказательство теоремы Сколема (251). § 16. Теорема Мальцева (253). § 17. Проблема полноты исчисления предикатов в широком смысле (261). § 18. Замечание о формулах без кванторов (262). § 19. Теорема Гёделя (264). § 20. Система аксиом в исчислении предикатов (273).
Глава V. Аксиоматическая арифметика 280
§ 1. Термы. Расширенное исчисление предикатов (280). § 2. Свойства предиката равенства и предметных функций (283). § 3. Отношение эквивалентности (287). § 4. Теорема дедукции (289). § 5. Аксиомы арифметики (290). § 6. Примеры выводимых формул (292). § 7. Рекурсивные термы (296). § 8. Ограниченная арифметика (298). § 9. Рекурсивные функции (303). § 10. Аксиоматическая и содержательная выводимость свойств арифметических функций (305). § П. Рекурсивные предикаты (310). § 12. Другие способы образования рекурсивных предикатов. Ограниченные кванторы (312). § 13. Приемы образования новых рекурсивных термов (314). § 14. Некоторые теоретико-числовые предикаты и термы (318). § 15. Вычислимые функции (322). § 16. Некоторые теоремы аксиоматической арифметики (327).
Глава VI. Элементы теории доказательства 335
§ 1. Постановка вопроса о непротиворечивости и независимости аксиом (335). § 2. Простые множители и простые слагаемые (337). § 3. Примитивно истинные формулы (338). § 4. Операции 1, 2, 3 (342). § 5. Регулярные формулы (345). § 0. Некоторые леммы о регулярных формулах (353). §. 7. Операции, двойственные операциям 1, 2, 3 (368). § 8. Свойства операций 1*, 2*, 3* (370). § 9. Регулярность формул, выводимых в арифметике (378). § 10. Непротиворечивость ограниченной арифметики (382). § 11. Независимость аксиомы полной индукции в арифметике (383). § 12. Усиленная теорема о независимости аксиомы полной индукции (385).
Предметный указатель 397
*
ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ
Интенсивное развитие математической логики в последнее время сопровождается увеличением ее роли в математике.
Одной из основных задач математической логики остается анализ оснований математики. Но в настоящее время она уже вышла из рамок этой задачи и оказала существенное влияние на развитие самой математики.-Из ее идей возникло точное определение понятия алгоритма, что позволило решить многие вопросы, которые без этого оставались бы в принципе неразрешимыми. Возникший в математической логике аппарат нашел приложение в вопросах конструкций вычислительных машин и автоматических устройств.
Со времени выхода в свет первого издания настоящей книги прошло 14 лет. За это время задача ознакомления широкого круга математиков с основами математической логики стала еще более актуальной. В настоящей книге была сделана попытка дать по возможности доступное изложение основ математической логики. Этой задаче посвящены первые пять глав книги, составляющие ее основное содержание. Последняя, шестая, глава носит более специальный характер и уже не является столь элементарной. В ней рассматриваются методы теории доказательства, посредством которых решаются некоторые вопросы математической логики, возникающие в основном тексте книги.
Настоящее издание по содержанию не отличается от первого издания. В нем исправлены опечатки и заменены устаревшие термины. В частности, удален термин «истинная в данном исчислении формула», который в первом издании использовался как синоним термина «выводимая в данном исчислении формула». Таким образом, исключена возможность смешения этого понятия с содержательной истинностью формул.
Книга не претендует на полноту освещения всех раз-вивающихся в настоящее время важных направлений в математической логике. Некоторые из этих направлений не затронуты вовсе.
С разделами математической логики, которые не отражены в настоящей книге, читатель сможет ознакомиться по книгам:
С. К. Клин и, Введение в метаматематику, ИЛ, 1957.
А. И. Мальцев, Алгоритмы и рекурсивные функции, «Наука», 1965.
А. А. Марков, Теория алгорифмов, Труды Матем. ин-та АН СССР им. В. А. Стеклова, Изд-во АН СССР, 1954.
Э. Мендельсон, Введение в математическую логику, «Наука», 1971.
П. С. Новиков
