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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

² P P = ((p
¡
¢
q)
¡
¢
p)
¡
¢
p
P
((p
¡
¢
q)
¡
¢
p)
¡
¢
p
(p
¡
¢
q)
¡
¢
p p
p p
p
p
¡
¢
q
p q
P
² P
(q
¡
¢
r)
¡
¢
(p ∨ q
¡
¢
p ∨ r) .
(q
¡
¢
r)
¡
¢
(p ∨ q
¡
¢
p ∨ r)
q
¡
¢
r p ∨ q
¡
¢
p ∨ r
p ∨ q p ∨ r
p, r
p ∨ q p
r r
p ∨ q p
r, q
p p
r, q
q p, r, q
¡
¢
|
q
¡
¢
r ∨|
p ∨ q
3. Õàðàêòåðèçàöèÿ ôîðìóë àëãåáðû âûñêàçûâàíèé                    33


  Ïðîäåìîíñòðèðóåì ðàáîòó ìåòîäà íà ïðèìåðàõ. Ôîðìóëó, âûçâàâ-
øóþ çàêðûòèå òàáëèöû, ìû áóäåì ïîä÷¼ðêèâàòü äâóìÿ ÷åðòàìè.
Ïðèìåð 1.9.  1. Äîêàæåì çàêîí Ïèðñà (ñì. ï. 16 ïðèìåðà 1.4).
                                           ¡    ¡   ¡
    Äëÿ äîêàçàòåëüñòâà ² P , ãäå P = ((p ¢ q) ¢ p) ¢ p ïîñòðîèì
    (ãëàâíóþ) ñåìàíòè÷åñêóþ òàáëèöó è ïîìåñòèì ôîðìóëó P â å¼
    ïðàâûé ñòîëáåö.
    Ïðèìåíåíèå ïðàâèë ìåòîäà ïðèâåä¼ò ê ñëåäóþùåìó ðåçóëüòàòó.
                                        ¡    ¡   ¡
                                   ((p ¢ q) ¢ p) ¢ p
                        ¡   ¡
                    (p ¢ q) ¢ p    p
                       p    p              p
                                               ¡
                                           p ¢q
                                      p    q


    Âñå ïîäòàáëèöû ïîëó÷èâøåãîñÿ äåðåâà òàáëèö îêàçàëèñü çàêðû-
    òûìè, îòêóäà ñëåäóåò îòñóòñòâèå êîíòðìîäåëè äëÿ P , ÷òî ýêâè-
    âàëåíòíî ² P .

  2. Äîêàæåì òîæäåñòâåííóþ èñòèííîñòü ôîðìóëû
                           ¡    ¡       ¡
                        (q ¢ r) ¢(p ∨ q ¢ p ∨ r) .

    Ïðèìåíÿÿ ê äàííîé ôîðìóëå âûøåîïèñàííûé àëãîðèòì, ïîëó÷èì
    ñëåäóþùèé ðåçóëüòàò.
                            ¡      ¡     ¡
                         (q ¢ r) ¢(p ∨ q ¢ p ∨ r)
                   ¡            ¡¢
                 q ¢r    p∨q p∨r
                 p∨q     p∨r
                         p, r
                                   p∨q      p
           p∨q     p
             r    r                        r, q
                             p    p               q    p, r, q
                                  r, q
                                                     ¡
    Ïåðâîå ðàñùåïëåíèå ïðîèçîøëî çäåñü ïî ïðàâèëó ¢ |, ïðèìåí¼í-
                       ¡¢
    íîìó ê ôîðìóëå q r, à âòîðîå  ïî ïðàâèëó ∨|, ïðèìåí¼ííîìó
    ê ôîðìóëå p ∨ q âî âòîðîé (ïðàâîé) ïîäòàáëèöå, ïîëó÷åííîé ïî-
    ñëå ïåðâîãî ðàñùåïëåíèÿ. Âñå ïîëó÷åííûå ïîäòàáëèöû îêàçàëèñü
    çàêðûòûìè, ÷òî ÿâëÿåòñÿ äîêàçàòåëüñòâîì ñïðàâåäëèâîñòè ïðî-
    âåðÿåìîãî óòâåðæäåíèÿ.

Страницы