KIF89

logii jako twierdzeń systemu opartego na regułach RO. DK OK. DA. OA. DR, OR.

(a)    (~q-+ ~p)-*(p-*g) (druga forma prawa transpozycji prot-

tej)

(b)    (~pvq)-*{p->q)

(c)    [(p A q)->r]~* [(p A ~r)—»~ q\ ) (dwie formy prawa transfo-

(d)    fO>A~r)-»~f]-[(/>A?)-*rj J zycjl złożonej)

37*. Celem skrócenia i uproszczenia dowodów założenio-wych wprowadza się zwykle — oprócz reguł przyjętych w sys-teinie bez uzasadnienia, zwanych regułami pierwotnymi — dodatkowe reguły, zwane regułami wtórnymi, których prawomocno# sankcjonują reguły pierwotne. W szczególności, udowodniwszy dowolne twierdzenie o postaci implikacji można wprowadzić do systemu regułę, która pozwala dołączyć do dowodu wyrażenie o budowie następnika tego twierdzenia, jeśli występuje już w dowodzie wyrażenie o budowie jego poprzednika Na przykład, udowodniwszy prawo podwójnej negacji (zob. zadanie 36). możemy przyjąć regułę, która pozwala na opuszczanie podwójnej negacji (ON)- Skorzystamy z niej. dowodząc drugiej formy tego prawa:

P~*—P

(1) p    (założenie)

(2) ---_P    (z. d. n.)

(3) ~P    (ON: 2)

Z kołd, w oparciu o ostatnio udowodnione twierdzenie można przyjąć regułę, która pozwala na dołączanie podwójnej negacji. (A) Sformułuj reguły, które odpowiadają następującym twierdzeniom rachunku zdań:

(a)    [{p-*q)*p]-*q    (modus ponendo ponens)

(b)    lO^,-*ę)A~ę]-.~p    (modus tolłendo tollens)

(c)    lU>vę)A~p]-»f (modus tolłendo ponens)

(cl [(p-»g)A(p-»~f/)l~»~/>) (prawo redukcji do absurdu) (e) ~(p-»q)-*(p a -g) (prawo negowania implikacji)

(O ~(pnq)-*(~pv ~q)

(prawią £><■ Morgana)

(g)    (~pv~ą)-*~(pAą)

(h)    ~(pv(/)-*(~pA~<?) 0) (~pA~₉)->-~(pv₉)

(B) Podaj układ twierdzeń, które są podstawa następującej reguły (zwanej regułą ekstensjoualności): wolno dołączyć do dowodu wyrażenie, które powstaje z wyrażenia należącego już. do dowodu przez zastąpienie dowolnego jego wyrażenia składowego W wyrażeniem W, o ile w dowodzie wystąpiło wyrażenie IV* W\

38. Dowód założeniowy niewprost twierdzenia, które nic jest implikacją, zawiera jako jedyne założenie założenie dowodu niewprost, będące negacją twierdzenia dowodzonego. Na przykład, dowód prawa wyłączonego środka jest ciągiem wyrażeń:

(1)    ~(p v ~p)

(2)    ~p a ~ ~~p

(3)    ~P

(4) --p

(z. d. n.)

(reguła oparu na prawie Dc Morgana: I) (OK: 2)

(OK: 2)

Zbuduj założeniowy dowód niewprost (korzystając ewentualnie z reguł wtórnych) następujących tautologii:

(a)    ~(pA~p) (prawo sprzeczności)

(b)    (p-<7)v ($-/>)

39. Zdanie reprezentowane przez tautologic/ny schemat zdaniowy nazywamy prawdą logiczną. Prawdy logiczne są zdaniami prawdziwymi na mocy znaczenia stałych logicznych (do których należą funktory a, v, ■) i jako takie zasługują

33

i — CwfeMOia ł lopU