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