Анисов А.М. Современная логика
Подождите немного. Документ загружается.
111
ôîðìóëà â äàííîé ñòðîêå? Ïðÿìîå âû÷èñëåíèå ïîêàçûâàåò, ÷òî
îíà áóäåò â ýòîé ñòðîêå èñòèííîé. Íî íàì è òðåáîâàëîñü, ÷òîáû
íåèçâåñòíàÿ ôîðìóëà À â äàííîé ñòðîêå áûëà èñòèííîé. Ïî÷å-
ìó ïîñòðîåííàÿ ôîðìóëà èñòèííà? – Ïîòîìó, ÷òî îíà àäåêâàòíî
îïèñûâàåò ñòðîêó. Ïåðåìåííàÿ ð
1
â íåé ëîæíà, íî ìû è ãîâîðèì
«¬ð
1
» (ò.å. «íåâåðíî, ÷òî ð
1
»), ïåðåìåííàÿ ð
2
âíîâü ëîæíà, íî ìû
è ãîâîðèì «¬ð
2
», ïåðåìåííàÿ ð
3
îêàçàëàñü èñòèííîé, íî ìû è
óòâåðæäàåì «ð
3
» è ò.ä. Ïðè ýòîì âñå ïåðå÷èñëåííûå ñëó÷àè ïðè-
íèìàþòñÿ ñîâìåñòíî, ÷òî ïåðåäà¸òñÿ êîíúþíêöèåé «¬ð
1
», è «¬ð
2
»,
è «ð
3
» è ò.ä. Ïîñêîëüêó êîíúþíêöèÿ åñòü â îáúåêòíîì ÿçûêå, ìû
ýòèì ïîëüçóåìñÿ, ïîëó÷àÿ â ðåçóëüòàòå èñêîìîå îïèñàíèå (¬ð
1
&
¬ð
2
& ð
3
& ð
4
& ¬ð
5
& ð
6
) äàííîé ñòðîêè íà ÿçûêå-îáúåêòå.
Àíàëîãè÷íûì îáðàçîì ïîñòðîèì êîíúþíêöèè äëÿ âñåõ ñòðîê,
â êîòîðûõ À èñòèííà. Ïî ïîñòðîåíèþ, êàæäàÿ òàêàÿ êîíúþíê-
öèÿ áóäåò èñòèííîé â ñîîòâåòñòâóþùåé ñòðîêå òàáëèöû. Äîïóñ-
òèì, ÷èñëî ñòðîê, â êîòîðûõ À èñòèííà, ðàâíî m ≥ 1. Çíà÷èò,
ïîëó÷èòñÿ m êîíúþíêöèé âèäà (#ð
1
& #ð
2
& ... & #ð
n
). Ïðîíó-
ìåðóåì ýòè êîíúþíêöèè. Äàëåå íàäî ñêàçàòü «Ôîðìóëà À, êîòî-
ðóþ ìû èùåì, èñòèííà â (#ð
1
& #ð
2
& ... & #ð
n
)
1
, è â (#ð
1
& #ð
2
& ... & #ð
n
)
2
, …, è â (#ð
1
& #ð
2
& ... & #ð
n
)
m
ñòðîêàõ». Íà ñàìîì
äåëå À ìû óæå ïî÷òè íàøëè. Ïåðå÷èñëåííûå êîíúþíêöèè èñ-
÷åðïûâàþò âñå ñëó÷àè, â êîòîðûõ À èñòèííà. Çíà÷èò, âìåñòî «À
èñòèííà» íàäî ïðîñòî ñêàçàòü «À», èñïîëüçóÿ äàííûå êîíúþíê-
öèè. Ñîåäèíèì âñå ýòè êîíúþíêöèè ñâÿçêîé ∨. Â ðåçóëüòàòå
ïîëó÷èì ôîðìóëó ñëåäóþùåãî âèäà.
(#ð
1
& #ð
2
& ... & #ð
n
)
1
∨ (#ð
1
& #ð
2
& ... & #ð
n
)
2
∨ … ∨ (#ð
1
& #ð
2
& ... & #ð
n
)
m
.
 ÷¸ì å¸ ñìûñë? –  òîì, ÷òî À èñòèííà èëè â ñòðîêå (#ð
1
&
#ð
2
& ... & #ð
n
)
1
, èëè â ñòðîêå (#ð
1
& #ð
2
& ... & #ð
n
)
2
, ..., èëè â
ñòðîêå (#ð
1
& #ð
2
& ... & #ð
n
)
m
. Ìîæåò ïîêàçàòüñÿ, ÷òî âìåñòî
«èëè» íàäî èñïîëüçîâàòü «è»: À èñòèííà è â ñòðîêå x, è â ñòðîêå y,
è â ñòðîêå z è ò.ä. Ýòî îçíà÷àëî áû, ÷òî âñå m ñòðîê ðåàëèçîâàëèñü
êàê áû îäíîâðåìåííî. Íà ñàìîì äåëå ñòðîêè òàáëèöû ïðåäñòàâ-
ëÿþò îòäåëüíûå àëüòåðíàòèâíûå âîçìîæíîñòè, ñìåøèâàòü êîòî-
ðûå, âîîáùå ãîâîðÿ, íåëüçÿ. Âîçüì¸ì, íàïðèìåð, òàáëèöó äëÿ èñ-
êëþ÷àþùåé äèçúþíêöèè (p ∇ q).  íåé äâå ñòðîêè, â êîòîðûõ
ôîðìóëà (p ∇ q) èñòèííà. Îïèøåì ýòè ñòðîêè: (p & ¬q), (¬p & q).
 äàííîì ñëó÷àå àëüòåðíàòèâû íåñîâìåñòèìû. Åñëè ìû ïðèìå-
íèì êîíúþíêöèþ äëÿ ñîåäèíåíèÿ îïèñàíèé ñòðîê, òî ïîëó÷èì
ïðîòèâîðå÷èâóþ ôîðìóëó ((p & ¬q) & (¬p & q)). Åñëè æå ïðèìå-
íèì äèçúþíêöèþ, òî ïîëó÷èì ôîðìóëó ((p & ¬q) ∨ (¬p & q)),
112
êîòîðàÿ íå òîëüêî íå ïðîòèâîðå÷èâà, íî è èìååò òó æå ñàìóþ òàá-
ëèöó èñòèííîñòè, ÷òî è ôîðìóëà (p ∇ q), ò.å. ýòè ôîðìóëó ýêâèâà-
ëåíòíû. Âåäü ôîðìóëà (p ∇ q) èñòèííà ëèáî â ñëó÷àå èñòèííîñòè ð
è ëîæíîñòè q, ëèáî â ñëó÷àå ëîæíîñòè ð è èñòèííîñòè q. Íî ôîð-
ìóëà ((p & ¬q) ∨ (¬p & q)) óòâåðæäàåò ðîâíî ýòî, íå èñïîëüçóÿ
îòñóòñòâóþùèå â îáúåêòíîì ÿçûêå ñëîâà «èñòèíà» è «ëîæü»!
Ïîïðîáóåì îïèñàòü òàáëèöû äëÿ îñòàâøèõñÿ ñâÿçîê. Òàáëèöó
äëÿ íå èñêëþ÷àþùåé äèçúþíêöèè (ð ∨ q) âûðàçèò ôîðìóëà (p &
q) ∨ (p & ¬q) ∨ (¬p & q), îïèñûâàþùàÿ òðè ñòðîêè, â êîòîðûõ
äèçúþíêöèÿ èñòèííà. Êîíúþíêöèÿ (p & q) èñòèííà òîëüêî â îä-
íîé ñòðîêå, îïèñàíèå êîòîðîé ñîâïàäàåò ñ ïåðâîíà÷àëüíîé ôîð-
ìóëîé (p & q). Èìïëèêàöèÿ (p → q) èìååò â òàáëèöå òðè ñòðîêè
ñî çíà÷åíèåì «èñòèíà», ïîýòîìó îïèñàíèå å¸ òàáëèöû äîëæíî
áûòü ïðåäñòàâëåíî ôîðìóëîé (p & q) ∨ (¬p & q) ∨ (¬p & ¬q). Äëÿ
ýêâèâàëåíöèè (p ↔ q) â ñîîòâåòñòâèè ñ å¸ òàáëèöåé èìååì (p & q)
∨ (¬p & ¬q). Íàêîíåö, òàáëèöà äëÿ îòðèöàíèÿ ¬ð, èìåþùàÿ òîëü-
êî îäíó ñòðîêó ñ ðåçóëüòèðóþùèì çíà÷åíèåì «èñòèíà», îïèñûâà-
åòñÿ, êàê è â ñëó÷àå ñ êîíúþíêöèåé, ñàìîé ôîðìóëîé ¬ð.
Ïîëó÷åííûé ðåçóëüòàò íå ñëó÷àåí. Äëÿ îïèñàíèÿ òàáëèöû,
ñîäåðæàùåé îäíî èëè áîëåå ðåçóëüòèðóþùåå çíà÷åíèå «èñòèíà»,
äîñòàòî÷íî çàïèñàòü ôîðìóëó (#ð
1
& #ð
2
& ... & #ð
n
)
1
∨ (#ð
1
& #ð
2
& ... & #ð
n
)
2
∨ … ∨ (#ð
1
& #ð
2
& ... & #ð
n
)
m
. Íè÷åãî áîëüøå (êàê è
â ïðèìåðàõ ñ òàáëèöàìè äëÿ èñõîäíûõ ñâÿçîê) äåëàòü íå íóæíî.
Ýòà ôîðìóëà è áóäåò èñêîìîé ôîðìóëîé À, êîòîðóþ ìû èñêàëè.
Äåéñòâèòåëüíî, åñëè À èñòèííà â íåêîòîðîé ñòðîêå n, òî ýòà
ñòðîêà îïèñûâàåòñÿ íåêîòîðîé ïîäôîðìóëîé (#ð
1
& #ð
2
& ... &
#ð
n
)
i
, êîòîðàÿ, êàê ìû óæå âèäåëè, áóäåò èñòèííà â ñòðîêå n. Íî
èñòèííîñòü äèçúþíêòèâíîãî ÷ëåíà (#ð
1
& #ð
2
& ... & #ð
n
)
i
ïðè-
âåä¸ò ê èñòèííîñòè âñåé äèçúþíêöèè (#ð
1
& #ð
2
& ... & #ð
n
)
1
∨
(#ð
1
& #ð
2
& ... & #ð
n
)
2
∨ … ∨ (#ð
1
& #ð
2
& ... & #ð
n
)
m
â òîé æå
ñòðîêå n, ÷òî è òðåáîâàëîñü.
Åñëè æå â ñòðîêå n À ëîæíà, òî è êàæäûé äèçúþíêòèâíûé
÷ëåí (#ð
1
& #ð
2
& ... & #ð
n
)
i
ïðè 1 ≤ i ≤ m áóäåò ëîæíûì, ÷òî
ïðèâåä¸ò ê ëîæíîñòè âñåé äèçúþíêöèè (#ð
1
& #ð
2
& ... & #ð
n
)
1
∨
(#ð
1
& #ð
2
& ... & #ð
n
)
2
∨ … ∨ (#ð
1
& #ð
2
& ... & #ð
n
)
m
â òîé æå
ñòðîêå n, ÷òî è òðåáîâàëîñü. Ïî÷åìó êàæäàÿ ïîäôîðìóëà (#ð
1
&
#ð
2
& ... & #ð
n
)
i
áóäåò ëîæíîé â ñòðîêå n ? – Ïîòîìó, ÷òî ýòè
ïîäôîðìóëû îïèñûâàëè òîëüêî ñòðîêè ñ ðåçóëüòèðóþùèì çíà-
÷åíèåì «èñòèíà». Íî â ñòðîêå n ðåçóëüòèðóþùèì çíà÷åíèåì, ïî
ïðåäïîëîæåíèþ, ÿâëÿåòñÿ «ëîæü». Ïóñòü ïîäôîðìóëà (#ð
1
& #ð
2
& ... & #ð
n
)
i
îïèñûâàåò ñòðîêó íîìåð k. Â ñòðîêå k ðåçóëüòèðóþ-
ùèì çíà÷åíèåì ÿâëÿåòñÿ «èñòèíà». Íî n îòëè÷àåòñÿ îò k õîòÿ áû
îäíèì ïðèïèñûâàíèåì çíà÷åíèÿ íåêîòîðîé ïåðåìåííîé p
j
.
113
Äîïóñòèì, ÷òî p
j
èñòèíà â n è ëîæíà â k. Òîãäà ïîäôîðìóëà
(#ð
1
& #ð
2
& ... & #ð
n
)
i
ïðèîáðåòàåò âèä (#ð
1
& #ð
2
& ... & ¬p
j
&
... & #ð
n
)
i
. Îòñþäà â ñòðîêå n ôîðìóëà ¬p
j
ïðèìåò çíà÷åíèå «ëîæü»,
÷òî ñäåëàåò ëîæíîé âñþ ïîäôîðìóëó (#ð
1
& #ð
2
& ... & ¬p
j
& ...
& #ð
n
)
i
â ñòðîêå n.
Äîïóñòèì òåïåðü, ÷òî p
j
ëîæíà â n è èñòèííà â k. Òîãäà
ïîäôîðìóëà (#ð
1
& #ð
2
& ... & #ð
n
)
i
ïðèîáðåòàåò âèä (#ð
1
& #ð
2
&
... & p
j
& ... & #ð
n
)
i
. Îòñþäà â ñòðîêå n ôîðìóëà p
j
ïðèìåò çíà÷å-
íèå «ëîæü», ÷òî ñäåëàåò ëîæíîé âñþ ïîäôîðìóëó (#ð
1
& #ð
2
& ...
& p
j
& ... & #ð
n
)
i
â ñòðîêå n.
Òàêèì îáðàçîì, äèçúþíêòèâíûé ÷ëåí (#ð
1
& #ð
2
& ... & #ð
n
)
i
áóäåò ëîæíûì âî âñÿêîé ñòðîêå n, â êîòîðîé ðåçóëüòèðóþùèì
çíà÷åíèåì ÿâëÿåòñÿ «ëîæü».
Òå æå ñàìûå ðàññóæäåíèÿ âåðíû äëÿ ëþáîãî äèçúþíêòèâíî-
ãî ÷ëåíà. Çíà÷èò, â ëþáîé ñòðîêå n, â êîòîðîé ðåçóëüòèðóþùèì
çíà÷åíèåì ÿâëÿåòñÿ «ëîæü», âñÿ äèçúþíêöèÿ (#ð
1
& #ð
2
& ... &
#ð
n
)
1
∨ (#ð
1
& #ð
2
& ... & #ð
n
)
2
∨ … ∨ (#ð
1
& #ð
2
& ... & #ð
n
)
m
òàêæå ïðèìåò çíà÷åíèå «ëîæü».
 ðåçóëüòàòå ïîëó÷èëîñü, ÷òî ôîðìóëà âèäà (#ð
1
& #ð
2
& ...
& #ð
n
)
1
∨ (#ð
1
& #ð
2
& ... & #ð
n
)
2
∨ … ∨ (#ð
1
& #ð
2
& ... & #ð
n
)
m
àäåêâàòíî îïèñûâàåò âñÿêóþ òàáëèöó, ñîäåðæàùóþ îäíî èëè
áîëåå ðåçóëüòèðóþùèõ çíà÷åíèé «èñòèíà». Òåì ñàìûì äîêàçàíà
òåîðåìà î ïîëíîòå ñèñòåìû ñâÿçîê ÊÄÎ. Ýòèõ òð¸õ ñâÿçîê äîñòà-
òî÷íî, ÷òîáû ïîñòðîèòü ôîðìóëó, ñîîòâåòñòâóþùóþ ëþáîé íà-
ïåð¸ä çàäàííîé òàáëèöå èñòèííîñòè (íàïîìíèì, ÷òî òàáëèöû,
ðåçóëüòèðóþùèå ñòîëáöû êîòîðûõ ñîäåðæàò òîëüêî ëîæü, òàêæå
îïèñûâàþòñÿ â ÿçûêå ÊÄÎ, êàê áûëî ïîêàçàíî âûøå).
Ïðèìåíèì íà ïðàêòèêå ïîëó÷åííûé ðåçóëüòàò. Ïóñòü äàíà
ñëåäóþùàÿ òàáëèöà èñòèííîñòè.
pq r A
èè è ë
èè ë è
èë è ë
èë ë è
ëèè ë
ëèë è
ëë è ë
ëë ë è
114
Êàêóþ ôîðìóëó â ÿçûêå ÊÄÎ íàäî ïîäñòàâèòü âìåñòî À?
Äàäèì ôîðìóëüíîå îïèñàíèå ñòðîê ñ ðåçóëüòèðóþùèì çíà÷åíè-
åì «èñòèíà» è ñîåäèíèì èõ äèçúþíêöèåé: (p & q & ¬r) ∨ (p & ¬q
& ¬r) ∨ (¬p & q & ¬r) ∨ (¬p & ¬q & ¬r). Ïðîâåðüòå, ÷òî ïîëó÷åí-
íàÿ ôîðìóëà äåéñòâèòåëüíî ñîîòâåòñòâóåò äàííîé òàáëèöå.
Ðàññìîòðèì åù¸ îäíó òàáëèöó èñòèííîñòè.
 íåé â ðåçóëüòèðóþùåì ñòîëáöå ñòîèò øåñòü çíà÷åíèé «èñ-
òèíà» è òîëüêî äâà çíà÷åíèÿ «ëîæü». Íåëüçÿ ëè âìåñòî äëèííîãî
îïèñàíèÿ øåñòè èñòèííûõ àëüòåðíàòèâ äàòü áîëåå êîðîòêîå îïè-
ñàíèå äâóõ ëîæíûõ ñòðîê?
Îêàçûâàåòñÿ, îïèñûâàòü ìîæíî íå òîëüêî èñòèííûå, íî è
ëîæíûå ñòðîêè. Òîëüêî äëÿ ýòîãî (èñêëþ÷èòåëüíî â èíòåðåñàõ
ëîãè÷åñêîãî äåëà) ïðèä¸òñÿ ëãàòü!  ïåðâîé ëîæíîé ñòðîêå ð
èñòèííî, q ëîæíî è r èñòèííî. Ïî ïðàâäå íàäî áûëî áû ñêàçàòü
«ð», «¬q» è «r». Íî ìû ñêàæåì «¬ð», «q» è «¬r». Äàëåå, ïðàâäè-
âûå óòâåðæäåíèÿ î ïåðåìåííûõ ñîåäèíÿëà êîíúþíêöèÿ, íî ìû
èñïîëüçóåì äèçúþíêöèþ (¬ð ∨ q ∨ ¬r). Äåéñòâóÿ òåì æå ñïîñî-
áîì, äëÿ âòîðîé ëîæíîé ñòðîêè ïîëó÷èì (p ∨ ¬q ∨ r). Íàêîíåö,
åñëè ðàíüøå îïèñàíèÿ ñòðîê îòäåëÿëà äðóã îò äðóãà äèçúþíê-
öèÿ, òî òåïåðü ìû ýòîìó âîïðåêè èñïîëüçóåì êîíúþíêöèþ.
 èòîãå ïîëó÷èòñÿ ôîðìóëà (¬ð ∨ q ∨ ¬r) & (p ∨ ¬q ∨ r), â êîòî-
ðîé âñ¸ ñêàçàíî øèâîðîò íàâûâîðîò. Çàòî ýòà ôîðìóëà ëîæíà â
òðåòüåé è øåñòîé ñòðîêàõ, à â îñòàëüíûõ ñòðîêàõ èñòèííà, ÷òî è
äà¸ò æåëàííîå áîëåå êîðîòêîå îïèñàíèå èñõîäíîé òàáëèöû.
Òåîðåìà î ïîëíîòå ñèñòåìû ÊÄÎ äàåò ìîùíûé èíñòðóìåíò
àíàëèçà ëîãè÷åñêèõ ñâîéñòâ ðàññóæäåíèé â ëîãèêå âûñêàçûâà-
íèé, ïîçâîëÿþùèé âûõîäèòü çà ðàìêè î÷åâèäíîãî. Ïðèìåíåíèå
ýòîãî èíñòðóìåíòà îáû÷íî îñóùåñòâëÿåòñÿ ñëåäóþùèì îáðàçîì.
pq r A
èè èè
èè ë è
èë èë
èë ë è
ëèèè
ëèë ë
ëë èè
ëë ëè
115
Ïîêàçûâàþò, ÷òî â íåêîòîðîé ñèñòåìå ëîãè÷åñêèõ ñâÿçîê {#
1
, #
2
,
..., #
n
} ìîæíî îïðåäåëèòü ñâÿçêè ÊÄÎ. Èíà÷å ãîâîðÿ, íàäî ïî-
êàçàòü, ÷òî ñâÿçêè ÊÄÎ âûðàçèìû â íîâîé ñèñòåìå. Òåì ñàìûì
íîâàÿ ñèñòåìà òàêæå îêàçûâàåòñÿ ïîëíîé: â íåé ìîæíî ïðîâî-
äèòü âñå ïîñòðîåíèÿ, ÷òî è â ñèñòåìå ÊÄÎ. Äàëüíåéøåå èçëîæå-
íèå ñäåëàåò ïîíÿòíûì ñêàçàííîå.
Ñèñòåìà ñâÿçîê {→, ¬} ÿâëÿåòñÿ ïîëíîé. Äëÿ äîêàçàòåëüñòâà
ýòîãî ôàêòà äîñòàòî÷íî ïîêàçàòü, ÷òî â ýòîé ñèñòåìå îïðåäåëè-
ìû ñâÿçêè &, ∨ è ¬. ×òî êàñàåòñÿ ñâÿçêè ¬, òî îíà óæå èìååòñÿ
â ñèñòåìå. Îñòàëîñü îïðåäåëèòü & è ∨ ÷åðåç → è ¬.
(À & Â) ↔ ¬(À → ¬Â)
(À ∨ Â) ↔ (¬À → Â)
Ïðîâåðüòå, âåðíû ëè äâå ïðèâåäåííûå ýêâèâàëåíòíîñòè.
 ëîãèêå äåéñòâóåò ïðèíöèï çàìåíû ýêâèâàëåíòíûõ, êîòîðûé
àíàëîãè÷åí ïðèíöèïó çàìåíû ðàâíîãî ðàâíûì â àðèôìåòèêå.
Ñîãëàñíî ýòîìó ïðèíöèïó, ëþáóþ ôîðìóëó èëè ïîäôîðìóëó
ìîæíî çàìåíèòü íà åé ýêâèâàëåíòíóþ. Â ðåçóëüòàòå òàêîé çàìå-
íû òàáëèöû èñòèííîñòè íå èçìåíÿòñÿ. Ïóñòü, ê ïðèìåðó, â ÿçû-
êå ÊÄÎ äàíà ôîðìóëà (p ∨ q) ∨ ¬(¬p & ¬q). Ïåðåâåä¸ì å¸ íà
ÿçûê {→, ¬}, èñïîëüçóÿ çàìåíû ýêâèâàëåíòíûõ. Ïåðâàÿ ãëàâíàÿ
ïîäôîðìóëà ÿâëÿåòñÿ äèçúþíêöèåé (p ∨ q). Ÿ ïåðåâîäîì áóäåò
ôîðìóëà (¬p → q). Êîíúþíêöèþ (¬p & ¬q) çàìåíèì íà ¬(¬ð →
¬¬q).  èñõîäíîé ôîðìóëå êîíúþíêöèÿ îòðèöàëàñü, ïîýòîìó
âòîðàÿ ãëàâíàÿ ïîäôîðìóëà ¬(¬p & ¬q) ïåðåâîäèòñÿ êàê ôîðìó-
ëà ¬¬(¬ð →
¬¬q). Ïîëó÷èì ôîðìóëó (¬p → q) ∨ ¬¬(¬ð → ¬¬q).
 íåé âñ¸ åù¸ âñòðå÷àåòñÿ äèçúþíêöèÿ, êîòîðóþ òîæå íàäî ýê-
âèâàëåíòíî óñòðàíèòü. Â ðåçóëüòàòå èìååì ôîðìóëó ¬(¬p → q)
→ ¬¬(¬ð → ¬¬q) ÿçûêà {→, ¬}. Ýòà ôîðìóëà ýêâèâàëåíòíà ïåð-
âîíà÷àëüíîé ôîðìóëå (p ∨ q) ∨ ¬(¬p & ¬q), ÷òî ïðîâåðÿåòñÿ
òàáëè÷íûìè âû÷èñëåíèÿìè.
Åù¸ îäèí ïðèìåð çàìåíû êîíúþíêöèè íà ýêâèâàëåíòíóþ
ôîðìóëó, ñîäåðæàùóþ òîëüêî → è ¬. Ïóñòü äàíà êîíúþíêöèÿ
(À &  & Ñ & D). ×òîáû ëåã÷å áûëî åå ïðåîáðàçîâûâàòü, ðàññòà-
âèì â íåé ñêîáêè (êàê ìû çíàåì, äåëàòü ýòî ìîæíî ïðîèçâîëü-
íûì îáðàçîì). Âîçüìåì, ñêàæåì, ((À & Â) & (Ñ & D)). Çàìåíèì
(À & Â) íà ýêâèâàëåíòíóþ ôîðìóëó ¬(À → ¬Â), à ôîðìóëó (Ñ &
D) – íà ýêâèâàëåíòíóþ ôîðìóëó ¬(Ñ → ¬D). Ïîëó÷èì (¬(À →
¬Â) & ¬(Ñ → ¬D)). Óñòðàíèì òåïåðü îñòàâøóþñÿ êîíúþíêöèþ:
¬(¬(À → ¬Â) → ¬¬(Ñ → ¬D)). Ïîñëåäíÿÿ ôîðìóëà ýêâèâàëåíò-
íà èñõîäíîé êîíúþíêöèè, â ÷åì íåòðóäíî óáåäèòüñÿ.
116
Àíàëîãè÷íûå öåïî÷êè ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé ìîæíî
ïðîâîäèòü ñ äèçúþíêöèÿìè. Ãëàâíîå, ÷òî ïðè ýòîì ïîëó÷àþòñÿ
ôîðìóëû, ýêâèâàëåíòíûå èñõîäíûì. Ýêâèâàëåíöèÿ ↔ èãðàåò â
ëîãèêå ïðèìåðíî òó æå ðîëü, ÷òî è çíàê ðàâåíñòâà = â àðèôìå-
òèêå. Êàê è â àðèôìåòèêå, ãäå øèðîêî ïðèìåíÿþòñÿ ïåðåõîäû
îò ðàâåíñòâà ê ðàâåíñòâó, â ëîãèêå ÷àñòî ïðèõîäèòñÿ ïåðåõîäèòü
îò îäíèõ ôîðìóë ê äðóãèì, ýêâèâàëåíòíûì èñõîäíûì.
Íàïðèìåð, ôîðìóëà ¬(¬(À → ¬Â) → ¬¬(Ñ → ¬D)) ÿâëÿåòñÿ
ýêâèâàëåíòíîé ôîðìóëå ¬(¬(À → ¬Â) → (Ñ → ¬D)), ïîñêîëüêó
äâîéíîå îòðèöàíèå ðàâíîçíà÷íî îòñóòñòâèþ îòðèöàíèÿ. Ò.ê.
ïåðâàÿ ôîðìóëà ýêâèâàëåíòíà êîíúþíêöèè (À & Â & Ñ & D),
âòîðàÿ ôîðìóëà òîæå áóäåò ýêâèâàëåíòíà ýòîé æå êîíúþíêöèè.
 ýòîì ðàññóæäåíèè òîæå áûë èñïîëüçîâàí ïðèíöèï çàìåíû
ýêâèâàëåíòíûõ âûñêàçûâàíèé.
Ïðèíöèï çàìåíû ýêâèâàëåíòíûõ äåéñòâèòåëüíî àíàëîãè÷åí
àðèôìåòè÷åñêîìó ïðèíöèïó çàìåíû ðàâíîãî ðàâíûì. Íàïðè-
ìåð, ïðè âû÷èñëåíèè àðèôìåòè÷åñêîãî âûðàæåíèÿ ((2 + 4) : 3)
âìåñòî (2 + 4) ìîæíî ïîäñòàâèòü ÷èñëî 6, ïîñêîëüêó (2 + 4) = 6.
Òî÷íî òàê æå â ëîãèêå, åñëè äàíà íåêîòîðàÿ ôîðìóëà F, ñîäåð-
æàùàÿ ïîäôîðìóëó À, è ïðè ýòîì À ↔ Â, òî ïðè çàìåíå À íà Â
ïîëó÷èì âûñêàçûâàíèå F' òàêîå, ÷òî F ↔ F'.
Ðàçóìååòñÿ, ïðè òàêîé çàìåíå íàäî ñîáëþäàòü íåêîòîðûå î÷å-
âèäíûå îãðàíè÷åíèÿ. Íàïðèìåð, â àðèôìåòè÷åñêîé ôîðìóëå ((2
+ 4) : 3) íåëüçÿ çàìåíÿòü ÷àñòü "2 +". Çàìåíÿåìàÿ ÷àñòü äîëæíà
áûòü îñìûñëåííûì àðèôìåòè÷åñêèì âûðàæåíèåì. Àíàëîãè÷íûì
îáðàçîì, â ëîãèêå íåëüçÿ, íàïðèìåð, çàìåíÿòü ÷àñòü âèäà "À →"
èëè "& Â)" íà êàêóþ-ëèáî äðóãóþ. Îïÿòü-òàêè, çàìåíÿåìîå âûðà-
æåíèå äîëæíî áûòü ëîãè÷åñêè îñìûñëåííûì. Ýòî îçíà÷àåò, ÷òî
òàêîå âûðàæåíèå äîëæíî áûòü ôîðìóëîé, êîòîðóþ ìîæíî èñ-
ïîëüçîâàòü ñàìîñòîÿòåëüíî (à íå òîëüêî êàê ñîñòàâíóþ ÷àñòü äðó-
ãèõ âûñêàçûâàíèé). Âûðàæåíèÿ òèïà "À → Â)", "(À & Â)) ∨ ¬" è
ò.ä. ìîãóò âõîäèòü â ïðàâèëüíî ïîñòðîåííûå âûñêàçûâàíèÿ â êà-
÷åñòâå ÷àñòåé, íî ñàìè ôîðìóëàìè íå ÿâëÿþòñÿ è ïîòîìó íå ñïî-
ñîáíû ñóùåñòâîâàòü â êà÷åñòâå îñìûñëåííûõ âûðàæåíèé.
Ñôîðìóëèðóåì ïðèíöèï çàìåíû ýêâèâàëåíòíûõ ñòðîæå.
Åñëè À ÿâëÿåòñÿ ïîäôîðìóëîé ôîðìóëû F è À
↔
Â, òî ïðè çàìåíå
êàæäîãî âõîæäåíèÿ À â F íà  ïîëó÷èòñÿ ôîðìóëà F' òàêàÿ, ÷òî
F
↔
F'. Åñëè À ñîâïàäàåò ñ F è À
↔
Â, òî òîãäà F' ïðîñòî
ñîâïàäåò ñ Â. Ïðèìåðû çàìåíû ýêâèâàëåíòíûõ ïðèâîäèëèñü
âûøå, è íàì åùå íå ðàç ïðèä¸òñÿ ñòîëêíóòüñÿ ñ ïðèìåíåíèåì
äàííîãî ïðèíöèïà.
117
Èòàê, ìû äîêàçàëè ïîëíîòó ñèñòåìû ñâÿçîê {→, ¬} è ïðîäå-
ìîíñòðèðîâàëè ìåòîä çàìåíû ýêâèâàëåíòíûõ âûñêàçûâàíèé.
Ïîëíîòà óïîìÿíóòîé ñèñòåìû îçíà÷àåò, ÷òî ìû ìîæåì îãðàíè-
÷èòüñÿ òîëüêî èñïîëüçîâàíèåì ñâÿçîê → è ¬ â ðàññóæäåíèÿõ
ëîãèêè âûñêàçûâàíèé. Êàê ìû âèäåëè, òó æå ñàìóþ ôóíêöèþ
ìîæåò âûïîëíÿòü ñèñòåìà ÊÄÎ. Êàêóþ æå ñèñòåìó âûáðàòü?
Ìîæíî âçÿòü ëþáóþ, íî áîëåå ïðàêòè÷íî îáúåäèíèòü íàçâàí-
íûå ñèñòåìû ñâÿçîê. Ðàçóìååòñÿ, ïðè ýòîì ñíîâà ïîëó÷èòñÿ ïîë-
íàÿ ñèñòåìà.  ñëó÷àå íåîáõîäèìîñòè ìîæíî è äàëüøå ïîïîë-
íÿòü ýòó ñîâîêóïíîñòü ñâÿçîê (äîáàâèâ ê íåé, íàïðèìåð, ýêâè-
âàëåíöèþ ↔ è èñêëþ÷àþùóþ äèçúþíêöèþ ∇. Âàæíî òî, ÷òî
ðàñøèðåíèå ïîëíîé ñèñòåìû ñâÿçîê âíîâü ïðèâîäèò ê ïîëíîé
ñèñòåìå.
 ñèñòåìå ÊÄÎ {&, ∨, ¬} òðè ñâÿçêè, â ñèñòåìå {→, ¬} äâå.
Ìîæíî ëè óìåíüøèòü ÷èñëî ñâÿçîê â ÊÄÎ, íå óòðàòèâ ïðè ýòîì
ñâîéñòâà ïîëíîòû? Îêàçûâàåòñÿ, ÷òî ïîëíûìè ÿâëÿþòñÿ ñëåäó-
þùèå äâå ïîäñèñòåìû ÊÄÎ: {&, ¬} è {∨, ¬}. Íå òîëüêî èìïëèêà-
öèÿ →, íî è êîíúþíêöèÿ & è äèçúþíêöèÿ ∨ â êîìáèíàöèè ñ
îòðèöàíèåì ¬ äàþò ïîëíûå ñèñòåìû ñâÿçîê.
×òîáû óáåäèòüñÿ â ñêàçàííîì, ïðîâåðüòå èñòèííîñòü äâóõ
ñëåäóþùèõ ýêâèâàëåíòíîñòåé.
(À & Â) ↔ ¬(¬À ∨ ¬Â)
(À ∨ Â) ↔ ¬(¬À & ¬Â)
Èç ïîëíîòû ñèñòåì {&, ¬} è {∨, ¬} ñëåäóåò, ÷òî íå òîëüêî
ñâÿçêè & è ∨ îïðåäåëèìû ÷åðåç → è ¬ (ñîîòâåòñòâóþùèå ýêâè-
âàëåíòíîñòè áûëè ïðèâåäåíû âûøå), íî è èìïëèêàöèÿ → äîëæ-
íà áûòü îïðåäåëèìîé â êàæäîé èç ýòèõ ñèñòåì. Äåéñòâèòåëüíî,
ñëåäóþùèå ýêâèâàëåíòíîñòè ïîêàçûâàþò, ÷òî ýòî òàê.
(À → Â) ↔ (¬À ∨ Â)
(À → Â) ↔ ¬
(À &
¬Â)
Ïðèìåíÿÿ ïðèíöèï çàìåíû ýêâèâàëåíòíûõ, ìû ìîæåì òå-
ïåðü èçáàâèòüñÿ îò èñïîëüçîâàíèÿ ëþáûõ äâóõ ñâÿçîê èç ñîâî-
êóïíîñòè {&, ∨, →}, îñòàâèâ òîëüêî êàêóþ-ëèáî îäíó èç íèõ
âìåñòå ñ îòðèöàíèåì ¬. Íî, êàê òîëüêî ÷òî áûëî îòìå÷åíî, óäîá-
íåå ïîëüçîâàòüñÿ âñåìè øèðîêî ïðèìåíÿåìûìè â ðàññóæäåíèÿõ
ëîãè÷åñêèìè ñâÿçêàìè.  ÷åì æå òîãäà ïðàêòè÷åñêîå çíà÷åíèå
ïîëó÷åííûõ ðåçóëüòàòîâ? Ðàññìîòðåííûå ýêâèâàëåíòíîñòè óñ-
òàíàâëèâàþò âçàèìíûå çàâèñèìîñòè ìåæäó ðàçëè÷íûìè ëîãè-
÷åñêèìè ñâÿçêàìè, ïîçâîëÿÿ ÿñíåå è ãëóáæå ïîíÿòü èõ ðîëü â
ðàññóæäåíèÿõ.
118
 ÷àñòíîñòè, ëåâûå ÷àñòè ïðèâåäåííûõ ýêâèâàëåíòíîñòåé íå
ñîäåðæàò çíàêà "¬" è èìåþò áîëåå ïðîñòîé âèä. Âñòðåòèâøèñü
ïðè àíàëèçå ðàññóæäåíèé ñ âûñêàçûâàíèÿìè èç ïðàâûõ ÷àñòåé
ýòèõ ýêâèâàëåíòíîñòåé, ìîæíî äàííûå ðàññóæäåíèÿ óïðîñòèòü,
çàìåíèâ â ñîîòâåòñòâèè ñ ïðèíöèïîì çàìåíû ýêâèâàëåíòíûõ
ïðàâûå ÷àñòè íà ëåâûå.
Íàïðèìåð, ãðîìîçäêîå âûñêàçûâàíèå ¬(¬¬(À & ¬Â) ∨ ¬¬(Â
& ¬À)), ñìûñë êîòîðîãî ñ ïåðâîãî âçãëÿäà ïðåäñòàâëÿåòñÿ çàãà-
äî÷íûì, ïîñëå òð¸õ íåñëîæíûõ ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé
ïðèîáðåòàåò ïðîñòîé è ïîíÿòíûé âèä.
(1) ¬(¬¬(À & ¬Â) ∨ ¬¬( & ¬À)) ↔ ¬(¬(A → Â) ∨ ¬( → À))
(Ýêâèâàëåíòíàÿ çàìåíà ¬(À & ¬Â) è ¬( & ¬À) íà (À → Â)
è (Â → À) ñîîòâåòñòâåííî.)
(2) ¬(¬(À → Â) ∨ ¬(Â → À)) ↔ ((À → Â) & (Â → À))
(Ýêâèâàëåíòíàÿ çàìåíà âûñêàçûâàíèÿ âèäà ¬(¬Õ ∨ ¬Y) íà
(Õ & Y), ãäå âìåñòî Õ ñòîèò ôîðìóëà (À → Â), à âìåñòî Y –
ôîðìóëà (Â → À).)
(3) ((À → Â) & (Â → À)) ↔ (À ↔ Â)
(Ýêâèâàëåíòíîñòü è åñòü èìïëèêàöèÿ â îáå ñòîðîíû.)
Ò.ê. ýêâèâàëåíöèÿ òðàíçèòèâíà, ò.å. åñëè (Õ ↔ Y) è (Y ↔ Z),
òî (Õ ↔ Z) (â ýòîì íåòðóäíî óáåäèòüñÿ, ïîñêîëüêó ýêâèâàëåíò-
íûå ôîðìóëû èìåþò îäèíàêîâûå ðåçóëüòèðóþùèå ñòîëáöû â
òàáëèöå èñòèííîñòè), ïðèìåíÿÿ óêàçàííûé ïåðåõîä äâàæäû,
ïðèõîäèì ê âûâîäó:
¬(¬¬(À & ¬Â) ∨ ¬¬( & ¬À)) ↔ (À ↔ Â).
Êàê âèäèì, ïåðâîíà÷àëüíîå ñëîæíîå âûñêàçûâàíèå ¬(¬¬(À
& ¬Â) ∨ ¬¬( & ¬À)) â äåéñòâèòåëüíîñòè èìååò î÷åíü ïðîñòîé
ñìûñë: îíî óòâåðæäàåò, ÷òî (À ↔ Â), ò.å., ÷òî âûñêàçûâàíèå À
ýêâèâàëåíòíî âûñêàçûâàíèþ Â.
Âíèìàòåëüíûé ÷èòàòåëü ìîã çàìåòèòü, ÷òî âî âñåõ ïðèâå-
äåííûõ ïîëíûõ ñèñòåìàõ ëîãè÷åñêèõ ñâÿçîê ôèãóðèðîâàëî îò-
ðèöàíèå. Ìîæåò áûòü, â ëþáîé ïîëíîé ñèñòåìå äîëæíî èìåòüñÿ
îòðèöàíèå ¬? Äàëåå, ïîñêîëüêó îäíî îòðèöàíèå ÿâíî íå îáðàçó-
åò ïîëíîé ñèñòåìû, âåðåí ëè âûâîä, ÷òî ïîëíàÿ ñèñòåìà ñîäåð-
æèò êàê ìèíèìóì äâå ëîãè÷åñêèå ñâÿçêè? Êàê ïîêàçûâàþò íè-
æåñëåäóþùèå ðàññóæäåíèÿ, íà îáà ýòè âîïðîñà íóæíî äàòü îò-
ðèöàòåëüíûé îòâåò.
Ðàññìîòðèì íîâóþ äâóõìåñòíóþ ëîãè÷åñêóþ ñâÿçêó ↓, êîòî-
ðàÿ íå èìååò àíàëîãà â åñòåñòâåííîì ÿçûêå, íî êîòîðóþ ìû, òåì
íå ìåíåå, ìîæåì îïðåäåëèòü òî÷íûì îáðàçîì, ïîñòðîèâ äëÿ íåå
òàáëèöó èñòèííîñòè.
119
Ñâÿçêà ↓ íàçûâàåòñÿ ñòðåëêîé Ïèðñà. Åù¸ ↓ íàçûâàþò àíòè-
êîíúþíêöèåé, ïîñêîëüêó å¸ ðåçóëüòèðóþùèé ñòîëáåö åñòü ïåðå-
â¸ðíóòûé ñòîëáåö äëÿ êîíúþíêöèè. Ïîñòðîèì ñëåäóþùóþ ñî-
âìåñòíóþ òàáëèöó äëÿ îòðèöàíèÿ è íîâîé ñâÿçêè.
Èç ýòîé òàáëèöû âèäíî, ÷òî âåðíà ýêâèâàëåíòíîñòü (¬À) ↔
(À ↓ À), ò.å îòðèöàíèå ¬ îïðåäåëèìî ÷åðåç ñâÿçêó ↓.
Ïîñòðîèì åùå îäíó ñîâìåñòíóþ òàáëèöû, íà ýòîò ðàç äëÿ
êîíúþíêöèè & è íîâîé ñâÿçêè ↓.
Êàê âèäèì, ðåçóëüòèðóþùèé ñòîëáåö äëÿ ôîðìóëû ((À ↓ À) ↓
(Â ↓ Â)) ñîâïàäàåò ñ ðåçóëüòèðóþùèì ñòîëáöîì ôîðìóëû (À & Â),
ò.å. èìååò ìåñòî ýêâèâàëåíòíîñòü (À & Â) ↔ ((À ↓ À) ↓ (Â ↓ Â)).
Äâå òîëüêî ÷òî ïîëó÷åííûå ýêâèâàëåíòíîñòè ïîêàçûâàþò,
÷òî ñâÿçêè ¬ è & îïðåäåëèìû ÷åðåç ñâÿçêó ↓. Ýòî îçíà÷àåò, ÷òî
ñèñòåìà {↓}, ñîäåðæàùàÿ îäíó-åäèíñòâåííóþ ñâÿçêó ↓, ÿâëÿåò-
ñÿ ïîëíîé!
Èìååòñÿ åùå îäíà ïîëíàÿ ñèñòåìà, ñîäåðæàùàÿ åäèíñòâåí-
íóþ ëîãè÷åñêóþ ñâÿçêó |, íàçûâàåìóþ øòðèõîì Øåôôåðà èëè
àíòèäèçúþíêöèåé. Êàê è ↓, ñâÿçêà | íå ïðåäñòàâëåíà â åñòåñòâåí-
íîì ÿçûêå. Åå ñâîéñòâà îïðåäåëÿþòñÿ ñëåäóþùåé òàáëèöåé èñ-
òèííîñòè.
ÀÂ(À↓ Â)
èè ë
èë ë
ëè ë
ëë è
À ¬À(À↓ À)
èë ë
ëè è
ÀÂ (À&Â) ((À↓ À) ↓ (Â ↓ Â))
èè è ë è ë
èë ë ë ë è
ëè ë è ë ë
ëë ë è ë è
120
Ïîëíîòà ñèñòåìû {|} âûòåêàåò èç ñëåäóþùèõ äâóõ ýêâèâà-
ëåíòíîñòåé.
¬À ↔ (À | À)
(À ∨ Â) ↔ ((À | À) | ((Â | Â))
(Ïðîâåðüòå èñòèííîñòü ýòèõ ýêâèâàëåíòíîñòåé ñàìîñòîÿòåëüíî.)
Ñòðåëêà Ïèðñà è øòðèõ Øåôôåðà ëèøíèé ðàç ñâèäåòåëü-
ñòâóþò î òîì, ÷òî ëîãèêà çàíèìàåòñÿ íå èçó÷åíèåì ýìïèðè÷åñ-
êèõ çàêîíîìåðíîñòåé ìûñëèòåëüíîé äåÿòåëüíîñòè, à óñòàíîâëå-
íèåì òåîðåòè÷åñêèõ çàêîíîâ âîçìîæíûõ ñïîñîáîâ ðàññóæäåíèé.
Âðÿä ëè êòî-ëèáî èç ëþäåé ñïîñîáåí ìûñëèòü, ôîðìóëèðóÿ âûñ-
êàçûâàíèÿ íà ÿçûêå àíòèêîíúþíêöèé èëè àíòèäèçúþíêöèé.
Îäíàêî äëÿ êîìïüþòåðîâ èëè èíûõ ìàøèí, îñóùåñòâëÿþùèõ
ëîãè÷åñêèå îïåðàöèè, ìîæåò áûòü, ïðîùå ðàññóæäàòü, èñïîëü-
çóÿ âñåãî îäíó ëîãè÷åñêóþ ñâÿçêó.
Ïîäâîäÿ èòîã, óêàæåì íà ïðåäîñòàâëÿåìûå ëîãèêîé øèðî-
êèå âîçìîæíîñòè âûáîðà ðàçëè÷íûõ ðàâíîñèëüíûõ ñïîñîáîâ
âûðàæåíèÿ ìûñëåé. Íåêîòîðûå èç ýòèõ ñïîñîáîâ âûãëÿäÿò äîñ-
òàòî÷íî ýêçîòè÷íî (âñïîìíèì î òîëüêî ÷òî ðàçîáðàííûõ îïåðà-
öèÿõ ↓ è | ), äðóãèå òåñíî ñâÿçàíû ñ ïðèâû÷íûìè ìåòîäàìè ôîð-
ìóëèðîâàíèÿ âûñêàçûâàíèé â åñòåñòâåííîì ÿçûêå. Íåçàâèñèìî
îò òîãî, êàêîé êîíêðåòíûé íàáîð ëîãè÷åñêèõ ñâÿçîê âçÿò çà îñ-
íîâó, îí äîëæåí îáåñïå÷èâàòü âîçìîæíîñòü âûðàçèòü ëþáîå
ìûñëèìîå âûñêàçûâàíèå, ò.å. äîëæåí áûòü ïîëíûì.
§7. Àëüòåðíàòèâíûå èíòåðïðåòàöèè ÿçûêà ëîãèêè âûñêàçûâàíèé
Âûøå óæå îòìå÷àëàñü àíàëîãèÿ, ñóùåñòâóþùàÿ ìåæäó íåêî-
òîðûìè ëîãè÷åñêèìè è àðèôìåòè÷åñêèìè çàêîíàìè. Ýòà àíàëî-
ãèÿ íàâîäèò íà ìûñëü îá èíîé ñåìàíòèêå äëÿ ÿçûêà ëîãèêè âûñ-
êàçûâàíèé. Íîâàÿ ñåìàíòèêà áóäåò àðèôìåòè÷åñêîé. Òî÷íåå,
áóäåò èñïîëüçîâàí ëèøü ôðàãìåíò àðèôìåòèêè. Èç âñåõ öåëûõ
÷èñåë îñòàâèì òîëüêî 0 è 1. ×èñëî 0 áóäåò àíàëîãîì ëæè, ÷èñëî
1 – àíàëîãîì èñòèíû. Òîãäà êîíúþíêöèÿ âåä¸ò ñåáÿ êàê óìíî-
æåíèå, ÷òî äåìîíñòðèðóåò ñëåäóþùàÿ òàáëèöà.
ÀÂ (À|Â)
èè ë
èë è
ëè è
ëë è