ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЙ
Интенсивное развитие математической логики в последнее время сопровождается увеличением ее роли в математике.
Одной из основных задач математической логики остается анализ оснований математики. Но в настоящее время она уже вышла из рамок этой задачи и оказала существенное влияние на развитие самой математики. Из ее идей возникло точное определение понятия алгоритма, что позволило решить многие вопросы, которые без этого оставались бы в принципе неразрешимыми. Возникший в математической логике аппарат нашел приложение в вопросах конструкций вычислительных машин и автоматических устройств.
Со времени выхода в свет первого издания настоящей книги прошло 14 лет. За это время задача ознакомления широкого круга математиков с основами математической логики стала еще более актуальной. В настоящей книге была сделана попытка дать по возможности доступное изложение основ математической логики. Этой задаче посвящены первые пять глав книги, составляющие ее основное содержание. Последняя, шестая, глава носит более специальный характер и уже не является столь элементарной. В ней рассматриваются методы теории доказательства, посредством которых решаются некоторые вопросы математической логики, возникающие в основном тексте книги.
ОГЛАВЛЕНИЕ
Предисловие ко второму изданию.............. 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). § 11. Рекурсивные предикаты (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). § 6. Некоторые леммы о регулярных формулах (353). § 7. Операции, двойственные операциям 1, 2, 3 (368). § 8. Свойства операций 1*, 2*, 3* (370). § 9. Регулярность формул, выводимых в арифметике (378). § 10. Непротиворечивость ограниченной арифметики (382). § 11. Независимость аксиомы полной индукции в арифметике (383). § 12. Усиленная теорема о независимости аксиомы полной индукции (385).
Предметный указатель...........•........397
Цена: 200руб.
