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

⇔s

1

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ż, 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=

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ą poprawnnie

zbudowanymi farmuł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. 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]→¬α, ¬β

2)

a[x::=y]→ α

3)

∀x●α→α, ¬β

4)

¬α→γ, ¬ α, β

Gdzie t jest różne od x. Na podstawie tego zbioru:

A)

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

B)

Można już stwierdzić, że formuła F nie 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. 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. 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