Логика высказываний

Московский государственный университет
имени М. В. Ломоносова
Факультет вычислительной математики 
и кибернетики

ЛОГИКА
ВЫСКАЗЫВАНИЙ

Учебное пособие

С. И. Гуров

Издательство Московского
университета
2015

УДК 510.63 
ББК 22.12   
          Г95

Печатается по решению редакционно-издательского совета 
факультета вычислительной математики и кибернетики
МГУ имени М. В. Ломоносова

Рд-р. физ.-мат. наук, профессор 
В. А. Захаров

ISBN 978-5-19-011105-7

© С. И. Гуров, 2015
© Факультет вычислительной математики 
и кибернетики МГУ имени М. В. Ломоносова, 2015
© Издательство Московского университета, 2015

Гуров С. И.
Логика высказываний: Учебное пособие. – М.: Издательство Мос ковского университета, 2015. – 268 с. – (Бакалавриат. Учебные пособия).

ISBN 978-5-19-011105-7

Предлагаемое учебное пособие предназначено для студентов, начинающих изучать математическую логику, оно также может быть использовано при самообразовании.
Подчёркиваются алгебраические аспекты исчислений высказываний 
классической и интуиционистской логик. Изложены методы характеризации формул логики высказываний, подробно рассмотрены гильбертовские исчисления, система натурального вывода и исчисление секвенций для исчисления высказываний. Для каждой из трёх систем рассматривается соответствующая мета теория. Рассматриваются семантические 
методы характеризации формул. 
Пособие содержит большое количество примеров, позволяющих читателю легко освоиться с вводимыми понятиями.

Г95

УДК 510.63 
ББК 22.12

Îãëàâëåíèå
3

Îãëàâëåíèå

1
Àëãåáðà ëîãèêè
6
1.1
Êëàññè÷åñêàÿ àëãåáðà âûñêàçûâàíèé C2 . .
6
1.1.1
Âûñêàçûâàíèÿ, ôîðìóëû è èíòåðïðåòàöèÿ
. . . . . . . . . . . . . . . . . .
6
1.1.2
Áóëåâà àëãåáðà. Îïåðàòîð çàìûêàíèÿ.
ßçûê ôóíêöèé è ÿçûê ôîðìóë . . . .
15
1.2
Áèíàðíûå îòíîøåíèÿ íà ìíîæåñòâå ôîðìóë
24
1.2.1
Òèïû ôîðìóë àëãåáðû ëîãèêè. Òàâòîëîãèè.
. . . . . . . . . . . . . . . .
24
1.2.2
Ëîãè÷åñêàÿ ýêâèâàëåíòíîñòü . . . . .
28
1.2.3
Ëîãè÷åñêîå ñëåäîâàíèå . . . . . . . .
34
1.3
Õàðàêòåðèçàöèÿ ôîðìóë C2
. . . . . . . . .
41
1.3.1
Ýëåìåíòàðíûå ìåòîäû õàðàêòåðèçàöèè 41
1.3.2
Ìåòîä ñåìàíòè÷åñêèõ òàáëèö . . . . .
45
1.3.3
Ìåòîä ðåçîëþöèè
. . . . . . . . . . .
52
1.4
Îá èíòóèöèîíèñòñêîé ëîãèêå I . . . . . . . .
61
1.4.1
Êðèçèñ îñíîâàíèé ìàòåìàòèêè è èíòóèöèîíèçì . . . . . . . . . . . . . . .
61
1.4.2
Òð¼õçíà÷íàÿ
èíòåðïðåòàöèÿ
ôðàãìåíòà èíòóèöèîíèñòñêîé ëîãèêè . . .
67

2
Èñ÷èñëåíèÿ âûñêàçûâàíèé
70
2.1
Ëîãè÷åñêèå èñ÷èñëåíèÿ . . . . . . . . . . . .
70
2.1.1
Ñèíòàêñè÷åñêîå çàäàíèå èñ÷èñëåíèé
71
2.1.2
Ñåìàíòèêà èñ÷èñëåíèÿ. Ìåòàÿçûê è
ìåòàòîðèÿ. Î òåîðèè äîêàçàòåëüñòâ .
75
2.2
Èñ÷èñëåíèå âûñêàçûâàíèé H
. . . . . . . .
80
2.2.1
Ñèíòàêñèñ è ñåìàíòèêà ÈÂ H
. . . .
80
2.2.2
Ñâîéñòâà âûâîäèìîñòè
. . . . . . . .
86
2.2.3
Òåîðåìà î äåäóêöèè . . . . . . . . . .
96

Îãëàâëåíèå

2.2.4
Äåäóêòèâíàÿ ýêâèâàëåíòíîñòü . . . .
103
2.3
Ìåòàòåîðèÿ ÈÂ H . . . . . . . . . . . . . . .
106
2.3.1
Êîððåêòíîñòü è íåïðîòèâîðå÷èâîñòü
106
2.3.2
Ñåìàíòè÷åñêàÿ ïîëíîòà . . . . . . . .
109
2.3.3
Ðàçëè÷íûå âèäû äåäóêòèâíîé ïîëíîòû è ðàçðåøèìîñòü
. . . . . . . . . .
119
2.3.4
Íåçàâèñèìîñòü ñèñòåìû àêñèîì
. . .
121
2.3.5
Ýëåìåíòàðíîå äîêàçàòåëüñòâî ñåìàíòè÷åñêîé ïîëíîòû È H
. . . . . . .
124
2.4
Èñ÷èñëåíèÿ âûñêàçûâàíèé H1 . . . . . . . .
127
2.4.1
Îïèñàíèå ÈÂ H1 . . . . . . . . . . . .
127
2.4.2
Ñâîéñòâà ÈÂ H1 . . . . . . . . . . . .
129
2.5
Òèïû êëàññè÷åñêèõ È è èõ ïðåäñòàâëåíèÿ
137
2.5.1
ÈÂ ãèëüáåðòîâñêîãî òèïà . . . . . . .
137
2.5.2
Âûâîäèìîñòü êàê îïåðàòîð çàìûêàíèÿ 146

3
Ñåêâåíöèàëüíûå èñ÷èñëåíèÿ
148
3.1
Èñ÷èñëåíèå N íàòóðàëüíîãî âûâîäà . . . . .
148
3.1.1
Îïðåäåëåíèå
èñ÷èñëåíèÿ
N
íàòóðàëüíîãî òèïà
. . . . . . . . . . . . .
149
3.1.2
Äîêàçàòåëüñòâî â âèäå äåðåâà. Íîâûå
äîïóñòèìûå ïðàâèëà â ÈC N . . . . .
160
3.1.3
Îñíîâíûå ñâîéñòâà ÈC N . . . . . . .
168
3.1.4
Ìåòàòåîðèÿ ÈC N . . . . . . . . . . .
173
3.1.5
Ïîèñê âûâîäà ôîðìóë â ÈC N . . . .
181
3.2
Èñ÷èñëåíèå ñåêâåíöèé S
. . . . . . . . . . .
195
3.2.1
Îïðåäåëåíèå ÈC S . . . . . . . . . . .
196
3.2.2
Ñâîéñòâà ÈC S. Ìåòàòåîðèÿ è ïîèñê
äîêàçàòåëüñòâ
. . . . . . . . . . . . .
202
3.2.3
Äîïóñòèìîñòü
ïðàâèëà
ñå÷åíèÿ
è
íåïðîòèâîðå÷èâîñòü ÈC S
. . . . . .
213

4
Èíòóèöèîíèñòñêèå ÈÂ è ÈÑ
218
4.1
Ñèíòàêñèñ èíòóèöèîíèñòñêîãî ÈÂ I . . . . .
218
4.1.1
Àêñèîìàòèêà è îñíîâíûå ñâîéñòâà . .
218
4.1.2
Ñèñòåìû NI è SI
. . . . . . . . . . .
223

Îãëàâëåíèå
5

4.2
Ñåìàíòèêà ÈÈÂ . . . . . . . . . . . . . . . .
227
4.2.1
Ëîãè÷åñêèå ìàòðèöû
. . . . . . . . .
227
4.2.2
Øêàëû Êðèïêå . . . . . . . . . . . . .
230

Ïåðñîíàëèÿ è àâòîðñêèé óêàçàòåëü
238

Ñïèñîê ëèòåðàòóðû
266

Ãëàâà 1. Àëãåáðà ëîãèêè

Ãëàâà 1

Àëãåáðà ëîãèêè

Ëîãèêà áûâàåò ðàçíîé. Îäèíàêîâûì áûâàåò òîëüêî å¼ îòñóòñòâèå.

Ñòàñ ßíêîâñêèé.

Ðàçëè÷àþò ôèëîñîôñêóþ ëîãèêó (íàóêó î íàèáîëåå
îáùèõ çàêîíàõ ÷åëîâå÷åñêîãî ìûøëåíèÿ) è å¼ ñîñòàâíóþ ÷àñòü  ôîðìàëüíóþ ëîãèêó, â êîòîðîé èññëåäóþòñÿ ñòðóêòóðà ðàññóæäåíèé è äîêàçàòåëüñòâ íà îñíîâå àíàëèçà èõ ôîðìû. Òåîðèÿ ïîçíàíèÿ îïðåäåëÿåò äâà ñïîñîáà
ïîëó÷åíèÿ íîâîãî çíàíèÿ: ïóò¼ì îïûòà è ïóò¼ì óìîçàêëþ÷åíèé. Çàêîíû ôîðìàëüíîé ëîãèêè ïðèçâàíû îáåñïå÷èòü
ïðàâèëüíûé âûâîä íîâîãî çíàíèÿ èç óæå èçâåñòíîãî, ò.å.
ïóò¼ì óìîçàêëþ÷åíèé. Äàííîå ó÷åáíîå ïîñîáèå íàõîäèòñÿ
â ðàìêàõ ôîðìàëüíîé ëîãèêè.

1.1
Êëàññè÷åñêàÿ àëãåáðà âûñêàçûâàíèé
C2

1.1.1
Âûñêàçûâàíèÿ, ôîðìóëû è èíòåðïðåòàöèÿ

Àëãåáðà ëîãèêè èçó÷àåò ñòðóêòóðó è ñâîéñòâà âûñêàçûâàíèé. Ïîä âûñêàçûâàíèåì ïîíèìàþò ïðåäëîæåíèå íà
åñòåñòâåííîì èëè èñêóññòâåííîì ÿçûêå, êîòîðîå ïðèíöèïèàëüíî (ïðè òî÷íîì îïðåäåëåíèè óñëîâèé ìåñòà, âðåìåíè,
íàëè÷èÿ òåõ èëè èíûõ îáñòîÿòåëüñòâ è ò. ä.) ìîæíî êàê-òî
îöåíèòü ñ òî÷êè çðåíèÿ åãî èñòèííîñòè. Òàêèìè îöåíêàìè
ìîãóò áûòü: ¾èñòèííî¿, ¾ëîæíî¿, ¾âåðîÿòíî¿ (áîëåå èëè
ìåíåå), ¾îáÿçàòåëüíî¿, ¾íåîáõîäèìî¿, ¾âîçìîæíî¿ (â òîé

1.1. Êëàññè÷åñêàÿ àëãåáðà âûñêàçûâàíèé C2
7

èëè èíîé ñòåïåíè), ¾íåâîçìîæíî¿ è ò. ä. Äàëåå â àëãåáðå
ëîãèêè îòâëåêàþòñÿ îò âñåõ ïðî÷èõ õàðàêòåðèñòèê âûñêàçûâàíèÿ, â òîì ÷èñëå è îò åãî ñìûñëà (!), è ðàññìàòðèâàþò
òîëüêî åãî èñòèííîñòíóþ îöåíêó. Â ñâÿçè ñ ýòèì çàìåòèì,
÷òî ëþáàÿ ôîðìàëèçàöèÿ ïðåíåáðåãàåò òåìè èëè èíûìè
ñòîðîíàìè ñîäåðæàíèÿ â ïîëüçó ôîðìû1.
Â
êëàññè÷åñêîé
àëãåáðå
ëîãèêè
âûñêàçûâàíèå

ýòî óòâåðäèòåëüíîå èëè îòðèöàòåëüíîå ïîâåñòâîâàòåëüíîå
ïðåäëîæåíèå, ïðî êîòîðîå ìîæíî ñêàçàòü, èñòèííî îíî èëè
ëîæíî. Òàêèì îáðàçîì, êîëè÷åñòâî èñòèííîñòíûõ çíà÷åíèé âûñêàçûâàíèÿ çäåñü ìèíèìàëüíî âîçìîæíî: èõ òîëüêî äâà  ¾èñòèííî¿ è ¾ëîæíî¿, êîòîðûå ìû áóäåì îáîçíà÷àòü 1 è 0 ñîîòâåòñòâåííî.  ñèëó ýòîãî êëàññè÷åñêóþ
àëãåáðó ëîãèêè íàçûâàþò äâóõâàëåíòíîé è îáîçíà÷àþò
C2. Íà ìíîæåñòâå äàííûõ èñòèííîñòíûõ çíà÷åíèé ââîäÿò ðåôëåêñèâíîå îòíîøåíèå ïîðÿäêà ⩽, ïîëàãàÿ 0 ⩽ 1.
Óñòàíîâëåííàÿ èñòèííîñòü âûñêàçûâàíèÿ ñ÷èòàåòñÿ íåèçìåííîé â äàííîì ðàññìîòðåíèè. Âûñêàçûâàíèÿ óêàçàííîãî
òèïà íàçûâàþò â ëîãèêå äèñêðèïòèâíûìè, èëè îïèñàòåëüíûìè. Îòìåòèì, ÷òî âûñêàçûâàíèÿ ñîîòâåòñòâóþò ñóæäåíèÿì â ôèëîñîôñêîé ëîãèêå (åñëè îòâëå÷üñÿ îò ñòðóêòóðû
ïîñëåäíèõ), âûðàæàþùèì ñâÿçü ìåæäó ïîíÿòèÿìè è îáëàäàþùèì ñâîéñòâîì áûòü èñòèííûìè èëè ëîæíûìè.
Ïðèìåð 1.1. 2 Ïðèâåä¼ííûå íèæå âûðàæåíèÿ ÿâëÿþòñÿ
âûñêàçûâàíèÿìè â C2.

1. Çåìëÿ  øàð.
2. Çåìëÿ ïëîñêàÿ.
3. Êóðèöà íå ïòèöà.
4. 6 äåëèòñÿ íà 2 è íà 3.
5. Çäåñü ðàñò¼ò äåðåâî.

1 Ïîä÷åðêí¼ì, ÷òî â àëãåáðå ëîãèêå ñíà÷àëà äàþò îöåíêó âûñêàçûâàíèþ, à çàòåì óæå îòâëåêàþòñÿ îò åãî ñìûñëà: èíà÷å ïîòåíöèàëüíî ìîæíî äàòü ëþáóþ èñòèííîñòíóþ îöåíêó ëþáîìó âûðàæåíèþ.
2 Â äàííîì ïîñîáèè ïðèíÿòà ñêâîçíàÿ â ïðåäåëàõ ãëàâ îáùàÿ íóìåðàöèÿ ïðèìåðîâ, îïðåäåëåíèé, òåîðåì è ëåìì.

Ãëàâà 1. Àëãåáðà ëîãèêè

6. Âñå ñîâåðøåííûå ÷èñëà ÷¼òíûå.

Èñòèííîñòü/ëîæíîñòü âûñêàçûâàíèé (1)(4) ðàç è íàâñåãäà óñòàíîâëåíà. Âûñêàçûâàíèÿ, àíàëîãè÷íûå (5), íàçûâàþò íåîïðåäë¼ííûìè. Èõ ïðèíÿòî âêëþ÷àòü â äèñêðèïòèâíûå âûñêàçûâàíèÿ, ïîñêîëüêó ïðè êîíêðåòèçàöèè
ñîîòâåòñòâóþùèõ óñëîâèé îíè ïîëó÷àþò îöåíêó ¾èñòèííî¿ èëè ¾ëîæíî¿. Èñòèííîñòíàÿ îöåíêà âûñêàçûâàíèÿ (6)
íåèçâåñòíà, îäíàêî îíà íå çàâèñèò îò êàêèõ-ëèáî ïðèâõîäÿùèõ îáñòîÿòåëüñòâ. Ïîñëåäíèé ïðèìåð òàêæå ïîêàçûâàåò, ÷òî õîòÿ óñòàíîâëåíèå èñòèííîñòè/ëîæíîñòè âûñêàçûâàíèé ìîæåò ïîòðåáîâàòü çíà÷èòåëüíûõ óñèëèé, â ëîãèêå âàæíà ëèøü ïðèíöèïèàëüíàÿ âîçìîæíîñòü óêàçàííîé
îöåíêè.
Ïðèìåð 1.2. Ïðèâåä¼ííûå íèæå âûðàæåíèÿ âûñêàçûâàíèÿìè â C2 íå ÿâëÿþòñÿ.

7. Òû êòî òàêîé?
8. Êàê õîðîøî áûòü ãåíåðàëîì!
9. Â
çàâòðàøíåì
ôóòáîëüíîì
ìàò÷å
¾Ñïàðòàê¿
¾Äèíàìî¿ ïîáåäèò ¾Ñïàðòàê¿
10. ß ëãó.
11. x + y = 2.

Âûðàæåíèå (7) íå ÿâëÿåòñÿ ïîâåñòâîâàòåëüíûì, òî åñòü
óòâåðæäàþùèì èëè îòðèöàþùèì íå÷òî. Ïîâåñòâîâàòåëüíîå ïðåäëîæåíèå (8) îòíîñèòñÿ ê òàê íàçûâàåìûì îöåíî÷íûì, âûðàæàþùèìè ñóáúåêòèâíîå ìíåíèå òîãî èëè èíîãî ëèöà, è ïîýòîìó â êëàññè÷åñêîé ëîãèêå îíè íå ðàññìàòðèâàþòñÿ. Èñòèííîñòü óòâåðæäåíèÿ (9) íå âûðàæàåòñÿ àäåêâàòíî â òåðìèíàõ ¾èñòèíà/ëîæü¿, îäíàêî äëÿ íåãî
âîçìîæíû îöåíêè, íàïðèìåð, âåðîÿòíîñòíîãî òèïà. Óòâåðæäåíèå (10)  åãî íàçûâàþò ïàðàäîêñîì ëæåöà  ïðèíöèïèàëüíî íå ìîæåò áûòü íè èñòèííûì, íè ëîæíûì3. Èñòèííîñòü âûðàæåíèÿ (11) çàâèñèò îò êîíêðåòíûõ çíà÷åíèé

3  àíòè÷íîé Ãðåöèè áûë îáíàðóæåí ïàðàäîêñ, âîçíèêøèé èç ñî

1.1. Êëàññè÷åñêàÿ àëãåáðà âûñêàçûâàíèé C2
9

âõîäÿùèõ â íåãî ïåðåìåííûõ èç íåêîòîðîé îáëàñòè îïðåäåëåíèÿ, îòëè÷íîé îò {0, 1}. Âûðàæåíèÿ òàêîãî òèïà íàçûâàþò âûñêàçûâàòåëüíûìè ôîðìàìè.
Ïåðåéäåì òåïåðü ê îïåðàöèÿì íàä âûñêàçûâàíèÿìè.
Îòìåòèì ñíà÷àëà, ÷òî êàæäîå èç âûñêàçûâàíèé (1), (2),
(5) è (6) ïðåäñòàâëÿåò ñîáîé îäíî íåðàçëîæèìîå óòâåðæäåíèå. Òàêèå âûñêàçûâàíèÿ íàçûâàþò ïðîñòûìè (ýëåìåíòàðíûìè, àòîìàðíûìè). Ñ äðóãîé ñòîðîíû, âûñêàçûâàíèÿ (3) è (4) ïðèìåðà 1.1 âêëþ÷àþò â ñåáÿ áîëåå ïðîñòûå
óòâåðæäåíèÿ: âûñêàçûâàíèå (3) åñòü îòðèöàíèå íåêîòîðîãî ôàêòà, â âûñêàçûâàíèè (4) óòâåðæäàåòñÿ ñîâìåñòíàÿ
ñïðàâåäëèâîñòü äâóõ ñâîéñòâ.
Ïîñêîëüêó â êëàññè÷åñêîé àëãåáðå ëîãèêå âûñêàçûâàíèÿ áûâàþò ëèáî èñòèííûìè, ëèáî ëîæíûìè, è ðàññìàòðèâàåòñÿ îíè òîëüêî ñ ýòîé òî÷êè çðåíèÿ, êàæäîìó ýëåìåíòàðíîìó âûñêàçûâàíèþ ñîïîñòàâëÿþò ïðîïîçèöèîíàëüíóþ4 èëè ëîãè÷åñêóþ ïåðåìåííóþ, ïðèíèìàþùóþ
çíà÷åíèÿ 1 èëè 0. Ýòè ïåðåìåííûå ìû áóäåì îáîçíà÷àòü
ñòðî÷íûìè ëàòèíñêèìè áóêâàìè, âîçìîæíî ñ èíäåêñàìè,
ñ ñåðåäèíû àëôàâèòà: p, q, . . . , z, à âñ¼ èõ ìíîæåñòâî 
V ar.

äåðæàùåãî ôðàçó ¾Êðèòÿíå, âå÷íûå ëæåöû...¿ ñòèõîòâîðåíèÿ, ïðèïèñûâàåìîìó ïîëóëåãåíäàðíîìó ïîýòó-ïðîðèöàòåëþ Ýïèìåíèäó èç
Êðèòà (IV â. äî í.ý.). Â ôèëîñîôñêîé òðàäèöèè ïàðàäîêñ ïðèíÿë
ôîðìó ¾Êðèòÿíèí Ýïèìåíèä çàÿâèë, ÷òî âñå êðèòÿíå  ëæåöû¿.
Îäíàêî, åñëè âñå êðèòÿíå  ëæåöû, òî Ýïèìåíèä, ïîñêîëüêó îí ñàì
êðèòÿíèí, ëæ¼ò è, ñëåäîâàòåëüíî, íå âñå êðèòÿíå ëæåöû. Âûõîäèò,
èç âûñêàçûâàíèÿ Ýïèìåíèäà ñëåäóåò òîëüêî ñóùåñòâîâàíèå êðèòÿíèíà, êîòîðûé íå ëæ¼ò. Ýòî íå ÿâëÿåòñÿ íåâîçìîæíûì, è ïîýòîìó
çäåñü íåò íèêàêîãî ïàðàäîêñà. Ïàðàäîêñ âîçíèêàåò ïðè òðàêòîâêå
îòðèöàíèÿ, â êîòîðîé óòâåðæäåíèå Ýïèìåíèäà, ïîñêîëüêó îí ñàì
êðèòÿíèí, îçíà÷àåò ¾Âñå êðèòÿíå ãîâîðÿò òîëüêî ïðàâäó¿. Äàííûé
íåäîñòàòîê èñïðàâëåí â âûøåïðèâåä¼ííîì èçðå÷åíèè, âîñõîäÿùåì
ê Æ. Áóðèäàíó.
Îòìåòèì, ÷òî íåâîçìîæíîñòü èñòèííîñòíîé îöåíêè ïîäîáíûõ âûðàæåíèé ëåæèò â îñíîâå ðÿäà çàìå÷àòåëüíûõ òåîðåì ìàòåìàòè÷åñêîé ëîãèêè.
4 propositio (ëàò.)  âûñêàçûâàíèå, ñóæäåíèå

Ãëàâà 1. Àëãåáðà ëîãèêè

Âûñêàçûâàíèÿ, êîòîðûå ïîëó÷àþòñÿ èç äðóãèõ âûñêàçûâàíèé ñ ïîìîùüþ ãðàììàòè÷åñêèõ ñâÿçîê ¾íå¿, ¾è¿,
¾èëè¿, ¾åñëè..., òî...¿ (¾èç... ñëåäóåò...¿), ¾òîãäà è òîëüêî
òîãäà, êîãäà¿ (¾..., åñëè è òîëüêî åñëè...¿, ¾ýêâèâàëåíòíî¿)
íàçûâàþò ñëîæíûìè èëè ñîñòàâíûìè. Óêàçàííûå ãðàììàòè÷åñêèå ñâÿçêè çàìåíÿþò ëîãè÷åñêèìè ñâÿçêàìè ¬5,
, ∨,
è ≡, ò.å. îòðèöàíèÿ, êîíúþíêöèè, äèçúþíêöèè,
èìïëèêàöèè è òîæäåñòâà ñîîòâåòñòâåííî. Â ðåçóëüòàòå òàêîé çàìåíû îáðàçóþòñÿ ôîðìóëû èç ïðîïîçèöèîíàëüíûõ
ïåðåìåííûõ èëè ôîðìóëû àëãåáðû ëîãèêè íàä ââåä¼ííûì
ìíîæåñòâîì ëîãè÷åñêèõ ñâÿçîê; îíè îòíîñÿòñÿ ê ñèíòàêñèñó ëîãèêè.
Ôîðìóëû àëãåáðû ëîãèêè è ñîîòâåòñòâóþùèå èì ñëîæíûå âûñêàçûâàíèÿ áóäåì îáîçíà÷àòü ïðîïèñíûìè ëàòèíñêèìè áóêâàìè èç íà÷àëà àëôàâèòà6: A, B, . . ..
Íàïîìíèì ïðàâèëà ïîñòðîåíèÿ ôîðìóë àëãåáðû ëîãèêè è ïîíÿòèÿ, ñ íèìè ñâÿçàííûå.

Îïðåäåëåíèå 1.3. Ôîðìóëîé (àëãåáðû ëîãèêè) íàä ìíîæåñòâîì Φ =
¬ , , ∨,
, ≡
ëîãè÷åñêèõ ñâÿçîê íàçû-
âàåòñÿ âûðàæåíèå âèäà

1) ëþáàÿ ïðîïîçèöèîíàëüíàÿ ïåðåìåííàÿ;

2)
(¬A), (A B), (A ∨ B), (A
B), (A ≡ B), ãäå A è
B  ôîðìóëû íàä Φ.

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

5  îòå÷åñòâåííîì òèïîãðàôñêîì íàáîðå ðàíåå ÷àñòî èñïîëüçîâàëè çíàê
.
6 Îòìåòèì, ÷òî â ëîãè÷åñêîé ëèòåðàòóðå ÷àñòî èñïîëüçóþòñÿ òðàäèöèîííûå îáîçíà÷åíèÿ ýëåìåíòàðíûõ âûñêàçûâàíèé ïðîèçâîëüíûìè ïðîïèñíûìè ëàòèíñêèìè áóêâàìè (è èìåííî ñ íà÷àëà àëôàâèòà),
à ôîðìóë íàä íèìè  âûáîðîì îñîáûõ ëèáî øðèôòà, ëèáî àëôàâèòà. Òàê æå òðàäèöèîííî äëÿ ôîðìóë èñïîëüçóþò ãîòè÷åñêèé øðèôò,
õîòÿ âñòðå÷àþòñÿ è ðóêîïèñíûé øðèôò, è ãðå÷åñêèé àëôàâèò.  ïîñëåäíåå âðåìÿ, îäíàêî, íàáëþäàåòñÿ òåíäåíöèÿ ê óïðîùåíèþ îáîçíà÷åíèé.

1.1. Êëàññè÷åñêàÿ àëãåáðà âûñêàçûâàíèé C2
11

Ôèãóðèðóþùèå â ï. 2) ôîðìóëû A è B íàçûâàþò ïîäôîðìóëàìè, ñèìâîëû ñâÿçîê  ãëàâíûìè ñâÿçêàìè ñîîòâåòñòâóþùèõ ôîðìóë, à ñêîáêè  ïàðíûìè äðóã ê äðóãó.
Åñëè A  ïîäôîðìóëà B, à B  ïîäôîðìóëà C, òî A 
ïîäôîðìóëà C. ×èñëî ñâÿçîê â äàííîé ôîðìóëå åñòü å¼
äëèíà èëè ñëîæíîñòü. Ýëåìåíòàðíûå âûñêàçûâàíèÿ (ïðîïîçèöèîíàëüíûå ïåðåìåííûå), ðàññìàòðèâàåìûå êàê ôîðìóëû, áóäåì îòìå÷àòü íóëåâûì èíäåêñîì  íàïðèìåð, A0.
Ìíîæåñòâî âñåõ ôîðìóë C2 áóäåì îáîçíà÷àòü çíàêîì A.
Äëÿ ñîêðàùåíèÿ ÷èñëî ñêîáîê â çàïèñè ôîðìóë ïðèíèìàþò ñëåäóþùèå ñîãëàøåíèÿ:

ˆ âíåøíèå ñêîáêè ó ôîðìóë îïóñêàþòñÿ;
ˆ ñâÿçêà ¬ ñèëüíåå (ò.å. âûïîëíÿåòñÿ ïðåæäå) âñåõ
îñòàëüíûõ ñâÿçîê;
ˆ ñâÿçêà ñèëüíåå îñòàëüíûõ äâóõìåñòíûõ ñâÿçîê;
ˆ ñâÿçêà ∨ ñèëüíåå ñâÿçîê
è ≡ ;
ˆ ñâÿçêè
è ≡ ðàâíîñèëüíû.

Äàëåå ïîä çàïèñüþ A = B ìû áóäåì ïîíèìàòü, ÷òî
ôîðìóëû A è B ñîâïàäàþò êàê ñòðîêè ñèìâîëîâ, òî åñòü
èõ ñèíòàêñè÷åñêîå òîæäåñòâî.  ñèëó ýòîãî, íàïðèìåð,
p ∨ q ̸= q ∨ p è x (y z) ̸= (x y) z. Çàìåòèì, ÷òî
ñèìâîë = íå ïðèíàäëåæèò ÿçûêó ëîãèêè C2, íî âûðàæàåò
îòíîøåíèå òîæäåñòâà íà ìíîæåñòâå A âñåõ ôîðìóë C2.
Ñëåäóåò ñêàçàòü, ÷òî ðàññìîòðåííàÿ âûøå çàìåíà
ãðàììàòè÷åñêèõ ñâÿçîê íà ëîãè÷åñêèå íå âñåãäà òî÷íî ñîõðàíÿåò ñìûñë èñõîäíîé ôðàçû. Íàïðèìåð, ïðè òàêîé çàìåíå ¾íå¿ ïîíèìàåòñÿ âñåãäà â êîíòðàäèêòîðíîì ñìûñëå (¾íåâåðíî, ÷òî...¿)7, ¾èëè¿  â ñîåäèíèòåëüíîì ñìûñëå

7 Êîíòðàäèêòîðíûì îòðèöàíèåì âûñêàçûâàíèÿ ¾ñíåã áåëûé¿ áóäåò ¾íåâåðíî, ÷òî ñíåã áåëûé¿ èëè ýêâèâàëåíòíîå ¾ñíåã íå áåëûé¿.
 ëîãèêå ðàññìàòðèâàþò è êîíòðàðíîå îòðèöàíèå (ñì. âûøå îáñóæäåíèå ïàðàäîêñà ëæåöà). Îíî, âîîáùå ãîâîðÿ, îïðåäåëÿåòñÿ íåîäíîçíà÷íî: íàïðèìåð, âîçìîæíûìè êîíòðàðíûìè îòðèöàíèÿìè ðàññìàòðèâàåìîãî âûñêàçûâàíèÿ áóäåò ¾ñíåã ÷¼ðíûé¿, ¾ñíåã çåë¼íûé¿ è ò. ä.

Ãëàâà 1. Àëãåáðà ëîãèêè

(¾èëè òî, èëè äðóãîå, èëè òî è äðóãîå âìåñòå¿), à â òðàêòîâêå ñâÿçêè ¾è¿ îòñóòñòâóþò èíîãäà ïðîÿâëÿþùèåñÿ âðåìåííîé èëè ïðè÷èííûé àñïåêòû8.
Èñêëþ÷èòåëüíî âàæíóþ ðîëü â ìàòåìàòè÷åñêîé ëîãèêå èãðàåò îïåðàöèÿ èìïëèêàöèè èëè óñëîâíîãî óòâåðæäåíèÿ, ïîçâîëÿþùàÿ â ÿâíîé ôîðìå ñòðîèòü ëîãè÷åñêèå
âûâîäû. Âõîäÿùèå â óñëîâíîå óòâåðæäåíèå âûñêàçûâàíèÿ èìåþò ñïåöèàëüíûå íàçâàíèÿ: åñëè äàíà èìïëèêàöèÿ
A
B, òî ôîðìóëó A íàçûâàþò å¼ àíòåöåäåíòîì, à ôîðìóëó B  êîíñåêâåíòîì9. Â ñîîòâåòñòâèè ñ òàáëèöåé èñòèííîñòè èìïëèêàöèè, îäíîâðåìåííàÿ èñòèííîñòü A
B
è A îçíà÷àåò èñòèííîñòü âûñêàçûâàíèÿ B10.
Èìïëèêàöèÿ, ïî-âèäèìîìó, â íàèáîëüøåé ñòåïåíè, ÷åì
äðóãèå ñâÿçêè, íå àäåêâàòíà ñâîåé ãðàììàòè÷åñêîé ôîðìå
¾åñëè..., òî...¿. Äåéñòâèòåëüíî, åñòåñòâåííî òðåáîâàòü, ÷òîáû âûðàæåíèå ¾Åñëè íàòóðàëüíîå n äåëèòñÿ íà 6, òî îíî
äåëèòñÿ è íà 3¿ áûëî èñòèííûì ïðè ëþáîì n. Íî òîãäà
ïðè n = 3 èìååì ëîæíûé àíòåöåäåíò11 è ïàðàäîêñ ëîæ
8 Ñð. ¾åìó ñòàëî ñòðàøíî, è îí çàêðûë ãëàçà¿ è ¾îí çàêðûë ãëàçà,
è åìó ñòàëî ñòðàøíî¿. Â èíòåðåñíîé êíèãå Þ.È. Ìàíèíà Äîêàçóåìîå
è íåäîêàçóåìîå ïðèâåäåíû ïÿòü ñïîñîáîâ âûðàçèòü êîíúþíêöèþ äëÿ
ðàçíûõ åñòåñòâåííûõ ÿçûêîâ, âêëþ÷àÿ ëàòûíü, êèòàéñêèé è ñóàõèëè.
9 Îò ëàò. antecedent  ïðåäøåñòâóþùèé è consequent  ïîñëåäóþùèé ÷ëåíû îòíîøåíèÿ.
10 Åñëè èìïëèêàöèÿ èñòèííà, à àíòåöåäåíò ëîæåí, òî êîíñåêâåíò
ìîæåò áûòü êàê èñòèííûì, òàê è ëîæíûì. Ïðèìåð: ¾Åñëè âîçðàñòàþùàÿ êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü p1 = 2, p2 = 3, . . . , pk ñîäåðæèò
âñå ïðîñòûå ÷èñëà (Ak), òî ÷èñëî p1·. . .·pk+1  òàêæå ïðîñòîå (Bk)¿.

Óñëîâíîå óòâåðæäåíèå Ak
Bk, î÷åâèäíî, èñòèííî äëÿ ëþáîãî k.
Òàêèì îáðàçîì, ìíîæåñòâî ïðîñòûõ ÷èñåë áåñêîíå÷íî è âñå âûñêàçûâàíèÿ A1, A2, . . . ëîæíû. Îäíàêî, èñïîëüçóÿ òîëüêî èñòèííîñòíûå
çíà÷åíèÿ, áåç îáðàùåíèÿ ê ñîäåðæàíèþ âûñêàçûâàíèé, èñòèííîñòü
Bk îïðåäåëèòü íåâîçìîæíî: òàê, âûñêàçûâàíèÿ B1, . . . , B5 èñòèííû, à B6 ëîæíî ( 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 · 509).
11 Èç ëîæíûõ ïîñûëîê ìîæåò ñëåäîâàòü èñòèíà. Íàïðèìåð, ïðèíöèïèàëüíî íåâåðíàÿ ãåîöåíòðè÷åñêàÿ ñèñòåìà ìèðà Ïòîëåìåÿ î÷åíü
òî÷íî îïèñûâàåò âèäèìîå äâèæåíèå ïëàíåò.

1.1. Êëàññè÷åñêàÿ àëãåáðà âûñêàçûâàíèé C2
13

íîãî âûñêàçûâàíèÿ, êîãäà èç ëæè ñëåäóåò èñòèíà. Ïîýòîìó îáà âûñêàçûâàíèÿ ¾Åñëè Çåìëÿ ïëîñêàÿ, òî äâàæäû
äâà  ÷åòûðå¿ è ¾Åñëè Çåìëÿ ïëîñêàÿ, òî äâàæäû äâà
 ïÿòü¿ ìû âûíóæäåíû îöåíèâàòü êàê èñòèííûå. Òàêàÿ
îöåíêà âñòóïàåò â ïðîòèâîðå÷èå ñ îáû÷íûì ïîíèìàíèåì
ñìûñëà ãðàììàòè÷åñêîé ñâÿçêè ¾åñëè..., òî...¿, ïðè êîòîðîì ïîäðàçóìåâàåòñÿ ïðè÷èííàÿ ñâÿçü ìåæäó ñîñòàâëÿþùèìè å¼ óòâåðæäåíèÿìè.
Áèíàðíóþ ëîãè÷åñêóþ îïåðàöèþ
ñ âåêòîðîì èñòèííîñòíûõ çíà÷åíèé (1, 1, 0, 1) ïðè ñòàíäàðòíîì ðàñïîëîæåíèè íàáîðîâ ïåðåìåííûõ (ñì. íèæå) íàçûâàþò â ëîãèêå
ìàòåðèàëüíîé èìïëèêàöèåé, à íåñîãëàñîâàííîñòè å¼ èñòèííîñòíûõ çíà÷åíèé ñî ñìûñëîì ãðàììàòè÷åñêîé ôîðìû
¾åñëè..., òî...¿  ïàðàäîêñàìè ìàòåðèàëüíîé èìïëèêàöèè.
Îòìåòèì, ÷òî ñòðåìëåíèå èñêëþ÷èòü óêàçàííûå ïàðàäîêñû ÿâëÿåòñÿ îäíèì èç ñòèìóëîâ êîíñòðóèðîâàíèÿ ðàçëè÷íûõ íåêëàññè÷åñêèõ ëîãèê.
 äàííîé êíèæêå çíàêè ⇒ è ⇔ ïðèìåíÿþòñÿ êàê ñîêðàùåíèÿ âûðàæåíèé ¾åñëè..., òî...¿ è ¾..., åñëè è òîëüêî
åñëè...¿ â òåêñòå, à çíàêè
è ≡ èñïîëüçóþòñÿ èñêëþ÷èòåëüíî â ôîðìóëàõ êàê ñèìâîëû ëîãè÷åñêèõ ñâÿçîê è îïåðàöèé èìïëèêàöèè è òîæäåñòâà ñîîòâåòñòâåííî. Ïðè ýòîì
â çàïèñè A ⇒ B óòâåðæäåíèå A íàçûâàþò ïîñûëêîé, à
B  ñëåäñòâèåì.
Êàê óæå óïîìèíàëîñü, â êëàññè÷åñêîé àëãåáðå ëîãèêè
ðàññìàòðèâàþòñÿ òîëüêî òàêèå îïåðàöèè íàä âûñêàçûâàíèÿìè, èñòèííîñòíûå çíà÷åíèÿ êîòîðûõ ïîëíîñòüþ îïðåäåëÿþòñÿ èñòèííîñòíûìè çíà÷åíèÿìè îïåðàíäîâ12. Ýòî

12 Íàïðèìåð, åñëè p  âûñêàçûâàíèå, òî ¾ß íå âåðþ, ÷òî p èñòèíî¿ íå áóäåò èìåòü ýêâèâàëåíòà â àëãåáðå ëîãèêè, ïîñêîëüêó åãî
èñòèííîñòü çàâèñèò, îò òîãî, êòî êîíêðåòíî ïðîèçíîñèò äàííóþ ôðàçó.
 íåêëàññè÷åñêèõ ëîãèêàõ óêàçàííîå óñëîâèå ìîæåò íå èìåòü ìåñòà: òàì èñòèííîñòü ñëîæíîãî âûñêàçûâàíèÿ ìîæåò çàâèñåòü òàêæå
è îò åãî ñòðóêòóðû, ñîäåðæàíèÿ âõîäÿùèõ â íåãî ïîíÿòèé, êîíòåêñòà
è ò. ä. (ñì. çàìå÷àíèå íà ñ. 32).