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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

A, Γ → ∆, B
C, A, Γ → ∆, B
A, Γ → ∆, B
A, Γ → ∆, B, C
C →
(→
¡
¢
)
C, Γ → ∆, A
¡
¢
B Γ → ∆, A
¡
¢
B, C
¤
A
`
S
A, Γ → ∆, A .
A
A
A A = ¬ B
B, Γ → ∆, B
B, Γ → ∆, B
Γ → ∆, B, ¬ B
(→ ¬)
¬ B, Γ → ∆, ¬ B
(¬ →)
A = B N C
B, C, Γ → ∆, B B, C, Γ → ∆, C
B, C, Γ → ∆, B B, C, Γ → ∆, C
B, C, Γ → ∆, B N C
B N C, Γ → ∆, B N C
(N →)
(→ N).
¤
118                Ãëàâà 3. Ãåíöåíîâñêèå èñ÷èñëåíèÿ âûñêàçûâàíèé


Òîãäà ïî èíäóêòèâíîìó ïðåäïîëîæåíèþ äîïóñòèìû âûâîäû
             A, Γ → ∆, B                A, Γ → ∆, B
                                 è
            C, A, Γ → ∆, B             A, Γ → ∆, B, C
ñ äîáàâëåíèåì ôîðìóëû C ñëåâà è ñïðàâà îò ñèìâîëà →. Ïðè-
                                                ¡
ìåíÿÿ ê çàêëþ÷èòåëüíûì ñåêâåíöèÿì ïðàâèëî (→ ¢), ïîëó÷èì
             ¡¢                             ¡¢
C, Γ → ∆, A B â ïåðâîì ñëó÷àå è Γ → ∆, A B, C âî âòîðîì.
   Îñòàëüíûå ñëó÷àè ðàññìàòðèâàþòñÿ àíàëîãè÷íî.          ¤


Ñëåäñòâèå. Ìîæíî óòâåðæäàòü, ÷òî èñïîëüçîâàíèå äàííûõ ïðàâèë
íå óâåëè÷èâàåò âûñîòó äåðåâà âûâîäà è êîëè÷åñòâà ñåêâåíöèé â í¼ì.
   Äàííîå óòâåðæäåíèå ñëåäóåò èç òîãî, ÷òî äîáàâëåíèå íóæíûõ ñèì-
âîëîâ ôîðìóë ìîæíî îáåñïå÷èòü ïðè çàïèñè àêñèîì, ÿâëÿþùèõñÿ ëè-
ñòüÿìè äåðåâà âûâîäà.
Ëåììà 3.8. Äëÿ âñÿêîé ôîðìóëû A ñïðàâåäëèâî
                         `S A, Γ → ∆, A .

Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ëåììû ïðîâîäÿò èíäóêöèåé ïî ïî-
ñòðîåíèþ ôîðìóëû A.
   Åñëè A  àòîìàðíàÿ ôîðìóëà, òî ðàññìàòðèâàåìàÿ ñåêâåíöèÿ åñòü
àêñèîìà è, ñëåäîâàòåëüíî, òðèâèàëüíî äîêàçóåìà.
   Äàëåå â äîêàçàòåëüñòâå øàãà èíäóêöèè ñëåäóåò ðàññìîòðåòü âñå ñëó-
÷àè ñòðîåíèÿ ôîðìóëû A. Ïóñòü, íàïðèìåð, A = ¬ B . Òîãäà ïî èí-
äóêòèâíîìó ïðåäïîëîæåíèþ äîêàçàíà ñåêâåíöèÿ B, Γ → ∆, B è
                    B, Γ → ∆, B
                                   (→ ¬)
                   Γ → ∆, B, ¬ B
                                            (¬ →)
                      ¬ B, Γ → ∆, ¬ B
åñòü òðåáóåìûé âûâîä.
   Ïóñòü òåïåðü A = B N C . Òîãäà ïî èíäóêòèâíîìó ïðåäïîëîæåíèþ
äîêàçàíû ñåêâåíöèè B, C, Γ → ∆, B è B, C, Γ → ∆, C , à
            B, C, Γ → ∆, B     B, C, Γ → ∆, C
                                                    (→ N).
                B, C, Γ → ∆, B N C
                                      (N →)
               B N C, Γ → ∆, B N C
åñòü òðåáóåìûé âûâîä.
   Îñòàëüíûå ñëó÷àè ðàññìàòðèâàþòñÿ àíàëîãè÷íî.                   ¤

Страницы