- •Математическая логика и теория алгоритмов
- •11. Понятие об алгоритмах. Схемы алгоритмов
- •11.1. Понятие об алгоритме и теории алгоритмов
- •11.2. Схемы алгоритмов
- •11.3. Рекурсивные функции
- •11.4. Машина Тьюринга
- •11.5. Машина Поста
- •11.6. Нормальные алгорифмы а.А. Маркова
- •11.7. Универсальная абстрактная машина
- •11.8. Разрешимость в теории алгоритмов. Проблема самоприменимости
- •11.9. Сложность алгоритма
- •11.10. Представление схемы алгоритма эквивалентным автоматом
- •11.11. Представление схемы алгоритма микропрограммой с двумя типами микрокоманд
- •12. Элементы формальной логики
- •12.1. Предмет формальной логики
- •12.2. Понятие и его виды
- •12.3. Отношения между понятиями
- •12.4. Операции над понятиями
- •12.5. Суждение и его характеристика
- •Модальные и категорические суждения.
- •Простые категорические суждения.
- •Виды простых категорических суждений.
- •Распределение терминов в простом категорическом суждении.
- •Логический квадрат.
- •13. Умозаключение
- •13.1. Виды умозаключений
- •13.2. Непосредственное умозаключение
- •Умозаключения путем противопоставления предикату.
- •13.3. Опосредованное дедуктивное умозаключение. Фигуры силлогизма
- •Фигуры пкс.
- •Модусы пкс.
- •13.4. Дополнительные виды силлогизмов
- •13.5. Индуктивные умозаключения. Математическая индукция
- •14. Логика высказываний
- •14.1. Семантика логики высказываний
- •I закон – тождества.
- •14.3. Формализация высказываний
- •14.4. Интерпретации, разрешимость, выполнимость, общезначимость
- •14. 5. Логическая равносильность. Законы логики
- •14.6. Формы представления формул логики высказываний
- •14.7. Проблема дедукции в логике высказываний
- •15. Проверка правильности логических выводов. Метод резолюций
- •15.1. Закон контрапозиции
- •15.2. Логическое следование. Проверка правильности логических выводов
- •15.3. Силлогизмы в логике высказываний
- •Разделительно-категоричные силлогизмы.
- •16. Синтаксис и семантика языка логики предикатов
- •16.1. Понятие предиката
- •16.2. Кванторы и связанные переменные
- •16.3. Синтаксис языка логики предикатов. Формулы логики предикатов и формализация суждений
- •16.4. Семантика формул логики предикатов
- •Общезначимость, выполнимость, невыполнимость.
- •17. Тождественные преобразования формул логики предикатов
- •17.1. Операции над предикатами
- •17.2. Основные равносильности логики предикатов
- •Отрицание предложений с кванторами.
- •17.3. Тождественные преобразования формул
- •17.4. Универсум Эрбрана
- •18. Использование метода резолюций в логике предикатов
- •18.1. Подстановка и унификация
- •18.2. Резольвенция и факторизация
- •18.3. Метод резолюций в логике предикатов
- •18.4. Принцип логического программирования
- •19. Логические исчисления
- •19.1. Понятие о формальных теориях
- •19.2. Исчисление высказываний
- •19.3. Исчисление предикатов
- •19.4. Система натурного вывода
- •19.5. Понятие о математической лингвистике
- •19.6. Формальный язык
- •19.7. Формальные грамматики и их свойства
- •19.8. Теоремы Гёделя
- •20. Неклассические логики
- •20.1. Современные модальные логики
- •20.2. Понятие о теории неопределенности
- •20.3. Элементы теории нечетких множеств и нечеткая логика
- •20.4. Нечеткие алгоритмы
- •Литература
- •Приложение 1 Варианты контрольных заданий по дисциплине «Дискретная математика»
- •Приложение 2 Варианты контрольных заданий по дисциплине «Математическая логика»
19.8. Теоремы Гёделя
В математической логике доказывается, что исчисление предикатов непротиворечиво – т.е. в нем невозможно одновременно вывести , и. Кроме того, в силу теоремы Гёделя о полноте исчисления предикатов общезначимая формула выводима в исчислении предикатов.
Рассмотренное исчисление предикатов – исчисление предикатов первого порядка. В исчислениях второго порядка возможны кванторы по предикатам, т.е. выражения вида "Р(Р(х)), или по функциям.
Итак, множество всех истинных высказываний логики высказываний перечислимо и разрешимо. Множество всех истинных высказываний логики предикатов перечислимо (ввиду его полноты), но неразрешимо (ввиду бесконечности предметной области).
В качестве еще одной формальной теории в математической логике рассматривается так называемая формальная арифметика, предложенная итальянским математиком Джузеппе Пеано (1858-1932 гг.) [26]. Пеано ввел символы и операции , , и впервые излагал логику как математическую дисциплину. Впервые попытка сведения математики к логике была предпринята немецким математиком и логиком Готтлибом Фреге (1848-1925 гг.). Это он определил множество, как объем понятия. Он писал: «Арифметика есть часть логики и не должна заимствовать ни у опыта, ни у созерцания никаких основ доказательств». Знаменитый парадокс о множестве всех множеств – это противоречие в системе Фреге, выявленное Бертраном Расселом.
Гёдель доказал, что любая формальная теория Т, содержащая формальную арифметику, неполна: в ней существует замкнутая формула F, такая, что истинно, но ни F, нине выводимы в Т. В соответствии со знаменитой теоремой Гёделя о неполноте, для любой непротиворечивой формальной теории Т, содержащей формальную арифметику, формула, выражающая непротиворечивость Т, недоказуема в Т.
Таким образом, арифметика и теория чисел являются неаксиматизируемыми теориями, а множество всех истинных высказываний арифметики неперечислимо.
Теоремы Гёделя имеют важное методологическое значение [19]. Оказывается, для достаточно богатых математических теорий не существует адекватных формализаций. Правда, любую неполную теорию Т можно расширить, добавив к ней в качестве аксиомы истинную, но не выводимую в Т формулу, однако, новая теория также будет неполна. Кроме того, невозможно исследовать метасвойства теории средствами самой формальной теории, т.е. всякая метатеория Т для того, чтобы иметь возможность доказывать хотя бы непротиворечивость, должна быть богаче Т [19].
Таким образом, под сомнение берется сам подход построения математики как некоторой фиксированной совокупности средств, которые можно было бы объявить единственно законными и с их помощью строить метатеории любых теорий. Но это вовсе не крах формального подхода. Наличие неразрешимых проблем не говорит о том, что конструктивный подход не пригоден, если он чего-то и не может, то лишь потому, что этого не может никто [19].
Невозможность полной формализации содержательно определенных теорий – это не недостаток концепции, а объективный факт, неустранимый никакой концепцией.
Невозможность адекватной формализации теории означает, что надо либо искать формализуемые ее фрагменты, либо строить более сильную формальную теорию, которая, правда, снова будет неполна, но, быть может, будет содержать всю исходную теорию [19].