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₂ siedzi po prawej stronie o₁

   2. ⓪X-zbiór samochodów na parkingu s₁,s₂∈X;
      s₁ R s₂ ⇔s₁ przejechał co najmniej tylke kilometrów, ile przejechał s₂

   3. ❶X-zbiór krzeseł w sali, k₁,k₂∈X;
      k₁ R k₂ ⇔ gdy oba krzesła są zajęte lub oba krzesła są wolne

   4. ❶X-zbiór funkcji zmiennej x, niech 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₁∩R ₂)∪ R₂

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

3. Niech A=_df{a,b}, B=_df{b,c}. Prawdą jest, że:

   1. ❶card(2^A∪B)=2³

   2. ❶ (A\B)∪B={a,b,c}

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

   4. ⓪{∅, a, {b}} ⊂ 2^A

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.

   1. ❶R jest relacją zwrotną

   2. ⓪R jest relacją antysymetryczną

   3. ⓪R jest relacją spójną

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

   1. ⓪+012

   2. ❶0-1+0

   3. ⓪1++1

   4. ⓪-1+0-1

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) ⇔ (¬p∧q)

   2. ⓪(p∨q) ⇒p

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

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

   1. ⓪INT_v(β)=P

   2. ⓪INT_v(α)=F

   3. ❶ INT_v(α)=P

   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 – symbolami predykatów, wskaż napisy, które są poprawnnie zbudowanymi farmułami rachunku kwantyfikatorów: ( formuła jest poprawna kiedy kiedy nie ma zmiennej wolnej )

    1. ❶ (∀x(p(x, a) ⇔q(b))) ⇒∃x●p(x,q(b))

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

    3. ⓪∀x ∀y ●((x∧y) ⇔¬(¬x∨¬y))

    4. ⓪∀y(∃x●(p(x))∧(q(x)⇒r(y))

11. Zakładając, że P, Q są predykatami, x – zmienną indywiduową wskaż, które z poniższych formuł rachunku kwantyfikatorów są tautologiami:

    1. ⓪(∀x●P(x))⇒(∃x●¬P(x))

    2. ❶ ((∀x●(P(x)) ⇒ (∃x●¬P(x))) ⇒(¬(∀x●P(x)) ∨(∀z●P(z)) ∨ (∃x●¬P(x)))

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

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

1. ⓪Nr 2

2. ❶Nr 3

3. ❶Nr 4

4. ⓪Nr 5

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. 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. α→ α, γ

    3. ∀x●α→¬α, ¬β

    4. ¬α→γ, ¬ α, β

Gdzie t₁, t₂ są różne od x. Na podstawie tego zbioru:

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

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

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 koloejnym węźle N₂ drzewa można wstawić sekwent:

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

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

3. ❶¬∀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,Γ → Δ

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

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

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

17. 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)) ∃y●∀x● (α(x,y) ∨ β(z,y))

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

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(x,y),z)

    3. ❶∀z●∃y●∀x●β(z,y,x) ∀z●∀x● β (z,h(z),x) // postać skolemowska jeślimamy kw.szcz to podstawiamy f stałą

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

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

    1. ⓪{x:=y}

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

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

    4. ⓪Nie istnieje

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:

    1. ❶p∨q

    2. ❶q

    3. ⓪¬q

    4. ❶q∨p