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ść.

1.

$\mathrm{\Gamma }:$ $P(x,y)\wedge Q(y,z)\to R(x,y)$ $R(x,y)\wedge S(z,v)\wedge W(y,v)\to W(x,z)$ $\mathrm{\neg }Q(x,y)\to Q(y,x)$ $P(a,b)$ $\mathrm{\neg }Q(c,b)$ $S(d,e)$ $W(c,e)$

${\beta }_1:W(a,d)$ ${\beta }_2:W(d,e)\to W(a,d)$

2.

$\mathrm{\Gamma }:$ $P(a)\vee P(b)\vee P(c)$ $Q(x,y)\wedge R(y,d)\to \mathrm{\neg }P(x)$ $S(x,y)\to Q(x,y)\vee U(x,y)$ $S(a,e)$ $\mathrm{\neg }U(a,e)$ $R(e,d)$

${\beta }_1:P(a)\to P(b)$ ${\beta }_2:\mathrm{\neg }P(a)\wedge P(b)$ ${\beta }_3:Q(a,e)\wedge \mathrm{\neg }P(a)$ ${\beta }_4:P(b)\vee P(c)$ ${\beta }_5:\mathrm{\neg }(P(a)\vee P(b)\vee P(c))$ ${\beta }_6:\mathrm{\neg }P(b)\wedge \mathrm{\neg }P(c)\to P(a)$

3.

$\mathrm{\Gamma }:$ $Z(x,y)\to S(x,y)$ $L(x,y)\to Z(x,y)$ $Z(x,y)\wedge L(y,z)\to S(x,z)$ $\mathrm{\neg }S(x,y)\to \mathrm{\neg }L(x,y)$ $Z(x,y)\wedge L(y,x)\to L(x,y)$ $Z(x,y)\wedge L(x,z)\wedge L(z,y)\to 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 \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 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 \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.