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

3.1. Основные понятия

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

Если неизвестны объекты высказывания или отношения между объектами высказывания, то такое высказывание называют высказывательной функцией. Высказывательную функцию иначе называют предикатом и обозначают символом Р(…). Аргументами предиката являются предметные переменные (обозначают строчными буквами латиницы {x,y,z}, при необходимости, с индексами) и предметные постоянные (обозначаются строчными буквами латиницы {a,b,…}, возможно, с индексами).

Примеры предикатов:

1) Р₁(х):= «х – простое число», или «быть простым числом»,

2) Р₂(6,y):= «y меньше 6»,

3) Р₃(6,y,z):= «z есть частное от деления 6 на y».

Очевидно, нельзя судить об истинности или ложности данных высказываний.

Предикаты бывают двух видов:

1) Одноместные - имеют аргументом одну предметную переменную и выражают свойства предметных переменных высказывательной функции (в примере 1).

2) Многоместные - могут иметь аргументами несколько предметных переменных и/или предметных постоянных; выражают отношения между объектами высказывательной функции (в примерах 2 и 3).

Высказывательная функция становится высказыванием F при замене предметных переменных предметными постоянными, например:

· при х=3 Р₁(х):= «3 – простое число»

· при х=4 Р₁(х):= «4 – простое число»

· при y=2 Р₂(6,y):= «2 меньше 6»

· при y=7 Р₂(6,y):= «7 меньше 6»

· при y=2, z=3 Р₃(6,y,z):= «3 есть частное от деления 6 на 2»

· при y=2, z=5 Р₃(6,y,z):= «5 есть частное от деления 6 на 2»

По этим примерам видно, что при присвоении предметной переменной значения можно судить об истинности предиката.

Множество, на котором заданы предметные переменные и предметные постоянные, называют областью определения предиката или универсумом.

Множество значений предметных переменных, на котором предикат принимает значение «истины», называют множеством истинности предиката.

Суждение, в котором утверждается или отрицается наличие каких-либо свойств или отношений у части предметных переменных, называют частным суждением. Для формального описания таких суждений используют логический оператор «∃_x» - квантор существования. Предикат Р записывают после квантора существования в круглых скобках (они определяют область действия квантора):

∃_xi(Р(x₁, x₂, …, х_i,…, x_n))

На естественном языке такая запись означает: «существуют такие предметные переменные х_i, для которых Р(х_i) истинно».

Частное суждение по нескольким переменным требует указания кванторов существования для каждой переменной перед предикатом. Например:

∃_x∃_y∃_z...(P(x, y, z,...)).

Суждение, в котором утверждается или отрицается наличие каких-либо свойств для всех предметных переменных области определения или отношений между ними, называют общими суждениями. Как правило, эти суждения в естественном языке отмечают словами «все», «каждый», «любой» и т.п. Для формального описания таких суждений используют логический оператор «∀_x» - квантор всеобщности. Предикат записывают после квантора всеобщности в круглых скобках (они определяют область действия квантора):

∀_xi(Р(x₁,x₂, …, x_n)).

На естественном языке эта формальная запись означает «для всех предметных переменных x_i значение Р(х_i) истинно».

Общее суждение по нескольким переменным требует указания кванторов существования для каждой переменной перед предикатом. Например:

∀_x∀_y∀_z…(Р(x,y, z…)).

Существуют предикаты, для которых область определения по различным предметным переменным ограничивают различными кванторами.

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

Между элементами области определения предиката могут быть заданы функциональные отношения. На это указывает функциональный символ: f(x₁, x₂,..., x_n).

Дата добавления: 2014-01-04