Inteligenta ArtificialaInteligenta Artificiala

Universitatea Politehnica BucurestiAnul 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 Logica predicatelor Demonstrarea teoremelor

1. Reprezentarea cunostintelor

Logica – avantaje Puterea de reprezentare a diverselor logici

simbolice Limbaj formal: sintaxa, semantica Conceptualizare + exprimarea in limbaj Reguli de inferenta

2. Sistem formal

Un sistem formal este un cuadruplu O regula de inferenta de aritate n este o

corespondenta:

Fie multimea de premise

Un element xeste o consecinta a multimii de premise

R

R , y = y ,...,y x, x,y i = 1,nn1 n

Ri F F F ,

S =< A, , , >F A

= {y , ... , y1 n } E =0 A

E = E x| y E , y x}1 0 0n

n 1{

E = E x| y E , y x}2 1 1

n

n 1{

E ( i 0)i

Sistem formal - cont

Daca atunci elementele lui Ei se numesc teoreme

Fie o teorema; x se obtine prin aplicarea succesiva a r.i. asupra formulelor din Ei

Secventa de reguli - demonstratie . |S x |R x

  Daca atunci este deductibil din

|S x

E = ( = )0 A

x Ei

E =0 A x Ei

3. Logica propozitiilor

Limbaj formal

3.1 Sintaxa

Alfabet O 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

Interpretare Functia de evaluare a unei formule Proprietatile fbf

Valida/tautologie Realizabila Inconsistenta Formule echivalente

Semantica - cont

O 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

Idempotenta P P P P P P

Asociativitate (P Q) R P (Q R) (P Q) R P (Q R)

Comutativitate P Q Q P P Q Q P P Q Q P

Distributivitate P (Q R) (P Q) (P R) P (Q R) (P Q) (P R)

De Morgan ~ (P Q) ~ P ~ Q ~ (P Q) ~ P ~ Q

Eliminareaimplicatiei P Q ~ P Q

Eliminareaimplicatiei duble P Q (P Q) (Q P)

3.3 Obtinerea de noi cunostinte

Conceptualizare Reprezentare in limbaj Teoria modelului

KB || M Teoria demonstratiei

KB |S x M

3.4 Reguli de inferenta

Modus Ponens Substitutia Regula inlantuirii

Regula introducerii conjunctiei

Regula transpozitiei

P QQ R

P R

PQ

P Q

P Q

~ Q ~ P

PP Q

Q

Exemplu

Mihai are bani Masina este alba Masina este frumoasa Daca masina este alba sau masina este frumoasa si

Mihai are bani atunci Mihai pleaca in vacanta

B A F (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).

Predicat de aritate n Atom 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 LP - cont

Sintaxa pe scurt

Constante Variabile Functiia x f(x, a)

Termeni PredicateP

Formule atomiceP(a, x)

Formule atomice negate~P(a, x)

LiteraliCuantificatori Conectori logici

Formule bine formate

FNC, FND O formula bine formata este in forma normala conjunctiva, pe

scurt FNC, daca formula are forma

F1… 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)

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

D Dn D = (x ,...,x )|x D,...,x D}n

1 n 1 n{

P:D { , }n a f

4.2 Semantica LP

a

2

f (1) f (2)

2 1

A(2,1) A(2,2) B(1) B(2) C C D D( ) ( ) ( ) ( )1 2 1 2

a f a f a f f a

(( ) )a f a f

(( ) )f a f a

X=1

X=2

( x)(((A(a,x) B(f (x))) C(x)) D(x))

D={1,2}

Interpretare I

4.3 Proprietatile fbf in LP

Valida/tautologie Realizabila Inconsistenta Echivalente

F - consecinta logica a unei formule P F - 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.

Echivalenta cuantificatorilor

(Qx)F[x] G (Qx)(F[x] G) (Qx)F[x] G (Qx)(F[x] G)

~ (( x)F[x]) ( x)(~ F[x]) ~ (( x)F[x]) ( x)(~ F[x])

( x)F[x] ( x)H[x] ( x)(F[x] H[x]) ( x)F[x] ( x)H[x] ( x)(F[x] H[x])

(Q x)F[x] (Q x)H[x1 2

] (Q x)(Q z)(F[x] H[z]) (Q x)F[x] (Q x)H[x] (Q x)(Q z)(F[x] H[z])1 2 1 2 1 2

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

Substitutia Regula inlantuirii Transpozitia Eliminarea conjunctiei (AE) ·      Introducerea conjunctiei (AI) ·      Instantierea universala (UI) ·      Instantierea existentiala (EI) ·      Rezolutia

P(a)( x)(P(x) Q(x))

Q(a)

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 inferenta

1.  x y Horse(x) Dog(y) Faster(x,y)

2. y Greyhound(y) (z Rabbit(z) Faster(y,z))

3. y Greyhound(y) Dog(y)

4. xyz Faster(x,y) Faster(y,z) Faster(x,z)

5. Horse(Harry)

6. Rabbit(Ralph)

7. Greyhound(Greg) (z Rabbit(z) Faster(Greg,z)) 2, EI

8. Greyhound(Greg) 7, AE

9. z Rabbit(z) Faster(Greg,z)) 7, AE

10.  Rabbit(Ralph) Faster(Greg,Ralph) 9, UI

11. Faster(Greg,Ralph) 6,10, MP

12. Greyhound(Greg) Dog(Greg) 3, UI

13. Dog(Greg) 12, 8, MP

14. Horse(Harry) Dog(Greg) Faster(Harry, Greg) 1, UI

15. Horse(Harry) Dog(Greg) 5, 13, AI

16. Faster(Harry, Greg) 14, 15, MP

17. Faster(Harry, Greg) Faster(Greg, Ralph) Faster(Harry,Ralph)

4, UI

18. Faster(Harry, Greg) Faster(Greg, Ralph) 16, 11, AI

19. Faster(Harry,Ralph) 17, 19, MP

Exemplu de demonstrare - cont