1. Które ze zdefiniowanych relacji są relacjami równoważności

   1. ❶X-zbiór osób zdających egzamin, o₁,o₂∈X;
      o₁ R o₂ ⇔o₁ jest tej samej płci co o₂

   2. ⓪X-zbiór samochodów na parkingu s₁,s₂∈X;
      s₁ R s₂ ⇔s₁ różnica cen samochodów s₁ i s₂ jest mniejsza od K(pewna stała kwota)

   3. ⓪X-zbiór krzeseł w sali, k₁,k₂∈X;
      k₁ R k₂ ⇔ k₂ znajduje się w odległości większej, niż r (pewna stała odległość) od k₁

   4. ⓪X-zbiór funkcji zmiennej x, f₁,f₂∈X;
      f₁ R f₂ ⇔ ∃x●(f₁(x)=f₂(x))

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. ⓪R₁\R ₂

   3. ⓪R_1\Y², gdzie Y⊂X

   4. ❶ (X²\R ₁) ∩R₂

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

   1. ⓪card(A)=card(B)⇒A\B=∅

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

   3. ❶2^A∩2^B=2^A∩B

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

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

   2. ⓪R jest relacją antysymetryczną

   3. ⓪R jest relacją spójną

5. Dana jest gramatyka G=_df<.,+,-,0,1,2,3,4,5},{S,R₁,R₂,X},P,S>,gdzie zbiór produkcji P jest zdefiniowany następująco:
   P=_df{S::=R₁|R₂|R₁.R₂ R1::=XR₁|X R₂::=+R₁|-R₁ X::=0|1|…|5}
   Które z poniższych słów należy do języka L(G):

   1. ⓪+012.

   2. ⓪12.1.1

   3. ⓪-0.000

   4. ⓪000.123

6. Niech formuły α i β będą tautologiami rachunku kwantyfikatorów. Które z poniższych formuł są również 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∧r)) ⇔ ((p∨q) ∧(p∨r))

   2. ⓪(p⇒q) ⇔ (p∨¬q)

   3. ⓪(((p∧q) ⇒r) ∧ ((p∧ q) ⇒¬r)) ⇒ (¬p∧ ¬q∧ ¬r)

8. Jeżeli INT_v(α⇒β)=F to zawsze zachodzi:

   1. ❶INT_v(α)=P oraz INT_v(β)=F

   2. ⓪INT_v(α)=F lub INT_v(β)=P

   3. ⓪INT_v(¬α∨β)=P

   4. ⓪INT_v(α ∨¬β)=F

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

   1. ⓪¬ (p∧q)

   2. ❶¬ (p∧¬ q)

   3. ❶ (p⇔q) ∨¬(q⇒p)

   4. ⓪¬(p⇔p) ∧(q⇒p)

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:

    1. ⓪∀x∀y● p(x, z) ⇔x∈ {y:y≥z}

    2. ⓪∀x●¬(x⇔x)) ⇒ ∃y●¬(y⇔y))

    3. ⓪∀x∃y ●p(x) ⇒(∃z●q(x,y,z) ∧(¬r(y) ⇔r(y)))

    4. ❶∀x(∃x●(p(x))∧(q(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●∀y●P(x,y))⇒∃x●∀y ●P(x,y)

    2. ⓪(¬∀x ●∀y ● P(x,y)∨ ∃x●∀y ●P(x,y)) ⇔(∀x●∀y●P(x,y) ∧∀x●∃y●¬P(x,y))

    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]→¬α, ¬β

    2. a[x::=y]→ α

    3. ∀x●α→α, ¬β

    4. ¬α→γ, ¬ α, β

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

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

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

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

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

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,Γ → Δ

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

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

    4. ⓪ɸ →Γ,X,Y, Δ
       ɸ→Γ,¬X, Δ | ɸ→Γ,¬Y, Δ

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

(¬ α∨¬β) [x::=t] → ¬∀x●¬(α∧β), ∀x●¬α, ∀x●¬β ●N₁

??? ●N₂

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

1. ⓪∀x●¬(α∧β) [x::=t] → ¬∀x●¬(α∧β), ∀x●¬α, ∀x●¬β

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

3. ⓪¬α[x::=t] ∧¬α[x::=t] →¬∀x●¬(α∧β), ∀x●¬α, ∀x●¬β

4. ⓪(¬α∧¬β) [x::=t] → ¬∀x●¬(α∧β), ∀x●¬α, ∀x●¬β
   gdzie t jest pewnym termem różnym od x

16. Które pary formuł są równoważne semantycznie:

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

    2. ❶∀x●α(x,y)) ∧ γ(z,y)) ∀w●(α(w,y) ∧ γ(z,y))

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

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

17. 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(x,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)

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

    1. ⓪{x:=y}

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

    3. ❶{x:=matka(PIOTR),y:=EWA}

    4. ⓪Nie istnieje

19. 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:

    1. ⓪¬q∨s

    2. ❶¬p

    3. ⓪q

    4. ⓪q∨p