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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

F = A
F
F = ¬ G F = G
¡
¢
H
F ' F (A|B) ¤
H
H
2
H
2
H [H] = T
`
H
A ⇔ ²
2
A .
H
`
H
A ⇒ ²
2
A ²
2
A ⇒ `
H
A
2
H
H
H
A
`
H
A ⇒ ²
2
A
64          Ãëàâà 2. Èñ÷èñëåíèÿ âûñêàçûâàíèé. Ãèëüáåðòîâñêèå ÈÂ


Äîêàçàòåëüñòâî. Ïóñòü õîòÿ áû îäíà ïîäñòàíîâêà ôàêòè÷åñêè ïðîèç-
âîäèòñÿ, èíà÷å äîêàçûâàòü íå÷åãî.
   Åñëè F = A, òî óòâåðæäåíèå òåîðåìû òðèâèàëüíî. Èíà÷å ïðèìå-
íÿåì ïðèíöèï èíäóêöèè ïî ïîñòðîåíèþ ôîðìóëû F . Áàçèñ èíäóêöèè
îáåñïå÷èâàåòñÿ ïðåäûäóùèì ñëó÷àåì. Øàã èíäóêöèè ðàñïàäàåòñÿ íà
                                  ¡
2 ïîäñëó÷àÿ: F = ¬ G è F = G ¢ H . Òðåáóåìàÿ ýêâèâàëåíòíîñòü
F ' F (A|B) ñëåäóåò èç èíäóêòèâíîãî ïðåäïîëîæåíèÿ è ëåììû 2.2. ¤
   Òåîðåìà î çàìåíå ïîçâîëÿåò óñòàíàâëèâàòü îäíè âûâîäèìîñòè íà
îñíîâàíèè äðóãèõ.


3 Ìåòàòåîðèÿ ÈÂ H
   Êàê óæå óêàçûâàëîñü, ìåòàòåîðèÿ èçó÷àåò ñâîéñòâà äàííîãî èñ÷èñ-
ëåíèÿ èëè ôîðìàëüíîé òåîðèè. Ê òàêîâûì, â ïåðâóþ î÷åðåäü, îòíî-
ñÿòñÿ êîððåêòíîñòü è íåïðîòèâîðå÷èâîñòü, ðàçëè÷íûå âèäû ïîëíîòû
èñ÷èñëåíèÿ, ïðîáëåìà ðàçðåøèìîñòè, íåçàâèñèìîñòü ñèñòåì àêñèîì è
ïðàâèë âûâîäà.

3.1 Êîððåêòíîñòü è íåïðîòèâîðå÷èâîñòü

   Èñ÷èñëåíèå H ñòðîèëîñü ñ öåëüþ ðåãóëÿðèçàöèè ïîëó÷åíèÿ òàâòî-
ëîãèé êëàññè÷åñêîé àëãåáðû ëîãèêè. Áûëî ïîêàçàíî, ÷òî ïî êðàéíåé
ìåðå íåêîòîðûå òàâòîëîãèè C2 ÿâëÿþòñÿ òåîðåìàìè H . Êðèòåðèåì
ïîëíîãî óñïåõà íàøåãî ïîñòðîåíèÿ áûëî áû ñîâïàäåíèå ìíîæåñòâ òàâ-
òîëîãèé C2 è ôîðìóë, âûâîäèìûõ H , ÷òî çàïèñûâàåòñÿ êàê [H] = T
èëè
                         `H A ⇔ ²C2 A .
   Íèæå äîêàçûâàåòñÿ, ÷òî èñ÷èñëåíèå H äåéñòâèòåëüíî óäîâëåòâî-
ðÿåò äàííîìó óñëîâèþ. Äëÿ ýòîãî ñíà÷àëà ïîêàæåì åãî äîñòàòî÷íîñòü
`H A ⇒ ²C2 A, à çàòåì íåîáõîäèìîñòü ²C2 A ⇒ `H A. Ïåðâîå
ñâîéñòâî âûðàæàåò êîððåêòíîñòü èëè ñåìàíòè÷åñêóþ ïðèãîäíîñòü , à
âòîðîå  ñåìàíòè÷åñêóþ ïîëíîòó (ïî îòíîøåíèþ ê ñâîéñòâó ôîðìóë
¾áûòü òàâòîëîãèåé â C2 ¿) èñ÷èñëåíèÿ H . Î÷åâèäíî, ïîñëåäíåå ñëå-
äîâàíèå íå áóäåò òðèâèàëüíûì, åñëè òîëüêî íå âñå ôîðìóëû îêàæóòñÿ
âûâîäèìûìè â H . Ýòî íå êàñàåòñÿ ïåðâîãî ñîîòíîøåíèÿ, ò.ê. ìû çíàåì,
÷òî íå âñå ôîðìóëû àëãåáðû ëîãèêè ÿâëÿþòñÿ òàâòîëîãèÿìè.
   Êîððåêòíîñòü È H ïî÷òè î÷åâèäíà.
Òåîðåìà 2.5 (Î êîððåêòíîñòè ÈÂ H ). Äëÿ ëþáîé ôîðìóëû A ñïðà-
âåäëèâî `H A ⇒ ²C2 A.

Страницы