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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

p ∨ ¬ p
p
¡
¢
(q
¡
¢
p)
¬ p
¡
¢
(p
¡
¢
q)
(p
¡
¢
(q
¡
¢
r))
¡
¢
((p
¡
¢
q)
¡
¢
(p
¡
¢
r))
(¬ q
¡
¢
¬ p)
¡
¢
((¬ q
¡
¢
p)
¡
¢
q)
((p
¡
¢
q)
¡
¢
p)
¡
¢
p
F, A
1
, . . . , A
k
p
1
, . . . , p
k
A
1
, . . . , A
k
F
p
1
, . . . , p
k
F (p
1
, . . . , p
k
k A
1
, . . . , A
k
) p
i
F A
i
F ∈ T ⇒ F (p
1
, . . . , p
m
k A
1
, . . . , A
m
) ∈ T .
F
q
1
, . . . , q
n
f
F
(q
1
, . . . , q
n
)
k F
1 6 k 6 n k 6 m ϕ
q
i
7→ α
i
∈ { , } i = 1, n,
|F (p
1
, . . . , p
m
k A
1
, . . . , A
m
)|
ϕ
=
= f
F
(|A
1
|
ϕ
, . . . , |A
k
|
ϕ
, α
k+1
, . . . , α
n
) = ,
ϕ ¤
18                                          Ãëàâà 1. Êëàññè÷åñêàÿ àëãåáðà ëîãèêè


 11. p ∨ ¬ p  çàêîí èñêëþ÷¼ííîãî òðåòüåãî (ëàò. tertium non datur:
     ¾âñÿêîå ñóæäåíèå ëèáî èñòèííî, ëèáî ëîæíî è òðåòüåãî íå äàíî¿).
         ¡      ¡
 12. p ¢ (q ¢ p)  çàêîí óòâåðæäåíèÿ êîíñåêâåíòà (çàêîí óïðîùå-
     íèÿ).
             ¡      ¡
 13. ¬ p ¢ (p ¢ q)  çàêîí îòðèöàíèÿ àíòåöåäåíòà.
          ¡¢     ¡¢     ¡ ¡   ¡    ¡
 14. (p (q r)) ¢ ((p ¢ q) ¢ (p ¢ r))  çàêîí ñàìîäèñòðèáóòèâíî-
     ñòè èìïëèêàöèè èëè çàêîí Ôðåãå).
              ¡       ¡   ¡   ¡
 15. (¬ q ¢ ¬ p) ¢ ((¬ q ¢ p) ¢ q)  óòâåðæäåíèå ÷åðåç ïðîòèâîðå÷èå
     (äîêàçàòåëüñòâî îò ïðîòèâíîãî, êîñâåííîå äîêàçàòåëüñòâî).
            ¡      ¡    ¡
 16. ((p ¢ q) ¢ p) ¢ p  çàêîí Ïèðñà.
    Ìåòîäû óñòàíîâëåíèÿ òîãî ôàêòà, ÷òî äàííàÿ ôîðìóëà åñòü òàâòî-
ëîãèÿ áóäóò ðàññìîòðåíû â ïîñëåäíåì ðàçäåëå ¾Õàðàêòåðèçàöèÿ ôîð-
ìóë àëãåáðû âûñêàçûâàíèé¿ äàííîé ãëàâû.
    Ïóñòü F, A1 , . . . , Ak  ôîðìóëû, à p1 , . . . , pk  ïîïàðíî
ðàçëè÷íûå ïðîïîçèöèîíàëüíûå ïåðåìåííûå. Ðåçóëüòàò îäíîâðå-
ìåííîé ïîäñòàíîâêè ôîðìóë A1 , . . . , Ak â ôîðìóëó F âìå-
ñòî âñåõ âõîæäåíèé p1 , . . . , pk ñîîòâåòñòâåííî áóäåì îáîçíà÷àòü
F (p1 , . . . , pk k A1 , . . . , Ak ). Ïðè ýòîì, åñëè ïåðåìåííàÿ pi íå âõîäèò â
F , òî Ai íèêóäà íå ïîäñòàâëÿåòñÿ.
Òåîðåìà 1.1 (Î ïîäñòàíîâêå â òàâòîëîãèþ).
                    F ∈ T ⇒ F (p1 , . . . , pm k A1 , . . . , Am ) ∈ T .
Äîêàçàòåëüñòâî. Ïóñòü ôîðìóëà                F çàâèñèò îò ïåðåìåííûõ
q1 , . . . , qn è òîëüêî îò íèõ è ðåàëèçóåò áóëåâó ôóíêöèþ fF (q1 , . . . , qn ),
ÿâëÿþùóþñÿ êîíñòàíòîé 1.
     Åñëè íèêàêèõ ïîäñòàíîâîê ôàêòè÷åñêè íå ïðîèçâîäèòñÿ, òî óòâåð-
æäåíèå òåîðåìû òðèâèàëüíî.  ïðîòèâíîì ñëó÷àå áåç îãðàíè÷åíèÿ
îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî ñîîòâåòñòâóþùèìè ôîðìóëàìè çà-
ìåùàþòñÿ ïåðâûå k ïðîïîçèöèîíàëüíûõ ïåðåìåííûõ ôîðìóëû F ,
1 6 k 6 n, k 6 m. Ïóñòü ïðè íåêîòîðîé èíòåðïðåòàöèè ϕ îñó-
ùåñòâëÿåòñÿ îòîáðàæåíèå qi 7→ αi ∈ {0, 1}, i = 1, n, è òîãäà áóäåì
èìåòü

     |F (p1 , . . . , pm k A1 , . . . , Am )|ϕ =
                                       = fF (|A1 |ϕ , . . . , |Ak |ϕ , αk+1 , . . . , αn ) = 1 ,
÷òî è äîêàçûâàåò óòâåðæäåíèå òåîðåìû â ñèëó ïðîèçâîëüíîñòè ϕ.                                      ¤

   ßñíî, ÷òî ïîäñòàíîâêà ëþáûõ ôîðìóë âìåñòî ïðîïîçèöèîíàëüíûõ
ïåðåìåííûõ â ïðîòèâîðå÷èå òàêæå äàñò ïðîòèâîðå÷èå. Ñ äðóãîé ñòîðî-
íû, äëÿ íåéòðàëüíîé ôîðìóëû ìîæíî íàéòè òàêèå ïîäñòàíîâêè, êîòî-
ðûå ïðåâðàòÿò å¼ è â òàâòîëîãèþ, è â ïðîòèâîðå÷èå.

Страницы