SBC3-1-2015

1

Sisteme bazate pe cunoaştere

Cap. III. Bazele logice ale inteligen ţei artificiale

1) Terminologia logicii matematice2) Calculul propoziţional3) Calculul cu predicate4) Elemente de teoria deducţiei

2

Bazele logice ale IA

Scopuri urm ărite :

Înţelegerea aspectelor de logică folosite în efectuarea raţionamentelor în sistemele de IA, în special în demonstrarea automată a teoremelor

Competen ţe dobândite:

Înţelegerea modului în care sistemele de IA pot fi analizate şi validate prin mecanismele formale din logică

3

III. Bazele logice ale IA

Limbajul obişnuit este ambiguu şi imprecis. În gândire apar afirmaţii, judecăţi, care se exprimă sub formă de enunţuri. Corespondentul acestora în SBC vor fi faptele şi regulile din baza de cunoştinţe.

Definiţia 1. Enunţul este o formaţiune lingvistică elementară, cu sens (de tip) narativ, declarativ şi cu înţeles de sine stătător - se afirmă ceva despre ceva.

Enunţul poate fi scris sau vorbit şi este o formaţiune capabilă să poarte informaţie. Din punct de vedere logic enunţul se compune din două părţi: subiectul (sau subiectele) şi partea predicativă.

Definiţia 2. Subiectul este acel ceva despre care se afirmă ceva într-un enunţ. Restul, ceea ce rămâne după îndepărtarea subiectului sau a subiectelor, este partea predicativă.

1. Terminologia logicii matematice

4

ExempleMicroprocesorul 8080 este depăşit. Microprocesorul 80686 este mai performant decât

microprocesorul 8086.

Ce înseamnă SBC ? Deschide geamul !

Un enunţ are unul sau mai multe subiecte şi o singură parte predicativă.

Subiectul poate să fie precizat (în IA se foloseşte termenul instanţiat) sau nu.


5

ExempluNumărul x se divide cu 2.

Definiţia 3. Un enunţ cu toate subiecte instanţiate se numeşte propoziţie. Enunţul care conţine unul sau mai multe subiecte neinstanţiate se numeşte predicat. Subiectele neinstanţiate dintr-un predicat se numesc variabile. Numărul subiectelor neprecizate dintr-un predicat se numeşte aritatea predicatului.

ExempleOraşul x şi oraşul y sunt conectate prin n drumuri. Numărul x este mai mare decât 3.


6

O propoziţie poate fi considerată ca un predicat de aritate 0. Dacă într-un predicat de aritate n, într-un mod oarecare, se instanţiază o variabilă a sa, se obţine un predicat de aritate n-1.

În limbajul natural putem exprima oricâte înţelesuri dorim prin compunerea enunţurilor. Enunţurile compuse au fost formalizate în logică folosind operatorii logici:

• Operaţiile logice (negaţia, conjuncţia, disjuncţia, implicaţia şi echivalenţa)

• Cuantificatorii (∃, ∀).


7

Definiţia 4. Fie P, Q două enunţuri.

Negaţia lui P, pe care o notăm cu (7P), este enunţul care afirmă că P nu are loc.

Conjuncţia lui P şi Q este enunţul notat (P ∧ Q) care afirmă că fiecare din cele două enunţuri are loc.

Disjuncţia lui P şi Q, notată cu (P ∨ Q), este enunţul care afirmă că măcar unul din cele două enunţuri are loc.

Implicaţia P implică Q se notează prin (P ⇒ Q) şi este enunţul care afirmă că dacă P are loc, atunci are loc şi Q.

Echivalenţa lui P şi Q afirmă că P şi Q au loc în acelaşi timp şi se notează cu (P ⇔ Q).


8

Cuantificatorii generează noi enunţuri numai dacă sunt ataşaţi variabilelor predicatelor. Dacă P este un predicat în care apar variabilele x, y, z, atunci îl vom nota P(x, y, z). Cuantificatorii permit formarea de enunţuri compuse în modul următor.

Definiţia 5. Fie P un predicat ce conţine variabila x şi care afirmă că obiectul desemnat de variabila x are proprietatea µ. Enunţul construit din P cu cuantificatorul ∃, relativ la variabila x, este enunţul notat (∃x) P(x), care se citeşte “există x astfel încât P(x)” şi care afirmă că în clasa de obiecte din care face parte x, există măcar unul cu proprietatea µ.


9

Enunţul construit din P cu cuantificatorul ∀ relativ la variabila x, se notează (∀x) P(x), se citeşte “oricare ar fi x, P(x)” şi afirmă că orice obiect al clasei din care face parte x are proprietatea µ.

Atunci când într-un predicat apare variabila x, înţelesul este precizat dacă ştim domeniul (mulţimea, iar în IA termenul folosit este univers de discurs) în care variabila x poate lua valori, adică în IA vom spune că se instanţiază.


10

În acest fel şi definiţiile enunţurilor în care apar cuantificatorii, date mai sus, au suport:cuantificatorul ∀ ne permite să precizăm informaţii despre toate elementele universului de discurs fără a fi necesar să le enumerăm, iar ∃ ne permite să precizăm existenţa unui element din universul de discurs, element având anumite proprietăţi, fără a fi necesar să-l identificăm în mod direct.


11

Informaţia circulă, este prelucrată şi stocată în măsura în care ea prezintă interes pentru receptor, adică în măsura în care are valoare. Cea mai simplă valoare informaţională este valoarea de adevăr a informaţiei. Atât în domeniul SBC cât şi în logică ne interesează determinarea valorii de adevăr a enunţurilor. Valoarea de adevăr reprezintă gradul de concordanţă dintre informaţia respectivă şi situaţia de fapt la care aceasta se referă. Valoarea de adevăr a unui enunţ poate avea o întreagă scară de gradaţii.


12


Calculul propoziţional este acea parte a logicii care se ocupă cu analiza propoziţiilor din punct de vedere al compunerii lor corecte cu ajutorul operaţiilor logice şi al studiului valorilor de adevăr pentru enunţurile compuse în acest fel.

Se poate vorbi despre un limbaj al calculului propoziţional, care este un limbaj formal, oferind o primă posibilitate de a formaliza limbajul natural (completarea făcându-se prin limbajul calculului cu predicate).

Orice limbaj presupune existenţa unui alfabet, care precizează simbolurile folosite, a unei sintaxe stabilind cum pot fi combinate în limbajul respectiv simbolurile admise şi a unei semantici, stabilind semnificaţia combinaţiilor admise de sintaxă.

2. Calculul propoziţional

13


Definiţia 6. Numim alfabetul calculului propoziţionalmulţimea Sp = V ∪ L ∪ {( , )}

V este o mulţime infinit numărabilă de simboluri, care se numesc variabile propoziţionale. Acestea vor fi notate cu p, q, r, eventual cu indici p1, p2

L = {7, ∧, ∨, ⇒, ⇔} este mulţimea operaţiilor logice.

Definiţia 7. Numim cuvânt peste un alfabet S o succesiune finită de elemente din S. Mulţimea tuturor cuvintelor peste alfabetul S se notează cu S*. Ne vor interesa cuvintele peste alfabetul calculului propoziţional, mulţimea acestora notându-se cu . Elementele mulţimii le vom nota cu A, B, . . .

Sintaxa calculului propozi ţional

*pS

14

Definiţia 8. Un cuvânt A ∈ se numeşte formulă în calculul propoziţional (notăm mulţimea formulelor în calculul propoziţional cu Fp) dacă şi numai dacă îndeplineşte una din condiţiile:

1. A ∈ V (A este o variabilă propoziţională);2. A = (7 B) unde B ∈ Fp;3. A = (B # C) unde B, C ∈ Fp, iar # ∈ L \ {7}.

Se poate observa că definiţia de mai sus este una de tip recursiv, deoarece entitatea definită este descrisă chiar pe baza entităţii de acelaşi tip (în cazurile 2 şi 3). Totodată, ea poate fi privită şi ca fiind de tip inductiv, în care 1 asigură pasul iniţial, iar 2 şi 3 asigură pasul inductiv.


*pS

15

Exemplu

Dacă p, q, r ∈ V, atunci: q r ⇒ ∧, r ∨ q, ((7p) ∧ (r ⇔ q)) sunt trei cuvinte peste alfabetul calculului propoziţional (elemente din ).

Din acestea, numai ultimul cuvânt este şi formulă în calculul propoziţional (element din Fp). Rezultă din definiţiile de mai sus şi din acest exemplu că are loc relaţia:

V ⊂ Fp ⊂ , incluziunile respective nefiind stricte.


*pS

*pS

16

Folosirea strictă a definiţiei formulei în calculul propoziţional presupune manevrarea unui număr mare de paranteze. Pentru simplitate, A ∈ Fp poate fi reprezentată printr-un cuvânt mai simplu A’, obţinut din A prin renunţarea, omiterea unor paranteze, cu condiţia ca din cuvântul redus A’ să se poată reconstitui în mod unic formula A, pe baza următoarelor 3 reguli de reconstituire:

1) restabilirea parantezelor se face în ordine pentru: 7, ∧, ∨, ⇒, ⇔;2) dacă A ∈ Fp atunci cuvântul 77 . . . 7A reprezintă formula (7 (7 (. . . (7A)). . .) );3) dacă A1, A2, . . . An ∈ Fp şi # ∈{∧, ∨, ⇒, ⇔} atunci cuvântul A1 # A2 #. . . #An reprezintă formula (. . . ((A1 # A2) #. . . #An).


17

Regula 1) de mai sus fixează prioritatea operaţiilor în calculul propoziţional – cea mai prioritară este negaţia, urmată de conjuncţie, disjuncţie, implicaţie şi echivalenţă, iar regulile 2) şi 3) arată că reconstituirea se face de la stânga la dreapta. Practic, se caută de la stânga la dreapta cea mai prioritară operaţie logică în jurul căreia se poate reconstitui o formulă, se reconstituie, ş.a.m.d.

ExempluDacă p, q, r ∈ V, să se reconstituie formula din care provine următorul cuvânt A: A = (p ⇒ q ∨ r ⇔ p) ∨ (7q ⇒ r) ∧ 7p ∧ r


18

Rezolvare

A1 = (((p ⇒ (q ∨ r)) ⇔ p) ∨ ((((7q) ⇒ r) ∧ (7p)) ∧ r))

În general nu se poate renunţa la toate parantezele unei formule pentru a obţine o formă simplificată a acesteia, existând pericolul de alterare a conţinutului formulei. Acest aspect este verificabil chiar pe exemplul de mai sus, unde, dacă în cuvântul iniţial A am renunţa la toate parantezele, după reconstituire nu am mai obţine A1, ci A2:

A2 = ((p ⇒ (q ∨ r)) ⇔ ((p ∨ (7q)) ⇒ ((r ∧ (7p)) ∧ r)))


19

Ţinând seama de prioritatea operaţiilor logice ne vom putea da seama de parantezele la care putem renunţa într-o formulă şi de cele la care nu putem renunţa.

ExempluFormula A = ((7p) ⇒ ((r ∨ p) ∧ (7r))), unde p, r ∈ V, poate fi reprezentată simplificat prin cuvântul: A1 = 7p ⇒ (r ∨ p) ∧ 7r.

Dacă am renunţa la toate parantezele, atunci din A2 = 7p ⇒ r ∨ p ∧ 7r nu am obţine prin reconstituire A, ci:A3 = ((7p) ⇒ (r ∨ (p ∧ (7r)))).


20

În continuare vom lucra numai cu reprezentările simplificate ale formulelor şi nu vom mai face distincţie între o formulă şi reprezentarea ei simplificată, cea obţinută prin omiterea anumitor paranteze.

Definiţia 9. Dacă A ∈ Fp atunci mulţimea părţilor lui A, notată π(A), se defineşte inductiv prin: 1) dacă A ∈ V atunci π(A) = {A};2) dacă A = 7B, unde B ∈ Fp, atunci π(A) = π(B) ∪ {A};3) dacă A = B # C, unde B, C ∈ Fp şi # ∈ L \ {7}, atunci

π(A) = π(B) ∪ π(C) ∪ {A}.


21

Rezultă din definiţia de mai sus că mulţimea π(A) are cardinalul egal cu 1 dacă şi numai dacă A ∈ V (A este o variabilă propoziţională).

În acest caz A se numeşte formulă atomică sau atom. Dacă A ∈ Fp şi A nu este atom, atunci formula va fi de forma A = 7B sau A = B # C, cu # ∈ L \ {7}, caz în care formula A se numeşte formulă compusă, iar 7 sau # se numeşte operaţie dominantă a formulei.

Elementele lui π(A) se numesc subformule ale lui A.


22

Exemplu

Fie p, r ∈ V şi formula A = 7p ⇒ (r ∨ p) ∧ 7r.

A este formulă compusă.

π(A) = {A, 7p, (r ∨ p) ∧ 7r, p, r ∨ p, 7r, r}

Operaţia dominantă pentru A este ⇒.


23

Ţinând seama de caracterul inductiv al definiţiei formulei în calculul propoziţional, vom putea aplica inducţia matematică pentru a demonstra proprietăţi referitoare la formulele din calculul propoziţional. Astfel, poate fi formulată o schemă a inducţiei matematice pentru formulele din calculul propoziţional.

Teorema Fie µ o proprietate referitoare la formulele din calculul propoziţional. Notăm cu µ (A) faptul că proprietatea µ este adevărată pentru A, A ∈ Fp. Dacă au loc:

i) µ(A), oricare ar fi A o formulă atomică;ii) dacă din µ(A1) şi µ(A2), A1, A2 fiind formule oarecare, se deduce µ(7A1), µ(A1 ∧ A2), µ(A1 ∨ A2), µ(A1 ⇒ A2), µ(A1 ⇔ A2)

atunci µ(A) are loc, oricare ar fi A ∈ Fp.


24


Definiţia 10. Se numeşte evaluare a formulelor în calculul propoziţional extensia unică a oricărei funcţii v : V → {adevărat, fals} la Fp, extensie pe care o vom nota tot cu v,

v : Fp → {adevărat, fals}

şi care se calculează după regulile sintetizate în următoarele tabele (în acestea am notat v(x) cu xv – valoarea evaluării v pentru x - şi adevărat cu a, respectiv fals cu f):

Semantica calculului propozi ţional

25


af

fa

(7A)vAv

aaffff

faafaf

ffaffa

aaaaaa

(A ⇔ B)v(A ⇒ B)v(A ∨ B)v(A ∧B)vBvAv

26

Ţinând seama de caracterul recursiv al definiţiei formulei în calculul propoziţional, se constată că pentru determinarea lui Av pentru o formulă dată este suficient să cunoaştem valorile lui v pentru toate variabilele propoziţionale ce apar în A.

Definiţia 11. O formulă A se numeşte tautologie (sau lege logică) dacă oricare ar fi v o evaluare a formulelor, avem Av = adevărat. Dacă A este tautologie, atunci se foloseşte notaţia |=A. Definiţia 12. O formulă A se numeşte realizabilă (consistentă, verificabilă) dacă există o evaluare v astfel încât Av = adevărat. O formulă A se numeşte nerealizabilă (contradicţie, falsă) dacă oricare ar fi v o evaluare avem Av

= fals.


27

Tautologii

Contradicţii

Formule realizabile

Fig. 1. O împărţire a mulţimii formulelor din calculul propoziţional

Fp


28

Teorema 2. O formulă este tautologie dacă şi numai dacă negaţia ei este contradicţie. Teorema 3. O formulă este realizabilă dacă şi numai dacă negaţia ei nu este tautologie.

Demonstraţiile sunt imediate pe baza definiţiei evaluării. Teorema 2 ne arată o posibilitate de a demonstra că o formulă este tautologie: se arătă că negaţia ei este contradicţie. Aceasta este calea urmată de demonstrarea automată a teoremelor.


29

Definiţiile privind realizabilitatea şi nerealizabilitatea se extind pentru mulţimi de formule.Definiţia 13. O mulţime I ⊆ Fp este realizabilă (consistentă) dacă există o evaluare v astfel încât oricare ar fi A ∈ I să avem Av = adevărat. O mulţime I ⊆ Fp este nerealizabilă (inconsistentă) dacă oricare ar fi v o evaluare, există A ∈ I astfel încât Av = fals.

Este uşor de observat că orice mulţime de formule este sau realizabilă sau nerealizabilă. Pentru SBC ne va interesa ca baza de cunoştinţe să fie păstrată realizabilă.


30

Deşi în definiţia tautologiei se cere Av = adevărat pentru oricare evaluare v, şi există o infinitate de evaluări, se poate decide într-un număr finit de paşi dacă formula A este tautologie pe baza observaţiilor următoare:

a) în formula A intră un număr finit de variabile propoziţionale; fie acestea p1, p2,. . .,pn.b) dacă v şi w sunt două evaluări astfel încât: pi

v = piw

∀ i = {1, ..., n}, atunci Av = Aw.c) există 2n evaluări distincte pe mulţimea {p1, . . . pn}.

Rezultă astfel că vom avea de testat cel mult 2n cazuri pentru a decide dacă A este tautologie.


31

Pentru calculul propoziţional există mai mulţi algoritmi ce pot fi aplicaţi pentru a decide asupra caracterului de tautologie al unei formule; unul dintre aceştia este prezentat în continuare.

Asociem pentru fiecare variabilă propoziţională e o variabilă numerică ē cu valori în mulţimea {0, 1}. Pentru orice formulă A, ale cărei variabile propoziţionale sunt e1, . . . , en, asociem un polinom depinzând de variabilele numerice ē1, . . . , ēn . Această asociere o facem pe baza următoarelor reguli de calcul:


32

1) dacă A ∈V, deci A = e, atunci Ā = ē2) dacă A = 7O, O ∈ Fp, atunci Ā = 1- Ō3) dacă A = O ∧ U, O, U ∈ Fp, atunci Ā = Ō·Ū4) dacă A = O ∨ U, O, U ∈ Fp, atunci Ā = Ō + Ū - Ō·Ū5) dacă A = O ⇒ U, O, U ∈ Fp, atunci Ā = 1- Ō + Ō·Ū6) dacă A = O ⇔ U, O, U ∈ Fp, atunci

Ā = 1 - Ō - Ū + Ō Ū + Ō Ū

Se remarcă faptul că prin regulile de mai sus orice polinom va lua valori în mulţimea {0, 1}.


33

Teorema 4. Dacă v este o evaluare oarecare şi oricare ar fi e, e ∈ V, îi asociem ē, astfel încât ē = 1 dacă ev = adevărat şi ē = 0 dacă ev = fals, atunci oricare ar fi A, A ∈ Fp, Av = adevărat dacă şi numai dacă valoarea polinomului Ā (asociat lui A conform celor şase reguli de calcul de mai sus), pentru valorile corespunzătoare ale variabilelor numerice ē de care depinde este Ā= 1.

Rezultă, pe baza teoremei 4, algoritmul pentru a decide dacă o formulă A este tautologie:

1) se construieşte polinomul Ā asociat formulei A;2) se verifică dacă Ā este o funcţie polinomială identic egală cu 1.


34

Pentru aplicarea algoritmului este util să observăm că dacă x este o variabilă ce ia valori în mulţimea {0,1} atunci x2 = x şi x(1-x) = 0. Această observaţie poate ajuta în rezolvarea pasului al doilea al algoritmului.

ExempluFie formula A = e ⇒ (u ⇒ e ∧ u), e, u ∈ V. Pentru a demonstra că are loc |=A construim Ā folosind

regulile de asociere.

Ā = 1 – ē + ē (u ⇒ e ∧ u) = 1 - ē + ē(1 – ū + ū e ∧ u) =

1 - ē + ē(1 – ū + ū ē ū) = 1 - ē + ē - ē ū + ē ū = 1


35

Teorema 5. Fie A ∈ Fp, o formulă ce conţine variabilele propoziţionale p1, . . ., pn şi fie B formula obţinută din A prin substituţia simultană a variabilelor p1, . . , pn, respectiv cu formulele C1, . . .Cn

(se poate demonstra, de exemplu folosind inducţia matematică pentru formulele din calculul propoziţional, că şi B este formulă).

Dacă A este tautologie atunci şi B este tautologie.

Demonstraţie.În enunţul teoremei p1, . . ., pn pot fi toate, sau o parte

din variabilele propoziţionale care apar în A. Fie v o evaluare oarecare.


36

Trebuie să arătăm că Bv = adevărat. Construim evaluarea w care satisface egalităţile: p1

w = C1v, p2

w = C2v, . . ., pn

w = Cnv.

Din această construcţie şi din felul în care a fost obţinută B rezultă: Aw = Bv. Cum din ipoteza teoremei are loc |= A, înseamnă că Aw = adevărat şi deci Bv = adevărat, ceea ce trebuia demonstrat.

Din această teoremă rezultă că în Fp există o infinitate de tautologii, de exemplu obţinute dintr-o unică tautologie prin substituţii repetate ale variabilelor propoziţionale din aceasta, cu alte formule. Există însă o serie de tautologii de bază, utilizate mai des. Acestea sunt date de următoarea teoremă.


37

Teorema 6. Dacă A, B, C ∈ Fp atunci au loc:

1) |= A ⇒ A 2) |= A ⇔ A (legea identităţii pentru echivalenţă)3) |= A ⇔ 77A (negarea negaţiei)4) |= A ∨ 7A (legea terţului exclus)

5) |= A # B ⇔ B # A, # ∈ {∧, ∨, ⇔} (legi de comutativitate pentru conjuncţie, disjuncţie şi echivalenţă)

6) |= (A # B) # C ⇔ A # (B # C), # ∈ {∧, ∨, ⇔} (legi de asociativitate pentru conjuncţie, disjuncţie şi echivalenţă)


38

7) |= A #1 (B #2 C) ⇔ (A #1 B) #2 (A #1 C), #1, #2 ∈ {∧, ∨, ⇔} (legi de distributivitate pentru conjuncţie şi disjuncţie)

8) |= (A ⇒ B) ⇔ (7A ∨ B) (înlocuirea implicaţiei cu disjuncţie)

9) |= (A ⇒ B) ∧ (B ⇒ C) ⇒ (A ⇒ C)10) |= (A ⇔ B) ⇔ (A ⇒ B) ∧ (B ⇒ A) (înlocuirea

echivalenţei cu dubla implicaţie)11) |= 7(A ∧ B) ⇔ (7A ∨ 7B) (lege a lui De Morgan)12) |= 7(A ∨ B) ⇔ (7A ∧ 7B) (lege a lui De Morgan)13) |= (A ⇒ B) ⇔ (7B ⇒ 7A) (legea contrapoziţiei)


39

14) |= 7A ∧ (A ∨ B) ⇒ B şi |= 7B ∧ (A ∨ B) ⇒ A (rezoluţia unitară)

15) |= (A ∨ B) ∧ (7B ∨ C) ⇒ (A ∨ C) (rezoluţia, importantă în demonstrarea automată a teoremelor)

16) |= A ⇒ (B ⇒ A)17) |= A ∧ (A ⇒ B) ⇒ B (modus ponens sau regula

detaşării, importantă pentru SE)18) |= (A ⇒ B) ∧ 7B ⇒ 7A (modus tollens)

Definiţia 14. Dacă A şi B sunt formule ele sunt echivalente dacă este tautologie A ⇔ B (conform definiţiei evaluării, acesta este acelaşi lucru cu a spune că A şi B iau aceleaşi valori de adevăr pentru orice evaluare).


SBC3-1-2015

Documents

Transcript of SBC3-1-2015