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