KIF04

Spróbuj rozstrzygnąć intuicyjnie, który z podanych ni tej schematów jest tautologią; porównaj własne odpowiedzi z rozwiązaniem podanym we „Wskazówkach

(3) A xP(x)-~\/ x-~P(x).

(b)    ~\/x~P(x)->/\ xP(_X).

(c)    \/xP(x)-+~/\x~P(x).

(d)    ~A x~P(x)-\J xP(x).

(e)    A -'(/‘W ¹ QMJ-(A ^xp(^x) ^A A ¹&¹))■

(0 (/\xP(x)a Ax&x))-+/\x{P(x) a Qix)].

(g)    /\ 4^)-¹ Qix)]-(A xP{x)-¹ A •¹£?(¹))•

(h)    (j\xP{x)-¹ /\xQ(x))-+ /\x[P(x)-+Q(x)].

(i)    V Wv 0(.v)]-(V rfW ^ V ¹(?(¹))•

© (V^)^v V^))-¹V#WvGM].

(k) v¹W»)-ewi-(V jci¹(x)-¹V¹«¹))• o (v xp(x)-v ¹cc¹»-¹V    &¹)]•

0) A ¹ A ?¹(¹. >¹)—A ²(¹. ¹)•

(o) A xR(x, x)-¹ ax A v¹(¹. y).

(n)    v ¹ Vy^(¹. y)-+ V ²(¹. ¹)■

(o)    v ¹ V >¹(¹. >)- V y V ²(¹. y)-

(p)    j\xp{x)-i\y).

(r) P{y)-¹\J xP(x).

(«) P(x)-¹P(y).

78. System aksjomatyczny rachunku kwantyfikatorów można I oprzeć na aksjomatyce, którą stanowi zbiór wszystkich twier- I dzeń rachunku zdań i wyrażeń, które z twierdzeń tych powstają przez podstawianie (konsekwentne) dowolnych wyrażeń rachunku kwantyfikatorów za zmienne zdaniowe⁸. Z aksjonu-tów tych można wywieść każdą tautologię rachunku kwantyfikatoró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 ó w W nic stanic się związana tam, gdzie a w W była wolna.

(OA) Reguła opuszczania dużego kwmtyfikatora w następniku: jeśli do dowodu należy wyrażenie postaci H',-* f\a\V_t, to wolno dołączyć do dowodu wyrażenie postaci M'_ł-» W_t.

(0\J) Reguła opuszczania małego kwantyfikatora w poprzedniku: jeśli do dowodu należy wyrażenie postaci V oiV_x-*W_it to wolno dołączyć do dowodu wyrażenie postaci fVi~> }V_t.

(D/\) Reguła dołączania dużego kwantyfikatora w następniku: jeśli do dowodu należy wyrażenie postaci Ił",— lV_t, to wolno dołączyć do dowodu wyrażenie postaci /\aW_t, pod warunkiem jednak, że w 1P, 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 W_x-+ to wolno dołączyć do dowodu wyTażcnic postaci \J a\V_x -* (Vj, 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 wyTażcnic postaci

A°r-

Przykład: zastosowanie reguły 0/\ do aksjomatu:

A*V    >)-* A * V    >•)

prowadzi do wyrażenia: A ^x V>^R(^X> >')“* V)'^R(^X> /)• kitwo

63

1

Modna leź przyjąć jako aksjomaty rachunku kwantyfikaterćw akgomaty rachunku zdań, dołączając do reguł rozszerzoną regułę potjuz-

2

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