Название: Вводный курс математической логики
Автор: Успенский В.А., Верещагин Н.К., Плиско В.Е.
Издательство: М.: Физматлит
Год: 2004
Страниц: 128
ISBN: 5-9221-0278-8
Формат: PDF
Размер: 10.7 Мб
Язык: русский

В пособии содержится материал основного курса «Введение в математическую логику», читаемого на механико-математическом факультете МГУ. Излагаются элементы теории множеств, основные понятия, относящиеся к семантике формализованных логико-математических языков 1-го порядка, исчисление предикатов и теорема о его полноте, дается введение в теорию алгоритмов и вычислимых функций.
Для студентов математических факультетов университетов, педагогических институтов, а также вузов с углубленным изучением информатики и кибернетики.





Оглавление

Введение ... 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. Теории первого порядка
§ 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

Скачать Вводный курс математической логики