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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

|A
1
, . . . , A
m
` | = |A
1
| N . . . N | A
m
| =
| ` | =
B
A
1
, . . . , A
m
H
{ A
1
, . . . , A
m
} N
N
N
A Γ N
A
N
Rl(N)
T
1
. . . T
m
Σ
,
T
1
, . . . , T
m
Σ
N
T N
N
Rl(N)
Σ T T
Σ Σ
N
96                     Ãëàâà 3. Ãåíöåíîâñêèå èñ÷èñëåíèÿ âûñêàçûâàíèé


      3) |A1 , . . . , Am ` | = |A1 | N . . . N | Am | = 0 ;
      4) | ` | = 0 .
   Ìû âèäèì, ÷òî â ãëàâíîé èíòåðïðåòàöèè ñåêâåíöèè âèäà (1) è (2)
ïîíèìàþòñÿ êàê óòâåðæäåíèÿ î âûâîäèìîñòè ôîðìóëû B èç íàáîðîâ 
ñîîòâåòñòâåííî A1 , . . . , Am è ïóñòîãî (àíàëîã òåîðåìû â ÈÂ H ). Ñå-
êâåíöèè âèäà (3) è (4) ïîíèìàþòñÿ êàê óòâåðæäåíèÿ ïðîòèâîðå÷èâî-
ñòè  íàáîðà ôîðìóë { A1 , . . . , Am } è ñàìîãî ÈÑ N ñîîòâåòñòâåííî.
   Ìû îïðåäåëÿëè èíòåðïðåòàöèþ â ÈÑ N êàê îòîáðàæåíèå ôîðìóë â
íåêîòîðóþ àëãåáðó ìíîæåñòâ. Ïîíÿòíî, ÷òî ââåä¼ííûå ïîíÿòèÿ ìîæíî
îáîáùèòü, âçÿâ â êà÷åñòâå îáðàçà èíòåðïðåòàöèè ïðîèçâîëüíóþ áóëåâó
àëãåáðó.

1.2 Äîêàçàòåëüñòâî â âèäå äåðåâà. Íîâûå äîïóñòèìûå ïðà-
    âèëà â N

   Âûâîä ôîðìóëû A èç ñîâîêóïíîñòè ôîðìóë Γ â ÈÑ N óäîáíî
èçîáðàæàòü â âèäå äåðåâà, â êîòîðîì A áóäåò êîðíåì, à ëèñòüÿìè 
àêñèîìû N . Ïðè ýòîì ïåðåõîä ïî äåðåâó îò äàííîé âåðøèíû ê ñîñåäíåé
ïî íàïðàâëåíèþ ê êîðíþ îáóñëîâëåí ïðèìåíåíèåì îäíîãî èç ïðàâèë
âûâîäà Rl(N ). Òî÷íîå îïðåäåëåíèå òàêîãî âûâîäà òðåáóåò ââåäåíèÿ
íîâûõ ïîíÿòèé.
   Äåðåâîì ìû áóäåì íàçûâàòü ëèáî îòäåëüíóþ ñåêâåíöèþ, ëèáî ôè-
ãóðó
                                 T1 . . . Tm
                                             ,
                                      Σ
ãäå T1 , . . . , Tm  äåðåâüÿ, à Σ  ñåêâåíöèÿ.
   Âõîæäåíèå ñåêâåíöèè â äàííîå äåðåâî áóäåì íàçûâàòü íà÷àëüíûì ,
åñëè íàä íèì íåò ãîðèçîíòàëüíîé ÷åðòû è çàêëþ÷èòåëüíûì , åñëè ãî-
ðèçîíòàëüíîé ÷åðòû íåò ïîä íèì. Èç îïðåäåëåíèÿ ÿñíî, ÷òî íà÷àëüíûõ
ñåêâåíöèé ìîæåò áûòü ìíîãî, à çàêëþ÷èòåëüíàÿ ñåêâåíöèÿ áóäåò åäèí-
ñòâåííîé.
   Ôèãóðà, ñîñòîÿùàÿ èç ãîðèçîíòàëüíîé ÷åðòû è ñåêâåíöèé íàä è ïîä
íåé íàçûâàþò ïåðåõîäîì . Çàìåòèì, ÷òî âñå ïðàâèëà âûâîäà ÈC N ñóòü
ïåðåõîäû.
Îïðåäåëåíèå 3.3. Äåðåâî T íàçûâàåòñÿ äîêàçàòåëüñòâîì â N â
âèäå äåðåâà , åñëè âñå åãî íà÷àëüíûå ñåêâåíöèè  àêñèîìû ÈÑ N , à
ïåðåõîäû  ÷àñòíûå ñëó÷àè ïðàâèë âûâîäà èç Rl(N ).
   Åñëè ïðè ýòîì Σ  çàêëþ÷èòåëüíàÿ ñåêâåíöèÿ T , òî T íàçûâàåòñÿ
äîêàçàòåëüñòâîì Σ â âèäå äåðåâà èëè äåðåâîì âûâîäà ñåêâåíöèè Σ â
N.

Страницы