Исчисления высказываний классической логики. Гуров С.И. - 55 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

H
Γ
B ∈ ∆ A ∆
A Γ
∆
∆
0
∆
0
` A
B ∆
0
A(x
1
, . . . , x
n
k y
1
, . . . , y
n
)
A π(A)
x ∨ ¯y z ∨ ¯x
A, A
1
, A
2
B Γ ∆
Γ, A ` A
Γ, A, A ` B
Γ, A ` B
2. Èñ÷èñëåíèå âûñêàçûâàíèé H                                     55


÷èñëà ãèïîòåç, ÷òî ñëåäóåò èç îïðåäåëåíèÿ âûâîäà êàê êîíå÷íîé ïîñëå-
äîâàòåëüíîñòè ôîðìóë. Çàìåòèì, ÷òî ÷àñòî îïðåäåëÿþò âûâîä òîëüêî
èç êîíå÷íîãî ìíîæåñòâà ãèïîòåç (ýòîãî äîñòàòî÷íî äëÿ ïðàêòè÷åñêèõ
öåëåé) è òîãäà äàííîå ïðàâèëî ñïåöèàëüíî íå ôîðìóëèðóþò.
    Ñïðàâåäëèâîñòü ñâîéñòâà òðàíçèòèâíîñòè äîêàçûâàåòñÿ ïîñëåäîâà-
òåëüíûì ïðèïèñûâàíèåì äðóã çà äðóãîì âûâîäîâ èç Γ âñåõ ôîðìóë
B ∈ ∆ ñ äîáàâëåíèåì âûâîäà A èç ∆ â êà÷åñòâå ïîñëåäíåãî: î÷åâèä-
íî, ïîëó÷åííàÿ ïîñëåäîâàòåëüíîñòü ôîðìóë óäîâëåòâîðÿåò âñåì òðå-
áîâàíèÿì, ïðåäúÿâëÿåìûì ê âûâîäó A èç íàáîðà Γ. Äàííîé ïðîöåññ
îñóùåñòâëÿåòñÿ çà êîíå÷íîå ÷èñëî øàãîâ, ïîñêîëüêó, ïðè áåñêîíå÷íîì
(ìóëüòè)ìíîæåñòâå ∆ ïî ñâîéñòâó ôèíèòàðíîñòè ìîæíî ðàññìàòðè-
âàòü åãî êîíå÷íîå ïîäìíîæåñòâî ∆0 , âûâîä ∆0 ` A è âûâîäû ôîðìóë
B èç ∆0 . Ðàññìàòðèâàåìîå ïðàâèëî ôîðìàëèçóåò ñâîéñòâî ðàññóæäå-
íèé ïî êîòîðîìó ïðè äîêàçàòåëüñòâå çàêëþ÷åíèÿ ìîæíî èñïîëüçîâàòü
ïðîìåæóòî÷íûå ðåçóëüòàòû.
    Ñâîéñòâî ñòðóêòóðíîñòè ãîâîðèò î òîì, ÷òî âûâîäèìîñòü ñâÿçàíà
ñî ñòðóêòóðîé ôîðìóëû è íå çàâèñèò îò èì¼í å¼ ïåðåìåííûõ, ò.ê. ñïðà-
âåäëèâîñòü âûâîäà, ïîëó÷åííîãî èç äàííîãî íåêîòîðîé ïåðåñòàíîâêîé
ïåðåìåííûõ ñëåäóåò èç âîçìîæíîñòè ïîäñòàíîâêè íîâûõ èì¼í ïåðåìåí-
íûõ â ñîîòâåòñòâóþùóþ ñõåìó âûâîäà. Äåéñòâèòåëüíî, â àêñèîìàõ è
ïðàâèëàõ âûâîäà êîíêðåòíûå èìåíà ïåðåìåííûõ íèêàê íå ôèêñèðóþò-
ñÿ (âîîáùå íå ôèãóðèðóþò) è âî âñåõ âõîäÿùèõ â íèõ ôîðìóëàõ ìîæíî
ñäåëàòü çàìåíó A(x1 , . . . , xn k y1 , . . . , yn ).
    Îòìåòèì, ÷òî ôîðìóëû A è π(A) (è ñîîòâåòñòâóþùèå ôóíêöèè)
íàçûâàþò êîíãðóýíòíûìè . Òàê, êîíãðóýíòíû ôîðìóëû x ∨ ȳ è z ∨ x̄.
Ïîíÿòíî, ÷òî êîíãðóýíòíîñòü  åù¼ îäíà ýêâèâàëåíòíîñòü íà ìíîæå-
ñòâå ôîðìóë.
    Èç îñíîâíûõ ñâîéñòâ âûâîäèìîñòè ìîæíî âûâåñòè äîïóñòèìûå ïðà-
âèëà âûâîäà. Âûâîä ôîðìóëû ñ èñïîëüçîâàíèåì ïðîèçâîäíûõ ïðàâèë
íàçûâàþò ñîêðàù¼ííûì âûâîäîì èëè êâàçèâûâîäîì , ïîä÷¼ðêèâàÿ, ÷òî
îí, ñòðîãî ãîâîðÿ, âûâîäîì íå ÿâëÿåòñÿ, îäíàêî ïðèâîäèò ê ôîðìóëå,
ÿâëÿþùåéñÿ òåîðåìîé èñ÷èñëåíèÿ. Áîëåå òîãî, êàê ïðàâèëî, èç íåãî
ìîæåò áûòü ïîëó÷åí ñòðîãèé âûâîä.
    Äàëåå A, A1 , A2 è B  ïðîèçâîëüíûå ôîðìóëû, à Γ è ∆  ìóëü-
òèìíîæåñòâà ôîðìóë (âîçìîæíî ïóñòûå).

           Äîïóñòèìûå ïðàâèëà âûâîäà (îñíîâíûå)
  1. Γ, A ` A     ïðàâèëî òðèâèàëüíîé âûâîäèìîñòè .
     Îíî ñðàçó ñëåäóåò èç ñâîéñòâà ðåôëåêñèâíîñòè.
     Γ, A, A ` B
  2.                  ñîêðàùåíèå ãèïîòåç .
       Γ, A ` B
     Ïðàâèëî ñëåäóåò èç îïðåäåëåíèÿ âûâîäà.

Страницы