KIF09

f

kształtne; świadczy o tym możliwość udowodnienia za pomocą następującej nictautologicznej formuły:

A-v V >^R(.x. y)-> V yR(y, >•)■

(1)    Ax\/yR(.x,y)

(2)    v y*(y. y)

(założenie)

(OA:i)

Możliwość tę usuwa następujące ograniczenie: zmienna, którą zastępujemy zmienną a opuszczając duży kwantyfikator, nie może stać się związana w wyrażeniu, w którym a była wolna.

Wykaż, że analogiczny warunek należy nałożyć również na regułę D bowiem nie respektując go można udowodnić nietautologiczną formułę:

V -v A y^R(^x’ y)-* Ay^R(y> >)•

91.    Udowodnij podane niżej tautologie jako twierdzenia systemu założeniowego rachunku kwantyfikatorów.

(a)    a*Ay^R(^x>>)* AyAxR(x,y)

(b)    V *V >*(*. y)^s V y V ^xR(x, >)

(«) V * A>^,R(^x> >•)- Aż¹ V *^R(x> y)

(d) A * Ay^R(x, y, z)= A>'A x^r(x, y. z)

(c)    V ^x V -^vR(^x< y> ^z)= V y V **(*» y>^z)

(0 VxAy^R(x, y, z)-* J\ V VxR(x, y, z)

92.    Do systemu założeniowego rachunku kwantyfikatorów można wprowadzać reguły wtórne, oparte na udowodnionej twierdzeniach. W szczególności, udowodniwszy dowolne twierdzenie implikacyjnc wolno przyjąć regułę, która powab dołączyć do dowodu wyrażenie o budowie następnika tto,' twierdzenia, jeśli występuje już w dowodzie wyrażenie o budowie jego poprzednika. Na przykład, udowodniwszy praw de Morgana dla kwantyfikatorów (zob. zadanie 86) możanj przyjąć m. in. regułę, która pozwala dołączyć do dotrodo wyrażenie postaci \/ a~ W, jeżeli należy już do dowodu wyrażenie postaci ~ f\aW.

Sformułuj pozostałe reguły wtórne, których podstawą są prawa dc Morgana dla kwantyfikatorów.

93. Formułę zdaniową (zdanie lub funkcję zdaniową) reprezentowaną przez schemat, który jest tautologią rachunku kwantyfikatorów, nazywamy prawdą logiczną^u. Na przykład, prawdą logiczną jest zdanie:

Jeśli każdy Marsjanin jest istotą rozumną, to jeśli istnieją Marsjanie, to istnieją istoty rozumne, reprezentuje je bowiem tautologiczny schemat:

A x(r(x)-+ CMI—*IV    V *ewi-

Wskaż prawdy logiczne wśród podanych niżej formuł zdaniowych.

(a)    Jeżeli każdy Ziemianin jest istotą rozumną, to każda istota rozumna jest Ziemianinem.

(b)    Jeżeli tylko Ziemianie są istotami rozumnymi, to tylko istoty rozumne są Ziemianami.

(c)    Jeżeli istnieją Marsjanie, to nic tylko Ziemianie są istotami rozumnymi.

(d)    Jeżeli każda istota rozumna jest Ziemianinem lub Marsjaninem, to tylko istoty rozumne są Ziemianami łub tylko istoty rozumne są Marsjanami.

(e)    Jeżeli istnieje człowiek rozumniejszy od każdego człowieka, to istnieje człowiek rozumniejszy od samego siebie.

(f)    Jeżeli, jeśli .v jest człowiekiem, to x jest rozumniejszy od każdego zwierzęcia, to każdy człowiek jest rozumniejszy od każdego zwierzęcia.

¹¹ Jest to uogólnienie pojęcia prawdy logicznej sformułowanego na gruncie rachunku zdań (zob. zadanie 39). bowiem koid* tautologia rachunku zdań jest tautologią rachunku kwantyfikatorów.

73