Успенский В. А. и др. Вводный курс математической логики ОНЛАЙН


Для студентов математических факультетов университетов, педагогических институтов, а также других вузов с углубленным изучением информатики и кибернетики.
ОГЛАВЛЕНИЕ
Введение…………………………………………………………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



Читать онлайн
скачать бесплатно


Теги:
Математическая логика, Успенский математическая логика

Коментарі до Успенский В. А. и др. Вводный курс математической логики ОНЛАЙН