2.3 Исчисление предикатов первого порядка.

2.3.1 Основные определения

Термин «первого порядка» означает, что в этой теории кванторы допускаются только по переменным и не допускаются по функциональным и предикатным символам. Кроме того, запрещены предикаты, которые в качестве своих аргументов имеют другие предикаты.

В логике высказываний атом рассматривается как единое целое, его структура и состав не анализируется. Однако, есть много умозаключений, которые не могут быть представлены таким простым способом. Например, рассмотрим следующее умозаключение:

Каждый человек смертен.

Так как Конфуций человек, то он смертен.

Приведенное рассуждение интуитивно корректно, однако, если мы введем обозначения:

P: Каждый человек смертен,

Q: Конфуций – человек,

R: Конфуций смертен,

то R не есть логическое следствие P и Q в рамках логики высказываний.

В логике предикатов первого порядка по сравнению с логикой высказываний имеет еще три логических понятия: термы, предикаты и кванторы.

Множество T базовых элементов исчисления предикатов включает в себя следующие символы:

1. Константы – это обычно строчные буквы a, b, c… или осмысленные имена объектов;

2. Переменные – это обычно строчные буквы x, y, z, …, возможно с индексами;

3. Функции – это обычно строчные буквы f, g, h,… или осмысленные слова из строчных букв;

4. Предикаты – это обычно прописные буквы P, Q, R … или осмысленные слова из прописных букв;

5. Логические связки: отрицание, дизъюнкция, конъюнкция, импликация, эквивалентность;

6. Кванторы всеобщности и существования - ",$;

7. Открывающая и закрывающая скобка.

Всякая функция или предикатный символ имеет определенное число аргументов. Если функция fимеетnаргументов, тоf называетсяn- местной функцией. Аналогично, если предикатP имеетnаргументов, тоP называетсяn- местным предикатом.

Определение 6. Термы определяются рекурсивно следующим образом:

• Константа есть терм;

• Переменная есть терм;

• Если f есть n- местная функция и t₁, t₂,…,t_n – термы, то f (t₁, t₂,…,t_n) – терм;

• Никаких термов, кроме порожденных применением указанных выше правил, нет.

Определение 7. ПредикатP(t₁, t₂,…,t_n)есть логическая функция, определенная на множестве термов t₁, t₂,…,t_n, при фиксированных значениях которых она превращается в высказывания со значением истина (И) или ложь(Л).

Определение 8. Если P – n- местный предикат и t₁, t₂,…,t_n – термы, то P(t₁, t₂,…,t_n) – атом.

Для построения формул в исчислении предикатов используются пять логических связок и два квантора: "- всеобщности и$ - существования. Еслиx– переменная, то ("x) читается как «для всехx», «для каждогоx», «для любогоx», тогда как ($x) читается как « существуетx», «для некоторыхx», «по крайней мере, для одногоx».

Пример 1: запишем следующие утверждения:

1. Каждое рациональное число есть вещественное число.

2. Существует число, которое является простым.

3. Для каждого числа x существует такое число y , что x<y.

Обозначим «x есть простое число»черезP(x),«x есть рациональное число» черезQ(x),«x есть вещественное число»черезR(x) и«x меньше y»черезМЕНЬШЕ (x, y).

Тогда указанные выше утверждения могут быть записаны соответственно выражениями:

1. ("x) (Q(x)® R(x)),

2. ($x) P(x),

3. ("x) ($y) МЕНЬШЕ (x, y).

Каждое из выражений 1, 2, 3называется формулой. Прежде чем дать формальное определение формулы в логике предикатов, следует установить различие междусвязанными переменнымиисвободными переменнымии определитьобласть действия квантора, входящего в формулу, как ту формулу, к которой этот квантор применяется. Так, область действия квантора существования в выражении3 естьМЕНЬШЕ (x, y), а область действия квантора всеобщности в выражении3есть($y) МЕНЬШЕ (x, y).

Определение 9.Вхождение переменнойxв формулуF называется связанным тогда и только тогда, когда оно совпадает с вхождением в квантор ("xF) или ($yF). Формула, к которой применяется квантор по данной переменной, называетсяобластью действия этого квантора. Вхождение переменной в формулу свободно тогда и только тогда, когда оно не находится в области действия какого-либо квантора. Формула, не содержащая свободных переменных, называетсязамкнутойи представляет собойвысказывание.

Пример2.

P(x, y) Ù R(z)® ("x)(R(x) Ù Q(y)). В этом примере первое вхождение переменной x является свободным, второе – связанным, первое вхождение переменной y является свободным, второе – связанным, единственное вхождение переменной z является свободным.

Отметим, что переменная в формуле может быть свободной и связанной одновременно.