ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ

ПРЕДИКА́ТОВ ИСЧИСЛЕ́НИЕ, об­щее на­зва­ние фор­маль­ных сис­тем

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

 >>

), так и их субъ­ек­тив­но-пре­ди­ка­тив­ная струк­ту­ра, т. е. связь ме­ж­ду субъ­ек­том су­ж­де­ния (о чём го­во­рит­ся в дан­ном су­ж­де­нии) и пре­ди­ка­том (что го­во­рит­ся о субъ­ек­те). При этом для ло­гич. ана­ли­за су­ж­де­ний на­ря­ду с та­ки­ми ло­гич. опе­ра­ция­ми, как дизъ­юнк­ция, конъ­юнк­ция, им­пли­ка­ция, от­ри­ца­ние, эк­ви­ва­лент­ность

 >>

, ис­поль­зу­ют­ся кван­то­ры

 >>

, а субъ­ек­тив­но-пре­ди­ка­тив­ная струк­ту­ра уточ­ня­ет­ся с по­мо­щью по­ня­тия пре­ди­ка­та

 >>

.

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

, ал­фа­вит ко­то­ро­го обыч­но со­дер­жит че­ты­ре груп­пы сим­во­лов: 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$ сов­па­да­ет с $𝔄$. Фор­му­ла $𝔄$ вы­во­ди­ма в П. и. или яв­ля­ет­ся тео­ре­мой, ес­ли мож­но по­стро­ить вы­вод этой фор­му­лы. Со­глас­но тео­ре­ме Гё­де­ля о пол­но­те, все об­ще­зна­чи­мые пре­ди­кат­ные фор­му­лы и толь­ко они вы­во­ди­мы в клас­сич. ис­чис­ле­нии пре­ди­ка­тов.

Де­дук­тив­ный ап­па­рат П. и., т. е. сис­те­ма ак­си­ом и пра­ви­ла вы­во­да, ис­поль­зу­ет­ся при по­строе­нии ло­ги­ко-ма­те­ма­тич. ис­чис­ле­ний (напр., фор­маль­ной ариф­ме­ти­ки и ак­сио­ма­ти­че­ской тео­рии мно­жеств

).