Partea a II-a
Reprezentarea cunostintelor
Capitolul 3
Modelul logicii simbolice
Partea a II-a a textului de fata este dedicata metodelor de reprezentare a cunostintelor. Acest capitol si urmatoarele trei prezinta cele mai importante modele de reprezentare a cunostintelor utilizate in programele de inteligenta artificiala. In finalul Capitolului 6 se vor pune in evidenta modalitati de combinare a modelelor discutate, combinarea paradigmelor de reprezentare fiind tendinta actuala in sistemele bazate pe cunostinte.
Unul dintre primele si cele mai importante modele de reprezentare a cunostintelor in inteligenta artificiala este logica simbolica. Logica simbolica a fost dezvoltata de logicieni ca o metoda formala de rationament, in principal in domeniul matematicii, cel mai raspindit model logic fiind logica cu predicate de ordinul I.
Logica cu predicate de ordinul I a fost folosita pentru prima data ca metoda de reprezentare a cunostintelor in inteligenta artificiala in programul de demonstrare a teoremelor al lui Gilmore si in programul "The Logic Theorist" al lui Newell, Shaw si Simon [1963]. Programul lui Gilmore pentru demonstrarea teoremelor in logica cu predicate de ordinul I s-a bazat pe rezultatele teoretice importante ale lui Herbrand [Chang,Lee,1973] care au stabilit conditiile in care o multime de formule (clauze) este inconsistenta. In 1965 Robinson, plecind de la rezultatele lui Herbrand, a propus o metoda mult mai eficienta de stabilire a inconsistentei unei formule: rezolutia. Aceasta metoda si diversele ei rafinari ulterioare au devenit abordarea preferentiala a celor mai multe demonstratoare de teoreme dezvoltate pina in prezent.
Utilizarea logicii simbolice ca model de reprezentare a cunostintelor in inteligenta artificiala este importanta deoarece ofera o abordare formala a rationamentului, cu fundamente teoretice riguroase. Formalismul logic permite derivarea unor cunostinte noi, plecind de la cele existente, pe baza deductiei si a demonstrarii teoremelor. Acest lucru faciliteaza automatizarea proceselor de rationament si executia inferentelor corecte si logic valide. Pe de alta parte, logica simbolica este suficient de expresiva si flexibila pentru a permite reprezentarea cu acuratete a cunostintelor problemei de rezolvat.
Rezolvarea problemelor in cadrul formalismului logic se bazeaza in special pe demonstrarea teoremelor. Exista doua abordari importante in demonstrarea teoremelor: metodele sintactice si metodele semantice.
Metodele sintactice de demonstrare a teoremelor, cum ar fi de exemplu cele propuse de Herbrand, Gilmore si Robinson, se bazeaza pe procedee mecanice de aplicare a regulilor de inferenta si sint independente de domeniul de interpretare al formulei. Aceste metode pot fi usor automatizate si constituie baza tuturor programelor de demonstrare a teoremelor.
Metodele semantice de demonstrare a teoremelor se bazeaza pe utilizarea sistematica a valorilor de adevar ale formulelor si depind de domeniul de interpretare fixat. Deoarece domeniul de interpretare al unei formule este de multe ori infinit, aceste metode sint greu algoritmizabile. O discutie a metodelor semantice de demonstrare poate fi gasita in Malita [1987] si Popa [1992]. O prezentare detaliata a principiilor teoretice si a metodelor sintactice de demonstrare a teoremelor poate fi gasita in Chang si Lee [1973] si Gabbay s.a. [1993].
Reprezentarea cunostintelor in logica se bazeaza in esenta pe urmatoarele doua componente:
Crearea structurilor formale care reprezinta fapte de baza, inferente si alte tipuri de cunostinte, numite structuri presupuse.
Aplicarea regulilor de inferenta ale sistemului logic pentru a compara, combina si obtine din aceste structuri presupuse (date) noi structuri, numite structuri deduse.
De exemplu, enuntul "Toti studentii de la calculatoare stiu sa programeze" poate fi exprimat in logica cu predicate de ordinul I astfel:
Daca se stie in plus ca Radu este student la calculatoare, deci
se poate concluziona pe baza celor doua structuri presupuse noua structura
3.1 Logica propozitionala
Logica propozitionala este un caz particular al logicii cu predicate de ordinul I. Elementele de baza ale logicii propozitionale sint propozitiile, numite si atomi sau propozitii simple. Urmatoarele enunturi sint propozitii:
Masina este alba P
Oamenii traiesc pe luna Q
Notatiile din dreapta reprezinta simbolic propozitiile enuntate. O propozitie poate fi adevarata sau falsa, deci poate avea doua valori de adevar. De exemplu, propozitia P este adevarata si propozitia Q este falsa. Atita timp cit se admit doar doua valori de adevar pentru o propozitie, adevarat si fals, logica se numeste logica clasica sau logica bivalenta. Acceptarea unui numar mai mare de valori conduce la logici polivalente (neclasice). Prezentarea care urmeaza se situeaza numai in cadrul logicii bivalente.
Propozitiile simple sau atomii sint compozabile. Ele se pot combina, dind nastere la noi propozitii care sint, la rindul lor, adevarate sau false. Propozitiile combinate se formeaza din atomi folosind conectorii logici. Conectorii logici indica operatiile de asociere sau combinare care sint cele mai frecvente in vorbire sau rationament. De exemplu, din doua propozitii simple
Mihaela este frumoasa P1
Mihaela este buna P2
se poate forma propozitia compusa
Mihaela este frumoasa si Mihaela este buna
notata cu  . In continuare se vor folosi urmatoarele simboluri pentru conectorii logici:
~ negatie
conjunctie
disjunctie
implicatie simpla
implicatie dubla
In consecinta, alfabetul logicii propozitionale este format din simbolurile care desemneaza atomii, conectorii logici si alte simboluri cum ar fi parantezele. In plus exista doua simboluri speciale pentru desemnarea valorilor logice de adevarat si fals, notate prin conventie cu a, respectiv f.
Limbajul logicii propozitionale se construieste pornind de la definitia alfabetului si definind regulile corecte de formare a cuvintelor limbajului cu simboluri din alfabet. Un cuvint in acest limbaj se numeste formula bine formata.
Definitie. 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.
O formula bine formata se scrie riguros utilizind paranteze. De obicei se omit aceste paranteze ori de cite ori absenta lor nu da nastere la confuzii, tinind cont de precedenta conectorilor logici. Precedenta conectorilor logici, in ordine descrescatoare, este: ~, , , , .
Exemple:
1.  nu este o formula bine formata.
2.  este o formula bine formata si poate fi scrisa  .
3.  este o formula bine formata si poate fi de asemenea scrisa  .
3.1.2 Semantica logicii propozitionale
Semantica sau intelesul unei propozitii este valoarea de adevarat sau fals a acesteia, i.e. atribuirea unei valori de adevar acelei propozitii pe baza unei functii de evaluare a propozitiei.
Definitie. Se numeste interpretare a unei formule bine formate atribuirea de valori de adevar fiecarui atom din formula. Altfel spus, o interpretare specifica functiile de evaluare ale tuturor atomilor componenti ai formulei.
Exemplu. Fie formula  si o interpretare I1 care asigneaza valorile de adevar a lui P si f lui Q. In aceasta interpretare formula este adevarata. O interpretare diferita I2 asigneaza valorile de adevar a lui P si a lui Q, formula fiind falsa in aceasta interpretare. Evident, exista patru interpretari distincte pentru aceasta propozitie.
Functia de evaluare a unei formule asociaza formulei o unica valoare de adevar, pe baza valorilor de adevar ale atomilor componenti ai formulei, utilizind regulile de evaluare ale conectorilor logici, reguli specificate de obicei prin tabele de adevar. Deoarece se refera la semantica formulei, aceste reguli se mai numesc si reguli semantice. In continuare se va nota valoarea de adevar a unei formule P cu Pv. Odata ce s-a stabilit o interpretare unei formule, valoarea ei de adevar poate fi determinata. Aceasta se poate face prin aplicarea repetata a regulilor semantice asupra unor portiuni din ce in ce mai mari ale formulei, pina cind se determina o singura valoare de adevar pentru formula. Regulile semantice sint prezentate in Figura 3.1.
Figura 3.1 Regulile semantice ale formulelor bine formate in calculul propozitional
Se observa ca Figura 3.1 reprezinta concis regulile de evaluare ale conectorilor logici. De exemplu, semnificatia tabelelor de adevar ale conectorilor logici si
este surprinsa de regulile 3, 4, 8 si 9 din Figura 3.1. In aceste conditii se poate gasi semnificatia unei propozitii fiind data o interpretare I pentru acea propozitie.
Exemplu. Fie formula  si interpretarea I: P adevarat, Q fals si R fals. Atunci:
prin aplicarea regulii 2 ~Q adevarat
prin aplicarea regulii 3  adevarat
prin aplicarea regulii 6  fals
prin aplicarea regulii 5 fals
Deci valoarea de adevar PV a formulei in interpretarea I este fals.
3.1.3 Proprietatile propozitiilor
Pe baza functiei de evaluare si a domeniului de interpretare se pot specifica urmatoarele proprietati ale formulelor bine formate:
O formula bine formata este valida sau tautologie daca formula are valoarea adevarat in orice interpretare.
O formula bine formata este inconsistenta (contradictie, nerealizabila) daca formula are valoarea fals in orice interpretare.
O formula bine formata este realizabila sau consistenta daca exista cel putin o interpretare in care formula are valoarea adevarat.
Doua formule sint echivalente daca au aceeasi valoare de adevar in orice interpretare.
Figura 3.2 prezinta intuitiv aceste proprietati ale formulelor bine formate.
Figura 3.2 Realizabilitatea formulelor bine formate
Realizarea rationamentului intr-un sistem logic implica existenta unui mecanism de obtinere a noi formule pe baza formulelor existente, deci de extindere consistenta a cunostintelor universului problemei.
Definitie. 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. Definitia se poate extinde si in cazul a n formule. O formula F este consecinta logica a unei multimi de formule  daca formula F este adevarata in toate interpretarile in care sint adevarate.
Consecinta logica se noteaza  .
Exemple:
1. P este o formula realizabila dar nu este valida deoarece o interpretare care atribuie fals lui P atribuie fals si formulei P.
2.  este o formula valida deoarece pentru orice interpretare, formula  este adevarata.
3.  este o contradictie deoarece pentru orice interpretare, formula  este falsa.
4. P si ~(~P) sint formule echivalente deoarece fiecare are aceeasi valoare de adevar pentru orice interpretare.
5. P este o consecinta logica a formulei  deoarece pentru orice interpretare in care este adevarata, P este totdeauna adevarata.
Notiunea de consecinta logica ofera o modalitate de a realiza inferenta valide in logica propozitionala. Urmatoarele doua teoreme stabilesc criteriile in functie de care o formula este o consecinta logica a unui set de formule.
Teorema. Formula F este consecinta logica a unei multimi de formule daca formula  este valida.
Demonstratie.
() Daca F este o consecinta logica a multimii de formule  , atunci pentru orice interpretare I in care sint adevarate, deci formula  este adevarata, F este de asemenea adevarata prin definitie. Deci  este adevarata pentru astfel de interpretari. Pentru interpretarile in care este falsa, este adevarata conform regulii 7 din Figura 3.1. Rezulta de aici ca este adevarata in orice interpretare, deci este formula valida.
() Daca este valida, atunci pentru orice interpretare I pentru care este adevarata, deci in care si sint adevarate, F este adevarata, deci F este o consecinta logica a multimii de formule .
Teorema. Formula F este consecinta logica a unei multimi de formule daca formula  este inconsistenta.
Demonstratie.
Demonstratia acestei teoreme se face pe baza primei teoreme. Conform acesteia, F este o consecinta logica a multimii de formule daca si numai daca este valida, i.e. daca si numai daca  este inconsistenta.
  , deci teorema este demonstrata.
Aceste doua teoreme prezinta o importanta deosebita in rationamentul logic, deoarece problema stabilirii consecintelor logice se reduce la problema demonstrarii validitatii sau a inconsistentei unei formule bine formate. Aceasta idee este importanta si reprezinta esenta tuturor metodelor de demonstrare automata a teoremelor in logica simbolica, asa cum se va vedea in Sectiunea 3.3.
O posibilitate de a determina echivalenta a doua formule este utilizarea tabelelor de adevar. Se observa ca demonstratia celei de a doua teoreme s-a facut utilizind echivalenta formulelor logice. De exemplu, pentru a arata ca  este o formula echivalenta cu  , se poate construi urmatoarea tabela de adevar.
In tabelul urmator sint prezentate citeva legi importante de echivalenta in logica propozitionala.
3.1.4 Discutie despre conectori
Definitie. O multime de conectori logici se numeste multime adecvata daca orice formula logica poate fi exprimata folosind numai conectorii acestei multimi.
Multimea  este o multime adecvata de conectori. Deasemenea, perechile  ,  si  sint si ele multimi adecvate de conectori. Nici o alta pereche de conectori din multimea  nu este o multime adecvata de conectori; de exemplu  nu este o multime adecvata.
Se pune problema minimalitatii unei multimi de conectori, respectiv se pune intrebarea "Exista multimi adecvate formate dintr-un singur conector?". Exista doi conectori, care, fiecare in parte, formeaza o multime adecvata de conectori.
Conectorul lui Nicod, numit si Nor si notat cu , permite definirea urmatoarelor formule de echivalenta:  si  , ceea ce face ca  sa fie o multime adecvata. Conectorul are tabela de adevar:
Conectorul lui Sheffer, numit incompatibilitate, si notat cu , este definit prin urmatoarea formula:  , ceea ce inseamna ca  este adevarat cind cel putin un atom este fals. Sint adevarate formulele:  si  , ceea ce face ca  sa fie o multime adecvata. Conectorul are tabela de adevar:
Semnificatia anumitor conectori a fost mult discutata in logica. De exemplu, disjunctia introduce ambiguitatea. Exista doua tipuri de disjunctie, disjunctia simpla si disjunctia exclusiva, notata de obicei cu . Urmatoarele formule definesc disjunctia exclusiva:
Replicatia, notata  , este folosita pentru a elimina argumentatiile care nu sint de acord cu semnificatia implicatiei logice conform careia falsul implica orice si adevarul este implicat de orice. Tabela de adevar a replicatiei este prezentata mai jos, comparativ cu cea a implicatiei.
3.1.5 Reguli de inferenta in logica propozitionala
Regulile de inferenta in logica propozitionala ofera o modalitate de a realiza demonstratii logice sau deductii. Fiind data o multime de formule  , problema este de a demonstra adevarul unei formule F, numita concluzie sau teorema, pe baza formulelor din P, numite axiome si utilizind regulile de inferenta.
Metodele sintactice de demonstrare a teoremelor, care nu se bazeaza pe atribuirea de valori de adevar atomilor din formula, utilizeaza reguli de inferenta sintactice. Aceste reguli de inferenta, logic valide, permit obtinerea de noi formule din multimea de formule initiale numai pe baza unor operatii sintactice. Cele mai importante reguli de inferenta (deductie) in logica propozitionala sint:
(1) Modus Ponens 
(2) Substitutia. Daca P este o formula valida, formula P' obtinuta din P prin substitutia consistenta a atomilor din P este de asemenea valida.
Exista doua tipuri de substitutie: substitutia uniforma, in care o variabila se inlocuieste peste tot cu aceeasi formula (echivalenta cu ea sau nu) si substitutia prin echivalenta, in care se poate inlocui fiecare aparitie a unei variabile cu o alta formula, dar aceste formule trebuie sa fie echivalente cu variabila substituita.
Exemplu. Formula este valida; atunci formula  este de asemenea valida prin aplicare regulii de substitutie uniforma.
(3) Regula inlantuirii 
(4) Regula conjunctiei 
(5) Regula transpozitiei 
Observatie. Aceste reguli de inferenta pastreaza caracterul de tautologie al formulelor obtinute prin aplicarea lor, daca formulele de plecare sint tautologii.
Dostları ilə paylaş: | 
