Предисловие ................................................................................................. 3 Введение. Математическая логика в системе современного образования.................................................................................6

Логика и интуиция (6). Логика традиционная и математическая логика (7). Немного истории. Математическая логика — логика или математика? Математическая логика в обучении математике. Математическая логика и современные ЭВМ

Г л а в а I. Алгебра высказываний...............................................................15 § 1. Высказывания и операции над ними.............................................15

Понятие высказывания. Отрицание высказывания. Конъюнкция двух высказываний. Дизъюнкция двух высказываний. Импликация двух высказываний. Эквивалентность двух высказываний. Союзы языка и логические операции (язык и логика). Общий взгляд на логические операции

§ 2. Формулы алгебры высказываний...................................................23

Конструирование сложных высказываний. Понятие формулы алгебры высказываний. Логическое значение составного высказывания. Составление таблиц истинности для формул. Классификация формул алгебры высказываний. Мышление и математическая логика

§ 3. Тавтологии алгебры высказываний...............................................33

О значении тавтологий. Основные тавтологии. Основные правила получения тавтологий

§4. Логическая равносильность формул..............................................39

Понятие равносильности формул. Признак равносильности формул. Примеры равносильных формул. Равносильные преобразования формул. Равно-сильности в логике и тождества в алгебре

§ 5. Нормальные формы для формул алгебры высказываний............45

Понятие нормальных форм. Совершенные нормальные формы. Представление формул алгебры высказываний совершенными дизъюнктивными нормальными (СДН) формами. Представление формул алгебры высказываний совершенными конъюнктивными нормальными (СКН) формами. Два способа приведения формулы алгебры высказываний к совершенной нормальной форме

§ 6. Логическое следование формул.....................................................53

Понятие логического следствия. Признаки логического следствия. Два свойства логического следования. Следование и равносильность формул. Правила логических умозаключений. Еще один способ проверки логического следования. Нахождение следствий из данных посылок. Нахождение посылок для данного следствия

§ 7. Приложение алгебры высказываний к логико-математической практике..........................................................................................64

Прямая и обратная теоремы. Необходимые и достаточные условия. Противоположная и обратная противоположной теоремы. Закон контрапозиции. Мо-

дификация структуры математической теоремы. Методы доказательства матматических теорем. Дедуктивные и индуктивные умозаключения. Правильном и неправильные дедуктивные умозаключения. Решение логических задач. Прин-цип полной дизъюнкции. Одно обобщение принципа полной дизъюнкции

Глава II. Булевы функции........................................................................XV § 8. Множества, отношения, функции.................................................8')

Понятие множества. Включение и равенство множеств. Операции над мно-жествами. Бинарные отношения и функции. Понятие n-арного отношения

§ 9. Булевы функции от одного и двух аргументов.............................93

Происхождение булевых функций. Булевы функции от одного аргумента, Булевы функции от двух аргументов. Свойства дизъюнкции, конъюнкции и отрицания. Свойства эквивалентности, импликации и отрицания. Выражение одних булевых функций через другие

§ 10. Булевы функции от п аргументов............................................../00

Понятие булевой функции. Число булевых функций. Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание. Булевы функции и формулы алгебры высказываний. Нормальные формы булевых функций

§ 11. Системы булевых функций.........................................................106

Полные системы булевых функций. Специальные классы булевых функ-ций. Теорема Поста о полноте системы булевых функций

§ 12. Применение булевых функций к релейно-контактным схемам..........................................................................................111

Идея применения. Две основные задачи теории релейно-контактных схем § 13. Релейно-контактные схемы в ЭВМ..........................................115

Двоичный полусумматор. Одноразрядный двоичный сумматор. Шифратор и дешифратор

§ 14. О некоторых других приложениях теории булевых функций.... 119 Диагностика (распознавание) заболеваний. Распознавание образов

Глава III. Формализованное исчисление высказываний.....................122 § 15. Система аксиом и теория формального вывода.......................122

Начало аксиоматической теории высказываний: первоначальные понятия, система аксиом, правило вывода. Понятие вывода и его свойства. Теоре-ма о дедукции и следствия из неё. Применение теоремы о дедукции. Производные правила вывода

§ 16. Полнота и другие свойства формализованного исчисления высказываний..............................................................................133

Доказуемость формулы и ее тождественная истинность (синтаксис и семантика). Лемма о выводимости. Полнота формализованного исчисления высказываний. Теорема адекватности. Непротиворечивость формализованного исчисления высказываний. Разрешимость формализованного исчисления высказываний

§ 17. Независимость системы аксиом формализованного исчисления высказываний..........................................................141

Понятие независимости. Независимость аксиомы (А1). Независимость аксиомы (А2). Независимость аксиомы (АЗ). Независимость системы аксиом

Глава IV. Логики предикатов.................................................................146

§ 18. Основные понятия, связанные с предикатами..........................146

Понятие предиката. Классификация предикатов. Множество истинности предиката. Равносильность и следование предикатов

§ 19. Логические операции над предикатами.....................................151

Отрицание предиката. Конъюнкция двух предикатов. Дизъюнкция двух предикатов. Свойства отрицания, конъюнкции и дизъюнкции. Импликация и эквивалентность двух предикатов

§ 20. Кванторные операции над предикатами....................................157

Квантор общности. Квантор существования. Численные кванторы. Ограниченные кванторы. Логический квадрат

§ 21. Формулы логики предикатов......................................................165

Понятие формулы логики предикатов. Классификация формул логики предикатов. Тавтологии логики предикатов

§ 22. Равносильные преобразования формул и логическое следование формул логики предикатов.........................................................178

Понятие равносильности формул. Приведенная форма для формул логики предикатов. Предваренная нормальная форма для формул логики предикатов. Логическое следование формул логики предикатов

§ 23. Проблемы разрешения для общезначимости и выполнимости

формул.........................................................................................184

Постановка проблемы и ее неразрешимость в общем виде. Решение проблемы для формул на конечных множествах. Пример формулы, выполнимой на бесконечном множестве и невыполнимой ни на каком конечном множестве. Проблема разрешения выполнимости: влияние мощности множества и структуры формулы. Решение проблемы для формул, содержащих только одноместные предикатные переменные. Проблема разрешения общезначимости и мощность множества, на котором рассматривается формула. 

§ 24. Применение логики предикатов к логико-математической

практике......................................................................................195

Запись на языке логики предикатов различных предложении. Сравнение логики предикатов и логики высказываний. Строение математических теорем. Методы рассуждений: аристотелева силлогистика. Аристотелева силлогистика и логика предикатов. Теоретико-множественная интерпретация аристотелевой силлогистики. О других методах рассуждений. Принцип полной дизъюнкции в предикатной форме. Метод (полной) математической индукции Необходимые и достаточные условия. Логика предикатов и алгебра множеств

§ 25. Формализованное исчисление предикатов................................222

Первоначальные понятия (язык формализованного исчисления предикатов). Система аксиом исчисления предикатов. Правила вывода (224). Теория формального вывода (224)

Глава V. Неформальные аксиоматические теории...............................226

§ 26. Аксиоматический метод в математике и аксиоматические

теории............................................................................................2.26

Понятие аксиоматической теории (226). Как возникают аксиоматические теории (229). Примеры аксиоматических теорий (230). Интерпретации и модели аксиоматической теории (235)

§ 27. Свойства аксиоматических теорий.............................................237

Непротиворечивость (238). Категоричность (240). Независимость системы аксиом (241). Полнота (243)

Глава VI. Формальные аксиоматические теории..................................247 § 28. О формальных аксиоматических теориях.................................248

Об истории идеи формальной аксиоматической теории (249). Поняние

формальной аксиоматической теории (251). Язык и метаязык, теоремы и м< татеоремы формальной теории (252). Интерпретации и модели формальной теории (253). Семантическая выводимость (255). Метаматематика (свойства формальных аксиоматических теорий) (255). Формализованное исчисления высказываний как формальная аксиоматическая теория (257). Формализации теории аристотелевых силлогизмов (258)

§ 29. Свойства формализованного исчисления предикатов..............'

Оправданность аксиоматизации (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). Обшерекурсивные и частично рекурсивные 11-функции (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