Исчисление предикатов: определение, основные аксиомы
Исчисление предикатов - это формальный логический аппарат, позволяющий анализировать структуру логических рассуждений с учетом связей между субъектами и предикатами высказываний. Давайте разберемся, как устроено это мощное средство.
Определение исчисления предикатов
Исчисление предикатов - это формальная логическая система, предназначенная для анализа структуры логических умозаключений. В отличие от исчисления высказываний, которое рассматривает простейшие истинностные значения, исчисление предикатов позволяет анализировать более сложные высказывания, включающие связи между субъектами и предикатами.
Конкретнее, исчисление предикатов учитывает:
- Логическую структуру суждений - как они получены из других высказываний с помощью логических операций
- Связь между субъектом (о чем говорится) и предикатом (что говорится) высказываний
Для анализа используются:
- Предикаты
- Кванторы (существования и всеобщности)
- Логические операции (отрицание, конъюнкция, дизъюнкция и др.)
Например, высказывание "Все люди смертны" можно представить в исчислении предикатов так:
∀x (Человек(x) → Смертный(x))
Здесь ∀x - квантор всеобщности, Человек(x) и Смертный(x) - предикаты, а → - логическая операция импликации.
Компоненты исчисления предикатов
Для формализации рассуждений исчисление предикатов использует специальный формальный язык. Рассмотрим основные компоненты этого языка.
В алфавит исчисления предикатов входят:
- Предметные переменные (x, y, z ...) - обозначают объекты предметной области
- Константы (a, b, c...) - обозначают конкретные объекты предметной области
- Функциональные символы (f, g, h...) - обозначают функции над объектами
- Предикатные символы (P, Q, R...) - обозначают предикаты, т.е. высказывания об объектах
- Логические символы (&, ∨, ¬...) - обозначают логические операции
Термы
Посредством комбинации предметных переменных, констант и функций строятся выражения, называемые термами. Например, f(x, a), g(b, f(b)) - термы.
На базе термов с использованием предикатных символов и логических операций строятся формулы исчисления предикатов по следующим правилам:
- Любой предикатный символ с термами в скобках является формулой
- Если A и B формулы, то ¬A, (A ∧ B), (A ∨ B) и т.д. также являются формулами
- Если A формула и x переменная, то ∀xA и ∃xA тоже являются формулами
Например, ∀x(P(x)→Q(f(x))), ∃y(R(y,a)∧W(y)) - формулы исчисления предикатов.
Аксиомы и правила вывода
Исчисление предикатов включает:
- Аксиомы - формулы, принимаемые за истинные
- Правила вывода - позволяющие на основе аксиом получать новые формулы (теоремы)
Аксиомы задают базовые истинные высказывания, а правила вывода - принципы логического следования. Рассмотрим их подробнее далее.
Итак, мы вкратце разобрались с основными компонентами, используемыми в исчислении предикатов для формализации логических рассуждений. Далее перейдем к более детальному рассмотрению семантики, аксиоматики и свойств этой важной логической системы.
Семантика исчисления предикатов
Чтобы формально определять истинностные значения формул в исчислении предикатов, вводится понятие семантики, или интерпретации формул.
Интерпретация формулы A задается на непустом множестве U, называемом предметной областью:
- Каждой переменной сопоставляется элемент предметной области
- Каждой n-местной предикатной переменной сопоставляется n-местный предикат на U
Определение истинности
На основе интерпретации по индукции определяется значение истинности |A| формулы A:
- Для элементарной формулы P(t1,...,tn) значение определяется значением предиката P на сопоставленных термах t1,...,tn
- Для составных формул определяется в соответствии со значениями логических операций
Например, если |A|=Истина и |B|=Ложь, то |A ∧ B|=Ложь.
Общезначимость и выводимость
Формула A называется:
- Общезначимой, если |A|=Истина в любой интерпретации
- Выводимой если существует ее вывод из аксиом исчисления предикатов
Основные аксиомы исчисления предикатов
Аксиомы исчисления предикатов строятся на базе исчисления высказываний с добавлением аксиом для кванторов.
Аксиомы вида A→(B→A) для логических связок (импликация, конъюнкция и т.д.). Например:
- (Q→(P→Q))
- ((P∧Q)→P)
Аксиомы для кванторов
Добавляются схемы аксиом:
- ∀xφ(x) → φ(y), где y свободна в φ(y)
- φ(y) → ∃xφ(x), где x не свободна в φ(y)
Например:
- ∀x(P(x)→P(y))
- P(y)→∃xP(x)
Правила вывода в исчислении предикатов
Основными правилами вывода являются:
- MP: правило вывода по правилу modus ponens
- ∀-правило: ∀xA → A(y)
- ∃-правило: A(x) → ∃xA
где A(x) и A(y) отличаются только заменой свободных вхождений x на y. Например:
| 1) ∀xP(x) |
| 2) ∀xP(x)→P(y) |
| 3) P(y) (∀-правило 1,2) |
Эти правила позволяют строить формальные выводы в исчислении предикатов.
Свойства исчисления предикатов
Исчисление предикатов первого порядка обладает важными свойствами:
- Непротиворечивость: нельзя вывести A и ¬A
- Полнота: общезначимая формула выводима
- Компактность: если множество формул невыполнимо, то существует его конечное невыполнимое подмножество
Благодаря этим свойствам исчисление предикатов первого порядка является удобным средством для формализации математических теорий и моделирования логических рассуждений.
Применение исчисления предикатов
Благодаря своим свойствам, исчисление предикатов широко применяется в логике и основаниях математики.
Исчисление предикатов позволяет формализовывать на математическом языке утверждения обыденного и научного языка, выявляя их логическую структуру.
Например, рассуждение "Все люди смертны, Сократ - человек, значит Сократ смертен" можно записать так:
- ∀x(Ч(x)→См(x))
- Ч(с)
- ∴ См(с)
Построение логико-математических теорий
На базе исчисления предикатов строятся аксиоматические теории в математике и информатике:
- Теория множеств
- Арифметика натуральных чисел (пеанова арифметика)
- Алгебраические структуры
Моделирование рассуждений в ИИ
Исчисление предикатов используется для логического моделирования в искусственном интеллекте:
- Представление знаний и рассуждений
- Построение экспертных систем
- Автоматическое доказательство теорем
Перспективы развития теории
Активно развиваются различные расширения и обобщения исчисления предикатов:
- Теория типов на базе λ-исчисления
- Исчисления высших порядков
- Неклассические исчисления (интуиционистское, модальное и др.)
Интенсивно исследуются новые применения в математике, лингвистике, искусственном интеллекте.
Неклассические исчисления предикатов
Помимо классического, существуют различные неклассические исчисления предикатов, отличающиеся набором аксиом и правил вывода.
В интуиционистском исчислении предикатов:
- Отвергается закон исключенного третьего
- Акцент на конструктивных доказательствах существования
Используется в интуиционистской математике, ориентированной на конструктивные методы.
Модальные исчисления предикатов
Модальности:
- Возможность ♢xA(x)
- Необходимость □xA(x)
Применяются в математической логике, лингвистике, информатике.
Временные исчисления предикатов
Вводятся операторы времени:
- Было истинно A, P(x)
- Будет истинно A, F(x)
Используются в искусственном интеллекте и онтологиях для моделирования временных аспектов.