Исчисление предикатов первого порядка
Вывод в исчислении предикатов — это не пустая и конечная последовательность формул, каждая из которых является либо посылкой, либо получена из предыдущих формул согласно одному из дедуктивных принципов так, что после применения правил Éв и Øв все формулы, начиная с последней посылки и вплоть до результата применения данного правила, не используются в дальнейших шагах построения вывода, при этом ни одна переменная не ограничивает сама себя и ни одна индивидуальная переменная не ограничивается абсолютно более одного раза. В том случае, если никакая абсолютно ограничивавшаяся в выводе переменная не встречается свободно в неисключённых посылках и заключении, имеет место завершённый вывод. Определение доказательства в классическом исчислении предикатов идентично определению доказательства в классическом исчислении высказываний, поэтому завершённое доказательство понимается как завершённый вывод из пустого множества неисключённых посылок. Пошаговый переход от одной формулы к другой осуществляется в исчислении предикатов посредством выполнения всех правил вывода, применяемых в исчислении высказываний, к которым добавляются кванторные правила вывода, а именно: 1) введения, 2) исключения кванторов.К дедуктивным принципам введения кванторов относятся правила:
1.1. — введения квантора общности (обозначим символом «"в»), выражаемое схемой:
А(x/ y, z1, …, zn)
______________________ , гдеy— абсолютное ограничение, z1, …, zn — ограничение.
"xA(x, z1, …, zn)
1.2. — введения квантора существования(обозначим символом «$в»), выражаемое схемой:
А(x/t)
___________ .
$xА(x)
2.1.— исключения квантора общности (обозначим символом «"и»), выражаемое схемой:
"xА(x)
___________ .
А(x/t)
2.2. — исключения квантора существования(обозначим символом «$и»), выражаемое схемой:
$xА(x, z1, …, zn)
______________________ , гдеy— абсолютное ограничение, z1, …, zn — ограничение.
А(x/ y, z1, …, zgn)
В правилах «введения квантора существования» и «исключения квантора общности» запись A(x/t)означает результат правильного замещения термом t всех имеющихся в формуле A(x) свободных вхождений предметной переменной x.
V Пример
Пусть формула A(x) является записью выражения $x(P2(x,y)ÉQ2(x,z)). Допустим, что универсумом рассуждения является множество городов, вместо свободной переменной y подставляется терм — предметная постоянная, имеющая значение «Омск», вместо z — предметная постоянная, имеющая значение «Тара», и P2 — предикаторная постоянная, имеющая значение «старше», а Q2 — предикаторная постоянная, имеющая значение «моложе», тогда мы получаем правильную подстановку, поскольку суждение «Существуют города, такие что они старше Омска, но моложе Тары» истинно.
Но в силу того, что рассматриваемая формула $x(P2(x,y)ÉQ2(x,z)), являясь выполнимой, не является общезначимой формулой логики предикатов, можно осуществить и такую подстановку термов вместо свободных переменных yи z, что данная формула будет иметь всегда ложное значение. Допустим, что универсумом рассуждения является множество людей, вместо свободной переменной y подставляется сложный функциональный терм, имеющий значение «являться отцом человека», вместо z — сложный функциональный терм, имеющий значение «являться предком человека», и P2 — предикаторная постоянная, имеющая значение «младше», а Q2 — предикаторная постоянная, имеющая значение «старше», тогда получаем неправильную подстановку, поскольку суждение «Существуют люди, такие что они старше отцов, но моложе потомков» является ложным всегда. В данном случае свободно входящая в подставляемые сложные функциональные термы переменная «человек» оказалась в результате этой подстановки связанной (попала в область действия квантора), что обусловило семантическую некорректность формулы. Правильной называется такая подстановка терма t вместо всех свободных вхождений предметной переменной x формулыА(x), при которой ни одна входящая в этот терм переменная не окажется связанной на местах, где этот терм появляется в результате подстановки. Запись А(x/ y, z1, …, zn) в правилах «введения квантора общности» и «исключения квантора существования» есть фиксация частного случая правильной подстановки предметной переменной y на место всех свободных вхождений предметной переменной x в выражении А(x, z1, …, zn). Содержащиеся в правилах «введения квантора общности» и «исключения квантора существования» указания вида «y — абсолютное ограничение; z1, …, zn — ограничение» обусловлены тем, что с содержательной точки зрения свободные предметные переменные являются пробегающими по универсуму рассуждения (некоторого множества предметов), принимая в выбранном универсуме любые значения (в таком случае они используются в интерпретации всеобщности). Но будучи включёнными в состав формул логики предикатов предметные переменные иногда не выполняют данную роль, поскольку не выступают в качестве знаков, обозначающих именно любой объект универсума рассуждения (т. е. используются в интерпретации всеобщности). Таким образом, имеют место два возможных случая функционирования предметной переменной в составе формул. Свободная индивидная переменная используется в формуле в интерпретации всеобщности тогда и только тогда, когда в составе этой формулы данная предметная переменная трактуется как знак, обозначающий любой объект из универсума рассуждения.
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