Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики

Учебное пособие. — М.: Физматлит, 2004. — 128 с. — ISBN 5-9221-0278-8.В пособии содержится материал основного курса «Введение в математическую логику», читаемого на механико-математическом факультете МГУ.
Излагаются элементы теории множеств, основные понятия, относящиеся к семантике формализованных логико-математических языков 1-го порядка, исчисление предикатов и теорема о его полноте, дается введение в теорию алгоритмов и вычислимых функций.
Для студентов математических факультетов университетов, педагогических институтов, а также вузов с углубленным изучением информатики и кибернетики.Введение.
Элементы теории множеств.
Основные понятия теории множеств.
Винарные отношения и функции.
Взаимно однозначные соответствия и эквивалентные множества.
Счетные множества.
Канторовскии диагональныи метод.
Кардинальные числа, или мощности.
Теорема Кантора.
Парадоксы теории множеств.
Аксиоматическая теория множеств.
Языки первого порядка.
Высказывания и высказывательные формы.
Логические операции.
Логика высказываний.
Кванторы.
Субъектно- предикатная структура предложений.
Языки первого порядка.
Примеры языков первого порядка.
Определение интерпретации.
Формальное определение истинности.
Общезначимые формулы, выполнимые формулы, равносильные формулы.
Предваренные формулы.
Истинность в конечных интерпретациях.
Изоморфизмы и элементарная эквивалентность.
Выразимость. Доказательство невыразимости с помощью автоморфизмов.
Элементы теории доказательств.
Аксиоматический метод.
Логическое следование.
Тавтологическое следствие.
Исчисление предикатов.
Вывод из гипотез.
Теории первого порядка.
Формальная арифметика.
Теорема Гёделя о полноте.
Расширение теории.
Каноническая интерпретация теории.
Доказательство теоремы о полноте.
Некоторые следствия теоремы Гёделя о полноте.
Математические применения теоремы о полноте и ее следствий.
Категоричность.
Теория алгоритмов.
Вычислимые функции.
Разрешимые множества.
Полуразрешимые множества.
Свойство пошагового выполнения алгоритма и его следствия.
У ниверсальная вычислимая функция.
Перечислимость множества теорем.
Машины Тьюринга.
Универсальная вычислимая по Тьюрингу функция.
Тезис Чёрча.
Список рекомендуемой литературы.
Предметный указатель.