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

2-изд., испр. — М.: Наука, 1973. — 399 с. — (Математическая логика и основания математики).Петр Сергеевич Новиков (1901-1975) - один из создателей школы математической логики в СССР, академик АН СССР, лауреат Ленинской премии. Основные труды по теории множеств, математической логике, теории алгоритмов, теории групп.
В настоящей книге сделана попытка дать по возможности доступное изложение основ математической логики. Этой задаче посвящены первые пять глав книги, составляющие ее основное содержание (логика и исчисление высказываний, логика и исчисление предикатов, аксиоматическая арифметика). Последняя, шестая, глава носит более специальный характер, в ней рассматриваются методы теории доказательства, посредством которых решаются некоторые вопросы математической логики, возникающие в основном тексте книги.
Книга привлечет внимание всех занимающихся или интересующихся математической логикой, а также может быть использована как учебное пособие по курсу математической логики в университетах.Оглавление.
Предисловие ко второму изданию.
Введение.Алгебра высказываний.
Логические операции.
Равносильность формул.
Закон двойственности.
Проблема разрешения.
Представление произвольной двузначной функции посредством формул алгебры высказываний.
Совершенные нормальные формы.Исчисление высказываний.
Понятие формулы.
Определение выводимых формул.
Теорема дедукции.
Некоторые правила исчисления высказываний.
Монотонность.
Эквивалентные формулы.
Некоторые теоремы о выводимости.
Связь между формулами алгебры высказываний и исчисления высказываний.
Непротиворечивость исчисления высказываний.
Полнота исчисления высказываний.
Независимость аксиом исчисления высказываний.Логика предикатов.
Предикаты.
Кванторы.
Теоретико-множественный смысл предикатов.
Аксиомы.
Непротиворечивость и независимость аксиом.
Взаимно одназначное соответствие областей.
Изоморфизм областей и полнота систем аксиом.
Аксиомы натурального ряда.
Нормальные формулы и нормальные формы.
Проблема разрешения.
Логика предикатов с одной переменной.
Конечные и бесконечные области.
Разрешающие функции (функции Сколема).
Теорема Лёвенгейма.Исчисление предикатов.
Формулы исчисления предикатов.
Замена переменных в формулах.
Аксиомы исчисления предикатов.
Правила образования выводимых формул.
Непротиворечивость исчисления предикатов.
Полнота в узком смысле.
Некоторые теоремы исчисления предикатов.
Теорема дедукции.
Дальнейшие теоремы исчисления предикатов.
Эквивалентные формулы.
Закон двойственности.
Нормальные формы.
Дедуктивная эквивалентность.
Нормальные формулы Сколема.
Доказательство теоремы Сколема.
Теорема Мальцева.
Проблема полноты исчисления предикатов в широком смысле.
Замечание о формулах без кванторов.
Теорема Гёделя.
Система аксиом в исчислении предикатов.Аксиоматическая арифметика.
Термы. Расширенное исчисление предикатов.
Свойства предиката равенства и предметных, функций.
Отношение эквивалентности.
Теорема дедукции.
Аксиомы арифметики.
Примеры выводимых формул.
Рекурсивные термы.
Ограниченная арифметика.
Рекурсивные функции.
Аксиоматическая и содержательная выводимость свойств арифметических функций.
Рекурсивные предикаты.
Другие способы образования рекурсивных предикатов. Ограниченные кванторы.
Приемы образования новых рекурсивных термов.
Некоторые теоретико-числовые предикаты и термы.
Вычислимые функции.
Некоторые теоремы аксиоматической арифметики.Элементы теории доказательства.
Постановка вопроса о непротиворечивости и независимости аксиом.
Простые множители и простые слагаемые.
Примитивно истинные формулы.
Операции 1, 2, 3.
Регулярные формулы.
Некоторые леммы о регулярных формулах.
Операции 1*, 2*, 3*, двойственные операциям 1, 2 ,3.
Свойства операций 1*, 2*, 3*.
Регулярность формул, выводимых в арифметике.
Непротиворечивость ограниченной арифметики.
Независимость аксиомы полной индукции в арифметике.
Усиленная теорема о независимости аксиомы полной индукции.
Предметный указатель.