logika egz03

Zad. 6. Niech X i Y będą formułami rachunku kwantyfikatorów, gdzie X jest tautologią a Y nie jest tautologią. Która z następujących formuł jest tautologią rachunku kwantyfikatorów:

A)    XvY

B)    XaY

C)    Xa(iY)

D)    Y => X.

Zad. 7. Wskazać formuły, które są tautologiami rachunku zdań:

A)    ( ip v (q v r)) o ((-.p v q) v r)

B)    <(-^p => q) a (q => -,p)) => ( ip v q)

C)    ((ip a q) v (-.p => q)) => (-.p => q)

D)    ((-.p vq)u (- >p v —iq)) =^(pvq)

Zad. 8. Wskaż prawdziwe stwierdzenia:

A)    Zbiór wszystkich liczb całkowitych, nie będących liczbami pierwszymi, jest przeliczalny.

B)    Zbiór wszystkich liczb zespolonych jest nieprzeliczalny.

C)    Zbiór wszystkich punktów na płaszczyźnie jest równoliczny ze zbiorem wszystkich odcinków na

płaszczyźnie.

D)    Zbiór wszystkich liczb całkowitych jest równoliczny ze zbiorem wszystkich liczb naturalnych

większych od 2.

Zad. 9. Dana jest teoria formalna T oparta o język rachunku zdań, której aksjomatami sąA^ A₂, A₃, A₄, regułami zastępowania definicyjnego sąD₁ i D₂ oraz regułą wnioskowania jest R-p

A-i: ((-iX)<=>(X=>false))    Rp — ^B)

B

A₂: ((X=>false) =>X)    Dp false = (—itrue)

A₃: ((-. false) => true)    D₂: true = (—.false)

A₄: (X=>(X=> false))

Które z poniższych stwierdzeń są prawdziwe:

A)    Formuła false nie jest twierdzeniem teorii T

B)    Formuła (X=> (-.true)) nie jest twierdzeniem teorii T

C)    Teoria T nie jest sprzeczna

D)    Teoria T nie jest skończona

Zad. 10. Dany jest zbiór X={a,b,c} oraz relacje R| ę X² (i=1,2,3,4) zdefiniowane następująco: R₁=0 , R₂= {<a,c>,<c,a>,<a,a>}, R₃={<a,c>,<a,b>}, R₄={<a,a>,<b,b>,<c,c>,<a,c>,<a,b>},

Prawdą jest, że

A)    Rt jest relacją symetryczną na X,

B)    R₂jest relacją zwrotną na X,

C)    R₃ nie jest relacją przechodnią na X,

D)    R₄ jest relacją równoważności na X.

Zad. 11. Niech x,y,z będą symbolami zmiennych indywiduowych; p,q,r - symbolami predykatów 2-argumentowego, 1-argumentowego i 3-argumentowego odpowiednio. Które z następujących wyrażeń są formułami rachunku:

A)    (Vx.(p(x,y)Aq(z)))

B)    (dr.(p(x,y)Aq(z)))

C)    (Vy.(p(x,y)Aq(r)))

D)    (Vx.(3z.(p(x,y)vq(z))))

Zad. 12. Zakładając, że P, Q są jednoargumentowymi predykatami, x, y zmiennymi indywiduowymi wskaż, które z poniższych formuł są tautologiami rachunku kwantyfikatorów:

A)    (Yx.P(x)) => (3x.P(x))

B)    (3x.( iP(x) v -iQ(x))) v (3x.(P(x) aQ(x)))

C)    (Vx.(P(x)    Q(x))) => (Vx.P(x) o Vx.Q(x))

D)    3x.P(x) Yx.P(x)