Логика предикатов первого порядка: Кванторы и формализация языка
Исчисление высказываний (булева алгебра) имеет существенный недостаток: оно работает только с простыми, неделимыми утверждениями. Оно не способно выразить структуру внутри предложения или проанализировать свойства объектов. Например, из утверждений «Все люди смертны» и «Сократ — человек» булева логика не может вывести, что «Сократ смертен». Эту фундаментальную проблему дискретной математики решает логика предикатов (исчисление предикатов) первого порядка.
Предикат — это логическая функция (n-арное отношение), зависящая от предметных переменных, которая принимает значение «Истина» (True) или «Ложь» (False) в зависимости от переданных аргументов. Например, предикат Больше(X, Y) истинен для X=5 и Y=3, но ложен для X=2 и Y=8. Предикаты позволяют описывать свойства объектов и отношения между ними.
Революционным нововведением логики предикатов стало появление кванторов, которые связывают предметные переменные:
- Квантор всеобщности (∀ - перевернутая A, от слова All): означает «для всех», «для любого», «каждый». Выражение (∀x)P(x) означает, что свойство P выполняется абсолютно для каждого объекта x в рассматриваемой предметной области.
- Квантор существования (∃ - перевернутая E, от слова Exists): означает «существует», «найдется хотя бы один». Выражение (∃x)P(x) означает, что есть как минимум один объект x, для которого истинно свойство P.
Кванторы тесно связаны с законами де Моргана. Отрицание всеобщности эквивалентно существованию контрпримера: ¬(∀x)P(x) ≡ (∃x)¬P(x) (утверждение «Неверно, что все птицы летают» эквивалентно «Существует хотя бы одна птица, которая не летает»).
Логика предикатов первого порядка (где кванторы применяются только к переменным-объектам, но не к самим предикатам) стала фундаментом для теории баз данных. Язык реляционных запросов SQL математически базируется на реляционном исчислении кортежей, которое является прямым приложением исчисления предикатов. Любой SELECT-запрос можно строго записать с помощью кванторов и логических связок.
Кроме того, логика предикатов породила целую парадигму логического программирования. В языке Prolog программа не содержит инструкций шаг за шагом (как в C++ или Python). Программист просто описывает базу фактов (предикатов) и логические правила (аксиомы). После этого он задает системе вопрос в виде целевого предиката с переменными, и встроенная машина вывода с помощью алгоритма унификации и механизма возврата (backtracking) сама ищет значения переменных, которые делают этот предикат истинным.
