Sztuczna inteligencja/SI Ćwiczenia 2: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
następna edycja →
WizualnieWikikod
Jarabas (dyskusja | edycje)
364 edycje
Początkowa zawartość
 
Jarabas (dyskusja | edycje)
364 edycje
Zmiana nazwy
Linia 29: Linia 29:


== Zadanie 5 ==
== Zadanie 5 ==
Sprowadzić następujące formuły do postaci '''[[../SI Moduł 2#Koniunkcyjna postać normalna|CNF]]''':
Sprowadzić następujące formuły do postaci '''[[../SI Moduł 2 - Od logiki do wnioskowania#Koniunkcyjna postać normalna|CNF]]''':
# <math>(P(x,y)\rightarrow(Q(y,z)\land\neg R(x,z)))\lor Q(x,y,z) </math>
# <math>(P(x,y)\rightarrow(Q(y,z)\land\neg R(x,z)))\lor Q(x,y,z) </math>
# <math>(P(x,y)\land Q(y,z)\leftrightarrow(\neg R(x,y)\lor S(y,z)) </math>
# <math>(P(x,y)\land Q(y,z)\leftrightarrow(\neg R(x,y)\lor S(y,z)) </math>


== Zadanie 6 ==
== Zadanie 6 ==
Sprowadzić następujące formuły do [[../SI Moduł 2#Postać standardowa Skolema|postaci standardowej Skolema]]:
Sprowadzić następujące formuły do [[../SI Moduł 2 - Od logiki do wnioskowania#Postać standardowa Skolema|postaci standardowej Skolema]]:
# <math> ((\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) </math>
# <math> ((\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) </math>
# <math> ((P(x,y) \land Q(y,z)) \leftrightarrow (\neg R(x,y) \lor S(y,z))</math>
# <math> ((P(x,y) \land Q(y,z)) \leftrightarrow (\neg R(x,y) \lor S(y,z))</math>


== Zadanie 7 ==
== Zadanie 7 ==
Dokonać [[../SI Moduł 2#Unifikacja|unifikacji]] następujących par formuł:
Dokonać [[../SI Moduł 2 - Od logiki do wnioskowania#Unifikacja|unifikacji]] następujących par formuł:
# <math> P(a, f(g(x))) \land Q(g(y), b) \rightarrow R(x,c)</math><br><math>P(y, f(v)) \land Q(z,b) \rightarrow R(g(z),z) </math>
# <math> P(a, f(g(x))) \land Q(g(y), b) \rightarrow R(x,c)</math><br><math>P(y, f(v)) \land Q(z,b) \rightarrow R(g(z),z) </math>
# <math> \neg P(z,a,f(y)) \land (Q(y,b) \rightarrow R(c, g(z))) \lor S(f(a),g(b),z)</math><br><math> \neg P(b,v,f(a)) \land (Q(z,x) \rightarrow R(w, g(a))) \lor S(f(z),g(x),y) </math>
# <math> \neg P(z,a,f(y)) \land (Q(y,b) \rightarrow R(c, g(z))) \lor S(f(a),g(b),z)</math><br><math> \neg P(b,v,f(a)) \land (Q(z,x) \rightarrow R(w, g(a))) \lor S(f(z),g(x),y) </math>


== Zadanie 8 ==
== Zadanie 8 ==
Zweryfikować przedstawiony niżej przebieg wnioskowania prowadzonego przez człowieka zapisując [[../SI Moduł 2#Baza wiedzy jako zbiór klauzul|bazę wiedzy]] w postaci formuł logiki predykatów i sprawdzając poprawność kroków dowodu.
Zweryfikować przedstawiony niżej przebieg wnioskowania prowadzonego przez człowieka zapisując [[../SI Moduł 2 - Od logiki do wnioskowania#Baza wiedzy jako zbiór klauzul|bazę wiedzy]] w postaci formuł logiki predykatów i sprawdzając poprawność kroków dowodu.
# Wszystkie liczby podzielne przez 2 są parzyste.<br>Dowolna liczba o 1 większa od liczby parzystej nie jest parzysta.<br>Żadna liczba przysta nie jest podzielna przez 3.<br>Niektóre liczby nieparzyste są podzielne przez 3.<br>Z powyższego wynika, że każda liczba podzielna przez 3 jest o 1 większa od pewnej liczby podzielnej przez 2.<br>
# Wszystkie liczby podzielne przez 2 są parzyste.<br>Dowolna liczba o 1 większa od liczby parzystej nie jest parzysta.<br>Żadna liczba przysta nie jest podzielna przez 3.<br>Niektóre liczby nieparzyste są podzielne przez 3.<br>Z powyższego wynika, że każda liczba podzielna przez 3 jest o 1 większa od pewnej liczby podzielnej przez 2.<br>
# Nie wszystkie trójki punktów na płaszczyźnie są współliniowe.<br>Jeżeli trzy punkty na płaszczyźnie nie są współliniowe, to są wierzchołkami pewnego trójkąta.<br>Jeśli z czterech punktów żadne trzy nie są współliniowe, to są one wierzchołkami pewnego czworokąta.<br>Z powyższego wynika, że:
# Nie wszystkie trójki punktów na płaszczyźnie są współliniowe.<br>Jeżeli trzy punkty na płaszczyźnie nie są współliniowe, to są wierzchołkami pewnego trójkąta.<br>Jeśli z czterech punktów żadne trzy nie są współliniowe, to są one wierzchołkami pewnego czworokąta.<br>Z powyższego wynika, że:
Linia 52: Linia 52:


== Zadanie 9 ==
== Zadanie 9 ==
Czy system wnioskowania z dwoma aksjomatami <math>\alpha\lor\beta \,</math> oraz <math>\alpha\rightarrow(\beta\rightarrow\alpha) \,</math> i regułą wnioskowania ''[[../SI Moduł 2#eq_modusponens|modus ponens]]'' jest pełny?
Czy system wnioskowania z dwoma aksjomatami <math>\alpha\lor\beta \,</math> oraz <math>\alpha\rightarrow(\beta\rightarrow\alpha) \,</math> i regułą wnioskowania ''[[../SI Moduł 2 - Od logiki do wnioskowania#eq_modusponens|modus ponens]]'' jest pełny?


== Zadanie 10 ==
== Zadanie 10 ==
Linia 61: Linia 61:


== Zadanie 12 ==
== Zadanie 12 ==
Zaproponować odpowiedniki reguł ''[[../SI Moduł 2#eq_modusponens|modus ponens]]'' i ''[[../SI Moduł 2#eq_modustollens|modus tollens]]'' dla formuł w postaci '''[[../SI Moduł 2#Koniunkcyjna postać normalna|CNF]]'''.
Zaproponować odpowiedniki reguł ''[[../SI Moduł 2 - Od logiki do wnioskowania#eq_modusponens|modus ponens]]'' i ''[[../SI Moduł 2 - Od logiki do wnioskowania#eq_modustollens|modus tollens]]'' dla formuł w postaci '''[[../SI Moduł 2 - Od logiki do wnioskowania#Koniunkcyjna postać normalna|CNF]]'''.

Wersja z 16:34, 24 lip 2006

Zadanie 1

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

  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. ¬Q(a,f(f(a)))
  2. Q(g(g(c)),c)
  3. ¬R(a,f(b))

Zadanie 3

Sprawdzić, czy z bazy wiedzy Γ można wyprowadzić formuły βi dla poniższych Γ i β. 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. α→β,β→γα→γ
  2. α→β,β→γ,αγ
  3. α∨β,α∨¬βα
  4. α→β¬β→¬α
  5. α→β¬α→¬β
  6. α→(β→γ)β→(α→γ)

Zadanie 5

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

  1. (P(x,y)→(Q(y,z)∧¬R(x,z)))∨Q(x,y,z)
  2. (P(x,y)∧Q(y,z)↔(¬R(x,y)∨S(y,z))

Zadanie 6

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

  1. ((∀x)(∀y)P(x,y)→((∃z)(∀y)(Q(y,z)∧¬R(x,z)))∨Q(x,y,z)
  2. ((P(x,y)∧Q(y,z))↔(¬R(x,y)∨S(y,z))

Zadanie 7

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

  1. P(a,f(g(x)))∧Q(g(y),b)→R(x,c)
    P(y,f(v))∧Q(z,b)→R(g(z),z)
  2. ¬P(z,a,f(y))∧(Q(y,b)→R(c,g(z)))∨S(f(a),g(b),z)
    ¬P(b,v,f(a))∧(Q(z,x)→R(w,g(a)))∨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 α∨β oraz α→(β→α) 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.

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Sztuczna_inteligencja/SI_Ćwiczenia_2&oldid=6013”