KIF05

._v/ ir wyrażenie to jest tautologią. Nic wolno doń

■ES ^°^^{wać rcgu,y RP}’’ f^^{stawiaj;,c y łi} *; wof. !

£ wyrażenie: A* VVJ** * * *1 tautc rstaic Sie wlaniem fałszywym np. w dziedzinie liczb natu-. \h no podstawieniu za * nazwy relacji mniejszo**)

(A) "Podaj pokłady zastosowania reguł RP' OV, D/_v ^K D V RU do wyrażeń powstających z twierdzeń rachunku

zdań przez podstawienie za zmienne zdaniowe wyrażeń

rachunku kwantyfikatorów.

_(B)    Uzasadnij na przykładach potrzebę przestrzegania wanin-ków stosowalności reguł D A ‘ ^ V-

_(C)    Uzasadnij w sposób intuicyjny, że żadna z podanych wyżej reguł nic prowadzi nigdy od tautologii do schematów

nietautologicznych.

79*. Dowodem danego twierdzenia rachunku kwantyfikatorów w danym systemie aksjomatycznym tego rachunku nazywamy ciąg wyrażeń, z których ostatnie jest tym twierdzeniem, a każde jest bądź aksjomatem (lub twierdzeniem \vcze5-[ niej udowodnionym) danego systemu, bądź powstaje z wyrażeń poprzedzających je w tym ciągu przez zastosowanie przy- j jętych reguł dowodzenia. Na przykład, dowodem jednego z k wantyfkatarowych praw de Morgana:

V x~P(Jr)-»~ /\ xP(x)

w systemie przedstawionym w zadaniu 78 jest ciąg wyrażeń:

(1)    /\xP(x)-+ /\xP(x)    (A)

(2)    A xP(x)-+P(x)    (OA^:1>

(3)    (A~ A*P(*))    (A)

(4)    ~P(x)-*~/\xP(x)    (RO:    2,3)

(5)    A^W    ^^DV^:

(Wyrażenia oznaczone literą A są podstawieniami twierdze® rachunku zdań (a więc aksjomatami niniejszego system®, które Czytelnik łatwo zidentyfikuje).

64

Udowodnij jako twierdzenia tego samego systemu następujące tautologie rachunku kwantyfikatorów:

(a)    A xP(x)~* V ^xP(*) (Prawo subaltemacjl).

(b)    f\X^p(x)~ /\yP<J>)\ (prawa zamiany zmiennych

(C) \JxP(x)= V y^p(y» ^zvdtpanych).

₍d)    (A xlP(x)~* Q(x)) a P(x))- Q(x).

(e) A GWHIA    A *«*)!

(prawo rozkładania dużego kwantyfikatoro).

(0 a    iv ^xp(*)~* v *m]

(prawo rozkładania małego kwantyfikalord).

(g) ~ \J xP(x)~* A x~P(x) (drugie prawo de Morgana dla kwantyfikatorów).

80. Wykaż, że kwantyfikatorowc prawa de Morgana (zob. zadanie 79) można wzmocnić do postaci równoważności, tj. udowodnij twierdzenia:

(a)    ~ A xP(x)-+ V x~P(x).

(b)    A x~P(x)—\/xP(x).

81. Wzorując się na dowodach odpowiednich twierdzeń z predykatami jednoargumentowymi (zob. zadania 79. 80) zbuduj dowody następujących twierdzeń:

fa) A*Ay^R(^x>y)- V* Vy^R(^x>>)•

(b)    A ^ A y^R(^xy y)^s A² A^vR(^z>^p)*

(c)    V^XV 3’) = V² V ^p)-

(d)    A*AM*(*.>0-.S(.r, ;■))-»

-»{A*A jflfo >)-* A-^VA    jOI-

Ce) A*>•))-*

-+[V * V    >•)-♦ V ^x    >’))■

(0 ~ /\x/\yR(x,y)a \/x\/y~R(x, y).

(g) - VxV^x,y)B /\x/\y~^R(x_f>^:).

⁵ — <Vcx*oJ« i logiki