Математическая логика и теория алгоритмов, Игошин В.И., 2008

Математическая логика и теория алгоритмов, Игошин В.И., 2008.
Предлагаемое учебное пособие (2-ое изд., стереотип.) составляет основу комплекта по курсу математической логики и теории алгоритмов, в который также входит сборник задач (Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов).
Подробно изложены основы теории, показаны направления проникновения логики в основания алгебры, анализа, геометрии, привлечен материал школьного курса математики для его логического анализа, охарактеризованы взаимосвязи математической логики с компьютерами, информатикой, системами искусственного интеллекта.

Введение. Математическая логика в системе современного образования.
Логика и интуиция . Логика традиционная и математическая логика . Немного истории. Математическая логика - логика или математика? Математическая логика в обучении математике. Математическая логика и современные ЭВМ.
Глава I. Алгебра высказываний.
§ 1. Высказывания и операции над ними.
Понятие высказывания. Отрицание высказывания. Конъюнкция двух высказываний. Дизъюнкция двух высказываний. Импликация двух высказываний. Эквивалентность двух высказываний. Союзы языка и логические операции (язык и логика). Общий взгляд на логические операции.
§2. Формулы алгебры высказываний.
Конструирование сложных высказываний. Понятие формулы алгебры высказываний. Логическое значение составного высказывания. Составление таблиц истинности для формул. Классификация формул алгебры высказываний. Мышление и математическая логика
§ 3. Тавтологии алгебры высказываний.
О значении тавтологий. Основные тавтологии. Основные правила получения тавтологии.
§ 4. Логическая равносильность формул.
Понятие равносильности формул. Признак равносильности формул. Примеры равносильных формул. Равносильные преобразования формул. Равносильности в логике и тождества в алгебре.
§ 5. Нормальные формы для формул алгебры высказываний.
Понятие нормальных форм. Совершенные нормальные формы. Представление формул алгебры высказываний совершенными дизъюнктивными нормальными (СДН) формами. Представление формул алгебры высказываний совершенными конъюнктивными нормальными (СКН) формами. Два способа приведения формулы алгебры высказываний к совершенной нормальной форме
§ 6. Логическое следование формул.
Понятие логического следствия. Признаки логического следствия. Два свойства логического следования. Следование и равносильность формул. Правила логических умозаключений. Еще один способ проверки логического следования. Нахождение следствий из данных посылок. Нахождение посылок для данного следствия.
§ 7. Приложение алгебры высказываний к логико-математической практике.
Прямая и обратная теоремы. Необходимые и достаточные условия. Противоположная и обратная противоположной теоремы. Закон контрапозиции. Модификация структуры математической теоремы. Методы доказательства математических теорем. Дедуктивные и индуктивные умозаключения. Правильные и неправильные дедуктивные умозаключения. Решение логических задач. Принцип полной дизъюнкции. Одно обобщение принципа полной дизъюнкции.
Глава II. Булевы функции.
§8. Множества, отношения, функции.
Понятие множества. Включение и равенство множеств. Операции над множествами. Бинарные отношения и функции. Понятие ларного отношения.
§ 9. Булевы функции от одного и двух аргументов.
Происхождение булевых функций. Булевы функции от одного аргумента. Булевы функции от двух аргументов. Свойства дизъюнкции, конъюнкции и отрицания. Свойства эквивалентности, импликации и отрицания. Выражение одних булевых функций через другие
§ 10. Булевы функции от п аргументов.
Понятие булевой функции. Число булевых функций. Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание. Булевы функции и формулы алгебры высказываний. Нормальные формы булевых функций.
§ 11. Системы булевых функций.
Полные системы булевых функций. Специальные классы булевых функций. Теорема Поста о полноте системы булевых функций
§ 12. Применение булевых функций к релейно-контактным схемам.
Идея применения. Две основные задачи теории релейно-контактных схем.
§ 13. Релейно-контактные схемы в ЭВМ.
Двоичный полусумматор. Одноразрядный двоичный сумматор. Шифратор и дешифратор.
§ 14. О некоторых других приложениях теории булевых функций.
Диагностика (распознавание) заболеваний. Распознавание образов.
Глава III. Формализованное исчисление высказываний.
§ 15. Система аксиом и теория формального вывода.
Начало аксиоматической теории высказываний: первоначальные понятия, система аксиом, правило вывода. Понятие вывода и его свойства. Теорема о дедукции и следствия из неё. Применение теоремы о дедукции. Производные правила вывода
§ 16. Полнота и другие свойства формализованного исчисления высказываний
Доказуемость формулы и ее тождественная истинность (синтаксис и семантика). Лемма о выводимости. Полнота формализованного исчисления высказываний. Теорема адекватности. Непротиворечивость формализованного исчисления высказываний. Разрешимость формализованного исчисления высказываний
§ 17. Независимость системы аксиом формализованного исчисления высказываний.
Понятие независимости. Независимость аксиомы (А1). Независимость аксиомы (А2). Независимость аксиомы (A3). Независимость системы аксиом
Глава IV. Логика предикатов.
§ 18. Основные понятия, связанные с предикатами.
Понятие предиката. Классификация предикатов. Множество истинности предиката. Равносильность и следование предикатов
§ 19. Логические операции над предикатами.
Отрицание предиката. Конъюнкция двух предикатов. Дизай перейти на страницу дикатов. Свойства отрицания, конъюнкции и дизъюнкции. Импликация и эквивалентность двух предикатов.
§ 20. Кванторные операции над предикатами.
Квантор общности. Квантор существования. Численные кванторы. Ограниченные кванторы. Логический квадрат
§ 21. Формулы логики предикатов.
Понятие формулы логики предикатов. Классификация формул логики предикатов. Тавтологии логики предикатов
§ 22. Равносильные преобразования формул и логическое следование формул логики предикатов
Понятие равносильности формул. Приведенная форма для формул логики предикатов. Предваренная нормальная форма для формул логики предикатов. Логическое следование формул логики предикатов
§ 23. Проблемы разрешения для обще значимости и выполнимости формул.
Постановка проблемы и ее неразрешимость в общем виде. Решение проблемы для формул на конечных множествах. Пример формулы, выполнимой на бесконечном множестве и невыполнимой ни на каком конечном множестве. Проблема разрешения выполнимости: влияние мощности множества и структуры формулы. Решение проблемы для формул, содержащих только одноместные предикатные переменные. Проблема разрешения общезначимости и мощность множества, на котором рассматривается формула. Решение проблемы для V-формул и 3-формул
§ 24. Применение логики предикатов к логико-математической практике.
Запись на языке логики предикатов различных предложении. Сравнение логики предикатов и логики высказываний. Строение математических теорем. Методы рассуждений: аристотелева силлогистика. Аристотелева силлогистика и логика предикатов. Теоретико-множественная интерпретация аристотелевой силлогистики. О других методах рассуждений. Принцип полной дизъюнкции в предикатной форме. Метод (полной) математической индукции Необходимые и достаточные условия. Логика предикатов и алгебра множеств.
§ 25. Формализованное исчисление предикатов.
Первоначальные понятия (язык формализованного исчисления предикатов). Система аксиом исчисления предикатов. Правила вывода . Теория формального вывода .
Глава V. Неформальные аксиоматические теории.
§ 26. Аксиоматический метод в математике и аксиоматические теории.
Понятие аксиоматической теории . Как возникают аксиоматические теории . Примеры аксиоматических теорий . Интерпретации и модели аксиоматической теории .
§ 27. Свойства аксиоматических теорий.
Непротиворечивость . Категоричность . Независимость системы аксиом . Полнота .
Глава VI. Формальные аксиоматические теории.
§ 28. О формальных аксиоматических теориях.
Об истории идеи формальной аксиоматической теории . Понятие формальной аксиоматической теории . Язык и метаязык, теоремы и метатеоремы формальной теории . Интерпретации и модели формальной теории . Семантическая выводимость . Метаматематика (свойства формальных аксиоматических теорий) . Формализованное исчисление высказываний как формальная аксиоматическая теория .Формализация теории аристотелевых силлогизмов .
§ 29. Свойства формализованного исчисления предикатов.
Оправданность аксиоматизации .Непротиворечивость формализованного исчисления предикатов. Теорема Гёделя о существовании модели . Полнота и адекватность формализованного исчисления предикатов . Неполнота формализованного исчисления предикатов в абсолютном и узком смыслах .Теорема компактности .
§ 30. Формальные теории первого порядка.
Теории первого порядка с равенством . О формальных теориях множеств . О формальной арифметике . О формальных теориях числовых систем .О формальной геометрии . О формальном математическом анализе . Обший взгляд на процесс формализации математической теории.О границах аксиоматического метода, метода формализации и логики .
Глава VII. Элементы теории алгоритмов.
§31. Интуитивное представление об алгоритмах.
Алгоритмы вокруг нас . Неформальное понятие алгоритма . Необходимость уточнения понятия алгоритма .
§ 32. Машины Тьюринга.
Определение машины Тьюринга .Применение машин Тьюринга к словам . Конструирование машин Тьюринга . Вычислимые по Тьюрингу функции . Правильная вычислимость функций на машине Тьюринга . Композиция машин Тьюринга . Тезис Тьюринга (основная гипотеза теории алгоритмов) . Машины Тьюринга и современные электронно-вычислительные машины .
§ 33. Рекурсивные функции.
Происхождение рекурсивных функций . Основные понятия теории рекурсивных функций и тезис Черча . Примитивно рекурсивные функции . Примитивная рекурсивность предикатов . Вычислимость по Тьюрингу примитивно рекурсивных функций . Функции Аккермана . Оператор минимизации . Общерекурсивные и частично рекурсивные функции . Вычислимость по Тьюрингу частично рекурсивных функций . Частичная рекурсивность функций, вычислимых по Тьюрингу.
§34. Нормальные алгоритмы Маркова.
Марковские подстановки . Нормальные алгоритмы и их применение к словам . Нормально вычислимые функции и принцип нормализации Маркова . Совпадение класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу . Эквивалентность различных теорий алгоритмов .
§ 35. Разрешимость и перечислимость множеств.
§ 36. Неразрешимые алгоритмические проблемы.
Нумерация алгоритмов . Нумерация машин Тьюринга . Существование невычислимых по Тьюрингу функций . Проблемы распознавания самоприменимости и применимости . Алгоритмически неразрешимые проблемы в обшей теории алгоритмов . Теорема Раиса . Другие примеры алгоритмической неразрешимости .
§ 37. Теорема Гёделя о неполноте формальной арифметики.
Формальные аксиоматические теории и натуральные числа . Формальная арифметика и ее свойства . Теорема Гёделя о неполноте . Гёдель и его роль в математической логике XX в. .
Глава VIII. Математическая логика и компьютеры, информатика, искусственный интеллект.
* § 38. Математическая логика и программное обеспечение компьютеров.
Теория алгоритмов и математическая логика - фундаментальная основа программирования . Описание компьютерных программ с помощью математической логики . Описание программирования и анализ его концепций с помощью математической логики . Верификация (доказательство правильности) программ с помощью математической логики .
§ 39. Применение компьютеров для доказательства теорем математической логики.
Программа «Логик-теоретик» и программы, близкие к ней . Метод резолюций для доказательства теорем исчисления высказываний и исчисления предикатов .
§ 40. От математической логики к логическому программированию.
Возникновение языка ПРОЛОГ и его развитие . Общая характеристика языка ПРОЛОГ . Краткое описание языка ПРОЛОГ и примеры. Сферы применения языка ПРОЛОГ .
§41. Математическая логика и информатика.
Общее понятие о базе данных . Реляционная база данных и логика запросов в ней.
§ 42. Математическая логика и системы искусственного интеллекта История развития и предмет искусственного интеллекта как науки . Представление знаний в системах искусственного интеллекта . Экспертные системы . Язык ПРОЛОГ в системах искусственного интеллекта . Может ли машина мыслить .
Заключение: Всесильна ли логика в познании законов мышления?
Список литературы.
Логика и интуиция.
Мыслительная деятельность человека представляет собой сложный и многогранный процесс, происходящий как на сознательном, так и на бессознательном (подсознательном) уровнях. Это высшая ступень человеческого познания, способность к адекватному отражению предметов и явлений действительности, т.е. к нахождению истины.
Логика и интуиция -два противоположных и неразрывно связанных между собой свойства человеческого мышления. Логическое (дедуктивное) мышление отличается тем, что оно от истинных посылок всегда приводит к истинному заключению, не опираясь при этом на опыт, интуицию и другие внешние факторы. Интуиция (от лат. intuitio - «пристальное всматривание») представляет собой способность постижения истины путем прямого ее усмотрения без обоснования с помощью логически строгого доказательства. Таким образом, интуиция является своего рода антиподом, противовесом логики и строгости.
Логическая часть мыслительного процесса протекает на уровне сознания, интуитивная - на подсознательном уровне.
Развитие науки и особенно математики немыслимо без интуиции. Различают два вида интуиции в научном познании1: интуицию-суждение и интуицию-догадку. Интуиция-суждение (или философская интуиция-суждение) характеризуется тем, что в этом случае прямое усмотрение истины, объективной связи вещей осуществляется не просто без логически строгого доказательства, но такого доказательства для данной истины не существует и не может существовать в принципе. Интуиция-суждение осуществляется как единый (единовременный) синтетический целостный акт обобщающего характера. Именно такой характер логически недоказуемых утверждений носят рассматриваемые в теории алгоритмов тезисы Тьюринга, Чёрча и Маркова.