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

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

Определение доказательства в классическом исчислении предикатов идентично определению доказательства в классическом исчислении высказываний, поэтому завершённое доказательство понимается как завершённый вывод из пустого множества неисключённых посылок.

Пошаговый переход от одной формулы к другой осуществляется в исчислении предикатов посредством выполнения всех правил вывода, применяемых в исчислении высказываний, к которым добавляются кванторные правила вывода, а именно: 1) введения, 2) исключения кванторов.

К дедуктивным принципам введения кванторов относятся правила:

1.1. — введения квантора общности (обозначим символом «_в»), выражаемое схемой:

А(x/ y, z₁, …, z_n)

^{______________________} , где y — абсолютное ограничение, z₁, …, z_n — ограничение.

xA(x, z₁, …, z_n)

1.2. — введения квантора существования (обозначим символом «_в»), выражаемое схемой:

А(x/t)

^___________ .

xА(x)

2.1.— исключения квантора общности (обозначим символом «_и»), выражаемое схемой:

xА(x)

^___________ .

А(x/t)

2.2. — исключения квантора существования (обозначим символом «_и»), выражаемое схемой:

xА(x, z₁, …, z_n)

^{______________________} , где y — абсолютное ограничение, z₁, …, z_n — ограничение.

А(x/ y, z₁, …, z_n)

В правилах «введения квантора существования» и «исключения квантора общности» запись A(x/t) означает результат правильного замещения термом t всех имеющихся в формуле A(x) свободных вхождений предметной переменной x.

• Пример

Пусть формула A(x) является записью выражения x(P²(x,y)Q²(x,z)). Допустим, что универсумом рассуждения является множество городов, вместо свободной переменной y подставляется терм — предметная постоянная, имеющая значение «Омск», вместо z — предметная постоянная, имеющая значение «Тара», и P² — предикаторная постоянная, имеющая значение «старше», а Q² — предикаторная постоянная, имеющая значение «моложе», тогда мы получаем правильную подстановку, поскольку суждение «Существуют города, такие что они старше Омска, но моложе Тары» истинно.

Но в силу того, что рассматриваемая формула x(P²(x,y)Q²(x,z)), являясь выполнимой, не является общезначимой формулой логики предикатов, можно осуществить и такую подстановку термов вместо свободных переменных y и z, что данная формула будет иметь всегда ложное значение.

Допустим, что универсумом рассуждения является множество людей, вместо свободной переменной y подставляется сложный функциональный терм, имеющий значение «являться отцом человека», вместо z — сложный функциональный терм, имеющий значение «являться предком человека», и P² — предикаторная постоянная, имеющая значение «младше», а Q² — предикаторная постоянная, имеющая значение «старше», тогда получаем неправильную подстановку, поскольку суждение «Существуют люди, такие что они старше отцов, но моложе потомков» является ложным всегда.

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

Правильной называется такая подстановка терма t вместо всех свободных вхождений предметной переменной x формулы А(x), при которой ни одна входящая в этот терм переменная не окажется связанной на местах, где этот терм появляется в результате подстановки.

Запись А(x/ y, z₁, …, z_n) в правилах «введения квантора общности» и «исключения квантора существования» есть фиксация частного случая правильной подстановки предметной переменной y на место всех свободных вхождений предметной переменной x в выражении А(x, z₁, …, z_n).

Содержащиеся в правилах «введения квантора общности» и «исключения квантора существования» указания вида «y — абсолютное ограничение; z₁, …, z_n — ограничение» обусловлены тем, что с содержательной точки зрения свободные предметные переменные являются пробегающими по универсуму рассуждения (некоторого множества предметов), принимая в выбранном универсуме любые значения (в таком случае они используются в интерпретации всеобщности). Но будучи включёнными в состав формул логики предикатов предметные переменные иногда не выполняют данную роль, поскольку не выступают в качестве знаков, обозначающих именно любой объект универсума рассуждения (т. е. используются в интерпретации всеобщности). Таким образом, имеют место два возможных случая функционирования предметной переменной в составе формул.

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

• Пример

В выражении x + y = y + x, представляющем собой закон перестановочности сложения, переменные x и y употреблены в интерпретации всеобщности, так как это соотношение истинно при любых значениях x и y.

Другую ситуацию имеем в том случае, когда переменные входят в состав, например, математических уравнений. Так, в выражении x + 5 = 8 переменная x уже не используется в интерпретации всеобщности, так как не обозначает произвольный объект из универсума. Напротив, возможные значения для x строго фиксированы, т. е. ограничены условием данного утверждения. В этом случае говорят, что переменная использована в условной интерпретации.

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

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

Четвёртая эвристика заключается в применении первой и второй эвристик для выбора посылок после того, как применение всех шагов по первой эвристике привело к формуле вида xA или xA.

• Пример

Обоснованием утверждения о выводимости - xP(x,y,a)xP(x,y,a) будет:

_______ _______________________

1. xP(x,y,a) — пос. (1 эвристика). 2. P(x,y,a) — пос. (4 эвристика). 3. xP(x,y,a) — в, 2. 4. P(x,y,a) — в, 1, 3. 5. P(x,y,a) — и, 4. 6. xP(x,y,a) — в, 5, x — абс. огр.; y — огр. 7. xP(x,y,a)xP(x,y,a) — в, 6.