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

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

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

øåíèÿ îá îïóñêàíèè ñêîáîê ïðè íàïèñàíèè ôîðìóë ßËÂ, òàê êàê

íàëè÷èå ñêîáîê â ôîðìóëàõ â ñîîòâåòñòâèè ñ îïðåäåëåíèåì ÿâëÿåò-

ñÿ

â äàííîì ðàçäåëå ïðèíöèïèàëüíûì.

! ÒÅÎÐÅÌÀ. ßçûê ëîãèêè âûñêàçûâàíèé ðàçðåøèì.

★ Ñôîðìóëèðóåì ðÿä ëåìì, îáëåã÷àþùèõ äîêàçàòåëüñòâî ðàçðå-

øèìîñòè ßËÂ

ËÅÌÌÀ 1. Åñëè ôîðìóëà À íå ÿâëÿåòñÿ ïðîïîçèöèîíàëüíîé

ïåðåìåííîé, òî ñóùåñòâóþò òàêèå ôîðìóëû

Â è Ñ è áèíàðíàÿ ïðî-

ïîçèöèîíàëüíàÿ ñâÿçêà ⊕, ÷òî À



(Â ⊕ Ñ) èëè À



(¬Â).

ËÅÌÌÀ 2. Äëÿ âñÿêîãî ñëîâà Õ

â àëôàâèòå ßËÂ îáîçíà÷èì

÷åðåç L(Õ), R(Õ) ÷èñëî âõîæäåíèé ñîîòâåòñòâåííî ëåâîé ñêîáêè è

ïðàâîé ñêîáêè

â ñëîâî Õ. Òîãäà äëÿ ëþáîé ôîðìóëû À:

à) ñóùåñòâóåò ñëîâî Õ òàêîå, ÷òî À



(Õ); á) L(À) = R(À).

ËÅÌÌÀ 3. Êàêîâû áû íè áûëè ñëîâî Y è ôîðìóëà À:

à) äëÿ âñÿêîãî ñîáñòâåííîãî íà÷àëà Õ ôîðìóëû À L(X) ≥ R(X) + 1;

á) åñëè À íå ÿâëÿåòñÿ ïðîïîçèöèîíàëüíîé ïåðåìåííîé, òî ñó-

ùåñòâóåò åäèíñòâåííîå âõîæäåíèå íåêîòîðîé ïðîïîçèöèîíàëüíîé

ñâÿçêè ⊕ (áèíàðíîé èëè óíàðíîé)

â ôîðìóëó À, òàêîå ÷òî À



Õ ⊕ Y

è L(X) = R(X) + 1 äëÿ íåêîòîðûõ ñëîâ Õ è Y.

ËÅÌÌÀ 4. Ïóñòü À – ñëîâî

â àëôàâèòå ßËÂ, òàêîå ÷òî À



(À

)

äëÿ íåêîòîðîãî ñëîâà À

, è, êðîìå òîãî, äëÿ À ñóùåñòâóåò åäèí-

ñòâåííîå âõîæäåíèå íåêîòîðîé ïðîïîçèöèîíàëüíîé ñâÿçêè ⊕ (áè-

íàðíîé èëè óíàðíîé), òàêîå ÷òî À



(



⊕ Y) è L(

(



) = R(

(



) + 1.

Òàêîå ñëîâî À ÿâëÿåòñÿ ôîðìóëîé òîãäà è òîëüêî òîãäà, êîãäà âûïîë-

íÿåòñÿ êàêîå-ëèáî èç ñëåäóþùèõ äâóõ óñëîâèé:

à) Õ, Y – ôîðìóëû, à ⊕ – áèíàðíàÿ ïðîïîçèöèîíàëüíàÿ ñâÿçêà;

á) Õ – ïóñòîå ñëîâî, Y – ôîðìóëà, à ⊕ – óíàðíàÿ ñâÿçêà ¬.

ËÅÌÌÀ 5. Âñÿêîå ñîáñòâåííîå íà÷àëî ôîðìóëû íå ìîæåò áûòü

ôîðìóëîé.

Ìàòåðèàë, ïðåäñòàâëåííûé â ýòîì ïàðàãðàôå â âèäå ëåìì è ïîäâîäÿùèé

ê ïîñòðîåíèþ ðàçðåøàþùåãî ßËÂ àëãîðèòìà, èçëîæåí â ïîëíîì ñîîòâåòñòâèè

ñ òåì, êàê â òå÷åíèå ìíîãèõ ëåò èçëàãàë òåìó «Ðàçðåøèìîñòü ßËÂ» Ô. À. Êàáà-

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

! ÒÅÎÐÅÌÀ (î åäèíñòâåííîñòè ñèíòàêñè÷åñêîãî àíàëèçà ôîðìóë

ßËÂ). Âñÿêàÿ ôîðìóëà ßËÂ ëèáî ÿâëÿåòñÿ ïðîïîçèöèîíàëüíîé ïå-

ðåìåííîé, ëèáî ìîæåò áûòü ïðåäñòàâëåíà, è ïðèòîì åäèíñòâåí-

íûì îáðàçîì,

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

(À & Â), èëè (À ∨ Â), èëè (À ⊃ Â), èëè (¬Â), ãäå À è

Â – ôîðìóëû.

Çàìå÷àíèå. Åäèíñòâåííîñòü ïðåäñòàâëåíèÿ îçíà÷àåò, ÷òî ôîð-

ìóëû À è Â

â ïåðâûõ òðåõ ñëó÷àÿõ è Â â ÷åòâåðòîì ñëó÷àå îïðåäåëÿ-

þòñÿ îäíîçíà÷íî.



Íà îñíîâàíèè ëåìì 1–5 ìîæíî ïîñòðîèòü àëãîðèòì, ïîçâîëÿ-

þùèé ïî ëþáîìó ñëîâó

â àëôàâèòå ßËÂ âûÿñíèòü, ÿâëÿåòñÿ ýòî

ñëîâî ôîðìóëîé ßËÂ èëè íåò.

Äîêàçàòåëüñòâî ëåìì, òåîðåìû, à òàêæå ïîñòðîåíèå ðàçðåøàþ-

ùåãî ßËÂ àëãîðèòìà îñòàâëÿåì ÷èòàòåëþ.

✰

§ 2.1. Ëîãè÷åñêàÿ ñòðóêòóðà§ 2.1. Ëîãè÷åñêàÿ ñòðóêòóðà

§ 2.1. Ëîãè÷åñêàÿ ñòðóêòóðà

ìàòåìàòè÷åñêèõ äîêàçàòåëüñòâìàòåìàòè÷åñêèõ äîêàçàòåëüñòâ

ìàòåìàòè÷åñêèõ äîêàçàòåëüñòâ

Ìàòåìàòè÷åñêèå äîêàçàòåëüñòâà ÿâëÿþòñÿ ãëàâ-

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

ëà ìàòåìàòè÷åñêîé ëîãèêè. Äëÿ òîãî ÷òîáû ïîíÿòèå ìàòåìàòè÷åñ-

êîãî äîêàçàòåëüñòâà ñòàëî îáúåêòîì èçó÷åíèÿ â ìàòåìàòèêå, íåîá-

õîäèìî ýòî ïîíÿòèå óòî÷íèòü.

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

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

íà èíòóèòèâíîì óðîâíå.

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

îáîñíîâàíèÿ êàêîãî-ëèáî ìàòåìàòè÷åñêîãî óòâåðæäåíèÿ, à åãî ðå-

çóëüòàò, îáû÷íî ïðåäñòàâëåííûé â âèäå íåêîòîðîãî òåêñòà. Îñî-

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

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

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

ñëåäóåò èç (ïðåäøåñòâóþùèõ) ïðåäëîæåíèé òàêèõ-òî». Ïðàâäà, â

ñîäåðæàòåëüíûõ äîêàçàòåëüñòâàõ èñïîëüçóåòñÿ ëèøü ñëîâî «ñëåäî-

âàòåëüíî» (èëè ðàâíîçíà÷íîå ñëîâî), à èç êàêèõ èìåííî ïîñûëîê

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

íî, äà è ñàìè ïîñûëêè, áûâàåò, íå âñå ñôîðìóëèðîâàíû. À ñàìîå

ãëàâíîå – íèêàê íå óòî÷íÿåòñÿ, ÷òî çíà÷èò «ëîãè÷åñêè ñëåäóåò».

Ïðè óòî÷íåíèè ïîä ýòèì ìîæíî ïîíèìàòü ñîîòâåòñòâèå êàæäîãî

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

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

ïðîïóùåííûå ïîñûëêè è øàãè. Îäíàêî íà ïðàêòèêå â íåôîðìàëü-

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

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

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

ðûå íå ÿâëÿþòñÿ ñëåäñòâèÿìè ïðåäûäóùèõ ïðåäëîæåíèé (âåäü òåêñò

ГлаваГлава

Глава

ÈÑ×ÈÑËÅÍÈß ÂÛÑÊÀÇÛÂÀÍÈÉ.ÈÑ×ÈÑËÅÍÈß ÂÛÑÊÀÇÛÂÀÍÈÉ.

ÈÑ×ÈÑËÅÍÈß ÂÛÑÊÀÇÛÂÀÍÈÉ.

ÏÐÎÏÎÇÈÖÈÎÍÀËÜÍÛÅ ÑÈÑÒÅÌÛÏÐÎÏÎÇÈÖÈÎÍÀËÜÍÛÅ ÑÈÑÒÅÌÛ

ÏÐÎÏÎÇÈÖÈÎÍÀËÜÍÛÅ ÑÈÑÒÅÌÛ

ÅÑÒÅÑÒÂÅÍÍÎÃÎ ÂÛÂÎÄÀÅÑÒÅÑÒÂÅÍÍÎÃÎ ÂÛÂÎÄÀ

ÅÑÒÅÑÒÂÅÍÍÎÃÎ ÂÛÂÎÄÀ

Äëÿ êðàòêîñòè â äàëüíåéøåì âìåñòî ìàòåìàòè÷åñêîå äîêàçàòåëüñòâî áó-

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

êîíå÷åí!). Òàêèìè èñõîäíûìè ïðåäëîæåíèÿìè ìîãóò ñëóæèòü àê-

ñèîìû òîé ìàòåìàòè÷åñêîé òåîðèè, â ðàìêàõ êîòîðîé ïðîâîäèòñÿ

äîêàçàòåëüñòâî. Èñõîäíûìè ìîãóò áûòü è ïðåäëîæåíèÿ, èìåþùèå

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

òàêæå âûñòóïàòü âñïîìîãàòåëüíûå äîïóùåíèÿ. Â ñàìîì äåëå, â äî-

êàçàòåëüñòâàõ î÷åíü ÷àñòî âñòðå÷àþòñÿ ñëîâà: «Äîïóñòèì, ÷òî èìå-

åò ìåñòî…». Çàêëþ÷èòåëüíûì â òåêñòå ÿâëÿåòñÿ òî ïðåäëîæåíèå,

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

Îòíîøåíèå ëîãè÷åñêîãî ñëåäîâàíèÿ, êàê áû ìû íè óòî÷íÿëè ýòî

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

ñòâà. Áîëåå òîãî, ýòîò ïîðÿäîê – äðåâîâèäíûé (èìååò âèä äåðåâà ñ

êîðíåì – íàèìåíüøèì ýëåìåíòîì), ïîñêîëüêó íà êàæäîì øàãå

ðàññóæäåíèÿ ïðîèñõîäèò ïåðåõîä îò íåêîòîðûõ ïðåäëîæåíèé À

…, À

ê îäíîìó åäèíñòâåííîìó ïðåäëîæåíèþ Â, íåïîñðåäñòâåííî

ñëåäóþùåìó èç íèõ ïî êàêîìó-ëèáî ïðàâèëó ëîãèêè.

Èòàê, ïðèõîäèì ê ñëåäóþùåìó îïèñàíèþ ïîíÿòèÿ äîêàçàòåëü-

ñòâà â âèäå äåðåâà.

S Ïîä äîêàçàòåëüñòâîì â âèäå äåðåâà áóäåì ïîíèìàòü óïîðÿäî-

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

õîäíîå ïðåäëîæåíèå ÿâëÿåòñÿ àêñèîìîé, èëè äîïóùåíèåì, èëè

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

ñëåäóåò èç íåïîñðåäñòâåííî ïðåäøåñòâóþùèõ åìó ïðåäëîæåíèé ïî

êàêîìó-ëèáî ïðàâèëó âûâîäà (ëîãè÷åñêîìó ïðàâèëó).

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

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

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

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

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

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

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

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

ò. å. ñâåäÿ âñå ê àêñèîìàì.

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

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

ìåâàþòñÿ, íî ÿâíî â ðàññóæäåíèè íå îãîâàðèâàþòñÿ. Êàê ïðàâèëî,

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

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

Ðàññìîòðèì â êà÷åñòâå ïðèìåðà îáû÷íîå íåñëîæíîå äîêàçà-

òåëüñòâî ñëåäóþùåãî óòâåðæäåíèÿ: åñëè íàòóðàëüíîå ÷èñëî íå äå-

ëèòñÿ íà 6 è äåëèòñÿ íà 9, òî îíî íå÷åòíî.

Çàïèøåì ýòî óòâåðæäåíèå, èñïîëüçóÿ ëîãè÷åñêóþ ñèìâîëèêó:

6  n & 9 | n → 2  n.

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

áîé ñëåäóþùåå ðàññóæäåíèå: «Ñîãëàñíî óñëîâèþ, n íå äåëèòñÿ íà

6 è äåëèòñÿ íà 9. Ïîñêîëüêó n äåëèòñÿ íà 9, òî n äåëèòñÿ è íà 3.

Êðîìå òîãî, n íå äåëèòñÿ íà 6, à çíà÷èò, n íå äåëèòñÿ íà 2 èëè íà 3.

Ñëåäîâàòåëüíî, n íå äåëèòñÿ íà 2».

Ïåðå÷èñëèì â âèäå ïîñëåäîâàòåëüíîñòè ïðåäëîæåíèÿ – ÷ëåíû

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

çàïèñè èçâåñòíûå ëîãè÷åñêèå ñèìâîëû:

6  n & 9 | n; 9 | n; 3 | n; 6  n; 2  n

∨

3  n; 2  n.

Ïðè òàêîé ôîðìå äîêàçàòåëüñòâà, ò. å. â âèäå öåïî÷êè óòâåðæ-

äåíèé, íå âèäíî, êàêîå óòâåðæäåíèå èç êàêîãî ñëåäóåò, íå ïðî-

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

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

äåðåâà, âûÿâèâ âñå ëîãè÷åñêèå ñâÿçè ìåæäó ÷ëåíàìè ðàññóæäåíèÿ.

Åñëè ïðåäëîæåíèå Â íåïîñðåäñòâåííî ñëåäóåò èç ïðåäëîæåíèé

, …, À

ïî êàêîìó-ëèáî ïðàâèëó ëîãèêè, áóäåì ïðèâû÷íûì îáðà-

çîì çàïèñûâàòü ýòî òàê:

...

Åñëè æå íà êàêîì-òî øàãå ðàññóæäåíèÿ ñäåëàí ñîêðàùåííûé ïå-

ðåõîä îò ïðåäëîæåíèé À

, …, À

ê ïðåäëîæåíèþ Â, êîòîðûé íå ÿâëÿ-

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

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

...

Êàæäûé òàêîé ñîêðàùåííûé ïåðåõîä îáû÷íî âîçíèêàåò â ðå-

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

äåíèåì, à òàêæå ëîãè÷åñêèõ óìîçàêëþ÷åíèé, ñâÿçàííûõ ñ ýòîé ïî-

ñûëêîé. Äâîéíàÿ ÷åðòà îçíà÷àåò, ÷òî ýòó ïðîïóùåííóþ ïîñûëêó è

ëîãè÷åñêèå ïåðåõîäû ìîæíî âîññòàíîâèòü.

Êðàòêîå ðàññóæäåíèå, ïðèâåäåííîå âûøå, åñëè åãî ïðåäñòàâèòü

â âèäå äåðåâà, èìååò ñëåäóþùèé âèä (ñïðàâà èçîáðàæåí ãðàô, îòðà-

æàþùèé ñòðóêòóðó äåðåâà êàê ÷àñòè÷íî óïîðÿäî÷åííîãî ìíîæåñòâà):

&9|

∨

6







(1)

Âîññòàíîâèâ â êðàòêîì âàðèàíòå ðàññóæäåíèÿ ïðîïóùåííûå

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

ðîãî èçîáðàæåíà åãî ãðàôè÷åñêàÿ ñòðóêòóðà):

6&9| 2|&3| 6|

6&9|

66(2|&3|)

9| 3|

(2 | & 3 | )

23 3|

nn nn n

nnnn

nn n

→

→¬

→

∨







(2)

Èñõîäíûìè â äåðåâå äîêàçàòåëüñòâà (2) ñëóæàò ñëåäóþùèå ïðåä-

ëîæåíèÿ:

6  n & 9 | n – óñëîâèå, êîòîðîå èñïîëüçóåòñÿ äâàæäû;

2 | n & 3 | n → 6 | n è 9 | n → 3 | n – óòâåðæäåíèÿ, äîêàçàòåëüñòâà

êîòîðûõ èçâåñòíû èç àðèôìåòèêè.

Èòàê, ìû óïîðÿäî÷èëè ïðåäëîæåíèÿ, ñîñòàâëÿþùèå êîíêðåò-

íîå ðàññóæäåíèå, â âèäå äåðåâà. Â âåðõóøêàõ «âåòâåé» äåðåâà, òàê

íàçûâàåìûõ «ëèñòüÿõ» äåðåâà, ðàñïîëàãàþòñÿ èñõîäíûå ïðåäëîæå-

íèÿ. Â äàííîì ñëó÷àå ýòî äîïóùåíèÿ, îäíî èç êîòîðûõ ïðåäñòàâ-

ëÿþò ñîáîé òàê íàçûâàåìîå «óñëîâèå», äâà äðóãèõ – ðàíåå äîêàçàí-

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

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

ïîëàãàåòñÿ ïðåäëîæåíèå, êîòîðîå ïîëó÷àåòñÿ ñ ïîìîùüþ íåêîòî-

ðîãî ëîãè÷åñêîãî ïðàâèëà èç ïðåäëîæåíèé, ðàñïîëîæåííûõ íåïîñ-

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

æåíèåì, êðîìå èñõîäíûõ, çàïèñàíû òå ïðåäëîæåíèÿ, èç êîòîðûõ

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

ñëóæèò äîêàçûâàåìîå óòâåðæäåíèå.

Åñëè ñòîëü æå ïîäðîáíîå ðàññóæäåíèå ïðåäñòàâèòü â âèäå ïîñ-

ëåäîâàòåëüíîñòè (öåïî÷êè) ïðåäëîæåíèé, òî ïîëó÷èì ïîñëåäîâà-

òåëüíîñòü, ñîñòîÿùóþ èç òåõ æå ÷ëåíîâ:

6  n & 9 | n; 6  n & 9 | n → 6  n; 6  n; 2 | n & 3 | n → 6 | n;

6  n → ¬(2 | n & 3 | n); ¬(2 | n & 3 | n); 2  n ∨ 3  n;

6  n & 9 | n → 9 | n; 9 | n; 9 | n → 3 | n; 3 | n; 2

 n.

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

êîìïàêòíûì, íî â îòëè÷èå îò äåðåâà äîêàçàòåëüñòâà (2) ëèøåíî

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

íàìè (ëîãè÷åñêóþ ñòðóêòóðó äîêàçàòåëüñòâà). Åñëè åãî ñíàáäèòü

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

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

íå áóäåò:

1) 6  n & 9 | n – äîïóùåíèå (óñëîâèå);

2) 6  n – ëîãè÷åñêè ñëåäóåò èç ïðåäëîæåíèÿ 1;

3) 2 | n & 3 | n → 6 | n – èçâåñòíîå óòâåðæäåíèå èç òåîðèè

äåëèìîñòè;

4) 6  n → ¬(2 | n & 3 | n) – ëîãè÷åñêè ñëåäóåò èç ïðåäëîæåíèÿ 3;

5) ¬(2 | n & 3 | n) – ëîãè÷åñêè ñëåäóåò èç ïðåäëîæåíèé 2 è 4;

6) 2  n ∨ 3  n – ëîãè÷åñêè ñëåäóåò èç ïðåäëîæåíèÿ 5;

7) 9 | n – ëîãè÷åñêè ñëåäóåò èç ïðåäëîæåíèÿ 1;

8) 9 | n → 3 | n – èçâåñòíîå óòâåðæäåíèå èç òåîðèè äåëèìîñòè;

9) 3 | n – ëîãè÷åñêè ñëåäóåò èç ïðåäëîæåíèé 7 è 8;

10) 2  n – ëîãè÷åñêè ñëåäóåò èç ïðåäëîæåíèé 6 è 9.

* * *

Òåïåðü ïåðåéäåì ê îáñóæäåíèþ ëîãè÷åñêèõ ñðåäñòâ, èñïîëüçó-

åìûõ â äîêàçàòåëüñòâàõ. Íàïîìíèì, ÷òî ïîêà íå áûëî äàíî îïèñà-

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

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

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

ñåáå â ýòîì îò÷åòà.

Âîçíèêàþò ñëåäóþùèå âîïðîñû:

– Êàêèìè ëîãè÷åñêèìè ïðàâèëàìè ïîëüçóþòñÿ ìàòåìàòèêè â

äîêàçàòåëüñòâàõ?

– Êàê îïèñàòü âñå äîïóñòèìûå äëÿ èñïîëüçîâàíèÿ ïðàâèëà?

– Ìîæíî ëè îïòèìàëüíûì îáðàçîì îðãàíèçîâàòü ýòè ïðàâèëà

â íåêîòîðóþ ñèñòåìó?

– Êàêèå ïðàâèëà ïðè ýòîì áðàòü çà îñíîâó?

Îòâåòû íà ýòè âîïðîñû áóäóò äàíû â ýòîé ãëàâå.

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

â ìàòåìàòè÷åñêèõ äîêàçàòåëüñòâàõ è îáåñïå÷èâàþùèõ ýëåìåíòàð-

íûå øàãè â äîêàçàòåëüñòâàõ, ïðåäëîæèë Ã. Ãåíöåí [2]. Ýòè ïðàâèëà

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

áóäóò ðàññìîòðåíû â § 2.2.

Ëîãè÷åñêèå âûâîäû â ñèñòåìàõ åñòåñòâåííîãî âûâîäà, ïðåä-

ëîæåííûõ Ãåíöåíîì, òàê íàçûâàåìûå äåðåâüÿ âûâîäà, ïðåäñòàâ-

ëÿþò ñîáîé äåðåâüÿ ôîðìóë, â êîòîðûõ âñå ïåðåõîäû ïðîèñõîäÿò

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

âîäà (èëè âûâîäà â âèäå äåðåâà) è ÿâëÿåòñÿ ìàòåìàòè÷åñêèì óòî÷-

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

ÿâëÿþòñÿ ìàòåìàòè÷åñêèìè ìîäåëÿìè íåôîðìàëüíûõ ìàòåìàòè-

÷åñêèõ äîêàçàòåëüñòâ. Ìàòåìàòè÷åñêîå îïðåäåëåíèå äåðåâà âûâî-

äà áóäåò ñôîðìóëèðîâàíî â § 2.4.

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

âèäå äåðåâà.

Åñëè âìåñòî ïðåäëîæåíèé â óçëàõ äåðåâà (2) ïîìåñòèòü ñîîò-

âåòñòâóþùèå ôîðìóëû, ÿâëÿþùèåñÿ ôîðìàëèçàöèåé ýòèõ ïðåäëî-

æåíèé (è îòðàæàþùèå ëîãè÷åñêóþ ñòðóêòóðó ýòèõ ïðåäëîæåíèé),

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

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

íûå, ñì. § 2.8). Îíî ïîëíîñòüþ îòðàæàåò ëîãè÷åñêóþ ñòðóêòóðó

íàøåãî ñîäåðæàòåëüíîãî äîêàçàòåëüñòâà:

(&)

AB DC A

AADC

DC C

¬⊃

¬¬⊃¬

⊃

¬∨¬

(3)

Â èñõîäíûõ (âåðõíèõ) óçëàõ ýòîãî äåðåâà âûâîäà ðàñïîëîæåíû

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

ùèõ èñõîäíûõ ïðåäëîæåíèé â äåðåâå (2):

¬À & B, D & C ⊃ À, Â ⊃ Ñ.

Åñëè ôîðìàëèçîâàòü ñîäåðæàòåëüíîå ëèíåéíîå äîêàçàòåëüñòâî,

òî ïîëó÷èì ñëåäóþùóþ ïîñëåäîâàòåëüíîñòü ôîðìóë:

¬À & B, ¬À, D & C ⊃ À, ¬À ⊃ ¬(D & C), ¬(D & C),

¬D ∨ ¬C, Â, Â ⊃ Ñ, Ñ, ¬D.

Ïîëó÷èëè òðàäèöèîííûé ôîðìàëüíûé òàê íàçûâàåìûé ëèíåé-

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

íûå ïðàâèëà). Ýòîò ëèíåéíûé âûâîä â îòëè÷èå îò äåðåâà âûâîäà (3)

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

ñâÿçè ìåæäó åãî ÷ëåíàìè (ëîãè÷åñêóþ ñòðóêòóðó âûâîäà).

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

ÿâëåíà ôîðìà êàæäîãî ïðåäëîæåíèÿ, à òàêæå ôîðìà êàæäîãî øàãà

ðàññóæäåíèÿ. Ýòî ïîçâîëèëî âûÿâèòü è ôîðìó âñåãî äîêàçàòåëü-

ñòâà â öåëîì. Î÷åâèäíî, ÷òî íåîáõîäèìîñòü â ñòîëü ïîäðîáíîì

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

íèêàåò, åñëè íóæíî ïðîàíàëèçèðîâàòü åãî ëîãè÷åñêóþ ñòðóêòóðó.

Ïðèíöèïèàëüíî âàæíûì ÿâëÿåòñÿ ñëåäóþùåå îáñòîÿòåëüñòâî.

Êàê áû ìû íå ïðåäñòàâèëè ðàññóæäåíèå – â âèäå ïîñëåäîâàòåëü-

íîñòè ïðåäëîæåíèé èëè â âèäå äåðåâà ïðåäëîæåíèé, ÿâëÿåòñÿ ëè

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

ëîãè÷åñêîé ôîðìû, à îòíþäü íå îò ñîäåðæàíèÿ.

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

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

èç îñíîâíûõ ìåòîäîâ ìàòåìàòè÷åñêîé ëîãèêè. Ìåòîä ôîðìàëèçàöèè

áûë èñïîëüçîâàí Ä. Ãèëüáåðòîì (1862–1943) êàê ìåòîä èçó÷åíèÿ

ìàòåìàòè÷åñêèõ äîêàçàòåëüñòâ è ìàòåìàòè÷åñêèõ òåîðèé ñ öåëüþ äàëü-

íåéøåãî äîêàçàòåëüñòâà íåïðîòèâîðå÷èâîñòè ýòèõ òåîðèé.

Áëàãîäàðÿ Ãèëüáåðòó âîçíèê îñíîâíîé ðàçäåë ìàòåìàòè÷åñêîé

ëîãèêè – òåîðèÿ äîêàçàòåëüñòâ. Âàæíåéøåé çàäà÷åé òåîðèè äîêà-

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

ñòâà. Ìåòîä ôîðìàëèçàöèè ÿâëÿåòñÿ îñíîâíûì ìåòîäîì, ïîçâîëÿ-

þùèì ðàçîáðàòüñÿ â òîì, ÷òî òàêîå äîêàçàòåëüñòâî, è âûðàáîòàòü

ìàòåìàòè÷åñêîå óòî÷íåíèå ýòîãî ïîíÿòèÿ.

S Â ìàòåìàòè÷åñêîé ëîãèêå ñóùåñòâóþò äâà îñíîâíûõ òèïà ìàòå-

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

ãî òèïà âîñõîäÿò ê Ãèëüáåðòó è ïðåäñòàâëÿþò ñîáîé ëèíåéíûå âûâî-

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

ìè ãèëüáåðòîâñêîãî òèïà (ñì. § 2.13). Óòî÷íåíèÿ âòîðîãî òèïà ïðè-

íàäëåæàò íåìåöêîìó ëîãèêó, ó÷åíèêó Ãèëüáåðòà, Ã. Ãåíöåíó (1909–

1945) è ïðåäñòàâëÿþò ñîáîé âûâîäû â âèäå äåðåâà â ñèñòåìàõ åñòå-

ñòâåííîãî (íàòóðàëüíîãî) âûâîäà (ñì. § 2.2).

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

ñòâåííîãî âûâîäà èìååò ðÿä ïðåèìóùåñòâ ïî ñðàâíåíèþ ñ ëèíåéíûì

âûâîäîì â ñèñòåìàõ ãèëüáåðòîâñêîãî òèïà. Ñóòü ýòèõ ïðåèìóùåñòâ

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

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

ëåå åñòåñòâåííóþ è àäåêâàòíóþ ìîäåëü îáû÷íûõ ìàòåìàòè÷åñêèõ äî-

êàçàòåëüñòâ. Ïîýòîìó çà îñíîâó äàëüíåéøåãî èçëîæåíèÿ òåîðèè äî-

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

§ 2.2. Ïðàâèëà çàêëþ÷åíèÿ§ 2.2. Ïðàâèëà çàêëþ÷åíèÿ

§ 2.2. Ïðàâèëà çàêëþ÷åíèÿ

! Âñÿêóþ ôîðìàëüíóþ ëîãè÷åñêóþ ñèñòåìó (ëîãè-

÷åñêîå èñ÷èñëåíèå) çàäàþò ÷åòûðüìÿ êîìïîíåíòàìè: ôîðìàëüíûì ÿçû-

êîì, ìíîæåñòâîì àêñèîì (ò. å. ñïåöèàëüíî âûäåëåííûì ìíîæåñòâîì

ôîðìóë ÿçûêà ýòîé ñèñòåìû, âîçìîæíî ïóñòûì), ïðàâèëàìè çàêëþ-

÷åíèÿ (ïðàâèëàìè âûâîäà) è îïðåäåëåíèåì ôîðìàëüíîãî âûâîäà.

Åñëè ÿçûêîì èñ÷èñëåíèÿ ñëóæèò ßËÂ, òî òàêîå èñ÷èñëåíèå

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

÷åñêîé ñèñòåìîé.

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

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

Íàðÿäó ñ òåðìèíîì åñòåñòâåííûé âûâîä èñïîëüçóþò òåðìèí

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

natural deduction (àíãë.).

Ïîñêîëüêó â ãë. 2 áóäóò ðàññìàòðèâàòüñÿ òîëüêî ïðîïîçèöèî-

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

òåìà åñòåñòâåííîãî âûâîäà» áóäåì ãîâîðèòü ïðîñòî «ñèñòåìà åñòå-

ñòâåííîãî âûâîäà», à èíîãäà è ñîâñåì êîðîòêî – «ñèñòåìà».

Ýòè ñèñòåìû ïðåäñòàâëÿþò ñîáîé íåêîòîðóþ ìîäèôèêàöèþ

ñèñòåì, ïîñòðîåííûõ Ã. Ãåíöåíîì. Íàèáîëåå âàæíûìè èç íèõ ÿâ-

ëÿþòñÿ êëàññè÷åñêàÿ (N

) è èíòóèöèîíèñòñêàÿ (N

) ñèñòåìû åñòå-

ñòâåííîãî âûâîäà. ßçûêîì ýòèõ ñèñòåì ñëóæèò ßËÂ. Ìíîæåñòâî

àêñèîì îáåèõ ñèñòåì ïóñòî.

Çàäàäèì ïðàâèëà çàêëþ÷åíèÿ ýòèõ ñèñòåì. Ïðàâèëà çàêëþ÷åíèÿ

äåëÿòñÿ íà ïðàâèëà ââåäåíèÿ è ïðàâèëà óäàëåíèÿ. Äëÿ êàæäîé ïðîïî-

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

íèÿ ýòîé ñâÿçêè (èíîãäà ïàðà ïðàâèë).

Ïðàâèëà çàêëþ÷åíèÿ èíòóèöèîíèñòñêîé ñèñòåìû N

ïðèâåäå-

íû â ñëåäóþùåé òàáëèöå (A, B, C – ñèìâîëû ìåòàÿçûêà). Ñïðàâà

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

÷åíèå (íàïðèìåð, &â – îáîçíà÷åíèå ïðàâèëà ââåäåíèÿ êîíúþíê-

öèè, ⊃ó – îáîçíà÷åíèå ïðàâèëà óäàëåíèÿ èìïëèêàöèè).

Ïðàâèëà çàêëþ÷åíèÿ

Ïðàâèëà ââåäåíèÿ Ïðàâèëà óäàëåíèÿ

(&â)

(&ó)

∨

(∨â)

[] []

∨

AB C C

(∨ó)

[]

⊃

(⊃â)

⊃AA B

(⊃ó)

[] []

(¬â)

¬AA

(¬ó)

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

, êðîìå óêàçàí-

íûõ â òàáëèöå ïðàâèë, èìååò åùå îäíî – ïðàâèëî óäàëåíèÿ äâîé-

íîãî îòðèöàíèÿ:

¬¬A

(¬¬ó).

Ïðàâèëà çàêëþ÷åíèÿ ñèñòåì N

è N

áóäåì òàêæå íàçûâàòü

-ïðàâèëàìè è N

-ïðàâèëàìè ñîîòâåòñòâåííî.