Sztuczna inteligencja/SI Ćwiczenia 2

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. $\mathrm{\neg }Q(a,f(f(a)))$
2. $Q(g(g(c)),c)$
3. $\mathrm{\neg }R(a,f(b))$

Zadanie 3

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

Zadanie 4

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

1. $\frac{\alpha \to \beta ,\beta \to \gamma }{\alpha \to \gamma }$
2. $\frac{\alpha \to \beta ,\beta \to \gamma ,\alpha }{\gamma }$
3. $\frac{\alpha \vee \beta ,\alpha \vee \mathrm{\neg }\beta }{\alpha }$
4. $\frac{\alpha \to \beta }{\mathrm{\neg }\beta \to \mathrm{\neg }\alpha }$
5. $\frac{\alpha \to \beta }{\mathrm{\neg }\alpha \to \mathrm{\neg }\beta }$
6. $\frac{\alpha \to (\beta \to \gamma )}{\beta \to (\alpha \to \gamma )}$

Zadanie 5

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

1. $(P(x,y)\to (Q(y,z)\wedge \mathrm{\neg }R(x,z)))\vee Q(x,y,z)$
2. $(P(x,y)\wedge Q(y,z))\leftrightarrow (\mathrm{\neg }R(x,y)\vee S(y,z))$

Zadanie 6

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

1. $(\mathrm{\forall }x)(\mathrm{\forall }y)P(x,y)\to ((\mathrm{\exists }z)(\mathrm{\forall }y)(Q(y,z)\wedge \mathrm{\neg }R(x,z)))\vee Q(x,y,z)$
2. $(P(x,y)\wedge Q(y,z))\leftrightarrow (\mathrm{\neg }R(x,y)\vee S(y,z))$

Zadanie 7

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

1. $P(a,f(g(x)))\wedge Q(g(y),b)\to R(x,c)$
   $P(y,f(v))\wedge Q(z,b)\to R(g(z),z)$
2. $\mathrm{\neg }P(z,a,f(y))\wedge (Q(y,b)\to R(c,g(z)))\vee S(f(a),g(b),z)$
   $\mathrm{\neg }P(b,v,f(a))\wedge (Q(z,x)\to R(w,g(a)))\vee S(f(z),g(x),y)$

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 przysta 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 \vee \beta$ oraz $\alpha \to (\beta \to \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?

Zadanie 11

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

Zadanie 12

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