Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Формализованное исчисление предикатов

Формализованное исчисление предикатов


Задача формализованного исчисления предикатов (ФИП) та же, что и формализованного исчисления высказываний (ФИВ), — дать аксиоматическую теорию совокупности всех общезначимых формул (тавтологий) логики предикатов, т. е. научиться выводить (доказывать) все такие формулы и только их, исходя из выбранной системы аксиом и с использованием выбранных правил вывода.


Язык формализованного исчисления предикатов


Алфавит исчисления предикатов состоит из предметных переменных [math]x_1,x_2,\ldots[/math], предметных констант (символы выделенных элементов) [math]c_1,c_2,\ldots[/math], предикатных букв [math]P'_1,P'_2,\ldots,P'_k,\ldots[/math], функциональных букв [math]f''_1,f''_2, \ldots, f''_{\ell},\ldots[/math], а также знаков логических связок [math]\lnot[/math] и [math]\land[/math], кванторов [math]\forall[/math] и [math]\exists[/math] и скобок [math](,)[/math]. При этом верхние индексы предикатных и функциональных букв указывают число аргументов соответственно предиката или функции, которые могут быть подставлены вместо этих букв.


Понятие формулы определяется в два этапа. Сначала определяются термы. Ими являются отдельно взятые предметные переменные и константы, а также выражения вида [math]f^n(t_1,\ldots,t_n)[/math], где [math]f^n[/math] — n-местный функциональный символ; [math]t_1,\ldots,t_n[/math] — термы. Наконец, определяются формулы:


а) если [math]P_n[/math] — предикатная буква, [math]t_1,\ldots,t_n[/math] — термы, то [math]P_n(t_1,\ldots,t_n)[/math] — формула; при этом все вхождения переменных в эту формулу называются свободными;


б) если [math]F_1,\,F_2[/math] — формулы, то формулами являются [math]\lnot F_1,\,(F_1\to F_2)[/math]; причем все вхождения переменных, свободные в [math]F_1,\,F_2[/math], являются свободными и в формулах указанных видов; кроме того, можно считать, что в [math]F_1[/math] и [math]F_2[/math] нет предметных переменных, которые связаны в одной формуле и свободны в другой;


в) если [math]F_x[/math] — формула, содержащая свободные вхождения переменной [math]x[/math], то [math](\forall x)(F(x))[/math] и [math](\exists x)(F(x))[/math] — формулы; при этом вхождения переменной [math]x[/math] в них называются связанными; вхождения же всех остальных предметных переменных в эти формулы остаются свободными (связанными), если они были свободными (связанными) в формуле [math]F(x)[/math] (формула [math]F(x)[/math] называется областью действия квантора);


г) никаких других формул, кроме тех, которые строятся по правилам а, б, в, нет.


Из этого определения ясно, что вхождения переменных в формулу обладают следующими свойствами: свободные и связанные переменные обозначены разными буквами (если это не так, то ясно, что, не нарушая смысла формулы, можно переобозначить в ней связанные переменные); если какой-либо квантор находится в области действия другого квантора, то переменные, связанные этими кванторами, обозначены разными буквами (если это не так, то ясно, что, не нарушая смысла формулы, можно переобозначить в ней соответствующие переменные). Нарушения этих свойств называются коллизией переменных. Определенные формулы называются формулами первой ступени, так как в них разрешается навешивать кванторы только по предметным переменным, а по функциональным и предикатным — не разрешается. Возникающее исчисление предикатов называют исчислением предикатов первой ступени или узким исчислением предикатов (в отличие от расширенного исчисления предикатов), сокращенно — УИП.


Совокупность [math]G=\{c_1,c_2,\ldots;~ f_1,f_2,\ldots;~ P_1,P_2,\ldots\}[/math] называется сигнатурой рассматриваемого исчисления предикатов. Если в сигнатуре отсутствуют функциональные символы, (а значит, функциональные термы), то возникающее исчисление предикатов называется чистым исчислением предикатов. Оно строится для произвольной предметной области и не зависит от взаимосвязи между предметами в этой области. Это чисто логическая теория. Именно о таком чистом исчислении предикатов и пойдет речь. Если же такие связи имеются и они описываются функциями на этой предметной области, то логика проникает в эту область и в эти связи и возникает логическая теория соответствующей математической Дисциплины, или, как говорят, некая формальная математическая теория.




Система аксиом исчисления предикатов


Указанная система состоит из двух групп из которых первая — это аксиомы формализованного исчисления высказываний:


[math]\begin{aligned}&\mathsf{(A1)}\colon\quad F\to (G\to F);\\ &\mathsf{(A2)}\colon\quad \bigl(F\to (G\to F)\bigr)\to \bigl((F\to G)\to (F\to H)\bigr);\\ &\mathsf{(A3)}\colon\quad (\lnot G\to\lnot F)\to \bigl((\lnot G\to F)\to G\bigr);\end{aligned}[/math]


где под [math]F,\,G,\,H[/math] понимаются уже любые формулы исчисления предикатов.


Вторая группа аксиом (схем аксиом) — это собственно предикатные аксиомы (схемы аксиом), т.е. аксиомы с кванторами. Выберем в качестве них следующие (называемые аксиомами Бернайса):


[math]\begin{aligned}&\mathsf{(PA1)}\colon\quad (\forall x)(F(x)\ton F(y);\\ &\mathsf{(PA2)}\colon\quad F(y)\to (\exists x)(F(x)); \end{aligned}[/math]


где [math]F(x)[/math] — любая формула, содержащая свободные вхождения [math]x[/math], причем ни одно из них не находится в области действия квантора по [math]y[/math] (если таковой имеется); формула [math]F(y)[/math] получена из [math]F(x)[/math] заменой всех свободных вхождений [math]x[/math] на [math]y[/math].


Существенность последнего требования можно пояснить следующим примером. Рассмотрим в качестве формулы [math]F(x)[/math] формулу [math](\exists x)(P(x,y))[/math], где это требование нарушено: свободное вхождение [math]x[/math] находится в области действия квантора [math]\exists y[/math]. Подставив эту формулу в аксиому [math]\mathsf{(PA1)}[/math], получим формулу [math](\forall x)(\exists y)(P(x,y))\to (\exists y)(P(y,y))[/math] которая не будет общезначимой. В самом деле, предикат [math]A(x,y)\colon\, x<y[/math] на множестве вещественных чисел превращает ее в ложное высказывание:


[math](\forall x)(\exists y)(x<y)\to (\exists y)(y<y).[/math]



Правила вывода в формальном исчислении высказываний


К правилу вывода modus ponens из исчисления высказываний добавляются еще два правила вывода:


∀-правило, или правило обобщения: [math]\frac{F\to G(x)}{F\to (\forall x)(G(x))}[/math];
∃-правило, или правило конкретизации: [math]\frac{G(x)\to F}{(\exists x)(G(x))\to F}[/math]

при условии, что [math]G(x)[/math] содержит свободное вхождение [math]x[/math], a [math]F[/math] не содержит.


Последнее требование также весьма существенно. Его нарушение может привести по этим правилам к ложным выводам из истинных посылок. Так, например, взяв предикаты [math]A(x)\colon\,6\mid x[/math] и [math]B(x)\colon\,3\mid x[/math] над [math]\mathbb{N}[/math], получим тождественно истинный предикат [math]A(x)\to B(x)\colon\, 6\mid x\to3\mid x[/math]. Но применив к нему правило обобщения, получим уже опровержимый предикат: [math]6\mid x\to (\forall x)(3\mid x)[/math] (он превращается в ложное высказывание при тех [math]x[/math], которые делятся на 6). Если к предикату [math]6\mid x\to3\mid x[/math] применить (в нарушение условия) ∃-правило, то получим также опровержимый предикат [math](\exists x)(6\mid x\to3\mid x)[/math]. Применив же к последнему предикату уже на корректных основаниях ∀-правило, придем к ложному высказыванию [math](\exists x)(6\mid x)\to (\forall x)(3\mid x)[/math].




Теория формального вывода


Определения формального доказательства (формального вывода из аксиом и из гипотез) доказуемой формулы (теоремы) в формализованном исчислении предикатов даются так же, как и в формализованном исчислении высказываний (см. определение 15.1), с точностью до добавления двух новых аксиомных схем [math]\mathsf{(PA1)}[/math] и [math]\mathsf{(PA2)}[/math] и двух новых правил вывода: ∀-правила и ∃-правила.


Уточним все же понятие формальной выводимости формулы из гипотез в исчислении предикатов. Формула [math]G[/math] называется выводимой из гипотез [math]F_1,\ldots,F_m[/math] с фиксированными вхождениями (в гипотезы) свободных переменных, если существует такая конечная последовательность формул [math]B_1,B_2,\ldots,B_k,\ldots,B_s\equiv G[/math], каждая формула которой является либо аксиомой, либо гипотезой, либо получена из предыдущих формул последовательности по одному из правил вывода. (Сама эта последовательность называется выводом [math]G[/math] из гипотез [math]F_1,\ldots,F_m[/math]). При этом, если [math]B_k[/math] есть первая гипотеза, встречающаяся в выводе, то дальше в этом выводе не могут быть использованы ∀- и ∃-правила вывода по любой переменной [math]x[/math], которая входит свободно хотя бы в одну из гипотез. Обозначение используется то же, что и в исчислении высказываний: [math]F_1,\ldots,F_m\vdash G[/math]. Если гипотезы отсутствуют, то говорят, что [math]G[/math] выводима из аксиом (или просто выводима), и называют [math]G[/math] теоремой формализованного исчисления предикатов и пишут [math]\vdash G[/math].


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


Дальнейшее изучение формализованного исчисления предикатов строится в форме систематизированной подборки задач на доказательство теорем ФИП. Подборка начинается с построения выводов из аксиом. Затем рассматривается построение выводов из гипотез. Наконец — теорема о дедукции и ее применение к доказательству теорем ФИП. Теорема о дедукции в ФИП формулируется так же, как и в ФИВ:


если [math]F_1,\ldots,F_{m-1},F_m\vdash G[/math], то [math]F_1,\ldots,F_{m-1}\vdash F_m\to G[/math]

(в частности, если [math]F\vdash G[/math]), то [math]\vdash F\to G[/math]. Ничем особо не отличается и идея доказательства, с той лишь разницей, что появятся случаи, связанные с получением формулы в последовательности-выводе не только по правилу modus ponens, но и по ∀-правилу и по ∃-правилу.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved