Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. — 2-е изд. — М., 2004. — 128 с.
В учебном пособии содержится материал основного курса «Введение в математическую логику», читаемого на механико-математическом факультете МГУ. Излагаются элементы теории множеств, основные понятия, относящиеся к семантике формализованных логико-математических языков первого порядка, исчисление предикатов и теорема о его полноте, дается введение в теорию алгоритмов и вычислимых функций.
Для студентов математических факультетов университетов, педагогических институтов, а также других вузов с углубленным изучением информатики и кибернетики.
ОГЛАВЛЕНИЕ
Введение..................................................................5
ГЛАВА 1 ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
§ 1. Основные понятия теории множеств.....................................6
§ 2. Бинарные отношения и функции..............................6
§ 3. Взаимно однозначные соответствия и эквивалентные множества..........9
§ 4. Счетные множества................................................10
§ 5. Канторовский диагональный метод....................................14
§ 6. Кардинальные числа, или мощности..................................14
§ 7. Теорема Кантора...................................................15
§ 8. Парадоксы теории множеств......................................16
§ 9. Аксиоматическая теория множеств................................17
ГЛАВА 2 ЯЗЫКИ ПЕРВОГО ПОРЯДКА
§ 1. Высказывания и высказывательные формы...........................19
§ 2. Логические операции.............................................21
§ 3. Логика высказываний............................................23
§ 4. Кванторы......................................................24
§5. Субъектно-предикатная структура предложений....................26
§ 6. Языки первого порядка......................................27
§ 7. Примеры языков первого порядка................................32
§ 8. Определение интерпретации....................................33
§ 9. Формальное определение истинности..........................35
§ 10. Общезначимые формулы, выполнимые формулы, равносильные формулы .....37
§11. Предваренные формулы..............................................42
§ 12. Истинность в конечных интерпретациях...............................44
§ 13. Изоморфизмы и элементарная эквивалентность......................46
§ 14. Выразимость. Доказательство невыразимости с помощью автоморфизмов ....50
ГЛАВА 3 ЭЛЕМЕНТЫ ТЕОРИИ ДОКАЗАТЕЛЬСТВ
§ 1. Аксиоматический метод......................................54
§ 2. Логическое следование...............
§ 3. Тавтологическое следствие......................................61
§ 4. Исчисление предикатов.............................................62
§ 5. Вывод из гипотез.............................................69
§ 6. Теории первого порядка..........................................72
§ 7. Формальная арифметика........................................... 76
ГЛАВА 4 ТЕОРЕМА ГЁДЕЛЯ О ПОЛНОТЕ
§ 1. Расширение теории...........................................79
§2. Каноническая интерпретация теории...............................81
§ 3. Доказательство теоремы о полноте...............................84
§ 4. Некоторые следствия теоремы Гёделя о полноте...................87
§ 5. Математические применения теоремы о полноте и ее следствий.....88
§ 6. Категоричность..............................................92
ГЛАВА 5 ТЕОРИЯ АЛГОРИТМОВ
§ 1. Вычислимые функции........................................... 93
§ 2. Разрешимые множества....................................... 95
§ 3. Полуразрешимые множества.......................................... 96
§ 4. Свойство пошагового выполнения алгоритма и его следствия......... 99
§ 5. Универсальная вычислимая функция................................. 104
§ 6. Перечислимость множества теорем.................................... 107
§ 7. Машины Тьюринга.................................................... 109
§ 8. Универсальная вычислимая по Тьюрингу функция................... 119
§ 9. Тезис Чёрча........................................................... 121
Список рекомендуемой литературы......................................... 122
Предметный указатель...................................................... 123
