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

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

111

Äîêàæåì ýòî ïîñòðîåíèåì äåðåâà N-âûâîäà, èñïîëüçóÿ ïðàâè-

ëî (I):

I(1)

[]

¬¬¬

Äîêàæåì òåïåðü, ÷òî ïðàâèëî ¬â ÿâëÿåòñÿ ïðîèçâîäíûì N-ïðà-

âèëîì, ò. å. äëÿ ëþáûõ Ã, À è Â

,;,

AB A B

ΓΓ¬

Γ¬





. (IIIR)

Ðàñïîëàãàÿ äåðåâüÿìè N-âûâîäà

, ãäå Δ

⊆ Ã è

⊆ Ã, ïîñòðîèì íîâîå äåðåâî ôîðìóë:

21 31

I(2) I(3)

I(1)

[][ ] [][ ]

AA AA

¬¬¬ ¬¬¬

ΔΔ

Ýòî äåðåâî ÿâëÿåòñÿ äåðåâîì N-âûâîäà ôîðìóëû ¬À, ìíîæå-

ñòâî çåëåíûõ ëèñòüåâ êîòîðîãî ñîäåðæèòñÿ â Ã. Òàêèì îáðàçîì,



¬À, à çíà÷èò, óòâåðæäåíèå (IIIR) äîêàçàíî. 

Çàìå÷àíèå 1. Íà ñàìîì äåëå àíàëîãè÷íûì îáðàçîì ìîæíî äî-

êàçàòü áîëåå ñèëüíîå óòâåðæäåíèå:

1') åñëè ñõåìû (II) è (III) ÿâëÿþòñÿ ïðîèçâîäíûìè N-ïðàâèëà-

ìè, òî è ñõåìà (I) ÿâëÿåòñÿ ïðîèçâîäíûì N-ïðàâèëîì;

2') åñëè ñõåìà (I) ÿâëÿåòñÿ ïðîèçâîäíûì N-ïðàâèëîì, òî ñõåìû

(II) è (III) òàêæå ÿâëÿþòñÿ ïðîèçâîäíûìè N-ïðàâèëàìè. 

! ÑËÅÄÑÒÂÈÅ 1. Ïóñòü N

– ñèñòåìà, ñðåäè îñíîâíûõ ïðàâèë

êîòîðîé åñòü ïðàâèëà (II) è (III), à N

– ñèñòåìà, êîòîðàÿ ïîëó÷à-

åòñÿ èç ñèñòåìû N

çàìåíîé ïðàâèë (II) è (III) íà ïðàâèëî (I).

Òîãäà ñèñòåìû N

è N

ðàâíîîáúåìíû.

ÑËÅÄÑÒÂÈÅ 2. Åñëè â ñèñòåìå N

çàìåíèòü ïðàâèëà ¬¬ó è ¬â

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

R, ðàâíîîáúåìíàÿ ñèñòåìå N

S Çàìå÷àíèå 2. Ïîçæå áóäåò äîêàçàíî, ÷òî ñõåìà ñíÿòèÿ äâîéíîãî

îòðèöàíèÿ (II) íå ÿâëÿåòñÿ ïðîèçâîäíûì N

-ïðàâèëîì. Ñëåäîâà-

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

112

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

ÿâëÿåòñÿ ïðîèçâîäíûì â N

. Áîëåå òîãî, óòî÷íèâ ïîíÿòèÿ, ìîæíî

äîêàçàòü, ÷òî ñõåìà (II) íå çàâèñèò îò ñõåìû (III), à òàêæå, ÷òî, íå

îïèðàÿñü íà ñõåìó (III), èç ñõåìû (II) âûâåñòè ñõåìó (I) íåâîçìîæ-

íî. 

Ïåðåéäåì îò ñîïîñòàâëåíèÿ ïðàâèë â ñèñòåìàõ

åñòåñòâåííîãî âûâîäà ê íåôîðìàëüíîìó ñîïîñ-

òàâëåíèþ ñîîòâåòñòâóþùèõ ìåòîäîâ äîêàçà-

òåëüñòâ.

Ìåòîä äîêàçàòåëüñòâà îò ïðîòèâíîãî ïðèíÿ-

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

òåëüñòâà, îäíàêî ÷àñòî òåðìèí «äîêàçàòåëüñòâî

îò ïðîòèâíîãî» èñïîëüçóåòñÿ â ðàçíûõ ñìûñëàõ è ïðèìåíèòåëüíî ê

ðàçíûì ìåòîäàì äîêàçàòåëüñòâà. ×àùå âñåãî ìåòîä äîêàçàòåëüñòâà

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

íåëåïîñòè.

Áóêâàìè

áóäåì îáîçíà÷àòü ïðîèçâîëüíûå ïðåäëîæåíèÿ,

à áóêâîé Ã – ïðîèçâîëüíûå êîíå÷íûå ìíîæåñòâà ïðåäëîæåíèé.

Áóäåì èñïîëüçîâàòü çàïèñü Ã ^

A äëÿ îáîçíà÷åíèÿ òîãî ôàêòà, ÷òî

ïðåäëîæåíèå

A îáîñíîâàíî (äîêàçàíî), èñõîäÿ èç ïðåäëîæåíèé Ã,

èëè

A ëîãè÷åñêè ñëåäóåò èç Ã. Îòíîøåíèå ^ ìåæäó ìíîæåñòâàìè

ïðåäëîæåíèé è ïðåäëîæåíèÿìè áóäåì íàçûâàòü îòíîøåíèåì ëîãè-

÷åñêîãî ñëåäîâàíèÿ.

Ìåòîä äîêàçàòåëüñòâà îò ïðîòèâíîãî çàêëþ÷àåòñÿ â ñëåäóþùåì.

Ïóñòü òðåáóåòñÿ äîêàçàòü ïðåäëîæåíèå

A, èñõîäÿ èç íåêîòîðûõ

ïðåäëîæåíèé Ã (ýòî ìîãóò áûòü ðàíåå äîêàçàííûå òåîðåìû, àêñèî-

ìû èëè äîïóùåíèÿ). Äîïóñêàåì, ÷òî

A íåâåðíî, ò. å. äîïóñêàåì ¬A

(íå A), è ïóòåì ðàññóæäåíèé, èñõîäÿ óæå èç Ã è ¬A, âûâîäèì ïðî-

òèâîðå÷èå, ò. å. íåêîòîðîå ïðåäëîæåíèå

è åãî îòðèöàíèå ¬

Ïîñëå ýòîãî ìû çàêëþ÷àåì, ÷òî äîïóùåíèå íåâåðíî, à çíà÷èò, âåð-

íî ïðåäëîæåíèå

A. Íàøå ðàññóæäåíèå ìîæíî îïèñàòü ñ ïîìîùüþ

ñëåäóþùåé íåôîðìàëüíîé ñõåìû ðàññóæäåíèé:

,,Γ¬ ⇒ Γ¬ ⇒¬

Γ⇒

AB A B

. (1)

Èìåííî ýòó ñõåìó ñëåäóåò íàçûâàòü ñõåìîé äîêàçàòåëüñòâà îò

ïðîòèâíîãî.

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

ïðèíàäëåæèò Ô. À. Êàáàêîâó, êîòîðûé ïðîâîäèë ýòó èäåþ â æèçíü íà ïðîòÿæå-

íèè ñîðîêà ëåò ðàáîòû íà ìàòåìàòè÷åñêîì ôàêóëüòåòå ÌÏÃÓ.

Сопоставление

методов

доказательства

от противного

и приведением

к нелепости

113

Ñèòóàöèÿ ìåíÿåòñÿ, êîãäà íóæíî îïðîâåðãíóòü ïðåäëîæåíèå A,

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

èìååò âèä ¬

A (íå A), ò. å. ÿâëÿåòñÿ îòðèöàòåëüíûì ïðåäëîæåíèåì.

Íàïðèìåð, òàêîé âèä èìååò ïðåäëîæåíèå «Íå ñóùåñòâóåò ðàöèî-

íàëüíîãî ÷èñëà, êâàäðàò êîòîðîãî ðàâåí 2». Äîêàçûâàåòñÿ îíî âû-

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

íîå ÷èñëî, êâàäðàò êîòîðîãî ðàâåí 2.

Èòàê, äëÿ òîãî ÷òîáû äîêàçàòü îòðèöàòåëüíîå óòâåðæäåíèå ¬

äîïóñêàåì, ÷òî èìååò ìåñòî

A, è âûâîäèì èç ýòîãî íåêîòîðîå ïðî-

òèâîðå÷èå:

è ¬

. Íåôîðìàëüíàÿ ñõåìà, îïèñûâàþùàÿ òàêîé õîä

ðàññóæäåíèé, âûãëÿäèò òàê:

,,Γ⇒ Γ⇒¬

Γ⇒¬

AB A B

(2)

Ýòó íåôîðìàëüíóþ ñõåìó ðàññóæäåíèé ïðèíÿòî íàçûâàòü ñõå-

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

àáñóðäó (ëàò. reductio ad absurdum).

Ê ñîæàëåíèþ, îáû÷íî â ïðàêòèêå ïðåïîäàâàíèÿ íå ðàçëè÷àþò

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

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

Îñòàíîâèìñÿ íà ïðè÷èíàõ òîãî, ïî÷åìó âñå æå ñëåäóåò ðàçëè-

÷àòü ýòè ñõåìû.

Âî-ïåðâûõ, î÷åâèäíî, ÷òî ýòè ñõåìû ðàçëè÷àþòñÿ ÷èñòî ãðàôè-

÷åñêè, à çíà÷èò, ðàññóæäåíèÿ ïî ýòèì ñõåìàì ðàçëè÷àþòñÿ ïî ôîð-

ìå. Ðàçëè÷èÿ òàêîãî æå õàðàêòåðà, ò. å. ïî êðàéíåé ìåðå ïî ôîðìå,

èìåþòñÿ ìåæäó ïðåäëîæåíèÿìè

A è ¬¬A (èëè ìåæäó ïðåäëîæåíè-

ÿìè

→

è ¬A

∨

). Äàæå åñëè, íàõîäÿñü íà êëàññè÷åñêèõ ïîçè-

öèÿõ, ìû ñ÷èòàåì, ÷òî ýòè óòâåðæäåíèÿ ðàâíîñèëüíû, òî âñå ðàâíî

ôàêò ðàçëè÷èÿ ïî ôîðìå ÿâëÿåòñÿ î÷åâèäíûì.

Îäíàêî òàêîå ðàçëè÷èå ìîæåò êîìó-òî ïîêàçàòüñÿ íåäîñòàòî÷-

íûì, íåóáåäèòåëüíûì äëÿ òîãî, ÷òîáû çàòåâàòü âåñü ýòîò ðàçãîâîð.

Åñòåñòâåííî, âîçíèêàþò âîïðîñû: íå ðàâíîñèëüíû ëè ýòè ñõåìû; â

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

äîêàçàòåëüñòâ; ýòî ðàçëè÷èå ëèøü ïî ôîðìå èëè òàêæå ïî ñóùå-

ñòâó?

Îòâåòèòü íà ïåðâûé âîïðîñ: «Ðàâíîñèëüíû ëè ñõåìû (1) è (2)?»

ìîæíî íà íåôîðìàëüíîì óðîâíå, íå ïåðåõîäÿ íà ïóòü ïîñòðîåíèÿ

ôîðìàëüíîé ëîãè÷åñêîé ñèñòåìû. Ñâÿçü ìåæäó ñõåìàìè (1) è (2)

óñòàíàâëèâàåòñÿ ñëåäóþùèì óòâåðæäåíèåì

Äîêàçàòåëüñòâî ýòîãî óòâåðæäåíèÿ ìîæíî íàéòè â [14].

114

! ÓÒÂÅÐÆÄÅÍÈÅ. Ñõåìà äîêàçàòåëüñòâà îò ïðîòèâíîãî

,,Γ¬ ⇒ Γ¬ ⇒¬

Γ⇒

AB A B

(1)

ðàâíîñèëüíà ñîâîêóïíîñòè äâóõ ñõåì:

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

,,Γ⇒ Γ⇒¬

Γ⇒¬

AB A B

(2)

è ñíÿòèÿ äâîéíîãî îòðèöàíèÿ

¬¬

^ A. (3)

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

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

äîêàçûâàåì ïðèâåäåíèåì ê íåëåïîñòè. Ýòî âûç-

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

ùåñòâåííî îïèðàåòñÿ íà ïðàâèëî ñíÿòèÿ äâîéíîãî îòðèöàíèÿ, à äî-

êàçàòåëüñòâî ïðèâåäåíèåì ê íåëåïîñòè – íåò. Èìåííî áëàãîäàðÿ

ýòîìó îáñòîÿòåëüñòâó ðàçëè÷èå ìåæäó ñõåìàìè (1) è (2) – ýòî ðàçëè-

÷èå íå òîëüêî ïî ôîðìå, íî è ïî ñóùåñòâó. Áîëåå òîãî, ýòî ðàçëè÷èå

òåñíî ñâÿçàíî ñ íåêîòîðûìè ïðîáëåìàìè îñíîâàíèé ìàòåìàòèêè.

Äåëî â òîì, ÷òî òàêèå ëîãè÷åñêèå çàêîíû, êàê çàêîí èñêëþ÷åííî-

ãî òðåòüåãî À ∨ ¬À, çàêîí ñíÿòèÿ äâîéíîãî îòðèöàíèÿ ¬¬À ⊃ À è

ñõåìà (1) äîêàçàòåëüñòâà îò ïðîòèâíîãî, ïðèâîäÿò ê íåýôôåêòèâíûì

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

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

ò. å. òåîðåì âèäà «Ñóùåñòâóåò x òàêîé, ÷òî P(x)»: (Eõ) P(õ).

Ýôôåêòèâíûì äîêàçàòåëüñòâîì òåîðåìû âèäà (Eõ) P(õ) íàçû-

âàåòñÿ ïîñòðîåíèå îáúåêòà õ (èëè ñïîñîáà, ïîçâîëÿþùåãî ïî-

ñòðîèòü ýòîò îáúåêò) è äîêàçàòåëüñòâî òîãî, ÷òî ýòîò îáúåêò õ

äåéñòâèòåëüíî îáëàäàåò òðåáóåìûì ñâîéñòâîì P. Äîêàçàòåëü-

ñòâî òåîðåìû ñóùåñòâîâàíèÿ, íå óäîâëåòâîðÿþùåå ýòèì óñëî-

âèÿì, ñ÷èòàþò íåýôôåêòèâíûì.

Òèïè÷íûì íåýôôåêòèâíûì äîêàçàòåëüñòâîì òåîðåìû ñóùåñòâî-

âàíèÿ ÿâëÿåòñÿ äîêàçàòåëüñòâî ìåòîäîì îò ïðîòèâíîãî. Äåéñòâè-

òåëüíî, ïóñòü òðåáóåòñÿ äîêàçàòü óòâåðæäåíèå âèäà (Eõ) P(õ) –

«ñóùåñòâóåò îáúåêò õ, îáëàäàþùèé ñâîéñòâîì P». Äîïóñòèì, ÷òî

¬(Eõ) P(õ). Ïóòåì ðàññóæäåíèÿ ïîëó÷àåì íåêîòîðîå ïðîòèâîðå÷èå:

Â è ¬Â. Îòñþäà, â ñèëó ñõåìû reductio ad absurdum, äåëàåì âûâîä,

Эффективные

и неэффективные

доказательства

115

÷òî äîïóùåíèå íåâåðíî, ò. å. ¬¬(Eõ) P(õ). Äàëåå, ñíèìàÿ äâîéíîå

îòðèöàíèå, ïîëó÷àåì (Eõ) P(õ) è ñ÷èòàåì äîêàçàòåëüñòâî çàâåðøåí-

íûì. Îäíàêî òàêîå äîêàçàòåëüñòâî íå çàâåðøàåòñÿ ïîñòðîåíèåì

õîòÿ áû îäíîãî îáúåêòà ñ òðåáóåìûì ñâîéñòâîì, îíî íèñêîëüêî íå

ïðèáëèæàåò íàñ ê ïîñòðîåíèþ ïðèìåðà òàêîãî õ, ÷òî P(õ), ò. å.

ÿâëÿåòñÿ íåýôôåêòèâíûì äîêàçàòåëüñòâîì.

Ïðèìåðàìè äîêàçàòåëüñòâ òàêîãî âèäà ñëóæàò äîêàçàòåëüñòâà

ñëåäóþùèõ òåîðåì: òåîðåìû îá îãðàíè÷åííîñòè íåïðåðûâíîé íà

îòðåçêå ôóíêöèè (ò. å. î ñóùåñòâîâàíèè âåðõíåé è íèæíåé ãðàíèö

íåïðåðûâíîé íà îòðåçêå ôóíêöèè); òåîðåìû î ñóùåñòâîâàíèè íàè-

áîëüøåãî è íàèìåíüøåãî çíà÷åíèé ó íåïðåðûâíîé íà îòðåçêå ôóí-

êöèè. Òðàäèöèîííîå äîêàçàòåëüñòâî ýòèõ òåîðåì ìåòîäîì îò ïðî-

òèâíîãî íå ñîäåðæèò êîíñòðóêöèè, ïîçâîëÿþùåé ïîñòðîèòü îáúåêò,

î ñóùåñòâîâàíèè êîòîðîãî èäåò ðå÷ü â òåîðåìå.

Íåýôôåêòèâíûå äîêàçàòåëüñòâà òåîðåì ñóùåñòâîâàíèÿ ïðèçíà-

þòñÿ íå âñåìè ìàòåìàòèêàìè. Äëÿ ìàòåìàòèêîâ, ñòîÿùèõ íà òðàäè-

öèîííûõ êëàññè÷åñêèõ ïîçèöèÿõ, õàðàêòåðíûì ÿâëÿåòñÿ ïðèçíàíèå

áåç âñÿêèõ îãðàíè÷åíèé çàêîíà èñêëþ÷åííîãî òðåòüåãî À ∨ ¬À è

çàêîíà ñíÿòèÿ äâîéíîãî îòðèöàíèÿ ¬¬À ⊃ À. Îíè ïðåíåáðåãàþò ðàç-

ëè÷èÿìè ìåæäó óòâåðæäåíèÿìè (Eõ) P(õ) è ¬¬(Eõ) P(õ). Ìàòåìàòè-

êè, íå ïðèäåðæèâàþùèåñÿ êëàññè÷åñêèõ âçãëÿäîâ (èíòóèöèîíèñòû

è êîíñòðóêòèâèñòû), îòðèöàþò óíèâåðñàëüíîñòü ýòèõ çàêîíîâ. Ðàç-

ëè÷èÿ ìåæäó óòâåðæäåíèÿìè (Eõ) P(õ) è ¬¬(Eõ) P(õ) òàêèå ìàòåìàòè-

êè ïðèçíàþò âåñüìà ñóùåñòâåííûìè, ñ÷èòàÿ óòâåðæäåíèå ¬¬(Eõ) P(õ),

âîîáùå ãîâîðÿ, áîëåå ñëàáûì, ÷åì (Eõ) P(õ). Äîêàçàòåëüñòâî îò ïðî-

òèâíîãî, ñ èõ òî÷êè çðåíèÿ, òàêæå ÿâëÿåòñÿ íåïðèåìëåìûì, ïîñêîëüêó

îíî îïèðàåòñÿ íà ïðèíöèï ñíÿòèÿ äâîéíîãî îòðèöàíèÿ.

Òàêèì îáðàçîì, ðàçëè÷èå ìåæäó ñõåìàìè (1) è (2) íîñèò ìåòî-

äîëîãè÷åñêèé õàðàêòåð, çàòðàãèâàÿ ïðîáëåìó ðàçíîãî ïîíèìàíèÿ

óòâåðæäåíèé î ñóùåñòâîâàíèè â ìàòåìàòèêå, à òàêæå ñâÿçàííûå ñ

ýòèì äðóãèå ïðîáëåìû îñíîâàíèé ìàòåìàòèêè (ñì. ãë. 6).

§ 2.11. Èíòåðïðåòàöèè ÿçûêà§ 2.11. Èíòåðïðåòàöèè ÿçûêà

§ 2.11. Èíòåðïðåòàöèè ÿçûêà

ëîãèêè âûñêàçûâàíèéëîãèêè âûñêàçûâàíèé

ëîãèêè âûñêàçûâàíèé

Ïîä èíòåðïðåòàöèåé (îò ëàò. interpretatio –

«ðàçúÿñíåíèå, èñòîëêîâàíèå») â ëîãèêå ïîíèìàþò èñòîëêîâàíèå,

ðàçúÿñíåíèå ñìûñëà, çíà÷åíèÿ ÿçûêîâûõ âûðàæåíèé; ïðèïèñûâà-

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

ìóëàì ôîðìàëüíîãî ÿçûêà; ðàññìîòðåíèå åãî êàê ÿçûêà, îïèñûâà-

þùåãî òó èëè èíóþ ïðåäìåòíóþ îáëàñòü. Ñàìó ýòó ïðåäìåòíóþ

116

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

íàçûâàþò èíòåðïðåòàöèåé.

Ëîãè÷åñêàÿ ñåìàíòèêà – ðàçäåë ëîãèêè, èññëåäóþùèé (àíàëè-

çèðóþùèé) âçàèìîñâÿçü ìåæäó ÿçûêîâûìè âûðàæåíèÿìè è âûðà-

æàåìûì èìè ñîäåðæàíèåì. Ê îñíîâíûì ñåìàíòè÷åñêèì êàòåãîðè-

ÿì îòíîñÿòñÿ «èíòåðïðåòàöèÿ», «ìîäåëü», «âûïîëíèìîñòü», «èñ-

òèííîñòü» è ò. ï. Âîïðîñû ñåìàíòèêè èãðàþò áîëüøóþ ðîëü â òåî-

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

Â § 1.3 óæå áûëî ðàññìîòðåíî îäíî èç òîëêîâàíèé ïðîïîçèöè-

îíàëüíûõ ñâÿçîê è ôîðìóë ßËÂ. Ïðîïîçèöèîíàëüíûå ïåðåìåííûå

ðàññìàòðèâàëèñü êàê ïåðåìåííûå ïî ìíîæåñòâó {È, Ë} èëè, êàê

íàì ñåé÷àñ áóäåò óäîáíåå ñ÷èòàòü, ïî ìíîæåñòâó {1, 0}, à ïðîïîçè-

öèîíàëüíûå ñâÿçêè &, ∨, ⊃, ¬ áûëè èíòåðïðåòèðîâàíû êàê èçâåñ-

òíûå îïåðàöèè íà ýòîì ìíîæåñòâå. Îäíàêî ýòî íå åäèíñòâåííàÿ

èíòåðïðåòàöèÿ ßËÂ. Âîçìîæíû è äðóãèå âàðèàíòû òîëêîâàíèÿ,

îñìûñëåíèÿ ñèìâîëîâ ßËÂ.

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

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

òîëêîâûâàòü êàê íåêîòîðûå îïåðàöèè íà ýòîì ìíîæåñòâå. Ââåäåì

îáùåå ïîíÿòèå èíòåðïðåòàöèè ßËÂ.

Èíòåðïðåòàöèåé ßËÂ íàçûâàþò âñÿêóþ àëãåáðàè÷åñêóþ ñèñ-

òåìó M = <M, &

, ∨

, ⊃

, ¬

, 1

>, ãäå M – íåïóñòîå ìíî-

æåñòâî (ïîëå èíòåðïðåòàöèè); &

, ∨

, ⊃

– áèíàðíûå îïåðà-

öèè íà M; ¬

– óíàðíàÿ îïåðàöèÿ íà M; 1

– íåêîòîðûé

ýëåìåíò Ì, êîòîðûé íàçûâàþò âûäåëåííûì ýëåìåíòîì M.

Èíòåðïðåòàöèþ M

= <{0, 1},

∨

⊃

, 1>, ãäå

∨

⊃

–

îïåðàöèè íà ìíîæåñòâå {0, 1}, îïðåäåëÿåìûå ñ ïîìîùüþ èçâå-

ñòíûõ èñòèííîñòíûõ òàáëèö (ñì. § 1.3), à âûäåëåííûì ýëåìåí-

òîì ÿâëÿåòñÿ 1, íàçûâàþò ãëàâíîé èíòåðïðåòàöèåé ßËÂ.

Ïóñòü M – íåêîòîðàÿ èíòåðïðåòàöèÿ ßËÂ, à F – ïðîèçâîëüíàÿ

ôîðìóëà. Åñëè ïåðåìåííûì ôîðìóëû F ïðèäàòü êàêèå-ëèáî çíà÷åíèÿ

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

âåòñòâóþùèìè èì îïåðàöèÿìè íà ìíîæåñòâå Ì (òî÷íåå, îáîçíà÷åíèÿ-

ìè ýòèõ îïåðàöèé), òî ïîëó÷åííûé â ðåçóëüòàòå âû÷èñëåíèé ýëåìåíò

èç Ì íàçûâàþò çíà÷åíèåì ôîðìóëû F ïðè çàäàííûõ çíà÷åíèÿõ åå ïåðå-

ìåííûõ. Óòî÷íèì ýòî ïîíÿòèå ïðè ïîìîùè ñëåäóþùèõ îïðåäåëåíèé.

Îöåíêîé â èíòåðïðåòàöèè M íàçûâàþò âñÿêîå îòîáðàæåíèå v

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

ñòâî M – ïîëå èíòåðïðåòàöèè, ò. å. îòîáðàæåíèå âèäà Vr → Ì.

117

Ïóñòü M – ïðîèçâîëüíàÿ èíòåðïðåòàöèÿ ßËÂ, à v – íåêîòîðàÿ

îöåíêà â ýòîé èíòåðïðåòàöèè. Êàæäîé ôîðìóëå F ñîïîñòàâèì ýëå-

ìåíò èç Ì, êîòîðûé áóäåì íàçûâàòü çíà÷åíèåì ôîðìóëû F â èí-

òåðïðåòàöèè M ïðè îöåíêå v è îáîçíà÷àòü ÷åðåç v(F).

Îïðåäåëåíèå çíà÷åíèÿ ôîðìóëû F â èíòåðïðåòàöèè M ïðè îöåí-

êå v.

1. Äëÿ âñÿêîé ïðîïîçèöèîíàëüíîé ïåðåìåííîé p

åå çíà÷åíèå

v(p

) çàäàåòñÿ îöåíêîé v.

2. Ïóñòü À è Â – ïðîèçâîëüíûå ôîðìóëû è çíà÷åíèÿ v(À) è v(Â)

îïðåäåëåíû. Òîãäà:

à) v(À ⊕ Â) = v(À)

⊕

v(B), ãäå ⊕ – ëþáàÿ èç ñâÿçîê &, ∨, ⊃;

á) v(¬À) = ¬

v(À).

Çàìåòèì, ÷òî, äëÿ òîãî ÷òîáû íàéòè v(F), äîñòàòî÷íî çàäàòü

çíà÷åíèÿ v(

), …, v(

), ãäå ω = (

, ...,

) – ñîáñòâåííûé

ñïèñîê ôîðìóëû F. Òàêèì îáðàçîì, ìîæíî ââåñòè ïîíÿòèå çíà÷å-

íèÿ ôîðìóëû F â èíòåðïðåòàöèè M íà íàáîðå α = (α

, …, α

) ýëå-

ìåíòîâ èç M îòíîñèòåëüíî ñîáñòâåííîãî ñïèñêà ôîðìóëû F (è

îáîçíà÷åíèå | F |

α, M

) àíàëîãè÷íî òîìó, êàê ýòî áûëî ñäåëàíî

äëÿ ãëàâíîé èíòåðïðåòàöèè. Ïðè ýòîì åñëè ω = (

, ...,

) –

ñîáñòâåííûé ñïèñîê ôîðìóëû F, à α = (v(

), …, v(

)), òî

v(F) = | F |

α, M

Èñïîëüçóÿ èíäóêöèþ ïî ïîñòðîåíèþ ôîðìóëû, ìîæíî äîêà-

çàòü, ÷òî åñëè îöåíêè v

è v

â èíòåðïðåòàöèè M óäîâëåòâîðÿþò

óñëîâèþ v

(

) = v

(

), ..., v

(

) = v

(

), òî v

(F) = v

(F) äëÿ

ëþáîé ôîðìóëû F ñ äîïóñòèìûì ñïèñêîì ω = (

, ...,

Áóäåì íàçûâàòü ôîðìóëó F îáùåçíà÷èìîé â èíòåðïðåòàöèè M

(èëè êðàòêî M-îáùåçíà÷èìîé) è ïèñàòü



F, åñëè ïðè ëþ-

áîé îöåíêå v â ýòîé èíòåðïðåòàöèè v(F) = 1

Î÷åâèäíî, ÷òî M

-îáùåçíà÷èìûìè ôîðìóëàìè ÿâëÿþòñÿ âñå

òàâòîëîãèè è òîëüêî îíè.

Ïóñòü N – ïðîèçâîëüíàÿ ïðîïîçèöèîíàëüíàÿ ñèñòåìà åñòåñòâåí-

íîãî âûâîäà.

118

Ìîäåëüþ ñèñòåìû åñòåñòâåííîãî âûâîäà N áóäåì íàçûâàòü

âñÿêóþ èíòåðïðåòàöèþ ßËÂ M, â êîòîðîé îáùåçíà÷èìû âñå

N-âûâîäèìûå ôîðìóëû. Ñèìâîëè÷åñêè ýòî óñëîâèå ìîæíî

çàïèñàòü òàê: (F) (



F →



F).

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

è N

ñâèäåòåëüñòâó-

åò î òîì, ÷òî ãëàâíàÿ èíòåðïðåòàöèÿ ßËÂ M

ÿâëÿåòñÿ ìîäåëüþ

ñèñòåì N

è N

Ââåäåì îòíîøåíèå M-ñëåäîâàíèÿ



àíàëîãè÷íî òîìó, êàê áûëî

ââåäåíî îòíîøåíèå ñåìàíòè÷åñêîãî ñëåäîâàíèÿ



Ïóñòü M – ïðîèçâîëüíàÿ èíòåðïðåòàöèÿ ßËÂ. Áóäåì ãîâîðèòü,

÷òî èç ìíîæåñòâà ôîðìóë Ã M-ñëåäóåò ôîðìóëà F (è ïèñàòü



F), åñëè äëÿ ëþáîé îöåíêè v â èíòåðïðåòàöèè M, ïðè êî-

òîðîé âñå ôîðìóëû èç Ã ïðèíèìàþò çíà÷åíèå 1

, ôîðìóëà F

òàêæå ïðèíèìàåò çíà÷åíèå 1

. Ñèìâîëè÷åñêè ýòî îïðåäåëåíèå

ìîæíî çàïèñàòü òàê:



def

←⎯ ⎯→

(v) (v(Ã) = 1

→ v(F) = 1

ãäå çàïèñü v(Ã) = 1

îçíà÷àåò, ÷òî v(À) = 1

äëÿ ëþáîé ôîðìóëû

À èç Ã.

Î÷åâèäíî, ÷òî îòíîøåíèå M

-ñëåäîâàíèÿ åñòü íå ÷òî èíîå,

êàê îòíîøåíèå ñåìàíòè÷åñêîãî ñëåäîâàíèÿ



ÒÅÎÐÅÌÀ (î äîñòàòî÷íîì óñëîâèè ìîäåëè). Ïóñòü N – ïðîèç-

âîëüíàÿ ñèñòåìà åñòåñòâåííîãî âûâîäà, M – ïðîèçâîëüíàÿ èíòåð-

ïðåòàöèÿ ßËÂ. Åñëè âñå N-ïðàâèëà ñîõðàíÿþò îòíîøåíèå



, òî

M ÿâëÿåòñÿ ìîäåëüþ N.

Äîêàçàòåëüñòâî. Âî-ïåðâûõ, îòíîøåíèå M-ñëåäîâàíèÿ



ðåôëåêñèâíî è ìîíîòîííî. Âî-âòîðûõ, ïî óñëîâèþ âñå

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



. Ñëåäîâàòåëüíî, â ñèëó ïðèí-

öèïà èíäóêöèè äëÿ N-âûâîäîâ (âî âòîðîé ôîðìå), îòíîøåíèå

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



ñîãëàñîâàíî ñ îòíîøåíèåì



, ò. å.

(Ã) (F) (Ã



F ® Ã



F).

Îòñþäà ïðè ïóñòîì Ã ïîëó÷àåì

119

(F) (



F ®



F).

Òàêèì îáðàçîì, M ÿâëÿåòñÿ ìîäåëüþ ñèñòåìû N.



Çàìå÷àíèå 1. Îáðàòíîå óòâåðæäåíèå íåâåðíî. Òàê, äëÿ ñèñòåìû

ìîæíî ïðèâåñòè ïðèìåð ìîäåëè, òàêîé ÷òî ïðàâèëî ⊃â íå ñî-

õðàíÿåò îòíîøåíèå



(ñì. íèæå àëãåáðó Ëèíäåíáàóìà). 

Ïóñòü M – ìîäåëü ñèñòåìû N. Âîçíèêàåò âîïðîñ: âåðíî ëè,

÷òî âñå M-îáùåçíà÷èìûå ôîðìóëû N-âûâîäèìû? Îêàçûâàåòñÿ,

÷òî ýòî âûïîëíÿåòñÿ äàëåêî íå äëÿ âñÿêîé ìîäåëè.

Òî÷íîé ìîäåëüþ ñèñòåìû N íàçûâàþò âñÿêóþ ìîäåëü M ýòîé

ñèñòåìû òàêóþ, ÷òî ëþáàÿ M-îáùåçíà÷èìàÿ ôîðìóëà ÿâëÿåòñÿ

N-âûâîäèìîé, ò. å. åñëè

(F) (



F →



F).

Òàêèì îáðàçîì, èíòåðïðåòàöèÿ M ÿâëÿåòñÿ òî÷íîé ìîäåëüþ

ñèñòåìû N òîãäà è òîëüêî òîãäà, êîãäà êëàññû M-îáùåçíà÷èìûõ

ôîðìóë è N-âûâîäèìûõ ôîðìóë ñîâïàäàþò:

(F) (



F ↔



F).

Òåîðåìà î ïîëíîòå N

îòíîñèòåëüíî êëàññà òàâòîëîãèé ñâèäå-

òåëüñòâóåò î òîì, ÷òî ãëàâíàÿ èíòåðïðåòàöèÿ ßËÂ M

ÿâëÿåòñÿ òî÷-

íîé ìîäåëüþ N

(åå íàçûâàþò ãëàâíîé ìîäåëüþ ñèñòåìû N

ÒÅÎÐÅÌÀ. Åñëè ñèñòåìà N èìååò êîíå÷íóþ òî÷íóþ ìîäåëü,

òî ýòà ñèñòåìà ðàçðåøèìà.

Äîêàçàòåëüñòâî. Áóäåì èñõîäèòü èç òîãî, ÷òî êîíå÷íàÿ

ìîäåëü M çàäàíà ýôôåêòèâíî (êîíå÷íîå ïîëå èíòåðïðåòàöèè – ñïèñ-

êîì ýëåìåíòîâ, îïåðàöèè – òàáëè÷íî). Òîãäà ðàçðåøàþùèé àëãî-

ðèòì çàêëþ÷àåòñÿ â ïðîâåðêå äàííîé ôîðìóëû F íà M-îáùåçíà÷è-

ìîñòü ñ ïîìîùüþ âû÷èñëåíèÿ çíà÷åíèé F íà âñåâîçìîæíûõ íàáî-

ðàõ çíà÷åíèé èç M äëÿ ñîáñòâåííîãî ñïèñêà ïåðåìåííûõ ôîðìóëû F

(ìíîæåñòâî òàêèõ íàáîðîâ êîíå÷íî â ñèëó êîíå÷íîñòè M).



Çàìå÷àíèå 2. Îêàçûâàåòñÿ, ÷òî íå âñÿêàÿ ðàçðåøèìàÿ ñèñòåìà

èìååò êîíå÷íóþ òî÷íóþ ìîäåëü. Êàê óæå îòìå÷àëîñü ðàíåå (áåç

äîêàçàòåëüñòâà), ñèñòåìà N

ðàçðåøèìà, îäíàêî êîíå÷íîé òî÷íîé

ìîäåëè îíà íå èìååò (ñì. ñëåäóþùóþ òåîðåìó). 

★ Èíòåðïðåòàöèþ ßËÂ, à òàêæå ìîäåëü ñèñòåìû N, M íàçûâàþò

ðåãóëÿðíîé, åñëè äëÿ ëþáûõ ôîðìóë À è Â âûïîëíÿåòñÿ óñëîâèå

À, À ⊃ Â



Â. Ëåãêî âèäåòü, ÷òî èíòåðïðåòàöèÿ M ÿâëÿåòñÿ ðåãó-

120

ëÿðíîé òîãäà è òîëüêî òîãäà, êîãäà ïðàâèëî ⊃ó ñîõðàíÿåò îòíîøå-

íèå M-ñëåäîâàíèÿ



Î÷åâèäíî, ãëàâíàÿ èíòåðïðåòàöèÿ M

ÿâëÿåòñÿ ðåãóëÿðíîé. ✰

Ïðèìåðû.

1. Ïóñòü Å – ïðîèçâîëüíîå ìíîæåñòâî. Îáîçíà÷èì ÷åðåç Â(Å) –

ìíîæåñòâî âñåõ åãî ïîäìíîæåñòâ (áóëåàí ìíîæåñòâà Å). Ðàññìîò-

ðèì èíòåðïðåòàöèþ B

= <Â(Å), &

, ∨

, ⊃

, ¬

, 1

>, ãäå 1

= Å è

äëÿ ëþáûõ ìíîæåñòâ Å

è Å

– ïîäìíîæåñòâ Å: Å

= Å

∩ Å

;

∨

= Å

∪ Å

; Å

⊃

= (Å \ Å

) ∪ Å

; ¬

= Å \ Å

. Èñïîëü-

çóÿ äîñòàòî÷íîå óñëîâèå ìîäåëè, ìîæíî äîêàçàòü, ÷òî B

– ìîäåëü

è N

. Áîëåå òîãî, ìîæíî äîêàçàòü, ÷òî äëÿ âñÿêîãî íåïóñòîãî

ìíîæåñòâà Å èíòåðïðåòàöèÿ B

ÿâëÿåòñÿ òî÷íîé ìîäåëüþ N

Ñ ýòîé öåëüþ ìîæíî ðàññìîòðåòü ïîäàëãåáðó B

àëãåáðû B

íîñèòåëåì (ïîëåì) {∅, Å}, èçîìîðôíóþ M

– ãëàâíîé ìîäåëè N

è äîêàçàòü, ÷òî åñëè



À, òî



À è



À, à çíà÷èò,



2. Ðàññìîòðèì èíòåðïðåòàöèþ M = <M, &

, ∨

, ⊃

, ¬

, 1

ãäå M = {0, 1/2, 1}, 1

= 1 è äëÿ ëþáûõ à, b èç M:

à &

b = min {a, b}; à ∨

b = max {a, b};

åñëè

1, ;

àb

bàb

≤

⊃=

⎧

⎨

⎩

åñëè

1, 0;

0, 0.

¬=

≠

⎧

⎨

⎩

Ìîæíî äîêàçàòü, ÷òî ýòà èíòåðïðåòàöèÿ ÿâëÿåòñÿ ìîäåëüþ N

3. Ìîæíî äîêàçàòü, ÷òî äëÿ ëþáîãî n (n = 1, 2, …) èíòåðïðåòàöèÿ

= < M

, &

, ∨

, ⊃

, ¬

, 1>, ãäå M

= {0, 1/n, 2/n, …, (n – 1)/n, 1}

è äëÿ ëþáûõ à, b èç M

à &

b = min {a, b}; à ∨

b = max {a, b};

åñëè

1, ;

àb

bàb

≤

⊃=

⎧

⎨

⎩

åñëè

1, 0;

0, 0,

¬=

≠

⎧

⎨

⎩

ÿâëÿåòñÿ ìîäåëüþ ñèñòåìû N

(êîíå÷íîé ëèíåéíî óïîðÿäî÷åííîé ìî-

äåëüþ N

). 

★ ÒÅÎÐÅÌÀ (î íåñóùåñòâîâàíèè êîíå÷íîé òî÷íîé ìîäåëè N

Ãåäåëü). Ñèñòåìà åñòåñòâåííîãî âûâîäà N

íå èìååò êîíå÷íîé òî÷-

íîé ìîäåëè.

Äîêàçàòåëüñòâî. Èçëîæèì òîëüêî èäåþ äîêàçàòåëüñòâà.

Ðàññìîòðèì ñëåäóþùóþ ôîðìóëó:

= (p

⊃ p

) ∨ (p

⊃ p

) ∨ (p

⊃ p

) ∨ … ∨(p

⊃ p

n-1

) ∨ … ∨ (p

⊃ p