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