KIF85

gdy awicrdzimy, żc tautologiczny jest zarówno schemat: If-iP v

jak i schemat p-*(p v q), będący jego poprzednikiem.

(A)    Podaj inne przykłady otrzymywania przez odrywanie no-wych tautologii z tautologii danych.

(B)    Wyjaśnij, dlaczego operacja odrywania nie prowadzi nigdy od tautologii do schematów nictautologicznych.

(C)    Powołując się na własności podstawiania i odrywania wyjaśnij, dlaczego wiedząc, iż schematy (a), (b) są tautologiami, wolno uznać za tautologię schemat (c).

(a)    (~p v q)-*{p-*q)

(b)    ~p v (q->p)

(c)    p-*(q-»p)

28*. Przyjmując jako podstawę stosownie dobrany zbiór tautologii rachunku zdań można udowodnić każdą inną tautologię przez odpowiednie powtarzanie operacji podstawiania i odrywania; tak zbudowany rachunek zdań nazywamy systemem aksjomatycznym tego rachunku, tautologie, które zostały przyjęte jako podstawa — aksjomatami lub twierdzeniami pierwotnymi systemu, zaś tautologie udowodnione w oparciu o aksjomaty — jego twierdzeniami pochodnymi, Punkiem wyjścia każdego dowodu są aksjomaty (lub twierdzenia wcześniej ^udowodnione); wolno je dołączać do dowodu także w dal-szych etapaclTdowodzenia. Reguła podstawiania dla zmiennych zdaniowych pozwala na włączenie do dowodu każdego rezultatu operacji podstawiania, wykonanej na wyrażeniu występującym już w dowodzie, a reguła odrywania — na włączenie doń każdego rezultatu operacji odrywania, zastosowanej do wyrażeń występujących już w dowodzie. Dowód jest więc ciągiem tautologii, złożonym z aksjomatów, twierdzeń wcześniej udowodnionych oraz z wyrażeń otrzymywanych z poprzedzających je w tym ciągu przez zastosowanie operacji podstawiania lub odrywania. Każdy taki ciąg jest dowodem ostatniego ze swych wyrażeń. Na przykład, przyjmując jako aksjomaty wyrażenia:

(Al) (p-*ę)-*Kł-*'V*U^*r)l (A2) (~p-+p)-*p (A3) p^(~p~+q)

budujemy dowód prawa tożsamości p—p jako ciąg wyrażeń:

(Al) (RP: 1)

(A3)

(A2)

(RO: 5, 6)

(1)    (p-*<?)-»[(<?-*'-)-*(p-*'-)l

(2)    [p->(~p-qj\-*{{(~P-q)-'r\->ip -r\

(3)    p-*(-p-*q)

(4)    [(~p-‘9)-»r—J-(p~*r)

(5)    ((~p-*p)-*p]-*(/>-»/>)

(6)    (~p-*p)-*p

(7)    p-*p (Skróty RP i RO oznaczają kolejno regułę podstawiania i regułę odrywania; cyfry następujące po dwukropku są numerami tych wyrażeń ciągu dowodowego, do których zastosowano odpowiednią operację.)

Udowodnij jako twierdzenie systemu o aksjomatach A1-A3 i regułach RP, RO dwie formy prawa podwójnej negacji.

(a)    p~*'—p, zakładając, żc wcześniej udowodnione zostało:

(Tl)

(b)    zakładając. żc wcześniej udowodnione zostało: (T2) ~p-*(p-e)

29*. Definiując za pomocą symboli stałych występujących w aksjomatach (zwanych terminami pierwotnymi) nowe terminy stale (zwane terminami pochodnymi lub wtórnymi) i przyjmując tzw. regułę zastępowania (w skrócie: RZ), która pozwala na włączenie do dowodu rezultatu zastąpienia w pewnym jego członie dowolnego wyrażenia składowego jego równowaźni-

25