В пособии содержится материал основного курса «Введение в математическую логику», читаемого на механико-математическом факультете МГУ. Излагаются элементы теории множеств, основные понятия, относящиеся к семантике формализованных логико-математических языков 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
В учебном пособии содержится материал основного курса «Введение в математическую логику», читаемого на механико-математическом факультете МГУ. Излагаются элементы теории множеств, основные понятия, относящиеся к семантике формализованных логико-математических языков первого порядка, исчисление предикатов и теорема о его полноте, дается введение в т ...
Введение в математическую логику — В книге дается доступное для начинающего читателя и достаточно полное изложение основных разделов современной математической логики и многих ее приложений. Наряду с такими разделами, как логика высказываний, исчисление предикатов, формальная арифметика и теория алгоритмов, в ней освещены также теория моделе ...
В книге излагаются основные исчисления математической логики: исчисления высказываний и исчисления предикатов; основы теории моделей и теории алгоритмов, а также элементы неклассических логик.
Изложены темы, традиционно изучаемые в курсе математической логики и теории алгоритмов: алгебра логики и исчисление высказываний, логика и исчисление предикатов, формальные аксиоматические теории, теория алгоритмов и теория вычислительной сложности.
Данный материал НЕ НАРУШАЕТ авторские права никаких физических или юридических лиц. Если это не так - свяжитесь с администрацией сайта. Материал будет немедленно удален. Электронная версия этой публикации предоставляется только в ознакомительных целях. Для дальнейшего её использования Вам необходимо будет приобрести бумажный (электронный, аудио) вариант у правообладателей.
Название: 
Распечатать
