curs 8 - prolog si logica predicatelor de ordinul i partea a ii-a

Curs 8PROLOG si Logica Predicatelor de Ordinul I

Partea a II-a

Programare logica

Formalizarea cunostintelor în forma clauzalaRecapitulare

Exercitiul 1

Sa se formalizeze proprietatile unui grup G în forma clauzala.

1 Daca x , y ∈ G atunci x · y ∈ G.

2 Daca x , y , z ∈ G atunci x · (y · z) = (x · y) · z.3 x · e = e · x = x pentru toti x ∈ G.

4 Pentru fiecare x ∈ G exista y ∈ G astfel încât x · y = y · x = e.

Programare logica

Formalizarea cunostintelor în forma clauzalaPasul 0: de la limbaj natural la logica predicatelor de ordinul I

Fie p(x , y , z) predicatul cu semnificatia x · y = z.1 Daca x , y ∈ G atunci x · y ∈ G.

(∀x)(∀y)(∃z)p(x , y , z).2 Daca x , y , z ∈ G atunci x · (y · z) = (x · y) · z.

(∀x)(∀y)(∀z)(∀u)(∀v)(p(x , y , u) ∧ p(y , z, v) ∧ p(u, z,w)→ p(x , v ,w)).

3 x · e = e · x = x pentru toti x ∈ G.(∀x)(p(x , e, x) ∧ p(e, x , x)).

4 Pentru fiecare x ∈ G exista y ∈ G astfel încât x · y = y · x = e.(∀x)(∃y)(p(x , y , e) ∧ p(y , x , e)).

Programare logica

Formalizarea cunostintelor în forma clauzalaDe la logica predicatelor de ordinul I la forma clauzala: pasii 1-3

1. Transformarea în forma prenex echivalenta.

(∀x)(∀y)(∃z)p(x , y , z).(∀x)(∀y)(∀z)(∀u)(∀v)(∀w)(p(x , y , u) ∧ p(y , z, v) ∧ p(u, z,w)→ p(x , v ,w)) ≡(∀x)(∀y)(∀z)(∀u)(∀v)(∀w)(¬(p(x , y , u) ∧ p(y , z, v) ∧ p(u, z,w)) ∨ p(x , v ,w)).

(∀x)(p(x , e, x) ∧ p(e, x , x)).

(∀x)(∃y)(p(x , y , e) ∧ p(y , x , e)).

2. Eliminarea cuantificatorilor existentiali (Skolemizare).Doar formulelele 1 si 4 au cuantificatori universali. Eliminarea lor produceformele Skolem:

(∀x)(∀y)(∃z)p(x , y , z) ≡ (∀x)(∀y)p(x , y , r(x , y)).(∀x)(∃y)(p(x , y , e) ∧ p(y , x , e)) ≡ (∀x)(p(x , i(x), e)) ∧ p(i(x), x , e)).

3. Calculul formelor normale conjunctive (CNF).

Formulele 1, 3 si 4 sunt în forma normala conjunctiva. Transformarea formulei 2:

(∀x)(∀y)(∀z)(∀u)(∀v)(∀w)(¬(p(x , y , u) ∧ p(y , z, v) ∧ p(u, z,w)) ∨ p(x , v ,w)) ≡(∀x)(∀y)(∀z)(∀u)(∀v)(∀w)(¬p(x , y , u) ∨ ¬p(y , z, v) ∨ ¬p(u, z,w) ∨ p(x , v ,w)︸︷︷︸

disjunctie de literali

).

Programare logica

Formalizarea cunostintelor în forma clauzalaDe la logica predicatelor de ordinul I la forma clauzala: pasul 4

4. Transformarea în conjunctie de forme clauzale

(∀x)(∀y)p(x , y , r(x , y)).(∀x)(∀y)(∀z)(∀u)(∀v)(∀w)(¬p(x , y , u)∨¬p(y , z, v)∨¬p(u, z,w))∨p(x , v ,w)).

(∀x)(p(x , e, x) ∧ p(e, x , x)) ≡ (∀x)p(x , e, x) ∧ (∀x)p(e, x , x).(∀x)(p(x , i(x), e)) ∧ p(i(x), x , e) ≡ (∀x)p(x , i(x), e)) ∧ (∀x)p(i(x), x , e).

⇒ 6 forme clauzale care au urmatoarele reprezentari simplificate:p(X ,Y , r(X ,Y )).¬(p(X ,Y ,U),¬p(Y ,Z ,V ),¬p(U,Z ,W ), p(X ,V ,W ).p(X , e,X).p(e,X ,X).p(X , i(X), e).p(i(X),X , e).

Toate cele 6 forme sunt clauze Horn⇒ pot fi descrise ca reguli si fapte în Prolog:p(X ,Y , r(X ,Y )). % faptp(X ,V ,W ):-p(X ,Y ,U), p(Y ,Z ,V ), p(U,Z ,W ), p(X ,V ,W ). % regulap(X , e,X). % faptp(e,X ,X). % faptp(X , i(X), e). % faptp(i(X),X , e). % fapt

Programare logica






Toate cele 6 forme sunt clauze Horn⇒ pot fi descrise ca reguli si fapte în Prolog:

p(X ,Y , r(X ,Y )). % faptp(X ,V ,W ):-p(X ,Y ,U), p(Y ,Z ,V ), p(U,Z ,W ), p(X ,V ,W ). % regulap(X , e,X). % faptp(e,X ,X). % faptp(X , i(X), e). % faptp(i(X),X , e). % fapt

Programare logica






Toate cele 6 forme sunt clauze Horn⇒ pot fi descrise ca reguli si fapte în Prolog:p(X ,Y , r(X ,Y )). % faptp(X ,V ,W ):-p(X ,Y ,U), p(Y ,Z ,V ), p(U,Z ,W ), p(X ,V ,W ). % regulap(X , e,X). % faptp(e,X ,X). % faptp(X , i(X), e). % faptp(i(X),X , e). % fapt

Programare logica

Formalizarea cunostintelor în forma clauzalaRecapitulare

Exercitiul 2

Sa se aduca formula

(∀x)(∀y)((∃z)(p(x , z) ∧ p(y , z))→ (∃z)q(x , y , z))

în forma clauzala.

(∀x)(∀y)((∃z)(p(x , z) ∧ p(y , z))→ (∃z)q(x , y , z))≡ (∀x)(∀y)(¬(∃z)(p(x , z) ∧ p(y , z)) ∨ (∃z)q(x , y , z)) % eliminare→≡ (∀x)(∀y)((∀z)(¬(p(x , z) ∧ p(y , z))) ∨ (∃z)q(x , y , z))≡ (∀x)(∀y)(∀u)(¬(p(x ,u) ∧ p(y ,u)) ∨ (∃z)q(x , y , z)) % redenumire≡ (∀x)(∀y)(∀u)(∃v)(¬(p(x ,u) ∧ p(y ,u)) ∨ q(x , y , v)) % redenumire≡ (∀x)(∀y)(∀u)(¬(p(x ,u) ∧ p(y ,u)) ∨ q(x , y , r(x , y ,u))) % skolemizare≡ (∀x)(∀y)(∀u)(¬p(x ,u) ∨ ¬p(y ,u) ∨ q(x , y , r(x , y ,u))︸︷︷︸

disjunctie de literali

).

Forma clauzala simplificata: ¬p(X ,U),¬p(Y ,U),q(X ,Y , r(X ,Y ,U)).

În PROLOG: q(X ,Y , r(X ,Y ,U)):-p(X ,U),p(Y ,U).

Programare logica

Principiul rezolutiei

A fost introdus în 1965 de Alan Robinson în demonstrareaautomata a teoremelorB Daca C si C′ sunt forme clauzale astfel încât

C ≡ L1, . . . ,Li−1, A, Li+1, . . . ,LmC′ ≡ M1, . . . ,Mj−1, ¬B, Mj+1, . . . ,Mn

si atomii A si B se pot unifica cu cel mai general unificatorθ = [X1 7→ t1, . . . ,Xr 7→ tr ]. (acest lucru implica Aθ = Bθ)

B atunci putem construi clauzaR ≡ M ′1, . . . ,M

′j−1,L

′1, . . . ,L

′i−1,L

′j+1, . . . ,L

′m,M ′j+1, . . . ,M

′n

unde L′u = Luθ si M ′v = Mvθ pentru toti indicii u, v .

R se numeste rezolvent al clauzelor C si C′.

OBSERVATIE: Daca C si C′ sunt clauze adevarate atunci sirezolventul lor este o clauza adevarata.

Programare logica

Principiul rezolutieiReprezentare schematica

C1,A,C2. C′1,¬B,C′2.clauza C clauza C′

θ = mgu(A,B)

Aθ = Bθ

C′1θ,C1θ,C2θ,C′2θ.

rezolvent al lui C si C′

Exemplu

str(X ,Z ),¬str(X ,Y ),¬str(Y ,Z ). ¬str(v ,Y 1),¬str(Y 1,g).

θ = [X 7→ v ,Y 1 7→ Z ]

¬str(v ,Y ),¬str(Y ,Z ),¬str(Y , g).

Programare logica

Interpretarea declarativa a programelor logice

Cautarea raspunsurilor la o întrebare ?-B1, . . . ,Bp. în raport cu unprogram logic P se face astfel:

Se presupune ca întrebarea este falsa, adica negatia ei esteadevarata. Negatia întrebarii este forma clauzalaR1 = ¬B1, . . . ,¬Bp.

Se cauta sa se deduca o contradictie cu principiul rezolutiei:

Daca R2 este un rezolvent între negatia întrebarii initiale (presupusaadevarata) si un variant al unei clauze sau fapte din program (care suntpresupuse adevarate) atunci R2 trebuie sa fie adevarat.We continua recursiv: se genereaza un rezolvent R3 din R2 si program, R4

din R3 si program, . . . , pâna când se obtine un rezolvent Rn+1 fara literali(rezolventul �). Conform principiului rezolutiei, toti Ri sunt adevarati.O forma clauzala este o disjunctie de literali⇒ poate fi adevarata doardaca unul din literali este adevarat.Rezolventul Rn+1 nu are nici un literal⇒ Rn+1 este fals⇒ contradictie⇒întrebarea initiala este adevarata.

Acest mod de interpretare a unei întrebari se numeste metoda respingerii rezolutive.

Programare logica

Principiul rezolutieiDerivatii, respingeri rezolutive si arbori de derivare

O derivatie a unei întrebari B este o secventa de întrebari

B1 = B,B2, . . . ,Bn,Bn+1, . . .

în care fiecare Bn+1 este negatia unui rezolvent calculat cusubstitutia θn între ¬Bn si un variant al unei clauze sau fapte.

O respingere rezolutiva a lui B este o derivatieB1 = B,B2, . . . ,Bn,Bn+1 = �.

Raspunsul calculat de aceasta derivatie pentru B estesubstitutia θ1θ2 . . . θn pentru variabilele din B.

Un arbore de derivare al unei întrebari B este un arbore curadacina B în care fiecare nod este o întrebare si

fiecare nod, cu exceptia lui �, are un atom selectat A (decinodul este de forma C,A,C′) iar fiii lui sunt toti rezolventiicare se pot obtine unificând A cu capul unei raguli sau faptedin program.

Programare logica

Semnificatia declarativa a programelor logice

Definitie

Spunem ca o întrebare ?− B1, . . . ,Bp este adevarata într-un program PROLOG dacap = 0 sau daca întrebarea poate fi satisfacuta sau derivata logic din program în felulurmator:

Putem selecta un atom Bi din întrebare

Putem selecta un variant A:-D1, . . . ,Dn. al unei reguli sau fapte din program stfelîncât A si B sa aibe un cel mai general unificator θ = [X1 7→ t1, . . . ,Xr 7→ tr ]

Gasirea termenilor t1, . . . , tr astfel încât Aθ = Biθ se numeste potrivire sauunificare.

Construim întrebarea noua B1θ, . . . ,Bi−1θ,D1θ, . . . ,Dnθ,Bi+1θ, . . . ,Bpθ.

Întrebarea nou construita este adevarata în programul PROLOG.

OBSERVATIE: O întrebare este adevarata într-un program PROLOG daca si numai dacaputem calcula o respingere rezolutiva a lui B:

B1 = B,B2, . . . ,Bn,Bn+1 = �

Programare logica

Metoda respingerii rezolutiveReprezentare schematica a interpretarii declarative

Interpretarea declarativa a unei întrebari ?-B1, . . . ,Bi−1︸︷︷︸D1

,Bi ,Bi+1, . . . ,Bp︸︷︷︸D2

.

Variantide

reguli si

fapte din

programderivatie

D1,Bi ,D2.

D1θ1,C1θ1,D2θ1 = E1,F ,E2.

G.

�.

A1:-C1.

A2:-C2.

...

An.

θ1 = mgu(A1, Bi )

θ2 = mgu(A2, F )

θn−1 = mgu(An−1, . . .)

θn = mgu(An−1,G)

întrebare initiala

întrebare finala

Rezolventii R2, . . . ,Rn,Rn+1 sunt negatiile întrebarilor succesive.

Fiecare Ri (i > 1) este un rezolvent dintre Ri−1 si un variant ¬Ci ∨ Ai alunei reguli sau fapte din program.

Raspunsul la întrebarea initiala se obtine compunând substitutiile calculate:θ1θ2 . . . θn.

Programare logica

Semnificatia declarativa a programelor PROLOGExemplu

Întrebarile adevarate pot fi recunoscute construind un arbore de derivare.

Program PROLOG: Arborele genealogic definit de program:

(1) parinte(vali,gelu).(2) parinte(ada,gelu).(3) parinte(ada, mia).(4) parinte(gelu,lina).(5) parinte(gelu,misu).(6) parinte(misu,roco).(7) str(X,Z):-parinte(X,Z).

(8) str(X,Z):-parinte(X,Y),str(Y,Z).

adavali

gelu mia

lina misu

roco

Întrebare: str(X,misu)

�

parinte(X,misu) parinte(X,Y1),str(Y1,misu)

str(gelu,misu). . . . . .. . .

. . .

(2), [X1=ada,Y1=gelu]

(7), [X1=X,Z1=misu]

(5), [X=gelu]

(8), [X1=X,Z1=misu]Arbore de derivare

pentru întrebarea

str(X,misu).

Programare logica

Arbori de derivareExemplul 1

Program PROLOG: Arbore de derivare infinit:

(1) parinte(vali,gelu).(2) parinte(ada,gelu).(3) parinte(ada, mia).(4) parinte(gelu,lina).(5) parinte(gelu,misu).(6) parinte(misu,roco).(7) str(X,Z):-str(X,Y),parinte(Y,Z).

(8) str(X,Z):-parinte(X,Z).

str(vali,gelu).

str(vali,Y1),parinte(Y1,gelu). parinte(vali,gelu).

�

str(vali,Y2),parinte(Y2,Y1),parinte(Y1,gelu).

...

(7)

(7)

(7)

(8)

(1)

Programare logica

Arbori de derivareExemplul 2

Program PROLOG: Arbore de derivare finit:



str(vali,gelu).

str(vali,Y1),parinte(Y1,gelu). parinte(vali,gelu).

�

str(vali,vali). str(vali,ada).

str(vali,Y2),parinte(Y2,vali). str(vali,Y2),parinte(Y2,ada).

parinte(vali,vali). parinte(vali,ada).

(7)

(1) (2)

(8)

(1)

(7)(8)

(7)(8)

OBSERVATIE: Faptul ca un arbore de derivare este finit sau nudepinde de selectia atomilor din întrebari.

Programare logica

Aplicatii ale principiului rezolutieiDemonstrarea automata a teoremelor

ExempluSa se demonstreze ca unghiurile interioare formate de diagonalaunui trapez sunt egale.

a

d

b

c

Definim

trapez(x , y , u, v) sa însemne ca xyuv este trapez cu colturile x în stânga sus, yîn dreapta sus, z în dreapta jos si v în stânga jos.

par(x , y , u, v) sa însemne ca segmentul xy este paralel cu segmentul uv .

eq(x , y , z, u, v ,w) sa însemne ca unghiul xyz este egal cu unghiul uvw .

Stim ca

(A1) (∀x)(∀y)(∀u)(∀v)(trapez(x , y , u, v)→ par(x , y , u, v)).

(A2) (∀x)(∀y)(∀u)(∀v)(par(x , y , u, v)→ eq(x , y , v , u, v , y)).

(A3) trapez(a, b, c, d).

si vrem sa demonstram ca eq(a, b, d , c, d , b).

Programare logica

Aplicatii ale principiului rezolutieiDemonstrarea automata a teoremelor

Exemplu (continuare)Baza de cunostinte este

par(X ,Y ,U,V ):-trapez(X ,Y ,U,V ).eq(X ,Y ,V ,U,V ,Y ):-par(X ,Y ,U,V ).trapez(a, b, c, d).

si vrem sa demonstram ca eq(a, b, d , c, d , b).

derivatie

eq(a, b, d , c, d , b).

par(a, b, c, d).

trapez(a, b, c, d).

�.

eq(X1, Y 1, V1,U1, V1, Y 1):-p(X1, Y 1,U1, V1).

par(X2, Y 2,U2, V2):-trapez(X2, Y 2,U2, V2).

trapez(a, b, c, d).

[X1 7→ a, Y1 7→ b, V1 7→ d,U1 7→ C, V1 7→ d ]

[X2 7→ a, Y2 7→ b,U2 7→ c, V2 7→ d ]

[]

Varianti de clauze din baza de cunostinte

Raspunsul la întrebarea ?-eq(a, b, d , c, d , b) este true deoarece a fost derivataîntrebarea �.

B Nu este afisata nici o substitutie deoarece întrebarea nu contine variabile.

Programare logica

Principiul Rezolutiei în PROLOG

PROLOG foloseste principiul rezolutiei în interpretareaprocedurala a programelor.

Singura diferenta dintre interpretarea declarativa si ceaprocedurala este strategia de selectie a atomilor dinîntrebare si strategia de selectie a regulilor si faptelor dinprogram.Strategia aleasa de PROLOG pentru implementarea principiuluirezolutiei se numeste strategie de intrare liniara.

Avantaj: implementare foarte eficienta.Dezavantaj: strategia nu este întotdeauna completa,

deoarece:Cautarea raspunsurilor se face parcurgândarborele de derivare în adâncime, de lastânga la dreapta.Daca arborele de derivare are o ramurainfinita, PROLOG nu ajunge sa gaseascaraspunsurile din dreapta ei.

Programare logica

Strategia de cautare liniaraExemplu de cautare incompleta

Program PROLOG: Arbore de derivare infinit:



stramos(vali,gelu).

stramos(vali,Y1),parinte(Y1,gelu). parinte(vali,gelu).

�

stramos(vali,Y2),parinte(Y2,Y1),parinte(Y1,gelu).

...

(7)

(7)

(7)

(8)

(1)

ramura infinita(se selecteaza mereu

atomul din stânga)

Raspunsul true la întrebarea ?-stramos(vali,gelu) nu va fiobtinut niciodata.

Programare logica

Quiz 1

1. Sa se exprime în forma clauzala cunostintele urmatoare:Unor pacienti le plac toti doctorii. Nici unui pacient nu-i placsarlatanii. Nici un doctor nu este sarlatan.

Folositi principiul rezolutiei pentru a demonstra ca dacaprimele doua afirmatii sunt adevarate atunci si a treiaafirmatie este adevarata.

2. Sa se aduca formulele urmatoare în forma clauzala:1 (¬p(a,b) ∧ p(x))→ r(a, x).2 ¬(p ∨ ¬q) ∧ (s(a)→ r(b)).3 p → (q ↔ (r ∧ p)).

3. Sa se transforme formulele urmatoare în forme clauzale:1 (∀x)(p(x)→ (∃y)q(x , y)).2 (∃x)(¬((∃y)p(x , y))→ ((∃z)q(z)→ r(x))).3 (∀x)(∀y)((∃z)p(x , y , z) ∧ ((∃u)q(x ,u)→ (∃x)q(y , x))).

Programare logica

Quiz 2

4. Se presupun adevarate urmatoarele afirmatii:Sfântul Petru este iubit de oricine care iubeste pe cineva.Nu exista persoana care sa nu iubeasca pe nimeni.

Folositi principiul rezolutiei pentru a demonstra ca SfântulPetru este iubit de toata lumea.

5. Se considera programul Prologparinte(vali,gelu).parinte(ada,gelu).parinte(ada, mia).parinte(gelu,lina).parinte(gelu,misu).parinte(misu,roco).str(X,Z):-str(X,Y),parinte(Y,Z).str(X,Z):-parinte(X,Z).

Sa se construiasca o derivatie care dovedeste faptul ca[X=ada,Y=lina] este un raspuns la întrebarea?-stramos(X,Y).

Programare logica

Referinte bibliografice

B Capitolele 3-4 dinChin-Liang Chang, Richard Char-Tung Lee. Symbolic Logicand Mechanical Theorem Proving. Computer ScienceClassics. Academic Press, 1973.

B A.M. Florea, B. Dorohonceanu, C. Frâncu. Programare înProlog pentru Inteligenta Artificiala. Capitolul 3: LimbajulProlog si logica cu predicate de ordinul I. Universitatea„Politehnica” Bucuresti 1997.

Programare logica

curs 8 - prolog si logica predicatelor de ordinul i partea a ii-a

Documents