ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 879
Скачиваний: 9
51
ñòâåííîíàó÷íûõ, òàê è ãóìàíèòàðíûõ îáëàñòåé çíàíèÿ: áèîëîãè è ôèëîëî-
ãè, ýêîíîìèñòû è þðèñòû. Âñå ýòî ñäåëàëî ïîíèìàíèå ïóòåé èñïîëüçîâàíèÿ
ìàòåìàòè÷åñêîãî àïïàðàòà âî âíåìàòåìàòè÷åñêèõ èññëåäîâàíèÿõ ÷óòü ëè
íå îäíèì èç âàæíåéøèõ ýëåìåíòîâ îáùåé êóëüòóðû, à âëàäåíèå òåðìèíàìè
¾ìàòåìàòè÷åñêàÿ ñòðóêòóðà¿ è ¾ìàòåìàòè÷åñêàÿ ìîäåëü¿ íåîáõîäèìû-
ìè àòðèáóòàìè îáðàçîâàííîãî ÷åëîâåêà.
Ïðåäìåòîì ëîãèêè íå ÿâëÿåòñÿ âíåøíèé ìèð, íî ëèøü ñèñòåìû åãî
îñìûñëåíèÿ. Ëîãèêà îäíîé èç òàêèõ ñèñòåì ìàòåìàòèêè â ñèëó ñâîåé
íîðìàëèçîâàííîñòè ïðåäñòàâëÿåò ïîäîáèå òðàôàðåòà, êîòîðûé ìîæíî íà-
êëàäûâàòü íà ëþáóþ äðóãóþ ñèñòåìó. Ñîîòâåòñòâèå èëè ðàñõîæäåíèå ýòîãî
òðàôàðåòà ñ ñèñòåìîé, îäíàêî, íå ñëóæèò êðèòåðèåì åå ïðèãîäíîñòè ëèáî
ìåðèëîì öåííîñòè.
Åùå Ëåéáíèö (1789-1857) âûñêàçàë èäåþ ôîðìàëèçàöèè âñåé ìàòåìà-
òèêè íà îñíîâå ñîçäàíèÿ ¾ëîãè÷åñêîãî èñ÷èñëåíèÿ¿ ñâîåîáðàçíîãî ìàòå-
ìàòè÷åñêîãî ÿçûêà. Çàïèñàâ âñå èñõîäíûå äîïóùåíèÿ íà òàêîì ÿçûêå ñïå-
öèàëüíûìè ñèìâîëàìè, ïîõîæèìè íà ìàòåìàòè÷åñêèå, îí íàäåÿëñÿ çàìå-
íèòü ðàññóæäåíèÿ âû÷èñëåíèÿìè.  òðèäöàòûõ ãîäàõ íàøåãî âåêà Äàâèä
Ãèëüáåðò âûñòóïèë ñ ïðîãðàììîé îáîñíîâàíèÿ ìàòåìàòèêè íà áàçå ôèíèò-
íûõ ìåòîäîâ ìàòåìàòè÷åñêîé ëîãèêè. Îêîí÷àòåëüíî ýòè íàäåæäû ðàçâåÿëè
óïîìÿíóòûå âûøå ðåçóëüòàòû üäåëÿ (1937) î íåïîëíîòå èñ÷èñëåíèÿ ïðå-
äèêàòîâ è ôîðìàëüíîé àðèôìåòèêè.
Ìû áóäåì èçó÷àòü îäíó èç ïðîñòåéøèõ ìîäåëåé ìàòåìàòè÷åñêîé ëîãè-
êè àëãåáðó âûñêàçûâàíèé èëè àëãåáðó ëîãèêè.
Ïåðâûìè ìàòåìàòè÷åñêèìè ðàáîòàìè, çàëîæèâøèìè îñíîâó ñîâðåìåí-
íîé àëãåáðû ëîãèêè, áûëè ðàáîòû Äæîðäæà Áóëÿ (1815-1864) è Àóãñòà-
ñà äå Ìîðãàíà (1806-1873). Íàçâàíèÿ ýòèõ ðàáîò íåñîìíåííî çàñëóæèâàþò
óïîìèíàíèÿ.
Äæîðäæ Áóëü:
¾Ìàòåìàòè÷åñêèé àíàëèç ëîãèêè, ÿâëÿþùèéñÿ î÷åðêîì, êàñàþùèìñÿ èñ-
÷èñëåíèÿ äåäóêòèâíûõ ðàññóæäåíèé¿, (1847 ã.),
¾Èññëåäîâàíèÿ çàêîíîâ ìûñëè. íà êîòîðûõ îñíîâûâàþòñÿ ìàòåìàòè÷åñêèå
òåîðèè ëîãèêè è âåðîÿòíîñòåé¿, (1854 ã.).
Àóãóñòóñ äå Ìîðãàí:
¾Ôîðìàëüíàÿ ëîãèêà èëè èñ÷èñëåíèå âûâîäîâ, íåîáõîäèìûõ è âîçìîæíûõ¿
(1847 ã.).
52
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
2.1 Ýëåìåíòàðíûå âûñêàçûâàíèÿ
 ëîãèêå ïîä ¾âûñêàçûâàíèåì¿ ïîíèìàþò òî, ÷òî âûðàæàåòñÿ, êàê ãîâîðÿò
â ëèíãâèñòèêå, ïîñðåäñòâîì îñìûñëåííîãî óòâåðäèòåëüíîãî ïðåäëîæåíèÿ,
òî åñòü ïîâåñòâîâàòåëüíîãî ïðåäëîæåíèÿ, î êîòîðîì ìîæíî (ïî êðàéíåé
ìåðå â ïðåäåëàõ îïðåäåëåííîãî êîíòåêñòà) ãîâîðèòü, ÷òî îíî èñòèííî èëè
ëîæíî.
Ïðèìåðû ýëåìåíòàðíûõ âûñêàçûâàíèé:
Ñíåã áåëûé.
Ïàðèæ ñòîëèöà Èòàëèè.
Âñå ëþäè ñìåðòíû.
Ñîêðàò ÷åëîâåê.
Åñëè ñíåã ãîðèò, òî îñòàåòñÿ çîëà.
Åñëè íà óëèöå èäåò äîæäü, òî âëàæíîñòü âûøå, ÷åì ïðè ñîëíå÷íîé ñóõîé
ïîãîäå.
Íå âñÿêîå ïðåäëîæåíèå ÿâëÿåòñÿ âûñêàçûâàíèåì. Òàê, ê âûñêàçûâà-
íèÿì íå îòíîñÿòñÿ âîïðîñèòåëüíûå è âîñêëèöàòåëüíûå ïðåäëîæåíèÿ, ïî-
ñêîëüêó ãîâîðèòü îá èõ èñòèííîñòè èëè ëîæíîñòè íåò ñìûñëà. Ïðåäëîæå-
íèÿ ¾Øåë ñíåã¿, ¾Ïëîùàäü êîìíàòû ðàâíà
20
ì
2
¿, ¾
a
2
= 4
¿ íå ÿâëÿþòñÿ
âûñêàçûâàíèÿìè; äëÿ òîãî, ÷òîáû èìåëî ñìûñë ãîâîðèòü îá èõ èñòèííîñòè
èëè ëîæíîñòè, íóæíû äîïîëíèòåëüíûå ñâåäåíèÿ: êîãäà è ãäå øåë ñíåã, î
êàêîé êîíêðåòíîé êîìíàòå èäåò ðå÷ü, êàêîå ÷èñëî îáîçíà÷åíî áóêâîé à. Â
ïîñëåäíåì ïðèìåðå à ìîæåò íå îáîçíà÷àòü êîíêðåòíîãî ÷èñëà, à áûòü ïå-
ðåìåííîé, âìåñòî êîòîðîé ìîæíî ïîäñòàâëÿòü ýëåìåíòû íåêîòîðîãî ìíî-
æåñòâà, íàçûâàåìûå çíà÷åíèÿìè ïåðåìåííîé.
Èç äâóõ äàííûõ ïðåäëîæåíèé ìîæíî îáðàçîâàòü íîâîå ïðåäëîæåíèå ñ
ïîìîùüþ ñîþçîâ ¾è¿, ¾èëè¿, ¾åñëè ... òî¿, ¾òîãäà è òîëüêî òîãäà, êîãäà¿.
Ñ ïîìîùüþ ÷àñòèöû ¾íå¿ èëè ñëîâîñî÷åòàíèÿ ¾íåâåðíî, ÷òî¿ èç îäíîãî
äàííîãî ïðåäëîæåíèÿ ìîæíî ïîëó÷èòü íîâîå. Ñîþçû ¾è¿, ¾èëè¿, ¾åñëè ...
òî¿, ¾òîãäà è òîëüêî òîãäà, êîãäà¿ è ÷àñòèöó ¾íå¿ íàçûâàþò ëîãè÷åñêèìè
ñâÿçêàìè.
 âûñêàçûâàíèè íàñ ïðåæäå âñåãî èíòåðåñóåò åãî èñòèííîñòíîå çíà÷å-
íèå, òî åñòü ÿâëÿåòñÿ îíî èñòèííûì èëè ëîæíûì. ×òîáû îòâåòèòü íà ýòîò
âîïðîñ, íàì íè÷åãî íå íàäî çíàòü î ñîñòàâëÿþùèõ âûñêàçûâàíèÿõ, êðîìå
èõ èñòèííîñòíûõ çíà÷åíèé. Ýòà èíôîðìàöèÿ ïîëíîñòüþ îïðåäåëÿåò èñòèí-
íîñòíîå çíà÷åíèå ñëîæíîãî âûñêàçûâàíèÿ.
Äëÿ îáîçíà÷åíèÿ ëæè ìû áóäåì èñïîëüçîâàòü ñèìâîë 0, à äëÿ îáîçíà-
÷åíèÿ èñòèíû ñèìâîë 1.
Ýëåìåíòàðíûå âûñêàçûâàíèÿ, òàêèì îáðàçîì, ìû áóäåì îáîçíà÷àòü ñèì-
2.2. ÝËÅÌÅÍÒÀÐÍÛÅ ËÎÃÈ×ÅÑÊÈÅ ÎÏÅÐÀÖÈÈ(ÔÓÍÊÖÈÈ)
53
âîëàìè ïåðåìåííûõ, ïðèíèìàþùèõ çíà÷åíèÿ 0 èëè 1. Òàêèå ïåðåìåííûå
áóäåì íàçûâàòü ëîãè÷åñêèìè èëè áóëåâûìè ïåðåìåííûìè.
Ïóñòü
U
=
{
u
1
, u
2
, . . . , u
n
, . . .
}
èñõîäíûé àëôàâèò ïåðåìåííûõ. ×òî-
áû èçáåæàòü ñëîæíûõ îáîçíà÷åíèé äëÿ èíäåêñîâ ïåðåìåííûõ, ìû áóäåì
óïîòðåáëÿòü â êà÷åñòâå ìåòàîáîçíà÷åíèé (îáîçíà÷åíèé äëÿ ïðîèçâîëüíûõ
ñèìâîëîâ àëôàâèòà
U
) ñèìâîëû
x
,
y
,
z
,
. . .
, à òàêæå ýòè è äðóãèå ñèìâîëû
ñ èíäåêñàìè. Èòàê, ëîãè÷åñêèå ïåðåìåííûå (ýëåìåíòàðíûå âûñêàçûâàíèÿ)
èìåþò âèä:
x, y, z, . . .
;
x
1
, x
2
, x
3
, . . .
;
x
∈
{èñòèíà, ëîæü} = {1, 0};
èñòèíà
= 1
;
ëîæü
= 0
.
2.2 Ýëåìåíòàðíûå ëîãè÷åñêèå îïåðàöèè(ôóíêöèè)
Îïðåäåëåíèå. Ôóíêöèÿ
f
(˜
x
n
)
, îïðåäåëåííàÿ íà ìíîæåñòâå
B
n
=
{
˜
x
n
|
˜
x
n
= (
x
1
, . . . , x
n
)
, x
i
∈ {
0
,
1
}
è ïðèíèìàþùàÿ çíà÷åíèÿ èç ìíîæåñòâà
{
0
,
1
}
, íàçûâàåòñÿ ôóíêöèåé àë-
ãåáðû ëîãèêè èëè áóëåâîé ôóíêöèåé.
Î÷åâèäíî, ÷òî äëÿ çàäàíèÿ ôóíêöèè
f
(˜
x
n
)
äîñòàòî÷íî óêàçàòü, êàêîå
çíà÷åíèå ïðèíèìàåò ôóíêöèÿ ïðè êàæäîì èç íàáîðîâ çíà÷åíèé àðãóìåí-
òîâ, òî åñòü âûïèñàòü òàáëèöó:
x
1
,
x
2
, . . . ,
x
n
−
1
,
x
n
f
(
x
1
, x
2
, . . . , x
n
−
1
, x
n
)
0 0
. . .
0 0
f
(0
,
0
, . . .
0
,
0)
0 0
. . .
0 1
f
(0
,
0
, . . .
0
,
1)
0 0
. . .
1 1
f
(0
,
0
, . . .
1
,
1)
. . .
. . .
1 1
. . .
1 1
f
(1
,
1
, . . . ,
1
,
1)
Òàáëèöà 2.1
Ëåãêî âèäåòü, ÷òî
n
ïåðåìåííûõ â ñîâîêóïíîñòè ïðèíèìàþò
2
n
ðàçëè÷-
íûõ çíà÷åíèé. Äëÿ óäîáñòâà ìû óïîòðåáëÿåì ñòàíäàðòíîå ðàñïîëîæåíèå
íàáîðîâ çíà÷åíèé ïåðåìåííûõ: åñëè íàáîð ðàññìàòðèâàòü êàê äâîè÷íóþ
54
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
çàïèñü ÷èñëà, òî èõ ðàñïîëîæåíèå ñîîòâåòñòâóåò åñòåñòâåííîìó ðàñïîëîæå-
íèþ ÷èñåë
0
,
1
, . . . ,
2
n
−
1
. Êàæäàÿ ôóíêöèÿ
f
(
x
1
, x
2
, . . . , x
n
)
îïðåäåëÿåò
îòîáðàæåíèå
B
2
×
B
2
. . .
×
B
2
→
B
2
. Ïîýòîìó åñòåñòâåííî èíòåðïðåòèðîâàòü
f
êàê ñèìâîë, îáîçíà÷àþùèé ýòî îòîáðàæåíèå, à
x
1
, x
2
, . . . , x
n
êàê íàçâà-
íèÿ ñòîëáöîâ.  ýòîì ñëó÷àå ôóíêöèè
f
(
x
1
, x
2
, . . . , x
n
)
è
f
(
y
1
, y
2
, . . . , y
n
)
áóäóò çàäàâàòü îäíî è òî æå îòîáðàæåíèå, à èõ òàáëèöû áóäóò îòëè÷àòüñÿ
òîëüêî, áûòü ìîæåò, íàçâàíèÿìè ñòîëáöîâ. Îáîçíà÷èì ÷åðåç
P
2
ìíîæå-
ñòâî âñåõ ôóíêöèé àëãåáðû ëîãèêè íàä àëôàâèòîì
U
, ñîäåðæàùåå òàêæå
è êîíñòàíòû
0
è
1
. Åñëè çàôèêñèðîâàòü
n
ïåðåìåííûõ
x
1
, x
2
, . . . , x
n
, òî
ðàçëè÷íûå òàáëèöû áóäóò îòëè÷àòüñÿ ëèøü çíà÷åíèÿìè â ïðàâîì ñòîëáöå.
Ïîýòîìó ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 2.1. ×èñëî
p
2
(
n
)
âñåõ ôóíêöèé èç
P
2
, çàâèñÿùèõ îò ïåðåìåííûõ
x
1
, x
2
, . . . , x
n
, ðàâíî
2
2
n
.
Çäåñü ñëåäóåò îáðàòèòü âíèìàíèå íà îäíî îáñòîÿòåëüñòâî. ×èñëî ôóíê-
öèé àëãåáðû ëîãèêè, çàâèñÿùèõ îò çàäàííûõ n àðãóìåíòîâ, êîíå÷íî. Ïî-
ýòîìó, åñëè íóæíî âûÿñíèòü, îáëàäàþò ëè ôóíêöèè èç ýòîãî êîíå÷íîãî
ìíîæåñòâà êàêèì-ëèáî ñâîéñòâîì, äîñòàòî÷íî îñóùåñòâèòü ïåðåáîð ôóíê-
öèé èç äàííîãî ìíîæåñòâà. Îäíàêî ÷èñëà
p
2
(
n
)
ñ ðîñòîì
n
áûñòðî ðàñòóò:
p
2
(1) = 4
,
p
2
(2) = 16
,
p
2
(3) = 256
,
p
2
(4) = 65536
,
. . .
Òàêèì îáðàçîì,
óæå ïðè ñðàâíèòåëüíî íåáîëüøèõ çíà÷åíèÿõ
n
(
n
≥
6)
ïåðåáîð ñòàíîâèò-
ñÿ ïðàêòè÷åñêè íåîñóùåñòâèìûì äàæå ñ èñïîëüçîâàíèåì âû÷èñëèòåëüíîé
òåõíèêè. Ñ ðîñòîì ÷èñëà àðãóìåíòîâ n òàáëèöà, çàäàþùàÿ ôóíêöèþ, ñèëü-
íî óñëîæíÿåòñÿ. Òàê ïðè
n
= 64
äëÿ çàïîëíåíèÿ òàêîé òàáëèöû ñî ñêîðî-
ñòüþ
10
9
ñòðîê â ñåêóíäó ïîíàäîáèòñÿ îêîëî
300
ëåò. Ïîýòîìó íåñìîòðÿ
íà ïðîñòîòó òàáëè÷íîãî çàäàíèÿ ôóíêöèé àëãåáðû ëîãèêè, òàêîé èíñòðó-
ìåíò èññëåäîâàíèÿ ôóíêöèé êðàéíå íåýôôåêòèâåí, åñëè íå áåñïîëåçåí, ïðè
áîëüøèõ çíà÷åíèÿõ
n
. Íåîáõîäèìîñòü ðàçðàáîòêè àíàëèòè÷åñêîãî çàäàíèÿ
è ìåòîäîâ èññëåäîâàíèÿ ôóíêöèé àëãåáðû ëîãèêè î÷åâèäíà.
Îïðåäåëåíèå. Ïåðåìåííàÿ
x
i
(1
≤
i
≤
n
)
ôóíêöèè
f
(
x
1
, x
2
, . . . , x
i
−
1
, x
i
, x
i
+1
, . . . , x
n
)
èç
P
2
íàçûâàåòñÿ ñóùåñòâåííîé,
åñëè ìîæíî óêàçàòü òàêèå íàáîðû
˜
α
= (
α
1
, . . . , α
i
−
1
,
0
, α
i
+1
, . . . , α
n
)
è
˜
β
= (
α
1
, . . . , α
i
−
1
,
1
, α
i
+1
, . . . , α
n
)
çíà÷åíèé ïåðåìåííûõ, ÷òî
f
( ˜
α
)
6
=
f
( ˜
β
)
.  ïðîòèâíîì ñëó÷àå ïåðåìåí-
íóþ
x
i
íàçûâàþò íåñóùåñòâåííîé èëè ôèêòèâíîé ïåðåìåííîé ôóíêöèè
f
(
x
1
, x
2
, . . . , x
i
−
1
, x
i
, x
i
+1
, . . . , x
n
)
.
2.2. ÝËÅÌÅÍÒÀÐÍÛÅ ËÎÃÈ×ÅÑÊÈÅ ÎÏÅÐÀÖÈÈ(ÔÓÍÊÖÈÈ)
55
Îïðåäåëåíèå. Äâå ôóíêöèè
f
(˜
x
n
)
è
g
(˜
y
n
)
íàçûâàþòñÿ ðàâíûìè, åñ-
ëè ìíîæåñòâà èõ ñóùåñòâåííûõ ïåðåìåííûõ ñîâïàäàþò è íà ëþáûõ äâóõ
íàáîðàõ
˜
α
n
è
˜
β
n
, ðàçëè÷àþùèõñÿ áûòü ìîæåò òîëüêî çíà÷åíèÿìè íåñóùå-
ñòâåííûõ ïåðåìåííûõ, çíà÷åíèÿ ôóíêöèé îäèíàêîâû:
f
( ˜
α
n
) =
g
( ˜
β
n
)
. Åñëè
f
(˜
x
n
)
è
g
(˜
y
n
)
ðàâíûå ôóíêöèè, òî îäíó èç íèõ ìîæíî ïîëó÷èòü èç äðóãîé
ïóòåì äîáàâëåíèÿ è/èëè èçúÿòèÿ íåñóùåñòâåííûõ ïåðåìåííûõ.
Ïîñòðîåíèå àíàëèòè÷åñêîé òåîðèè ôóíêöèé àëãåáðû ëîãèêè íà÷íåì ñ
ýëåìåíòàðíûõ ôóíêöèé (îïåðàöèé).
Äàííûå îïåðàöèè (ôóíêöèè) ÷àñòî óïîòðåáëÿþòñÿ â ìàòåìàòè÷åñêîé
ëîãèêå è êèáåðíåòèêå è èãðàþò òàêóþ æå ðîëü, êàê, íàïðèìåð,
x
+
y
â
àðèôìåòèêå,
x
2
â àëãåáðå,
sin
x
è
exp
x
â àíàëèçå, ïîýòîìó èõ ìîæíî ñ÷è-
òàòü ýëåìåíòàðíûìè ôóíêöèÿìè.
Îïðåäåëèì ëîãè÷åñêèå èëè áóëåâñêèå îïåðàöèè (ôóíêöèè) íàä ýëåìåí-
òàðíûìè âûñêàçûâàíèÿìè èëè ëîãè÷åñêèìè (áóëåâñêèìè) ïåðåìåííûìè.
1. Êîíñòàíòû (íóëüìåñòíûå îïåðàöèè):
0 òîæäåñòâåííûé íóëü (òîæäåñòâåííàÿ ëîæü),
1 òîæäåñòâåííàÿ åäèíèöà (òîæäåñòâåííàÿ èñòèíà).
2. Îïåðàöèè íàä îäíîé ïåðåìåííîé (îäíîìåñòíûå, óíàðíûå îïåðàöèè):
îòðèöàíèå, îáîçíà÷àåòñÿ êàê
¯
x
èëè
e
x
, ÷èòàåòñÿ ¾íå x¿ èëè ¾îòðèöà-
íèå
x
¿. Ýòó îïåðàöèþ ìîæíî çàäàòü ñëåäóþùåé òàáëèöåé, â êîòîðîé
óêàçàíî, êàêîå çíà÷åíèå ôóíêöèè (îïåðàöèè) ñîîòâåòñòâóåò êàæäîìó
èç çíà÷åíèé ïåðåìåííîé
x
:
x
e
x
0
1
1
0
3. Îïåðàöèè íàä äâóìÿ ïåðåìåííûìè (äâóõìåñòíûå, áèíàðíûå îïåðà-
öèè)
x
y
x
∧
y
x
∨
y
x
→
y
x
≡
y
x
+
y
x
|
y
x
↓
y
0 0
0
0
1
1
0
1
1
0 1
0
1
1
0
1
1
0
1 0
0
1
0
0
1
1
0
1 1
1
1
1
1
0
0
0
Ïðèâåäåì íàçâàíèÿ è äðóãèå îáîçíà÷åíèÿ ïåðå÷èñëåííûõ â òàáëèöå
ôóíêöèé.