GRUPA 1  
 
ZAD. 1.    Dana jest relacja R

⊆N²x N²(N-zbiór liczb naturalnych,  

zdefiniowana następująco: <a,b>R<c,d>

⇔a*d=b*c         

A)  

❶R jest relacją równoważności 

B)  

⓪R jest symetryczna i zwrotna, ale nie jest przechodnia 

C)  

❶   Pary <l,k> oraz <l,k>, gdzie k jest pewną liczbą naturalną,  

                                                                 

są ze sobą w relacji R 

D)  

❶

 

Gdyby R była zdefiniowana na zbiorze liczb wymiernych,  

czyli R

⊆ W²x W²(W-zbiór liczb wymiernych), to byłaby relacją  

 
ZAD. 2. Niech R

1

 ,R

 2

 

będą relacjami równoważności na zbiorze X. 

 

Wówczas relacjami równoważności są również relacje: 

A)  

⓪ R

1

\R

 2   

 

B)  

⓪ X²\R

 2

 

C)  

⓪ (R

1

\R

 2

)

∪ (R

2

\R

1

)  

D)  

⓪ (R

1

∪R

 2

) \R 

 
ZAD. 3.  Niech A, B, C będą dowolnymi zbiorami.  
Prawdą jest, że: 
A) 

⓪card(A)=card(B)⇒A∪B=A 

B) 

❶A∪(B\A)=A∪B 

C) 

❶Jeżeli x∈A oraz x∉B, to {x}∈2

A

∪B

 

D) 

⓪(A\B)∪(B\A)=∅⇔A∩B=∅ 

 
ZAD. 4.      Dana jest funkcja f: X→Y całkowicie określona na X.  
Niech R

⊆X² będzie relacją binarną na X określoną następująco:  

<x,y>

∈R wtedy i tylko wtedy, gdy f(x)=f(y).  

Wskaż, które z własności posiada relacja R: 
A)   

⓪R jest relacją antysymetryczną  

B)   

⓪R jest relacją spójną  

C)  

❶R jest relacją przechodnią 

ZAD. 5. Słowo postaci a {bc} {a}, gdzie {x} oznacza jedno lub  
więcej powtórzeń elementu x, jest generowane przez gramatykę  
G=

df

<{a,b,c},{

S,A,B},P,S>, gdzie zbiór produkcji  

P jest zdefiniowany następująco: 
A)   

⓪P=

df

{S::=a|AB, A::=b|bcA, B::=a|aB} 

B)  

⓪P=

df

{S::=ab|cA|B, A::=bc|A|a , B::=a|b|c} 

C)  

⓪P=

df

{S::=a|B|A, B::=b|BA, A::=a|A|b} 

D)  

❶P=

df

{S::=B|A, B::=aB|bcB|a, A::=a|Aa} 

 

 
ZAD. 6.   Formuła α nie jest tautologią, a formuła β jest tautologią  
rachunku kwantyfikatorów. Które z poniższych formuł są 
 

tautologiami rachunku kwantyfikatorów: 

A)  

⓪α ∧ β 

B) 

❶α ∨ β 

C)  

⓪α ⇔ β 

D)  

❶α ⇒ β 

 
ZAD. 7.

 

Niech p,q,r będą zmiennymi zdaniowymi.  

Wskazać wyrażenia, które są tautologiami: 
A)  

❶ (¬(p⇒q) ∧ (q⇒p)) ⇒ (p∧¬q) 

B)  

⓪((p∨q) ∧ (p⇒q)) ⇒ (q⇒p) 

C)  

❶ ((p∨q) ⇒r) ⇒ ((p⇒r) ∨ (q⇒r)) 

D)  

⓪(p⇒(q∨r)) ⇒ (p ⇒q) 

 
ZAD. 8.

 

 Jeżeli INT

v

(α

∨(β∧α))=P to zawsze zachodzi：  

A)   

⓪INT

v

(

β)=P 

B)   

❶INT

v

(

α)=P 

C)   

⓪INT

v

(α)=F 

D)   

❶INT

v

(α

∨β)=P  

 
ZAD. 9.  

 

Wyrażenie ¬p jest semantycznie  

równoważne wyrażeniu: 
A)  

⓪p∨(¬q∧p) 

B)  

❶¬p∧ (q∨¬p) 

C)  

⓪p⇒q 

D)  

⓪¬p⇔¬p 

 
ZAD. 10.    Zakładając, że x,y,z są zmiennymi indywiduowymi, 
 p, q, r, s 

– symbolami predykatów, wskaż napisy, które są  

poprawnnie zbudowanymi farmułami rachunku kwantyfikatorów 
A)  

❶∀x●p(x, true)  

B)  

❶∀x●(¬(x⇒x)⇔(x∧¬x))

  

C)  

⓪(∃x●p(a,b,c)∧(¬q(y)⇔q(y)))⇒∀x●(p(x)∧q(y)) 

 

D)  

❶∀x●(∃x●((p(x)∧∃x●q(x))⇒r(x))∧∃x●s(x)) 

 
ZAD. 11.    Zakładając, że P, Q są predykatami, x, y – zmiennymi 
 

indywiduowymi wskaż, które z poniższych  

formuł rachunku kwantyfikatorów są tautologiami: 
A)  

❶(∀x●P(x))⇒(∃x●P(x))  

B)  

❶(∃x●(¬P(x)∨¬Q(x)))∨∃x●(P(x)∧Q(x))  

C)  

❶(∀x●P(x)⇔Q(x)))⇒(∀x●P(x)⇔∀x●Q(x)) 

 
ZAD. 12.    Dana jest formuła 

∃x●(P(x,y)∧Q(x,y)), system relacyjny 

 SR=<A

sr

,R

1

,R

2

> oraz interpretacja dan

ej formuły w systemie  

relacyjny SR oznaczona I

. Jeżeli nośnik systemu relacyjnego A

sr

={a,b} 

 i relacje: R

1

={<a,b>,<b,a>}, R

2

={<a,a>,<b,b>,<a,b>}, to: 

A)  

⓪Dla I(P)=R

1

 i I(Q)=R

2

 

oraz dla wartościowania  

v(x)=a i v(y)=a formuła jest spełniona 
B)  

⓪Dla I(P)=R

1

 i I(Q)=R

1

 

oraz dla wartościowania  

v(x)=a i v(y)=a formuła jest spełniona 
C)  

❶Dla I(P)=R

2

 i I(Q)=R

1

 

oraz dla wartościowania  

v(x)=a i v(y)=a formuła nie jest spełniona  
 
ZAD. 13.

 

Poniższe drzewo ilustruje zostosowanie rachunku 

 

sekwencji dla sprawdzenia, czy formuła (α

∨β)⇒(α∧β) jest tautologią. 

1)   

→(α

∨β)⇒(α∧β) 

2)   

→¬ (α

∨β) ∨ (α∧β) 

3)   

→¬ (α

∨β),α∧β 

4)   

   

→¬ α

∨¬β,α∧β 

5)   

→¬ α,α

∧β      

→¬β,α

∧β 

Zakładając, że poprzedni węzeł jest poprawny,  
określ czy poprawnie wyprowadzono węzeł: 
A)  

❶Nr 2 

B)  

❶Nr 3 

C)  

⓪Nr 4 

D)  

⓪Nr 5  

 
ZAD. 15.    Poniżej jest dany węzeł N

1

 drzewa dowodu budowanego 

 

zgodnie z algorytmem wykorzystującym rachunek sekwentów Gentzena. 

→

∀x●¬ α∨∀x●¬β, ¬∀x●¬(α∧β)                             ●N

1

 

???                                                                        

●N

2

 

W kolejnym węźle N

2

 

drzewa można wstawić sekwent: 

A)   

⓪¬∀x●¬(α∧β) →∀x●¬(α∧β)B)   

 

B) 

⓪ ∀x●¬α∧∀x●¬β∧¬∀x●¬(α∧β)→ 

C)   

❶→∀x●¬ α,∀x●¬β, ¬∀x●¬(α∧β) 

D)   

❶¬∀x●¬ α, ¬∀x●¬β→¬∀x●¬(α∧β) 

 

 
ZAD. 16.    

 

Wskazać, które z podanych niżej reguł są semantycznie 

 

poprawnymi regułami wnioskowania. X, Y są tu dowolnymi 

 

formułami, a ɸ, Γ – dowolnymi zbiorami formuł. 

A)   

⓪ɸ→ Γ,X⇔Y 

ɸ,X,Y→Γ   ɸ→Γ, X,Y 
B)   

⓪ɸ,X⇔Y→Γ 

ɸ,X→Γ,Y    ɸ,Y→ Γ,X 
C)   

❶ɸ→Γ,X∨Y 

ɸ, ¬X→ Γ ,Y 
D)   

❶ɸ,X∧Y→Γ 

ɸ,X→Γ,¬Y 
 
ZAD. 17.    Które pary formuł są równoważne semantycznie:  
A)  (

∀x●α(x,y))⇒(∃y●β(z,y))             ∀x●∃y●(α(x,y) ⇒ β(z,y)) 

B)  

∀z●∃y●∀z●α(x,z,f(z))                 ∀z●∀x●α(x,h(z,x),f(y)) 

C)  (

∀x●α(x,y)) ∨ (∃y●β(z,y))            ∀x●∃y● (α(x,y) ∨ β(z,y)) 

D)  

∀y●∃z●∀x ●β(x,h(y),z)                ∀y●∀x●β (x,h(y),f(x)) 

 
ZAD. 18.    Które pary formuł są równoważne w sensie spełnialności 
A)  

⓪(∀x●∃y● α (x,y)) ⇒β (y,z)            ∀x●∃y●(α(x,y) ⇒ β(y,z)) 

B)  

⓪∃y●∀x●α(x,y,z)                           ∀x●α(x,g(y),z) 

C)  

⓪∀z●∃y●∀x●β(z,y,x)                     ∀z●∀x● β (z,h(z),x) 

D)  

⓪∀y●∀x ●β(x,g(x,y),y) 

 

∀x●∀y●β (x,h(x,y),y)  

 
ZAD. 19.   Dane są dwie klauzule: kocha(PIOTR, x)  
oraz lubi(ojciec(EWA),y) 
Najbardziej ogólny unifikator tych klauzul to:  
A)   

⓪{x:=y} 

B)   

⓪{x:=EWA,y:=PIOTR} 

C)   

⓪{x:=ojciec(EWA),y:=PIOTR} 

D)   

❶Nie istnieje 

 
ZAD. 20.  Dany jest zbiór klauzul S={¬p

∨q, ¬r∨s, p∨r}.  

Wska

ż które z poniżej podanych klauzul są  

wyprowadzalne ze zbioru S przez zastosowanie  
zasady rezolucji: 
A)   

⓪¬q∨s 

B)   

⓪p∨q 

C)   

⓪¬q ∨r 

D)   

❶q∨s  

 
 
 
 
 
 
 
 
 
 
 
 
 
 

GRUPA 2 
 
ZAD. 1.  Które ze zdefiniowanych relacji są relacjami równoważności 
A)   

⓪X-zbiór osób zdających egzamin, o

1

,o

2

∈X;  

o

1 

R o

2

 

⇔o

2 

siedzi po prawej stronie o

1

 

B)   

⓪X-zbiór samochodów na parkingu s

1

,s

2

∈X;  

s

1 

R s

2

 

⇔s

1 

przejechał co najmniej tylke kilometrów, ile przejechał s

2

 

C)   

❶X-zbiór krzeseł w sali,  k

1

,k

2

∈X;  

k

1 

R k

2

 

⇔ 

 

gdy oba krzesła są zajęte lub oba krzesła są wolne 

D)   

❶X-zbiór funkcji zmiennej x, niech f

1

,f

2

∈X;  

f

1 

R f

2

 

⇔ ∀x●(f

1

(x)=f

2

(x)) 

 
ZAD. 2.      Niech R

1

 ,R

 2

 

będą relacjami równoważności na zbiorze X 

 

Wówczas relacjami równoważności są również relacje: 

A)   

❶R

1

∩R

 2   

 

 

B)   

⓪R

1

\R

 2

 

C)   

❶ (R

1

∩R

 2

)

∪ R

2 

 

D)   

⓪(X

2

\R

 1

) ∩R

2

 

 

 
ZAD. 3.   Niech A=

df

{a,b}, B=

df

{b,c}. Prawdą jest, że: 

A)      

❶card(2

A

∪B

)=2

3

 

B)   

❶ (A\B)∪B={a,b,c} 

C)   

❶2

A

∩2

B

=2

A∩B    

 

D)   

⓪{∅, a, {b}} ⊂ 2

A

 

 
ZAD. 4.   Relacja binarna R

⊆2Nat x 2Nat jest zdefiniowana następująco 

 <A,B>

∈R wtedy  i tylko wtedy, gdy A⊆B. Wskaż które z  

własności posiada relacja R.  
A)   

❶R jest relacją zwrotną 

B)   

❶

R jest relacją antysymetryczną  

C)   

⓪R jest relacją spójną  

 

 
ZAD. 5. 

 OK 

ok   

 Dana jest gramatyka G opisana za pomocą notacji  

BNF (symbole terminalne są ujęte w apostrofy,  
R jest symbolem początkowym gramatyki): 
R::= X’-‘R |  X’+’R  |  X 
X::=LX|L 
L::=’0’|’1’|…|’9’ 
Które z poniższych słów należy do języka L(G): 
A)   

⓪+012  

 

 B)   

❶0-1+0  

C)   

⓪1++1  

D)   

⓪-1+0-1  

 
ZAD. 6.   Niech formuły α  i  β będą tautologiami  rachunku kwantyfikatorów 
Które z poniższych formuł są również tautologiami rachunku kwantyfikatorów: 
A)   

⓪¬α ∧¬ β 

B)   

❶¬α ∨ β 

C)   

❶α ⇔ β 

D)   

❶α ⇒ β 

 
ZAD. 7.    Niech p,q,r będą zmiennymi zdaniowymi. Wskazać  
wyrażenia, które są tautologiami: 
A)   

⓪

  (p

⇒q) ⇔ (¬p∧q)  

 

 B)   

⓪(p∨q) ⇒p 

C)   

❶ (p∨q∨r)⇒ (¬p⇒((q∨r) ∧¬p)) 

 
ZAD. 8.     Jeżeli INT

v

(α

∧ (β∨α))=P to zawsze zachodzi: 

A)  

⓪INT

v

(

β)=P 

B)  

⓪INT

v

(

α)=F 

C)  

❶ INT

v

(α)=P  

D)  

❶ INT

v

(α

∨β)=P  

 
ZAD. 9.   Wyrażenie p jest semantycznie równoważne wyrażeniu: 
A)   

❶p∧ (q∨p) 

B)   

❶p∨ (q∧p) 

C)   

⓪¬p⇒¬q 

D)   

⓪p⇔p 

 
ZAD. 10.    Zakładając, że x,y,z są zmiennymi indywiduowymi, 
 p, q, r 

– symbolami predykatów, wskaż napisy, które  

są poprawnnie zbudowanymi farmułami rachunku kwantyfikatorów: 
A)      

⓪(∀x(p(x, a) ⇔q(b))) ⇒∃x●p(x,q(b)) 

B)      

⓪ (∀x●p(x)) ⇒ (∃x●(q(a,b,x) ∧(¬q(y) ⇔q(y))) 

C)      

⓪∀x ∀y ●((x∧y) ⇔¬(¬x∨¬y))  

D)      

⓪∀y(∃x●(p(x))∧(q(x)⇒r(y)) 

ZAD. 11.    Zakładając, że P, Q są predykatami, x – zmienną  
indywiduową  wskaż, które z poniższych formuł rachunku  
k

wantyfikatorów są tautologiami: 

A)  

⓪(∀x●P(x))⇒(∃x●¬P(x)) 

B)  

❶ ((∀x●(P(x)) ⇒ (∃x●¬P(x))) ⇒(¬(∀x●P(x)) ∨(∀z●P(z)) ∨ (∃x●¬P(x))) 

 

C)  

⓪ (∀x●P(x)⇔Q(x)))⇒((∀x●P(x))⇔∀x●Q(x) 

 
 
 
 
 

ZAD. 12.    Poniższe drzewo ilustruje zostosowanie rachunku  
sekwencji dla sprawdzenia, czy formuła (α

∧β)⇒(α∨β) jest tautologią. 

1)   

→(α

∧β)⇒(α∨β) 

2)   

→(α 

∧β) ∨ ¬ (α∨β) 

3)   

→(α

∧β), ¬(α∨β)   4)   

 

α

∨β→α∧β 

5)   

α,β →α

∧β 

Zakładając, że poprzedni węzeł jest poprawny, określ czy  
poprawnie wyprowadzono węzeł: 
A)   

⓪Nr 2 

B)   

❶

Nr 3  

C)   

❶

Nr 4  

D)   

⓪

Nr  

 
ZAD. 13. Dana jest formuła 

∃x●(P(x,y)∧Q(x,y)), system relacyjny 

 SR=<A

sr

,R

1

,R

2

> oraz interpretacja danej formuły w systemie relacyjnym 

 SR oznaczona I

. Jeżeli nośnik systemu relacyjnego A

sr

={a,b} i relacje: 

 R

1

={<a,b>,<b,a>}, R

2

={<a,a>,<b,b>,<a,b>}, to: 

A)   

⓪Dla I(P)=R

1

 i I(Q)=R

2

 

oraz dla wartościowania v(x)=a i  

v(y)=a formuła jest spełniona 
B)   

⓪Dla I(P)=R

1

 i I(Q)=R

1

 

oraz dla wartościowania v(x)=a i 

v(y)=a formuła jest spełniona  
C)   

❶Dla I(P)=R

2

 i I(Q)=R

1

 

oraz dla wartościowania v(x)=a i  

v(y)=a formuła nie jest spełniona 
 
ZAD. 14.    Na pewnym etapie działania algorytm oparty o rachunek  
sekwentów wyprowadził z formuły F następujący zbiór sekwentów  
– liści drzewa dowodu: 
1)   

¬ α[x::=t

1

], 

β[x::=t

2

] → β  

2)   

α→ α, γ

 

 

3)   

∀x●α→¬α, ¬β 

4)   

¬α→γ, ¬ α, β  

Gdzie t

1

, t

2

 

są różne od x. Na podstawie tego zbioru: 

A)  

❶W drzewie istnieją liście które są aksjomatami  

B)  

⓪Można już stwierdzić, że formuła F jest tautologią  

rachinku kwantyfikatorów 

 

C)  

⓪Nie można jeszcze stwierdzić, że formuła jest tautologią  

rachunku zdań, ani, że nie jest tautologią rachunku kwantyfikatorów 
D)  

⓪Nie można jeszcze stwierdzić, że formuła nie jest tautologią  

rachunku kwantyfikatorów 
 
ZAD. 15.    Poniżej jest dany węzeł N

1

 drzewa dowodu budowanego  

zgodnie z algorytme

m wykorzystującym rachunek sekwentów Gentzena. 

→(

∀x●¬ α∨∀x●¬β) ∨ ¬∀x●¬(α∧β)                         ●N

1w

 

???                                                                        

●N

2

 

W kolejnyme  

węźle N

2

 

drzewa można wstawić sekwent:

 

 

A)  

⓪(∀x●¬α)∧( ∀x●¬β) ∧¬∀x●¬(α∧β)→ 

B)  

❶→∀x●¬ α∨ ∀x●¬β, ¬∀x●¬(α∧β) 

C)  

⓪¬∀x●¬( α∧β) →∀x●¬(α∧β) 

 

D)  

⓪→¬∀x●¬ α, ¬∀x●¬β,¬∀x●¬(α∧β) 

ZAD. 16.    Wskazać, które z podanych niżej reguł są semantycznie 
 

poprawnymi regułami wnioskowania. X, Y są tu dowolnymi formułami, 

 

a ɸ, Γ ,Δ – dowolnymi zbiorami formuł. 

A)  

 

⓪ɸ,X,Y,Γ→ Δ 

 

    ɸ,X

⇒Y,Γ → Δ 

B) 

⓪

  

ɸ →Γ,X,Y 

      

ɸ, ¬Y→¬X, Γ 

C)  

 

❶

 

ɸ,Y→Γ, ¬X, Δ 

        

ɸ, X→ Γ , Δ , ¬Y 

D)  

⓪

 

ɸ →Γ,X,Y, Δ 

    

ɸ→Γ,¬X, Δ     ɸ→Γ,¬Y, Δ   

 
ZAD. 17.    Które pary formuł są równoważne semantycznie: 
A)  

⓪(∀x●∃y● α (x,y)) ∨β (y,z)                       ∀x●∃y●(α(x,y) ∨β(y,z))                 

B)  

❶

 (

∀x●α(x,y)) ∧ γ(z,y)                               ∀w●(α(w,y) ∧ γ(z,y)) 

        

C)  

⓪(∃y ●α(x,y)) ∨ (∀x●β(z,y))             ∃y●∀x● (α(x,y) ∨ β(z,y))               

D)  

⓪∀x●∃y●∀z● γ (x,y,z)                               ∀x●∀y● γ (x,h(y,x),f(y)) 

 
ZAD. 18.    Które pary formuł są równoważne w sensie spełnialności:  
A)  (

∀x●∃y● α (x,y)) ∨β (y,z)            

∀x●∃y●(α(x,y) ∨ β(y,z)) 

B)  

∃y●∀x●α(x,y,z)                          

∀x●α(x,g(x,y),z) 

C)  

∀z●∃y●∀x●β(z,y,x)                    

∀z●∀x● β (z,h(z),x) 

D)  

❶

∀y●∀x ●β(x,g(x,y),y) 

               

∀x●∀y●β (x,h(x,y),y) 

 
ZAD. 19.    Dane są dwie klauzule: lubi(x,EWA) oraz  
lubi(ojciec(PIOTR),y) 
Najbardziej ogólny unifikator tych klauzul to: 
A)   

⓪{x:=y} 

B)   

⓪{x:=PIOTR,y:=EWA} 

C)   

❶{x:=ojciec(PIOTR),y:=EWA} 

 

D)   

⓪Nie istnieje 

 
ZAD. 20.    Dany jest zbiór klauzul S={¬p

∨q, ¬r∨q, p∨r}. 

Wskaż które z poniżej podanych klauzul są wyprowadzalne 
 ze zbioru S przez zastosowanie zasady rezolucji:00 
A)   

❶p∨q 

B)   

❶q  

C)   

⓪¬q 

D)   

❶sq∨p 

 
 
 

GRUPA 3 
 
ZAD. 1.    Które ze zdefiniowanych relacji są relacjami równoważności 
A)   

❶X-zbiór osób zdających egzamin, o

1

,o

2

∈X; 

o

1 

R o

2

 

⇔o

1 

jest tej samej 

płci co o

2

 

B)   

⓪X-zbiór samochodów na parkingu s

1

,s

2

∈X 

s

1 

R s

2

 

⇔różnica cen samochodów s

1

 i s

2

 jest mniejsza od  

K(pewna stała kwota) 
C)   

⓪X-zbiór krzeseł w sali,  k

1

,k

2

∈X;  

k

1 

R k

2

 

⇔ k

2 

znajduje się w odległości większej, niż 

 

r (pewna stała odległość) od k

1

 

D)   

⓪X-zbiór funkcji zmiennej x, f

1

,f

2

∈X;  

 

 

f

1 

R f

2

 

⇔ ∃x●(f

1

(x)=f

2

(x))  

 
ZAD. 2.     Niech R

1

 ,R

 2

 

będą relacjami równoważności na zbiorze X. 

Wówczas relacjami równoważności są również relacje: 
A)   

⓪R

1

∪R

 2  

 

B)   

⓪R

1

\R

 2

  

C)   

⓪R

1

\Y

2

, gdzie Y

⊂X 

 

 

D)   

⓪

 (X

2

\R

 1

) ∩R

2

 

 

 

 ZAD. 3.  Niech A, B, C będą dowolnymi zbiorami. Prawdą jest, że: 
A)      

⓪card(A)=card(B)⇒A\B=∅ 

B)      

⓪(A\B) ∪C=C⇔A=B 

 

C)      

❶2

A

∩2

B

=2

A∩B

 

D)      

⓪(A\B)∪(B\A)=∅ 

 
ZAD. 4.      Dana jest funkcja f: X→Y całkowicie określona na X.  
Niech R

⊆X² będzie relacją binarną na X określoną następująco:  

<x,y>

∈R wtedy i tylko wtedy, gdy f(x)=f(y). Wskaż,  

k

tóre z własności posiada relacja R: 

A)   

❶R jest relacją zwrotną 

B)   

⓪R jest relacją antysymetryczną 

C)   

❶R jest relacją spójną  

 
ZAD. 5.   Dana jest gramatyka G=

df

<.,+,-,0,1,2,3,4,5},{S,R

1

,R

2

,X},P,S> 

gdzie zbiór produkcji  P jest zdefiniowany następująco: 
P=

df

{S::=R

1

|R

2

|R

1

.R

2 

         R1::=XR

1

|X        R

2

::=+R

1

|-R

1

    

X::=0|1|…|5} 

Które z poniższych słów należy do języka L(G): 
A)   

⓪+012.

 

 

B)   

⓪12.1.1 

C)   

⓪-0.000 

D)   

⓪000.123 

 
ZAD. 6.      Niech formuły α  i  β będą tautologiami  rachunku  
kwantyfikatorów. Które z poniższych formuł są również  
tautologiami rachunku kwantyfikatorów: 
A)   

⓪¬α ∧¬ β 

B)   

❶¬α ∨ β 

C)   

❶α ⇔ β 

D)   

❶α ⇒ β 

 
ZAD. 7.     Niech p,q,r będą zmiennymi zdaniowymi.  
Wskazać wyrażenia, które są tautologiami: 
A)   

❶ (p∨(q∧r)) ⇔ ((p∨q) ∧(p∨r)) 

B)   

⓪(p⇒q) ⇔ (p∨¬q) 

C)   

⓪(((p∧q) ⇒r) ∧ ((p∧ q) ⇒¬r)) ⇒ (¬p∧ ¬q∧ ¬r) 

 
ZAD. 8.     Jeżeli INT

v

(α

⇒β)=F to zawsze zachodzi: 

A)   

❶INT

v

(α)=P oraz INT

v

(β)=F 

B)   

⓪INT

v

(α)=F lub INT

v

(β)=P 

C)   

⓪INT

v

(¬α

∨β)=P 

D)   

⓪INT

v

(α 

∨¬β)=F 

 
ZAD. 9.    Wyrażenie p

⇒q jest semantycznie  

równoważne wyrażeniu: 
A)  

⓪ ¬ (p∧q) 

B)  

❶ ¬ (p∧¬ q) 

C)  

❶ (p⇔q) ∨¬(q⇒p)  

D)  

⓪ ¬(p⇔p) ∧(q⇒p) 

 
ZAD. 10.    Zakładając, że  x,y,z są zmiennymi indywiduowymi,  
p, q, r 

– symbolami predykatów, wskaż napisy, które są poprawnie  

zbudowanymi formułami rachunku kwantyfikatorów: 
A)  

⓪∀x∀y● p(x, z) ⇔x∈ {y:y≥z} 

B)  

❶

∀x●¬(x⇔x)) ⇒ ∃y●¬(y⇔y)) 

 

C)  

⓪∀x∃y ●p(x) ⇒(∃z●q(x,y,z) ∧(¬r(y) ⇔r(y)))

 

 

D)      

❶∀x(∃x●(p(x))∧(q(x))) 

 
ZAD. 11.    Zakładając, że P, Q są predykatami, x, y – zmiennymi  
indywiduowymi wskaż, które z poniższych formuł rachunku 
kwantyfikatorów są tautologiami: 
A)  

❶

(

∀x●∀y●P(x,y))⇒∃x●∀y ●P(x,y)

 

 

B)  

⓪ (¬∀x ●∀y ● P(x,y)∨ ∃x●∀y ●P(x,y)) ⇔(∀x●∀y●P(x,y) ∧∀x●∃x●¬P(x,y))  

C)  

⓪ (∀x●P(x)⇔Q(x))⇒(∀x●P(x)⇔∀x●Q(x))  

 

ZAD. 12.    Dana jest formuła 

∃x●(P(x,y)∧Q(x,y)), system relacyjny  

SR=<A

SR

,R

1

,R

2

> oraz interpretacja danej formuły w systemie relacyjnym  

SR oznaczona I

. Jeżeli nośnik systemu relacyjnego A

SR

={a,b} i relacje:  

R

1

={<a,b>,<b,a>}, R

2

={<a,a>,<b,b>,<a,b>}, to: 

A)  

⓪Dla I(P)=R

1

 i I(Q)=R

2

 

oraz dla wartościowania v(x)=a i  

v(y)=a formuła jest spełniona 
B)  

⓪Dla I(P)=R

1

 i I(Q)=R

1

 

oraz dla wartościowania v(x)=a i  

v(y)=a formuła jest spełniona 
C)  

❶Dla I(P)=R

2

 i I(Q)=R

1

 

oraz dla wartościowania v(x)=a i  

v(y)=a formuła nie jest spełniona  
 
ZAD. 13. Poniższe drzewo ilustruje zostosowanie rachunku  
sekwencji dla sprawdzenia, czy formuła ¬ (α

⇔ β) jest tautologią. 

1)   

→¬ (α

⇒β), ¬ (β ⇒ α) 

2)   

α

⇒β→ ¬ (β ⇒ α) 

3)   

α,β→ ¬ (β 

⇒ α) 

4)   

α,β, β

⇒ α→ 

5)   

α,β, β, α→ 

Zakładając, że poprzedni węzeł jest poprawny, określ czy  
poprawnie wyprowadzono węzeł: 
A)   

❶Nr 2 

B)   

⓪Nr 3 

C)   

❶Nr 4 

D)   

⓪Nr 5 

 
ZAD. 15.   Wskazać, które z podanych niżej reguł są semantycznie  
poprawnymi regułami wnioskowania. X, Y są tu dowolnymi formułami,  
a ɸ, Γ ,Δ – dowolnymi zbiorami formuł. 
A)  

⓪     ɸ,X,Y,Γ→ Δ 

ɸ,X

⇒Y,Γ → Δ 

B)  

⓪     ɸ →Γ,X,Y   

ɸ, ¬Y→¬X, Γ 

C)  

❶     ɸ,Y→Γ, ¬X, Δ 

ɸ, X→ Γ , Δ , ¬Y 

D)  

⓪ 

ɸ →Γ,X,Y, 

 

ɸ→Γ,¬X, Δ        ɸ→Γ,¬Y, Δ 

 
ZAD. 16. Poniżej jest dany węzeł N

1

 drzewa dowodu budowanego  

zgodnie z algorytmem wykorzystującym rachunek sekwentów Gentzena. 
(¬ α

∨¬β) [x::=t] → ¬∀x●¬(α∧β), ∀x●¬α, ∀x●¬β     ●N

1

 

???                                                                        

●N

2

 

W kolejnym węźle N

2

 

drzewa można wstawić sekwent: 

A)   

∀x●¬(α∧β) [x::=t] → ¬∀x●¬(α∧β), ∀x●¬α, ∀x●¬β 

B)   

¬(α

∧β) → ¬∀x●¬(α∧β), ∀x●¬α, ∀x●¬β 

C)  

⓪ 

¬α[x::=t] 

∧¬α[x::=t] →¬∀x●¬(α∧β), ∀x●¬α, ∀x●¬β 

D)  

⓪ 

(¬α

∧¬β) [x::=t] → ¬∀x●¬(α∧β), ∀x●¬α, ∀x●¬β 

gdzie t jest pewnym termem różnym od x 
 
ZAD. 17.   Które pary formuł są równoważne semantycznie: 
A)  

⓪(∀x●∃y● α (x,y)) ∨β (y,z)                      ∀x●∃y●(α(x,y) ∨β(y,z)) 

B)  

❶∀x●α(x,y)) ∧ γ(z,y))                               ∀w●(α(w,y) ∧ γ(z,y)) 

C)  

⓪(∃y ●α(x,y)) ∨ (∀x●β(z,y))                     ∃x●∀y● (α(x,y) ∨ β(z,y))  

D)  

⓪∀x●∃y●∀z● γ (x,y,z)                             ∀x●∀y● γ (x,h(y,x),f(y)) 

 
ZAD. 18.    Które pary formuł są równoważne w sensie spełnialności: 
A)  

❶ ∀x●∃y●( α (x,y) ∨β (y,z))      

∀x●∃y●(α(x,y) ∨ β(y,z)) 

B)  

⓪∃y●∀x●α(x,y,z)                     

∀x●α(x,g(x,y),z) 

C)  

❶∀z●∃y●∀x●β(z,y,x)               

∀z●∀x● β (z,h(z),x) 

D)  

❶∀y●∀x ●β(x,g(x,y),y)             

∀x●∀y●β (x,h(x,y),y) 

 
ZAD. 19.   Dane są dwie klauzule: lubi(x,EWA) oraz  
lubi(matka(PIOTR),y) 
Najbardziej ogólny unifikator tych klauzul to: 
A)   

⓪{x:=y} 

B)   

⓪{x:=PIOTR,y:=EWA} 

C)   

❶{x:=matka(PIOTR),y:=EWA} 

D)   

⓪Nie istnieje 

 
ZAD. 20. Dany jest zbiór klauzul S={¬p

∨q, ¬p∨s, ¬q, ¬s}. Wskaż które  

z poniżej podanych klauzul są wyprowadzalne ze zbioru S przez  
zastosowanie zasady rezolucji: 
A)  

⓪ ¬q ∨ s 

B)  

❶ ¬p 

C)  

⓪ q 

D)  

⓪ q ∨ p