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

3. Õàðàêòåðèçàöèÿ ôîðìóë àëãåáðû âûñêàçûâàíèé                                29


   Ìû âèäèì, ÷òî åñëè ïîëó÷åíû ÊÍÔ [ÄÍÔ] ôîðìóëû, òî å¼ ïðî-
âåðêà íà òàâòîëîãè÷íîñòü [ïðîòèâîðå÷èâîñòü] ñòàíîâèòñÿ òðèâèàëüíîé.
Ïðîâåðêà âûïîëíèìîñòè ìîæåò áûòü ïðîèçâåäåíà, ñêàæåì, ñ èñïîëü-
çîâàíèåì àëãîðèòìà Äåâèñà è Ïàòíåìà êîòîðûé ìû íå áóäåì çäåñü
ðàññìàòðèâàòü18 .

Ìåòîä ðåäóêöèè. Ìåòîä ðåäóêöèè îñíîâàí íà ðåøåíèè ëîãè÷åñêèõ
óðàâíåíèé. Îí îñîáåííî óäîáåí, åñëè ôîðìóëà ñîäåðæèò ìíîãî çíàêîâ
èìïëèêàöèè.
    Ïóñòü íåîáõîäèìî ïðîâåðèòü óñëîâèå A ∈ T. Åñòåñòâåííî ïðåäïî-
ëîæèòü, ÷òî ôîðìóëà A áóäåò ôàëüñèôèöèðîâàòüñÿ íà íåáîëüøîé äî-
ëå âîçìîæíûõ èíòåðïðåòàöèé. Òîãäà ðåøåíèå ëîãè÷åñêîãî óðàâíåíèÿ
|A| = 0, ñêîðåå âñåãî, íå ïðèâåä¼ò ê ðàññìîòðåíèþ çíà÷èòåëüíîãî ÷èñ-
ëà ëîãè÷åñêèõ óðàâíåíèé äëÿ ïîäôîðìóë A.
    Ïîêàæåì íà ïðèìåðå, êàê ðàáîòàåò ðàññìàòðèâàåìûé ìåòîä.
Ïðèìåð 1.8. Äîêàæåì ìåòîäîì ðåäóêöèè, ÷òî ôîðìóëà A = p ¡¢ (q ¡¢ p)
ÿâëÿåòñÿ òàâòîëîãèåé.
    Ïðåäïîëîæèì îáðàòíîå, ò.å. ÷òî â íåêîòîðîé èíòåðïðåòàöèè ôîð-
ìóëà A ôàëüñèôèöèðóåòñÿ. Ðåøàÿ ëîãè÷åñêîå óðàâíåíèå |A| = 0 ïî-
ëó÷àåì çíà÷åíèå ïðîïîçèöèîíàëüíîé ïåðåìåííîé p = 1 è óðàâíåíèå
    ¡
| q ¢ p | = 0. Ðåøàÿ ïîñëåäíåå óðàâíåíèå, íàõîäèì p = 0, ÷òî ïðî-
òèâîðå÷èò ðàíåå ïîëó÷åííîìó. Òàêèì îáðàçîì, ïðåäïîëîæåíèå |A| = 0
ïðèâîäèò ê ïðîòèâîðå÷èþ è, ñëåäîâàòåëüíî, â ñèëó ïðîèçâîëüíîñòè ðàñ-
ñìàòðèâàåìîé èíòåðïðåòàöèè, A ∈ T.

3.2 Ìåòîä ñåìàíòè÷åñêèõ òàáëèö

   Ìåòîä ñåìàíòè÷åñêèõ òàáëèö [1], ïðåäëîæåííûé â 50-õ ãîäàõ ïðî-
øëîãî âåêà Ý. Áåòîì, îáúåäèíÿåò ðàññìîòðåííûå âûøå ïîäõîäû. Íèæå
îïèñàí ïðîñòåéøèé âàðèàíò äàííîãî ìåòîäà, ïîçâîëÿþùèé îñóùåñòâ-
ëÿòü ïðîâåðêó ïðîèçâîëüíîé ïðîïîçèöèîíàëüíîé ôîðìû íà ïðèíàä-
ëåæíîñòü êëàññàì T, F, R, à òàêæå ðåøåíèÿ ïðîáëåìû äåäóêöèè.
   Êàæäàÿ ñåìàíòè÷åñêàÿ òàáëèöà ñîñòîèò èç äâóõ ñòîëáöîâ, êîòîðûå
ñîäåðæàò ôîðìóëû è èõ ïîäôîðìóëû. Ïðè ýòîì ôîðìóëû, îöåíèâàå-
ìûå êàê èñòèííûå, ïîìåùàþòñÿ â ëåâûé ñòîëáåö òàáëèöû, à îöåíèâàå-
ìûå êàê ëîæíûå  â ïðàâûé. Ìåòîä ñîñòîèò â ïîñëåäîâàòåëüíîì ðàñ-
ñìîòðåíèè ôîðìóë, ñîñòàâëÿþùèõ ñåìàíòè÷åñêóþ òàáëèöó è äåêîìïî-
çèöèè èõ íà ñîñòàâëÿþùèå ïîäôîðìóëû ñ ïîìîùüþ îïèñûâàåìûõ íèæå
ïðàâèë. Ïîñëå òîãî, êàê ôîðìóëà ïîäâåðãëàñü äåêîìïîçèöèè, ê å¼ àíà-
ëèçó áîëüøå íå âîçâðàùàþòñÿ. Ïðè ýòîì ìîæåò ïðîèçîéòè ðàñùåïëåíèå
  18 Åãî ìîæíî íàéòè, íàïðèìåð, â [12], [22] èëè ó÷åáíèêå Þ.Ë. Êàïèòîíîâîé ñ ñî-
àâòîðàìè ¾Ëåêöèè ïî äèñêðåòíîé ìàòåìàòèêå¿ (ÑÏá.: ÁÕÂ-Ïåòåðáóðã, 2004).