Sztuczna inteligencja/SI Ćwiczenia 2

From Studia Informatyczne

Spis treści

Zadanie 1

Zapisać następujące stwierdzenia w języku logiki predykatów, wprowadzając niezbędne symbole i ustalając ich interpretację:

  1. ojciec każdego człowieka jest jego bezpośrednim przodkiem,
  2. jeśli ktoś jest przodkiem bezpośredniego przodka pewnej osoby, to jest także przodkiem tej osoby,
  3. każdy jest spokrewniony z każdym swoim przodkiem,
  4. każdy jest spokrewniony ze swoim bratem i siostrą,
  5. każdy jest spokrewniony z braćmi i siostrami wszystkich osób spokrewnionych ze sobą.

Zadanie 2

Dla bazy wiedzy dotyczącej świata klocków podanej w przykładzie wnioskowania znaleźć wyprowadzenia (jeśli istnieją) następujących formuł:

  1. \neg Q(a, f(f(a))) \,
  2. Q(g(g(c)),c) \,
  3. \neg R(a,f(b)) \,

Zadanie 3

Sprawdzić, czy z bazy wiedzy \Gamma\, można wyprowadzić formuły \beta_i\, dla poniższych \Gamma\, i \beta\,. W razie potrzeby można wprowadzić dodatkowe reguły wnioskowania, sprawdzając uprzednio ich poprawność.

1.

\Gamma: P(x,y) \land Q(y,z) \rightarrow R(x,y)
R(x,y) \land S(z,v) \land W(y,v) \rightarrow W(x,z)
\neg Q(x,y) \rightarrow Q(y,x)
P(a,b)
\neg Q(c,b)
S(d,e)
W(c,e)
\beta_1:\;\;W(a,d)
\beta_2:\;\;W(d,e) \rightarrow W(a,d)

2.

\Gamma: P(a) \lor P(b) \lor P(c)
Q(x,y) \land R(y,d) \rightarrow \neg P(x)
S(x,y) \rightarrow Q(x,y) \lor U(x,y)
S(a,e)
\neg U(a,e)
R(e,d)
\beta_1:\;\;P(a) \rightarrow P(b)
\beta_2:\;\;\neg P(a) \land P(b)
\beta_3:\;\;Q(a,e) \land \neg P(a)
\beta_4:\;\;P(b) \lor P(c)
\beta_5:\;\;\neg (P(a) \lor P(b) \lor P(c))
\beta_6:\;\;\neg P(b) \land \neg P(c) \rightarrow P(a)

3.

\Gamma: Z(x,y) \rightarrow S(x,y)
L(x,y) \rightarrow Z(x,y)
Z(x,y) \land L(y,z) \rightarrow S(x,z)
\neg S(x,y) \rightarrow \neg L(x,y)
Z(x,y) \land L(y,x) \rightarrow L(x,y)
Z(x,y) \land L(x,z) \land L(z,y) \rightarrow L(x,y)
L(x,f(x))
L(a,b)
L(f(a),c)
L(c,d)
Z(a,c)
Z(a,d)
Z(b,d)
\beta_1:\;\;L(b,c)
\beta_2:\;\;L(b,d)
\beta_3:\;\;L(c,f(a))

Zadanie 4

Które z następujących reguł wnioskowania są poprawne:

  1. \frac{\alpha\rightarrow\beta, \; \beta\rightarrow\gamma}{\alpha\rightarrow\gamma}
  2. \frac{\alpha\rightarrow\beta, \; \beta\rightarrow\gamma, \; \alpha}{\gamma}
  3. \frac{\alpha\lor\beta, \; \alpha\lor\neg\beta}{\alpha}
  4. \frac{\alpha\rightarrow\beta}{\neg\beta\rightarrow\neg\alpha}
  5. \frac{\alpha\rightarrow\beta}{\neg\alpha\rightarrow\neg\beta}
  6. \frac{\alpha\rightarrow(\beta\rightarrow\gamma)}{\beta\rightarrow(\alpha\rightarrow\gamma)}

Zadanie 5

Sprowadzić następujące formuły do postaci CNF:

  1. (P(x,y)\rightarrow(Q(y,z)\land\neg R(x,z)))\lor Q(x,y,z)
  2. (P(x,y)\land Q(y,z))\leftrightarrow(\neg R(x,y)\lor S(y,z))

Zadanie 6

Sprowadzić następujące formuły do postaci standardowej Skolema:

  1. (\forall x)(\forall y)P(x,y) \rightarrow ((\exists z)(\forall y)(Q(y,z) \land \neg R(x,z))) \lor Q(x,y,z)
  2. (P(x,y) \land Q(y,z)) \leftrightarrow (\neg R(x,y) \lor S(y,z))

Zadanie 7

Dokonać unifikacji następujących par formuł:

  1. P(a, f(g(x))) \land Q(g(y), b) \rightarrow R(x,c)
    P(y, f(v)) \land Q(z,b) \rightarrow R(g(z),z)
  2. \neg P(z,a,f(y)) \land (Q(y,b) \rightarrow R(c, g(z))) \lor S(f(a),g(b),z)
    \neg P(b,v,f(a)) \land (Q(z,x) \rightarrow R(w, g(a))) \lor S(f(z),g(x),y)

Rozwiązanie

Zadanie 8

Zweryfikować przedstawiony niżej przebieg wnioskowania prowadzonego przez człowieka zapisując bazę wiedzy w postaci formuł logiki predykatów i sprawdzając poprawność kroków dowodu.

  1. Wszystkie liczby podzielne przez 2 są parzyste.
    Dowolna liczba o 1 większa od liczby parzystej nie jest parzysta.
    Żadna liczba parzysta nie jest podzielna przez 3.
    Niektóre liczby nieparzyste są podzielne przez 3.
    Z powyższego wynika, że każda liczba podzielna przez 3 jest o 1 większa od pewnej liczby podzielnej przez 2.
  2. Nie wszystkie trójki punktów na płaszczyźnie są współliniowe.
    Jeżeli trzy punkty na płaszczyźnie nie są współliniowe, to są wierzchołkami pewnego trójkąta.
    Jeśli z czterech punktów żadne trzy nie są współliniowe, to są one wierzchołkami pewnego czworokąta.
    Z powyższego wynika, że:
    • istnieje trójkąt,
    • istnieje czworokąt,
    • jeśli ABC, BCD, ABD i ACD są trójkątami, to ABCD jest czworokątem.

Zadanie 9

Czy system wnioskowania z dwoma aksjomatami \alpha\lor\beta \, oraz \alpha\rightarrow(\beta\rightarrow\alpha) \, i regułą wnioskowania modus ponens jest pełny?

Zadanie 10

Czy można sformułować pełny i poprawny system wnioskowania bez aksjomatów?

Rozwiązanie

Zadanie 11

Czy można sformułować pełny i poprawny system wnioskowania bez reguł wnioskowania?

Rozwiązanie

Zadanie 12

Zaproponować odpowiedniki reguł modus ponens i modus tollens dla formuł w postaci CNF.

Rozwiązanie