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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

|
¡
¢
A
¡
¢
B
A B
≡ |
A ≡ B
A, B A, B
| ≡
A ≡ B
A B B A
² A
A 2 A
A
A
A ∈ T
A
A
A
A ∈ F
A
Γ ² A
Γ A
32                            Ãëàâà 1. Êëàññè÷åñêàÿ àëãåáðà ëîãèêè

  ¡
| ¢.
                     ¡
                   A ¢B
               A   B

≡ |.
                       A≡B

                   A, B             A, B

| ≡.
                              A≡B

                   A      B     B    A

Cls. Åñëè íåêîòîðàÿ ôîðìóëà îêàçûâàåòñÿ â îáîèõ ñòîëáöàõ òàáëèöû,
     òî äàííàÿ òàáëèöà ñ÷èòàåòñÿ çàêðûòîé, ðàññìîòðåíèå å¼ çàâåðøà-
     åòñÿ è ïåðåõîäÿò ê àíàëèçó ôîðìóë â äðóãèõ íåçàêðûòûõ òàáëè-
     öàõ.

    Ïðè ïðîâåðêå ñïðàâåäëèâîñòè ² A íà÷èíàþò ñ ãëàâíîé òàáëèöû, â
ïðàâûé ñòîëáåö êîòîðîé ïîìåùàþò ôîðìóëó A, ò.å. ïîëàãàÿ, ÷òî 2 A.
Ýòî îçíà÷àåò, ÷òî ìû ïûòàåìñÿ íàéòè êîíòðìîäåëü äëÿ A. Åñëè â ðå-
çóëüòàòå ðàáîòû îïèñàííîãî àëãîðèòìà ãëàâíàÿ òàáëèöà îêàæåòñÿ çà-
êðûòîé, òî ýòî áóäåò îçíà÷àòü, ÷òî èñêîìîé êîíòðìîäåëè íå ñóùåñòâó-
åò, íàøå ïðåäïîëîæåíèå íå íàõîäèò ïîäòâåðæäåíèÿ è, òàêèì îáðàçîì,
óñòàíîâëåíî, ÷òî A ÿâëÿåòñÿ òàâòîëîãèåé. Åñëè æå àëãîðèòì îêîí÷èò
ðàáîòó, à íåêîòîðàÿ èç ïîäòàáëèö (ñîïîñòàâëåííûõ ëèñòüÿì ïîñòðîåí-
íîãî äåðåâà) îêàæåòñÿ íåçàêðûòîé, òî ýòà ïîäòàáëèöà è îïèøåò èñêî-
ìóþ êîíòðìîäåëü.
    Ïðîâåðÿÿ âêëþ÷åíèå A ∈ T îïèñàííûé àëãîðèòì ñòðîèò, êàê
íåòðóäíî âèäåòü, âñå èíòåðïðåòàöèè, íà êîòîðûõ ôîðìóëà A ìîæåò
ôàëüñèôèöèðîâàòüñÿ, îòáðàñûâàÿ ëèøü òå, ÷òî çàâåäîìî òàêîâûìè íå
ÿâëÿþòñÿ. Ñòðîãîãî äîêàçàòåëüñòâà ýòîãî ìû íå áóäåì ïðîâîäèòü.
    Çàìåòèì, ÷òî åñëè íà÷àòü ðàáîòó ñ ïîìåùåíèÿ ôîðìóëû A â ëåâûé
ñòîëáåö ãëàâíîé òàáëèöû, òî â ðåçóëüòàòå ðàáîòû àëãîðèòìà áóäåò ëèáî
îïðîâåðãíóòî ïðåäïîëîæåíèå î âûïîëíèìîñòè A (êîãäà ãëàâíàÿ òàá-
ëèöà îêàæåòñÿ çàêðûòîé) è, ñëåäîâàòåëüíî, ïîêàçàíî, ÷òî A ∈ F, ëèáî
íàéäåíû èñòèííîñòíûå çíà÷åíèÿ ïðîïîçèöèîíàëüíûõ ïåðåìåííûõ, ñî-
äåðæàùèõñÿ â ôîðìóëå A, ïðè êîòîðûõ îíà ïîëó÷àåò îöåíêó 1, ò.å.
óñòàíîâëåíà å¼ âûïîëíèìîñòü. Î÷åâèäíî òàêæå, ìåòîä ñåìàíòè÷åñêèõ
òàáëèö ìîæíî èñïîëüçîâàòü è äëÿ ïðîâåðêè ëîãè÷åñêîãî ñëåäîâàíèÿ
Γ ² A. Äëÿ ýòîãî íàäî íà÷àòü ñ ãëàâíîé òàáëèöû, ñîäåðæàùèé â ëåâîì
ñòîëáöå ôîðìóëû èç ìíîæåñòâà Γ, à â ïðàâîì  ôîðìóëó A.

Страницы