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

Вывод в исчислении предикатов — это не пустая и конечная последовательность формул, каждая из которых является либо посылкой, либо получена из предыдущих формул согласно одному из дедуктивных принципов так, что после применения правил É_в и Ø_в все формулы, начиная с последней посылки и вплоть до результата применения данного правила, не используются в дальнейших шагах построения вывода, при этом ни одна переменная не ограничивает сама себя и ни одна индивидуальная переменная не ограничивается абсолютно более одного раза. В том случае, если никакая абсолютно ограничивавшаяся в выводе переменная не встречается свободно в неисключённых посылках и заключении, имеет место завершённый вывод. Определение доказательства в классическом исчислении предикатов идентично определению доказательства в классическом исчислении высказываний, поэтому завершённое доказательство понимается как завершённый вывод из пустого множества неисключённых посылок. Пошаговый переход от одной формулы к другой осуществляется в исчислении предикатов посредством выполнения всех правил вывода, применяемых в исчислении высказываний, к которым добавляются кванторные правила вывода, а именно: 1) введения, 2) исключения кванторов. К дедуктивным принципам введения кванторов относятся правила:

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

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

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

"x A (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₁, …, zg_n)

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

 

V Пример

Пусть формула 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 — ограничение» обусловлены тем, что с содержательной точки зрения свободные предметные переменные являются пробегающими по универсуму рассуждения (некоторого множества предметов), принимая в выбранном универсуме любые значения (в таком случае они используются в интерпретации всеобщности). Но будучи включёнными в состав формул логики предикатов предметные переменные иногда не выполняют данную роль, поскольку не выступают в качестве знаков, обозначающих именно любой объект универсума рассуждения (т. е. используются в интерпретации всеобщности). Таким образом, имеют место два возможных случая функционирования предметной переменной в составе формул. Свободная индивидная переменная используется в формуле в интерпретации всеобщности тогда и только тогда, когда в составе этой формулы данная предметная переменная трактуется как знак, обозначающий любой объект из универсума рассуждения.

 

V Пример

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

 

Используя вышеозначенный перечень и истолкование правил вывода, обратим внимание на тот факт, что понятия вывода и доказательства в классической логике предикатов остаются формально теми же, что и в классической логике высказываний, поэтому в логике предикатов работают все правила вывода логики высказываний, но к ним добавляются правила квантификации. По этим же причинам в качестве эвристик в исчислении логики предикатов используются все эвристики исчисления логики высказываний, но к ним добавляется ещё одна, четвёртая эвристика. 4- я эвристика заключается в применении 1-й и 2-й эвристик для выбора посылок после того, как применение всех шагов по первой эвристике привело к формуле вида "xA или $xA.

 

V Пример

Обоснованием утверждения о выводимости |- Ø$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.

Разбирая содержание данного параграфа, следует осознаваться его связанность с силлогистикой Аристотеля, о чём было сказано ранее, равно как данный параграф не следует брать в отрыве от материала, также изложенного ранее в связи с операциями логики классов (булевой алгебры).

Контрольные вопросы

I. Каковы функции пропозициональных 1) переменных и 2) связок?

II. Что является законом классической логики высказываний?

III. В чём заключаются общие принципы построения истинностных таблиц?

VI. Каковы содержание и объём понятия формулы исчисления высказываний?

V. На какие виды подразделяются правила вывода логики высказываний?

VI. Каковы эвристики и их последовательность в выводах логики предикатов?

VII. Возможно ли формализовать средствами логики высказываний суждение «Для всякого предмета из множества металлов существует такой предмет этого множества, что эти предметы находятся в отношении подобия» и почему?

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

IX. Чем сходны и чем различаются классические исчисления логики предикатов и логики высказываний?

ЧАСТЬ IV