Логика предикатов

Логика предикатов

В сравнении с логикой высказываний логика предикатов является более сложным фрагментом. Высказывания обычно связаны с некоторым единичным объектом. Примером могут служить высказывания, связанные с Петром. О таких высказываниях можно однозначно сказать, истинны они или ложны. Логика предикатов формализует высказывания, связанные с множеством объектов. Истинность таких высказываний может зависеть от значений ряда предметных переменных. Простейшим примером является отношение "больше". Высказывание $$X > Y$$ истинно для некоторых пар предметных переменных (например, для пары чисел 5 и 3) и ложно для некоторых других значений этих переменных (например, для пары чисел 3 и 3). Отношение "больше" можно определить не только на числах, но и для других предметных областей, например, рассматривать отношение "больше" в животном мире. Тогда утверждение $$X > Y$$ справедливо, если $$X$$ имеет значение "слон", а $$Y$$ – "тигр", при других значениях, например для пары <слон, кит>, утверждение "слон больше кита" следует считать ложным.

Поскольку мы обсуждаем логику предикатов, то следует определить понятие "предикат". Если задано отношение, то с ним можно связать предикат.

Предикат – это функция, определенная на кортежах отношения. Функция принимает значение Истина, если кортеж принадлежит отношению, и Ложь – в противном случае. Поскольку значением предиката может быть только одно из двух логических значений, то над ними, также как над логическими переменными, определены все логические операции – конъюнкция, дизъюнкция и другие операции. Пример: $$X > Y U < V$$.

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

Поскольку формулы логики предикатов позволяют формализовать суждения о множествах, то в этих формулах, наряду с логическими функциями разрешается использовать два квантора – квантор всеобщности и квантор существования.

Квантор всеобщности, навешенный на формулу $$Ф(x)$$, где $$x$$ – предметная переменная – элемент некоторого множества $$X$$, указывает, что формула $$Ф$$ должна выполняться для всех $$x \in X$$. Записывается формула с квантором всеобщности следующим образом: $$\forall xФ(x)$$

Квантор существования, навешенный на формулу $$Ф(x)$$, где $$x$$ – предметная переменная – элемент некоторого множества $$X$$, указывает, что формула $$Ф$$ должна выполняться, по крайней мере, для одного из элементов $$x \in X$$. Записывается формула с квантором существования следующим образом: $$\exists xФ(x)$$.

Пример: Утверждение "Все греки – люди" может быть записано следующей формулой логики предикатов:

$$\forall x(x \in \{греки \} \to x \in \{люди \})$$

В дальнейших уроках мы ограничимся рассмотрением только формул логики высказываний.