Лекции - Математическая логика
Подождите немного. Документ загружается.
71
Òàê êàê ìíîæåñòâî Δ ∪ Δ
2
⊆ Ã, òî ìíîæåñòâî çåëåíûõ ëèñòüåâ
ýòîãî äåðåâà ÿâëÿåòñÿ ïîäìíîæåñòâîì Ã. Òàêèì îáðàçîì, Ã
N
c
F.
Ñâîéñòâî 4' ÿâëÿåòñÿ ñëåäñòâèåì ñâîéñòâà 4, ïîñêîëüêó åñëè
N
c
À, òî Ã
N
c
À äëÿ ëþáîãî ìíîæåñòâà ôîðìóë Ã.
5. Äîêàçàòåëüñòâî ñâîéñòâà 5 îñòàâëÿåì ÷èòàòåëþ. Çàìåòèì ëèøü,
÷òî ïðè åãî äîêàçàòåëüñòâå íóæíî âîñïîëüçîâàòüñÿ ïðèíöèïîì
èíäóêöèè äëÿ N
c
-âûâîäîâ âî âòîðîé ôîðìå (ñì. § 2.6). Ñâîéñòâî 5'
ïîëó÷àåòñÿ èç ñâîéñòâà 5 ïðè ïóñòîì ìíîæåñòâå Ã.
Ðàññìîòðèì åùå ðÿä ñâîéñòâ îòíîøåíèÿ N
c
-âûâîäèìîñòè.
! ÓÒÂÅÐÆÄÅÍÈÅ (ñâîéñòâà îòíîøåíèÿ N
c
-âûâîäèìîñòè, ñâÿ-
çàííûå ñ ââåäåíèåì è óäàëåíèåì ïðîïîçèöèîíàëüíûõ ñâÿçîê). Äëÿ
ëþáûõ ôîðìóë A, B, Ñ è ëþáîãî ìíîæåñòâà ôîðìóë Ã:
1)
NN
N
cc
c
ÃèÃ
Ã&
ÀÂ
ÀB
; 2)
N
NN
c
cc
Ã&
ÃèÃ
ÀB
ÀÂ
;
3)
NN
N
cc
c
ÃèëèÃ
Ã
ÀÂ
ÀB
∨
; 4)
NN
N
cc
c
Ã, è Ã,
Ã,
ÀÑ ÂÑ
ÀÂ Ñ
∨
;
5)
N
N
c
c
Ã,
Ã
ÀÂ
ÀB
⊃
; 6)
NN
N
cc
c
ÃèÃ
Ã
ÀÀÂ
Â
⊃
;
7)
NN
N
cc
c
Ã, è Ã,
Ã
ÀÂ À Â
À
¬
¬
; 8)
NN
N
cc
c
ÃèÃ
Ã
ÀÀ
B
¬
.
Êðîìå òîãî, òîëüêî äëÿ ñèñòåìû N
k
âåðíî:
9)
k
k
N
N
Ã
Ã
À
À
¬¬
.
Çàìå÷àíèå 2. Ãîðèçîíòàëüíàÿ ÷åðòà çäåñü ÿâëÿåòñÿ ìåòàñèìâî-
ëîì è èñïîëüçóåòñÿ äëÿ ñîêðàùåíèÿ çàïèñè óñëîâíîãî óòâåðæäå-
íèÿ â îòëè÷èå îò ãîðèçîíòàëüíîé ÷åðòû, èñïîëüçóåìîé ïðè çàïèñè
ïðàâèë çàêëþ÷åíèÿ èëè äåðåâüåâ âûâîäà è ÿâëÿþùåéñÿ ÷àñòüþ ýòèõ
ãðàôè÷åñêèõ îáúåêòîâ.
Äîêàæåì íàèáîëåå èçâåñòíîå èç ýòèõ ñâîéñòâ – ñâîéñòâî 5,
êîòîðîå îáû÷íî íàçûâàþò òåîðåìîé äåäóêöèè (î äåäóêöèè).
72
! ÒÅÎÐÅÌÀ (î äåäóêöèè). Åñëè Ã, À
N
c
B, òî Ã
N
c
A ⊃ B.
Äîêàçàòåëüñòâî. Ïóñòü Ã, À
N
c
B. Îáîçíà÷èì ÷åðåç
B
Δ
– äåðåâî N
c
-Δ-Â-âûâîäà òàêîå, ÷òî Δ ⊆ Ã ∪ {A}. Äîêàæåì, ÷òî
Ã
N
c
A ⊃ B. Ïîñòðîèì íîâîå äåðåâî âûâîäà:
â
B
AB
⊃
Δ
⊃
Ìíîæåñòâî åãî çåëåíûõ ëèñòüåâ åñòü ìíîæåñòâî Δ \ {A}. Ïî-
ñêîëüêó Δ \ {A} ⊆ Ã, òî Ã
N
c
A ⊃ B.
Çàìå÷àíèå 3. Îáðàòíîå óòâåðæäåíèå òàêæå ñïðàâåäëèâî: åñëè
Ã
N
c
A ⊃ B, òî Ã, À
N
c
B.
Ëåãêî äîêàçàòü ñëåäóþùèå ïîëåçíûå óòâåðæäåíèÿ (A, B, Ñ –
ïðîèçâîëüíûå ôîðìóëû; à – ïðîèçâîëüíîå êîíå÷íîå ìíîæåñòâî
ôîðìóë):
1) Ã
N
c
À & Â ↔ Ã
N
c
À è Ã
N
c
Â;
2) Ã, À ∨ Â
N
c
Ñ ↔ Ã, À
N
c
Ñ è Ã, Â
N
c
Ñ;
3) Ã
N
c
A ⊃ B ↔ Ã, À
N
c
B;
4) Ã, À & Â
N
c
Ñ ↔ Ã, À, Â
N
c
Ñ;
5) Ã
K
N
¬¬À ↔ Ã
K
N
À.
Íàïîìíèì ââåäåííîå ðàíåå îáîçíà÷åíèå ñâÿçêè
~
, íàçûâàåìîé
ýêâèâàëåíöèåé:
À
~
 (À ⊃ Â) & ( ⊃ À).
Áóäåì ãîâîðèòü, ÷òî ôîðìóëà À N
c
-ýêâèâàëåíòíà ôîðìóëå Â,
åñëè
N
c
À
~
Â.
Ëåãêî äîêàçàòü, ÷òî îòíîøåíèå N
c
-ýêâèâàëåíòíîñòè ðåôëåê-
ñèâíî, òðàíçèòèâíî è ñèììåòðè÷íî, ò. å. ÿâëÿåòñÿ îòíîøåíèåì ýê-
âèâàëåíòíîñòè íà ìíîæåñòâå âñåõ ôîðìóë ßËÂ.
ÒÅÎÐÅÌÀ (îá ýêâèâàëåíòíîé çàìåíå). Åñëè â ôîðìóëå F êàêîå-
ëèáî âõîæäåíèå â íåå ïîäôîðìóëû À çàìåíèòü âõîæäåíèåì ôîðìó-
73
ëû Â, N
c
-ýêâèâàëåíòíîé À, òî ïîëó÷èì ôîðìóëó, N
c
-ýêâèâàëåíò-
íóþ èñõîäíîé ôîðìóëå F.
Äîêàçàòåëüñòâî. Äîñòàòî÷íî äîêàçàòü ñëåäóþùåå áîëåå
ñèëüíîå óòâåðæäåíèå. Ïóñòü À, Â, F – ôîðìóëû, ïðè÷åì äëÿ íåêî-
òîðûõ ñëîâ Õ è Y â àëôàâèòå ßË F
XAY (ò. å. À – ïîäôîðìóëà
ôîðìóëû F). Òîãäà À
~
Â
N
c
XAY
~
XBY.
Òåïåðü íàìåòèì ýòàïû äîêàçàòåëüñòâà ýòîãî óòâåðæäåíèÿ. Ïðåæ-
äå âñåãî íåîáõîäèìî äîêàçàòü ðÿä óòâåðæäåíèé, îáúåäèíåííûõ â
ñëåäóþùåé ëåììå.
ËÅÌÌÀ. Êàêîâû áû íè áûëè ôîðìóëû À, À
1
, Â, Â
1
, äëÿ ñèñòåì
N
i
è N
k
, èìååò ìåñòî:
1) À
~
À
1
N
c
À & Â
~
À
1
& Â ; 2) Â
~
Â
1
N
c
À & Â
~
À & Â
1
;
3) À
~
À
1
N
c
À ∨ Â
~
À
1
∨ Â ; 4) Â
~
Â
1
N
c
À ∨ Â
~
À ∨ Â
1
;
5) À
~
À
1
N
c
À ⊃ Â
~
À
1
⊃ Â ; 6) Â
~
Â
1
N
c
À ⊃ Â
~
À ⊃ Â
1
;
7) À
~
À
1
N
c
¬À
~
¬À
1
.
Ýòè óòâåðæäåíèÿ ìîæíî äîêàçàòü ïîñòðîåíèåì äåðåâüåâ âûâî-
äà, ÷òî ÷èòàòåëü ìîæåò ïðîäåëàòü â êà÷åñòâå óïðàæíåíèÿ.
Äàëåå ñ ïîìîùüþ ïðèíöèïà èíäóêöèè äëÿ ôîðìóë ßË íå-
ñëîæíî çàâåðøèòü äîêàçàòåëüñòâî òåîðåìû, ÷òî òàêæå ïðåäîñòàâ-
ëÿåòñÿ ÷èòàòåëþ.
Ðàññìîòðèì åùå ðÿä âàæíûõ ïðèìåðîâ äåðå-
âüåâ âûâîäà íåêîòîðûõ èçâåñòíûõ ôîðìóë.
Ñíà÷àëà ðàññìîòðèì äåðåâüÿ âûâîäà ôîð-
ìóë, íàçûâàåìûõ çàêîíàìè äå Ìîðãàíà. Ïåðâûå òðè èç íèõ âû-
âîäèìû â èíòóèöèîíèñòñêîé ñèñòåìå (à çíà÷èò, è â êëàññè÷åñ-
êîé). Ïîñëåäíÿÿ ôîðìóëà âûâîäèìà òîëüêî â êëàññè÷åñêîé ñèñ-
òåìå.
1.
N
c
¬(À ∨ Â) ⊃ ¬À & ¬Â.
(1)
23
11
(2) (3)
â
[] []
[( )] [( )]
&
() &
AB
AB AB
AB AB
AB
AB
AB A B
⊃
∨∨
¬∨ ¬∨
¬¬
¬¬
¬∨ ⊃¬ ¬
Примеры
деревьев вывода
74
2.
N
c
¬À & ¬Â ⊃ ¬(À ∨ Â).
(2)
(1)
(3)
1
3
1
23
[&]
[]
[&]
[][]
()
&()
AB
B
B
A
AB
AB A
AA
AB
AB AB
¬¬
¬
¬¬
∨
¬
¬∨
¬¬⊃¬∨
3.
N
c
(¬À ∨ ¬Â) ⊃ ¬(À & Â).
(3) (3)
(2)
(1)
33
22
1
[&] [&]
[] []
(&) (&)
[]
(&)
()(&)
AB AB
AB
AB
AB AB
AB
AB
AB AB
¬¬
¬¬
¬∨¬
¬
¬∨¬ ⊃¬
4.
K
N
¬(À & Â) ⊃ (¬À ∨ ¬Â).
(3)
(2)
(1)
4
3
2
2
(4)
1
[]
[]
[( )]
[( )]
[( & )]
&
()
(&) ( )
B
A
AB
AB
AB
AB
AB
AB
AB
AB
AB
AB
AB A B
¬
¬
¬∨¬
¬¬ ∨¬
¬∨¬
¬¬ ∨¬
¬¬ ¬¬
¬
¬¬ ¬ ∨ ¬
¬∨¬
¬⊃¬∨¬
Òåïåðü ðàññìîòðèì äåðåâüÿ âûâîäà ôîðìóë, íàçûâàåìûõ çàêî-
íàìè äèñòðèáóòèâíîñòè. Âñå ÷åòûðå ôîðìóëû âûâîäèìû â èíòóè-
öèîíèñòñêîé ñèñòåìå (à çíà÷èò, è â êëàññè÷åñêîé).
5.
N
c
((À & Â) ∨ (À & Ñ)) ⊃ À & (Â ∨ Ñ).
(2)
(1)
22
22
1
[&] [&]
[&] [&]
[& &] &( ) &( )
&( )
(& &) &( )
AB AC
AB AC
BC
ABC ABC
ABAC A BC A BC
ABC
ABAC A BC
∨∨
∨∨∨
∨
∨⊃∨
75
6.
N
c
À & (Â ∨ Ñ) ⊃ ((À & Â) ∨ (À & Ñ)).
11
(2)
(1)
22
1
[&( )] [&( )]
[] []
[&( )]
&&
&& &&
&&
&( ) ( & & )
ABC ABC
AA
BC
ABC
AB AC
BC ABAC ABAC
ABAC
ABC ABAC
∨∨
∨
∨∨ ∨
∨
∨⊃ ∨
7.
N
c
(À ∨ (Â & C)) ⊃ (À ∨ Â) & (À ∨ Ñ).
23
2
3
11
(2) (3)
(1)
[&] [&]
[]
[]
[&] [&]
()&()
(&)()&()
BC BC
A
A
BC
ABC ABC
AB
AB AC AC
AB AC
AB AC
ABC AB AC
∨∨
∨
∨∨∨
∨∨
∨∨
∨⊃∨ ∨
8.
N
c
(À ∨ Â) & (À ∨ Ñ) ⊃ (À ∨ (Â & C)).
23
1
3
1
2
(3)
(2)
(1)
[][]
[( ) & ( )]
[]
&
[( ) & ( )]
[]
&&
&&
&
()&()( &)
BC
AB AC
A
BC
AB AC
A
AC AB CA B C
AB AB C ABC
ABC
AB AC AB C
∨∨
∨∨
∨∨∨
∨∨ ∨
∨
∨∨⊃∨
Ðàññìîòðèì äåðåâüÿ âûâîäà ôîðìóë, âûðàæàþùèõ ñâÿçü ìåæäó
èìïëèêàöèåé, ñ îäíîé ñòîðîíû, è äèçúþíêöèåé è îòðèöàíèåì – ñ
äðóãîé. Çäåñü ïåðâàÿ ôîðìóëà âûâîäèìà â îáåèõ ñèñòåìàõ, à âòîðàÿ –
òîëüêî â êëàññè÷åñêîé.
9.
N
c
(¬À ∨ Â) ⊃ (À ⊃ Â).
23
13
(3)
(2)
(1)
[][ ]
[] []
()()
AA
B
AB B
B
AB
AB A B
¬
¬ ∨
⊃
¬∨ ⊃ ⊃
76
10.
K
N
(À ⊃ Â) ⊃ (¬À ∨ Â).
5
3
41 2
2
(5)
(4) (3)
(2)
(1)
[]
[]
[] [ ] [( )]
[( )]
()
()( )
B
A
AAB AB
AB
AB
AB
BB
AA
AB
AB
AB AB
¬
⊃¬¬∨
¬∨
¬¬ ∨
¬∨
¬
¬¬¬
¬¬ ¬ ∨
¬∨
⊃⊃¬∨
 çàêëþ÷åíèå ðàññìîòðèì äåðåâî âûâîäà èçâåñòíîãî êëàññè-
÷åñêîãî çàêîíà èñêëþ÷åííîãî òðåòüåãî (ëàò. tertium non datur), êîòî-
ðûé âûâîäèì â êëàññè÷åñêîé, íî íå âûâîäèì â èíòóèöèîíèñòñêîé
ñèñòåìå.
11.
K
N
À ∨ ¬À.
(2) (3)
(1)
23
1
1
[] [ ]
[( )]
[( )]
()
AA
AA
AA
AA AA
AA
AA
AA
¬
¬∨¬
¬∨¬
∨¬ ∨¬
¬¬¬
¬¬ ∨ ¬
∨¬
ÓÏÐÀÆÍÅÍÈÅ
Äîêàæèòå ïîñòðîåíèåì äåðåâüåâ N
c
-âûâîäà (A, B, Ñ – ïðîèç-
âîëüíûå ôîðìóëû):
1)
N
c
À ⊃ (Â ⊃ À);
2)
N
c
(À ⊃ (Â ⊃ Ñ)) ⊃ ((À ⊃ Â) ⊃ (À ⊃ Ñ));
3)
N
c
À & Â ⊃ À; 4)
N
c
À & Â ⊃ Â;
5)
N
c
À ⊃ (Â ⊃ À & Â);
6)
N
c
À ⊃ À ∨ Â; 7)
N
c
 ⊃ À ∨ Â;
8)
N
c
(À ⊃ Ñ) ⊃ ((Â ⊃ Ñ) ⊃ (À ∨ Â ⊃ Ñ));
9)
N
c
(A ⊃ Â) ⊃ ((A ⊃ ¬Â) ⊃ ¬A);
10)
N
c
À ⊃ (¬À ⊃ Â);
11)
K
N
¬¬À ⊃ À.
77
§ 2.6. Ïðèíöèï èíäóêöèè§ 2.6. Ïðèíöèï èíäóêöèè
§ 2.6. Ïðèíöèï èíäóêöèè§ 2.6. Ïðèíöèï èíäóêöèè
§ 2.6. Ïðèíöèï èíäóêöèè
äëÿ äåðåâüåâ âûâîäàäëÿ äåðåâüåâ âûâîäà
äëÿ äåðåâüåâ âûâîäàäëÿ äåðåâüåâ âûâîäà
äëÿ äåðåâüåâ âûâîäà
Ìû óæå çíàêîìû ñ íåêîòîðûìè îòíîøåíèÿìè
ìåæäó ìíîæåñòâàìè ôîðìóë è ôîðìóëàìè: ñ îò-
íîøåíèåì N
i
-âûâîäèìîñòè
N
i
, îòíîøåíèåì
N
k
-âûâîäèìîñòè
k
N
, îòíîøåíèåì ñåìàíòè÷åñ-
êîãî ñëåäîâàíèÿ
. Â äàëüíåéøåì ìû ðàñøèðèì ñïèñîê ïîäîáíî-
ãî ðîäà îòíîøåíèé. Âñå ýòè îòíîøåíèÿ òåì èëè èíûì îáðàçîì
óòî÷íÿþò èíòóèòèâíîå ïîíÿòèå ëîãè÷åñêîãî ñëåäîâàíèÿ, èñïîëüçóå-
ìîå â íåôîðìàëüíûõ ìàòåìàòè÷åñêèõ ðàññóæäåíèÿõ.
Îäíè èç ýòèõ îòíîøåíèé îïðåäåëÿþòñÿ â òåðìèíàõ ôîðìàëü-
íûõ âûâîäîâ â íåêîòîðîì èñ÷èñëåíèè (ôîðìàëüíîé ëîãè÷åñêîé
ñèñòåìå). Èõ ìîæíî ðàññìàòðèâàòü êàê ñèíòàêñè÷åñêèå óòî÷íåíèÿ
ïîíÿòèÿ ëîãè÷åñêîãî ñëåäîâàíèÿ. Òàêèìè ÿâëÿþòñÿ, íàïðèìåð,
îòíîøåíèå N
i
-âûâîäèìîñòè
N
i
è îòíîøåíèå N
k
-âûâîäèìîñòè
K
N
.
Äðóãèå îòíîøåíèÿ îïðåäåëÿþòñÿ â ñåìàíòè÷åñêèõ òåðìèíàõ,
òàêèõ êàê èíòåðïðåòàöèÿ, îöåíêà, çíà÷åíèå ôîðìóëû è ò. ï. Òà-
êèå îòíîøåíèÿ ìîæíî ðàññìàòðèâàòü êàê ñåìàíòè÷åñêèå óòî÷íå-
íèÿ îòíîøåíèÿ ëîãè÷åñêîãî ñëåäîâàíèÿ. Ïîêà íàì èçâåñòíî òîëüêî
îäíî òàêîå îòíîøåíèå – îòíîøåíèå ñåìàíòè÷åñêîãî ñëåäîâàíèÿ
. Ýòî îòíîøåíèå ïîÿâèëîñü ïðè ñòàíäàðòíîì òîëêîâàíèè ïðî-
ïîçèöèîíàëüíûõ ñâÿçîê (ïðè ñòàíäàðòíîé èõ èíòåðïðåòàöèè).
Ïîçæå, êîãäà áóäóò ðàññìîòðåíû äðóãèå èíòåðïðåòàöèè, ïîÿâÿò-
ñÿ è ñîîòâåòñòâóþùèå èì òàê íàçûâàåìûå îòíîøåíèÿ M-ñëåäî-
âàíèÿ (ñì. § 2.11).
È òå è äðóãèå îòíîøåíèÿ, ñëóæàùèå ìàòåìàòè÷åñêèìè óòî÷íå-
íèÿìè ïîíÿòèÿ ëîãè÷åñêîãî ñëåäîâàíèÿ, îòíîñÿòñÿ ê îòíîøåíèÿì
òèïà ñëåäîâàíèÿ. Óêàæåì âàæíåéøèå ñâîéñòâà òàêèõ îòíîøåíèé.
Ñíà÷àëà ââåäåì îáîçíà÷åíèÿ è äàäèì íåñêîëüêî îïðåäåëåíèé.
S Ïðîèçâîëüíîå îòíîøåíèå ìåæäó ìíîæåñòâàìè ôîðìóë è ôîð-
ìóëàìè áóäåì îáîçíà÷àòü áóêâîé ρ. Åñëè ìíîæåñòâî ôîðìóë à íà-
õîäèòñÿ â îòíîøåíèè ρ ñ ôîðìóëîé F, áóäåì çàïèñûâàòü ýòî òàê:
ÃρF. Âìåñòî (Ã∪{A})ρF áóäåì ïèñàòü Ã,
ÀρF, à âìåñòî {A}ρF – ïðî-
ñòî AρF.
Îòíîøåíèå ρ áóäåì íàçûâàòü ðåôëåêñèâíûì, åñëè äëÿ ëþáîé
ôîðìóëû F âûïîëíÿåòñÿ FρF.
Математические
уточнения понятия
логического
следования
78
Îòíîøåíèå ρ áóäåì íàçûâàòü ìîíîòîííûì, åñëè äëÿ ëþáûõ
ìíîæåñòâ ôîðìóë Ã è ÃR è ëþáîé ôîðìóëû F, òàêèõ ÷òî ÃρF è
à ⊆ ÃR, âûïîëíÿåòñÿ à RρF, ò. å. åñëè
(Ã) (ÃR) (F) (ÃρF → (Ã ⊆ ÃR→ ÃRρF)).
Îòíîøåíèå ρ áóäåì íàçûâàòü òðàíçèòèâíûì, åñëè äëÿ ëþáûõ
Ã
1
, Ã
2
è F èç óñëîâèé Ã
1
ρÃ
2
è Ã
2
ρF ñëåäóåò, ÷òî Ã
1
ρF (ãäå çàïèñü
Ã
1
ρÃ
2
îçíà÷àåò, ÷òî Ã
1
ρ äëÿ êàæäîé ôîðìóëû  ∈ Ã
2
), ò. å. åñëè
(Ã
1
) (Ã
2
) (F) (Ã
1
ρÃ
2
→ (Ã
2
ρF → Ã
1
ρF)).
Îòíîøåíèå ρ áóäåì íàçûâàòü ïîäñòàíîâî÷íûì, åñëè äëÿ ëþáî-
ãî îïåðàòîðà ïîäñòàíîâêè S è ëþáûõ Ã è F, òàêèõ ÷òî ÃρF,
âûïîëíÿåòñÿ S(Ã)ρS(F):
(Ã) (F) (ÃρF → S(Ã)ρS(F)).
Îòíîøåíèå ìåæäó êîíå÷íûìè ìíîæåñòâàìè ôîðìóë è ôîðìó-
ëàìè áóäåì íàçûâàòü îòíîøåíèåì òèïà ñëåäîâàíèÿ, åñëè îíî
ðåôëåêñèâíî, ìîíîòîííî, òðàíçèòèâíî è ïîäñòàíîâî÷íî
1)
.
Ëåãêî ïðîâåðèòü, íàïðèìåð, ÷òî îòíîøåíèÿ
N
i
,
k
N
è
ÿâ-
ëÿþòñÿ îòíîøåíèÿìè òèïà ñëåäîâàíèÿ.
Çàìå÷àíèå 1. Ïóñòü ρ – ïðîèçâîëüíîå îòíîøåíèå ìåæäó êîíå÷-
íûìè ìíîæåñòâàìè ôîðìóë è ôîðìóëàìè. Îòíîøåíèå ρ áóäåì íà-
çûâàòü êâàçèðåôëåêñèâíûì, åñëè äëÿ ëþáîãî ìíîæåñòâà ôîðìóë Ã è
ëþáîé ôîðìóëû F èç à âûïîëíÿåòñÿ ÃρF. Ñèìâîëè÷åñêè ýòî óñëî-
âèå ìîæíî çàïèñàòü òàê: (Ã) (F) (F ∈ Ã → ÃρF).
Ìîæíî äîêàçàòü ñëåäóþùèå óòâåðæäåíèÿ, îòðàæàþùèå ñâÿçü
ìåæäó ââåäåííûìè õàðàêòåðèñòèêàìè îòíîøåíèÿ ρ:
1) åñëè ρ ðåôëåêñèâíî è ìîíîòîííî, òî ρ êâàçèðåôëåêñèâíî;
2) åñëè ρ êâàçèðåôëåêñèâíî è òðàíçèòèâíî, òî ρ ìîíîòîííî;
3) åñëè ρ êâàçèðåôëåêñèâíî, òî îíî ðåôëåêñèâíî.
 ðÿäå òåîðåì î ñèñòåìàõ åñòåñòâåííîãî âûâîäà ãîâîðèòñÿ î
ñâÿçè ìåæäó îòíîøåíèåì N
i
- èëè N
k
-âûâîäèìîñòè è êàêèì-ëèáî
îòíîøåíèåì òèïà ñëåäîâàíèÿ. Ïîäîáíûå òåîðåìû ôîðìóëèðóþòñÿ
îáû÷íî òàê: «Êàêîâû áû íè áûëè ìíîæåñòâî ôîðìóë à è ôîðìó-
ëà F, åñëè Ã
N
c
F, òî Ã íàõîäèòñÿ â òàêîì-òî îòíîøåíèè ñ F».
1)
Åñëè íå îãðàíè÷èâàòüñÿ êîíå÷íûìè ìíîæåñòâàìè Ã, òî ñëåäóåò ïîòðåáî-
âàòü, ÷òîáû îòíîøåíèå ρ óäîâëåòâîðÿëî åùå îäíîìó óñëîâèþ – óñëîâèþ êîíå÷-
íîñòè: êàêîâû áû íè áûëè à è F, åñëè ÃρF, òî ñóùåñòâóåò òàêîå êîíå÷íîå
ïîäìíîæåñòâî Δ ìíîæåñòâà Ã, ÷òî ΔρF.
79
Äðóãèìè ñëîâàìè: «Äëÿ ëþáîãî ìíîæåñòâà ôîðìóë Ã è ëþáîé
N
c
-âûâîäèìîé èç Ã ôîðìóëû F ìíîæåñòâî ôîðìóë Ã íàõîäèòñÿ â
îòíîøåíèè ρ ñ F», ãäå ρ – íåêîòîðîå îòíîøåíèå òèïà ñëåäîâàíèÿ.
Äàëåå â ýòîì ïàðàãðàôå áóäåò óñòàíîâëåíî, ÷òî äëÿ äîêàçàòåëü-
ñòâà òàêîãî âèäà òåîðåì äîñòàòî÷íî ïðîâåðèòü, ÷òî ρ óäîâëåòâîðÿåò
íåêîòîðûì èçâåñòíûì óñëîâèÿì.
Ñíà÷àëà ââåäåì åùå íåñêîëüêî âàæíûõ ïîíÿòèé.
!
Ïóñòü ρ – îòíîøåíèå ìåæäó êîíå÷íûìè ìíîæå-
ñòâàìè ôîðìóë è ôîðìóëàìè.
Áóäåì ãîâîðèòü, ÷òî ïðÿìîå N
c
-ïðàâèëî (ñõåìà
çàêëþ÷åíèé)
...
n
1
FF
F
ñîõðàíÿåò îòíîøåíèå ρ, åñëè
äëÿ ëþáîãî ìíîæåñòâà ôîðìóë Ã è ëþáîãî íàáî-
ðà ôîðìóë F
1
, ..., F
n
, F, ñîîòâåòñòâóþùåãî ýòîìó
ïðàâèëó, èç óñëîâèé ÃρF
1
, …, ÃρF
n
ñëåäóåò, ÷òî
ÃρF.
Ñèìâîëè÷åñêè ýòî ïîñëåäíåå óñëîâèå áóäåì çàïèñûâàòü òàê:
1
à ; ...; Ã
Ã
n
FF
F
ρρ
ρ
Íàïðèìåð, ïðàâèëî &â ñîõðàíÿåò îòíîøåíèå ρ, åñëè äëÿ ëþ-
áûõ ôîðìóë À è  è ëþáîãî ìíîæåñòâà ôîðìóë Ã, òàêèõ ÷òî ÃρÀ è
ÃρÂ, âûïîëíÿåòñÿ Ãρ(À & Â), ò. å. åñëè:
(A) (B) (Ã)
ρ ; ρ
ρ (&)
AB
AB
ΓΓ
⎛⎞
⎜⎟
Γ
⎝⎠
.
!
Áóäåì ãîâîðèòü, ÷òî êîñâåííûå ïðàâèëà ⊃â, ∨ó, ¬â ñîõðàíÿþò
îòíîøåíèå ρ, åñëè äëÿ ëþáîãî ìíîæåñòâà ôîðìóë Ã è ëþáûõ
ôîðìóë À, Â, Ñ âûïîëíÿþòñÿ ñîîòâåòñòâåííî ñëåäóþùèå óñëî-
âèÿ:
Ã,
Ã)
AB
AB
ρ
ρ( ⊃
;
Ã);Ã,;Ã,
Ã
ÀÂ ÀÑ BÑ
Ñ
ρ
(∨
ρρ
ρ
;
Ã, ; Ã,
Ã
ÀÂ À Â
A
ρρ¬
ρ¬
.
Àíàëîãè÷íûì îáðàçîì ìîæíî îïðåäåëèòü ïîíÿòèå ñîõðàíåíèÿ
îòíîøåíèÿ ρ ïðîèçâîëüíîé êîñâåííîé ñõåìîé çàêëþ÷åíèé.
S Îòìåòèì, ÷òî ãîðèçîíòàëüíàÿ ÷åðòà çäåñü è äàëåå â àíàëîãè÷-
íûõ ñèòóàöèÿõ ÿâëÿåòñÿ ìåòàñèìâîëîì è èñïîëüçóåòñÿ äëÿ ñîêðà-
ùåíèÿ çàïèñè óñëîâíîãî óòâåðæäåíèÿ â îòëè÷èå îò ãîðèçîíòàëü-
Отношения,
сохраняемые
правилами
заключения
80
íîé ÷åðòû, èñïîëüçóåìîé ïðè çàïèñè ïðàâèë çàêëþ÷åíèÿ èëè äå-
ðåâüåâ âûâîäà è ÿâëÿþùåéñÿ ÷àñòüþ ýòèõ ãðàôè÷åñêèõ îáúåêòîâ
(ñð. ñ çàìå÷àíèåì 2 èç § 2.5).
Ñîîòâåòñòâóþùèå ñâîéñòâà îòíîøåíèÿ N
c
-âûâîäèìîñòè èç § 2.5
îçíà÷àþò, ÷òî âñå N
c
-ïðàâèëà ñîõðàíÿþò îòíîøåíèå N
c
-âûâîäè-
ìîñòè. Ñîîòâåòñòâóþùèå ñâîéñòâà ñåìàíòè÷åñêîãî ñëåäîâàíèÿ èç
§ 1.6 ñâèäåòåëüñòâóþò î òîì, ÷òî âñå N
c
-ïðàâèëà ñîõðàíÿþò òàêæå
îòíîøåíèå ñåìàíòè÷åñêîãî ñëåäîâàíèÿ.
★ Ïóñòü Ã, Δ, Δ
1
, …, Δ
n
– ïåðåìåííûå ïî êîíå÷íûì ìíîæåñòâàì
ôîðìóë; F
1
, …, F
n
, F, À, Â, Ñ – ïåðåìåííûå ïî ôîðìóëàì.
Ìîæíî äîêàçàòü, ÷òî:
I. Åñëè ρ – ðåôëåêñèâíîå, ìîíîòîííîå è òðàíçèòèâíîå îòíî-
øåíèå, òî ñëåäóþùèå òðè óñëîâèÿ ýêâèâàëåíòíû:
1) (Ã)
1
à , ..., Ã
Ã
n
FF
F
ρρ
ρ
⎛⎞
⎜⎟
⎝⎠
;
2) (Δ
1
)…(Δ
n
)
11
1
, ...,
( ...
nn
n
FF
F
Δρ Δρ
Δ∪ ∪Δ ρ
⎛⎞
⎜⎟
)
⎝⎠
;
3) {F
1
, …, F
n
}ρF.
Ïðè ýòîì äëÿ äîêàçàòåëüñòâà ýêâèâàëåíòíîñòè óñëîâèé 1 è 2
äîñòàòî÷íî, ÷òîáû ρ áûëî ìîíîòîííûì. Ýêâèâàëåíòíîñòü óñëîâèé
1 è 3 áóäåò äîêàçàíà äàëåå. Òàêèì îáðàçîì, â îïðåäåëåíèè ïîíÿòèÿ
ñîõðàíåíèÿ ïðÿìûì ïðàâèëîì îòíîøåíèÿ ρ ìîæíî âìåñòî óñëîâèÿ 1
âçÿòü óñëîâèå 2 èëè óñëîâèå 3.
II. Åñëè ρ – ìîíîòîííîå îòíîøåíèå, òî ñëåäóþùèå äâà óñëî-
âèÿ ýêâèâàëåíòíû:
1) (Ã)
Ã,
Ã)
AB
AB
ρ
ρ( ⊃
⎛⎞
⎜⎟
⎝⎠
; 2) (Δ)
(\{}) )
B
AAB
Δρ
Δρ(⊃
⎛⎞
⎜⎟
⎝⎠
.
III. Åñëè ρ – ðåôëåêñèâíîå, ìîíîòîííîå è òðàíçèòèâíîå îòíî-
øåíèå, òî ñëåäóþùèå òðè óñëîâèÿ ýêâèâàëåíòíû:
1) (Ã)
Ã);Ã,;Ã,
Ã
ÀÂ ÀÑ BÑ
Ñ
ρ( ∨ ρ ρ
ρ
⎛⎞
⎜⎟
⎝⎠
;
2) (Δ
1
) (Δ
2
) (Δ
3
)
123
12 3
); ;
((\{})(\{}))
ÀÂ Ñ Ñ
ABÑ
Δρ( ∨ Δρ Δρ
Δ∪Δ ∪Δ ρ
⎛⎞
⎜⎟
⎝⎠
;
3) (Ã)
Ã, ; Ã,
Ã,( )
ÀÑ BÑ
ÀÂÑ
ρρ
∨ρ
⎛⎞
⎜⎟
⎝⎠
.