ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ
-
Рубрика: Математика
-
-
Скопировать библиографическую ссылку:
ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ, общее название формальных систем, служащих для формализации логических умозаключений, в которых учитывается как логическая структура суждений (т. е. каким образом данное суждение получено из других с помощью логических операций), так и их субъективно-предикативная структура, т. е. связь между субъектом суждения (о чём говорится в данном суждении) и предикатом (что говорится о субъекте). При этом для логич. анализа суждений наряду с такими логич. операциями, как дизъюнкция, конъюнкция, импликация, отрицание, эквивалентность, используются кванторы, а субъективно-предикативная структура уточняется с помощью понятия предиката.
Поскольку в математич. логике интересуются лишь структурой суждений, отвлекаясь от их конкретного смысла, а также во избежание двусмысленностей, свойственных естественным языкам, для построения логики предикатов используется формализованный язык, алфавит которого обычно содержит четыре группы символов: 1) предикатные переменные – выражения вида , где $m$ и $n$ – неотрицательные целые числа; 2) предметные переменные $x_1,x_2,\dots$; 3) логич. символы $\&$ (конъюнкция), $∨$ (дизъюнкция), $→$ (импликация), $≈$ (эквивалентность), $¬$ (отрицание), $∃$ (квантор существования), $∀$ (квантор всеобщности); 4) вспомогательные символы $(, )$ (скобки) и $,$ (запятая). Выражение $P_n^m$ называется $m$-местной предикатной переменной, $0$-местные предикатные переменные – пропозициональными переменными.
Элементарной формулой называется всякая пропозициональная переменная, а также любое выражение вида $P(y_1,...,y_m)$, где $P$ – к.-л. $m$-местная предикатная переменная ($m>0$), а $y_1,...,y_m$ – произвольные предметные переменные. Из элементарных формул следующим образом строятся предикатные формулы: 1) все элементарные формулы суть формулы; 2) если $𝔄$ и $𝔅$ – формулы, то выражения $(𝔄\&𝔅)$, $(𝔄∨𝔅)$, $(𝔄→𝔅)$, $(𝔄≈𝔅)$, $¬𝔄$ считаются формулами; 3) если $𝔄$ – формула, $x$ – предметная переменная, то $∀x𝔄$ и $∃x𝔄$ суть формулы. Напр., $$P_0^1,\,P_1^0(x),\,∃x_1P_1^2(x_1,x_3),\\(P_0^1(x_2)\&∃x_1P_1^2(x_1,x_2))$$ являются предикатными формулами.
Часть формулы $𝔄$, которая сама является формулой, называется подформулой формулы $𝔄$ . Областью действия квантора $∀y$ или $∃y$ в формуле $𝔄$ называется такая её подформула $𝔅$, что $∀y𝔅$ или $∃y𝔅$ является подформулой формулы $𝔄$. Вхождение переменной $y$ в формулу $𝔄$ называется связанным, если оно есть вхождение в квантор $∀y$ или $∃y$ либо в область действия одного из этих кванторов. Всякое вхождение переменной $y$, не являющееся связанным, называется свободным. Напр., в формуле $(∀x_1P_0^1(x_1)\&P_1^1(x_1))$ первые два вхождения переменной $x_1$ – связанные, а третье – свободное. Переменная $y$ называется свободной переменной формулы $𝔄$, если она имеет свободные вхождения в $𝔄$.
Говорят, что задана интерпретация формулы $𝔄$ на непустом множестве $M$, если каждой свободной переменной формулы $𝔄$ сопоставлен некоторый элемент из $M$, а каждой $m$-местной предикатной переменной из $𝔄$ – некоторый $m$-местный предикат на $M$. Истинностное значение $|𝔄|$ формулы $𝔄$ в данной интерпретации определяется индукцией по построению формулы $𝔄$. Если $𝔄$ имеет вид $P(y_1,...,y_m)$, то её значением является значение предиката, сопоставленного предикатной переменной $P$, на наборе значений переменных $y_1,...,y_m$. Если $𝔄$ имеет вид $¬𝔅$, то $|𝔄|= И$ («истина») тогда и только тогда, когда $|𝔅|=Л$ («ложь»). Аналогично, в соответствии с истинностными значениями для логич. операций $\&$, $∨$, $→$, $∼$ определяются значения формул вида $(𝔄\&𝔅)$, $(𝔄∨𝔅)$, $(𝔄→𝔅)$, $(𝔄∼𝔅)$ через значения формул $𝔄$ и $𝔅$. Напр., $|𝔄\&𝔅|=И$ тогда и только тогда, когда $|𝔄|=И$ и $|𝔅|=И$. Значение формулы $∀y𝔄$ есть $Л$ в том и только в том случае, когда $|𝔄|=Л$ в некоторой интерпретации, полученной из данной приписыванием значения переменной $y$. Значение формулы $∃y𝔄$ есть $И$, если $|𝔄|=И$ в некоторой интерпретации, полученной из данной приписыванием значения переменной $y$. Если $|𝔄|=И$, то говорят, что формула $𝔄$ истинна в данной интерпретации.
Предикатная формула называется общезначимой на множестве $M$, если она истинна в любой интерпретации на $M$. Напр., формула $$∃x_1P_0^1(x_1)\rightarrow \forall x_2 P_0^1(x_2))$$ общезначима на любом множестве, содержащем ровно один элемент, и не будет общезначимой на $M$, если в $M$ есть хотя бы два элемента. Формула называется общезначимой, или тавтологией, или тождественно истинной, если она общезначима на любом непустом множестве. Тот факт, что формула $𝔄$ общезначима, обозначают так: $|=𝔄$.
Целью логики предикатов является описание класса всех общезначимых формул. Одним из способов такого описания является построение П. и., т. е. исчисления, аксиомами и выводимыми объектами которого являются предикатные формулы. При этом в качестве аксиом выбираются некоторые общезначимые формулы, а правила вывода позволяют из общезначимых формул получать новые общезначимые формулы.
Обычно классич. П. и. строятся на основе того или иного варианта высказываний исчисления: аксиомы классич. исчисления высказываний считаются схемами аксиом П. и., т. е. любая предикатная формула, полученная из некоторой аксиомы исчисления высказываний подстановкой в неё к.-л. предикатных формул вместо пропозициональных переменных, объявляется аксиомой П. и. Напр., из аксиомы исчисления высказываний $A→(B→A)$ таким образом получается аксиома П. и. $$(\forall x_2 P_0^1(x_2)\rightarrow (P_3^0\rightarrow \forall x_2 P_0^1(x_2))).$$ К этим аксиомам добавляются две новые схемы аксиом м $$(∀x𝔄(x)⊃𝔄(y))\,\,и\,\,(𝔄(y)⊃\exists x𝔄(x)),$$$𝔄(x)$ – произвольная предикатная формула, в которой переменная $x$ не находится в области действия кванторов $∀y$ и $∃y$, а формула $𝔄(y)$ получена заменой в $𝔄(x)$ каждого свободного вхождения переменной $x$ на $y$. Правилами вывода П. и. являются правило модус поненс и следующие два правила: $∀$-правило, позволяющее из формулы $(𝔅→𝔄)$ получить формулу $(𝔅→∀x𝔄)$, где $𝔄$ и $𝔅$ – произвольные предикатные формулы, причём $B$ не содержит свободно переменную $x$, и $∃$-правило, позволяющее при тех же предположениях относительно формул $𝔄$, $𝔅$ и переменной $x$ перейти от формулы $(𝔄→𝔅)$ к формуле $(∃x𝔄→𝔅)$.
Выводом формулы $𝔄$ в П. и. называется конечная последовательность формул $𝔄_1,...,𝔄_m$ такая, что каждая из формул $𝔄_i$ либо есть аксиома, либо получается из некоторых предшествующих ей формул по одному из перечисленных правил вывода, и $𝔄_m$ совпадает с $𝔄$. Формула $𝔄$ выводима в П. и. или является теоремой, если можно построить вывод этой формулы. Согласно теореме Гёделя о полноте, все общезначимые предикатные формулы и только они выводимы в классич. исчислении предикатов.
Дедуктивный аппарат П. и., т. е. система аксиом и правила вывода, используется при построении логико-математич. исчислений (напр., формальной арифметики и аксиоматической теории множеств).