Новиков П.С. Элементы математической логики

Новиков П.С. Элементы математической логики. - М., 1973, 400 с.
В настоящей книге сделана попытка дать по возможности доступное изложение основ математической логики. Этой задаче посвящены первые пять глав книги, составляющие ее основное содержание (логика и исчисление высказываний, логика и исчисление предикатов, аксиоматическая арифметика). Последняя, шестая, глава носит более специальный характер, в ней рассматриваются методы теории доказательства, посредством которых решаются некоторые вопросы математической логики, возникающие в основном тексте книги.
ОГЛАВЛЕНИЕ
Предисловие ко второму изданию.............. 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. Аксиомы П36). § 5. Непротиворечивость и независимость аксиом (139). § 6. Взаимно одназначное соответствие областей (142). § 7. Изоморфизм областей и полнота систем аксиом (145). § 8. Аксиомы натурального ряда (149). § 9. Нормальные формулы и нормальные формы (155). § 10. Проблема разрешения (159). § П. Логика предикатов с одной переменной (160). § 12. Конечные и бесконечные области (168). § 13. Разрешающие функции (функции Сколема) (172). § 14. Теорема Лёвенгейма (178).
Глава IV. Исчисление предикатов............183
§ Формулы исчислёния предикатов (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

Created using FlowPaper Flipbook Maker ↗