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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

N
+
¡
¢
−
¡
¢
Γ ` A Γ
H N
'
A ' B , A ` B B ` A .
'
A B C N
¬¬A ' A
A
¡
¢
B ' ¬A ∨ B
A N B ' B N A A ∨ B ' B ∨ A
A N B ' ¬(¬A ∨ ¬B) A ∨ B ' ¬(¬A N ¬B)
A N B ' B N A A ∨ B ' B ∨ A
(A∨B) N C ' (A N C)∨(B N C) (A N B)∨C ' (A∨C) N(B ∨C)
(A ∨ B) ∨ C ' A ∨ (B ∨ C) (A N B) N C ' A N(B N C)
¬¬A ' A
¬¬ A ` A
A ` ¬¬ A
A ` A
A, ¬ A ` A
¬ A ` ¬ A
A, ¬ A ` ¬ A
A, ¬ A `
A ` ¬¬ A
(+¬)
(RA)
A
¡
¢
B ' ¬A ∨ B
A
¡
¢
B ` ¬A ∨ B
A ` A A
¡
¢
B ` A
¡
¢
B
A
¡
¢
B, A ` B
(−
¡
¢
)
A
¡
¢
B, A ` ¬A ∨ B
(+∨) ,
¬A ` ¬A
¬A ` ¬A ∨ B
(+∨) .
1. Èñ÷èñëåíèå N íàòóðàëüíîãî òèïà                                   103

                        ¡        ¡
ïðèâëå÷åíèå ïðàâèë ( + ¢ ) è ( − ¢) ). Âî âñåõ ñëó÷àÿõ ñóùåñòâåííûì
ÿâëÿåòñÿ òî, ÷òî â ñåêâåíöèè Γ ` A ìíîæåñòâî ãèïîòåç Γ âñåãäà
êîíå÷íî. Ñâîéñòâî ñòðóêòóðíîñòè îáåñïå÷èâàåòñÿ äîïóñòèìîñòüþ ïðà-
âèëà ïîäñòàíîâêè.
   Ïðèâåä¼ííûå ïðîèçâîäíûå ñâîéñòâà çíàêà âûâîäèìîñòè îñòàþòñÿ
ñïðàâåäëèâûìè ïî îïðåäåëåíèþ â ñèëó îïðåäåëåíèÿ ñåêâåíöèè.
   Àíàëîãè÷íî È H , íà ìíîæåñòâå ôîðìóë ÈÑ N ââîäèòñÿ îòíîøå-
íèå ' äåäóêòèâíîé ýêâèâàëåíòíîñòè ôîðìóë:
        A ' B , åñëè äîêàçóåìû ñåêâåíöèè A ` B è B ` A .
Äåéñòâèòåëüíî, ðåôëåêñèâíîñòü è ñèììåòðè÷íîñòü ' î÷åâèäíû, à
òðàíçèòèâíîñòü îáåñïå÷èâàåòñÿ ïðàâèëîì ñå÷åíèÿ.
Ëåììà 3.3. Ïóñòü A, B è C  ôîðìóëû ÈÑ N . Òîãäà:
  1.   ¬¬A ' A ;
           ¡
  2.   A ¢ B ' ¬A ∨ B ;
  3.   A N B ' B N A, A ∨ B ' B ∨ A ;
  4.   A N B ' ¬(¬A ∨ ¬B), A ∨ B ' ¬(¬A N ¬B) ;
  5.   A N B ' B N A, A ∨ B ' B ∨ A ;
  6.   (A ∨ B) N C ' (A N C) ∨ (B N C), (A N B) ∨ C ' (A ∨ C) N(B ∨ C) ;
  7.   (A ∨ B) ∨ C ' A ∨ (B ∨ C), (A N B) N C ' A N(B N C) .
Äîêàçàòåëüñòâî.
  1. ¬¬A ' A
     Âûâîäèìîñòü ñåêâåíöèè ¬¬ A ` A áûëà ïîêàçàíà â ïðèìåðå
     3.3. Äîêàçàòåëüñòâîì âûâîäèìîñòè ñåêâåíöèè A ` ¬¬ A ñëóæèò
     äåðåâî
                     A ` A         ¬A ` ¬A
                   A, ¬ A ` A     A, ¬ A ` ¬ A
                                                 (RA)
                         A, ¬ A `
                                    (+¬)
                         A ` ¬¬ A
          ¡¢
  2. A B ' ¬A ∨ B Ïîêàæåì ñíà÷àëà âûâîäèìîñòü ñåêâåíöèè
         ¡
     A ¢ B ` ¬A ∨ B . Âî ïåðâûõ,
                              ¡        ¡
                A ` A      A ¢B ` A ¢B         ¡
                         ¡                 (− ¢)
                      A ¢ B, A ` B
                           ¡                       (+∨) ,
                       A ¢ B, A ` ¬A ∨ B
       à âî âòîðûõ 
                             ¬A ` ¬A
                                            (+∨) .
                            ¬A ` ¬A ∨ B

Страницы