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. $\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)$ Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle L(x,y) \rightarrow Z(x,y)} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle Z(x,y) \land L(y,z) \rightarrow S(x,z)} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg S(x,y) \rightarrow \neg L(x,y)} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle Z(x,y) \land L(y,x) \rightarrow L(x,y)} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle Z(x,y) \land L(x,z) \land L(z,y) \rightarrow L(x,y)} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle L(x,f(x))} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle L(a,b)} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle L(f(a),c)} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle L(c,d)} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle Z(a,c)} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle Z(a,d)} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle Z(b,d)}

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \beta_1:\;\;L(b,c)} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \beta_2:\;\;L(b,d)} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \beta_3:\;\;L(c,f(a))}

Zadanie 4

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

1. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \frac{\alpha\rightarrow\beta, \; \beta\rightarrow\gamma}{\alpha\rightarrow\gamma}}
2. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \frac{\alpha\rightarrow\beta, \; \beta\rightarrow\gamma, \; \alpha}{\gamma}}
3. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \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