Partea a ii-a Reprezentarea cunostintelor Capitolul 3 Modelul logicii simbolice

3.2 Logica cu predicate de ordinul I

Modelul de reprezentare a cunostintelor in programele de inteligenta artificiala trebuie sa posede un grad mare de flexibilitate pentru a putea reprezenta adecvat domeniul discursului. Logica propozitionala nu are aceasta proprietate deoarece nu permite exprimarea proprietatilor obiectelor si a relatiilor existente intre obiecte, si nici generalizarea enunturilor la clase de obiecte cu caracteristici similare.

Logica cu predicate de ordinul I a fost dezvoltata tocmai pentru a da posibilitatea exprimarii rationamentelor despre obiecte complexe sau clase de obiecte si despre relatiile existente intre ele. Aceasta generalizare se face pe baza introducerii predicatelor in locul propozitiilor, a utilizarii functiilor, a variabilelor si a cuantificatorilor de variabile. Aceste concepte sint riguros definite in continuare.

3.2.1 Sintaxa logicii cu predicate de ordinul I

Alfabetul logicii cu predicate de ordinul I contine simboluri pentru reprezentarea constantelor, notate prin conventie cu litere mici de la inceputul alfabetului , variabilelor, notate prin conventie cu litere mici de la sfirsitul alfabetului , functiilor, notate cu , predicatelor, notate cu , a conectorilor si a cuantificatorilor logici. Conectorii logici folositi in logica cu predicate de ordinul I sint: si , iar cuantificatorii sint cuantificatorul existential () si cuantificatorul universal ().

In cazul logicii cu predicate de ordinul I, predicatele sint functii logice de mai multe argumente, argumentele predicatelor numindu-se termeni.

Definitie. Fie D un domeniu de valori. Un termen se defineste astfel:

(1) O constanta este un termen cu valoare fixa apartinind 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 sint termeni, atunci este termen.

(4) Toti termenii sint generati prin aplicarea regulilor (1)(3).

Definitie. Se numeste predicat de aritate n o functie P de n argumente cu valori adevarat sau fals, . Un predicat de aritate 0 este o propozitie, numita si predicat constant.

Definitie. Daca P este un predicat de aritate n si sint termeni, atunci se numeste atom sau formula atomica. Nici o alta expresie nu poate fi atom.

Definitie. Se numeste literal un atom sau un atom negat.

Definitie. O formula bine formata in logica cu predicate de ordinul I se defineste astfel:

(1) Un atom este o formula bine formata.

(2) Daca P este o formula bine formata atunci: sint formule bine formate.

(3) Daca P si Q sint formule bine formate atunci: sint formule bine formate.

(4) Orice formula bine formata este generata prin aplicarea de un numar finit de ori a regulilor (1)(3).

O reprezentare intuitiva a modului de construire a cuvintelor, deci a formelor bine formate in limbajul logicii cu predicate de ordinul I, este prezentata in Figura 3.3. In continuare se vor omite parantezele din formule ori de cite ori aceasta nu creeaza ambiguitate. De asemenea, in anumite conditii, se va folosi x si y in loc de si .

Figura 3.3 Constructia formulelor bine formate in logica cu predicate de ordinul I

Exemple:

1. este o formula bine formata. , si sint literali, in acest caz literali pozitivi deci nenegati. x, y, z sint variabile.

2. este o formula bine formata. x, y si z sint variabile, f(x) functie, toate fiind considerate termeni. este un literal.

3. este o formula bine formata. si sint literali, primul pozitiv si cel de al doilea negativ.

4. nu este o formula bine formata deoarece cuantificatorii nu pot fi aplicati predicatelor. Acest lucru este posibil numai in logicile de ordin superior (logici de ordinul II).

5. nu este o formula bine formata deoarece negatia nu poate fi aplicata unei constante si, in general, nici unui termen.

6. nu este o formula bine formata deoarece argumentele predicatelor nu pot fi predicate.

Definitie. O formula bine formata este in forma normala conjunctiva, pe scurt FNC, daca formula are forma , unde este o formula formata dintr-o disjunctie de literali.

Definitie. O formula bine formata este in forma normala disjunctiva, pe scurt FND, daca formula are forma , unde este o formula formata dintr-o conjunctie de literali.

De exemplu, este o formula in forma normal conjunctiva, iar este o formula in forma normal disjunctiva.

3.2.2 Semantica logicii cu predicate de ordinul I

Similar logicii propozitiilor, semantica unei formule bine formate in logica cu predicate de ordinul I se poate stabili pe baza domeniului de interpretare al formulei. Domeniul de interpretare este multimea tuturor obiectelor din care se selecteaza constantele, variabilele si care stabileste domeniul de definitie si domeniul de valori ale functiilor din formule. Daca nu este exprimat explicit, domeniul de interpretare se deduce din context, putind fi si infinit. Odata stabilit domeniul de interpretare, se poate specifica interpretarea unei formule bine formate, deci se poate afla valoarea ei de adevar in acea interpretare.

Definitie. 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 .

Exemplu. Fie urmatoarea formula bine formata cu domeniul de interpretare D={1,2} si urmatoarea interpretare I:

Pentru a stabili valoarea de adevar a formulei se considera:

fals

adevarat

In consecinta, deoarece formula nu este adevarata pentru orice x din domeniul de interpretare D, expresia are valoarea de adevar fals.

Odata stabilite sintaxa si semantica logicii cu predicate de ordinul I, aceasta poate fi utilizata pentru a reprezenta cunostinte. In continuare se dau exemple de transformare a unor enunturi din limbaj natural in logica cu predicate de ordinul I.

Fie urmatoarele patru enunturi, dintre care primele trei sint axiome si cel de-al patrulea este teorema de demonstrat, sau concluzia.

(1) Oricine poate citi este literat.

(2) Delfinii nu sint literati.

(3) Anumiti delfini sint inteligenti.

(4) Exista inteligenti care nu pot citi.

Exprimind cele patru propozitii in logica cu predicate de ordinul I se obtine:

(A1)

(A2)

(A3)

(A4)

unde cu Citeste(x) s-a notat asertiunea "x poate citi", cu Delfin(x) "x este delfin", cu Literat(x) "x este literat" si cu Inteligent(x) "x este inteligent". Domeniul de interpretare al acestor formule este considerat implicit multimea tuturor fiintelor.

Fie axiomele de baza ale numerelor naturale:

(1) Pentru fiecare numar natural exista un unic succesor imediat.

(2) Nu exista nici un numar natural pentru care 0 este succesorul imediat.

(3) Pentru orice numar natural diferit de zero, exista un unic predecesor imediat.

Utilizind functia s(x) pentru a desemna succesorul imediat al lui x, functia p(x) pentru predecesorul imediat al lui x si predicatul pentru a exprima asertiunea "x este egal cu y", se obtine urmatoarea exprimare a axiomelor numerelor naturale in logica cu predicate de ordinul I.

(A1)

(A2)

(A3)

Domeniul de interpretare al acestor formule este evident multimea numerelor naturale, iar functiile s(x) si p(x) sint definite in consecinta.

Intr-o formula variabilele pot fi variabile libere sau legate. O variabila este legata intr-o formula daca exista un cuantificator ce o refera. In caz contrar, variabila este libera. O formula care contine variabile libere nu poate fi evaluata. De exemplu, formula nu poate fi evaluata deoarece nu se cunoaste cuantificarea lui y si nici cea a lui z. Variabila x este legata, iar variabilele y si z sint libere.

3.2.3 Proprietatile formulelor bine formate

Proprietatile formulelor bine formate in logica cu predicate de ordinul I sint aceleasi ca si in logica propozitiilor: validitate, inconsistenta, realizabilitate, echivalenta formulelor, consecinta logica. Definitiile sint similare dar, de aceasta data, trebuie sa se considere interpretarile pentru toate domeniile de interpretare posibile ale formulelor. De exemplu, formula:

din sectiunea anterioara nu este o tautologie, deci nu este valida, deoarece exista cel putin o interpretare pentru care ea este falsa. Formula este inconsistenta sau contradictie deoarece nu exista nici o interpretare pentru care aceasta formula sa fie adevarata. Formula este insa valida, deoarece ea este adevarata indiferent de interpretare.

Fie urmatoarele doua formule:

(A1) Bun(roco)

(A2)

Se poate arata ca formula , unde roco este o constanta, este o consecinta logica a formulelor (A1) si (A2). Sa presupunem ca atit (A1) cit si (A2) sint adevarate intr-o interpretare I. Atunci formula este adevarata deoarece (A2) specifica pentru "orice x" din domeniu. Dar se stie ca Bun(roco) este adevarata in interpretarea I pe baza lui (A1), deci rezulta ca este adevarata deoarece adevarat nu poate implica fals. S-a demonstrat ca pentru orice interpretare in care (A1) si (A2) sint formule adevarate si formula este adevarata, deci este o consecinta logica a formulelor (A1) si (A2).

Echivalenta formulelor poate fi stabilita utilizind legile de echivalenta din logica cu predicate de ordinul I prezentate in Figura 3.4. In figura s-au notat cu Q si cuantificatorii universal si existential.

Figura 3.4 Legi de echivalenta a formulelor in logica cu predicate de ordinul I



Figura 3.4 (continuare) Legi de echivalenta a formulelor in logica cu predicate de ordinul I

In toate exemplele mentionate mai sus s-au folosit metode semantice pentru stabilirea caracterului formulelor. In sectiunea urmatoare se vor discuta metode semantice pentru realizarea deductiilor si stabilirea caracterului unei multimi de formule. Dupa cum se observa din exemplele de mai sus, inspectarea tuturor interpretarilor unei formule peste toate domeniile posibile poate fi deosebit de dificila, daca nu imposibila in anumite cazuri, deci o astfel de abordare este greu de automatizat.

3.2.4 Reguli de inferenta in logica cu predicate de ordinul I

Regulile de inferenta sintactice din logica propozitionala prezentate in Sectiunea 3.1.5, Modus Ponens, substitutia, inlantuirea, conjunctia si transpozitia, pot fi generalizate in cazul logicii cu predicate de ordinul I. De exemplu, regula Modus Ponens are urmatoarea forma:

Modus Ponens

Se observa ca s-a facut substitutia lui a cu x, ceea ce a fost posibil deoarece P(x)Q(x) este adevarata pentru orice interpretare.

Regula substitutiei poate avea forme mai sofisticate in cazul logicii cu predicate de ordinul I. Aceste forme vor fi discutate in sectiunea urmatoare. Tot in aceeasi sectiune se prezinta in detaliu si rezolutia, regula de inferenta sintactica importanta.

Regulile de inferenta prezentate sint reguli deductive, deci valide. Ele pastreaza caracterul de tautologie al formulei. In programele de inteligenta artificiala se folosesc insa si reguli de inferenta nedeductive, numite si invalide deoarece rezultatele obtinute pe baza acestor reguli nu sint intotdeauna adevarate. Aceste reguli pot fi insa utile in numeroase cazuri, asa cum se va vedea mai tirziu, desi nu garanteaza corectitudinea rezultatului obtinut. In continuare se prezinta citeva astfel de reguli de inferenta invalide, dar utilizate:

(1) Inferenta abductiva. Inferenta abductiva se bazeaza pe utilizarea cunostintelor cauzale pentru a explica sau a justifica o concluzie, posibil invalida. Inferenta abductiva are urmatoarea forma:

De exemplu, din formulele:

se poate infera desi s-ar putea ca Radu sa se legene datorita unui cutremur de pamint.

(2) Inferenta inductiva. Inferenta inductiva se bazeaza pe ideea ca o proprietate adevarata pentru o submultime de obiecte dintr-o clasa este adevarata pentru toate exemplele din acea clasa. Inferenta inductiva are forma:

De exemplu, dupa ce se constata ca cele mai multe lebede sint albe, se poate infera prin inductie ca toate lebedele sint albe, desi exista si lebede negre, cum ar fi unele dintre cele care cresc in Australia.

(3) Inferenta analogica. Inferenta analogica este o forma de inferenta bazata pe experienta si se bazeaza pe ideea conform careia situatii sau entitati care tind sa fie asemanatoare sub anumite aspecte sint asemanatoare in general. Inferenta analogica este de fapt o combinatie a celorlalte forme de inferenta: abductive, deductive si inductive. Inferenta analogica are forma:

Toate aceste trei forme de inferenta sint invalide, dar reprezinta modalitati de simulare a rationamentului de bun simt. Ele sint folosite in inteligenta artificiala, mai ales in cazul programelor de invatare automata, asa cum se va vedea in Capitolul 9.

3.2.5 Rezolvarea problemelor in cadrul formalismului logic

Pentru a putea investiga cum se rezolva problemele in logica cu predicate de ordinul I si puterea expresiva a acestui model de reprezentare a cunostintelor, se considera urmatorul exemplu. Fie multimea de enunturi:

(1) Marcus era om.

(2) Marcus era pompeian.

(3) Toti pompeenii erau romani.

(4) Cezar era dictator.

(5) Toti romanii fie erau devotati lui Cezar, fie il urau.

(6) Fiecare om este devotat cuiva.

(7) Oamenii incearca sa asasineze dictatorii fata de care nu sint devotati.

(8) Marcus a incercat sa-l asasineze pe Cezar.

Faptele descrise de aceste propozitii pot fi reprezentate sub forma de formule bine formate in calculul cu predicate de ordinul I astfel:

(1) Marcus era om se exprima sub forma:

(A1) Om(marcus)

Aceasta reprezentare surprinde elementul esential al propozitiei, si anume faptul ca Marcus era om, dar nu exprima informatia continuta in limbaj natural despre timpul trecut utilizat. Pentru exemplul considerat aceasta informatie este nerelevanta, dar in alte cazuri ea ar putea sa conteze, deci ar trebui extinsa reprezentarea in consecinta.

(2) Marcus era pompeian se exprima sub forma:

(A2) Pompeian(marcus)

(3) Toti pompeenii erau romani se exprima sub forma:

(A3)

Conform conventiei facute x este o variabila, in timp ce simbolul marcus utilizat in (A1) si (A2) este o constanta.

(4) Cezar era dictator se exprima sub forma:

(A4) Dictator(cezar)

Tot conform conventiei facute, simbolul cezar este considerat o constanta. In plus, se face presupunerea implicita ca exista un unic individ care se numeste Cezar in universul problemei de rezolvat.

(5) Toti romanii erau fie devotati lui Cezar fie il urau. Pentru a exprima aceasta propozitie, tinind cont de semantica ei, nu se poate folosi conectorul logic care are semnificatia de "sau inclusiv", ci trebuie folosit un "sau exclusiv". In aceste conditii propozitia se exprima sub forma:

(A5)

(6) Fiecare om este devotat cuiva se exprima sub forma:

(A6)

Aici apare o noua problema de traducere a limbajului natural in forma logica, si anume ordinea cuantificatorilor. Utilizind formula logica de mai sus s-a presupus ca pentru orice persoana x, exista o persoana y fata de care x este devotata. Dar aceeasi fraza ar fi putut fi interpretata, eventual, si ca exista o persoana y fata de care toate celelalte persoane sint devotate, ceea ce s-ar fi exprimat in logica sub forma:

(7) Oamenii incearca sa asasineze dictatorii fata de care nu sint devotati poate fi exprimata sub forma:

(A7)

Evident ca si in acest caz ar fi putut sa existe o exprimare logica diferita. Cititorul poate incerca sa o gaseasca.

(8) Marcus a incercat sa-l asasineze pe Cezar se exprima sub forma:

(A8)

Presupunind ca faptele (1)(8) sint adevarate, deci sint axiome, cum se poate stabili daca Marcus nu era devotat lui Cezar, deci cum se poate demonstra teorema (concluzia):

(c) ?

Aceasta demonstratie se poate face aplicind regulile de inferenta ale logicii cu predicate de ordinul I prezentate in sectiunea anterioara. Inspectind axiomele (A1)(A8), se observa ca demonstratia s-ar putea face numai pe baza axiomelor (A1), (A4), (A7) si (A8). Dar apare urmatoarea problema: desi oricine stie ca daca Marcus este om el este in acelasi timp persoana, acest lucru nu este explicit indicat in enunt. Se observa de aici una din dificultatile fundamentale in rezolvarea problemelor de inteligenta artificiala si anume reprezentarea cunostintelor de bun simt. Pentru a putea rezolva problema, trebuie adaugat un nou enunt care sa statueze ca toti oamenii sint persoane.

(9) Toti oamenii sint persoane se exprima sub forma:

(A9)

In acest moment se poate demonstra concluzia (c) pe baza axiomelor (A1), (A4), (A7), (A8) si (A9). Aplicind regula substitutiei in axioma (A7) si substituind uniform variabila x cu constanta marcus si variabila y cu constanta cezar se obtine o noua axioma

(A10)

Aplicind regula Modus Ponens asupra axiomelor (A1) si (A9) se obtine:

(A11) Persoana(marcus)

si aplicind din nou regula Modus Ponens asupra axiomelor (A11), (A4), (A8) si (A10) se obtine concluzia cautata:

Se observa ca aceasta demonstratie a fost facuta prin selectia intuitiva a axiomelor ce trebuie combinate si a diverselor reguli de inferenta ce trebuie utilizate. O asemenea abordare este evident nepractica intr-un program de demonstrare automata a teoremelor. Pentru a putea automatiza procesul de demonstrare este preferabil sa existe o singura regula de inferenta. Aceasta este rezolutia. In plus, trebuie stabilita o strategie de aplicare a regulii de inferenta pentru a ajunge cit mai repede la solutie, daca exista solutie. Aceste probleme vor fi abordate in sectiunea urmatoare.

Un alt aspect important ce trebuie considerat in momentul in care se discuta rezolvarea problemelor in cadrul formalismului logic este posibilitatea existentei unei solutii. Este orice teorema demonstrabila? In cazul logicii propozitionale exista intotdeauna proceduri efective care permit atit stabilirea faptului ca o formula este teorema, cit si a faptului ca nu este teorema. In consecinta problema demonstrarii teoremelor in logica propozitionala este decidabila. In cazul logicii cu predicate de ordinul I se garanteaza existenta unei proceduri care sa demonstreze ca o formula este teorema daca acea formula este intr-adevar teorema. Dar aceasta procedura nu este garantata sa se opreasca daca formula de demonstrat nu este teorema. In consecinta demonstrarea teoremelor in logica cu predicate de ordinul I nu este decidabila, ci este o problema semidecidabila.

In pofida acestui rezultat trist, formalismul logic este utilizat intens ca metoda de rezolvare a problemelor in inteligenta artificiala deoarece, in cele mai multe cazuri, produce rezultatele dorite. De asemenea trebuie tinut cont de faptul ca utilizarea unei strategii particulare sau a unei combinatii de strategii in demonstrarea teoremelor poate genera situatii in care o teorema nu se poate demonstra chiar daca acea formula este intr-adevar teorema. Acesta este cazul strategiilor incomplete. Si in aceasta situatie s-au facut compromisuri, in sensul ca s-au acceptat strategii incomplete de demonstrare a teoremelor datorita avantajului de eficienta pe care il aduc. O strategie completa va reusi intotdeauna sa demonstreze ca o formula este teorema daca formula este cu adevarat teorema, dar aceasta completitudine poate fi penalizata de necesitati crescute ale resurselor de timp si spatiu utilizate de programul care o implementeaza.