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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

|A
¡
¢
C|
|F | =
F
¤
A, A
¡
¢
(B ∨ C), B
¡
¢
D, C
¡
¢
D ² D
A ∨ X, B ∨ ¬ X ² A ∨ B
A, ¬ A ∨ B ² B ¬ A ∨ B, ¬ B ∨ C ² ¬ A ∨ C
A
A Γ
2
A ∈ T
A
26                             Ãëàâà 1. Êëàññè÷åñêàÿ àëãåáðà ëîãèêè

                                       ¡
       Òàêèì îáðàçîì, êîíñåêâåíò |A ¢ C| èñòèíåí â îáîèõ äàííûõ ñëó-
       ÷àÿõ, ò.å. îïÿòü |F | = 1.  ñèëó ïðîèçâîëüíîñòè ðàññìîòðåííîé
       èíòåðïðåòàöèè F ÿâëÿåòñÿ òàâòîëîãèåé, ÷òî îçíà÷àåò ñïðàâåäëè-
       âîñòü äîêàçûâàåìîãî ëîãè÷åñêîãî ñëåäîâàíèÿ.                  ¤

              ¡            ¡      ¡
     8. A, A ¢(B ∨ C), B ¢ D, C ¢ D ² D  äîêàçàòåëüñòâî ìåòîäîì
        ðàçáîðà ñëó÷àåâ.
     9. A ∨ X, B ∨ ¬ X ² A ∨ B  îáîáù¼ííîå ïðàâèëî ðåçîëþöèé.
        Ê ýòîìó î÷åíü ìîùíîìó ïðàâèëó ñâîäÿòñÿ ìíîãèå äðóãèå ïðàâèëà
        ëîãè÷åñêîãî âûâîäà. Íàïðèìåð, ïðàâèëà çàêëþ÷åíèÿ ïî ïîëîæè-
        òåëüíîìó ñïîñîáó è ñèëëîãèçìà ìîãóò áûòü ïðèâåäåíû ê âèäó
              A, ¬ A ∨ B ² B   è   ¬ A ∨ B, ¬ B ∨ C ² ¬ A ∨ C
       ñîîòâåòñòâåííî, ò.å. ÿâëÿþòñÿ ÷àñòíûìè ñëó÷àÿìè îáîáù¼ííîãî
       ïðàâèëà ðåçîëþöèé.
   Èç òåîðåìû 1.2 ñëåäóåò, ÷òî âî âñåõ ïðèâåä¼ííûõ âûøå ïðèìåðàõ
ëîãè÷åñêîãî ñëåäîâàíèÿ âìåñòî äàííîãî ñèìâîëà âûñêàçûâàíèÿ ìîæíî
ïîäñòàâèòü ïðîèçâîëüíóþ ôîðìóëó.
   Âìåñòå ñ ïðàâèëàìè îáðàçîâàíèÿ ôîðìóë, ëîãè÷åñêèå ïðàâèëà ñî-
ñòàâëÿþò ñèíòàêñèñ ëîãèêè.


3 Õàðàêòåðèçàöèÿ ôîðìóë àëãåáðû âûñêàçûâàíèé
3.1 Ýëåìåíòàðíûå ìåòîäû õàðàêòåðèçàöèè

   Ôóíäàìåíòàëüíîé ïðîáëåìîé ëîãèêè ÿâëÿåòñÿ õàðàêòåðèçàöèÿ
ôîðìóë, ò.å. óñòàíîâëåíèå, ê êàêîìó èç íåêîòîðûì îáðàçîì âûäåëåí-
íûõ êëàññîâ ôîðìóë ïðèíàäëåæèò äàííàÿ ôîðìóëà A. Óêàçàííóþ
ïðîáëåìó íàçûâàþò ïðîáëåìîé ðàçðåøèìîñòè . Ê íåé ïðèìûêàåò
ïðîáëåìà äåäóêöèè , ñîñòîÿùàÿ â ïðîâåðêå ñïðàâåäëèâîñòè ëîãè÷åñêîãî
ñëåäîâàíèÿ A èç íåêîòîðîãî íàáîðà ôîðìóë Γ. Äàííûå ïðîáëåìû
ÿâëÿþòñÿ àëãîðèòìè÷åñêèìè, ÷òî îçíà÷àåò òðåáîâàíèå âûÿñíèòü,
ñóùåñòâóåò ëè àëãîðèòì, âû÷èñëÿþùèé ñîîòâåòñòâóþùåå ñâîéñòâî äëÿ
ïðîèçâîëüíîé ôîðìóëû.
   Óïîìÿíóòûìè êëàññàìè ëîãèêè C2 ÿâëÿþòñÿ êëàññû òàâòîëîãèé,
ïðîòèâîðå÷èé è íåéòðàëüíûõ ôîðìóë. ßñíî, ÷òî çäåñü õàðàêòåðèçà-
öèÿ ìîæåò áûòü ñâåäåíà ê âû÷èñëåíèþ ïðåäèêàòà ïðèíàäëåæíîñòè
A ∈ T, ò.ê. èìåÿ ñîîòâåòñòâóþùèé àëãîðèòì, ëåãêî ïîëó÷èòü êàê ñïî-
ñîáû îïðåäåëåíèÿ ïðèíàäëåæíîñòè ôîðìóëû A ê îñòàëüíûì êëàññàì,
òàê è äëÿ ïðîáëåìû äåäóêöèè.

Страницы