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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

D
1
D
2
res (D
1
, D
2
) = ∅
D
1
= p ∨ q ∨ r, D
2
= ¬ p ∨ ¬ q ∨ s
res
p
(D
1
, D
2
) = q ∨ r ∨ ¬ q ∨ s,
res
q
(D
1
, D
2
) = p ∨ r ∨ ¬ p ∨ s,
res
r
(D
1
, D
2
) = ∅ .
res (D
1
, D
2
) 6= ∅
D
1
N D
2
∼ D
1
N D
2
N res (D
1
, D
2
)
{D
1
, . . . , D
k
} Γ D
Γ
D
1
, . . . , D
l
D
l
= D
Γ
RR
D Γ
Γ = { p ∨ q, p ∨ r, ¬ q ∨ ¬ r, ¬ p}
p ∨ q Γ r res
p
((2), (4))
p ∨ r Γ p res
r
((2), (5))
¬ q∨¬ r Γ ¬ r res
q
((3), (6))
¬ p Γ ¬ q res
r
((3), (8))
p∨¬ r res
q
((1), (3)) ¬ r res
p
((4), (5))
q res
p
((1), (4)) ¬ q res
p
((4), (7))
p∨ ¬ q res
r
((2), (3)) ∅ res
p
((4), (9))
A
RR
Γ
Γ
36                                 Ãëàâà 1. Êëàññè÷åñêàÿ àëãåáðà ëîãèêè


    ßñíî, ÷òî äèçúþíêòû D1 è D2 ìîãóò èìåòü íå îäíó ðåçîëüâåí-
òó, à ìîãóò è íå èìåòü èõ ñîâñåì.  ïîñëåäíåì ñëó÷àå áóäåì ïèñàòü
res (D1 , D2 ) = ∅ (íå ïóòàòü ñ ïóñòûì äèçúþíêòîì!).
Ïðèìåð 1.10. Ïóñòü20 D1 = p ∨ q ∨ r, D2 = ¬ p ∨ ¬ q ∨ s. Òîãäà
                      resp (D1 , D2 ) = q ∨ r ∨ ¬ q ∨ s,
                      resq (D1 , D2 ) = p ∨ r ∨ ¬ p ∨ s,
                             resr (D1 , D2 ) = ∅ .
   Ïóñòü res (D1 , D2 ) 6= ∅. Òîãäà, êàê ëåãêî âèäåòü, ÷òî èìååò ìåñòî
ýêâèâàëåíòíîñòü D1 N D2 ∼ D1 N D2 N res (D1 , D2 ).
   Ðàññìîòðèì         íåêîòîðîå       íåïóñòîå   ìíîæåñòâî     äèçúþíêòîâ
{D1 , . . . , Dk }, êîòîðîå îáîçíà÷èì Γ. Äèçúþíêò D íàçûâàåòñÿ
ðåçîëþòèâíûì ñëåäñòâèåì ìíîæåñòâà äèçúþíêòîâ Γ, åñëè ñó-
ùåñòâóåò êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü D1 , . . . , Dl äèçúþíêòîâ
òàêàÿ, ÷òî Dl = D, è êàæäûé ýëåìåíò ýòîé ïîñëåäîâàòåëüíîñòè
ëèáî ïðèíàäëåæèò Γ, ëèáî ñëåäóåò èç êàêèõ-ëèáî ïðåäûäóùèõ ýëå-
ìåíòîâ ïî ïðàâèëó RR. Óêàçàííóþ ïîñëåäîâàòåëüíîñòü íàçûâàþò
ðåçîëþòèâíûì âûâîäîì äèçúþíêòà D èç ìíîæåñòâà Γ.
Ïðèìåð 1.11. Ïîñòðîèì âñåâîçìîæíûå ðåçîëþòèâíûå ñëåäñòâèÿ èç
ìíîæåñòâà äèçúþíêòîâ Γ = { p ∨ q, p ∨ r, ¬ q ∨ ¬ r, ¬ p}. Ïîëó÷àåìûå
äèçúþíêòû áóäåì íóìåðîâàòü ÷èñëàìè â êðóãëûõ ñêîáêàõ è äàâàòü ïî-
ÿñíåíèÿ ê èõ ïîÿâëåíèþ.
      (1) p ∨ q        ýëåìåíò Γ           (8)     r  resp ((2), (4))
      (2) p ∨ r        ýëåìåíò Γ           (9)     p  resr ((2), (5))
      (3) ¬ q∨¬ r  ýëåìåíò Γ               (10)    ¬ r  resq ((3), (6))
      (4) ¬ p          ýëåìåíò Γ           (11)    ¬ q  resr ((3), (8))
      (5) p∨¬ r        resq ((1), (3))     (12)    ¬ r  resp ((4), (5))
      (6) q            resp ((1), (4))     (13)    ¬ q  resp ((4), (7))
      (7) p∨¬ q        resr ((2), (3))     (14)    ∅  resp ((4), (9))
   Ìåòîä ðåçîëþöèé äëÿ ïðîâåðêè âûïîëíèìîñòè äàííîé ôîðìóëû
A ñîñòîèò â ïîëó÷åíèè å¼ ÊÍÔ è ïîñëåäóþùåé ïðîâåðêå ïîëó÷åííî-
ãî ìíîæåñòâà äèçúþíêòîâ íà ñåìàíòè÷åñêóþ ïðîòèâîðå÷èâîñòü. Òàêàÿ
ïðîâåðêà òðåáóåò, âîîáùå ãîâîðÿ, ïîðîæäåíèÿ âñåõ ðåçîëüâåíò äàííîãî
ìíîæåñòâà äèçúþíêòîâ. Îòìåòèì, ÷òî íàðÿäó ñ ïðàâèëîì êðîìå ïðàâè-
ëà RR â ìåòîäå ðåçîëþöèé èñïîëüçóåòñÿ ïðàâèëî ñêëåéêè , óäàëÿþùåå
ïîâòîðíûå âõîæäåíèÿ ëèòåðàëîâ â äèçúþíêò.
Òåîðåìà 1.5 (Î ïîëíîòå ìåòîäà ðåçîëþöèé). Ìíîæåñòâî äèçú-
þíêòîâ Γ ñåìàíòè÷åñêè ïðîòèâîðå÷èâî, åñëè è òîëüêî åñëè ïóñòîé
äèçúþíêò ÿâëÿåòñÿ ðåçîëþòèâíûì ñëåäñòâèåì Γ.
 20 Ïðèìåðû äàííîãî ðàçäåëà âçÿòû èç [12] è [20].

Страницы