Home >Documents >Inteligenta Artificiala

Inteligenta Artificiala

Date post:31-Jan-2016
Category:
View:31 times
Download:2 times
Share this document with a friend
Description:
Inteligenta Artificiala. Universitatea Politehnica Bucuresti Anul universitar 2005-2006 Adina Magda Florea http://turing.cs.pub.ro/ia_06. Curs nr. 4. Reprezentarea cunostintelor in IA Modelul logicii simbolice Reprezentarea logicii simbolice Sistem formal Logica propozitiilor - PowerPoint PPT Presentation
Transcript:
  • Inteligenta ArtificialaUniversitatea Politehnica Bucuresti Anul universitar 2005-2006

    Adina Magda Floreahttp://turing.cs.pub.ro/ia_06

  • Curs nr. 4Reprezentarea cunostintelor in IAModelul logicii simboliceReprezentarea logicii simboliceSistem formalLogica propozitiilorLogica predicatelorDemonstrarea teoremelor

  • 1. Reprezentarea cunostintelorLogica avantajePuterea de reprezentare a diverselor logici simboliceLimbaj formal: sintaxa, semanticaConceptualizare + exprimarea in limbajReguli de inferenta

  • 2. Sistem formalUn sistem formal este un cuadrupluO regula de inferenta de aritate n este o corespondenta:

    Fie multimea de premise

    Un element xeste o consecinta a multimii de premise

  • Sistem formal - contDaca atunci elementele lui Ei se numesc teoreme

    Fie o teorema; x se obtine prin aplicarea succesiva a r.i. asupra formulelor din EiSecventa de reguli - demonstratie . |S x |R xDaca atuncieste deductibil din |S x

  • 3. Logica propozitiilorLimbaj formal3.1 SintaxaAlfabetO formula bine formata in calculul propozitional se defineste recursiv astfel:(1)Un atom este o formula bine formata(2)Daca P este formula bine formata, atunci ~P este formula bine formata.(3)Daca P si Q sint formule bine formate atunci PQ, PQ, PQ si PQ sint formule bine formate.(4)Multimea formulelor bine formate este generata prin aplicarea repetata a regulilor (1)..(3) de un numar finit de ori.

  • 3.2 Semantica InterpretareFunctia de evaluare a unei formule Proprietatile fbfValida/tautologieRealizabilaInconsistentaFormule echivalente

  • Semantica - contO formula F este o consecinta logica a unei formule P daca F are valoarea adevarat in toate interpretarile in care P are valoarea adevarat.O formula F este consecinta logica a unei multimi de formule P1,Pn daca formula F este adevarata in toate interpretarile in care P1,Pn sunt adevarate.Consecinta logica se noteaza P1,Pn F.Teorema.Formula F este consecinta logica a unei multimi de formule P1,Pn daca formula P1,Pn F este valida.Teorema. Formula F este consecinta logica a unei multimi de formule P1,Pn daca formula P1 Pn ~F este inconsistenta.

  • Legi de echivalenta

  • 3.3 Obtinerea de noi cunostinteConceptualizareReprezentare in limbajTeoria modeluluiKB || MTeoria demonstratieiKB |S x M

  • 3.4 Reguli de inferentaModus PonensSubstitutiaRegula inlantuirii

    Regula introducerii conjunctiei

    Regula transpozitiei

  • ExempluMihai are baniMasina este albaMasina este frumoasaDaca masina este alba sau masina este frumoasa si Mihai are bani atunci Mihai pleaca in vacantaBAF(A F) B C

  • 4. Logica cu predicate de ordinul I 4.1 SintaxaFie D un domeniu de valori. Un termen se defineste astfel:(1)O constanta este un termen cu valoare fixa apartinand domeniului D.(2)O variabila este un termen ce poate primi valori diferite din domeniul D.(3)Daca f este o functie de n argumente si t1,..tn sint termeni, atunci f(t1,..tn) este termen.(4)Toti termenii sunt generati prin aplicarea regulilor (1)(3).

  • Sintaxa LP - contPredicat de aritate nAtom sau formula atomica.LiteralO formula bine formata in logica cu predicate de ordinul I se defineste astfel:(1)Un atom este o formula bine formata(2)Daca P[x] este fbf, atunci ~P[x] este fbf.(3)Daca P[x] si Q [x] sunt fbf atunci P[x]Q[x],P[x] Q[x], P[x]Q[x] si P[x]Q[x] sunt fbf.(4)Daca P[x] este fbf atunci x P[x], x P[x] sunt fbf.(5)Multimea formulelor bine formate este generata prin aplicarea repetata a regulilor (1)..(4) de un numar finit de ori.

  • Sintaxa pe scurt

  • FNC, FND O formula bine formata este in forma normala conjunctiva, pe scurt FNC, daca formula are formaF1 Fn,unde este Fi , i=1,n sunt formule formate dintr-o disjunctie de literali (Li1 Lim).O formula bine formata este in forma normala disjunctiva, pe scurt FND, daca formula are forma , F1 Fn,unde Fi , i=1,n sunt formule formate dintr-o conjunctie de literali (Li1 Lim)

  • 4.2 Semantica LP Interpretarea unei formule F in logica cu predicate de ordinul I consta in fixarea unui domeniu de valori nevid D si a unei asignari de valori pentru fiecare constanta, functie si predicat ce apar in F astfel:(1)Fiecarei constante i se asociaza un element din D.(2)Fiecarei functii f, de aritate n, i se asociaza o corespondenta , unde

    (3)Fiecarui predicat de aritate n, i se asociaza o corespondenta

  • X=1

    X=2D={1,2} Interpretare I

  • 4.3 Proprietatile fbf in LPValida/tautologieRealizabilaInconsistentaEchivalenteF - consecinta logica a unei formule PF - consecinta logica a unei multimi de formule P1,Pn Teorema.Formula F este consecinta logica a unei multimi de formule P1,Pn daca formula P1,Pn F este valida.Teorema. Formula F este consecinta logica a unei multimi de formule P1,Pn daca formula P1 Pn ~F este inconsistenta.

  • Exemple Toate merele sunt rosii Toate obiectele sunt mere rosii Exista un mar rosu Toate pachetele din camera 27 sunt mai mici decat orice pachet din camera 28Toate ciupercile purpurii sunt otravitoarex (Purpuriu(x) Ciuperca(x)) Otravitor(x)x Purpuriu(x) (Ciuperca(x) Otravitor(x))x Ciuperca (x) (Purpuriu (x) Otravitor(x))(x)(y) iubeste(x,y)(y)(x) iubeste(x,y)

  • 4.4. Reguli de inferenta in LP Modus Ponens

    SubstitutiaRegula inlantuiriiTranspozitiaEliminarea conjunctiei (AE)Introducerea conjunctiei (AI)Instantierea universala (UI)Instantierea existentiala (EI)Rezolutia

  • Exemplu Horses are faster than dogs and there is a greyhound that is faster than every rabbit. We know that Harry is a horse and that Ralph is a rabbit. Derive that Harry is faster than Ralph.Horse(x) Greyhound(y) Dog(y) Rabbit(z) Faster(y,z)Faster(Harry, Ralph)?

    y Greyhound(y) Dog(y)x y z Faster(x,y) Faster(y,z) Faster(x,z) x y Horse(x) Dog(y) Faster(x,y)y Greyhound(y) (z Rabbit(z) Faster(y,z))Horse(Harry)Rabbit(Ralph)

  • Exemplu de demonstrare Teorema: Faster(Harry, Ralph) ?Demonstrare folosind reguli de inferentax y Horse(x) Dog(y) Faster(x,y)y Greyhound(y) (z Rabbit(z) Faster(y,z))y Greyhound(y) Dog(y)xyz Faster(x,y) Faster(y,z) Faster(x,z)Horse(Harry)Rabbit(Ralph)Greyhound(Greg) (z Rabbit(z) Faster(Greg,z))2, EIGreyhound(Greg)7, AEz Rabbit(z) Faster(Greg,z))7, AE

  • Exemplu de demonstrare - contRabbit(Ralph) Faster(Greg,Ralph)9, UIFaster(Greg,Ralph)6,10, MPGreyhound(Greg) Dog(Greg)3, UIDog(Greg)12, 8, MPHorse(Harry) Dog(Greg) Faster(Harry, Greg)1, UIHorse(Harry) Dog(Greg)5, 13, AIFaster(Harry, Greg)14, 15, MPFaster(Harry, Greg) Faster(Greg, Ralph) Faster(Harry,Ralph)4, UIFaster(Harry, Greg) Faster(Greg, Ralph)16, 11, AIFaster(Harry,Ralph)17, 19, MP

Embed Size (px)
Recommended