KIF04

Spróbuj rozstr/ygrujć intuicyjnie, który z podanych „u¹

schematów jest tautologią; porównaj własne odpowie? z rozwiązaniem podanym we „Wskazówkach”.

(a) A ²«¹)-²    W

(b)    ~v¹~^/>w-^#A^tW

w

(d)    ~ A²~¹t²)-¹V ³(¹)•

(e)    A ¹l^pW^A GMHCAtFOOA A ¹ew).

(0 (A^)aAjffiC¹))—A¹^¹)a q{x)).

(i) A GttJ-CA-^to- A ¹Cto).

(h) (/\xAx)- A-^tt-A^to-ew].

(D y¹IA¹)v g(¹)]-(V ¹n¹) v V ¹Cto).

g> (v^)v\/xe(¹))-v«ve(x)].

(k)    GW1-(V xP(x)-+\J xQ(x)).

(l)    (V V xQ(x))-¹y x[P(x)-¹ Q(x)).

fl) A ¹ A y^R(x. y)-¹A ²(¹, ¹).

(m)    A ¹/?(¹, ¹)-» A ¹ A >’¹(■¹. y).

(n)    V¹V>■¹(¹. y)- V²(¹, X).

(o)    V¹V^x.y)-¹VyV^x_t>-).

(p)    AxP(x)->P{y).

(0 P(y)^\/xP(x).

W Ąx)-P(j).

78. System aksjomatyczny rachunku kwantyfikatorów tnoin¹ oprzeć na aksjomatycc, którą stanowi zbiór wszystkie \ dzeń rachunku zdań i wyrażeń, które z twierdzeń tych P°'« » przez podstawianie (konsekwentne) dowolnych wyrażeń ^ chunku kwantyfikatorów za zmienne zdaniowe^. Z a ^SJ°

tów tych można wywieść każdą tautologię rachunku kwanty-

fikutorów, stosując następujące reguły dowodzenia:

(RO) Reguła odrywania (zob. zadania 27, 28, 33).

(RP') Reguła podstawiania dla zmiennych nazwowych: jeśli do dowodu należy wyrażenie W zawierające zmienną wolną a, to wolno dołączyć do dowodu wyrażenie W' powstające z W przez zastąpienie zmiennej a zmienną b wszędzie, gdzie a jest wolna, pod warunkiem jednak, że i w W nic stanic się zw iązana tam, gdzie a w W była wolna.

(0/\) Reguła opuszczania dużego kwantyfikatora w następniku: jeśli do dowodu należy wyrażenie postaci f\aW._t to wolno dołączyć do dowodu wyrażenie postaci W^/i-» Wf

(0\/) Reguła opuszczania małego kwantyfikatora w poprzedniku: jeśli do dowodu należy wyrażenie postaci V a\V_x-* \V₂, to wolno dołączyć do dowodu wyrażenie postaci H⁷-.

(D/\) Reguła dołączania dużego kwantyfikatora w następniku: jeśli do dowodu należy wyrażenie postaci W_t, to wolno dołączyć do dowodu wyrażenie postaci Wi~» f\aW_t, pod warunkiem jednak, że w nic występuje zmienna wolna a.

(D\/) Reguła dołączania małego kwantyfikatora w poprzedniku: jeśli do dowodu należy wyrażenie postaci FP*-* W_t, to wolno dołączyć do dowodu wyrażenie postaci \J a\Vi -*W₂, pod warunkiem jednak, że w W_t nic występuje zmienna wolna a.

(RU) Reguła uogólniania: jeśli do dowodu należy wyrażenie W, to wolno dołączyć do dowodu wyrażenie postaci !\aW.

Przykład: zastosowanie reguły O (\ do aksjomatu:

A*V y)-A ^xV >■)

prowadzi do wyrażenia: /\ x V )’R(^X> y)~* V*'^atv>0

63

1

Można Ki przyjąć jako aksjomaty rachunku kwantyfik¹^_

2

akijomaiy rachunku zdań, dołączając do reguł rozszerzony r^c»^{ulv 1}

3

wiania RP i — ewentualnie — regułę zastępowania RZ.