Игошин В.И. Математическая логика и теория алгоритмов : учеб. пособие для студ. высш. учеб. заведений / В. И. Игошин. — 2-е изд., стер. — М., 2008. — 448 с.
Предлагаемое учебное пособие составляет основу комплекта по курсу математической логики и теории алгоритмов, в который также входит сборник задач (Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов). Подробно изложены основы теории, показаны направления проникновения логики в основания алгебры, анализа, геометрии, привлечен материал школьного курса математики для его логического анализа, охарактеризованы взаимосвязи математической логики с компьютерами, информатикой, системами искусственного интеллекта. Для студентов университетов, технических и педагогических вузов, обучающихся по специальностям «Математика», «Прикладная математика».
Оглавление
Предисловие......................................................3
Введение. Математическая логика в системе современного образования..............6
Логика и интуиция (6). Логика традиционная и математическая логика (7). Немного истории. Математическая логика — логика или математика? Математическая логика в обучении математике. Математическая логика и современные ЭВМ
Глава I. Алгебра высказываний...............................................................15
§ 1. Высказывания и операции над ними.............................................15
Понятие высказывания. Отрицание высказывания. Конъюнкция двух высказываний. Дизъюнкция двух высказываний. Импликация двух высказываний. Эквивалентность двух высказываний. Союзы языка и логические операции (язык и логика). Общий взгляд на логические операции
§ 2. Формулы алгебры высказываний...................................................23
Конструирование сложных высказываний. Понятие формулы алгебры высказываний. Логическое значение составного высказывания. Составление таблиц истинности для формул. Классификация формул алгебры высказываний. Мышление и математическая логика
§ 3. Тавтологии алгебры высказываний...............................................33
О значении тавтологий. Основные тавтологии. Основные правила получения тавтологий
§ 4. Логическая равносильность формул..............................................39
Понятие равносильности формул. Признак равносильности формул. Примеры равносильных формул. Равносильные преобразования формул. Равносильности в логике и тождества в алгебре
§ 5. Нормальные формы для формул алгебры высказываний............45
Понятие нормальных форм. Совершенные нормальные формы. Представление формул алгебры высказываний совершенными дизъюнктивными нормальными (СДН) формами. Представление формул алгебры высказываний совершенными конъюнктивными нормальными (СКН) формами. Два способа приведения формулы алгебры высказываний к совершенной нормальной форме
§ 6. Логическое следование формул.....................................................53
Понятие логического следствия. Признаки логического следствия. Два свойства логического следования. Следование и равносильность формул. Правила логических умозаключений. Еще один способ проверки логического следования. Нахождение следствий из данных посылок. Нахождение посылок для данного следствия
§ 7. Приложение алгебры высказываний к логико-математической практике......................64
Прямая и обратная теоремы. Необходимые и достаточные условия. Противоположная и обратная противоположной теоремы. Закон контрапозиции. Мо-
дификация структуры математической теоремы. Методы доказательства математических теорем. Дедуктивные и индуктивные умозаключения. Правильные и неправильные дедуктивные умозаключения. Решение логических задач. Принцип полной дизъюнкции. Одно обобщение принципа полной дизъюнкции
Глава II. Булевы функции........................................................................89
§ 8. Множества, отношения, функции.................................................89
Понятие множества. Включение и равенство множеств. Операции над множествами. Бинарные отношения и функции. Понятие n-арного отношения
§ 9. Булевы функции от одного и двух аргументов.............................93
Происхождение булевых функций. Булевы функции от одного аргумента. Булевы функции от двух аргументов. Свойства дизъюнкции, конъюнкции и отрицания. Свойства эквивалентности, импликации и отрицания. Выражение одних булевых функций через другие
§ 10. Булевы функции от п аргументов..............................................100
Понятие булевой функции. Число булевых функций. Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание. Булевы функции и формулы алгебры высказываний. Нормальные формы булевых функций
§ 11. Системы булевых функций.........................................................106
Полные системы булевых функций. Специальные классы булевых функций. Теорема Поста о полноте системы булевых функций
§ 12. Применение булевых функций к релейно-контактным схемам...............................111
Идея применения. Две основные задачи теории релейно-контактных схем § 13. Релейно-контактные схемы в ЭВМ..........................................115
Двоичный полусумматор. Одноразрядный двоичный сумматор. Шифратор и дешифратор
§ 14. О некоторых других приложениях теории булевых функций.... 119
Диагностика (распознавание) заболеваний. Распознавание образов
Глава III. Формализованное исчисление высказываний.....................122
§ 15. Система аксиом и теория формального вывода.......................122
Начало аксиоматической теории высказываний: первоначальные понятия, система аксиом, правило вывода. Понятие вывода и его свойства. Теорема о дедукции и следствия из неё. Применение теоремы о дедукции. Производные правила вывода
§ 16. Полнота и другие свойства формализованного исчисления высказываний..................133
Доказуемость формулы и ее тождественная истинность (синтаксис и семантика). Лемма о выводимости. Полнота формализованного исчисления высказываний. Теорема адекватности. Непротиворечивость формализованного исчисления высказываний. Разрешимость формализованного исчисления высказываний
§ 17. Независимость системы аксиом формализованного исчисления высказываний................141
Понятие независимости. Независимость аксиомы (А1). Независимость аксиомы (А2). Независимость аксиомы (A3). Независимость системы аксиом
Глава IV. Логика предикатов.................................................146
§ 18. Основные понятия, связанные с предикатами..........................146
Понятие предиката. Классификация предикатов. Множество истинности предиката. Равносильность и следование предикатов
§ 19. Логические операции над предикатами.....................................151
Отрицание предиката. Конъюнкция двух предикатов. Дизъюнкция двух предикатов. Свойства отрицания, конъюнкции и дизъюнкции. Импликация и эквивалентность двух предикатов
§ 20. Кванторные операции над предикатами....................................157
Квантор общности. Квантор существования. Численные кванторы. Ограниченные кванторы. Логический квадрат
§ 21. Формулы логики предикатов......................................................165
Понятие формулы логики предикатов. Классификация формул логики предикатов. Тавтологии логики предикатов
§ 22. Равносильные преобразования формул и логическое следование формул логики предикатов.........................................................178
Понятие равносильности формул. Приведенная форма для формул логики предикатов. Предваренная нормальная форма для формул логики предикатов. Логическое следование формул логики предикатов
§ 23. Проблемы разрешения для общезначимости и выполнимости формул....................184
Постановка проблемы и ее неразрешимость в общем виде. Решение проблемы для формул на конечных множествах. Пример формулы, выполнимой на бесконечном множестве и невыполнимой ни на каком конечном множестве. Проблема разрешения выполнимости: влияние мощности множества и структуры формулы. Решение проблемы для формул, содержащих только одноместные предикатные переменные. Проблема разрешения общезначимости и мощность множества, на котором рассматривается формула. Решение проблемы для V-формул и 3-формул
§ 24. Применение логики предикатов к логико-математической практике................................195
Запись на языке логики предикатов различных предложении. Сравнение логики предикатов и логики высказываний. Строение математических теорем. Методы рассуждений: аристотелева силлогистика. Аристотелева силлогистика и логика предикатов. Теоретико-множественная интерпретация аристотелевой силлогистики. О других методах рассуждений. Принцип полной дизъюнкции в предикатной форме. Метод (полной) математической индукции Необходимые и достаточные условия. Логика предикатов и алгебра множеств
§ 25. Формализованное исчисление предикатов................................222
Первоначальные понятия (язык формализованного исчисления предикатов). Система аксиом исчисления предикатов. Правила вывода (224). Теория формального вывода (224)
Глава V. Неформальные аксиоматические теории...............................226
§ 26. Аксиоматический метод в математике и аксиоматические теории............................226
Понятие аксиоматической теории (226). Как возникают аксиоматические теории (229). Примеры аксиоматических теорий (230). Интерпретации и модели аксиоматической теории (235)
§ 27. Свойства аксиоматических теорий............................................237
Непротиворечивость (238). Категоричность (240). Независимость системы аксиом (241). Полнота (243)
Глава VI. Формальные аксиоматические теории.................................247
§ 28. О формальных аксиоматических теориях.................................248
Об истории идеи формальной аксиоматической теории (249). Понятие формальной аксиоматической теории (251). Язык и метаязык, теоремы и ме-татеоремы формальной теории (252). Интерпретации и модели формальной теории (253). Семантическая выводимость (255). Метаматематика (свойства формальных аксиоматических теорий) (255). Формализованное исчисление высказываний как формальная аксиоматическая теория (257). Формализация теории аристотелевых силлогизмов (258)
§ 29. Свойства формализованного исчисления предикатов..............262
Оправданность аксиоматизации (262). Непротиворечивость формализованного исчисления предикатов (264). Теорема Гёделя о существовании модели (266). Полнота и адекватность формализованного исчисления предикатов (272). Неполнота формализованного исчисления предикатов в абсолютном и узком смыслах (273). Теорема компактности (274)
§ 30. Формальные теории первого порядка........................................276
Теории первого порядка с равенством (277). О формальных теориях множеств (278). О формальной арифметике (290). О формальных теориях числовых систем (295). О формальной геометрии (302). О формальном математическом анализе (306). Общий взгляд на процесс формализации математической теории (308). О границах аксиоматического метода, метода формализации и логики (310)
Глава VII. Элементы теории алгоритмов..............................................312
§ 31. Интуитивное представление об алгоритмах..............................312
Алгоритмы вокруг нас (312). Неформальное понятие алгоритма (314). Необходимость уточнения понятия алгоритма (316)
§ 32. Машины Тьюринга......................................................................317
Определение машины Тьюринга (317). Применение машин Тьюринга к словам (320). Конструирование машин Тьюринга (322). Вычислимые по Тьюрингу функции (324). Правильная вычислимость функций на машине Тьюринга (327). Композиция машин Тьюринга (329). Тезис Тьюринга (основная гипотеза теории алгоритмов) (330). Машины Тьюринга и современные электронно-вычислительные машины (331)
§ 33. Рекурсивные функции.................................................................333
Происхождение рекурсивных функций (333). Основные понятия теории рекурсивных функций и тезис Чёрча (334). Примитивно рекурсивные функции (337). Примитивная рекурсивность предикатов (339). Вычислимость по Тьюрингу примитивно рекурсивных функций (340). Функции Аккермана (342). Оператор минимизации (345). Общерекурсивные и частично рекурсивные функции (347). Вычислимость по Тьюрингу частично рекурсивных функций (347). Частичная рекурсивность функций, вычислимых по Тьюрингу (349)
§ 34. Нормальные алгоритмы Маркова..............................................354
Марковские подстановки (354). Нормальные алгоритмы и их применение к словам (355). Нормально вычислимые функции и принцип нормализации Маркова (356). Совпадение класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу (359). Эквивалентность различных теорий алгоритмов (361)
§ 35. Разрешимость и перечислимость множеств..............................361
§ 36. Неразрешимые алгоритмические проблемы..............................366
Нумерация алгоритмов (366). Нумерация машин Тьюринга (367). Существование невычислимых по Тьюрингу функций (368). Проблемы распознавания самоприменимости и применимости (369). Алгоритмически неразрешимые проблемы в общей теории алгоритмов (370). Теорема Райса (373). Другие примеры алгоритмической неразрешимости (375)
§ 37. Теорема Гёделя о неполноте формальной арифметики...........376
Формальные аксиоматические теории и натуральные числа (377). Формальная арифметика и ее свойства (379). Теорема Гёделя о неполноте (382). Гёдель и его роль в математической логике XX в. (384)
Глава VIII. Математическая логика и компьютеры, информатика, искусственный интеллект...........385
§ 38. Математическая логика и программное обеспечение компьютеров.....................386
Теория алгоритмов и математическая логика — фундаментальная основа программирования (386). Описание компьютерных программ с помощью математической логики (387). Описание программирования и анализ его концепций с помощью математической логики (389). Верификация (доказательство правильности) программ с помощью математической логики (393)
§ 39. Применение компьютеров для доказательства теорем математической логики..................397
Программа «Логик-теоретик» и программы, близкие к ней (398). Метод резолюций для доказательства теорем исчисления высказываний и исчисления предикатов (401)
§ 40. От математической логики к логическому программированию................408
Возникновение языка ПРОЛОГ и его развитие (408). Общая характеристика языка ПРОЛОГ (409). Краткое описание языка ПРОЛОГ и примеры (410). Сферы применения языка ПРОЛОГ (413)
§ 41. Математическая логика и информатика...................................414
Общее понятие о базе данных (414). Реляционная база данных и логика запросов в ней (415)
§ 42. Математическая логика и системы искусственного интеллекта..............419
История развития и предмет искусственного интеллекта как науки (420). Представление знаний в системах искусственного интеллекта (422). Экспертные системы (425). Язык ПРОЛОГ в системах искусственного интеллекта (426). Может ли машина мыслить (426).
Заключение: Всесильна ли логика в познании законов мышления?........428
Список литературы....................................................................................435
