Анисов А.М. Современная логика

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

241

îçíà÷àåò ñóùåñòâîâàíèå èíäèâèäîâ, íå ñðàâíèìûõ ïî äàííîìó

îòíîøåíèþ. Î äâóõ ñîëäàòàõ õ è ó, èìåþùèõ îäèíàêîâûé ðîñò,

íåëüçÿ ñêàçàòü íè òîãî, ÷òî õ íèæå ó, íè òîãî, ÷òî ó íèæå õ, íè

òîãî, ÷òî õ = ó.

Âñå ðàññìîòðåííûå â ýòîì ïàðàãðàôå îòíîøåíèÿ ïîðÿäêà â

ðåàëüíîñòè ÿâëÿþòñÿ ÷àñòè÷íûìè, íî íå ëèíåéíûìè. Îäíàêî, ÷å-

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

äîê òàì, ãäå åãî âîâñå íå ñóùåñòâóåò. Âûñòðàèâàíèå â ëèíèþ ïî

ðîñòó ñîëäàò îäèíàêîâîãî ðîñòà – íå ñàìûé ïëîõîé ïðèìåð íå-

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

ñàìîãî õîðîøåãî èëè ñàìîãî ïëîõîãî, ñàìîãî óìíîãî èëè ñàìîãî

ãëóïîãî, ñàìîãî êðàñèâîãî èëè ñàìîãî óðîäëèâîãî. Ïðåäïîñûë-

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

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

òû íà ïëàöó. À çàòåì, äåñêàòü, ìîæíî âûáðàòü êðàéíèõ. Íî â

äåéñòâèòåëüíîñòè êðàéíèõ ìîæåò è íå áûòü! Äàæå â ãðóïïå èç

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

ìîãî êðàñèâîãî. Ïðîñòî ýòè äâà ÷åëîâåêà íåñðàâíèìû ïî íà-

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

íà ñâîé ìàíåð óìíàÿ è êðàñèâàÿ. Íà íàø âçãëÿä, íåìíîãî â ìèðå

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

Âñ¸ æå èìååòñÿ äîñòàòî÷íî ìíîãî ñèòóàöèé, êîãäà ïðèìåíå-

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

êå íàòóðàëüíûå, îòðèöàòåëüíûå, öåëûå, ðàöèîíàëüíûå è äåé-

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

îòíîøåíèåì ìåíüøå èëè îòíîøåíèåì áîëüøå). À âîò îòíîøå-

íèå âêëþ÷åíèÿ ⊂ îäíîãî ìíîæåñòâà ÷èñåë â äðóãîå ìíîæåñòâî

÷èñåë îêàçûâàåòñÿ îòíîøåíèåì íå ëèíåéíîãî, à òîëüêî ÷àñòè÷-

íîãî ïîðÿäêà. Òàê, ìíîæåñòâà {0, 1}, {0, 1, 2} è {0, 1, 3} âûïîëíÿ-

þò âêëþ÷åíèÿ {0, 1} ⊂ {0, 1, 2} è {0, 1} ⊂ {0, 1, 3}, íî íè {0, 1, 2}

⊂ {0, 1, 3}, íè {0, 1, 3} ⊂ {0, 1, 2}, íè {0, 1, 2} = {0, 1, 3} íå

âûïîëíÿþòñÿ.

Èíîãäà áûâàåò íå âïîëíå ïîíÿòíî, êàê óïîðÿäî÷åíû ðåàëü-

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

ñÿ â òîì, ÷òî âðåìÿ óïîðÿäî÷èâàåò ñîáûòèÿ. Íî êàêîé ïîðÿäîê

ðåàëèçîâàí ïðèðîäîé íà ìíîæåñòâå ìãíîâåíèé âðåìåíè? Îáû÷-

íî äëÿ ïðîñòîòû åãî ñ÷èòàþò ëèíåéíûì. Äëÿ ìíîãèõ íàó÷íûõ è

ïðàêòè÷åñêèõ çàäà÷ ýòîãî äîñòàòî÷íî. Íàïðèìåð, êîëëèçèÿ ñ

÷àøêîé, êîòîðàÿ ðàçáèëàñü è óïàëà, òåïåðü ðàçðåøàåòñÿ ëåãêî.

Íàäî âçÿòü âûñêàçûâàíèÿ «×àøêà ðàçáèëàñü â ìîìåíò âðåìåíè

t» è «×àøêà óïàëà â ìîìåíò âðåìåíè s», äîáàâèâ ê íèì: «È ïðè

ýòîì s ðàíüøå t».

242

Òåìïîðàëüíîå îòíîøåíèå ðàíüøå (äâîéñòâåííûì îáðàçîì,

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

ïîðÿäêà, íî îñòà¸òñÿ, òåì íå ìåíåå, çàãàäî÷íûì äî ñèõ ïîð. Åñëè

äîïóñòèòü, ÷òî ýòî îòíîøåíèå ëèíåéíî, òî âñå ìãíîâåíèÿ âðå-

ìåíè âûñòðîÿòñÿ â ëèíèþ. Òîãäà áóäóùåå ïîëíîñòüþ ïðåäîïðå-

äåëåíî, è íè÷åãî èçìåíèòü â íàøåé ñóäüáå íåëüçÿ. Ìîæåò áûòü,

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

áóäóùåå â êàæäîì ìîìåíòå, îáåñïå÷èâàÿ â êàæäîå ìãíîâåíèå

àëüòåðíàòèâíîñòü áóäóùåãî? Â ñëó÷àå óòâåðäèòåëüíîãî îòâåòà

ïîòðåáóåòñÿ ê èìåþùèìñÿ àêñèîìàì ÷àñòè÷íîãî ïîðÿäêà äîáà-

âèòü ñëåäóþùóþ àêñèîìó.

Â′3. ∀õ∃ó∃z(õ < ó & x < z & ¬(y < z) & ¬(z < y) & y ≠ z)

Àêñèîìà Â′3 ïðîòèâîðå÷èò àêñèîìå ñâÿçíîñòè Â3, ïîýòîìó â

çàâèñèìîñòè îò ðåøàåìûõ çàäà÷ âûáðàòü íóæíî ÷òî-òî îäíî.

§4. Òåîðèÿ ðîäñòâåííûõ îòíîøåíèé

Â êíèãå «Ëîãèêà è êîìïüþòåð» (Ì., 1996) óòâåðæäàåòñÿ: «Òå-

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

ìûõ îáúåêòîâ – ëþäè.» Â ñòðîÿùåéñÿ â ýòîé êíèãå òåîðèè èìå-

þòñÿ äâà èñõîäíûõ ïðåäèêàòà: Ð(õ,ó) – õ ðîäèòåëü ó è Ì(õ) –

ìóæ÷èíà õ.

Äàþòñÿ ÿâíûå îïðåäåëåíèÿ íåêîòîðûì íîâûì ïîíÿòèÿì.

«Æåíùèíà»: W(õ) ↔ ¬Ì(õ)

«Îòåö»: Î(õ,y) ↔ P(x,y) & M(x)

«Ìàòü»: M(x,y) ↔ P(x,y) & W(x)

Äàëåå ïðèíèìàþòñÿ òðè àêñèîìû

1. Íè îäèí ÷åëîâåê íå ÿâëÿåòñÿ ðîäèòåëåì ñàìîãî ñåáÿ

∀x¬P(x,x)

2. Êàæäûé ÷åëîâåê èìååò åäèíñòâåííîãî îòöà

∀y∃!xO(x,y)

3. Êàæäûé ÷åëîâåê èìååò åäèíñòâåííóþ ìàòü

∀y∃!xM(x,y)

Â §6 ïðåäûäóùåé ãëàâû îïðåäåëåíèå êâàíòîðà ∃! äàâàëîñü ñ

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

ïðåäèêàòîâ ñ ðàâåíñòâîì K

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

êî ÷òî-òî ðàçðåøàòü, íî è ÷òî-òî çàïðåùàòü. È ÷åì áîëüøå òåî-

ðèÿ çàïðåùàåò, òåì îíà ëó÷øå. Íàøà æå òåîðèÿ ðàçðåøàåò êîå-

÷òî ëèøíåå.

243

Â ñàìîì äåëå, îíà íå èñêëþ÷àåò ñèòóàöèé, èçîáðàæåííîé â

íèæíåé ÷àñòè ðèñóíêà: Ð(à,b), Ð(b,ñ), íî îäíîâðåìåííî Ð(b,à) è

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

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

áàáóøêè! ß ïðåäâèæó âîçðàæåíèå àâòîðîâ êíèãè: ñóùåñòâîâà-

íèå ñèòóàöèè Ð(à,b) & Ð(b,ñ) & Ð(b,a) & Ð(ñ,à) íåëüçÿ äîêàçàòü.

Íî îíà íå çàïðåùåíà. Åñëè áû îíà áûëà äîêàçóåìà, òåîðèÿ áûëà

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

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

áåííîñòè ðîäñòâåííûõ îòíîøåíèé ëþäåé. Îíà íå ëîæíà, à íå-

äîñòàòî÷íî ñëîæíà. Íåìíîãî ïîäïðàâèì òåîðèþ. Âìåñòî íåî-

ïðåäåëÿåìîãî ÿâíî ïîíÿòèÿ «ðîäèòåëü» – Ð(õ,ó) ââåäåì ïîíÿòèå

«ïðåäîê» – Ï(õ,ó) è äîáàâèì ñëåäóþùèå àêñèîìû.

4. Íèêòî íå ÿâëÿåòñÿ ïðåäêîì ñàìîãî ñåáÿ

∀x¬Ï(x,x)

5. Ïðåäîê ìîåãî ïðåäêà ÿâëÿåòñÿ è ìîèì ïðåäêîì

∀x∀y∀z(Ï(õ,z) & Ï(z,y) → Ï(õ,y))

(Êàê âèäèì, îòíîøåíèå Ï(õ, ó) ÿâëÿåòñÿ îòíîøåíèåì ñòðî-

ãîãî ÷àñòè÷íîãî ïîðÿäêà.)

Òåïåðü îòíîøåíèå «ðîäèòåëü» ìîæíî îïðåäåëèòü â òåðìè-

íàõ îòíîøåíèÿ «ïðåäîê»

Ð(õ,ó) ↔ Ï(õ,ó) & ¬∃z(Ï(õ,z) & Ï(z,y))

Èíûìè ñëîâàìè, ðîäèòåëü – ýòî íåïîñðåäñòâåííûé ïðåäîê.

Òåïåðü ñèòóàöèÿ Ð(à,b) & Ð(b,ñ) & Ð(b,a) & Ð(ñ,à) çàïðåùåíà.

Äåéñòâèòåëüíî, äîïóñòèì, ÷òî Ð(à,b) & Ð(b,a). Ïî òîëüêî ÷òî

ïðèíÿòîìó îïðåäåëåíèþ, âñÿêèé ðîäèòåëü îäíîâðåìåííî ÿâëÿ-

åòñÿ ïðåäêîì ñâîåãî ïîòîìêà. Ïîýòîìó èç Ð(à,b) & Ð(b,a) íåìåä-

ëåííî ñëåäóåò, ÷òî Ï(à,b) & Ï(b,a). Â ñèëó 5 àêñèîìû, èìååì

Ï(à,b) & Ï(b,a) → Ï(à,à). Ïî ïðàâèëó →ó ïîëó÷àåì Ï(à,à), ÷òî

ïðîòèâîðå÷èò àêñèîìå 4. Ñëåäîâàòåëüíî, íàøå äîïóùåíèå ïðè-

âåëî ê ïðîòèâîðå÷èþ, çíà÷èò, îíî íå âåðíî. Òàêîé ñèòóàöèè

áûòü íå ìîæåò.

244

Äîïóñòèì òåïåðü Ð(à,b) & Ð(b,ñ) & Ð(ñ,à). Âíîâü èç Ð(à,b) &

Ð(b,ñ) & Ð(ñ,à) ñëåäóåò Ï(à,b) & Ï(b,ñ) & Ï(ñ,à). Çíà÷èò, Ï(à,b) &

Ï(b,ñ) è Ï(ñ,à). Ïî 5 àêñèîìå, Ï(à,b) & Ï(b,ñ) → Ï(à,c). Ïî →ó

èìååì Ï(à,ñ). Ïîñêîëüêó åñòü Ï(à,ñ) è Ï(ñ,à), èìååì òàêæåÏ(à,ñ)

& Ï(ñ,à). Âíîâü èñïîëüçóÿ àêñèîìó 5, ïîëó÷àåì Ï(à,ñ) & Ï(ñ,à) →

Ï(à,à). Ïî →ó ïîëó÷àåì Ï(à,à), ÷òî ïðîòèâîðå÷èò àêñèîìå 4.

Êñòàòè ãîâîðÿ, àêñèîìà 1 òåïåðü ëèøíÿÿ, ò.ê. îíà âûâîäèò-

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

Çíà÷èò, Ï(à,à), ÷òî ïðîòèâîðå÷èò àêñèîìå 4. Îòñþäà ∀x¬P(x,x),

÷òî è òðåáîâàëîñü.

Îñòàâëÿÿ â ñòîðîíå èñïîëüçîâàííûå ëîãè÷åñêèå ïîíÿòèÿ,

îáðàòèìñÿ ê äåñêðèïòèâíîìó ñëîâàðþ. Îí ñîäåðæèò îïðåäåëåí-

íûå àêñèîìàòè÷åñêè (ò.å. íåÿâíî) ïîíÿòèÿ «ïðåäîê» è «ìóæ÷è-

íà», à òàêæå ÿâíî îïðåäåëåííûå ÷åðåç íèõ ïîíÿòèÿ «ðîäèòåëü»,

«æåíùèíà», «îòåö» è «ìàòü». Ýìïèðè÷åñêèå ýòî ïîíÿòèÿ èëè

òåîðåòè÷åñêèå? Òåîðåòè÷åñêèå. Òåîðèÿ íè÷åãî íå ãîâîðèò î òîì,

êàêèå êîíêðåòíûå èíäèâèäû ñóùåñòâóþò, êòî èõ ðîäèòåëè è êòî

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

ñòóëèðóåìàÿ òåîðèåé, áåñêîíå÷íà! Â ñàìîì äåëå, àêñèîìû ãàðàí-

òèðóþò ñóùåñòâîâàíèå äëÿ êàæäîãî èíäèâèäà ðîâíî äâóõ ðîäè-

òåëåé (ìóæ÷èíó è æåíùèíó). Íî êàæäûé èç ðîäèòåëåé èìååò ïî

äâà ñâîèõ ðîäèòåëÿ è òàê äàëåå, ad infinitum. Ïîëó÷àåòñÿ, ÷òî

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

çûâàåòñÿ áåñêîíå÷íûì. Áåñêîíå÷íîñòü æå íå íàáëþäàåìà! Çíà-

÷èò, âñå ýòè ïîíÿòèÿ òåîðåòè÷åñêèå.

Îäíàêî â ðåàëüíîñòè ñóùåñòâóåò òîëüêî êîíå÷íîå ÷èñëî

èíäèâèäîâ. Îçíà÷àåò ëè ýòî, ÷òî íàøà òåîðèÿ îêàçàëàñü íå òîëü-

êî íåóäà÷íîé, íî è ëîæíîé? Íè òî, íè äðóãîå. Ïðè ïîñòðîåíèè

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

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

âàëèñü îò êîëè÷åñòâåííûõ ñâîéñòâ îòíîøåíèÿ ðîäñòâà è ñîñðå-

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

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

ïîìîùè òâîð÷åñêîãî âîîáðàæåíèÿ! Ñóäèòå òåïåðü ñàìè, ìîæíî

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

òîâ ÷óâñòâåííîãî îïûòà, êàê ïîëàãàëè ñåíñóàëèñòû. Çàìåòèì,

÷òî áåñêîíå÷íîñòü âîçíèêëà â íàøèõ ïîñòðîåíèÿõ ñîâåðøåííî

åñòåñòâåííûì îáðàçîì. Óâåðÿþ âàñ, ÷òî ïîïûòêà èçáàâèòüñÿ îò

íåå ðåçêî óñëîæíèëà áû íàøó òåîðèþ (âîò îäíà èç ïðîáëåì:

êîëè÷åñòâî èíäèâèäîâ êîíå÷íî, íî òî÷íîå èõ ÷èñëî íåîïðåäå-

ë¸ííî – êàê áûòü?; åùå ïðîáëåìà: åñëè ÷èñëî ëþäåé êîíå÷íî,

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

íî). Ñîìíåâàþùèìñÿ ïðåäëàãàþ ïîïðîáîâàòü îïèñàòü îòíîøå-

íèå ðîäñòâà áåç ââåäåíèÿ àáñòðàêöèè áåñêîíå÷íîñòè! Âûâîä:

àáñòðàêòíûå òåîðåòè÷åñêèå ïîíÿòèÿ îáëåã÷àþò íàì ïîñòèæåíèå

ðåàëüíîñòè.

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

ñòè ýìïèðè÷åñêèå ïîíÿòèÿ è ñîîòíåñòè èõ ñ òåîðåòè÷åñêèìè

ïîñðåäñòâîì ïðàâèë ñîîòâåòñòâèÿ. Ñäåëàòü ýòî ìîæíî ïðèáëè-

çèòåëüíî ñëåäóþùèì îáðàçîì. Ñíà÷àëà, èñïîëüçóÿ þðèäè÷åñêèå

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

â îòíîøåíèè ðîäñòâà, ÿâëÿþòñÿ ìóæ÷èíàìè èëè æåíùèíàìè.

Íà ýòîì ïóòè ìîæíî ïîëó÷èòü, íàïðèìåð, ýìïèðè÷åñêîå ïîíÿòèå

«ïðåäîê

»: õ ÿâëÿåòñÿ ïðåäêîì ó, åñëè è òîëüêî åñëè ïðåäúÿâëå-

íû òàêèå-òî è òàêèå-òî äîêóìåíòû (íåêîòîðûå óâåðÿþò, ÷òî èõ

ïðåäêè – ëþäè áëàãîðîäíîãî ïðîèñõîæäåíèÿ – ïðåäîñòàâüòå

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

Çàòåì ìîæíî ââåñòè ïðàâèëî ñîîòâåòñòâèÿ ∀x∀y(Ï

(õ,ó) →

Ï(õ,ó)). Ïîñëå ýòîãî âñå, ÷òî èçâåñòíî òåîðåòè÷åñêîãî î ïðåä-

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

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

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

ãî ïðèìåðà. Íî â áîëåå ñëîæíûõ ñëó÷àÿõ áåç òåîðèè íå îáîéòèñü.

Íàó÷íà ëè ýòà òåîðèÿ? Äà, ïîñêîëüêó åå â ïðèíöèïå ìîæíî

îïðîâåðãíóòü. Íàïðèìåð, îñóùåñòâëåíèå êëîíèðîâàíèÿ ñ èñïîëü-

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

÷òî êàæäûé ÷åëîâåê èìååò îòöà. Èñòèííà ëè ýòà òåîðèÿ? Ïî

êðàéíåé ìåðå, â îòíîøåíèè èñòîðè÷åñêîãî ïðîøëîãî îíà íå

âûçûâàåò ñîìíåíèé. Âåäü äî ñèõ ïîð íå áûëî íè îäíîãî îïðî-

âåðãàþùåãî å¸ ôàêòà.

246

ÃËÀÂÀ 7. ÂÛ×ÈÑËÈÌÎÑÒÜ È ËÎÃÈÊÀ

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

òîä çàäàíèÿ òåîðèé. Îí ñîñòîÿë â ïðèíÿòèè ðÿäà óòâåðæäåíèé â

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

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

ñòâî âûñêàçûâàíèé, çàìêíóòîå îòíîñèòåëüíî âûâîäèìîñòè. Ñó-

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

äÿò íå èç âûñêàçûâàíèé, à èç íåêîòîðîãî ñòðîãî çàäàííîãî íàáîðà

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

ë¸ííûå îïåðàöèè. Ýòî òàê íàçûâàåìûé ãåíåòè÷åñêèé ìåòîä ïî-

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

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

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

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

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

§1. Íàòóðàëüíûé óíèâåðñóì è êîäèðîâàíèå

Ìíîæåñòâî íàòóðàëüíûõ (ò.å. ìíîæåñòâî öåëûõ ïîëîæèòåëü-

íûõ ÷èñåë, ê êîòîðîìó äîáàâëåíî ÷èñëî 0) îáîçíà÷èì ÷åðåç N.

Àðèôìåòè÷åñêèå îïåðàöèè ñ íàòóðàëüíûìè ÷èñëàìè åù¸ íàçû-

âàþò ôóíêöèÿìè. Âñåì èçâåñòíû çíàìåíèòûå ÷åòûðå îïåðàöèè

ñëîæåíèÿ, óìíîæåíèÿ, âû÷èòàíèÿ è äåëåíèÿ. Ñëîæåíèå, íàïðè-

ìåð, åñòü äâóõìåñòíàÿ ôóíêöèÿ, îáîçíà÷àåìàÿ ñèìâîëîì «+», êî-

òîðàÿ êàæäîé óïîðÿäî÷åííîé ïàðå íàòóðàëüíûõ ÷èñåë <õ, ó> ñîïî-

ñòàâëÿåò íàòóðàëüíîå ÷èñëî, ÿâëÿþùååñÿ ñóììîé õ è ó. Çàïèñûâàÿ

ôóíêöèþ â îáùåì âèäå, îáû÷íî çíàê ôóíêöèè ñòàâÿò âïåðåäè,

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

òàò ñëîæåíèÿ ÷èñåë õ è ó çàïèøåòñÿ â âèäå +(õ, ó). Â ïðèâû÷íîé

ôîðìå çàïèñè ýòî âûðàæåíèå ïåðåïèøåòñÿ â âèäå õ + ó. Çíàê ôóí-

êöèè ñòàâÿò âïåðåäè ïîòîìó, ÷òî ôóíêöèè ìîãóò áûòü çíàêàìè n-

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

óïîðÿäî÷åííîé n-êîé ÷èñåë: f(õ

, õ

, ..., õ

). Ïðèìåðîì îäíîìåñò-

íîé ôóíêöèè áóäåò ôóíêöèÿ ïðèáàâëåíèÿ åäèíèöû s, êîòîðàÿ êàæ-

äîìó íàòóðàëüíîìó ÷èñëó õ ñîïîñòàâëÿåò ÷èñëî s(x) =

x +1. Íå-

òðóäíî ïðèäóìàòü ïðèìåð áîëåå ÷åì äâóõìåñòíîé ôóíêöèè. Îïðå-

äåëèì ôóíêöèþ ×

ñëåäóþùèì îáðàçîì: ×

(õ, ó, z) =

õ × ó × z.

Òàêèì ïóò¸ì ïîëó÷èëè òð¸õ ìåñòíóþ ôóíêöèþ ×

. È ò.ä.

247

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

ïûâàåòñÿ íàòóðàëüíûìè ÷èñëàìè. Íî íåêîòîðûå îïåðàöèè âû-

âîäÿò íàñ çà ïðåäåëû óíèâåðñóìà N. Íàïðèìåð, ðåçóëüòàò âû÷è-

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

íàäëåæèò îáëàñòè íàòóðàëüíûõ ÷èñåë. Íàïðèìåð, (4 – 3) ∈ N,

íî (3 – 4) ∉ N. Â ýòîé ñâÿçè ðàçëè÷àþò ÷àñòè÷íûå è òîòàëüíûå

ôóíêöèè. Ôóíêöèÿ íàçûâàåòñÿ ÷àñòè÷íîé, åñëè ðåçóëüòàò å¸ ïðè-

ìåíåíèÿ â íåêîòîðûõ ñëó÷àÿõ (à, ìîæåò áûòü, è âî âñåõ ñëó÷àÿõ)

íå îïðåäåë¸í. Åñëè æå ôóíêöèÿ âñåãäà ïðèâîäèò ê îïðåäåë¸í-

íîìó ðåçóëüòàòó, òî òàêóþ ôóíêöèþ íàçîâ¸ì òîòàëüíîé. Â óíè-

âåðñóìå N ñëîæåíèå è óìíîæåíèå ÿâëÿþòñÿ òîòàëüíûìè ôóíê-

öèÿìè, à âû÷èòàíèå è äåëåíèå – ÷àñòè÷íûìè.

Âûáîð óíèâåðñóìà N â êà÷åñòâå èñõîäíîãî îáóñëîâëåí ìíî-

ãèìè ïðè÷èíàìè. Îäíà èç íèõ – ýòî íåîáû÷àéíîå áîãàòñòâî ýòîãî

(êàçàëîñü áû, ïðîñòîãî) óíèâåðñóìà, ïîçâîëÿþùåãî â ÷èñëîâîé

ôîðìå ïðåäñòàâëÿòü ñàìûå ðàçíîîáðàçíûå âåùè. Òàêîå ïðåäñòàâ-

ëåíèå îñóùåñòâëÿåòñÿ ïîñðåäñòâîì êîäèðîâàíèÿ. Ïóñòü äàí óíè-

âåðñóì U. Êîäèðîâàíèå U ñîñòîèò âî âçàèìíî îäíîçíà÷íîì ýô-

ôåêòèâíîì ñîïîñòàâëåíèè êàæäîìó îáúåêòó u ∈ U íàòóðàëüíîãî

÷èñëà n ∈ N. Ýôôåêòèâíîñòü îçíà÷àåò, ÷òî äîëæíû áûòü âûïîë-

íåíû äâà óñëîâèÿ. Âî-ïåðâûõ, ïî ïðåäúÿâëåíèþ u äîëæíî îäíî-

çíà÷íî âû÷èñëÿòüñÿ n. Âî-âòîðûõ, ïî ëþáîìó n îäíîçíà÷íî îï-

ðåäåëÿåòñÿ, ÿâëÿåòñÿ ëè n îáîçíà÷åíèåì êàêîãî-ëèáî u, è åñëè

ÿâëÿåòñÿ, òî ýòî u äîëæíî áûòü ïðåäúÿâëåíî.

Ïîíÿòü, ÷òî òàêîå êîäèðîâàíèå, ïðîùå íà êîíêðåòíîì ïðè-

ìåðå. Ïóñòü U – ìíîæåñòâî âñåõ ôîðìóë ëîãèêè âûñêàçûâàíèé.

Îñóùåñòâèì êîäèðîâàíèå óíèâåðñóìà U. Äåëàòü ýòî ìîæíî ðàç-

íûìè ñïîñîáàìè. Ìû âûáåðåì ñëåäóþùèé. Ñîïîñòàâèì êàæäîìó

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

¬ – 1

&– 11

∨ – 111

→ – 1111

↔ – 11111

( – 111111

) – 1111111

p – 11111111

q – 111111111

r – 1111111111

s – 11111111111

– 111111111111

– 1111111111111

248

Êàæäûé áåç òðóäà ïðîäîëæèò íóìåðàöèþ ïðîïîçèöèîíàëü-

íûõ ïåðåìåííûõ. Ïðîèçâîëüíàÿ ïðîïîçèöèîíàëüíàÿ ïåðåìåí-

íàÿ ð

ïîëó÷èò íîìåð, ñîñòàâëåííûé èç n åäèíèö è åù¸ îäèí-

íàäöàòè åäèíèö. Îòìåòèì, ÷òî ýòî ýôôåêòèâíàÿ íóìåðàöèÿ,

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

çíà÷íî ñîïîñòàâèòü íîìåð, íî è ìîæåì ïî ïðîèçâîëüíîìó ÷èñëó

n îïðåäåëèòü, áóäåò ëè n íîìåðîì êàêîãî-ëèáî ñèìâîëà àëôàâè-

òà: áóäåò, åñëè öèôðà n ñîñòîèò èç îäíèõ åäèíèö, è íå áóäåò,

åñëè öèôðà n ñîäåðæèò îòëè÷íûå îò åäèíèöû öèôðû.

Êàæäàÿ ôîðìóëà À ëîãèêè âûñêàçûâàíèé ñîñòàâëåíà èç ñèì-

âîëîâ àëôàâèòà à

, à

, ..., à

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

íûå ÷èñëà m

, m

, ..., m

. Ýôôåêòèâíî ñîïîñòàâèì ôîðìóëå À

÷èñëî ñëåäóþùèì îáðàçîì: m

0 ... 0m

. Èíûìè ñëîâàìè, çà-

ïèøåì ÷èñëî, êîòîðîå ïîëó÷àåòñÿ, åñëè âûïèñûâàòü ïîäðÿä ñëåâà

íàïðàâî íîìåðà ñèìâîëîâ ôîðìóëû À, ðàçäåëÿÿ èõ öèôðîé 0.

Âû÷èñëèì, íàïðèìåð, íîìåð ôîðìóëû (¬ð ∨ ð

). Îíà ñî-

ñòàâëåíà èç ñèìâîëîâ ñ íîìåðàìè 111111, 1, 11111111, 111,

1111111111111, 1111111. Çíà÷èò,

(¬ð ∨ ð

) – 1111110101111111101110111111111111101111111.

Ïî ïðîèçâîëüíîìó ÷èñëó n ìîæíî ýôôåêòèâíî îïðåäåëèòü,

áóäåò ëè n êîäèðîâàòü íåêîòîðóþ ôîðìóëó ëîãèêè âûñêàçûâà-

íèé. ßñíî, íàïðèìåð, ÷òî ÷èñëî 11120444 íè÷åãî íå êîäèðóåò,

ïîòîìó ÷òî â åãî çàïèñè èñïîëüçîâàíû öèôðû 2 è 4, îòëè÷íûå

îò 1 è 0. Êîäèðóåò ëè ôîðìóëó ÷èñëî 11111101011111111? Ïðî-

âåðèì. Ïåðâûå øåñòü åäèíèö êîäèðóþò ëåâóþ ñêîáêó (, îäíà

åäèíèöà ¬, ïîñëåäíèå âîñåìü åäèíèö ð. Ïîëó÷èëè âûðàæåíèå

(¬ð, íå ÿâëÿþùååñÿ ôîðìóëîé. Ðàññìîòðèì ÷èñëî 10111111111.

Åãî ïåðåâîäîì áóäåò âûðàæåíèå ¬q, ÿâëÿþùååñÿ ôîðìóëîé.

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

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

÷åì äëÿ ëîãèêè âûñêàçûâàíèé). Íî êîäèðóþòñÿ íå òîëüêî ìíî-

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

ôîðìóë. Íàïðèìåð, â ñëó÷àå ëîãèêè âûñêàçûâàíèé êàæäîé ïîñ-

ëåäîâàòåëüíîñòè ôîðìóë âèäà À

, À

, ..., À

ñîïîñòàâèì ÷èñëî ñëå-

äóþùèì ñïîñîáîì. Ñíà÷àëà âû÷èñëèì êîäû ôîðìóë À

, À

, ..., À

Ïîëó÷èì ïîñëåäîâàòåëüíîñòü ÷èñåë m

, m

, ..., m

. Òåïåðü ñîåäè-

íèì ýòè ÷èñëà ïîñðåäñòâîì äâóõ íóëåé ïîäðÿä: m

00m

00 ... 00m

ßñíî, ÷òî îïèñàííîå ñîïîñòàâëåíèå áóäåò ýôôåêòèâíûì.

Ýôôåêòèâíîå ñîïîñòàâëåíèå îáúåêòó ÷èñëà – ýòî êîäèðîâà-

íèå, à îáðàòíûé ïðîöåññ ïåðåõîäà îò ÷èñëà ê îáúåêòó – ýòî äåêî-

äèðîâàíèå. Íå êàæäûé óíèâåðñóì U ìîæíî êîäèðîâàòü, îäíàêî

249

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

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

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

èç U âû÷èñëåíèÿìè íà íàòóðàëüíûõ ÷èñëàõ. Ýòî ïîçâîëÿåò ñâî-

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

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

öèþ, â äåéñòâèòåëüíîñòè êîäèðóþò ýòó èíôîðìàöèþ, ïåðåâîäÿ

å¸ â ÷èñëîâóþ ôîðìó, ïðîèçâîäÿò ñîîòâåòñòâóþùèå âû÷èñëå-

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

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

øèðîêîì ñìûñëå, ñâÿçàííîì ñ ëþáûì ýôôåêòèâíûì ïåðåâîäîì

èíôîðìàöèè èç îäíîé ôîðìû â äðóãóþ. Êîäèðîâàíèåì è äåêî-

äèðîâàíèåì èíôîðìàöèè çàíèìàþòñÿ ñïåöñëóæáû, æåëàþùèå

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

ôîííûì êàíàëàì òðåáóåò êîäèðîâàíèÿ è äåêîäèðîâàíèÿ. Òåëå-

âèçèîííûå êàðòèíêè êîäèðóþòñÿ è ïåðåäàþòñÿ â ýôèð ñ òåì,

÷òîáû áûòü äåêîäèðîâàííûìè â òåëåâèçîðàõ. È ò.ä.

§2. Ëîãè÷åñêèé êîìïüþòåð

Ðàññìîòðåííûå àðèôìåòè÷åñêèå ôóíêöèè îïðåäåëÿþòñÿ

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

ïðàâèë íå òðåáóåò èçîáðåòàòåëüíîñòè è ìóê òâîð÷åñòâà. Âñå, ÷òî

òðåáóåòñÿ – ýòî íåóêîñíèòåëüíîå ñëåäîâàíèå èíñòðóêöèÿì. Â òà-

êèõ ñëó÷àÿõ ãîâîðÿò, ÷òî çàäàí àëãîðèòì âû÷èñëåíèÿ ôóíêöèè

èëè ÷òî ôóíêöèÿ ÿâëÿåòñÿ âû÷èñëèìîé.

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

÷åñêîå ïðåäïèñàíèå èëè àëãîðèòì. Ïîïðîáóéòå, îïèðàÿñü íà èí-

òóèöèþ, îòâåòèòü, áóäåò ëè âû÷èñëèìîé ñëåäóþùàÿ ôóíêöèÿ g(n).

Íî ïðåæäå ïðåäïîëîæèì, ÷òî êàæäîé ôîðìóëå èñ÷èñëåíèÿ

ïðåäèêàòîâ ýôôåêòèâíî ñîïîñòàâëåíî íàòóðàëüíîå ÷èñëî òàêèì

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

ïî ëþáîìó íàòóðàëüíîìó ÷èñëó ìîæíî óçíàòü, êîäèðóåò ëè îíî

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

{ 1, åñëè n ÿâëÿåòñÿ íîìåðîì ôîðìóëû è ýòà ôîðìóëà

{ ÿâëÿåòñÿ òåîðåìîé èñ÷èñëåíèÿ ïðåäèêàòîâ;

{

{ 0 â ïðîòèâíîì ñëó÷àå.

g(n) =

250

Èòàê, âû÷èñëèìà ëè ôóíêöèÿ g? Óñòàíîâëåíî, ÷òî ñóùå-

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

íîãî ïåðåáîðà âñåõ òåîðåì èñ÷èñëåíèÿ ïðåäèêàòîâ. Ïðèìåì ýòî

óòâåðæäåíèå íà âåðó. Òåïåðü íàïðàøèâàåòñÿ ñëåäóþùàÿ ïðîöå-

äóðà âû÷èñëåíèÿ g.

Ïðè çàäàííîì n îïðåäåëèì, ÿâëÿåòñÿ ëè n íîìåðîì ôîðìóëû

èñ÷èñëåíèÿ ïðåäèêàòîâ. Åñëè íå ÿâëÿåòñÿ, òî g(n) = 0 è âû÷èñëå-

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

ìóëó À. Ïðèìåíèì ìåõàíèçì ïîðîæäåíèÿ òåîðåì èñ÷èñëåíèÿ

ïðåäèêàòîâ. Åñëè ñðåäè òåîðåì âñòðåòèòñÿ ôîðìóëà À, òî g(n) = 1

è âû÷èñëåíèÿ çàâåðøåíû; åñëè æå ôîðìóëà À íå âñòðåòèòñÿ ñðå-

äè òåîðåì èñ÷èñëåíèÿ ïðåäèêàòîâ, ïîëîæèì g(n) = 0.

Íåäîñòàòêîì ýòîé ïðîöåäóðû ÿâëÿåòñÿ òî îáñòîÿòåëüñòâî,

÷òî åñëè äëÿ íåêîòîðîé ôîðìóëû À ñ íîìåðîì n íå ñóùåñòâóåò

äîêàçàòåëüñòâà â èñ÷èñëåíèè ïðåäèêàòîâ, òî â ïðîöåññå ïåðåáî-

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

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

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

âû÷èñëèòü. Ïîñêîëüêó òåîðåòè÷åñêè äîêàçàíî, ÷òî íåò ýôôåê-

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

ôîðìóëû îïðåäåëèòü, áóäåò ëè îíà òåîðåìîé èñ÷èñëåíèÿ ïðåäè-

êàòîâ, îñòàåòñÿ ëèøü íàäåÿòüñÿ, ÷òî èññëåäóåìàÿ ôîðìóëà â êîíöå

êîíöîâ ïîÿâèòñÿ â ïðîöåññå ïåðåáîðà. Îäíàêî, åñëè îíà íå òåî-

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

ñìîæåì çàêîí÷èòü âû÷èñëåíèÿ è çàïèñàòü g(n) = 0. Ñëåäóåò ëè

èç ýòîãî, ÷òî íå ñóùåñòâóåò àëãîðèòìà âû÷èñëåíèÿ ôóíêöèè g,

ò.å. ÷òî îíà íå ÿâëÿåòñÿ âû÷èñëèìîé ôóíêöèåé?

Èòàê, ïîíÿòèå âû÷èñëèìîé ôóíêöèè íóæäàåòñÿ â óòî÷íå-

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

ëèòåëüíîãî óñòðîéñòâà èëè êîìïüþòåðà. Îò ðåàëüíûõ ÝÂÌ äàí-

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

ìåðû îáðàáàòûâàåìûõ ÷èñåë è îáúåìû ïàìÿòè äëÿ íåãî ñíÿòû.

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

áî îòëè÷àòüñÿ îò îáû÷íûõ êîìïüþòåðíûõ ïðîãðàìì. Â ÷àñòíî-

ñòè, âñå ïðîãðàììû áóäóò êîíå÷íûìè.

Èäåàëüíûé êîìïüþòåð, ñ êîòîðûì íàì ïðåäñòîèò ðàáîòàòü,

íàçûâàåòñÿ ìàøèíîé ñ íåîãðàíè÷åííûìè ðåãèñòðàìè (ÌÍÐ);

åãî òàêæå íàçûâàþò àäðåñíîé ìàøèíîé (RAM). ÌÍÐ ñîäåðæèò

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

÷åðåç R1, R2, R3..., Rn, ... . Êàæäûé èç ðåãèñòðîâ Ri â ëþáîé

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