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