Петр Сергеевич Новиков (1901-1975) - один из создателей школы
математической логики в СССР, академик АН СССР, лауреат Ленинской
премии. Основные труды по теории множеств, математической логике,
теории алгоритмов, теории групп.
В настоящей книге сделана попытка дать по возможности доступное изложение основ математической логики. Этой задаче посвящены первые пять глав книги, составляющие ее основное содержание (логика и исчисление высказываний, логика и исчисление предикатов, аксиоматическая арифметика). Последняя, шестая, глава носит более специальный характер, в ней рассматриваются методы теории доказательства, посредством которых решаются некоторые вопросы математической логики, возникающие в основном тексте книги.
Книга привлечет внимание всех занимающихся или интересующихся математической логикой, а также может быть использована как учебное пособие по курсу математической логики в университетах.
ИЗДАНИЕ ВТОРОЕ, ИСПРАВЛЕННОЕ
ИЗДАТЕЛЬСТВО «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
МОСКВА 1973
ОГЛАВЛЕНИЕ
Предисловие ко второму изданию. 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). §. П. Закон двойственности (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).
Предметный указатель
В настоящей книге сделана попытка дать по возможности доступное изложение основ математической логики. Этой задаче посвящены первые пять глав книги, составляющие ее основное содержание (логика и исчисление высказываний, логика и исчисление предикатов, аксиоматическая арифметика). Последняя, шестая, глава носит более специальный характер, в ней рассматриваются методы теории доказательства, посредством которых решаются некоторые вопросы математической логики, возникающие в основном тексте книги.
Книга привлечет внимание всех занимающихся или интересующихся математической логикой, а также может быть использована как учебное пособие по курсу математической логики в университетах.
ИЗДАНИЕ ВТОРОЕ, ИСПРАВЛЕННОЕ
ИЗДАТЕЛЬСТВО «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
МОСКВА 1973
ОГЛАВЛЕНИЕ
Предисловие ко второму изданию. 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). §. П. Закон двойственности (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).
Предметный указатель