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ą równoważności 

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

1

 

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

A)  ⓪card(A)=cadr(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 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. 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) 

α[x←t

1

, x←t

3

]→ α, β 

3) 

 α, β →¬α, β 

4) 

¬∃x●¬α→γ, ¬∀x● α, β 

Na podstawie tego zbioru: 

A)  Nie można jeszcze stwierdzić, że formuła jest tautologią rachunku zdań, ani, że nie jest tautologią rachunku 

kwantyfikatorów 

B) 

Można już stwierdzić, że formuła F jest tautologią rachinku kwantyfikatorów 

C) 

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

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●¬(α∧β) 
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