Strona główna

Reprezentacja wiedzy I reprezentacja logiczna wstęp Logika – długie tradycje, „prawa myślenia”


Pobieranie 28.17 Kb.
Data19.06.2016
Rozmiar28.17 Kb.
Sztuczna Inteligencja
Reprezentacja wiedzy I Reprezentacja logiczna
Reprezentacja logiczna - wstęp

Logika – długie tradycje, „prawa myślenia” Boole’a.

Notacja logiczna pozwala wyrazić wiedzę.

Notacja logiczna pozwala prowadzić rozumowania.

Czasami jest naturalna, np. szukanie w Google:

Duch AND neural:

{p Î WebPages|contain(p,Duch) & contain(p,neural)}

= {p Î WebPages|contain(p,Duch))} Ç

{p Î WebPages|contain(p,neural)}
Rachunek zdań

Zdania mogą być prawdziwe lub nie.

Zdania stanowią zbiór, do którego należą również zdania otrzymane przez zastosowanie operatorów logicznych:

~ nieprawda


 koniunkcja, i
alternatywa
 implikacja

  • Do zdań można stosować kwantyfikatory:
     dla wszystkich
    istnieje

Rachunek zdań pozwala na wnioskowanie na kilka sposobów.

Logika predykatów

Logiczna reprezentacja stwierdzeń o obiektach.



  • Logika stwierdzeń mających za argumenty obiekty, np. ja, człowiek, kartka.

  • Predykaty mają argumenty i wartość logiczną.

  • Predykat jest-czerwony(x), większy-od(x,y), lżejszy-od(x,y)

  • Predykat isa, czyli „jest członkiem”.

  • Logika predykatów dopuszcza kwantyfikatory.


Reprezentacja logiczna

x, Ptak(x), czyli istnieje przynajmniej jedno takie x, że Ptak(x)=T.

„Każdy ptak ma skrzydła” można zapisać jako:

x, Ptak(x) => MaSkrzydła(x)


Wnioskowanie:
z prawdziwych faktów => nowe, prawdziwe fakty.

x. Wróbel(x) => Ptak(x) to

x .Wróbel (x) => MaSkrzydła (x)

Reguły wnioskowania nie zależą od konkretnej wiedzy.  

J

eśli P  Q, oraz Q  R to P  R
Tablice Logiczne

Tablice wartości logicznych:


zbadaj wszystkie wartości zmiennych logicznych.
Dla n zmiennych 2n kombinacji – zadanie NP-trudne.

Przydatne jedynie w prostych przypadkach.


Tablice semantyczne

  • Utwórz graf zamieniając znane fakty logiczne na gałęzie.

  • Dodaj zaprzeczenie konkluzji i sprawdź, czy we wszystkich gałęziach pojawią się sprzeczności.


Rozumowanie Logiczne -Dedukcja

  • Dedukcja:
    kojarz fakty, stosuj reguły oderwania:
    modus ponens, modus tolens,
    podstawienia and/or, eliminacji and/or, rezolucji.
    α  β  β  γ  α  γ
    Klauzule Horna – stwierdzenia logiczne, składające się z koniunkcji zdań:
    P1 P2 ..  Pn  Q

  • Możliwe jest wnioskowanie w czasie wielomianowym!


Logika Pierwszego Rzędu

Kwantyfikatory stosowane są tylko do obiektów, a nie do predykatów (funkcji, relacji).  

Funkcje(obiekt) lub Operatory:obiekt

mają argumenty, zwracają inne obiekty.



  • Równość obiektów w sensie predykatów:

X=Y jeśli P mamy P(X)=P(Y).

Literał: zdanie lub predykat, najmniejsza jednostka mająca sens.


Własności Logiki Pierwszego Rzędu

 FOL, First Order Logic



  • Nie można w niej dowieść fałszywego twierdzenia.

  • Wszystkie prawdziwe twierdzenia mają dowód.

  • Logika pierwszego rzędu i rachunek predykatów pierwszego rzędu mają ograniczone możliwości ekspresji.
    Np. w FOL nie można zapisać stwierdzenia:
    „Wszystkie predykaty mają jeden argument”.

  • Logiki wyższego rzędu (HOL, Higher-Order Logic) są trudne w implementacji.
    Równość predykatów: jeśli zawsze f(x)=g(x) to f=g.


Przykłady stwierdzeń FOL

  • Jeśli samochód należy do Karola, to jest on zielony.

posiada(Karol, auto-1) -> kolor(auto-1, zielony)

X auto(X)  posiada(Karol, X) -> kolor(X, zielony)



gra_na_inst(Mirek, gitara)  gra_na_inst(Mirek, skrzypce)

  • Niektórzy ludzie lubią żmije.

X (człowiek(X)  lubi(X, żmija))

X (człowiek(X)  Y (żmija(Y) -> lubi(X, Y)))

Często zapis nie jest jednoznaczny.
Procedura unifikacji


  • Kiedy dwa stwierdzenia są równoważne?

P  (Q  R) -> S = P  (Q  R) -> S ¹ P  (S  Q) -> R


  • Zmienne w predykatach komplikują zadanie

gra_na_inst(X, Y)  gra_na_inst(Mirek, skrzypce)
if X=Mirek, Y=skrzypce


  • Unifikacja: algorytm sprawdzania równoważności stwierdzeń rachunku zdań.

  • Czy zdania p(X,X) i p(Y,Z) są jednakowe?



Podstaw X/Y – czyli X za Y; Podstaw X/Z – czyli X za Z

Czasami konieczne jest podstawienie funkcji za zmienną człowiek(X) -> śmiertelny(X); człowiek(ojciec(Jana))/X

człowiek(ojciec(Jana)) -> śmiertelny (ojciec(Jana))
CNF, postać normalna

Literał: zdanie p lub zaprzeczenie  p

Klauzula: koniunkcja literałów.

Postać normalna (conjunctive normal form, CNF): koniunkcja klauzul.



  1. Eliminowany jest operator => stosując równoważność
    p => q oraz p  q;

  2. Rozwijane są wyrażenia z negacją
    np.  (p  q) przechodzi w  p   q

  3. Zmienne opisywane przez różne kwantyfikatory otrzymują różne nazwy.

  4. Wszystkie kwantyfikatory przesuwa się na początek zachowując porządek.

  5. Skolemizacja: pozwala na usunięcie wszystkich kwantyfikatorów , np. x P(x) zamieniany na P(A);
    x: Osoba(x) -> y Serce(y)  Ma(x,y)
    x: Osoba(x) -> Serce(F(x))  Ma(x, F(x))

  6. Pozostają tylko uniwersalne kwantyfikatory ";
    można je opuścić.

  7. Przekształcić na koniunkcję wyrażeń zawierających tylko alternatywy.

  8. Każdy człon koniunkcji stanowi osobną klauzule, wszystkie muszą być spełnione.

  9. Zmienne każdej z klauzuli otrzymują swoje odrębne nazwy.

Wynik: CNF, zbiór klauzul, które są alternatywą literałów.
Metoda rezolucji.

Metoda rezolucji: iteracyjny dowód przez sprzeczność; podstawowa metoda stosowana w Prologu.

Rezolucja: (P  Q)  (Q  R) => (P  R)

Zamieniamy negację  p (dowodzonego zdania) na klauzule:



  • dokonujemy rezolucji jednej pary klauzul (zamieniając ją na pojedynczą klauzulę);

  • wybieramy parę klauzul z aksjomatów i negacji p

Jeśli klauzula jest pusta to mamy sprzeczność, np. wyrażenie q   q daje pustą klauzulę

Chcemy znaleźć przypadek w którym nie da się utrzymać, że wszystkie klauzule są jednocześnie prawdziwe.


Przykład.

x,  c,  h, kolor(x, c)  masa(x, h) -> przedmiot(x).

Obiekt x jest przedmiotem jeśli ma kolor i masę. kolor(złoto, żółty), masa(złoto, ciężkie).

Forma CNF:

A1: x,  c,  h,  kolor(x, c) Ú  masa(x, h) Ú przedmiot(x)

A2: kolor(złoto, żółty); A3: masa(złoto, ciężkie).

Dowiedź: przedmiot(złoto)

Zakładamy  przedmiot(złoto) i szukamy sprzeczności.

Rezolucja A1, A2 daje x,  h,  masa(x, h) Ú przedmiot(x)

Rezolucja A3, z wynikiem daje przedmiot(złoto)

Sprzeczne z założeniem, qed.
Logika i zdrowy rozsądek


  • Logika klasyczna dostarcza teorii rozumowania opartej na „oczywistych” założeniach.

  • W realnej sytuacji wiedza jest niekompletna, niepewna, ciągle uzupełniana.



  • Logika niemonotoniczna: dodanie nowej wiedzy może falsyfikować istniejące konkluzje.

  • Stwierdzenia są prawdziwe, fałszywe lub nieokreślone.

  • Nowe fakty mogą być sprzeczne ze starymi.

  • Wnioski z braku faktów, założenia domyślne.

  • Potrzebna jest metoda rozstrzygania konfliktów jeśli wnioski są sprzeczne.


Przykład zastosowania: QA3

QA3, Question and Answer (Green 1969)

Program odpowiada na pytania, np.

Czy niebieska substancja może być siarczkiem żelaza?

Zapis faktów:

FeS jest siarczkiem, substancją ciemnoszarą, kruchą.

Predykat siarczek-żelaza(), zmienna FeS.

Własności FeS: prawdziwe jest

siarczek-żelaza(FeS)  substancja(FeS)  ciemnoszary(FeS)  kruchy(FeS)  ...

Pytanie sprowadza się do dowodu zaprzeczenia:

X. niebieski(X)  siarczek-żelaza(X)

Konieczny jest sprawny algorytm szukania.


Przykład zastosowania: STRIPS.

STRIPS (Fikes, Hart, Nillson, SRI 1972)

Mając robota w punkcie A i skrzynki w punktach B, C, D,
zbierz skrzynki razem.

Sytuacja opisana jest następująco:

AT(Robot,A)

AT(Box1,B)  AT(Box2,C)  AT(Box3,D)

Polecenie (cel) brzmi

 X. AT(BOX1,X) AT(BOX2,X) AT(BOX3,X)


Dowód konstruktywny <=> sekwencji czynności rozwiązujących zadanie. Stosowany jest rachunek predykatów pierwszego rzędu oraz analiza celów i środków.
Wady i zalety rep. logicznej

FOL (First Order Logic, Filman i Weyhrauch 1976)

Sprawdza interakcyjnie dowody w zakresie logiki pierwszego rzędu.

Istnieją nieliczne programy wychodzące poza FOL.



Zalety reprezentacji logicznej:

spójność - wszystkie fakty to stwierdzenia logiczne

zupełność - można wywnioskować wszystkie prawdziwe stwierdzenia dające się wyrazić w ramach FOL.
oddzielenie części epistemologicznej od dedukcyjnej.

Wady:

problemy z eksplozją kombinatoryczną, niewielka efektywność wnioskowania, niektóre formy wiedzy trudno jest wyrazić za pomocą reprezentacji logicznej.


Przykłady pytań

  • Co to jest rachunek zdań

  • Co to jest CNF

  • Co to jest metoda wnioskowania przez rezolucję

  • Czym różni się logika monotoniczna od niemonotonicznej





©snauka.pl 2016
wyślij wiadomość