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