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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

A
F A ∈ F
F H
H
+
H
H
+
H
+
F ¬ F ¬ F
H
+
¤
S
I
S
A S
S
I
H
A ∈ Ax
Ax A Ax r A
P (x
1
, . . . , x
k
)
D
1
× . . . × D
k
D
i
i = 1, k
{ , }
A = ∃ xP (x)
¡
¢
∀ xP (x)
x ∈ D |D| = 1 A
72            Ãëàâà 2. Èñ÷èñëåíèÿ âûñêàçûâàíèé. Ãèëüáåðòîâñêèå ÈÂ


ïåðåìåííûõ, îò êîòîðûõ çàâèñèò ôîðìóëà A, èç íå¼ ìîæåò áûòü ïîëó-
÷åíà òîæäåñòâåííî ëîæíàÿ ôîðìóëà F (ïðè A ∈ F íèêàêèõ ïîäñòà-
íîâîê ïðîâîäèòü íå íàäî). Äîáàâèì F ê ñïèñêó àêñèîì H , îáðàçîâàâ
èñ÷èñëåíèå H + . Ïîíÿòíî, ÷òî âñå òåîðåìû H òàêæå áóäóò è òåîðåìàìè
H + .  ðåçóëüòàòå ïîëó÷àåì, ÷òî â H + òðèâèàëüíî âûâîäèìà ôîðìóëà
F è, ïîñêîëüêó ¬ F  òàâòîëîãèÿ, âûâîäèìà è ¬ F , ò.å. èñ÷èñëåíèå
H + ïðîòèâîðå÷èâî.                                                ¤

   Èíîãäà ñåìàíòè÷åñêóþ ïîëíîòó èñ÷èñëåíèÿ íàçûâàþò ïîëíîòîé â
øèðîêîì ñìûñëå , à ïîëíîòó ïî Ïîñòó  ïîëíîòîé â óçêîì ñìûñëå . Òà-
êèå íàçâàíèÿ ñâÿçàíû ñ òåì, ÷òî èç ïîëíîòû â óçêîì ñìûñëå ñëåäóåò
ïîëíîòà â øèðîêîì ïî îòíîøåíèþ ê äàííîìó ñâîéñòâó S . Äåéñòâè-
òåëüíî, ïóñòü íåïðîòèâîðå÷èâîå èñ÷èñëåíèå I ñåìàíòè÷åñêè íå ïîëíî,
íî êîððåêòíî îòíîñèòåëüíî ñâîéñòâà S . Ýòî îçíà÷àåò ñóùåñòâîâàíèå
ôîðìóëû A îáëàäàþùåé ñâîéñòâîì S , íî íåäîêàçóåìîé. Äîáàâèâ å¼
ê àêñèîìàì, ïîëó÷àåì êîððåêòíîå îòíîñèòåëüíî S è, â ñèëó äàííîé
êîððåêòíîñòè, íåïðîòèâîðå÷èâîå èñ÷èñëåíèå. Îòñþäà ñëåäóåò, ÷òî èñ-
õîäíîå èñ÷èñëåíèå I íå ïîëíî ïî Ïîñòó
   Âîîáùå, ïîëíîòà ïî Ïîñòó ÿâëÿåòñÿ î÷åíü ñèëüíûì ñâîéñòâîì èñ-
÷èñëåíèÿ: ñåìàíòè÷åñêè ïîëíûå èñ÷èñëåíèÿ, êàê ïðàâèëî, íåïîëíû ïî
Ïîñòó15 .
   Ïðîáëåìà ðàçðåøèìîñòè èñ÷èñëåíèÿ ñîñòîèò â îïðåäåëåíèè íàëè-
÷èÿ èëè îòñóòñòâèÿ àëãîðèòìà äëÿ óñòàíîâëåíèÿ ôàêòà âûâîäèìîñòè
ïðîèçâîëüíîé ôîðìóëû èç ïðîèçâîëüíîãî (âîçìîæíî ïóñòîãî) íàáîðà
ãèïîòåç.  ñèëó ñåìàíòè÷åñêîé ïîëíîòû î÷åâèäíî ïîëîæèòåëüíîå ðå-
øåíèå âîïðîñà î ðàçðåøèìîñòè èñ÷èñëåíèÿ H : äëÿ ýòîãî ìîæíî èñ-
ïîëüçîâàòü àëãîðèòìû â ï. 3 ãëàâû 1.

3.4 Íåçàâèñèìîñòü ñèñòåìû àêñèîì

    Àêñèîìà A ∈ Ax íåêîòîðîãî ëîãè÷åñêîãî èñ÷èñëåíèÿ íåçàâèñèìà
(â ñèñòåìå àêñèîì Ax), åñëè A íå ìîæåò áûòü âûâåäåíà èç Ax r A.
    Äîêàçàòåëüñòâà íåçàâèñèìîñòè ñõåì àêñèîì íåêîòîðîãî ëîãè÷åñêî-
ãî èñ÷èñëåíèÿ îáû÷íî ïðîâîäÿò ïðèìåíÿÿ êîíå÷íûå ìíîãîçíà÷íûå ëî-
ãèêè . Äëÿ ýòîãî ðàññìàòðèâàþò ìíîæåñòâî èñòèííîñòíûõ çíà÷åíèé
 15 Ýòî îòíîñèòñÿ, íàïðèìåð, ê êëàññè÷åñêîìó èñ÷èñëåíèþ ïðåäèêàòîâ (ÈÏ).
  Ïðåäèêàòîì íàçûâàåòñÿ ôóíêöèÿ P (x1 , . . . , xk ), îïðåäåë¼ííàÿ íà äåêàðòîâîì
ïðîèçâåäåíèè D1 × . . . × Dk íåïóñòûõ ìíîæåñòâ Di , i = 1, k è ïðèíèìàþùàÿ çíà-
÷åíèÿ èç {0, 1}. Êëàññè÷åñêîå ÈÏ íåïðîòèâîðå÷èâî (Ãèëüáåðò è Àêêåðìàí, 1928),
ñåìàíòè÷åñêè ïîëíî (üäåëü, 1930), íî íå ïîëíî ïî Ïîñòó. Íàïðèìåð, ôîðìóëà
               ¡
A = ∃ xP (x) ¢ ∀ xP (x) íåâûâîäèìà â ÈÏ, íî èñòèíà â îäíîýëåìåíòíîé ìîäåëè
(x ∈ D, |D| = 1), è, ñëåäîâàòåëüíî, äîáàâëåíèå A ê àêñèîìàì ÈÏ íå ïðèâîäèò ê
ïðîòèâîðå÷èâîé òåîðèè (à ëèøü ê ñóæåíèþ ìíîæåñòâà ìîäåëåé).

Страницы