Лекции - Математическая логика

Подождите немного. Документ загружается.

131

à) åñëè Ã



À, òî v(&Ã)  v(À) äëÿ ëþáîé îöåíêè v â M, ãäå

v(&Ã)  v(F

& … & F

), åñëè Ã = {F

, …, F

}, è v(&Ã)  1, åñëè

Ã = ∅. Ïðè äîêàçàòåëüñòâå óäîáíî âîñïîëüçîâàòüñÿ ïðèíöèïîì

èíäóêöèè äëÿ N

-âûâîäîâ, îïðåäåëèâ îòíîøåíèå ρ ñëåäóþùèì îá-

ðàçîì:

ÃρÀ

←⎯⎯→

def

(v) (v(&Ã)  v(À));

á) åñëè äëÿ âñÿêîé îöåíêè v â M v(&Ã)  v(À), òî Ã



À. ✰

Äîêàæåì òåïåðü, ÷òî ¬¬p



p. Äåéñòâèòåëüíî, ïðè îöåíêå v,

òàêîé ÷òî v(p) = 1/2, èìååì: v(¬¬p) =

(

1/2) =

0 = 1, à

v(p)

≠

1. 

! ÑËÅÄÑÒÂÈÅ 1. Ñèñòåìà N

íå ÿâëÿåòñÿ äåäóêòèâíî ïîëíîé.

Äîêàçàòåëüñòâî. Äåéñòâèòåëüíî, äîáàâèâ ê ñèñòåìå

ïðàâèëî ¬¬ó, êîòîðîå íå ÿâëÿåòñÿ N

-ïðîèçâîäíûì, ïîëó÷èì

íåïðîòèâîðå÷èâóþ ñèñòåìó N

. Ñëåäîâàòåëüíî, N

íå ÿâëÿåòñÿ äå-

äóêòèâíî ïîëíîé.



! ÑËÅÄÑÒÂÈÅ 2. Ôîðìóëû ¬¬p ⊃ p è p ∨ ¬p íåâûâîäèìû â N

Äîêàçàòåëüñòâî. Èíòåðïðåòàöèÿ M, ðàññìîòðåííàÿ â òåî-

ðåìå, ÿâëÿåòñÿ ìîäåëüþ N

, ïîñêîëüêó âñå N

-ïðàâèëà ñîõðàíÿþò



. Âìåñòå ñ òåì ôîðìóëû ¬¬p ⊃ p è p ∨ ¬p îïðîâåðæèìû (íå-

îáùåçíà÷èìû) â M. Äåéñòâèòåëüíî, ïðè îöåíêå v òàêîé, ÷òî v(p) = 1/2,

èìååì v(¬¬p ⊃ p) = v(¬¬p)

⊃

v(p) = 1

⊃

1/2 = 1/2 è v(p ∨ ¬p) =

= 1/2

∨

0 = 1/2. 

! ÑËÅÄÑÒÂÈÅ 3. Ñèñòåìà N

íå ÿâëÿåòñÿ ïîëíîé îòíîñèòåëüíî

êëàññà òàâòîëîãèé.

Äîêàçàòåëüñòâî. Äåéñòâèòåëüíî, ôîðìóëà ¬¬p ⊃ p ÿâ-

ëÿåòñÿ òàâòîëîãèåé, îäíàêî îíà íåâûâîäèìà â N

. 

Òàêèì îáðàçîì, êëàññ òåîðåì ñèñòåìû N

øèðå êëàññà òåîðåì

ñèñòåìû N

132

ÑËÅÄÑÒÂÈÅ 4. Êàæäîå ïðàâèëî ñèñòåìû

íå çàâèñèò îò

îñòàëüíûõ ïðàâèë ýòîé ñèñòåìû (

– ñèñòåìà, ïîëó÷àåìàÿ èç N

çàìåíîé ïðàâèëà ¬ó íà ïðàâèëî ¬¬ó).

Äîêàçàòåëüñòâî. Äîñòàòî÷íî ïðè äîêàçàòåëüñòâå íåçàâè-

ñèìîñòè ïðàâèëà ¬â ê òåì ðàññóæäåíèÿì, êîòîðûå ïðîâîäèëèñü

äëÿ ýòîãî ïðàâèëà â òåîðåìå î íåçàâèñèìîñòè N

-ïðàâèë, äîáàâèòü

ïðîâåðêó òîãî, ÷òî ïðàâèëî ¬¬ó ñîõðàíÿåò îòíîøåíèå





. Íåçà-

âèñèìîñòü æå ïðàâèëà ¬¬ó îò îñòàëüíûõ ïðàâèë N

, à çíà÷èò è

áûëà äîêàçàíà ðàíåå.



S Çàìå÷àíèå 3. Ìåòîä äîêàçàòåëüñòâà íåâûâîäèìîñòè ôîðìóë â

íåêîòîðîé ñèñòåìå N çàêëþ÷àåòñÿ â ñëåäóþùåì: äëÿ òîãî ÷òîáû

äîêàçàòü, ÷òî ôîðìóëà F íåâûâîäèìà â N, äîñòàòî÷íî ïðèâåñòè

ïðèìåð òàêîé ìîäåëè ñèñòåìû N, â êîòîðîé ôîðìóëà F îïðîâåð-

æèìà, ò. å. íå ÿâëÿåòñÿ â íåé îáùåçíà÷èìîé.

Èñïîëüçóÿ ìåòîä ìîäåëåé, ìîæíî äîêàçàòü, ÷òî ôîðìóëû

¬p ∨ ¬¬p, (p ⊃ q) ⊃ (¬p ∨ q), ¬(p & q) ⊃ (¬p ∨ ¬q)

íåâûâîäèìû â N

. 

★ Ïîíÿòèå çàâèñèìîñòè (íåçàâèñèìîñòè) ìîæíî ââåñòè è äëÿ

ïðîïîçèöèîíàëüíûõ ñâÿçîê. Áèíàðíóþ ïðîïîçèöèîíàëüíóþ ñâÿç-

êó ⊕ íàçîâåì çàâèñèìîé â ñèñòåìå N (îò îñòàëüíûõ ñâÿçîê ßËÂ),

åñëè äëÿ ëþáûõ ôîðìóë À è Â ñóùåñòâóåò ôîðìóëà F â òåõ æå

ïåðåìåííûõ, â êîòîðóþ íå âõîäèò ñâÿçêà ⊕, òàêàÿ, ÷òî



À ⊕ Â

Ñâÿçêó ¬ íàçîâåì çàâèñèìîé â ñèñòåìå N (îò îñòàëüíûõ ñâÿçîê

ßËÂ), åñëè äëÿ ëþáîé ôîðìóëû À ñóùåñòâóåò ôîðìóëà F â òåõ

æå ïåðåìåííûõ, â êîòîðóþ íå âõîäèò ñâÿçêà ¬, òàêàÿ, ÷òî



¬À

F. Ïðîïîçèöèîíàëüíóþ ñâÿçêó íàçûâàþò íåçàâèñèìîé â

ñèñòåìå N, åñëè îíà íå ÿâëÿåòñÿ çàâèñèìîé îò îñòàëüíûõ ñâÿ-

çîê. Ìîæíî äîêàçàòü, ÷òî:

1) êàæäàÿ èç áèíàðíûõ ñâÿçîê çàâèñèò â N

îò îñòàëüíûõ ñâÿçîê

ßËÂ;

2) ñâÿçêà ¬ íå çàâèñèò â N

îò îñòàëüíûõ ñâÿçîê;

3) êàæäàÿ èç ïðîïîçèöèîíàëüíûõ ñâÿçîê íå çàâèñèò â N

îò

îñòàëüíûõ ñâÿçîê ßËÂ.

✰

133

§ 2.13. Èñ÷èñëåíèÿ âûñêàçûâàíèé§ 2.13. Èñ÷èñëåíèÿ âûñêàçûâàíèé

§ 2.13. Èñ÷èñëåíèÿ âûñêàçûâàíèé

ãèëüáåðòîâñêîãî òèïàãèëüáåðòîâñêîãî òèïà

ãèëüáåðòîâñêîãî òèïà

Â § 2.2 áûëî ââåäåíî îáùåå ïîíÿòèå ôîðìàëü-

íîé ëîãè÷åñêîé ñèñòåìû (ëîãè÷åñêîãî èñ÷èñëåíèÿ) êàê ñèñòåìû,

çàäàâàåìîé ÷åòûðüìÿ êîìïîíåíòàìè: ôîðìàëüíûì ÿçûêîì, ìíî-

æåñòâîì àêñèîì, ïðàâèëàìè çàêëþ÷åíèÿ (ïðàâèëàìè âûâîäà) è îï-

ðåäåëåíèåì âûâîäà.

Íàïîìíèì, ÷òî àêñèîìîé ëîãè÷åñêîé ñèñòåìû íàçûâàþò âñÿ-

êèé ýëåìåíò ñïåöèàëüíî âûäåëåííîãî ìíîæåñòâà ôîðìóë ÿçûêà

ýòîé ñèñòåìû – ìíîæåñòâà åå àêñèîì (âîçìîæíî, ïóñòîãî).

Ëîãè÷åñêèå ñèñòåìû (èñ÷èñëåíèÿ) ïðèíÿòî äåëèòü íà èñ÷èñëå-

íèÿ ãèëüáåðòîâñêîãî òèïà è ãåíöåíîâñêîãî òèïà ïî èìåíàì ìàòåìà-

òèêîâ Ä. Ãèëüáåðòà è Ã. Ãåíöåíà

Â èñ÷èñëåíèÿõ ãèëüáåðòîâñêîãî òèïà ïî÷òè âñå ëîãè÷åñêèå ñðåä-

ñòâà âûðàæåíû â âèäå àêñèîì, ïîýòîìó èõ íàçûâàþò òàêæå àêñèî-

ìàòè÷åñêèìè èñ÷èñëåíèÿìè. Óòî÷íåíèåì ïîíÿòèÿ äîêàçàòåëüñòâà

â ýòèõ èñ÷èñëåíèÿõ ñëóæèò ïîíÿòèå ëèíåéíîãî âûâîäà – ïîñëåäî-

âàòåëüíîñòè ôîðìóë, óäîâëåòâîðÿþùåé óêàçàííûì äàëåå óñëîâè-

ÿì. Â èñ÷èñëåíèÿõ ãåíöåíîâñêîãî òèïà ëîãè÷åñêèå ñðåäñòâà âûðà-

æåíû â âèäå ïðàâèë âûâîäà, à àêñèîì èëè ñîâñåì íåò (êàê â ñèñòå-

ìàõ åñòåñòâåííîãî âûâîäà), èëè ïî÷òè íåò (êàê â ñåêâåíöèàëüíûõ

èñ÷èñëåíèÿõ

), ïðè ýòîì óòî÷íåíèåì ïîíÿòèÿ äîêàçàòåëüñòâà ñëó-

æèò ïîíÿòèå âûâîäà â âèäå äåðåâà.

Ñèñòåìû ãåíöåíîâñêîãî òèïà íå çðÿ íàçûâàþò åñòåñòâåííûìè:

äåðåâüÿ âûâîäà áîëüøå ïîõîæè íà îáû÷íûå ìàòåìàòè÷åñêèå ðàñ-

ñóæäåíèÿ è äîêàçàòåëüñòâà, ÷åì ëèíåéíûå âûâîäû. Â äåðåâå âûâî-

äà çíà÷èòåëüíî íàãëÿäíåå îòðàæåíû ëîãè÷åñêèå âçàèìîñâÿçè ìåæ-

äó åãî ÷ëåíàìè, ò. å. åãî ëîãè÷åñêàÿ ñòðóêòóðà. Òàêèì îáðàçîì,

ïîíÿòèå äåðåâà âûâîäà ëó÷øå îòðàæàåò ñóùíîñòü îáû÷íûõ ìàòå-

ìàòè÷åñêèõ äîêàçàòåëüñòâ. Êðîìå òîãî, âûâîäû â âèäå äåðåâà ñòðî-

Ä. Ãèëüáåðò (1862–1943) – íåìåöêèé ìàòåìàòèê, âíåñøèé îãðîìíûé âêëàä

â ðàçâèòèå ðàçëè÷íûõ îáëàñòåé ìàòåìàòèêè, â òîì ÷èñëå è â ðàçâèòèå ìàòåìà-

òè÷åñêîé ëîãèêè.

Ã. Ãåíöåí (1909–1945) – íåìåöêèé ëîãèê, ó÷åíèê è ñîðàòíèê Ä. Ãèëüáåðòà,

âêëàä êîòîðîãî â ðàçâèòèå ìàòåìàòè÷åñêîé ëîãèêè íå îãðàíè÷èâàåòñÿ ñîçäàíè-

åì ñèñòåì åñòåñòâåííîãî âûâîäà è ñåêâåíöèàëüíûõ èñ÷èñëåíèé (è òå è äðóãèå

íàçûâàþò òåïåðü èñ÷èñëåíèÿìè ãåíöåíîâñêîãî òèïà). Èñïîëüçóÿ èñ÷èñëåíèÿ

èìåííî ýòîãî òèïà, Ãåíöåí äîêàçàë íåïðîòèâîðå÷èâîñòü àðèôìåòèêè (ñì. § 5.6

è ãë. 6).

Î ñåêâåíöèàëüíûõ èñ÷èñëåíèÿõ ìîæíî ïðî÷èòàòü, íàïðèìåð, â [6] èëè [3].

134

èòü ãîðàçäî ïðîùå, ÷åì ëèíåéíûå âûâîäû â ãèëüáåðòîâñêèõ èñ-

÷èñëåíèÿõ.

Â òî æå âðåìÿ èñ÷èñëåíèÿ ãèëüáåðòîâñêîãî òèïà ïðîùå îïè-

ñàòü è ñôîðìóëèðîâàòü îïðåäåëåíèå âûâîäà â ýòèõ ñèñòåìàõ. Â ñâÿçè

ñ ýòèì èñ÷èñëåíèÿ ãèëüáåðòîâñêîãî òèïà ÷àñòî èñïîëüçóþò ïðè

èçëîæåíèè îñíîâ òåîðèè äîêàçàòåëüñòâ.

Ðàññìîòðåííûå ðàíåå ïðîïîçèöèîíàëüíûå ñèñòåìû åñòåñòâåí-

íîãî âûâîäà îòíîñÿòñÿ ê ñèñòåìàì ãåíöåíîâñêîãî òèïà. Ðàññìîòðèì

òåïåðü äâå ëîãè÷åñêèå ñèñòåìû ãèëüáåðòîâñêîãî òèïà – êëàññè÷åñ-

êîå èñ÷èñëåíèå âûñêàçûâàíèé (K) è èíòóèöèîíèñòñêîå èñ÷èñëå-

íèå âûñêàçûâàíèé (I). Ôîðìàëüíûì ÿçûêîì ýòèõ èñ÷èñëåíèé ñëó-

æèò ßËÂ. Áåñêîíå÷íîå ìíîæåñòâî àêñèîì èñ÷èñëåíèÿ I çàäàåòñÿ

ñëåäóþùèìè ñõåìàìè:

S (À

) A ⊃ (B ⊃ A);

(À

) (A ⊃ (B ⊃ C)) ⊃ ((A ⊃ B) ⊃ (A ⊃ C));

(À

) A & B ⊃ A;

(À

) A & B ⊃ B;

(À

) A ⊃ (B ⊃ A & B);

(À

) A ⊃ A ∨ B;

(À

) B ⊃ A ∨ B;

(À

) (A ⊃ C) ⊃ ((B ⊃ C) ⊃ (A ∨ B ⊃ C));

(À

) (A ⊃ B) ⊃ ((A ⊃ ¬B) ⊃ ¬A);

(À

) A ⊃ (¬A ⊃ B).

Ñïèñîê ñõåì àêñèîì êëàññè÷åñêîãî èñ÷èñëåíèÿ K ïîëó÷àåòñÿ

äîáàâëåíèåì ê óêàçàííîìó ñïèñêó åùå îäíîé ñõåìû:

(

) ¬¬A ⊃ A.

Îáå ñèñòåìû èìåþò åäèíñòâåííîå ïðàâèëî âûâîäà (çàêëþ÷å-

íèÿ) – modus ponens:

⊃AA B

. Êàêîâû áû íè áûëè ôîðìóëû À è

Â, ôîðìóëó Â íàçûâàþò íåïîñðåäñòâåííî ñëåäóþùåé èç ôîðìóë À

è À ⊃ Â ïî ïðàâèëó modus ponens

Áóäåì îáîçíà÷àòü ñèìâîëîì Ñ ïðîèçâîëüíîå èç èñ÷èñëåíèé

K è I.

Ïóñòü Ã – ïðîèçâîëüíîå êîíå÷íîå ìíîæåñòâî ôîðìóë.

Ñ-Ã-âûâîäîì (âûâîäîì èç ìíîæåñòâà ôîðìóë Ã â èñ÷èñëåíèè Ñ)

áóäåì íàçûâàòü âñÿêóþ êîíå÷íóþ ïîñëåäîâàòåëüíîñòü ôîðìóë

Ôàêòè÷åñêè, ýòî ïðàâèëî ñîâïàäàåò ñ ïðàâèëîì ⊃ó â ñèñòåìàõ åñòåñòâåí-

íîãî âûâîäà, îäíàêî äëÿ íåãî òðàäèöèîííî èñïîëüçóþò íàçâàíèå modus ponens

(ëàò.).

135

, …, F

, êàæäûé ÷ëåí êîòîðîé ÿâëÿåòñÿ èëè àêñèîìîé Ñ, èëè

ôîðìóëîé èç Ã, èëè íåïîñðåäñòâåííûì ñëåäñòâèåì êàêèõ-ëèáî

äâóõ ïðåäøåñòâóþùèõ ôîðìóë ïî ïðàâèëó modus ponens.

Ñ-Ã-âûâîä áóäåì íàçûâàòü Ñ-Ã-F-âûâîäîì, åñëè åãî ïîñëåäíèì

÷ëåíîì ÿâëÿåòñÿ ôîðìóëà F.

Ôîðìóëó F áóäåì íàçûâàòü Ñ-Ã-âûâîäèìîé è ïèñàòü Ã



F, åñëè

ñóùåñòâóåò õîòÿ áû îäèí Ñ-Ã-F-âûâîä (ïðè ýòîì ôîðìóëû èç

ìíîæåñòâà Ã ïðèíÿòî íàçûâàòü ãèïîòåçàìè).

Ôîðìóëó F áóäåì íàçûâàòü Ñ-âûâîäèìîé è ïèñàòü



F, åñëè

ñóùåñòâóåò åå âûâîä â èñ÷èñëåíèè Ñ èç ïóñòîãî ìíîæåñòâà ôîð-

ìóë.

Çàìå÷àíèå 1. Ìîæíî äîêàçàòü, ÷òî èñ÷èñëåíèå K ðàâíîîáúåìíî

èñ÷èñëåíèþ K*, êîòîðîå ïîëó÷àåòñÿ èç èñ÷èñëåíèÿ I çàìåíîé ñõå-

ìû àêñèîì A ⊃ (¬A ⊃ B) íà ñõåìó ¬¬A ⊃ A èëè, èíà÷å ãîâîðÿ,

óäàëåíèåì ñõåìû A ⊃ (¬A ⊃ B) èç ñïèñêà ñõåì àêñèîì K.



Ðàññìîòðèì ïðèìåðû Ñ-âûâîäîâ.

Ïðèìåð. Ïóñòü À – ïðîèçâîëüíàÿ ôîðìóëà. Ïîñòðîèì

Ñ-âûâîä ôîðìóëû À ⊃ À. Ïðîíóìåðóåì ôîðìóëû, âõîäÿùèå â âû-

âîä. Êàæäûé ÷ëåí âûâîäà ñîïðîâîäèì êîììåíòàðèåì, óêàçûâàþ-

ùèì, íà êàêîì îñíîâàíèè îí âõîäèò â âûâîä:

1) À ⊃ ((À ⊃ À) ⊃ À) – àêñèîìà ïî ñõåìå À

;

2) (À ⊃ ((À ⊃ À) ⊃ À)) ⊃ ((À ⊃ (À ⊃ À)) ⊃ (À ⊃ À)) – àêñèîìà ïî

ñõåìå À

;

3) (À ⊃ (À ⊃ À)) ⊃ (À ⊃ À) – modus ponens (1, 2);

4) À ⊃ (À ⊃ À) – àêñèîìà ïî ñõåìå À

;

5) À ⊃ À – modus ponens (4, 3).

Òàêèì îáðàçîì,



À ⊃ À è



À ⊃ À. 

Çàìå÷àíèå 2. Â ïîñòðîåííîì âûâîäå èñïîëüçóþòñÿ àêñèîìû

òîëüêî ïî ñõåìàì À

è À

, à çíà÷èò, åãî ìîæíî ðàññìàòðèâàòü êàê

âûâîä â ëþáîì èñ÷èñëåíèè ãèëüáåðòîâñêîãî òèïà, ñðåäè ñõåì àê-

ñèîì êîòîðîãî èìåþòñÿ ñõåìû À

è À

. 

Ïðèìåð. Äîêàæåì, ÷òî À



¬¬À ïîñòðîåíèåì Ñ-âûâîäà:

1) (¬À ⊃ À) ⊃ ((¬À ⊃ ¬À) ⊃ ¬¬À) – àêñèîìà ïî ñõåìå À

;

2) À – ãèïîòåçà;

3) À ⊃ (¬À ⊃ À) – àêñèîìà ïî ñõåìå À

;

4) ¬À ⊃ À – modus ponens (2, 3);

5) (¬À ⊃ ¬À) ⊃ ¬¬À – modus ponens (4, 1);

136

6) ¬À ⊃ ((¬À ⊃ ¬À) ⊃ ¬À) – àêñèîìà ïî ñõåìå À

;

7) (¬À ⊃ ((¬À ⊃ ¬À) ⊃ ¬À)) ⊃ ((¬À ⊃ (¬À ⊃ ¬À)) ⊃ (¬À ⊃ ¬À)) –

àêñèîìà ïî ñõåìå À

;

8) (¬À ⊃ (¬À ⊃ ¬À)) ⊃ (¬À ⊃ ¬À) – modus ponens (6, 7);

9) ¬À ⊃ (¬À ⊃ ¬À) – àêñèîìà ïî ñõåìå À

;

10) ¬À ⊃ ¬À – modus ponens (9, 8);

11) ¬¬À – modus ponens (10, 5).



Êàê âèäíî óæå èç ïðèìåðîâ 1 è 2, ïîñòðîåíèå âûâîäîâ â

èñ÷èñëåíèÿõ K è I – çàíÿòèå âåñüìà óòîìèòåëüíîå, à ñàìè âûâî-

äû î÷åíü ãðîìîçäêè. Ýòî îñîáåííî çàìåòíî, åñëè ñðàâíèòü èõ ñ

ñîîòâåòñòâóþùèìè äåðåâüÿìè åñòåñòâåííîãî âûâîäà òåõ æå ôîð-

ìóë. Òàêèì îáðàçîì, äîêàçûâàòü Ñ-âûâîäèìîñòü ôîðìóë ïîñò-

ðîåíèåì âûâîäà, ò. å. íåïîñðåäñòâåííî, äîâîëüíî ãðîìîçäêî è

íåïðîñòî.

Ñëåäóþùåå óòâåðæäåíèå ïîçâîëÿåò ïðîâîäèòü äîêàçàòåëü-

ñòâî óòâåðæäåíèé î âûâîäèìîñòè, íå ïðèáåãàÿ ê ïîñòðîåíèþ

âûâîäà.

ÓÒÂÅÐÆÄÅÍÈÅ (î ïðîèçâîäíûõ ïðàâèëàõ èñ÷èñëåíèé K è I).

Ïóñòü A, B, Ñ – ïðîèçâîëüíûå ôîðìóëû, à Ã – ïðîèçâîëüíîå êî-

íå÷íîå ìíîæåñòâî ôîðìóë. Òîãäà:

ÑÑ

ÃèÃ

Ã&

ÀÂ

ÀB





; 2)

ÑÑ

Ã&

ÃèÃ

ÀB

ÀÂ





;

ÑÑ

ÃèëèÃ

ÀÂ

ÀB

∨





; 4)

ÑÑ

Ã, è Ã,

Ã,

ÀÑ ÂÑ

ÀÂ Ñ

∨





;

Ã,

ÀÂ

ÀB

⊃



; 6)

ÑÑ

ÃèÃ

ÀÀÂ

⊃



;

ÑÑ

Ã, è Ã,

ÀÂ À Â





; 8)

ÑÑ

ÃèÃ

ÀÀ

¬



;

¬¬



Âñå óòâåðæäåíèÿ, êðîìå 5, ëåãêî äîêàçàòü, èñïîëüçóÿ îïðåäå-

ëåíèå Ñ-âûâîäà. Îòìåòèì, ÷òî íàèáîëåå âàæíûì è ïîëåçíûì ÿâ-

ëÿåòñÿ óòâåðæäåíèå 5, èçâåñòíîå êàê òåîðåìà äåäóêöèè äëÿ èñ÷èñ-

137

ëåíèé K è I

. Äîêàçàòåëüñòâî òåîðåìû äåäóêöèè, â îòëè÷èå îò äî-

êàçàòåëüñòâ îñòàëüíûõ ïðîèçâîäíûõ ïðàâèë, íåòðèâèàëüíî. Åãî

óäîáíî ïðîâîäèòü ñ ïîìîùüþ ïðèíöèïà èíäóêöèè äëÿ Ñ-Ã-âûâî-

äèìûõ ôîðìóë. Ïåðåéäåì ê ôîðìóëèðîâêå ýòîãî ïðèíöèïà.

Ïóñòü P – ïðîèçâîëüíîå ñâîéñòâî ôîðìóë. Áóäåì ãîâîðèòü, ÷òî

ïðàâèëî modus ponens ñîõðàíÿåò ñâîéñòâî P, åñëè äëÿ ëþáûõ ôîð-

ìóë À è Â èç óñëîâèé P(A) è P(A ⊃Â) ñëåäóåò P(Â).

ÒÅÎÐÅÌÀ (ïðèíöèï èíäóêöèè äëÿ Ñ-Ã-âûâîäèìûõ ôîðìóë). Ïóñòü

P – ïðîèçâîëüíîå ñâîéñòâî ôîðìóë, à Ã – ïðîèçâîëüíîå êîíå÷íîå

ìíîæåñòâî ôîðìóë.

Åñëè 1) âñå àêñèîìû è ôîðìóëû èç Ã îáëàäàþò ñâîéñòâîì P

è 2) ïðàâèëî modus ponens ñîõðàíÿåò ñâîéñòâî P,

òî âñå Ñ-Ã-âûâîäèìûå ôîðìóëû îáëàäàþò ñâîéñòâîì P.

Äîñòàòî÷íî äîêàçàòü ìàòåìàòè÷åñêîé èíäóêöèåé ïî íàòóðàëü-

íîìó n ñëåäóþùåå óòâåðæäåíèå (ïðè âûïîëíåíèè óñëîâèé 1 è 2):

äëÿ ëþáîãî íàòóðàëüíîãî n è ëþáîãî Ñ-Ã-âûâîäà äëèíû n (ò. å. ñ n

÷ëåíàìè) êàæäûé ÷ëåí ýòîãî âûâîäà îáëàäàåò ñâîéñòâîì P.

Ïðîâåäåíèå ýòîé èíäóêöèè ïðåäîñòàâëÿåòñÿ ÷èòàòåëþ.

Ýòîò ïðèíöèï óäîáíî èñïîëüçîâàòü ïðè äîêàçàòåëüñòâå òåîðåì

âèäà: «Äëÿ ëþáîãî ìíîæåñòâà ôîðìóë Ã è ëþáîé Ñ-Ã-âûâîäèìîé

ôîðìóëû F ýòà ôîðìóëà îáëàäàåò ñâîéñòâîì P». Ñèìâîëè÷åñêè òà-

êîãî âèäà óòâåðæäåíèå ìîæíî çàïèñàòü òàê:

(Ã) (F) (Ã



F → P(F)).

Òåïåðü ïåðåéäåì ê âîïðîñó î ñâÿçè ìåæäó èñ÷èñëåíèÿìè K è I

è èñ÷èñëåíèÿìè N

è N

ñîîòâåòñòâåííî.

ÒÅÎÐÅÌÀ (î ñîãëàñîâàííîñòè îòíîøåíèé N

-âûâîäèìîñòè è

Ñ-âûâîäèìîñòè). Äëÿ ëþáîé ôîðìóëû F è ëþáîãî êîíå÷íîãî ìíî-

æåñòâà ôîðìóë Ã ôîðìóëà F ÿâëÿåòñÿ N

-Ã-âûâîäèìîé òîãäà è òîëü-

êî òîãäà, êîãäà îíà Ñ-Ã-âûâîäèìà, ò. å. (Ã) (F) (Ã



F ↔ Ã



F).

Äîêàçàòåëüñòâî. Ñíà÷àëà äîêàæåì, ÷òî äëÿ ëþáûõ Ã è

F, åñëè ôîðìóëà F ÿâëÿåòñÿ N

-Ã-âûâîäèìîé, òî îíà Ñ-Ã-âûâîäè-

ìà, ò. å.

(Ã) (F) (Ã



F → Ã



F).

Äîêàçàòåëüñòâî òåîðåìû äåäóêöèè èñïîëüçóåò ëèøü ñõåìû àêñèîì À

, à ñëåäîâàòåëüíî, ýòî óòâåðæäåíèå âåðíî äëÿ ëþáîãî èñ÷èñëåíèÿ âûñêàçûâà-

íèé ãèëüáåðòîâñêîãî òèïà, èìåþùåãî ñðåäè ñõåì àêñèîì ñõåìû À

è À

. Äîêà-

çàòåëüñòâî ýòîé òåîðåìû â ó÷åáíèêàõ îáû÷íî ïðîâîäèòñÿ èíäóêöèåé ïî íàòó-

ðàëüíîìó n (ñì., íàïðèìåð, [10]).

138

Âîñïîëüçóåìñÿ ïðèíöèïîì èíäóêöèè äëÿ N

-âûâîäîâ âî âòî-

ðîé ôîðìå, âçÿâ â êà÷åñòâå îòíîøåíèÿ ρ îòíîøåíèå Ñ-âûâîäèìî-

ñòè



. Ñîãëàñíî ýòîìó ïðèíöèïó, äîñòàòî÷íî ïðîâåðèòü, ÷òî îò-

íîøåíèå



ðåôëåêñèâíî è ìîíîòîííî, à âñå N

-ïðàâèëà ñîõðàíÿ-

þò îòíîøåíèå Ñ-âûâîäèìîñòè



. Ðåôëåêñèâíîñòü è ìîíîòîí-

íîñòü



ïðèñóòñòâóþò ñðåäè îñíîâíûõ ñâîéñòâ îòíîøåíèÿ Ñ-âû-

âîäèìîñòè. Óòâåðæäåíèå î ïðîèçâîäíûõ ïðàâèëàõ èñ÷èñëåíèé K è

I ñâèäåòåëüñòâóåò êàê ðàç î òîì, ÷òî âñå N

-ïðàâèëà ñîõðàíÿþò

îòíîøåíèå Ñ-âûâîäèìîñòè.

Òåïåðü äîêàæåì, ÷òî äëÿ ëþáûõ Ã è F, åñëè ôîðìóëà F ÿâëÿåòñÿ

Ñ-Ã-âûâîäèìîé, òî îíà N

-Ã-âûâîäèìà, ò. å.

(Ã) (F) (Ã



F → Ã



F).

Çàôèêñèðóåì ïðîèçâîëüíîå ìíîæåñòâî Ã. Âîñïîëüçóåìñÿ ïðèí-

öèïîì èíäóêöèè äëÿ Ñ-Ã-âûâîäèìûõ ôîðìóë, âçÿâ â êà÷åñòâå ñâîé-

ñòâà P ñâîéñòâî ôîðìóëû «áûòü N

-âûâîäèìîé èç Ã», ò. å. ïîëîæèì

P(F) ↔ Ã



F. Ñîãëàñíî ýòîìó ïðèíöèïó, äîñòàòî÷íî ïðîâåðèòü,

÷òî âñå àêñèîìû èñ÷èñëåíèÿ Ñ ÿâëÿþòñÿ N

-âûâîäèìûìè, à ïðà-

âèëî modus ponens ñîõðàíÿåò ñâîéñòâî P. Äëÿ êàæäîé ñõåìû àêñèîì

èñ÷èñëåíèÿ Ñ N

-âûâîäèìîñòü ïðîèçâîëüíîé àêñèîìû ïî ýòîé

ñõåìå ëåãêî äîêàçàòü íåïîñðåäñòâåííî ïîñòðîåíèåì äåðåâà N

-âû-

âîäà (ñì. óïðàæíåíèå èç § 2.5). Êðîìå òîãî, î÷åâèäíî, ïðàâèëî

modus ponens ñîõðàíÿåò ñâîéñòâî P, ïîñêîëüêó ýòî ïðàâèëî ÿâëÿåò-

ñÿ òàêæå N

-ïðàâèëîì, à èìåííî, ïðàâèëîì ⊃ó. 

Â êà÷åñòâå ñëåäñòâèÿ ïîëó÷àåì ñëåäóþùóþ âàæíóþ òåîðåìó.

! ÒÅÎÐÅÌÀ (î ðàâíîîáúåìíîñòè èñ÷èñëåíèé Ñ è N

). Êëàññ

-âûâîäèìûõ ôîðìóë ñîâïàäàåò ñ êëàññîì Ñ-âûâîäèìûõ ôîðìóë,

ò. å. (F) (



F ↔



F).

Òåïåðü, ïîëüçóÿñü ðàâíîîáúåìíîñòüþ èñ÷èñëåíèé K è I ñ îä-

íîèìåííûìè èñ÷èñëåíèÿìè åñòåñòâåííîãî âûâîäà N

è N

, à òàêæå

ñåìàíòè÷åñêîé êîððåêòíîñòüþ N

è N

è ïîëíîòîé N

, ñðàçó ïîëó-

÷àåì ñëåäóþùèå òåîðåìû

Âïðî÷åì, ýòè òåîðåìû ìîæíî äîêàçàòü íåçàâèñèìî îò ñîîòâåòñòâóþùèõ

ðåçóëüòàòîâ äëÿ ñèñòåì åñòåñòâåííîãî âûâîäà (ñì., íàïðèìåð, [10]).

139

ÒÅÎÐÅÌÀ. Âñÿêàÿ Ñ-âûâîäèìàÿ ôîðìóëà ÿâëÿåòñÿ òàâòîëîãèåé.

ÒÅÎÐÅÌÀ. Êëàññ K-âûâîäèìûõ ôîðìóë ñîâïàäàåò ñ êëàññîì

òàâòîëîãèé.

Çàìå÷àíèå 3. Äëÿ ãèëüáåðòîâñêèõ èñ÷èñëåíèé ìîæíî ââåñòè ïî-

íÿòèå äåäóêòèâíîé (ñèíòàêñè÷åñêîé) ïîëíîòû è äîêàçàòü äåäóê-

òèâíóþ ïîëíîòó K. Åñòåñòâåííûì îáðàçîì ìîæíî ââåñòè ïîíÿòèå

íåçàâèñèìîñòè ñõåìû àêñèîì îò îñòàëüíûõ ñõåì àêñèîì è äîêà-

çàòü, ÷òî êàæäàÿ èç ñõåì èñ÷èñëåíèé I è K* íå çàâèñèò îò îñòàëü-

íûõ ñõåì àêñèîì ýòèõ èñ÷èñëåíèé (ñì., íàïðèìåð, [11]). 

ÓÏÐÀÆÍÅÍÈÅ

Äîêàæèòå ïîñòðîåíèåì Ñ-Ã-âûâîäà (À, Â, Ñ – ïðîèçâîëüíûå

ôîðìóëû):



¬(À & ¬À);

2) À ⊃ Â, ¬Â



¬À;

3) Â, À ⊃ (Â ⊃ Ñ)



À ⊃ Ñ;

4) À ⊃ Â, Â ⊃ Ñ



À ⊃ Ñ;

5) À, ¬À



Â;

6) ¬À ∨ Â, À



Â.

140

Ñðåäñòâ ëîãèêè âûñêàçûâàíèé íå õâàòàåò äëÿ

èçó÷åíèÿ ôîðìû ìàòåìàòè÷åñêèõ ïðåäëîæåíèé

è ìàòåìàòè÷åñêèõ ðàññóæäåíèé â ïîëíîì îáúå-

ìå. Ðåäêîå ìàòåìàòè÷åñêîå ðàññóæäåíèå

îáõîäèòñÿ áåç ïðåäëîæåíèé ñ òàê íàçûâàåìû-

ìè êâàíòîðíûìè ñëîâàìè «ëþáîé» («âñÿêèé») è «ñóùåñòâóåò»

(«íåêîòîðûé»).

Ðàññìîòðèì, íàïðèìåð, ñëåäóþùèå ðàññóæäåíèÿ:

1. Âñÿêàÿ äèôôåðåíöèðóåìàÿ â íåêîòîðîé òî÷êå ôóíêöèÿ íå-

ïðåðûâíà â ýòîé òî÷êå. Ôóíêöèÿ Äèðèõëå ðàçðûâíà â êàæäîé òî÷-

êå îòðåçêà [0, 1]. Ñëåäîâàòåëüíî, ôóíêöèÿ Äèðèõëå íå äèôôåðåí-

öèðóåìà íè â îäíîé òî÷êå îòðåçêà [0, 1].

2. Âñÿêîå òðàíñöåíäåíòíîå ÷èñëî èððàöèîíàëüíî. ×èñëî π èð-

ðàöèîíàëüíî, ñëåäîâàòåëüíî, îíî òðàíñöåíäåíòíî.

×òîáû âûÿâèòü è ïðîàíàëèçèðîâàòü ëîãè÷åñêóþ ôîðìó òàêèõ

ðàññóæäåíèé, âûÿñíèòü, ïðàâèëüíûå îíè èëè íåò, âûðàçèòåëüíûõ

ñðåäñòâ ÿçûêà ëîãèêè âûñêàçûâàíèé íå äîñòàòî÷íî.

Èñïîëüçóþòñÿ êâàíòîðíûå ñëîâà è â îïðåäåëåíèÿõ. Äîñòàòî÷-

íî âñïîìíèòü îïðåäåëåíèå ïðåäåëà ôóíêöèè â òî÷êå: «Äëÿ âñÿêîãî

ïîëîæèòåëüíîãî ε ñóùåñòâóåò δ …»

Â ýòîì ðàçäåëå áóäåò ïîñòðîåí ôîðìàëüíûé ëîãè÷åñêèé

ÿçûê ñ áîëåå øèðîêèìè âûðàçèòåëüíûìè âîçìîæíîñòÿìè, ÷åì

ÿçûê ëîãèêè âûñêàçûâàíèé, – ÿçûê ëîãèêè ïðåäèêàòîâ. Ïðåæäå

÷åì ïåðåéòè ê åãî ïîñòðîåíèþ, ïîçíàêîìèìñÿ ñ ïîíÿòèåì ïðå-

äèêàòà.

ГлаваГлава

Глава

ßÇÛÊ ËÎÃÈÊÈ ÏÐÅÄÈÊÀÒÎÂßÇÛÊ ËÎÃÈÊÈ ÏÐÅÄÈÊÀÒÎÂ

ßÇÛÊ ËÎÃÈÊÈ ÏÐÅÄÈÊÀÒÎÂ

Недостаточность

выразительных

средств ЯЛВ