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

   1. ❶R jest relacją równoważności

   2. ⓪R jest symetryczna i zwrotna, ale nie jest przechodnia

   3. ❶Pary <l,k> oraz <l,k>, gdzie k jest pewną liczbą naturalną, są ze sobą w relacji R

   4. ⓪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

2. Niech R₁ ,R ₂ będą relacjami równoważności na zbiorze X. Wówczas relacjami równoważności są również relacje:

   1. ⓪R₁\R ₂

   2. ⓪X²\R ₂

   3. ⓪(R₁\R ₂)∪ (R₂\R₁)

   4. ⓪(R₁∪R ₂) \R₁

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

   1. ⓪card(A)=card(B)⇒A∪B=A

   2. ❶A∪(B\A)=A∪B

   3. ❶Jeżeli x∈A oraz x∉B, to {x}∈2^A∪B

   4. ⓪(A\B)∪(B\A)=∅⇔A∩B=∅

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:

   1. ⓪R jest relacją antysymetryczną

   2. ❶R jest relacją spójną

   3. ❶R jest relacją przechodnią

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:

   1. ⓪P=_df{S::=a|AB, A::=b|bcA, B::=a|aB}

   2. ⓪P=_df{S::=ab|cA|B,A::=bc|A|a , B::=a|b|c}

   3. ⓪P=_df{S::=a|B|A, B::=b|BA, A::=a|A|b}

   4. ❶P=_df{S::=B|A, B::=aB|bcB|a, A::=a|Aa}

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:

   1. ⓪α ∧ β

   2. ❶α ∨ β

   3. ⓪α ⇔ β

   4. ❶α ⇒ β

7. Niech p,q,r będą zmiennymi zdaniowymi. Wskazać wyrażenia, które są tautologiami:

   1. ❶ (¬(p⇒q) ∧ (q⇒p)) ⇒ (p∧¬q)

   2. ⓪((p∨q) ∧ (p⇒q)) ⇒ (q⇒p)

   3. ❶ ((p∨q) ⇒r) ⇒ ((p⇒r) ∨ (q⇒r))

   4. ⓪(p⇒(q∨r)) ⇒ (p ⇒q)

8. Jeżeli INT_v(α∨(β∧α))=P to zawsze zachodzi:

   1. ⓪INT_v(β)=P

   2. ❶INT_v(α)=P

   3. ⓪INT_v(α)=F

   4. ❶INT_v(α∨β)=P

9. Wyrażenie ¬p jest semantycznie równoważne wyrażeniu:

   1. ⓪p∨(¬q∧p)

   2. ❶¬p∧ (q∨¬p)

   3. ⓪p⇒q

   4. ⓪¬p⇔¬p

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:

    1. ❶∀x●p(x, true)

    2. ❶∀x●(¬(x⇒x)⇔(x∧¬x))

    3. ⓪(∃x●p(a,b,c)∧(¬q(y)⇔q(y)))⇒∀x●(p(x)∧q(y))

    4. ❶∀x●(∃x●((p(x)∧∃x●q(x))⇒r(x))∧∃x●s(x))

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:

    1. ❶ (∀x●P(x))⇒(∃x●P(x))

    2. ⓪(∃x●(¬P(x)∨¬Q(x)))∨∃x●(P(x)∧Q(x))

    3. ❶ (∀x●P(x)⇔Q(x)))⇒(∀x●P(x)⇔∀x●Q(x))

12. Dana jest formuła ∃x●(P(x,y)∧Q(x,y)), system relacyjny SR=<A_sr,R₁,R₂> oraz interpretacja danej formuły w systemie relacyjnym SR oznaczona I. Jeżeli nośnik systemu relacyjnego A_sr={a,b} i relacje: R₁={<a,b>,<b,a>}, R₂={<a,a>,<b,b>,<a,b>}, to:

    1. Dla I(P)=R₁ i I(Q)=R₂ oraz dla wartościowania v(x)=a i v(y)=a formuła jest spełniona

    2. Dla I(P)=R₁ i I(Q)=R₁ oraz dla wartościowania v(x)=a i v(y)=a formuła jest spełniona

    3. Dla I(P)=R₂ i I(Q)=R₁ oraz dla wartościowania v(x)=a i v(y)=a formuła nie jest spełniona

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ł:

1. ❶Nr 2

2. ❶Nr 3

3. ⓪Nr 4

4. ⓪Nr 5

13. 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₁], β[x←t₂] → β

    2. α[x←t₁, x←t₃]→ α, β

    3. α, β →¬α, β

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

Na podstawie tego zbioru:

1. Nie można jeszcze stwierdzić, że formuła jest tautologią rachunku zdań, ani, że nie jest tautologią rachunku kwantyfikatorów

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

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

4. Nie można jeszcze stwierdzić, że formuła nie jest tautologią rachunku kwantyfikatorów

14. Poniżej jest dany węzeł N₁ drzewa dowodu budowanego zgodnie z algorytmem wykorzystującym rachunek sekwentów Gentzena.

→∀x●¬ α∨∀x●¬β, ¬∀x●¬(α∧β) ●N₁

??? ●N₂

W kolejnym węźle N₂ drzewa można wstawić sekwent:

1. ⓪¬∀x●¬(α∧β) →∀x●¬(α∧β)

2. ⓪ ∀x●¬α∧∀x●¬β∧¬∀x●¬(α∧β)→

3. ❶→∀x●¬ α,∀x●¬β, ¬∀x●¬(α∧β)

4. ❶¬∀x●¬ α, ¬∀x●¬β→¬∀x●¬(α∧β)

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ł.

    1. ⓪ɸ→ Γ,X⇔Y
       ɸ,X,Y→Γ ɸ→Γ, X,Y

    2. ⓪ɸ,X⇔Y→Γ
       ɸ,X→Γ,Y ɸ,Y→ Γ,X

    3. ❶ɸ→Γ,X∨Y
       ɸ, ¬X→ Γ ,Y

    4. ❶ɸ,X∧Y→Γ
       ɸ,X→Γ,¬Y

17. Które pary formuł są równoważne semantycznie ( str 167)

    1. ⓪(∀x●α(x,y))⇒(∃y●β(z,y)) ∀x●∃y●(α(x,y) ⇒ β(z,y))

    2. ⓪∀z●∃y●∀z●α(x,z,f(z)) ∀z●∀x●α(x,h(z,x),f(y))

    3. ❶ (∀x●α(x,y)) ∨ (∃y●β(z,y)) ∀x●∃y● (α(x,y) ∨ β(z,y))

    4. ⓪∀y●∃z●∀x ●β(x,h(y),z) ∀y●∀x●β (x,h(y),f(x))

18. Które pary formuł są równoważne w sensie spełnialności:

    1. ⓪(∀x●∃y● α (x,y)) ⇒β (y,z) ∀x●∃y●(α(x,y) ⇒ β(y,z))

    2. ⓪∃y●∀x●α(x,y,z) ∀x●α(x,g(y),z)

    3. ❶∀z●∃y●∀x●β(z,y,x) ∀z●∀x● β (z,h(z),x)

    4. ❶∀y●∀x ●β(x,g(x,y),y) ∀x●∀y●β (x,h(x,y),y)

19. Dane są dwie klauzule: kocha(PIOTR, x) oraz lubi(ojciec(EWA),y)
    Najbardziej ogólny unifikator tych klauzul to:

    1. ⓪{x:=y}

    2. ⓪{x:=EWA,y:=PIOTR}

    3. ⓪{x:=ojciec(EWA),y:=PIOTR}

    4. ❶Nie istnieje

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:

    1. ⓪¬q∨s

    2. ⓪p∨q

    3. ⓪¬q ∨r

    4. ❶q∨s