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

30                            Ãëàâà 1. Êëàññè÷åñêàÿ àëãåáðà ëîãèêè


òàáëèöû íà äâå ïîäòàáëèöû, êàæäàÿ èç êîòîðûõ òîæå ìîæåò áûòü ðàñ-
ùåïëåíà è ò.ä. Òàêèì îáðàçîì ïîëó÷àåòñÿ äâîè÷íîå äåðåâî, âåðøèíàì
êîòîðîãî ñîïîñòàâëåíû ñåìàíòè÷åñêèå òàáëèöû. Òàáëèöó, ñîîòâåòñòâó-
þùóþ êîðíþ ýòîãî äåðåâà, ñ êîòîðîé íà÷àëîñü åãî ïîñòðîåíèå, íàçûâà-
þò ãëàâíîé .
    Åñëè â ðåçóëüòàòå ïîñòðîåíèÿ óêàçàííîãî äåðåâà êàêàÿ-íèáóäü ôîð-
ìóëà îêàçûâàåòñÿ è â ïðàâîì, è â ëåâîì ñòîëáöå íåêîòîðîé òàáëèöû, òî
ýòî îçíà÷àåò, ÷òî ñèòóàöèÿ, îïèñûâàåìàÿ äàííîé òàáëèöåé íåâîçìîæ-
íà. Òàêàÿ òàáëèöà íàçûâàåòñÿ çàêðûòîé è ðàáîòà ñ íåé ïðåêðàùàåò-
ñÿ. Àëãîðèòì ìåòîäà ñåìàíòè÷åñêèõ òàáëèö íà÷èíàåò ðàáîòó ñ ãëàâíîé
òàáëèöû è çàêàí÷èâàåò ðàáîòó, êîãäà äàëüíåéøèé ðàçáîð ôîðìóë âî
âñåõ ïîëó÷åííûõ òàáëèöàõ çàâåðø¼í. Ýòî áóäåò èìåòü ìåñòî, ëèáî êî-
ãäà âñå ïîëó÷åííûå òàáëèöû îêàæóòñÿ çàêðûòûìè, è òîãäà çàêðûòîé
ñ÷èòàåòñÿ ãëàâíàÿ òàáëèöà, ëèáî êîãäà äàëüíåéøàÿ äåêîìïîçèöèÿ âñåõ
ñîäåðæàùèõñÿ â íèõ ôîðìóë áóäåò íåâîçìîæíà (ïîäòàáëèöû ñîäåðæàò
èñêëþ÷èòåëüíî ïðîïîçèöèîíàëüíûå ïåðåìåííûå) è õîòÿ áû îäíà èç òàá-
ëèö îêàæåòñÿ íåçàêðûòîé.
    ßñíî, ÷òî â ðàññìàòðèâàåìîì âàðèàíòå ìåòîäà äàííûé àëãîðèòì
âñåãäà çàêîí÷èò ðàáîòó çà êîíå÷íîå ÷èñëî øàãîâ.
    Äàëåå ïðèâåäåíû ïðàâèëà ðàçáîðà ôîðìóë. Çäåñü ïðåäïîëàãàåòñÿ,
÷òî â òåõ ïðàâèëàõ, êîòîðûå ïðèâîäÿò ê ðàñùåïëåíèþ òàáëèöû, ïîëó-
÷àåìûå ïîäòàáëèöû äóáëèðóþò ñîäåðæàíèå ðàñùåïëÿåìîé çà èñêëþ÷å-
íèåì ðàññìàòðèâàåìîé ôîðìóëû, êîòîðàÿ â ïîäòàáëèöàõ îòñóòñòâóåò,
è äâóõ å¼ ïîäôîðìóë, êàæäàÿ èç êîòîðûõ ïîìåùàåòñÿ â òîò èëè èíîé
ñòîëáåö òîëüêî îäíîé èç ïîäòàáëèö. Íåñêîëüêî êîðîòêèõ ôîðìóë áó-
äåì èíîãäà ïèñàòü â îäíîé ñòðîêå òàáëèöû ÷åðåç çàïÿòóþ. Ôîðìóëó, ê
êîòîðîé ïðèìåíÿåòñÿ äàííîå ïðàâèëî áóäåì ïîä÷¼ðêèâàòü.


           Ïðàâèëà àíàëèçà ñåìàíòè÷åñêèõ òàáëèö

¬| è |¬ . Åñëè ôîðìóëà ¬ A íàõîäèòñÿ â ëåâîì [ïðàâîì] ñòîëáöå òàá-
     ëèöû, òî â ïðàâûé [ëåâûé] å¼ ñòîëáåö ïîìåùàåòñÿ ôîðìóëà A,
     ÷òî ñèìâîëè÷åñêè ìû çàïèøåì êàê
               ¬A                              ¬A
                            è
                    A                     A

N |. Åñëè ôîðìóëà A N B íàõîäèòñÿ â ëåâîì ñòîëáöå òàáëèöû, òî â
     ýòîò æå ñòîëáåö ïîìåùàþòñÿ ôîðìóëû A è B :
               ANB
                A, B