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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

∼
A
2
2
¬¬ p ∼ p Inv
0
p ≡ q ∼ (p
¡
¢
q) N(q
¡
¢
p)
p
¡
¢
q ∼ ¬ p ∨ q ∼ ¬ (p N ¬ q)
¬ (p ∨ q) ∼ ¬ p N ¬ q DeM1
¬ (p N q) ∼ ¬ p ∨ ¬ q DeM2
(p ∨ q) N r ∼ p N r ∨ q N r Dtr1
p N q ∨ r ∼ (p ∨ r) N(q ∨ r) Dtr2
DeM1
¬ (p ∨ q) ¬ p N ¬ q
p = q =
¤
F X
Y F
X F (X | Y )
F A
B F A
A ∼ B ⇒ F ∼ F (A | B) .
k
F
1
◦
k = 0 F
2
◦
k > 0
F = A
F
F = ¬ G, F = G ∨ H, F = G N H, F = G
¡
¢
H F = G ≡ H .
20                               Ãëàâà 1. Êëàññè÷åñêàÿ àëãåáðà ëîãèêè


âèäåòü, ÷òî ðàâíîñèëüíîñòü ∼ ÿâëÿåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè
íà ìíîæåñòâå A ôîðìóë ëîãèêè C2  å¼ ñâîéñòâà ðåôëåêñèâíîñòè,
ñèììåòðè÷íîñòè è òðàíçèòèâíîñòè íàñëåäóþòñÿ àíàëîãè÷íûõ ñâîéñòâ
ðàâåíñòâà îöåíîê.
Ëåììà 1.2. Â C2 ñïðàâåäëèâû, íàïðèìåð, ñëåäóþùèå ðàâíîñèëüíî-
ñòè:
     1.   ¬¬ p ∼ p  Inv 0 ;
                       ¡        ¡
     2.   p ≡ q ∼ (p ¢ q) N(q ¢ p) ;
             ¡¢
     3.   p q ∼ ¬ p ∨ q ∼ ¬ (p N ¬ q) ;
     4.   ¬ (p ∨ q) ∼ ¬ p N ¬ q  DeM 1;
     5.   ¬ (p N q) ∼ ¬ p ∨ ¬ q  DeM 2;
     6.   (p ∨ q) N r ∼ p N r ∨ q N r  Dtr1;
     7.   p N q ∨ r ∼ (p ∨ r) N(q ∨ r)  Dtr2.
Äîêàçàòåëüñòâî ýòèõ ðàâíîñèëüíîñòåé ëåãêî ïðîâîäèòñÿ ëèáî îïèðà-
ÿñü íà çàêîíû èç ïðèìåðà 1.4, ëèáî ðàññìîòðåíèåì âàðèàíòîâ èñòèííî-
ñòè/ëîæíîñòè ñîñòàâëÿþùèõ èõ ôîðìóë. Íàïðèìåð, äëÿ çàêîíà DeM 1
ðàññóæäåíèÿ òàêîâû: ôîðìóëû ¬ (p ∨ q) è ¬ p N ¬ q îäíîâðåìåííî èñ-
òèííû ïðè p = q = 0 è îäíîâðåìåííî ëîæíû ïðè îñòàëüíûõ çíà÷åíèÿõ
ïðîïîçèöèîíàëüíûõ ïåðåìåííûõ.                                    ¤

   Ïðèâåä¼ííûé ñïèñîê ýêâèâàëåíòíîñòåé ìîæåò áûòü áåç òðóäà ïðî-
äîëæåí ÷èòàòåëåì.
   Ïóñòü ôîðìóëà F ñîäåðæèò ïîäôîðìóëó X . Ðåçóëüòàò îäíîâðåìåí-
íîé ïîäñòàíîâêè ôîðìóëû Y â ôîðìóëó F âìåñòî íåêîòîðûõ âõîæ-
äåíèé ïîäôîðìóëû X áóäåì îáîçíà÷àòü F (X | Y ).
Òåîðåìà 1.2 (Î çàìåíå ëîãè÷åñêè ýêâèâàëåíòíûõ). Ïóñòü F , A
è B  ôîðìóëû àëãåáðû ëîãèêè, ïðè÷åì F ñîäåðæèò A â êà÷åñòâå
ïîäôîðìóëû. Òîãäà
                        A ∼ B ⇒ F ∼ F (A | B) .
Äîêàçàòåëüñòâî. Ïðîâåä¼ì åãî èíäóêöèåé ïî ÷èñëó k ñâÿçîê ôîðìó-
ëû F (ò.å. ïî å¼ äëèíå).
   1◦ . Áàçèñ èíäóêöèè ( k = 0).  ýòîì ñëó÷àå ôîðìóëà F åñòü ïðîïî-
çèöèîíàëüíàÿ ïåðåìåííàÿ, ò.å. îíà èìååò åäèíñòâåííóþ (ñîáñòâåííóþ)
ïîäôîðìóëó  ñàìó ñåáÿ è óòâåðæäåíèÿ òåîðåìû î÷åâèäíî.
   2◦ . Øàã èíäóêöèè ( k > 0). Ñëó÷àé ñîáñòâåííîé ïîäôîðìóëû
( F = A ) ñîâïàäàåò ñ ðàññìîòðåííûì âûøå. Èíà÷å, â çàâèñèìîñòè îò
ãëàâíîé ñâÿçêè ôîðìóëû F âîçìîæíû ñëåäóþùèå ñëó÷àè:
                                                 ¡
F = ¬ G, F = G ∨ H, F = G N H, F = G ¢ H è F = G ≡ H .

Страницы