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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Идея применения. Две основные задачи теории релейно-контактных схем.

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

§ 14. О некоторых других приложениях теории булевых функций.

Диагностика (распознавание) заболеваний. Распознавание образов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Непротиворечивость . Категоричность . Независимость системы аксиом . Полнота .

Об истории идеи формальной аксиоматической теории . Понятие формальной аксиоматической теории . Язык и метаязык, теоремы и метатеоремы формальной теории . Интерпретации и модели формальной теории . Семантическая выводимость . Метаматематика (свойства формальных аксиоматических теорий) . Формализованное исчисление высказываний как формальная аксиоматическая теория .Формализация теории аристотелевых силлогизмов .

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

Оправданность аксиоматизации .Непротиворечивость формализованного исчисления предикатов. Теорема Гёделя о существовании модели . Полнота и адекватность формализованного исчисления предикатов . Неполнота формализованного исчисления предикатов в абсолютном и узком смыслах .Теорема компактности .

Теории первого порядка с равенством . О формальных теориях множеств . О формальной арифметике . О формальных теориях числовых систем .О формальной геометрии . О формальном математическом анализе . Обший взгляд на процесс формализации математической теории.О границах аксиоматического метода, метода формализации и логики .

Алгоритмы вокруг нас . Неформальное понятие алгоритма . Необходимость уточнения понятия алгоритма .

Определение машины Тьюринга .Применение машин Тьюринга к словам . Конструирование машин Тьюринга . Вычислимые по Тьюрингу функции . Правильная вычислимость функций на машине Тьюринга . Композиция машин Тьюринга . Тезис Тьюринга (основная гипотеза теории алгоритмов) . Машины Тьюринга и современные электронно-вычислительные машины .

Происхождение рекурсивных функций . Основные понятия теории рекурсивных функций и тезис Черча . Примитивно рекурсивные функции . Примитивная рекурсивность предикатов . Вычислимость по Тьюрингу примитивно рекурсивных функций . Функции Аккермана . Оператор минимизации . Общерекурсивные и частично рекурсивные функции . Вычислимость по Тьюрингу частично рекурсивных функций . Частичная рекурсивность функций, вычислимых по Тьюрингу.

Марковские подстановки . Нормальные алгоритмы и их применение к словам . Нормально вычислимые функции и принцип нормализации Маркова . Совпадение класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу . Эквивалентность различных теорий алгоритмов .

Нумерация алгоритмов . Нумерация машин Тьюринга . Существование невычислимых по Тьюрингу функций . Проблемы распознавания самоприменимости и применимости . Алгоритмически неразрешимые проблемы в обшей теории алгоритмов . Теорема Раиса . Другие примеры алгоритмической неразрешимости .

§ 37. Теорема Гёделя о неполноте формальной арифметики.

Формальные аксиоматические теории и натуральные числа . Формальная арифметика и ее свойства . Теорема Гёделя о неполноте . Гёдель и его роль в математической логике XX в. .

Глава VIII. Математическая логика и компьютеры, информатика, искусственный интеллект.

* § 38. Математическая логика и программное обеспечение компьютеров.

Теория алгоритмов и математическая логика - фундаментальная основа программирования . Описание компьютерных программ с помощью математической логики . Описание программирования и анализ его концепций с помощью математической логики . Верификация (доказательство правильности) программ с помощью математической логики .

§ 39. Применение компьютеров для доказательства теорем математической логики.

Программа «Логик-теоретик» и программы, близкие к ней . Метод резолюций для доказательства теорем исчисления высказываний и исчисления предикатов .

§ 40. От математической логики к логическому программированию.

Возникновение языка ПРОЛОГ и его развитие . Общая характеристика языка ПРОЛОГ . Краткое описание языка ПРОЛОГ и примеры. Сферы применения языка ПРОЛОГ .

Общее понятие о базе данных . Реляционная база данных и логика запросов в ней.

§ 42. Математическая логика и системы искусственного интеллекта История развития и предмет искусственного интеллекта как науки . Представление знаний в системах искусственного интеллекта . Экспертные системы . Язык ПРОЛОГ в системах искусственного интеллекта . Может ли машина мыслить .

Заключение: Всесильна ли логика в познании законов мышления?

Мыслительная деятельность человека представляет собой сложный и многогранный процесс, происходящий как на сознательном, так и на бессознательном (подсознательном) уровнях. Это высшая ступень человеческого познания, способность к адекватному отражению предметов и явлений действительности, т.е. к нахождению истины.

Развитие науки и особенно математики немыслимо без интуиции. Различают два вида интуиции в научном познании1: интуицию-суждение и интуицию-догадку. Интуиция-суждение (или философская интуиция-суждение) характеризуется тем, что в этом случае прямое усмотрение истины, объективной связи вещей осуществляется не просто без логически строгого доказательства, но такого доказательства для данной истины не существует и не может существовать в принципе. Интуиция-суждение осуществляется как единый (единовременный) синтетический целостный акт обобщающего характера. Именно такой характер логически недоказуемых утверждений носят рассматриваемые в теории алгоритмов тезисы Тьюринга, Чёрча и Маркова.

Бесплатно скачать электронную книгу в удобном формате и читать:

Рабочая тетрадь по статистике с ответами