Лекции - Математическая логика

Подождите немного. Документ загружается.

2.1.1. Åñëè

åñòü N

-Δ

-À-âûâîä, à

åñòü N

-Δ

-Â-âûâîä,

òî

ΔΔ

åñòü N

-Δ

∪ Δ

-À&Â-âûâîä.

2.1.2. Åñëè

ÀB

åñòü N

-Δ

-À & Â -âûâîä, òî

åñòü

-Δ

-À-âûâîä è

åñòü N

-Δ

-Â-âûâîä.

2.1.3. Åñëè

åñòü N

-Δ

-À-âûâîä, òî

∨

åñòü N

-Δ

-À ∨ Â-âûâîä,

è åñëè

– N

-Δ

-Â-âûâîä, òî

∨

åñòü N

-Δ

-À ∨ Â-âûâîä.

2.1.4. Åñëè

åñòü N

-Δ

-À-âûâîä, à

AÂ

⊃

åñòü N

-Δ

-À ⊃ Â-âû-

âîä, òî

AAB

ΔΔ

⊃

åñòü N

-Δ

∪ Δ

-Â-âûâîä.

2.1.5. Åñëè

åñòü N

-Δ

-À-âûâîä, à

åñòü N

-Δ

-¬A-âûâîä,

òî

ΔΔ

åñòü N

-Δ

∪ Δ

-Â-âûâîä.

2.1.6 (äëÿ N

). Åñëè

¬¬

åñòü N

-Δ

-¬¬À-âûâîä, òî

¬¬

åñòü

-Δ

-A-âûâîä.

2.2.1. Åñëè

åñòü N

-Δ

-B-âûâîä, òî

⊃

åñòü N

-Δ-À ⊃ Â-âû-

âîä, ãäå Δ = Δ

\{A}.

2.2.2. Åñëè

∨

åñòü N

-Δ

-À ∨ Â-âûâîä,

åñòü N

-Δ

-Ñ-âûâîä

åñòü N

-Δ

-Ñ-âûâîä, òî

123

AB C C

ΔΔΔ

∨

DDD

åñòü N

-Δ-Ñ-âû-

âîä, ãäå Δ = Δ

∪ (Δ

\ {A}) ∪ (Δ

\ {B}).

2.2.3. Åñëè

åñòü N

-Δ

-B-âûâîä, à

åñòü N

-Δ

-¬Â -âûâîä,

òî

ΔΔ

åñòü N

-Δ-¬À-âûâîä, ãäå Δ = (Δ

\ {A}) ∪ (Δ

\ {A}).

3. Äåðåâî ôîðìóë ÿâëÿåòñÿ N

-Δ-F-âûâîäîì òîãäà è òîëüêî òîã-

äà, êîãäà ýòî ìîæåò áûòü îáîñíîâàíî ñ ïîìîùüþ ï. 1 è 2.

Â øàãå èíäóêöèè ýòîãî îïðåäåëåíèÿ êàæäîìó ïðàâèëó çàêëþ÷åíèÿ

ñîîòâåòñòâóåò ñâîé ïóíêò. Òî÷íåå, ï. 2 ñîäåðæèò âîñåìü ïîäïóíêòîâ äëÿ

(è 9 äëÿ N

), êàæäûé èç êîòîðûõ ñîîòâåòñòâóåò íåêîòîðîìó N

-ïðàâè-

ëó, ïðè÷åì ïåðâûå ïÿòü ïóíêòîâ äëÿ N

(øåñòü äëÿ N

) ñîîòâåòñòâóþò

ïðÿìûì ïðàâèëàì, à ïîñëåäíèå òðè ïóíêòà – êîñâåííûì ïðàâèëàì.

Ìíîæåñòâà çåëåíûõ ëèñòüåâ äåðåâüåâ N

-âûâîäà, ïîñòðîåííûõ

ñîãëàñíî ï. 2.1.1–2.1.6, êîòîðûå îòíîñÿòñÿ ê ïðÿìûì ïðàâèëàì,

îïðåäåëÿþòñÿ àíàëîãè÷íî, â ñâÿçè ñ ÷åì ýòè ïóíêòû ìîæíî îáúå-

äèíèòü â îäèí ïóíêò, ïîëó÷àÿ «ñâåðíóòîå» îïðåäåëåíèå

-Δ-F-âûâîäà. Àíàëîãè÷íîå îáúåäèíåíèå ï. 2.2.1–2.2.3, îòíîñÿ-

ùèõñÿ ê êîñâåííûì ïðàâèëàì, ñóùåñòâåííî óñëîæíÿåò âîñïðèÿòèå

ýòîãî îïðåäåëåíèÿ, è ïîýòîìó ìû ýòîãî äåëàòü íå áóäåì.

«Ñâåðíóòîå» îïðåäåëåíèå N

ΔΔ

Δ-F-âûâîäà:

1. Áàçèñ èíäóêöèè. Ëþáàÿ ôîðìóëà F åñòü N

-Δ-F-âûâîä, ãäå Δ = {F}.

2. Øàã èíäóêöèè.

2.1. Åñëè äëÿ êàæäîãî i (i = 1, …, n)

åñòü N

-Δ

-F

-âûâîä, à

äåðåâî ôîðìóë

...

ïîñòðîåíî ïî êàêîìó-ëèáî ïðÿìîìó

-ïðàâèëó, òî

...

åñòü N

-Δ-F-âûâîä, ãäå Δ = Δ

∪ …

... ∪ Δ

(n = 1, 2)

2.2.1. Åñëè

åñòü N

-Δ

-B-âûâîä, òî

⊃

åñòü N

-Δ-À ⊃ Â-âû-

âîä, ãäå Δ = Δ

\{A}.

2.2.2. Åñëè

∨

åñòü N

-Δ

-À ∨ Â-âûâîä,

– N

-Δ

-Ñ-âûâîä

– N

-Δ

-Ñ-âûâîä, òî

123

AB C C

ΔΔΔ

∨

DDD

åñòü N

-Δ-Ñ-âûâîä,

ãäå Δ = Δ

∪ (Δ

\{A}) ∪ (Δ

\{B}).

2.2.3. Åñëè

åñòü N

-Δ

-B-âûâîä, à

åñòü N

-Δ

-¬Â-âû-

âîä, òî

ΔΔ

åñòü N

-Δ-¬À-âûâîä, ãäå Δ = (Δ

\{A}) ∪ (Δ

\{A}).

3. Äåðåâî ôîðìóë ÿâëÿåòñÿ N

-Δ-F-âûâîäîì òîãäà è òîëüêî òîã-

äà, êîãäà ýòî ìîæåò áûòü îáîñíîâàíî ñ ïîìîùüþ ï. 1 è 2.

Êàæäîå ïðÿìîå N

-ïðàâèëî èìååò îäíó (n = 1) èëè äâå (n = 2) ïîñûëêè.

Âñÿêèé N

-Δ-F-âûâîä áóäåì òàêæå èíîãäà íàçûâàòü äåðåâîì N

-âû-

âîäà èëè ïðîñòî N

-âûâîäîì (ò. å. N

-âûâîäîì èëè N

-âûâîäîì).

S Çàìå÷àíèå 1. Êàê óæå ãîâîðèëîñü, ïðè ïîñòðîåíèè äåðåâà

-âûâîäà óäîáíî èñïîëüçîâàòü ñëåäóþùèå äîïîëíèòåëüíûå ñèì-

âîëû è ìåòêè. Âî-ïåðâûõ, íà êàæäîì øàãå ïîñòðîåíèÿ äåðåâà

-âûâîäà ñïðàâà îò êàæäîé ÷åðòû áóäåì óêàçûâàòü ñèìâîëè÷åñ-

êîå îáîçíà÷åíèå ïðèìåíÿåìîãî íà ýòîì øàãå ïðàâèëà. Âî-âòîðûõ,

åñëè â ðåçóëüòàòå ïðèìåíåíèÿ êîñâåííîãî ïðàâèëà (ï. 2.2.1–2.2.3

îïðåäåëåíèÿ N

-Δ-F-âûâîäà) íåêîòîðàÿ ôîðìóëà óäàëÿåòñÿ èç ìíî-

æåñòâà çåëåíûõ ëèñòüåâ (â ýòîì ñëó÷àå áóäåì ãîâîðèòü, ÷òî ëèñò

óâÿäàåò

), òî âñå ñîîòâåòñòâóþùèå èñõîäíûå âõîæäåíèÿ ýòîé ôîð-

ìóëû áóäåì çàêëþ÷àòü â êâàäðàòíûå ñêîáêè. Êðîìå òîãî, ýòèì âõîæ-

äåíèÿì áóäåì ïðèñâàèâàòü îäèí è òîò æå íîìåð è ýòîò æå íîìåð

çàïèñûâàòü ñïðàâà îò ÷åðòû ñîîòâåòñòâóþùåãî çàêëþ÷åíèÿ ïî äàí-

íîìó êîñâåííîìó ïðàâèëó. Òàêèå ìåòêè óêàçûâàþò, íà êàêîì øàãå

ïîñòðîåíèÿ äåðåâà è êàêîé èìåííî ëèñò óâÿë. 

Çàìå÷àíèå 2. Îòìåòèì, ÷òî ïîíÿòèå ìíîæåñòâà óâÿäøèõ ëèñòüåâ

(ïðîìåæóòî÷íûõ äîïóùåíèé) äåðåâà N

-âûâîäà ìîæíî îïðåäåëèòü

èíäóêòèâíî. Ïðè ýòîì äëÿ ýëåìåíòàðíîãî äåðåâà âûâîäà F ìíîæå-

ñòâî óâÿäøèõ ëèñòüåâ ïóñòî. Øàã ïîñòðîåíèÿ äåðåâà N

-âûâîäà ñ

ïîìîùüþ ïðÿìîãî ïðàâèëà çàêëþ÷åíèÿ íå ìåíÿåò îáùåå ìíîæå-

ñòâî óâÿäøèõ ëèñòüåâ. Øàã ïîñòðîåíèÿ äåðåâà N

-âûâîäà ñ ïîìî-

ùüþ êîñâåííîãî ïðàâèëà çàêëþ÷åíèÿ ê ìíîæåñòâó óâÿäøèõ ëèñòü-

åâ äîáàâëÿåò â òî÷íîñòè òå ôîðìóëû, êîòîðûå óäàëÿåò ïðè ýòîì èç

ìíîæåñòâà çåëåíûõ ëèñòüåâ Δ. Îñòàâëÿåì ôîðìóëèðîâêó èíäóêòèâ-

íîãî îïðåäåëåíèÿ ìíîæåñòâà óâÿäøèõ ëèñòüåâ ÷èòàòåëþ â êà÷åñòâå

óïðàæíåíèÿ. 

Âûøå áûëî ïîêàçàíî, êàêèì îáðàçîì óäîáíî

ñòðîèòü äåðåâî âûâîäà, íà÷èíàÿ ñ êîðíÿ. Òåïåðü

ïðîàíàëèçèðóåì êîíêðåòíûé N

-∅-F-âûâîä â

ñîîòâåòñòâèè ñ èíäóêòèâíûì îïðåäåëåíèåì,

ò. å. îò ëèñòüåâ ê êîðíþ. Âîçüìåì â êà÷åñòâå

ïðèìåðà ôîðìóëó F



À ⊃ (Â ⊃ À & Â). Ýòîò àíà-

ëèç ïðîâåäåì ïî øàãàì. Ïîñòðîèì ïîñëåäîâàòåëüíîñòü

äåðåâüåâ

-âûâîäà, îòðàæàþùóþ øàãè «ïîëó÷åíèÿ» èç ýëåìåíòàðíûõ äå-

ðåâüåâ (ëèñòüåâ) èñêîìîãî äåðåâà N

-∅-F-âûâîäà. Áóäåì óêàçûâàòü

äëÿ êàæäîãî åå ÷ëåíà

ñîîòâåòñòâóþùåå åìó ìíîæåñòâî çåëåíûõ

Ñëåäóåò îáðàòèòü âíèìàíèå íà òî, ÷òî ëèñò – ýòî íå èñõîäíîå âõîæäåíèå

ôîðìóëû â äåðåâî, à ñàìà ôîðìóëà, êîòîðàÿ èìååò îäíî èëè íåñêîëüêî èñõîä-

íûõ âõîæäåíèé.

Пример,

иллюстрирующий

определение

&Δ&

&вывода

ëèñòüåâ Δ

, ìíîæåñòâî óâÿäøèõ ëèñòüåâ Θ

, êîðåíü F

è âûñîòó h

Êàæäûé ðàç, ïðèìåíÿÿ êàêîå-ëèáî ïðàâèëî çàêëþ÷åíèÿ, áóäåì

ñïðàâà îò ÷åðòû çàïèñûâàòü ñèìâîëè÷åñêîå îáîçíà÷åíèå ýòîãî ïðà-

âèëà.

Ïåðâûé øàã:



À; Δ

= {A}; Θ

= ∅; h

= 0; F

= À.

Âòîðîé øàã:



Â; Δ

= {Â}; Θ

= ∅; h

= 0; F

= Â.

Çàìåòèì, ÷òî

– ýëåìåíòàðíûå äåðåâüÿ.

Òðåòèé øàã:



&â

; Δ

= {À, Â}; Θ

= ∅; h

= 1; F

= À & Â.

Çäåñü ìû ïåðâûé ðàç ïðèìåíèëè ïðàâèëî çàêëþ÷åíèÿ, à èìåí-

íî, ïðàâèëî ââåäåíèÿ êîíúþíêöèè, è ñïðàâà îò ÷åðòû óêàçàëè ýòî

ñèìâîëîì &â.

×åòâåðòûé øàã:



ÂAB

⊃

; Δ

= Δ

\ {Â} = {À}; Θ

= Θ

∪

∪ {Â} = {B}; h

= 2; F

= Â ⊃ À & Â.

Íà ýòîì øàãå ïîëó÷åíèÿ äåðåâà ìû ïðèìåíèëè êîñâåííîå ïðà-

âèëî ⊃â, ïðè ýòîì ôîðìóëà Â ïåðåñòàëà áûòü çåëåíûì ëèñòîì,

êàêîâûì îíà áûëà â

(ëèñò óâÿë). Íà ýòîì øàãå ìû åäèí-

ñòâåííîå èñõîäíîå âõîæäåíèå ôîðìóëû Â â äåðåâî

çàêëþ÷àåì â

êâàäðàòíûå ñêîáêè, ñíàáæàÿ åãî íîìåðîì 1, è ñòàâèì ýòîò æå íî-

ìåð â êðóãëûõ ñêîáêàõ ñïðàâà îò ÷åðòû ñîîòâåòñòâóþùåãî çàêëþ-

÷åíèÿ ïî ïðàâèëó ⊃â. Òàêèì îáðàçîì,

èìååò âèä

(1)

[]

BAB

⊃

Ïÿòûé øàã:



(&)

ÀÂAB

⊃

⊃⊃

; Δ

= Δ

\ {À} = ∅; Θ

= Θ

∪

∪ {À} = {A, B}; h

= 3; F

À ⊃

(Â ⊃

À & Â).

Íà ýòîì øàãå ëèñò À ñòàë óâÿäøèì. Åäèíñòâåííîå èñõîäíîå

âõîæäåíèå ôîðìóëû À â äåðåâî

ìû çàêëþ÷àåì â êâàäðàòíûå

ñêîáêè, ñíàáæàÿ åãî íîìåðîì 2, è ñòàâèì ýòîò æå íîìåð ñïðàâà îò

÷åðòû ñîîòâåòñòâóþùåãî çàêëþ÷åíèÿ ïî ïðàâèëó ⊃â. Â ðåçóëüòàòå

ïîëó÷àåì èñêîìîå äåðåâî âûâîäà:

(1)

(2)

[] []

(&)

BAB

ABAB

⊃

⊃⊃

Ïðèâåäåííûé ïðèìåð ñëóæèò èëëþñòðàöèåé îïðåäåëåíèÿ

-Δ-F-âûâîäà. Â ñîîòâåòñòâèè ñ ýòèì îïðåäåëåíèåì äåðåâî âûâîäà

ïðîàíàëèçèðîâàíî «ñâåðõó âíèç». Íà ïðàêòèêå, åñëè òðåáóåòñÿ ïîñò-

ðîèòü äåðåâî N

-Δ-F-âûâîäà, îáû÷íî óäîáíî äåéñòâîâàòü èíà÷å.

S Ïîñòðîåíèå äåðåâà N

-âûâîäà ñ çàäàííûì êîð-

íåì è çàäàííûì ìíîæåñòâîì çåëåíûõ ëèñòüåâ

óäîáíî íà÷èíàòü ñ êîðíÿ, ñâîäÿ çàäà÷ó ïîñòðîå-

íèÿ èñêîìîãî äåðåâà ê çàäà÷å ïîñòðîåíèÿ áîëåå

ïðîñòûõ äåðåâüåâ N

-âûâîäà ìåíüøåé âûñîòû.

Ïðè ýòîì ìîãóò áûòü ïîëåçíûìè ñëåäóþùèå ðåêîìåíäàöèè:

1. Äëÿ ïîñòðîåíèÿ äåðåâà N

-âûâîäà ñ êîðíåì À & Â (

)

äîñòàòî÷íî ïîñòðîèòü äâà äåðåâà N

-âûâîäà: ïåðâîå ñ êîðíåì À

(

), à âòîðîå ñ êîðíåì Â (

), ãäå Δ

∪ Δ

= Δ. Òîãäà èñêîìîå

äåðåâî âûâîäà áóäåò èìåòü âèä

ΔΔ

2. Äëÿ ïîñòðîåíèÿ äåðåâà N

-âûâîäà ñ êîðíåì À ∨ Â (

∨

)

äîñòàòî÷íî (íî íå âñåãäà âîçìîæíî!) ïîñòðîèòü äåðåâî N

-âûâîäà ñ

êîðíåì À (

) èëè äåðåâî N

-âûâîäà ñ êîðíåì Â (

3. Äëÿ ïîñòðîåíèÿ äåðåâà N

-âûâîäà ñ êîðíåì À ⊃ Â (

⊃

)

äîñòàòî÷íî, äîáàâèâ ê ìíîæåñòâó çåëåíûõ ëèñòüåâ Δ ôîðìóëó À,

ïîñòðîèòü N

-âûâîä ñ êîðíåì Â (

4. Äëÿ ïîñòðîåíèÿ äåðåâà N

-âûâîäà ñ êîðíåì ¬À (

) äîñòà-

òî÷íî, ñ÷èòàÿ ôîðìóëó À çåëåíûì ëèñòîì, ïîñòðîèòü äâà äåðåâà

-âûâîäà – ïåðâîå ñ êîðíåì F (

), à âòîðîå ñ êîðíåì ¬F (

)

äëÿ íåêîòîðîé ôîðìóëû F, ãäå Δ

∪ Δ

= Δ (ãîâîðÿ íåôîðìàëüíî,

ïîëó÷èòü ïðîòèâîðå÷èå).

Ðåêîìåíäàöèè 1–4 ïîäñêàçûâàþò äâèæåíèå îò êîðíÿ ê ëèñòü-

ÿì – «ñíèçó-ââåðõ». Åãî øàãè îïðåäåëÿþòñÿ ëîãè÷åñêîé ñòðóêòó-

ðîé êîðíÿ è îáîñíîâûâàþòñÿ ïðàâèëàìè ââåäåíèÿ. Ýòî äâèæåíèå

«ñíèçó-ââåðõ» óäîáíî ñî÷åòàòü ñ äâèæåíèåì «ñâåðõó-âíèç», îò ëèñ-

òüåâ ê êîðíþ. Ïåðâûå øàãè äâèæåíèÿ «ñâåðõó-âíèç» îïðåäåëÿþòñÿ

ëîãè÷åñêîé ñòðóêòóðîé ëèñòüåâ è îáîñíîâûâàþòñÿ ïðàâèëàìè óäà-

ëåíèÿ. Çäåñü ìîãóò áûòü ïîëåçíûìè ñëåäóþùèå ðåêîìåíäàöèè:

Рекомендации,

полезные

при построении

деревьев вывода

5. Åñëè ôîðìóëà À & Â ÿâëÿåòñÿ çåëåíûì ëèñòîì èñêîìîãî äå-

ðåâà (èëè âûâåäåíà èç çåëåíûõ ëèñòüåâ íà ïðåäûäóùèõ øàãàõ), òî

èç ýòîé ôîðìóëû ìîæíî ïîëó÷èòü ñ ïîìîùüþ ïðàâèëà &ó êàæäóþ

èç ôîðìóë À è Â â îòäåëüíîñòè.

6. Åñëè ôîðìóëà À ∨ Â ÿâëÿåòñÿ çåëåíûì ëèñòîì èñêîìîãî äå-

ðåâà (èëè âûâåäåíà èç çåëåíûõ ëèñòüåâ íà ïðåäûäóùèõ øàãàõ) è

òðåáóåòñÿ ïîñòðîèòü äåðåâî âûâîäà ñ êîðíåì Ñ (

Δ∨

), òî äîñ-

òàòî÷íî ïîñòðîèòü äâà äåðåâà N

-âûâîäà, îáà ñ êîðíåì Ñ, ñ÷èòàÿ â

ïåðâîì äåðåâå çåëåíûì ëèñòîì ôîðìóëó À (

), à âî âòîðîì –

ôîðìóëó Â (

,Δ B

), ãäå Δ

∪ Δ

= Δ. Ãîâîðÿ íåôîðìàëüíî, äîñòàòî÷-

íî ðàññìîòðåòü («ðàçîáðàòü») äâà ñëó÷àÿ.

7. Åñëè ôîðìóëà À ⊃ Â ÿâëÿåòñÿ çåëåíûì ëèñòîì èñêîìîãî äå-

ðåâà (èëè âûâåäåíà èç ìíîæåñòâà çåëåíûõ ëèñòüåâ Δ íà ïðåäûäó-

ùèõ øàãàõ), òî ìîæíî ïîïûòàòüñÿ âûâåñòè ôîðìóëó À èç Δ ñ òåì,

÷òîáû îò ôîðìóë À è À ⊃ Â ïåðåéòè ê ôîðìóëå Â.

8. Åñëè ôîðìóëà ¬À ÿâëÿåòñÿ çåëåíûì ëèñòîì èñêîìîãî äåðåâà

(èëè âûâåäåíà èç ìíîæåñòâà çåëåíûõ ëèñòüåâ Δ íà ïðåäûäóùèõ

øàãàõ), òî ìîæíî ïîïûòàòüñÿ âûâåñòè ôîðìóëó À èç Δ ñ òåì, ÷òî-

áû, âîñïîëüçîâàâøèñü ïðàâèëîì ¬ó, ïîëó÷èòü òðåáóåìóþ (âîîáùå

ãîâîðÿ, ëþáóþ) ôîðìóëó.

Íàêîíåö, ïîñëåäíÿÿ ðåêîìåíäàöèÿ îòíîñèòñÿ òîëüêî ê ñèñòåìå N

9. Äëÿ ïîñòðîåíèÿ N

-âûâîäà ñ êîðíåì À äîñòàòî÷íî ïîñòðîèòü

äåðåâî âûâîäà ñ êîðíåì ¬¬À.

Ïðîèëëþñòðèðóåì íà ïðèìåðå ïðîöåññ ïîñòðîåíèÿ äåðåâà âû-

âîäà â ñîîòâåòñòâèè ñ ïðèâåäåííûìè ðåêîìåíäàöèÿìè.

Ïðèìåð. Ïîñòðîèì äåðåâî N

-∅-F-âûâîäà, ãäå F – ôîðìóëà

(À & Â ⊃ Ñ) ⊃ (À ⊃ (Â ⊃ Ñ)).

Ôîðìóëà (À & Â ⊃ Ñ) ⊃ (À ⊃ (Â ⊃ Ñ)) ïðåäñòàâëÿåò ñîáîé

èìïëèêàöèþ, ïîýòîìó, ñîãëàñíî ïðàâèëó ⊃â, äîñòàòî÷íî âûâåñòè

ôîðìóëó À ⊃ (Â ⊃ Ñ), âçÿâ â êà÷åñòâå äîïóùåíèÿ (çåëåíîãî ëèñòà)

ôîðìóëó À & Â ⊃ Ñ. Ñíàáäèì åå ñðàçó íîìåðîì 1. Ôîðìóëà À ⊃ (Â ⊃ Ñ)

òàêæå ÿâëÿåòñÿ èìïëèêàöèåé, ïðè÷åì åå çàêëþ÷åíèå ñàìî ÿâëÿåò-

ñÿ èìïëèêàöèåé. Ïîýòîìó, äâàæäû ñîñëàâøèñü íà ïðàâèëî ⊃â, çàê-

ëþ÷àåì, ÷òî äîñòàòî÷íî âûâåñòè ôîðìóëó Ñ, äîáàâèâ åùå äâà äî-

ïóùåíèÿ: À (ñ íîìåðîì 2) è Â (ñ íîìåðîì 3). Âîçìîæíîñòè äâèæå-

íèÿ «ñíèçó-ââåðõ» èñ÷åðïàíû. Äîñòðàèâàòü äåðåâî áóäåì ñâåðõó.

Èòàê, âñåãî èìååì òðè äîïóùåíèÿ: À, Â è À & Â ⊃ Ñ, èç êîòîðûõ

õîòèì âûâåñòè ôîðìóëó Ñ. Ïî ïðàâèëó &â èç ôîðìóë

À è Â ïîëó÷à-

åì ôîðìóëó À & Â, çàòåì, ïðèìåíÿÿ ïðàâèëî ⊃ó, èç ôîðìóë À & Â

è À & Â ⊃ Ñ ïîëó÷àåì æåëàåìóþ ôîðìóëó Ñ. Íàêîíåö, óïîðÿäî÷èâ

ôîðìóëû ñîîòâåòñòâóþùèì îáðàçîì, ïîëó÷àåì èñêîìîå äåðåâî

âûâîäà.

(3)

(2)

(1)

[] []

[& ]

()

(& ) ( ( ))

ABC

ABC A BC

⊃

⊃⊃

⊃⊃⊃⊃



Åñëè ñóùåñòâóåò äåðåâî N

-âûâîäà ñ ïóñòûì ìíîæåñòâîì çåëåíûõ

ëèñòüåâ è êîðíåì F, òî áóäåì èñïîëüçîâàòü çàïèñü



F (ñì. § 2.5).

Ïðèìåð. Äîêàæåì, ÷òî



À ⊃ À . Äëÿ ýòîãî äîñòàòî÷íî ïîñò-

ðîèòü äåðåâî N

-âûâîäà:

(1)

[]

⊃

Çàìåòèì, ÷òî çäåñü ìû èìååì äåðåâî

{}

⊃

, ãäå

{}

 A. 

§ 2.5. Îòíîøåíèå § 2.5. Îòíîøåíèå

§ 2.5. Îòíîøåíèå

-âûâîäèìîñòè-âûâîäèìîñòè

-âûâîäèìîñòè

Ïóñòü Ã – ïðîèçâîëüíîå êîíå÷íîå ìíîæåñòâî ôîðìóë.

Áóäåì ãîâîðèòü, ÷òî èç ìíîæåñòâà ôîðìóë Ã N

-âûâîäèìà ôîð-

ìóëà F, è ïèñàòü Ã



F, åñëè ñóùåñòâóåò N

-Δ-F-âûâîä, ìíî-

æåñòâî çåëåíûõ ëèñòüåâ êîòîðîãî Δ ÿâëÿåòñÿ ïîäìíîæåñòâîì Ã

(Δ ⊆ Ã).

Åñëè Ã



F, òî ôîðìóëû èç ìíîæåñòâà Ã ïðèíÿòî íàçûâàòü

ãèïîòåçàìè.

Åñëè Ã = {À

, …, À

}, òî âìåñòî {À

, …, À

}



F áóäåì ïèñàòü

, …, À



Åñëè Ã



F è Ã = ∅, ò. å. ñóùåñòâóåò N

-∅-F-âûâîä, òî áóäåì

ãîâîðèòü, ÷òî ôîðìóëà F N

-âûâîäèìà (èëè âûâîäèìà â ñèñòå-

ìå N

), è ïèñàòü



F âìåñòî ∅



Òàêèì îáðàçîì, ìû ââåëè îòíîøåíèå ìåæäó êîíå÷íûìè ìíî-

æåñòâàìè ôîðìóë è ôîðìóëàìè – îòíîøåíèå N

-âûâîäèìîñòè.

Â äàëüíåéøåì áóêâû Ã è Δ, âîçìîæíî ñ èíäåêñàìè èëè ñî øòðè-

õàìè, áóäåì èñïîëüçîâàòü êàê ìåòàïåðåìåííûå ïî êîíå÷íûì ìíî-

æåñòâàì ôîðìóë.

Âûÿñíèì òåïåðü, êàêîâà ñâÿçü ìåæäó îòíîøåíèÿìè N

-âûâîäè-

ìîñòè è N

-âûâîäèìîñòè, à òàêæå, êàê ñâÿçàíû äðóã ñ äðóãîì êëàñ-

ñû N

-âûâîäèìûõ è N

-âûâîäèìûõ ôîðìóë.

ÓÒÂÅÐÆÄÅÍÈÅ. Åñëè ôîðìóëà F N

-âûâîäèìà èç ìíîæåñòâà

Ã, òî F N

-âûâîäèìà èç ìíîæåñòâà Ã, ò. å. (Ã) (F) (Ã



F → Ã



F).

Äîêàçàòåëüñòâî. Ïóñòü Ã



F, ò. å. ñóùåñòâóåò

-Δ-F-âûâîä òàêîé, ÷òî Δ ⊆ Ã. Ïîñêîëüêó âñÿêîå N

-ïðàâèëî ÿâ-

ëÿåòñÿ N

-ïðàâèëîì, òî âñÿêèé N

-Δ-F-âûâîä ÿâëÿåòñÿ N

-Δ-F-âû-

âîäîì, â ÷àñòíîñòè, ïðè ïóñòîì Ã. Ñëåäîâàòåëüíî, Ã



F. 

! ÑËÅÄÑÒÂÈÅ. Âñÿêàÿ N

-âûâîäèìàÿ ôîðìóëà ÿâëÿåòñÿ N

-âûâî-

äèìîé, ò. å. (F)(



F →



F).

Çàìå÷àíèå 1. Ñðàçó îòìåòèì, ÷òî îáðàòíîå íåâåðíî. Íàïðèìåð,

òàêèå ôîðìóëû, êàê p ∨ ¬p, ¬¬p ⊃ p, ¬p ∨ ¬¬p, (p ⊃ q) ⊃ (¬p ∨ q),

¬(p & q) ⊃ (¬p ∨ ¬q) âûâîäèìû â N

, íî íåâûâîäèìû â N

. Î òîì,

êàê äîêàçûâàòü óòâåðæäåíèÿ î íåâûâîäèìîñòè ôîðìóë, ðå÷ü ïîé-

äåò ïîçæå. 

Îñòàíîâèìñÿ òåïåðü íà îñíîâíûõ ñâîéñòâàõ îòíîøåíèÿ âûâî-

äèìîñòè â ñèñòåìàõ åñòåñòâåííîãî âûâîäà.

! ÓÒÂÅÐÆÄÅÍÈÅ. Êàêîâû áû íè áûëè ôîðìóëû

A, F è ìíîæåñòâà ôîðìóë Ã, ÃR, Ã

, Ã

1) À



A (ðåôëåêñèâíîñòü



);

1') åñëè À ∈ Ã, òî Ã



A (êâàçèðåôëåêñèâíîñòü



);

2) åñëè Ã



F è Ã ⊆ ÃR, òî ÃR



F (ìîíîòîííîñòü



);

Основные

свойства

отношения

&выводимости

3) åñëè Ã



è Ã



F, òî Ã



F (òðàíçèòèâíîñòü



ãäå çàïèñü Ã



îçíà÷àåò, ÷òî êàæäàÿ ôîðìóëà èç Ã

ÿâëÿåòñÿ

-âûâîäèìîé èç Ã

;

4) åñëè Ã, A



F è Ã



À, òî Ã



4') åñëè Ã, A



F è



À, òî Ã



F (óäàëåíèå âûâîäèìûõ

ãèïîòåç);

5) åñëè Ã



F, òî S(Ã)



S(F) äëÿ ëþáîãî îïåðàòîðà ïîäñòà-

íîâêè S, ãäå S(Ã)  {S(À) | À ∈ Ã};

5') åñëè



F, òî



S(F) äëÿ ëþáîãî îïåðàòîðà ïîäñòàíîâêè S.

Äîêàçàòåëüñòâî. Ïóñòü À – ïðîèçâîëüíàÿ ôîðìóëà.

1. Ôîðìóëà À ñàìà ÿâëÿåòñÿ äåðåâîì N

-âûâîäà ñ êîðíåì À è

ìíîæåñòâîì çåëåíûõ ëèñòüåâ {A}. Òàêèì îáðàçîì, À



À.

1'. Ïóñòü À ∈ Ã. Äîêàæåì, ÷òî Ã



A, ò. å. ÷òî ñóùåñòâóåò

äåðåâî N

-âûâîäà ñ êîðíåì À è ìíîæåñòâîì çåëåíûõ ëèñòüåâ, ñî-

äåðæàùèìñÿ â Ã. Äåéñòâèòåëüíî, ïîñêîëüêó {A} ⊆ Ã, ôîðìóëà À

ñàìà ÿâëÿåòñÿ òàêèì äåðåâîì. Òàêèì îáðàçîì, Ã



2. Ïóñòü Ã



F è Ã ⊆ Ã R. Äîêàæåì, ÷òî Ã R



F. Äåéñòâèòåëü-

íî, åñëè

– äåðåâî N

-âûâîäà ôîðìóëû F, ìíîæåñòâî çåëåíûõ

ëèñòüåâ êîòîðîãî Δ ÿâëÿåòñÿ ïîäìíîæåñòâîì Ã, òî, î÷åâèäíî,

Δ ⊆ ÃR, à çíà÷èò, ÃR



3. Ïóñòü Ã



è Ã



F. Äîêàæåì, ÷òî Ã



F. Îáîçíà÷èì

÷åðåç

...

– äåðåâî N

-Δ-F-âûâîäà òàêîå, ÷òî Δ = {F

, …, F

} è

Δ ⊆ Ã

(ñëó÷àé, êîãäà Δ = ∅, òðèâèàëåí). Ïîñêîëüêó èç Ã

âûâîäèìà

â N

êàæäàÿ ôîðìóëà èç Ã

, òî Ã



(i = 1, …, n). Äëÿ êàæäîãî i

îáîçíà÷èì ÷åðåç

äåðåâî N

-Δ

-F

-âûâîäà òàêîå, ÷òî Δ

⊆ Ã

. Êàæ-

äîå âõîæäåíèå ôîðìóëû F

(i = 1, …, n) â äåðåâî

...

â êà÷åñòâå

çåëåíîãî ëèñòà çàìåíèì äåðåâîì

. Äåðåâî N

-âûâîäà, êîòîðîå

ïîëó÷àåòñÿ â ðåçóëüòàòå òàêîé çàìåíû, ìîæíî èçîáðàçèòü ñëåäóþ-

ùèì îáðàçîì:

...

ΔΔ

Ìíîæåñòâî çåëåíûõ ëèñòüåâ ýòîãî äåðåâà åñòü ïîäìíîæåñòâî

∪ … ∪ Δ

. Ïîñêîëüêó Δ

∪ … ∪ Δ

⊆ Ã

, òî Ã



4. Ïóñòü Ã, A



F è Ã



À. Äîêàæåì, ÷òî Ã



Îáîçíà÷èì ÷åðåç

– äåðåâî N

-Δ

-F-âûâîäà òàêîå, ÷òî

⊆ Ã ∪ {A}, à ÷åðåç

– äåðåâî N

-Δ

-À -âûâîäà òàêîå, ÷òî

⊆ Ã. Åñëè À

∉

, òî Δ

⊆ Ã è Ã



F. Åñëè À ∈ Δ

, òî Δ

= Δ ∪ {À},

ãäå Δ = Δ

\ {À}. Â ýòîì ñëó÷àå äåðåâî âûâîäà

óäîáíî ïðåäñòà-

âèòü ñëåäóþùèì îáðàçîì:

. Êàæäîå âõîæäåíèå ôîðìóëû À â

äåðåâî âûâîäà

â êà÷åñòâå çåëåíîãî ëèñòà çàìåíèì íà äåðåâî

. Òîãäà äåðåâî N

-âûâîäà, êîòîðîå ïîëó÷àåòñÿ â ðåçóëüòàòå òà-

êîé çàìåíû, ìîæíî èçîáðàçèòü ñëåäóþùèì îáðàçîì: