Лекции - Математическая логика
Подождите немного. Документ загружается.
91
Íåïðîòèâîðå÷èâîñòü ÿâëÿåòñÿ îäíèì èç ñàìûõ âàæíûõ óñëî-
âèé, êîòîðûì äîëæíà óäîâëåòâîðÿòü ëîãè÷åñêàÿ ñèñòåìà. Çíà÷åíèå
ýòîãî óñëîâèÿ ïîÿñíÿåò ñëåäóþùàÿ òåîðåìà.
ÒÅÎÐÅÌÀ (êðèòåðèé ïðîòèâîðå÷èâîñòè ñèñòåìû). Ïóñòü N –
ïðîèçâîëüíàÿ ñèñòåìà åñòåñòâåííîãî âûâîäà, ñðåäè ïðàâèë êîòî-
ðîé åñòü ïðàâèëî ¬ó. Ñèñòåìà N ÿâëÿåòñÿ ïðîòèâîðå÷èâîé òîãäà è
òîëüêî òîãäà, êîãäà ëþáàÿ ôîðìóëà N-âûâîäèìà.
Äîêàçàòåëüñòâî. Åñëè ëþáàÿ ôîðìóëà N-âûâîäèìà, òî,
î÷åâèäíî, ÷òî ñèñòåìà N ïðîòèâîðå÷èâà.
Äîïóñòèì òåïåðü, ÷òî ñèñòåìà N, ñîäåðæàùàÿ ïðàâèëî ¬ó ñðå-
äè èñõîäíûõ, ïðîòèâîðå÷èâà, è ïóñòü ôîðìóëà F òàêàÿ, ÷òî
N
F è
N
¬F, à
F
D
∅
è
F
¬
D
∅
– ñîîòâåòñòâóþùèå äåðåâüÿ N-âûâîäà. Òîãäà
äëÿ ëþáîé ôîðìóëû B äåðåâî
FF
B
¬
DD
∅∅
, ïîñòðîåííîå ïî ïðàâèëó
¬ó, ÿâëÿåòñÿ äåðåâîì N-âûâîäà ôîðìóëû Â ñ ïóñòûì ìíîæåñòâîì
çåëåíûõ ëèñòüåâ, ò. å.
N
Â. Ñëåäîâàòåëüíî, åñëè N – ïðîòèâîðå÷è-
âàÿ ñèñòåìà ñ ïðàâèëîì ¬ó, òî â íåé âûâîäèìà ëþáàÿ ôîðìóëà.
Òàêèì îáðàçîì, ïðîòèâîðå÷èâûå ñèñòåìû, èìåþùèå ïðàâèëî
¬ó, íå ïðåäñòàâëÿþò ñîáîé íèêàêîãî èíòåðåñà, ïîñêîëüêó â íèõ
âûâîäèìû âñå ôîðìóëû.
Ñðàçó âîçíèêàåò âîïðîñ: ÿâëÿþòñÿ ëè íåïðîòèâîðå÷èâûìè ñè-
ñòåìû N
i
è N
k
?
Ïðåæäå ÷åì áóäåò ïîëó÷åí îòâåò íà ýòîò âîïðîñ, âûÿñíèì:
Êàêîâà ñâÿçü ìåæäó îòíîøåíèÿìè N
i
- è N
k
-âûâîäèìîñòè, ñ
îäíîé ñòîðîíû, è îòíîøåíèåì ñåìàíòè÷åñêîãî ñëåäîâàíèÿ, ñ äðó-
ãîé?
Êàê ñâÿçàíû êëàññû N
i
- è N
k
-âûâîäèìûõ ôîðìóë ñ êëàññîì
òàâòîëîãèé?
Ñíà÷àëà äîêàæåì ñëåäóþùóþ òåîðåìó.
! ÒÅÎÐÅÌÀ (î ñîãëàñîâàííîñòè îòíîøåíèÿ N
c
-âûâîäèìîñòè
N
c
ñ îòíîøåíèåì ñåìàíòè÷åñêîãî ñëåäîâàíèÿ
). Îòíîøåíèå N
c
-âû-
âîäèìîñòè ñîãëàñîâàíî ñ îòíîøåíèåì ñåìàíòè÷åñêîãî ñëåäîâàíèÿ,
ò. å. êàêîâû áû íè áûëè ìíîæåñòâî ôîðìóë Ã è ôîðìóëà F, åñëè F
N
c
-âûâîäèìà èç Ã, òî F ñåìàíòè÷åñêè ñëåäóåò èç Ã.
Ñèìâîëè÷åñêè ýòî óòâåðæäåíèå ìîæíî çàïèñàòü òàê:
(Ã) (F) (Ã
N
c
F → Ã
F).
92
Äîêàçàòåëüñòâî. Âîñïîëüçóåìñÿ ïðèíöèïîì èíäóêöèè
äëÿ N
c
-âûâîäîâ (âî âòîðîé ôîðìå).
Âî-ïåðâûõ, îòíîøåíèå ñåìàíòè÷åñêîãî ñëåäîâàíèÿ
ðåôëåê-
ñèâíî è ìîíîòîííî. Âî-âòîðûõ, âñå N
c
-ïðàâèëà ñîõðàíÿþò îòíî-
øåíèå ñåìàíòè÷åñêîãî ñëåäîâàíèÿ, ÷òî íåïîñðåäñòâåííî îòðàæåíî
â èçâåñòíûõ ñâîéñòâàõ ñåìàíòè÷åñêîãî ñëåäîâàíèÿ (§ 1.6). Òàêèì
îáðàçîì, ñîãëàñíî ïðèíöèïó èíäóêöèè äëÿ N
c
-âûâîäîâ âî âòîðîé
ôîðìå, îòíîøåíèå N
c
-âûâîäèìîñòè ñîãëàñîâàíî ñ îòíîøåíèåì
ñåìàíòè÷åñêîãî ñëåäîâàíèÿ.
!
Ñèñòåìó åñòåñòâåííîãî âûâîäà N íàçûâàþò ñåìàíòè÷åñêè êîð-
ðåêòíîé ñèñòåìîé, åñëè âñÿêàÿ N-âûâîäèìàÿ ôîðìóëà ÿâëÿåò-
ñÿ òàâòîëîãèåé, ò. å. åñëè (F) (
N
F →
F).
! ÒÅÎÐÅÌÀ (î ñåìàíòè÷åñêîé êîððåêòíîñòè ñèñòåì N
i
è N
k
).
Âñÿêàÿ N
c
-âûâîäèìàÿ ôîðìóëà ÿâëÿåòñÿ òàâòîëîãèåé, ò. å.
(F) (
N
c
F →
F).
Äîêàçàòåëüñòâî. Ðàññìàòðèâàåìîå óòâåðæäåíèå ïîëó÷àåò-
ñÿ èç òåîðåìû î ñîãëàñîâàííîñòè îòíîøåíèÿ N
c
-âûâîäèìîñòè ñ îò-
íîøåíèåì ñåìàíòè÷åñêîãî ñëåäîâàíèÿ ïðè ïóñòîì ìíîæåñòâå Ã.
 äàëüíåéøåì òåîðåìó î ñåìàíòè÷åñêîé êîððåêòíîñòè ñèñòåì
N
i
è N
k
áóäåì òàêæå íàçûâàòü òåîðåìîé î ñîãëàñîâàííîñòè ñèñòåì
N
i
è N
k
ñ êëàññîì òàâòîëîãèé.
! ÒÅÎÐÅÌÀ (î íåïðîòèâîðå÷èâîñòè ñèñòåì N
i
è N
k
). Ñèñòåìû N
i
è N
k
íåïðîòèâîðå÷èâû.
Äîêàçàòåëüñòâî. Âîñïîëüçóåìñÿ ìåòîäîì äîêàçàòåëüñòâà
ïðèâåäåíèåì ê íåëåïîñòè. Ïðåäïîëîæèì, ÷òî N
c
– êàêàÿ-ëèáî èç
ñèñòåì N
i
èëè N
k
, ïðîòèâîðå÷èâà, è ïóñòü ôîðìóëà F òàêàÿ, ÷òî
N
c
F è
N
c
¬F. Òîãäà, ïî òåîðåìå î ñåìàíòè÷åñêîé êîððåêòíîñòè
ñèñòåì N
i
è N
k
, îáå ôîðìóëû F è ¬F ÿâëÿþòñÿ òàâòîëîãèÿìè, ò. å.
F è
¬F, ÷òî íåâîçìîæíî. Ñëåäîâàòåëüíî, îáå ñèñòåìû N
i
è N
k
íåïðîòèâîðå÷èâû.
Ïðè âûÿñíåíèè òîãî, êàê ñîîòíîñèòñÿ êëàññ òàâ-
òîëîãèé ñ êëàññàìè N
i
- è N
k
-âûâîäèìûõ ôîð-
ìóë, áûëî óñòàíîâëåíî, ÷òî äëÿ êàæäîé èç ýòèõ
ñèñòåì âñÿêàÿ âûâîäèìàÿ â íåé ôîðìóëà ÿâëÿåò-
Семантическая
полнота
классической
системы N
k
93
ñÿ òàâòîëîãèåé. Âåðíû ëè îáðàòíûå óòâåðæäåíèÿ: âñÿêàÿ ëè òàâòî-
ëîãèÿ âûâîäèìà â N
i
? â N
k
? Äðóãèìè ñëîâàìè, äîñòàòî÷íî ëè ïîë-
íû ñïèñêè N
i
- è N
k
-ïðàâèë äëÿ òîãî, ÷òîáû äëÿ âñÿêîé òàâòîëîãèè
ìîæíî áûëî ïîñòðîèòü äåðåâî åå âûâîäà â ñèñòåìàõ N
i
è N
k
?
Îêàçûâàåòñÿ, ÷òî îòâåòû íà ýòè âîïðîñû äëÿ ñèñòåì N
i
è N
k
ðàçíûå: äëÿ N
k
– ïîëîæèòåëüíûé, à äëÿ N
i
– îòðèöàòåëüíûé.
!
Ñèñòåìó åñòåñòâåííîãî âûâîäà N íàçûâàþò ñåìàíòè÷åñêè ïîë-
íîé (èëè ïîëíîé îòíîñèòåëüíî êëàññà òàâòîëîãèé), åñëè âñÿêàÿ
òàâòîëîãèÿ N-âûâîäèìà, ò. å. åñëè (F) (F →
N
F).
Äîêàæåì, ÷òî ñèñòåìà N
k
ïîëíà îòíîñèòåëüíî êëàññà òàâòîëî-
ãèé. Äëÿ ýòîãî ñíà÷àëà äîêàæåì âñïîìîãàòåëüíîå óòâåðæäåíèå,
êîòîðîå èãðàåò îñíîâíóþ ðîëü â äîêàçàòåëüñòâå òåîðåìû î ïîëíîòå
ñèñòåìû N
k
.
Áóäåì èñïîëüçîâàòü ñëåäóþùèå îáîçíà÷åíèÿ: À
È
À, À
Ë
¬À,
ãäå À – ïðîèçâîëüíàÿ ôîðìóëà.
! ËÅÌÌÀ 1 (îñíîâíàÿ). Êàêîâû áû íè áûëè ôîðìóëà F, åå äîïóñòè-
ìûé ñïèñîê ω = (
1
i
p
, ...,
n
i
p
) è èñòèííîñòíûé íàáîð α = (α
1
, …, α
n
),
1
1
α
α
, ...,
pp
n
n
ii
N
c
ω
α
||
F
F
.
Äîêàçàòåëüñòâî. Âîñïîëüçóåìñÿ ïðèíöèïîì èíäóêöèè
ïî ïîñòðîåíèþ ôîðìóëû (§ 1.2).
Áàçèñ èíäóêöèè. Ïóñòü ôîðìóëà F åñòü ïðîïîçèöèîíàëüíàÿ ïå-
ðåìåííàÿ, à ω = (
1
i
p
, …,
n
i
p
) – ïðîèçâîëüíûé åå äîïóñòèìûé ñïè-
ñîê. Ýòî îçíà÷àåò, ÷òî F
k
i
p
äëÿ íåêîòîðîãî k (k = 1, …, n). Åñëè
α – ïðîèçâîëüíûé èñòèííîñòíûé íàáîð äëèíû n, òî
ω
α
||
F
= α
k
è
ω
α
||
F
F
=
α
k
k
i
p
. Òîãäà, â ñèëó ðåôëåêñèâíîñòè è ìîíîòîííîñòè îòíî-
øåíèÿ N
c
-âûâîäèìîñòè,
1
1
αα
α
, ..., , ...,
ppp
kn
kn
ii i
N
c
α
p
k
k
i
.
Øàã èíäóêöèè. Äîïóñòèì, ÷òî äëÿ ëþáîãî äîïóñòèìîãî ñïèñêà
ω = (
1
i
p
, ...,
n
i
p
) ôîðìóë À è Â è ëþáîãî èñòèííîñòíîãî íàáîðà
α = (α
1
, …, α
n
) âûïîëíÿåòñÿ
1
1
αα
, ...,
pp
n
n
ii
N
c
ω
||
A
A
α
è
1
1
αα
, ...,
pp
n
n
ii
N
c
ω
||
B
B
α
94
(ïðåäïîëîæåíèå èíäóêöèè). Äîêàæåì, ÷òî ñîîòâåòñòâóþùèå óòâåðæ-
äåíèÿ âåðíû äëÿ ôîðìóë À & Â, À ∨ Â, À ⊃ Â, ¬À.
I. Ñíà÷àëà ïðîâåäåì äîêàçàòåëüñòâî äëÿ ôîðìóëû À ⊃ Â.
Ïóñòü ω = (
1
i
p
,…,
n
i
p
) – ïðîèçâîëüíûé äîïóñòèìûé ñïèñîê
ôîðìóëû À ⊃ Â, à α = (α
1
, …, α
n
) – ïðîèçâîëüíûé èñòèííîñòíûé
íàáîð äëèíû n. Î÷åâèäíî, ω ÿâëÿåòñÿ äîïóñòèìûì ñïèñêîì êàê
ôîðìóëû À, òàê è ôîðìóëû Â. Òîãäà ïî ïðåäïîëîæåíèþ èíäóêöèè
èìååì: Ã
N
c
ω
α
||
A
A
è Ã
N
c
ω
α
||
B
B
, ãäå Ã {
1
1
α
α
,...,
n
n
ii
pp
}. Äîêàæåì,
÷òî Ã
N
c
ω
α
||
()
ÀB
AB
⊃
⊃
. Â ñèëó òðàíçèòèâíîñòè îòíîøåíèÿ
N
c
äî-
ñòàòî÷íî äîêàçàòü, ÷òî
ω
α
||
A
A
,
ω
α
||
B
B
N
c
ω
α
||
()
ÀB
AB
⊃
⊃
. (1)
Ðàññìîòðèì âñå âîçìîæíûå ñëó÷àè.
1. Äîïóñòèì, ÷òî
ω
α
||⊃AB
= Ë. Òîãäà
ω
α
||
A
= È, à
ω
α
||
B
= Ë.
 ýòîì ñëó÷àå âûâîäèìîñòü (1) èìååò âèä À, ¬Â
N
c
¬(À ⊃ Â). Äî-
êàæåì åå, ïîñòðîèâ ñîîòâåòñòâóþùåå äåðåâî N
c
-âûâîäà:
y
в
1
(1)
[]
()
AA B
Â
B
ÀÂ
⊃
¬
⊃
¬
¬⊃
2. Äîïóñòèì, ÷òî
ω
α
||
AB
⊃
= È. Òîãäà
ω
α
||
A
= Ë èëè
ω
α
||
B
= È.
2.1. Äîïóñòèì, ÷òî
ω
α
||
A
= Ë.  ýòîì ñëó÷àå äîñòàòî÷íî äîêà-
çàòü, ÷òî ¬À
N
c
À ⊃ Â. Äîêàæåì ýòó âûâîäèìîñòü ïîñòðîåíèåì
äåðåâà N
c
-âûâîäà:
в
1
ó
(1)
[]
ÀA
Â
ÀÂ
¬
⊃
¬
⊃
2.2. Äîïóñòèì, ÷òî
ω
α
||
B
= È.  ýòîì ñëó÷àå äîñòàòî÷íî äîêà-
çàòü, ÷òî Â
N
c
À ⊃ Â. Äîêàæåì ýòó âûâîäèìîñòü, ïîñòðîèâ ñîîò-
âåòñòâóþùåå äåðåâî N
c
-âûâîäà:
в
B
ÀÂ
⊃
⊃
95
II. Òåïåðü ðàññìîòðèì ôîðìóëó À & Â. Àíàëîãè÷íî ñëó÷àþ I,
äîñòàòî÷íî äîêàçàòü, ÷òî äëÿ ëþáûõ ω è α
ω
α
||
,
A
A
ω
α
||
B
B
N
c
ω
α
|&|
&
()
ÀB
AB
. (2)
Ðàññìîòðèì âñå âîçìîæíûå ñëó÷àè.
Åñëè
ω
α
|&|
AB
= È, òî äîñòàòî÷íî äîêàçàòü, ÷òî À, Â
N
c
À & Â.
Åñëè
ω
α
||
A
= Ë, òî äîñòàòî÷íî äîêàçàòü, ÷òî ¬À
N
c
¬(À & Â).
Åñëè
ω
α
||
B
= Ë, òî äîñòàòî÷íî äîêàçàòü, ÷òî ¬Â
N
c
¬(À & Â).
Ïåðâûé èç ýòèõ ñëó÷àåâ òðèâèàëåí. Äâà äðóãèõ àíàëîãè÷íû äðóã
äðóãó. Ïîýòîìó ïîñòðîèì ñîîòâåòñòâóþùåå äåðåâî âûâîäà òîëüêî
äëÿ âòîðîãî ñëó÷àÿ:
в
1
&y
(1)
(&)
[&]
ÀÂ
ÀB
A
A
¬
¬
¬
Ðàññìîòðåíèå ñëó÷àåâ ôîðìóë À ∨ Â è ¬À îñòàâëÿåì ÷èòà-
òåëþ.
ËÅÌÌÀ 2. Êàêîâû áû íè áûëè ìíîæåñòâî ôîðìóë Ã, ôîðìóëà F
è ïðîïîçèöèîíàëüíàÿ ïåðåìåííàÿ q, åñëè Ã, q
k
N
F è Ã, ¬q
k
N
F,
òî Ã
k
N
F.
Äîêàçàòåëüñòâî. Äîïóñòèì, ÷òî Ã, q
k
N
F è Ã, ¬q
k
N
F.
Ïóñòü
1
q
F
Δ
è
2
q
F
Δ¬
– íåêîòîðûå ñîîòâåòñòâóþùèå äåðåâüÿ
N
k
-âûâîäà òàêèå, ÷òî Δ
1
⊆ Ã è Δ
2
⊆ Ã. Îáîçíà÷èì ÷åðåç
qq
∨¬
∅
êàêîé-ëèáî N
k
-âûâîä ôîðìóëû q ∨ ¬q ñ ïóñòûì ìíîæåñòâîì
çåëåíûõ ëèñòüåâ, ñóùåñòâîâàíèå êîòîðîãî îáåñïå÷åíî òåì, ÷òî
k
N
q ∨ ¬q. Òîãäà äåðåâî ôîðìóë
11
12
y(1)
[] [ ]
qq
qqF F
F
∨
ΔΔ¬
∅
∨¬
96
– äåðåâî N
k
-âûâîäà ôîðìóëû F, ìíîæåñòâî çåëåíûõ ëèñòüåâ êîòî-
ðîãî Δ
1
∪ Δ
2
ÿâëÿåòñÿ ïîäìíîæåñòâîì Ã. Ñëåäîâàòåëüíî, Ã
k
N
F.
! ÒÅÎÐÅÌÀ (î ïîëíîòå N
k
îòíîñèòåëüíî êëàññà òàâòîëîãèé).
Âñÿêàÿ òàâòîëîãèÿ N
k
-âûâîäèìà:
(F) (F →
k
N
F).
Äîêàçàòåëüñòâî. Ïóñòü F – ïðîèçâîëüíàÿ òàâòîëîãèÿ,
ω = (
1
i
p
, …,
n
i
p
) – ñîáñòâåííûé ñïèñîê ïåðåìåííûõ ôîðìóëû F.
Ïîñêîëüêó F – òàâòîëîãèÿ, òî äëÿ ëþáîãî íàáîðà α = (α
1
, …, α
n
) âåðíî,
÷òî
α
||
F
ω
= È, à çíà÷èò,
ω
α
||
F
F
= F. Ñëåäîâàòåëüíî, ïî îñíîâíîé
ëåììå äëÿ ëþáûõ èñòèííîñòíûõ çíà÷åíèé α
1
, …, α
n
âûïîëíÿåòñÿ
1
1
,...,
n
n
ii
pp
α
α
k
N
F. (1)
Îòñþäà, ïîëàãàÿ ñíà÷àëà α
n
= È, à çàòåì α
n
= Ë, ïîëó÷àåì, ÷òî
äëÿ ëþáûõ α
1
, …, α
n – 1
âûïîëíÿåòñÿ ñîîòâåòñòâåííî:
11
11k
11
11 k
N
N
.
,..., , ;
,..., ,
n
nn
n
nn
iii
iii
F
F
ppp
ppp
−
−
−
−
αα
αα
¬
Ñëåäîâàòåëüíî, ñîãëàñíî ëåììå 2, äëÿ ëþáûõ α
1
, …, α
n–1
1
k
11
N
,...,
ni
n
ii
F
pp
−
−
α
α
. (2)
Îòìåòèì, ÷òî óòâåðæäåíèå (2) ñîäåðæèò íà îäíó ãèïîòåçó ìåíüøå
ïî ñðàâíåíèþ ñ óòâåðæäåíèåì (1).
Ïîâòîðÿÿ àíàëîãè÷íûå ðàññóæäåíèÿ ïîñëåäîâàòåëüíî äëÿ
α
n – 1
, …, α
1
, óäàëÿåì îäíó çà äðóãîé ãèïîòåçû â óòâåðæäåíèè (2). Íà
ïðåäïîñëåäíåì øàãå ïîëó÷àåì: äëÿ ëþáîãî α
1
èìååò ìåñòî âûâîäè-
ìîñòü
1
1
α
N
k
F
p
i
, ò. å.
1
i
p
k
N
F, è ¬
1
i
p
k
N
F. Îòñþäà ïî ëåììå 2,
íàêîíåö, ïîëó÷àåì, ÷òî
k
N
F.
Îáúåäèíÿÿ âìåñòå òåîðåìó î ñîãëàñîâàííîñòè N
k
ñ êëàññîì òàâ-
òîëîãèé è òåîðåìó î ïîëíîòå N
k
îòíîñèòåëüíî êëàññà òàâòîëîãèé,
ïîëó÷àåì â êà÷åñòâå ñëåäñòâèÿ óòâåðæäåíèå, êîòîðîå òàêæå ÷àñòî
íàçûâàþò òåîðåìîé î ïîëíîòå N
k
:
97
!
ÑËÅÄÑÒÂÈÅ 1. Êëàññ N
k
– âûâîäèìûõ ôîðìóë ñîâïàäàåò ñ
êëàññîì òàâòîëîãèé, ò. å. (F) (
k
N
F ↔ F).
Çàìå÷àíèå 1. Àíàëîãè÷íîå óòâåðæäåíèå äëÿ N
i
íåâåðíî. Ïîçæå
áóäóò ïðèâåäåíû ïðèìåðû òàâòîëîãèé, íåâûâîäèìûõ â N
i
(ñì.
§ 2.12). Òàêèì îáðàçîì, ñèñòåìà N
i
íåïîëíà îòíîñèòåëüíî êëàññà
òàâòîëîãèé.
ÑËÅÄÑÒÂÈÅ 2. Îòíîøåíèÿ è
k
N
ñîãëàñîâàíû äðóã ñ äðó-
ãîì, ò. å. (Ã) (F) (Ã
k
N
F ↔ Ã F).
Ïåðåéäåì ê ñëåäóþùåé õàðàêòåðèñòèêå ñèñòåì
åñòåñòâåííîãî âûâîäà.
!
Ñèñòåìó åñòåñòâåííîãî âûâîäà N íàçûâàþò ðàç-
ðåøèìîé ñèñòåìîé, åñëè ñóùåñòâóåò àëãîðèòì, êî-
òîðûé ïî ïðîèçâîëüíîé ôîðìóëå F ïîçâîëÿåò âû-
ÿñíèòü, ÿâëÿåòñÿ ëè îíà N-âûâîäèìîé.
! ÒÅÎÐÅÌÀ. Ñèñòåìà N
k
ðàçðåøèìà.
Äîêàçàòåëüñòâî. Ïîñêîëüêó êëàññ N
k
-âûâîäèìûõ ôîð-
ìóë ñîâïàäàåò ñ êëàññîì òàâòîëîãèé, äëÿ èññëåäîâàíèÿ ôîðìóëû F
íà N
k
-âûâîäèìîñòü äîñòàòî÷íî âûÿñíèòü, ÿâëÿåòñÿ ëè îíà òàâòî-
ëîãèåé. Êëàññ òàâòîëîãèé ðàçðåøèì, òàê êàê ñóùåñòâóåò àëãîðèòì,
êîòîðûé ïî ïðîèçâîëüíîé ôîðìóëå F ïîçâîëÿåò îïðåäåëèòü, ÿâëÿ-
åòñÿ ëè îíà òàâòîëîãèåé. Îäèí èç òàêèõ àëãîðèòìîâ çàêëþ÷àåòñÿ â
ïîñòðîåíèè èñòèííîñòíîé òàáëèöû äëÿ ôîðìóëû F.
S Çàìå÷àíèå 2. Ñóùåñòâóåò òàêæå àëãîðèòì, êîòîðûé ïîçâîëÿåò
ïî ëþáîìó êîíå÷íîìó ìíîæåñòâó ôîðìóë à è ëþáîé ôîðìóëå F
âûÿñíèòü, èìååò ëè ìåñòî âûâîäèìîñòü Ã
k
N
F. Äåéñòâèòåëüíî,
F
1
, …, F
n
k
N
F òîãäà è òîëüêî òîãäà, êîãäà
k
N
F
1
⊃ (F
2
⊃ … (F
n–1
⊃ (F
n
⊃ F)) …).
Ñëåäîâàòåëüíî, ÷òîáû âûÿñíèòü, èìååò ëè ìåñòî âûâîäèìîñòü
F
1
, …, F
n
k
N
F, äîñòàòî÷íî âûÿñíèòü, ÿâëÿåòñÿ ëè òàâòîëîãèåé ôîð-
ìóëà F
1
⊃ (F
2
⊃ … (F
n–1
⊃ (F
n
⊃ F)) ...).
Разрешимость
систем
естественного
вывода
98
S Çàìå÷àíèå 3. Ñèñòåìà N
i
òàêæå ðàçðåøèìà, îäíàêî ðàçðåøàþ-
ùèé åå àëãîðèòì âåñüìà ñëîæåí, è åãî ïîñòðîåíèå âûõîäèò çà ðàì-
êè äàííîãî êóðñà.
Ê îñíîâíûì õàðàêòåðèñòèêàì ñèñòåì åñòåñòâåííîãî âûâîäà
îòíîñÿòñÿ òàêæå äåäóêòèâíàÿ ïîëíîòà è íåçàâèñèìîñòü, êîòîðûå
áóäóò ðàññìîòðåíû â § 2.9 è 2.12.
§ 2.8. Ïðîèçâîäíûå§ 2.8. Ïðîèçâîäíûå
§ 2.8. Ïðîèçâîäíûå§ 2.8. Ïðîèçâîäíûå
§ 2.8. Ïðîèçâîäíûå
è äîïóñòèìûå ïðàâèëàè äîïóñòèìûå ïðàâèëà
è äîïóñòèìûå ïðàâèëàè äîïóñòèìûå ïðàâèëà
è äîïóñòèìûå ïðàâèëà
 äàëüíåéøåì èçëîæåíèè N-ïðàâèëà çàêëþ÷å-
íèÿ áóäåì ïðè íåîáõîäèìîñòè íàçûâàòü îñíîâíûìè èëè èñõîäíûìè
N-ïðàâèëàìè, ÷òîáû îòëè÷àòü èõ îò òàê íàçûâàåìûõ ïðîèçâîäíûõ
N-ïðàâèë.
Ïðè èçó÷åíèè òîé èëè èíîé ñèñòåìû åñòåñòâåííîãî âûâîäà N âîç-
íèêàþò ñëåäóþùèå âîïðîñû: êàê èçìåíèòñÿ êëàññ N-âûâîäèìûõ ôîð-
ìóë, åñëè ê èñõîäíûì ïðàâèëàì äîáàâèòü íîâîå ïðàâèëî; ïðè êàêèõ
óñëîâèÿõ îí ðàñøèðèòñÿ, à ïðè êàêèõ îñòàíåòñÿ ïðåæíèì? Íàïðèìåð,
äîáàâèâ ê ïðàâèëàì ñèñòåìû N
i
íîâîå ïðàâèëî ¬¬ó, ìû ïîëó÷èëè ñè-
ñòåìó N
k
, ïðè ýòîì êëàññ N
k
-âûâîäèìûõ ôîðìóë îêàçûâàåòñÿ øèðå,
÷åì êëàññ N
i
-âûâîäèìûõ ôîðìóë (÷òî áóäåò äîêàçàíî â § 2.12). Â ýòîì
ïàðàãðàôå áóäåò èäòè ðå÷ü î ïðàâèëàõ, äîáàâëåíèå êîòîðûõ ê èñõîä-
íûì N-ïðàâèëàì íå óâåëè÷èâàåò êëàññ âûâîäèìûõ ôîðìóë.
!
Ïóñòü N – ñèñòåìà åñòåñòâåííîãî âûâîäà. Áóäåì íàçûâàòü ïðî-
èçâîäíûì N-ïðàâèëîì âñÿêóþ ñõåìó çàêëþ÷åíèé, ñîõðàíÿþùóþ
îòíîøåíèå N-âûâîäèìîñòè.
Òàêèì îáðàçîì, ïðÿìàÿ ñõåìà
...
n
FF
F
1
ÿâëÿåòñÿ (ïðÿìûì) ïðî-
èçâîäíûì N-ïðàâèëîì òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîãî
ìíîæåñòâà ôîðìóë Ã è ëþáîãî íàáîðà ôîðìóë F
1
, ..., F
n
, F, ñîîò-
âåòñòâóþùåãî ýòîé ñõåìå,
NN
1
N
à ; ...; Ã
Ã
n
FF
F
Ãîâîðÿ îá óñëîâíûõ ïðîèçâîäíûõ ïðàâèëàõ, äëÿ ïðîñòîòû èç-
ëîæåíèÿ îãðàíè÷èìñÿ ñõåìàìè âèäà
][
E
H
G
F
.
99
Óñëîâíàÿ ñõåìà
][
E
H
G
F
ÿâëÿåòñÿ (óñëîâíûì) ïðîèçâîäíûì
N-ïðàâèëîì òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîãî ìíîæåñòâà
ôîðìóë Ã è ëþáûõ ôîðìóë Å, F, G è H, ñîîòâåòñòâóþùèõ ýòîé
ñõåìå,
NN
N
Ã;Ã,
Ã
EHG
F
Îêàçûâàåòñÿ, ãîâîðÿ î ïðîèçâîäíûõ ïðàâèëàõ äëÿ ñèñòåì ñ ïðà-
âèëàìè ⊃ó è ⊃â, ìîæíî îãðàíè÷èòüñÿ òîëüêî ïðÿìûìè ïðàâèëàìè.
ÓÒÂÅÐÆÄÅÍÈÅ (î ñâÿçè ìåæäó êîñâåííûìè è ïðÿìûìè ïðîèç-
âîäíûìè ïðàâèëàìè). Ïóñòü N – ñèñòåìà, ñðåäè èñõîäíûõ ïðàâèë
êîòîðîé åñòü ïðàâèëà ⊃ó è ⊃â. Êîñâåííàÿ ñõåìà
]
[
E
H
G
F
ÿâëÿåòñÿ
ïðîèçâîäíûì N-ïðàâèëîì òîãäà è òîëüêî òîãäà, êîãäà ÿâëÿåòñÿ
ïðîèçâîäíûì N-ïðàâèëîì ñîîòâåòñòâóþùàÿ ïðÿìàÿ ñõåìà
⊃
EH G
F
.
Äîêàçàòåëüñòâî. Ïîñêîëüêó ñðåäè N-ïðàâèë åñòü ïðà-
âèëà ⊃ó è ⊃â, òî Ã, H
N
G òîãäà è òîëüêî òîãäà, êîãäà Ã
N
H ⊃ G.
Ñëåäîâàòåëüíî, óñëîâèÿ
NN
N
Ã;Ã,
Ã
EHG
F
è
NN
N
Ã;Ã
Ã
EHG
F
⊃
,
îçíà÷àþùèå, ÷òî ðàññìàòðèâàåìûå ñõåìû ÿâëÿþòñÿ ïðîèçâîäíû-
ìè, òàêæå ýêâèâàëåíòíû.
ÒÅÎÐÅÌÀ (êðèòåðèé ïðîèçâîäíîñòè ïðàâèëà).
1. Ïðÿìàÿ ñõåìà çàêëþ÷åíèé
...
n
FF
F
1
ÿâëÿåòñÿ ïðîèçâîä-
íûì N-ïðàâèëîì òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîãî íàáîðà
ôîðìóë F
1
, ..., F
n
, F, ñîîòâåòñòâóþùåãî ýòîé ñõåìå, F
1
, ..., F
n
N
F
(
F
1
, …,
F
n
N
F
).
100
2. Åñëè ïðàâèëà ⊃ó è ⊃â ÿâëÿþòñÿ èñõîäíûìè äëÿ N, òî êîñ-
âåííàÿ ñõåìà
][
E
H
G
F
ÿâëÿåòñÿ ïðîèçâîäíûì N-ïðàâèëîì òîãäà è
òîëüêî òîãäà, êîãäà äëÿ ëþáûõ ôîðìóë Å, F, G è H, ñîîòâåòñòâóþ-
ùèõ ýòîé ñõåìå, E, H ⊃ G
N
F (
E
,
H
⊃
G
N
F
).
Äîêàçàòåëüñòâî.
1. Îòíîøåíèå N-âûâîäèìîñòè
N
, êàê èçâåñòíî, ðåôëåêñèâíî,
ìîíîòîííî è òðàíçèòèâíî. Ñëåäîâàòåëüíî, ñîãëàñíî êðèòåðèþ ñî-
õðàíåíèÿ îòíîøåíèÿ ρ (§ 2.6), ñõåìà
...
n
FF
F
1
ñîõðàíÿåò îòíîøåíèå
N
(ò. å. ÿâëÿåòñÿ ïðîèçâîäíûì N-ïðàâèëîì) òîãäà è òîëüêî òîãäà,
êîãäà äëÿ ëþáîãî íàáîðà ôîðìóë F
1
, ..., F
n
, F, ñîîòâåòñòâóþùåãî
ýòîé ñõåìå, F
1
, ..., F
n
N
F.
2. Óòâåðæäåíèå ïóíêòà 2 ñëåäóåò èç óòâåðæäåíèÿ ïóíêòà 1 è
óòâåðæäåíèÿ î ñâÿçè ìåæäó êîñâåííûìè è ïðÿìûìè ïðîèçâîäíû-
ìè ïðàâèëàìè.
Çàìåòèì, ÷òî ïðèâåäåííîå äîêàçàòåëüñòâî âìåñòå ñ äîêàçà-
òåëüñòâîì ïðåäûäóùåãî óòâåðæäåíèÿ ïî÷òè äîñëîâíî ïîâòîðÿþò
äîêàçàòåëüñòâî êðèòåðèÿ ñîõðàíåíèÿ îòíîøåíèÿ ρ (èç § 2.6). Äåëî
â òîì, ÷òî äîêàçàííàÿ òåîðåìà è ïðåäøåñòâóþùåå ïðåäëîæåíèå
íåïîñðåäñòâåííî ñëåäóþò èç êðèòåðèÿ ñîõðàíåíèÿ îòíîøåíèÿ ρ,
ïîñêîëüêó îòíîøåíèå
N
ðåôëåêñèâíî, ìîíîòîííî è òðàíçè-
òèâíî.
Ïðèìåðû.
1. Ñõåìà
∨¬ABB
A
ÿâëÿåòñÿ ïðîèçâîäíûì N
c
-ïðàâèëîì, ïî-
ñêîëüêó À ∨ Â, ¬Â
N
c
À äëÿ ëþáûõ ôîðìóë À è Â, ÷òî íåòðóäíî
äîêàçàòü ïîñòðîåíèåì ñîîòâåòñòâóþùåãî äåðåâà N
c
-âûâîäà.
2. Êîñâåííàÿ ñõåìà
[][ ]¬AA
CC
C
ÿâëÿåòñÿ ïðîèçâîäíûì N
k
-ïðàâèëîì. Äåéñòâèòåëüíî, ïîñêîëüêó
À ⊃ Ñ, ¬À ⊃ Ñ
k
N
Ñ äëÿ ëþáûõ ôîðìóë À è Ñ, ÷òî íåòðóäíî