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. 

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 kwantyfikatoró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 5 

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 algorytmem wykorzystującym rachunek sekwentów 

Gentzena. 
→(∀x●¬ α∨∀x●¬β) ∨ ¬∀x●¬(α∧β) 

 

●N

1 

???   

 

 

 

●N

2 

W koloejnym 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: 
A) 

p∨q 

B) 

q 

C) 

¬q 

D) 

q∨p