Logică computaționalăO introducere practică pentru studenți la

informatică

Note de curs

Adrian Crăciunadrian.craciun@e-uvt.ro

24 ianuarie 2019

1

Cuprins

I. Introducere 2

1. Rezolvare problemelor prin raționament 31.1. Rezolvarea de probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2. Rezolvarea problemelor prin raționament . . . . . . . . . . . . . . . . . . . 61.3. Limbajul ca suport al raționamentului . . . . . . . . . . . . . . . . . . . . 81.4. Logica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.5. Probleme abordate de logica matematică . . . . . . . . . . . . . . . . . . . 10

1.5.1. Limbaje: proprietăţi, clasificare . . . . . . . . . . . . . . . . . . . . 101.5.2. Model: consistenţă . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.5.3. Corectitudinea regulilor de raţionament . . . . . . . . . . . . . . . 121.5.4. Completitudinea regulilor de raţionament . . . . . . . . . . . . . . 131.5.5. Limitele raţionamentului: incompletitudine, nedecidabilitate . . . . 131.5.6. Complexitate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.6. Rolul logicii în informatică . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

II. Logica predicatelor 15

2. Sintaxa logicii predicatelor de ordinul întâi 172.1. Expresiile logicii predicatelor de ordinul întâi . . . . . . . . . . . . . . . . 172.2. Parcurgerea expresiilor logicii predicatelor de ordinul întâi . . . . . . . . . 20

2.2.1. Recunoaşterea expresiilor logicii predicatelor folosind definiţia sin-taxei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2.2. Recunoaşterea şi parcurgerea sintaxei logicii predicatelor: sintaxaabstractă . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3. Relaxarea sintaxei (I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.4. Substituţii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.5. Relaxarea sintaxei (II) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3. Semantica logicii predicatelor 383.1. Interpretare, asignare de valori variabilelor, valoarea expresiilor . . . . . . 383.2. Semantica şi substituţiile . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.3. Întrebări legate de înţelesul formulelor . . . . . . . . . . . . . . . . . . . . 43

i

Definiţii1.1. Definiţie (Problemă, soluție, context) . . . . . . . . . . . . . . . . . . . . . 31.2. Definiţie (Raţionament, proprietăţile raţionamentului) . . . . . . . . . . . 71.3. Definiţie (Limbaj) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.4. Definiţie (Sistem de raţionament) . . . . . . . . . . . . . . . . . . . . . . . 91.5. Definiţie (Logica matematică) . . . . . . . . . . . . . . . . . . . . . . . . . 91.6. Definiţie ((O) Logică) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.1. Definiţie (Vocabularul logicii de ordinul întâi) . . . . . . . . . . . . . . . . 172.2. Definiţie (Termenii logicii predicatelor de ordinul întâi) . . . . . . . . . . . 182.3. Definiţie (Simboluri dominante, subtermeni) . . . . . . . . . . . . . . . . . 182.4. Definiţie (Formulele logicii predicatelor de ordinul întâi) . . . . . . . . . . 182.5. Definiţie (Simboluri dominante, subformule) . . . . . . . . . . . . . . . . . 202.6. Definiţie (Arbori (ordonaţi)) . . . . . . . . . . . . . . . . . . . . . . . . . . 212.7. Definiţie (Sintaxa abstractă a termenilor logicii predicatelor) . . . . . . . 222.8. Definiţie (Sintaxa abstractă a formulelor logicii predicatelor) . . . . . . . . 232.9. Definiţie (Substituţie) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.10. Definiţie (Substituţie aplicată unei expresii) . . . . . . . . . . . . . . . . . 352.11. Definiţie (Compunerea substituţiilor) . . . . . . . . . . . . . . . . . . . . . 36

3.1. Definiţie (Interpretare) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.2. Definiţie (Asignare de valori variabilelor) . . . . . . . . . . . . . . . . . . . 393.3. Definiţie (Valoarea termenilor) . . . . . . . . . . . . . . . . . . . . . . . . 393.4. Definiţie (Domeniu de valori de adevăr) . . . . . . . . . . . . . . . . . . . 403.5. Definiţie (Funcţii de adevăr) . . . . . . . . . . . . . . . . . . . . . . . . . . 403.6. Definiţie (Valoarea formulelor) . . . . . . . . . . . . . . . . . . . . . . . . 403.7. Definiţie (Substituibilitate) . . . . . . . . . . . . . . . . . . . . . . . . . . 423.8. Definiţie (Validitate în logica predicatelor) . . . . . . . . . . . . . . . . . . 433.9. Definiţie (Satisfiabilitate în logica predicatelor) . . . . . . . . . . . . . . . 433.10. Definiţie (Echivalenţă logică în logica predicatelor) . . . . . . . . . . . . . 433.11. Definiţie (Consecinţă logică în logica predicatelor) . . . . . . . . . . . . . 43

1

Partea I.

Introducere

2

1. Rezolvare problemelor prin raționament

1.1. Rezolvarea de problemeDefiniţie 1.1 (Problemă, soluție, context).

O problemă este o situație în care un anume obiect sau stare sunt dorite, dar nu suntdisponibile.

O soluție a unei probleme reprezintă un mod de a face disponibile obiectul sau stareacare sunt dorite.Problemele nu apar izolate, ci mai degrabă într-un context (univers de discurs,lume de interes), care este necesar pentru ca problema să poată fi formulată şiînţeleasă.

Rezolvarea problemelor este procesul prin care lumea care conţine problema se trans-formă în lumea cu soluţie, vezi Figura 1.

■

Figura 1.: Rezolvarea de probleme: transformarea unei lumi (context, univers de discurs)cu problemă într-o lume (context, univers de discurs) cu soluție.

Definiţia 1.1 se potriveşte cu intuiţia şi experienţa noastră de zi cu zi. Suntem obișnuițicu probleme, rezolvăm probleme în fiecare zi, folosind diferite metode care ne sunt laîndemână. Tentaţia este să rezolvăm problemele cât mai rapid, cât mai direct.

Să considerăm niște exemple de probleme și soluții (directe) posibile.

3

Exemplul 1.1 (Trecerea unui râu).Să ne imaginăm un moment din zorile umanității, un (h)om(inid) (flămând) pe malul

unui râu, observând pe cealaltă parte un pom plin cu fructe. Problema este cum săajungă acolo (vezi Figura 2).

Tentaţia soluţiei directe există, impulsul este acela de a ajunge cât mai rapid la pomulcu fructe. Însă există un râu de trecut. Dacă (h)om(inid)ul nu ştie să înoate, aceas-tă încercare de a rezolva problema direct poate avea consecinţe dramatice, potenţialireversibile.

▲

Figura 2.: O problemă din lumea reală: trecerea unui râu.

Desigur, există multe soluții (evidente acum pentru noi) la problema din Exemplul 1.1.Este clar că primii oameni au ajuns la aceste soluții acumulând experiență din încercărieșuate, observând mediul, învățând (de exemplu de la animale) cum să construiascăbaraje peste râu, cum să găsească porțiuni ce pot fi trecute cu piciorul, cum să înoate,cum să improvizeze poduri doborând copaci care sunt suficient de înalți pentru a trecepeste râu. Apoi au învățat să îmbunătățească aceste soluții, dezvoltând unelte cu caresă construiască de exemplu poduri, bărci, etc.

Aceste soluții sunt parte a poveştii succesului rasei umane. Însă pentru individul dinexemplul nostru, care încearcă să ajungă la fructele de pe malul opus, această informațies-ar putea să fie cumva nefolositoare, să vină prea târziu. Aceste soluţii menţionate maisus au fost dezvoltate într-un interval de timp foarte lung (de generaţii).

Acest mod de abordare a problemei, direct, în universul de discurs, în esență „încercareși eșec”, poate fi:

4

• consumator de timp: găsirea soluțiilor ia mult timp (generații),

• consumator de resurse: fiecare încercare necesită comiterea unor resurse semnifi-cative,

• potențial ireversibil: resursele comise pot fi irosite în caz de eşec (mai mult, uneorichiar cel care încearcă rezolvarea directă a problemelor poate suferi – de exemplu,ce se poate întâmpla dacă (h)om(inid)ul din Exemplul 1.1 nu ştie să înoate?).

Bineînțeles, metoda directă de rezolvare a problemelor nu trebuie ignorată. Este oabordare care are succes (este probabil ceea ce numim evoluție). Deși s-ar putea să nu-iservească celui din povestea noastră care încearcă să treacă râul, umanitatea a evoluat șiacum este într-o poziție să rezolve (ușor) astfel de probleme, inclusiv datorită experiențeiindividului respectiv.

Există însă un mod mai eficient de a rezolva probleme?

Exemplul 1.2 (Rezolvarea de probleme prin cutii negre).În lumea modernă există o presiune masivă pentru a rezolva probleme rapid și cât mai

direct posibil. Pentru a face asta, suntem obișnuiți să folosim diverse unelte și servicii,cutii negre: avem o aplicație pentru orice, alunecăm degetul pe ecranul unui dispozitivmobil și ca prin minune, avem soluția (pizza online ar rezolva problema (h)om(inid)uluidin Exemplul 1.1). Aproape nimeni nu mai are răbdare dacă soluția nu este disponibilăinstant.

▲Această metodă bazată pe tehnologie este:

• rapidă: în concordanță cu cerințele lumii moderne,

• (relativ) ieftină: din ce în ce mai mult ne așteptăm ca aceste cutii negre să fiedisponibile (dar observați că acest tip de așteptări poate fi considerat o poziție deprivilegiu, și în general cutiile negre nu sunt atât de răspândite precum ar părea),

• opacă: soluțiile sunt obținute într-un mod care pare aproape magic, fără să ne peseîn ce mod și fără să înțelegem în ce mod, fără a avea control asupra procesului.

Evident, în multe situaţii nu este necesar să se înţeleagă soluţia atât timp cât proble-ma este rezolvată. Cu toate acestea, sunt numeroase probleme pentru care verificareasoluţiei este importantă, chiar esenţială. Există situaţii critice în care trebuie să ne asi-gurăm nu numai că găsim soluţia, dar şi că aceasta are anumite proprietăţi, care pot fistabilite numai înţelegând modul în care această soluţie poate fi găsită/construită, etc.În plus, aceste cutii negre sunt construite de cineva. Aceştia, din ce în ce mai mult, suntprofesioniştii în informatică (din moment ce prin natura lor, aceste cutii magice conţinşi funcţionează pe baza „sofware”-ului).

Întrebarea rămâne: avem un mod mai eficient de a rezolva probleme într-un mod carene permite menținerea controlului asupra acestui proces?

5

1.2. Rezolvarea problemelor prin raționamentRăspunsul este afirmativ. Există o metodă prin care se pot rezolva problemele într-un mod eficient, menținând controlul asupra procesului, în principiu disponibilă oricui.Aceasta este rezolvarea de probleme bazată pe raționament, și funcționează în modulurmător, vezi Figura 3:

1. Observație: folosind simțurile, ajutate de instrumente (microscop, telescop, rigle,etc), se construiește un model intelectual al universului de discurs (o imagine inte-lectuală), ce conţine o imagine a problemei de rezolvat.

2. Raționament: modelul care conține o imagine a problemei de rezolvat este trans-format prin raționament într-un model care conține soluția. Suportul acestui paseste mintea, ajutată de instrumente (hârtie și creion, calculatoare, etc).

3. Acțiune: odată soluția găsită în model, aceasta poate fi implementată în universulde discurs folosind membrele ajutate de instrumente (ciocan, roboți, buldozere,etc).

Figura 3.: Rezolvarea de probleme prin raţionament: prin observaţie, se construieşte unmodel al universului de discurs care conţine problema, care este transformatprin raţionament într-un model cu soluţie, care apoi este implementată înuniversul de discurs.

Aparent, tot ce aduce nou această schemă este faptul că înainte de a încerca o abor-dare directă pentru rezolvarea problemei, este bine „să te gândeşti”, oferind un filtrupentru eliminarea celor mai proaste abordări. În Exemplul 1.1, dacă nu ştie să înoate,(h)om(ninid)ul „se poate gândi” că această abordare directă este una proastă.

Mai mult, într-un anumit sens, schema din Figura 3 se potriveşte unei game largi deabordări, care include printre altele:

6

Abordarea magică: (h)om(ninid)ul găseşte şamanul tribului, îi explică situaţia, acestaîşi creează o imagine intelectuală a problemei, şi printr-un ritual care poate implicaun zbor cosmic, întâlnirea cu şamanii care i-au precedat, etc, acesta „vede” soluţia.

Cutii negre: aplicaţiile, cutiile negre bazate pe tehnologie, necesită în fapt un nivel deabstractizare, modelare a problemelor pe care le rezolvă. Interfeţele, reprezentareaproblemelor la nivelul cutiilor negre (aplicaţii, dispozitive) presupun în fapt unproces de modelare.

Ambele abordări funcţionează (mai mult sau mai puţin subiectiv), sunt abordări valide(din anumite puncte de vedere), utilizate pentru rezolvarea de probleme. Există, însă, înambele cazuri un pas „magic” prin care se obţine soluţia, un pas ce nu poate fi explicatsau controlat de către beneficiarul soluţiei sau chiar de către cei care generează/descoperăsoluţia.

În mod esenţial, abordarea bazată pe raţionament elimină necunoscutul şi oferă controlcelor care folosesc acest instrument pentru verificarea şi validarea soluţiei. În continuarevom descrie proprietăţile raţionamentului, ce diferenţiază această abordare de altele, deexemplu de cele „magice”.

Definiţie 1.2 (Raţionament, proprietăţile raţionamentului).Raţionamentul este procesul prin care se transformă un model intelectual ce conţine oproblemă într-un model intelectual, caracterizat de următoarele proprietăţi:

1. Abstract: Raționamentul operează într-un model intelectual. După ce modelul esteconstruit, nu mai există legătură cu lumea (universul) pe care o descrie. Aceastăproprietate asigură:

• puterea raționamentului: este reversibil, rapid, ieftin (totul se întâmplă înmintea noastră),

• limitările raționamentului: modelele construite pot fi inadecvate,concentrându-se pe anumite aspecte ale universului de discurs, dar ignorândaltele (și se pierde legătura cu realitatea). Această situație a dus de fapt laseria de crize pe care le parcurge omenirea: ecologică, tehnologică, economică,socială.

2. Verificabil: Raționamentul se desfășoară în pași mici, pe care toată lumea îi poateefectua. Aceşti paşi au o natură „deterministă”, în sensul că n pas de raționamentaplicat într-o anumită situație va produce întotdeauna aceleași modificări în model,indiferent cine aplică acel pas. Acești pași de raționament se vor numi regulide raționament, și mulțimea de reguli de raționament va forma sistemul deraționament (împreună cu o descriere a modului în care se construiește o soluțieși cum arată aceasta).

3. Corect: Raționamentul transportă „adevărul”. Modelul intelectual conţine imagini(intelectuale) ale unor obiecte şi situaţii din universul de discurs. În consecinţă,acestea sunt „adevărate”. Prin aplicarea regulilor de raţionament, modelul iniţialse modifică, prin adăugarea de noi imagini (de obiecte sau situaţii din universul

7

de discurs). Aceste noi imagini trebuie să aibă un corespondent în universul dediscurs, adică atunci când „ne întoarcem”, imaginile (noi) trebuie să corespundăunor obiecte sau situaţii care pot fi construite/au loc în universul de discurs. Altfelspus, când pornim de la ceva „adevărat”, prin aplicarea unui pas de raționamenttrebuie să obținem ceva ce este tot „adevărat”. Prin raţionament nu putem construiobiecte sau situaţii care nu există în universul de discurs.

4. General: Prin raţionament trebuie să putem rezolva clase întregi de probleme, unnumăr potenţial infinit.

■Metoda de rezolvare a problemelor bazată pe raţionament stă la baza dezvoltării

tehnologice a societăţii occidentale în ultimile câteva sute de ani. Această dezvoltarea fost una extrem de rapidă, iar ritmul ei accelerează. În acest sens, rezolvarea bazatăpe raţionament este o metodă extrem de eficientă, un instrument esenţial în abordareaproblemelor în general, şi mai ales într-un domeniu atât de dinamic şi competitiv, cumeste informatica.

Observaţie (Raţionamentul în contextul domeniilor ştiinţifice). Schema din Figura 3oferă şi un tablou al modului în care domeniile ştiinţifice corespund rezolvării problemelorprin raţionament:

• Faza de observație corespunde științelor naturale – fizică, chimie, biologie, şti-inţelor pământului, astronomie, etc. – ce au ca scop înţelegerea lumii, construireade imagini (modele) adecvate, ce să explice diferitele aspecte ale acesteia.

• Faza de raţionament corespunde matematicii – ştiinţa care se ocupă cu rezolvareade probleme în modele abstracte (inclusiv informatica – automatizarea, pe câtposibil, a acestui proces de rezolvare de probleme).

• Faza de acţiune corespunde ştiinţelor inginereşti – care se ocupă cu aplicarea şiimplementarea cunoştinţelor şi soluţiilor dezvoltate în cadrul ştiinţelor naturale şimatematicii.

▲În mod necesar, acest tablou este unul extrem de simplificat, domeniile menţionate

sunt extrem de vaste şi complexe, la fel şi modul în care acestea interacţionează. În-să poate reprezenta un punct de plecare în înţelegerea modului în care funcţioneazăraţionamentul şi rolul acestuia (şi al matematicii) în aceste domenii ştiinţifice.

1.3. Limbajul ca suport al raționamentuluiSă ne întoarcem la Exemplul 1.1. Ce se întâmplă dacă persoana care stă pe malul râuluirezolvă problema traversării (prin raționament)? Dacă va dori să transmită celorlalțidin trib care este soluția, astfel încât să o implementeze împreună? Soluția va trebuicomunicată.

8

Pentru asta avem nevoie de un limbaj. Toate fazele rezolvării problemei trebuie săpoată fi exprimate într-un limbaj, pentru a fi comunicate: modelul, problema, regulilede raţionament şi modul cum sunt aplicate pentru a găsi soluţia (şi cum arată aceasta).

Drept consecință, limbajul este suportul raționamentului:

• modelele intelectuale sunt construite din expresii ale unui limbaj,

• regulile de raționament iau expresii din model și produc expresii noi (modificândmodelul).

Definiţie 1.3 (Limbaj). Un limbaj (care urmează să fie folosit pentru a construimodele și a rezolva probleme) este definit de:

• sintaxa limbajului care cuprinde:– vocabularul – simbolurile folosite pentru a forma expresii,– regulile după care sunt formate expresiile care aparțin limbajului,

• semantica limbajului – înțelesul expresiilor, modul în care expresiile descriuobiecte și realități în universul de discurs.

■Observaţie (Limbajul descrie abordările directe). De notat că odată ce avem la dis-poziţie sintaxa şi semantica unui limbaj, putem descrie abordările directe, vezi Figura 1.De exemplu, putem descrie istoria abordărilor directe din Exemplul 1.1, adică putemdescrie şi arhiva experienţele, încercările, eşecurile. ▲

Pentru a rezolva probleme prin raţionament, limbajul singur nu este suficient.

Definiţie 1.4 (Sistem de raţionament). Fiind dat un limbaj (sintaxa, semantica), unsistem de raţionament constă în descrierea:

• problemei,

• paşilor de raţionament,

• modului în care paşii de raţionament sunt aplicaţi pentru a construi soluţia pro-blemei.

■

1.4. LogicaLimbajele, sintaxa şi semantica lor, sistemele de raţionament asociate, sunt studiate încadrul logicii.

Definiţie 1.5 (Logica matematică). Logica (logica matematică, logica simbolică, me-tamatematica) este un domeniu științific care se ocupă cu studiul sistemelor de ra-ţionament, prin aplicarea metodei matematice asupra problemei raţionamentului. ■

9

Observaţie. (Terminologie: logică, logică computaţională) Folosim în aceste paginitermenul logică pentru a desemna logica matematică, aşa cum este definită aceasta maisus.

Pe lângă domeniul matematic, logica este studiată în cadrul filozofiei, într-un sensmai larg (studiul modului în care funcţionează gândirea şi modul cum se aplică aceastaproblemelor filozofice), care are părţi semnificative în comun cu logica matematică.

Există, bineînţeles, şi logica din viaţa de zi cu zi – termen care în principiu se referăla un anumit mod („raţional”) de a face lucrurile.

Nu în ultimul rând, logica computaţională reprezintă aspectul din logică ce se referăla automatizarea raţionamentului, sau raţionament despre calcul mecanic (automat).Vom atinge aceste aspecte într-o anumită măsură, dar vom urmări şi modul în carelogica (matematică) poate fi folosită ca un instrument practic de înţelegere, explorare,acumulare eficientă de cunoştinţe în informatică, pentru studenţi. ▲

În afară de logică drept domeniu de studiu, vom considera o logică în sensul următor:

Definiţie 1.6 ((O) Logică). O logică este formată din:

• un limbaj (sintaxă, semantică),

• un model,

• un sistem de raţionament, incluzând reguli şi modul de aranjare a acestora într-osoluţie,

• o mulţime de proprietăţi (demonstrate) legate de sistemul de raţionament.

■

1.5. Probleme abordate de logica matematicăVom prezenta, în continuare, la un nivel informal, câteva dintre problemele abordate delogica matematică. Scopul acestei prezentări este să ofere o privire de ansamblu asupratipului de rezultate, să prezinte câteva din implicaţiile acestora la nivel „filozofic” şipractic.

1.5.1. Limbaje: proprietăţi, clasificareUn prim pas pentru a putea descrie o problemă şi soluţia acesteia este alegerea unuilimbaj potrivit. Suficient de expresiv pentru a putea descrie problema şi soluţia, dar nuexcesiv de complicat.

Există mai multe criterii după care pot fi clasificate limbajele:

Limbaje universale și limbaje speciale:Limbajele universale sunt limbaje care sunt suficient de puternice pentru a descrieorice univers de discurs, și pentru a exprima orice soluții la probleme (ce potfi descrise și au soluții). Un astfel de limbaj este limbajul logicii predicatelor,

10

care este universal în sensul că toată matematica (adică tot ce se poate rezolvaprin raţionament) poate fi exprimată în acest limbaj (inclusiv partea automată,algoritmică). În fapt, chiar şi o versiune restricţionată, logica predicatelor de ordinulîntâi (împreună cu aşa numita teorie a mulţimilor) este suficientă pentru a exprimatoată matematica.Limbajele speciale sunt limbaje relativ simple, și care pot descrie doar universurilimitate. Motivul pentru care aceste limbaje sunt de preferat (în cazul în carepot exprima problema de interes şi soluţia acesteia), este tocmai simplitatea, careoferă proprietăţi mai bune, care în general nu sunt disponibile pentru limbaje maicomplicate, după cum vom discuta mai jos. Exemple de limbaje speciale sunt logicapropozițională, limbajul circuitelor cu comutare, geometria solidă constructivă.

Limbaje descriptive și limbaje algoritmiceLimbajele descriptive sunt folosite pentru a descrie obiecte, situații, cunoștințe. Unexemplu îl reprezintă limbajul matematicii „tradiționale” sau „pure”. Un exemplude folosire este efortul colectivului Bourbaki de a construi sistematic cunoştinţelematematice, cu accent pus pe rigoare şi formalism vezi [Bou04].Limbajele algoritmice sunt folosite pentru a descrie acțiuni, pași pentru rezolvareaproblemelor. Exemple sunt limbajele de programare.De notat însă că aceste aspecte nu ar trebui separate. Folosirea celor două aspecte,descriptiv și algoritmic, în același limbaj îi mărește puterea din punct de vederepractic. Cele două aspecte sunt fețe diferite ale aceleiași monede.

Limbaje naturale și limbaje formaleLimbajele naturale sunt limbaje învățate în context (aflându-ne între cei care folo-sesc un limbaj, începem să recunoaștem și să învățăm sintaxa, semantica, sistemulde raționament, într-o manieră evoluționară).Pentru limbaje formale, vocabularul, sintaxa, semantica și sistemul de raționamentsunt descrise și definite precis, și apoi pot fi folosite conform definiției.De exemplu, putem spune că în mare măsură oamenii învăță matematica în con-text, și numai mai târziu aceasta devine un limbaj formal.

Metalimbaj și limbaj obiectUn metalimbaj este un limbaj care se folosește pentru a defini un alt limbaj (numitlimbajul obiect) și pentru a raționa despre proprietățile acestuia.Să observăm că aceștia nu sunt termeni absoluți, un limbaj poate juca rolul unuimetalimbaj (vom folosi limbajul naiv al teoriei mulțimilor pentru a defini logicilepe care le studiem şi vom folosi raţionamentul pe care l-am învăţat ), iar mai târziuacelași limbaj poate fi definit formal (jucând rolul unui limbaj obiect).

11

1.5.2. Model: consistenţăEste modelul (descrierea universului de discurs) consistent, liber de contradicţii?

Observaţie (Specificarea modelului). În matematică, forma în care se specifică mode-lul universului de discurs este luată de axiome. Rolul axiomelor este acela de a descriecomportamentul obiectelor de interes, noţiunile de bază.

În particular, axiomele sunt afirmaţii considerate adevărate, dar justificarea acestuifapt vine tocmai din faptul că acestea descriu universul de discurs, comportamentul şirelaţiile dintre obiectele acestui univers. ▲Exemplul 1.3 (Paradoxul lui Russell). Să considerăm o axiomă (afirmaţie, parte amodelului), care descrie o proprietate a mulţimilor. Intuitiv:

Pentru orice „proprietate” P , există „mulţimea” tuturor obiectelor x care posedă pro-prietatea P .

Mai exact, pentru orice proprietate P :„există o mulţime M astfel încât pentru orice x (x ∈M dacă şi numai dacă P )”, unde

M este o variabilă.Din moment ce funcţionează pentru orice proprietate, să considerăm proprietatea x ̸∈

x: „există o mulţime M astfel încât pentru orice x (x ∈M dacă şi numai dacă x ̸∈ x)”Din moment ce există o mulţime, fie aceasta M0 (M0 nu mai este o variabilă, este o

constantă): „pentru orice x (x ∈M dacă şi numai dacă x ̸∈ x)”Din moment ce afirmaţia este adevărată pentru toţi x, este adevărată şi pentru x := M :

„(M ∈M dacă şi numai dacă M ̸∈M)”, ceea ce este o contradicţie.▲

Acest exemplu (faimos), vezi [Rus03], ne arată cum o axiomă intuitiv rezonabilă poateduce la inconsistenţe în model.

Axioma poate fi „reparată” pentru a evita paradoxul:Pentru orice proprietate P în care apare (liberă) variabila x şi orice variabilă B care

nu apare liberă în P :„pentru orice B există M astfel încât pentru orice x (x ∈M dacă şi numai dacă (x ∈

B şi P ))”.

1.5.3. Corectitudinea regulilor de raţionamentSunt regulile de raţionament corecte, „transportă adevărul”? Există două abordări po-sibile pentru stabilirea acestei proprietăţi:

• abordarea evoluţionară: anumite reguli de raţionament sunt corecte pentru că îndecursul timpurilor acestea au fost observate şi verificate în numeroase instanţe decătre numeroşi observatori şi au fost acceptate ca fiind corecte.

• abordarea formală: presupune folosirea unui metalimbaj şi a unui sistem de raţiona-ment corespunzător acestuia pentru a stabili corectitudinea regulilor de inferenţă.

12

1.5.4. Completitudinea regulilor de raţionamentSe pot rezolva într-un sistem de raţionament toate problemele care au o soluţie, este acelsistem de raţionament suficient de puternic? Gödel a demonstrat în [Göd30] că logicapredicatelor are această proprietate: orice afirmaţie „adevărată” are o demonstraţie însistemul de raţionament al logicii predicatelor (de ordinul întâi).

Pentru limbaje (logici) mai simple (de exemplu, logica propoziţiilor), în general aceastăproprietate este uşor de stabilit.

1.5.5. Limitele raţionamentului: incompletitudine, nedecidabilitateExistă însă rezultate care arată că raţionamentul are limite. Gödel a arătat că pentrusituaţia în care modelul este consistent şi conţine aritmetică (numere naturale), atunciexistă afirmaţii exprimate în limbajul respectiv (logica predicatelor de ordinul întâi) carenu pot fi nici demonstrate nici respinse, vezi [Göd31].

O altă întrebare importantă este decidabilitatea unei probleme: pentru o problemădată, există o metodă mecanică (algoritm) prin care să se ajungă la un răspuns „da”sau „nu”, adică să se decidă dacă problema are soluţie, sau nu are soluţie. Pentru logicapredicatelor, Church, vezi [Chu36], şi Turing, vezi [Tur37], au arătat că acest lucru nueste posibil. De exemplu, problema opririi unei maşini de calcul – dacă pentruorice date de intrare o maşină de calcul se va opri şi va da un răspuns sau calculează lanesfârşit – este în general nedecidabilă.

Aceste rezultate aparent negatived ne spun că raţionamentul matematic are limite, şică pentru a depăşi limitele este nevoie de ingeniozitatea umană.

Totodată, în contextul acestor rezultate, efortul este de a identifica cazuri (limbaje,modele, sisteme de raţionament) pentru care aceste proprietăţi au loc.

În general, limbajele speciale sunt atractive datorită faptului că au proprietăţi cadecidabilitate, adică pentru orice problemă fie se găseşte o soluţie, fie se determină că nuare soluţie. Acest lucru se poate face automat, printr-un algoritm (raţionamentul esteautomat).

1.5.6. ComplexitateDacă o problemă se poate rezolva automat, o problemă importantă este complexitateasoluţiei. Există clase de probleme pentru care complexitatea este prea mare, adică timpulşi/sau spaţiul de memorie necesare sunt prea mari pentru a rezolva probleme în practică.Acest aspect este foarte important. Oricât de mare ar fi puterea de calcul, aceasta poatefi uşor depăşită de complexitatea unor probleme. Există o graniţă de la care calcululdevine nepractic.

1.6. Rolul logicii în informatică[To do.]

13

DeclaraţieAutorul acestor note de curs a învăţat despre logică, rolul acesteia în rezolvarea deprobleme, mecanismele prin care funcţionează, etc., de la îndrumătorul său, Bruno Bu-chberger. Acest prim capitol urmează structura din notele de curs (nepublicate) ale luiBuchberger, vezi [Buc91].

14

Partea II.

Logica predicatelor

15

Logica predicatelor de ordinul întâi: sintaxăşi semanticăLogica predicatelor este limbajul matematicii. Chiar şi o versiune restrânsă pe care ovom discuta aici – logica predicatelor de ordinul întâi – este suficientă (împreună cuteoria mulţimilor) pentru a exprima tot ce se poate exprima în matematică.

Totodată, este într-un anumit sens cel mai bine înţeleasă – munca de fundamentare amatematicii (punerea matematicii pe bază solide) în cea mai mare măsură a fost făcutăîn această logică.

Mai mult, logica predicatelor de ordinul întâi poate servi ca un cadru general pentruinformatică (matematică, raţionament automat).

În ceea ce urmează, vom introduce limbajul logicii predicatelor de ordinul întâi. Vomprezenta sintaxa şi semantica, vom vedea că a rezolva probleme direct folosind logicapredicatelor este nepractic.

16

2. Sintaxa logicii predicatelor de ordinulîntâi

Rolul unui limbaj (în particular al limbajului considerat aici) este să descrie un universde interes. Pentru a forma expresii avem nevoie de simboluri, care vor juca diferite roluriîn expresiile limbajului.

2.1. Expresiile logicii predicatelor de ordinul întâiDefiniţie 2.1 (Vocabularul logicii de ordinul întâi). Simbolurile limbajului logicii deordinul întâi sunt:

• V - mulţimea (numărabilă) de variabile obiect. Faptul că mulţimea este numă-rabilă ne asigură că putem lua o variabilă nouă de câte ori este nevoie.Notaţie: Prin convenţie, variabilele vor fi notate cu litere mici, de la sfârşitulalfabetului, eventual folosind indecşi: x, y, z, x1, x2, y5, etc.

• L - mulţimea simbolurilor limbajului (signatura), care conţine:– F - simbolurile funcţionale (nume de funcţii): nume pentru funcţii

din universul de interes. Pentru fiecare astfel de nume, vom ataşa aritatea,numărul de argumente a funcţiei descrise de fiecare nume.

– P - simbolurile predicative (predicate, nume de relaţii): nume pentrurelaţii din universul de interes. Pentru fiecare astfel de predicat vom ataşaaritatea, numărul de argumente din relaţia descrisă de predicatul respectiv.

– C - simboluri constante (nume de constante): nume pentru obiecte dinuniversul de discurs.

• Simboluri rezervate:– (, ) – paranteze şi delimitator (virgula)– conectori logici: ¬ (negaţia), ∧ (conjuncţia), ∨ (disjuncţia), ⇒ (implica-

ţia), ⇔ (echivalenţa),– cuantificatori: ∀ (cuantificatorul universal), ∃ (cuantificatorul existenţial).

■Exemplul 2.1 (Simboluri ale unui limbaj). Vom considera următoarea signatură L aunui limbaj:

17

F ={f/2, g/1, h/3,+/2, !/1

},

unde h/3 indică faptul că funcţia pentru care am ales numele h are aritate 3 (3 argu-mente).

P ={P/2,≤/2, prim/1, par/1

},

unde par/2 indică faptul că predicatul pentru care am ales numele par are aritate 2 (2argumente).

C = {a, b, 0, 12} .

▲Observaţie (constantele sunt funcţii). Tehnic, simbolurile constante sunt la fel cusimbolurile funcţionale de aritate 0. Intuitiv, o funcţie „returnează” un obiect „în funcţie”de argumentele sale, adică modificând argumentele, se modifică rezultatul. Dacă funcţianu are argumente, atunci rezultatul nu poate fi influenţat, aşadar este neschimbat. Atuncifuncţia (cu 0 argumente) se poate identifica cu valoarea pe care o returnează. ▲

Primul tip de expresii în logica predicatelor de ordinul întâi sunt termenii, care descriuobiecte din universul de discurs.

Definiţie 2.2 (Termenii logicii predicatelor de ordinul întâi). Fie V mulţimea de va-riabile, L mulţimea simbolurilor (signatura) unui limbaj al predicatelor de ordinul întâi.Mulţimea termenilor peste L şi mulţimea de variabile V, notată T(L,V) estedefinită după cum urmează:

• Dacă x ∈ V, atunci x ∈ T(L,V). (Variabilele sunt termeni.)

• Dacă c ∈ C, atunci c ∈ T(L,V). (Constantele sunt termeni.)

• Dacă f/n ∈ F şi t1, . . . , tn ∈ T(L,V), atunci f(t1, . . . , tn) ∈ T(L,V). (Un simbolfuncţional aplicat unui număr corespunzător – cu aritatea sa – de termeni este larândul său un termen.)

În primele două cazuri avem de-a face cu termeni simpli (variabilă, constantă), iarîn ultimul avem termeni compuşi (din simbol funcţional aplicat altor termeni).

■Definiţie 2.3 (Simboluri dominante, subtermeni). Fie f(t1, . . . , tn) ∈ T(L,V) un ter-men compus. Spunem că f este simbol dominant al termenului compus şi t1, . . . , tnsunt subtermeni. ■

Al doilea tip de expresii în logica predicatelor de ordinul întâi sunt formulele, careintuitiv descriu relaţii, situaţii din universul de discurs.

Definiţie 2.4 (Formulele logicii predicatelor de ordinul întâi). Fie V mulţimea devariabile, L mulţimea simbolurilor (signatura) unui limbaj al predicatelor de ordinul

18

întâi. Mulţimea formulelor peste L şi mulţimea de variabile V, notată F(L,V)este definită după cum urmează:

• Dacă P/n ∈ P şi t1, . . . , tn ∈ T(L,V), atunci P (t1, . . . , tn) ∈ F(L,V). (Un predicataplicat unui număr corespunzător – cu aritatea sa – de termeni este o formulă,numită formulă atomică).

• Dacă F,G ∈ F(L,V), atunci:

(¬F ) ∈ F(L,V).Negaţia unei formule este o formulă, se citeşte „negaţia lui F” sau „nuF”.

(F ∧G) ∈ F(L,V).

Conjuncţia a două formule este o formulă, se citeşte „F şi G”.

(F ∨G) ∈ F(L,V).

Disjuncţia a două formule este o formulă, se citeşte „F sau G”.

(F ⇒ G) ∈ F(L,V).

Implicaţia a două formule este o formulă, se citeşte „F implică G” sau„dacă F atunci G”.

(F ⇔ G) ∈ F(L,V).

Echivalenţa a două formule este o formulă, se citeşte „F echivalent cuG” sau „F dacă şi numai dacă G”.

Aceste formule, formate din alte formule legate prin conectori logici, se cheamăformule compuse.

• Dacă x ∈ V şi F ∈ F(L,V), atunci

∀xF ∈ F(L,V),

∃xF ∈ F(L,V).

Aceste formule formate dintr-un cuantificator, o variabilă şi o formulă se numescformule cuantificate, respectiv formula cuantificată universal şi formulacuantificată existenţial.În ambele cazuri, x se zice că este variabilă legată de cuantificator (universal,respectiv existenţial), în cadrul lui F. Aşadar, cadrul unei variabile legate estelocul, formula în care aceasta apare legată.O variabilă care nu este legată se cheamă variabilă liberă.

19

■Definiţie 2.5 (Simboluri dominante, subformule). Considerăm formulele logicii pre-dicatelor de ordinul întâi, F(L,V):

• Pentru formule atomice P (t1, . . . , tn), P este simbolul dominant şi t1, . . . , tnsunt subtermeni.

• Pentru formulele compuse (¬F ), (F ∧ G), (F ∨ G), (F ⇒ G), (F ⇔ G), simbo-lurile dominante sunt conectorii logici, respectiv ¬,∧,∨,⇒,⇔, iar F,G suntsubformule.

■

2.2. Parcurgerea expresiilor logicii predicatelor de ordinul întâiDefiniţiile 2.2 şi 2.4 oferă instrumentele pentru a recunoaşte expresiile logicii de ordinulîntâi. În continuare vom investiga cum se pot recunoaşte şi parcurge expresiile logiciipredicatelor.

2.2.1. Recunoaşterea expresiilor logicii predicatelor folosind definiţia sintaxeiExemplul 2.2 (Recunoaşterea expresiilor folosind definiţia). Considerăm expresia

(P (x, y) ∧ ∀xP (f(a), x)),

unde x, y ∈ V, P/2 ∈ P, f/1 ∈ F , şi a ∈ C.Vom aplica definiţia într-o manieră „top-down” (de sus în jos), identificând simbolul

dominant, şi verificând în ce măsură componentele se conformează definiţiei.Pentru

(P (x, y)∧∀xP (f(a), x)) ,

simbolul dominant este conjuncţia (∧, subliniată în expresia de mai sus), expresia începeşi se termină cu paranteze, deci conform Definiţiei 2.4, trebuie să verificăm că:

(a) P (x, y) este formulă. Acest lucru se întâmplă, conform definiţiei este o formulăatomică, un predicat binar (P ) aplicat la doi termeni, x respectiv y (care suntvariabile, deci termeni, conform Definiţiei 2.2).

(b) ∀xP (f(a), x)) este formulă. Simbolul dominant este ∀ (subliniat în formulă), urmatde o variabilă (x), deci conform definiţiei, trebuie să verificăm că P (f(a), x) esteformulă. Acest lucru se întâmplă, conform definiţiei este o formulă atomică, unpreficat binar (P ) este aplicat la doi termeni, f(x), un termen compus (simbolulfuncţional f aplicat termenului constantă a, şi variabilei x).

20

Aşadar, conform definiţiei, expresia este o conjuncţie, formulă compusă în logica pre-dicatelor de ordinul întâi.

▲Observaţie (Subitare). De notat că în Exemplul 2.2 fiecare pas este justificat, aşadaravem o soluţie acceptabilă (în sensul discutat în Capitolul 1) pentru problema propusă.Cu toate acestea, metoda conţine ceea ce pare a fi un pas „mare”: identificarea simboluluidominant. În fiecare caz, acesta este identificat imediat, fără a indica explicit cum amfăcut asta. Deşi ar putea părea simplu, acest pas poate să nu fie verificabil pentru oricine(mai ales pentru un program).

Oamenii au capacitatea de a identifica instant (fără a avea nevoie de a parcurge fiecarecomponentă) structuri simple. Acest fenomen se cheamă subitare (vezi [KLRV49]).

Dar această metodă nu scalează. Dacă expresia este una mai complicată, atuncieste posibil să nu putem identifica imediat simbolul dominant. Mai mult, chiar pentrustructuri simple, simbolul dominant nu poate fi identificat de un program fără a parcurgesimbolurile expresiei.

Avem nevoie, aşadar, pentru aceste situaţii, de o metodă în care structura expresieiparcurse este identificată pas cu pas.

▲

2.2.2. Recunoaşterea şi parcurgerea sintaxei logicii predicatelor: sintaxaabstractă

În cele ce urmează vom prezenta o metodă prin care şirul de simboluri va fi parcurs de lastânga la dreapta şi pe măsură ce analizăm fiecare simbol, vom construi sintaxa abs-tractă - o reprezentare „internă”, o structură de date care ne va permite să manipulămmai eficient expresia, odată construită.

Pentru reprezentarea internă a expresiilor logicii predicatelor vom folosi arbori, carevor fi definiţi informal.

Definiţie 2.6 (Arbori (ordonaţi)). Un arbore ordonat este definit în modul următor:

• arborele vid,

• arborele nevid, format dintr-un nod rădăcină şi o listă (posibil vidă) de su-barbori.

Fiecare nod care nu este rădăcină un singur nod părinte. Nodurile (în afară denodul răđacină) sunt conectate prin muchii la nodurile părinte corespunzătoare.

Nodurile care nu sunt noduri părinte se cheamă noduri frunză.Fiecare nod al unui arbore conţine informaţii (de exemplu obiecte de anumit tip). ■

Exemplul 2.3 (Arbori). Mai jos, vom considera că nodurile arborilor ilustraţi conţinnumere naturale.

• arbore cu un singur nod (rădăcină):

21

1

• arbore cu mai multe noduri:

1

6

117

9

10

8

2

543

Vom folosi o reprezentare generică pentru un arbore cu n subarbori, vezi Figura 4.Fiecare subarbore este la rândul său un arbore.

r

subarboren· · ·subarbore1

Figura 4.: Un arbore cu rădăcina r şi n subarbori.

▲În continuare, vom folosi arborii pentru a reprezenta expresiile logicii predicatelor.

Vom numi aceşti arbori sintaxa abstractă, sau arbori sintactici pentru logicapredicatelor.

Definiţie 2.7 (Sintaxa abstractă a termenilor logicii predicatelor). Fie T(L,V) mulţi-mea termenilor peste un limbaj. Atunci sintaxa abstractă a termenilor este repre-zentată de următorii arbori:

• Pentru termenii simpli (variabile şi constante) x şi c:

22

x c

• Pentru termeni compuşi, dacă fn(t1, . . . , tn) ∈ T(L,V):

f

tn· · ·t1

■Definiţie 2.8 (Sintaxa abstractă a formulelor logicii predicatelor). Fie F(L,V) mulţi-mea formulelor peste un limbaj. Atunci sintaxa abstractă a formulelor este repre-zentată de următorii arbori:

• Pentru formule atomice, dacă P (t1, . . . , tn) ∈ F(L,V):

P

tn· · ·t1

• Pentru formule compuse (¬F ), (F□G), unde □ ∈ {∧,∨,⇒,⇔}:

¬

F

□

GF

• Pentru formule cuantificate ∀xF, ∃xF :

∀

Fx

∃

Fx

23

■Vom descrie o metodă prin care se pot recunoaşte expresiile (şi în acelaşi

timp construi arborele sintactic).Metoda de recunoaştere pe care o propunem aici va parcurge expresia simbol cu simbol.

La fiecare pas, vom avea un arbore incomplet, poziţia în acel arbore, şi o regulă bazatăpe simbolul considerat. Regula ne va spune ce adăugăm la arborele incomplet, şi la cepoziţie.

Metoda se termină cu succes când am parcurs tot şirul de caractere din expresie, şiavem un arbore sintactic complet.

În orice alt caz:

• şirul este parcurs în întregime, dar arborele corespunzător nu este complet,

• arborele este complet, dar şirul nu a fost parcurs în întregime,

• la pasul curent se adaugă un nod în arbore, care nu corespunde niciunui arboreacceptat (de Definiţiile 2.7, 2.8),

avem eşec.

Exemplul 2.4 (Recunoaşterea expresiilor logicii predicatelor şi construcţia arboreluisintactic). Pentru a ilustra această metodă, reluăm Exemplul 2.2:

(P (x, y) ∧ ∀xP (f(a), x)).

Vom numerota fiecare simbol în expresia ce trebuie parcursă:

(

1P2

(

3x4

,

5y

6)

7∧8∀9

x

10P

11(

12f

13(

14a

15)

16,

17x

18)

19)

20

Paşii algoritmului

(1): ( – paranteza deschisă înseamnă că expresia vrea să fie o formulă compusă. Avem2 variante: negaţie, sau formulă ce conţine un conector binar. Arborii incompleţicorespunzători celor 2 posibilităţi sunt:

„¬”

„F”

„□”

„F”„F”

În arborii de mai sus, folosim următoarele convenţii:

24

• dacă într-un nod sau subarbore avem ghilimele („· · · ”), acestea indică faptulcă în acel loc avem se aşteaptă următoarele, după cum urmează:

– „T”,„F”: termen, respectiv formulă (în subarbori),– „¬”, „□”: negaţie, respectiv conector binar (unul din ∧,∨,⇒,⇔),– „Q”: quantificator (unul din ∀, ∃),– „v”: variabilă.

• Un nod sau subarbore reprezentat cu linie întreruptă reprezintă poziţia înarborele incomplet, unde vom completa la pasul următor.

(2): P – este un predicat binar. Prima variantă (în care formula este o negaţie) cade,lucrăm pe varianta a doua.Prezenţa lui P indică faptul că avem nevoie de o formulă atomică, cu 2 subarbori:

„¬”

„F”

„□”

„F”P

„T”„T”

(3): ( – paranteza deschisă după P mută poziţia pe primul subarbore după al noduluice conţine P .

„□”

„F”P

„T”„T”

(4): x – este o variabilă, deci termen, exact ce se aştepta, subarborele este închis, semută poziţia la părinte.

25

„□”

„F”P

„T”x

(5): , – virgula indică faptul că ne mutăm pe următoarea ramură:

„□”

„F”P

„T”x

(6): y – este o variabilă, deci termen, exact ce se aştepta, subarborele este închis.

„□”

„F”P

yx

(7): ) – paranteza închisă, închide tot subarborele ce începe cu nodul P , poziţia se mutăla părintele acestui subarbore.

26

„□”

„F”P

yx

(8): ∧ – este un conector propoziţional binar, ceea ce era aşteptat, se completează şipoziţia se muta pe al doilea subarbore:

∧

„F”P

yx

(9): ∀ – cuantificatorul universal, vom avea nevoie de o variabilă şi de o formulă, poziţiase mută pe primul subarbore:

∧

∀

„F”„v”

P

yx

(10): x – este o variabilă, ceea ce era aşteptat, se închide subarborele, trecem la urmă-torul:

27

∧

∀

„F”x

P

yx

(11): P – este predicat binar, vrem formulă atomică, cu două subramuri, fiecare cores-punzând unui termen:

∧

∀

P

„T”„T”

x

P

yx

(12): ( – paranteză deschisă, trecem la primul subarbore:

∧

∀

P

„T”„T”

x

P

yx

28

(13): f este o funcţie unară (ok, aveam nevoie de un termen), construim o ramură nouă,unde avem nevoie de un termen:

∧

∀

P

„T”f

„T”

x

P

yx

(14): ( – paranteză deschisă, ne mutăm pe subarbore:

∧

∀

P

„T”f

„T”

x

P

yx

(15): a – este o constantă, deci termen, ok, asta aşteptam:

29

∧

∀

P

„T”f

a

x

P

yx

(16): ) – paranteză închisă, am terminat cu subarborele ce începe cu f , ne mutămdeasupra:

∧

∀

P

„T”f

a

x

P

yx

(17): , – virgulă, coborâm pe următoarea ramură:

30

∧

∀

P

„T”f

a

x

P

yx

(18): x – o variabilă, deci termen, ceea ce aşteptam, se închide nodul:

∧

∀

P

xf

a

x

P

yx

(19): ) paranteză închisă, subarborele care începe la P este închis, trecem la părinte:

31

∧

∀

P

xf

a

x

P

yx

(20): ) paranteză închisă, subarborele care începe la ∧ este închis, trecem la părinte (dar∧ este rădăcină, deci am terminat, avem arborele sintactic, avem o expresie în logicapredicatelor):

∧

∀

P

xf

a

x

P

yx

▲Observaţie (Cazurile cu eşec). În cazul unui eşec, metoda descrisă mai sus oferă şimotivul pentru eşec. Acesta se găseşte la pasul la care se produce eşecul. De exemplu,dacă în expresia de mai sus, P ar fi un simbol funcţional binar (şi nu un predicat),

32

la pasul 2 inserăm un simbol funcţional în nodul curent, ceea ce ar contrazice definiţiaformulelor compuse.

▲

2.3. Relaxarea sintaxei (I)Metodade parcurgere şi recunoaştere a expresiilor logicii predicatelor prezentată în se-cţiunea anterioară funcţionează pentru că simbolurile funcţionale şi predicative se punînaintea argumentelor. În practică, vrem să scriem lucruri ca x + y, x ≤ y, unde +,≤sunt respectiv un simbol funcţional şi un predicat. Acest mod de a scrie lucrurile nu esteacceptat conform Definiţiilor 2.2, 2.4. Ar trebui să avem +(x, y),≤ (x, y), respectiv.

Dar intenţia este să folosim logica predicatelor ca un limbaj practic. În acest sens, deacum înainte vom accepta o relaxare a sintaxei care să permită folosirea simbolurilorîn modul indicat mai sus. Însă acest lucru trebuie făcut tinând cont de anumite aspectece vor fi menţionate în continuare, pentru a evita ambiguităţile.

Poziţia simbolurilorSimbolurile funcţionale sau predicative pot fi plasate în următoarele poziţii:

Prefix: simbolurile funcţionale sau predicative sunt plasate înaintea argumentelor (aşase folosesc simbolurile în Definiţiile 2.2, 2.4).

Infix: simbolurile funcţionale sau predicative sunt plasate între argumente. De obiceiacest mod de scriere este folosit pentru simboluri de funcţii şi predicate binare:x+ y, x ≤ y. Un caz particular de simbol infix este cel din expresia xy. Simbolulcorespunzător este □□, unde □ reprezintă poziţiile argumentelor.

Postfix: simbolurile funcţionale sau predicative sunt plasate după argumente. De obicei,acest mod de scriere este folosit pentru simboluri unare: x! sau x este prim, unde,tradiţional ! este funcţia factorial, iar este prim este un predicat unar.

Altele (notaţii 2D): argumentele sunt plasate în poziţii nestandard, bidimensională. Deexemplu: x

y , n√x. De remarcat că în aceste cazuri, simbolurile funcţionale cores-

punzătoare sunt □□ , □√□ (sau n

√□, dacă considerăm funcţie unară).

AsociativitateaDacă scriem (3+4)+5 sau 3+(4+5), expresiile respective, în interpretarea tradiţională,denotă acelaşi lucru (adică + este o funcţie asociativă). Însă nu acelaşi lucru se întâmplăîn cazul 8/2/2. Dacă funcţia este asociativă la stânga, (8/2)/2 înseamnă 2, pe când dacafuncţia este asociativă la dreapta, 8/(2/2) înseamnă 8. În acest caz este esenţial să seprecizeze asociativitatea. În general, pentru funcţii aritmetice, asociativitatea este lastânga (dar dacă nu este clar din context, atunci aceasta trebuie specificată).

33

De remarcat că nu toate simbolurile au proprietatea de asociativitate. De exemplu,3 ≤ 4 ≤ 2 nu are sens nici cu asociativitate la stânga, nici la dreapta.

De asemenea, conectorii logici ∧,∨ sunt asociativi (vom vedea mai târziu de ce), iar⇒ este asociativă la stânga, iar ⇔ nu este asociativă.

PrecedenţaExpresia x + yz poate fi parcursă ca x + (yz) sau (x + y)z. Care dintre cele douăelemente sunt considerate, depinde de precedenţa simbolurilor. Pentru interpretareaclasică (dacă considerăm expresia ca fiind expresie aritmetică), trebuie ca simbolul □□să aibă precedenţă mai mică (să lege mai tare) decât +.

În mod similar, pentru conectorii logici, precedenţa uzuală este următoarea:

¬, {∧,∨},⇒,⇔

(conjuncţia şi disjuncţia au aceeaşi precedenţă).

Dacă vrem să folosim expresiile logicii predicatelor în forma relaxată, trebuie specificateelementele relevante (poziţia, asociativitatea, precedenţa), pentru a evita ambiguităţile.sintaxa relaxată are avantajul că permite expresii mai compacte. În practică (de exîn sursele matematice, etc) se foloseşte sintaxa relaxată (sintaxa este definită implicit).Însă în cazul în care sunteţi nesiguri, folosiţi parantezele!

Relativ la sintax abstractă (reprezentarea sub formă de arbori sintactici), aceasta esteaceeaşi pentru sintaxa relaxată, însă modul în care se construieşte nu mai este la fel (deuşor) precum a fost în cazul sintaxei stricte.

2.4. SubstituţiiSubstituţia de termeni pentru variabile este un proces elementar prin care putem construiexpresii noi din cele existente. Vom defini conceptul de substituţie:

Definiţie 2.9 (Substituţie).O substituţie de termeni pentru variabile este o mapare

σ : V → T(L,V)

astfel încât pentru un număr finit de variabile x ∈ V avem σ(x) ̸= x.Mulţimea substituţiilor peste un limbaj va fi notată cu S(L,V) (sau S, dacă L,V

sunt clare din context).Fie σ ∈ S(L,V) o substituţie, n ∈ N, i ∈ {1, . . . , n}, şi xi ∈ V, ti ∈ T(L,V) astfel încât

σ(xi) = ti şi xi ̸= ti. Vom reprezenta substituţia σ ca o mulţime în felul următor:

σ = {x1 ← t1, . . . , xn ← tn} .

În particular, dacă n = 0, avem substituţia vidă. ■

34

Vom nota substituţiile cu litere greceşti σ, θ, λ, etc. Substituţia vidă va fi notată cu ε.Substituţiile pot fi extinse pentru a fi aplicate la termeni. Această extindere corespun-

de aplicaţiei unei substituţii unei expresii. Intuitiv, se înlocuiesc variabilele cu termeniicorespunzători specificaţi în substituţie. Această înlocuire are loc în paralel (toate va-riabilele se înlocuiesc în acelaşi timp cu termenii corespunzători). Totuşi, înlocuirea nupoate avea loc în orice condiţii. Următoarea definiţie specifică modul în care se facesubstituţia.

Definiţie 2.10 (Substituţie aplicată unei expresii). Fie σ = {x1, . . . , xn} o substituţie.Aplicarea substituţiei σ unei expresii E din logica predicatelor, notată cu Eσ este definităîn modul următor:

• Pentru termeni:

– dacă x ∈ V, atunci

xσ =

{x dacă x ̸= xi, 1 ≤ i ≤ n,

xi dacă pentru un i, x = xi.

– dacă c ∈ C, atunci cσ = c.– dacă f/m ∈ F şi t1, . . . , tm ∈ T(L,V), atunci:

f(t1, . . . , tm)σ = f(t1σ, . . . , tmσ).

• Pentru formule:– Dacă P/m ∈ P şi t1, . . . , tm ∈ T(L,V), atunci:

P (t1, . . . , tm)σ = P (t1σ, . . . , tmσ).

– Dacă F,G ∈ F(L,V) atunci:

(¬F )σ = (¬Fσ),

(F ∧G)σ = (Fσ ∧Gσ),

(F ∨G)σ = (Fσ ∨Gσ),

(F ⇒ G)σ = (Fσ ⇒ Gσ),

(F ⇔ G)σ = (Fσ ⇔ Gσ).

– Dacă x ∈ V şi F ∈ F(L,V), atunci:

(∀xF )σ = ∀x(Fσ∖{x←t}

),

(∃xF )σ = ∃x(Fσ∖{x←t}

),

unde

{x← t} =

{{xi ← ti} dacă pentru uni, x = xi,

{} , altfel.

35

■Aşadar, pentru a sumariza, pentru variabila se schimbă dacă coincide cu o variabilă

ce apare în substituţie, constanta rămâne neschimbată la substituţie. Pentru termeniicompuşi, formulele atomice, formulele compuse, substituţia se face pe componente. Pen-tru formulele cuantificate, variabilele legate sunt protejate de la substituţie (substituţiamerge pe componente, dar eliminând din substituţie variabilele care sunt legate).

Exemplul 2.5 (Substituţii în logica predicatelor). Fie

σ = {x← f(y, z), y ← z, z ← a} .

Atunci:

f(x+ y, z)σ = f((x+ y)σ, zσ) = f(xσ + yσ, zσ) = f(f(y, z) + z, a).

(P (x, y)⇒ ∀x(P (x, y) ∧Q(z)))σ =

= (P (x, y)σ ⇒ (∀x(P (x, y) ∧Q(z)))σ)=

(P (x, y)σ ⇒ ∀x(P (x, y) ∧Q(z))σ∖{x←f(y,z)}

)=

(P (x, y)σ ⇒ ∀x(P (x, y)σ∖{x←f(y,z)} ∧Q(z)σ∖{x←f(y,z)})

)= (P (f(y, z), z)⇒ ∀x(P (x, z) ∧Q(a))) .

▲Fiind date substituţii, se pot obţine unele noi prin operaţia de compoziţie.

Definiţie 2.11 (Compunerea substituţiilor). Fie θ = {x1 ← t1, . . . , xn ← tn} şi σ ={y1 ← s1, . . . , yn ← sk} substituţii, X,Y respectiv mulţimile de variabile ce apar în θ, σ.Atunci compoziţia substituţiilor θ şi σ, notată cu θσ este o substituţie definită astfel:

θσ = {xi ← tiσ|xi ∈ X,xi ̸= tiσ} ∪ {yj ← sj |yj ∈ Y, yj ̸∈ X}.

■Aşadar, se aplică a doua substituţie termenilor din prima substituţie, se elimină pe-

rechile pentru care termenul substituit este acelaşi cu variabila şi se adaugă elementeledin a doua substituţie a căror variabilă nu apare în prima.

Exemplul 2.6 (Compoziţia substituţiilor). Fie

θ = {x← f(y), y ← f(a), z ← u},σ = {y ← g(a), u← z, v ← f(f(a))},

Atunci:

θσ = {x← f(y)σ, y ← f(a)σ, z ← uσ} ∪ {u← z, v ← f(f(a))}= {x← f(g(a)), y ← f(a), z ← z} ∪ {u← z, v ← f(f(a))}= {x← f(g(a)), y ← f(a),����z ← z} ∪ {u← z, v ← f(f(a))}= {x← f(g(a)), y ← f(a), u← z, v ← f(f(a))}.

▲

36

Proprietăţi ale substituţiilor

• Fie E o expresie şi θ, σ substituţii. Atunci E(θσ) = (Eθ)σ.

• Fie θ, σ, λ substituţii. Atunci θ(σλ) = (θσ)λ.

2.5. Relaxarea sintaxei (II)Logica predicatelor este folosită implicit în matematică, informatică, etc, însă într-o for-mă ce nu se conformează neapărat definiţiei sintaxei pe care am propus-o aici. Motivulpentru acest fapt este legat de nevoia de a exprima eficient anumite lucruri. În conti-nuare, vom identifica câteva cazuri tipice de „prescurtări”, „zahăr sintactic” (din engl.„syntactic sugar”). Cunoaşterea acestor notaţii, şi a altora similare, face posibilă par-curgerea mai eficientă a materialelor, translatarea în cadrul oferit de logica predicatelor(cu toată maşinăria de raţionament pe care o vom dezvolta în continuare).

• Negaţii de predicate binare: x ⋪ y este o prescurtare a lui ¬(x ◁ y), unde ◁ esteun predicat binar.

• Asociativitarea conectorilor logici: P ∧Q∧R este o prescurtare pentru P ∧(Q∧R),P ∨Q ∨R este o prescurtare pentru P ∨ (Q ∨R), P ⇒ Q⇒ R este o prescurtarepentru P ⇒ (Q⇒ R).

• Dacă . . ., atunci . . . { altfel . . . }: (if . . . then . . . else): „Dacă P , atunci Q” este oprescurtare pentru P ⇒ Q, „DacăP , atunci Q, altfel R” este o prescurtare pentru

(P ⇒ Q) ∧ (¬P ⇒ R).

• Conjuncţii de formule: P,Q,R este o prescurtare pentru P ∧Q ∧R.

• Conjuncţii de formule atomice conţinând predicate binare:– x < y < z < 1 este o prescurtare pentru x < y ∧ y < z ∧ z < 1,– x, y, z < 1 este o prescurtare pentru x < 1 ∧ y < 1 ∧ z < 1.

• Formule cuantificate:– ∀

x,yA ( ∃

x,yA) este o prescurtare pentru ∀

x∀yA (∃

x∃yA),

– ∀P (x)

A este o prescurtare pentru ∀x(P (x)⇒ A),

– ∃P (x)

A este o prescurtare pentru ∃x(P (x) ∧A).

37

3. Semantica logicii predicatelorLimbajul logicii predicatelor (de ordinul întâi) este universal, în sensul în care poateexprima „orice”. Prin urmare, va putea descrie orice univers. Vom defini în continuaremodul în care înţelesul expresiilor din limbaje de ordinul întâi poate fi determinat. Vomvedea care sunt problemele legate de înţelesul unor astfel de expresii.

3.1. Interpretare, asignare de valori variabilelor, valoareaexpresiilor

Limbajul L va descrie un domeniu (univers de discurs, lume) D. Vom ataşa numele desimboluri unor concepte corespunzătoare din D (funcţii, relaţii, valori) – prin interpretare.Apoi vom ataşa valori variabilelor prin asignare. Cu aceste ingrediente, vom puteadetermina valoarea (înţelesul) expresiilor.

Definiţie 3.1 (Interpretare). Fie L = {F ,P, C} mulţimea simbolurilor unui limbaj, şiD un domeniu nevid. O interpretare I a limbajului L în domeniul D este o maparecare ataşează:

• fiecărui simbol funcţional f/n ∈ F o funcţie de aritate corespunzătoare din D,

• fiecărui simbol predicativ p/n ∈ P o relaţie de aritate corespunzătoare din D,

• fiecărei constante c ∈ C o valoare din D.

■Observaţie (Reprezentarea domeniului descris). Domeniul descris de un limbaj, es-te format din obiecte, concepte (funcţii şi relaţii) „concrete”. Totuşi, pentru a puteadescrie procesul prin care limbajul cu simbolurile L este folosit pentru a descrie do-meniul de interes, suntem nevoiţi să reprezentăm acest univers. Pentru aceasta, vomfolosi ghilimele singulare ′ . . .′ (şi un font corespunzător, unde este cazul, caresă indice faptul că suntem în domeniul D, şi să separe de limbaj). ▲Exemplul 3.1 (Interpretări). Fie un limbaj L, astfel încât ⊙/2 ∈ F , P/2 ∈ P şia, b ∈ C. Următoarele sunt interpretări ale limbajului L:

• I1, interpretarea limbajului în domeniul N (adică D = N),I1(P ) := ′ ≤′, I1(⊙) := ′+′, I1(a) := ′0′, I1(b) := ′1′.

• I2, interpretarea limbajului în domeniul Z,I2(P ) :=′<′, I2(⊙) :=′ −′, I2(a) := ′3′, I2(b) := ′ − 5′.

38

• I3, intepretarea limbajului în domeniul şirurilor de caractere,I3(P ) := 'subşir', I3(⊙) := 'concatenare', I3(a) := '„un şir oarecare”', I3(b) :='„alt şir”'.

▲Definiţie 3.2 (Asignare de valori variabilelor). Fie I o interpretare. O asignare devalori pentru variabile sub interpretarea I este o mapare

σI : V → D

care asignează fiecărei variabile un element din domeniul D.■

Evident, având în vedere că V este o mulţime numărabilă, vom specifica asignăriledoar pentru variabilele folosite, de exemplu în expresiile pe care le folosim.

Vom folosi următoarea notaţie: σI [x ← d] pentru o asignare σI unde în particularvariabilei x i se ataşează elementul d.

Observaţie (Diferenţa între substituţii şi asignări de valori variabilelor). Atenţie, celedouă concepte sunt diferite! În primul caz, la substituţii, se ataşează variabilelor termeni(este o operaţie sintactică), în al doilea caz, se ataşează valori de adevăr, se „traduce”limbajul în domeniul descris. ▲

Intuitiv, termenii descriu obiecte, valori din domeniul de interes.

Definiţie 3.3 (Valoarea termenilor). Fie I o interpretare şi σI o asignare de valorivariabilelor. Atunci valoarea unui termen sub intepretarea I şi asignarea devalori variabilelor σI , υσI este definită în modul următor:

• Dacă x ∈ V, υσI (x) = σI(x).

• Dacă c ∈ C, υσI (c) = I(c).

• Dacă f/n ∈ F , t1, . . . tn sunt termeni,

υσI (f(t1, . . . , tn)) = I(f)(υσI (t1), . . . , υσI (tn)).

■Exemplul 3.2. Să considerăm interpretările I1, I2, I3 din Exemplul 3.1. Pentru ur-mătorii termenii ((x⊙ y)⊙ a), (y ⊙ (a⊙ b)):

• Considerăm υσI1(x) = ′2′, υσI1

(y) = ′4′ şi calculăm

υσI1(((x⊙ y)⊙ a)) = I1(⊙)(υσI1

(x⊙ y), υσI1(a))

= ′+′(I1(⊙)(υσI1(x), υσI1

(y)), υσI1(a))

= ′+′(′+′(σI1(x), σI1(y)), I1(a))= ′+′(′+′(′2′, ′4′), ′0′)

39

Observaţi că am trecut complet în domeniul descris de limbaj, deci avem valoareacăutată. Mai mult, în respectivul domeniu ′+′(′+′(′2′, ′4′), ′0′) = ′6′. Dar atenţie,în momentul acesta nu mai operăm cu simboluri, ci direct în domeniul N cu numerenaturale.Folosim aici sintaxa relaxată pentru termeni, cu ⊙ simbol funcţional infix.

• Considerăm υσI3(y) = '„”' (şirul de caractere vid) şi calculăm:

υσI3(y ⊙ (a⊙ b)) = I3(⊙)(υσI3

(y), υσI3(a⊙ b))

= ′concatenare′(σI3(y), I3(⊙)(υσI3(a), υσI3

(b)))

= ′concatenare′(′„”′, ′concatenare′(I3(a), I3(b)))= ′concatenare′(′„”′, ′concatenare′('„un şir oarecare”', '„alt şir”'))= '„un şir oarecarealt şir”'.

▲Intuitiv, o formulă descrie o situaţie, valoarea unei formule spune daca situaţia are loc

(este „adevărată”) sau nu (este „falsă”).

Definiţie 3.4 (Domeniu de valori de adevăr). Alegem două valori distincte A,F (ade-vărat, fals). Mulţimea de valori de adevăr este mulţimea {A,F}. Acest domeniu semai numeşte domeniu boolean. ■Definiţie 3.5 (Funcţii de adevăr). Funcţiile de adevăr pentru conectorii logicisunt definite în modul următor:

B¬ : {A,F} → {A,F}B∧,B∨,B⇒,B⇔ : {A,F} × {A,F} → {A,F}

x y B¬(x) B∧(x, y) B∨(x, y) B⇒(x, y) B⇔(x, y)

F F A F F A AF A F A A FA F F F A F FA A A A A A

■Definiţie 3.6 (Valoarea formulelor). Fie I o interpretare şi σI o asignare de valorivariabilelor. Atunci valoarea de adevăr a unei formule, sub intepretarea I şiasignarea de valori variabilelor σI , υσI este definită în modul următor:

• Dacă P/n ∈ P şi t1, . . . , tn sunt termeni, atunci

υσI (P (t1, . . . , tn)) = I(P )(υσI (t1), . . . , υσI (tn)).

• Fie F , G formule. Atunci:υσI (¬F ) = B¬(υσI (F )),

40

υσI (F ∧G) = B∧(υσI (F ), υσI (G)),

υσI (F ∨G) = B∨(υσI (F ), υσI (G)),

υσI (F ⇒ G) = B⇒(υσI (F ), υσI (G)),

υσI (F ⇔ G) = B⇔(υσI (F ), υσI (G)).

• Fie x ∈ V, F o formulă:– υσI (∀xF ) = A dacă şi numai dacă pentru orice d ∈ D, υσI [x←d](F ) = A,– υσI (∃xF ) = A dacă şi numai dacă pentru unii d ∈ D, υσI [x←d](F ) = A.

■Exemplul 3.3 (Valoarea formulelor sub interpretare şi asignare de valori). Să consi-derăm interpretările I1, I2, I3 din Exemplul 3.1, şi formula P (a, x⊙ b).

• Considerăm υσI1(x) = ′2′, şi calculăm

υσI1(P (a, x⊙ b)) = I1(P )(υσI1

(a), υσI1(x⊙ b))

= ′ ≤′(I1(a), I1(⊙)(υσI1(x), υσI1

(b)))

= ′ ≤′(′0′, ′+′(σI1(x), I1(b)))= ′ ≤′(′0′, ′+′(′2′, ′1′))= ′ ≤′(′0′, ′3′))= A.

• Considerăm υσI3(x) = '„ceva”' şi calculăm:

υσI3(P (a, x⊙ b)) = I3(P )(υσI3

(a), υσI3(x⊙ b))

= ′subşir′(I3(a), I3(⊙)(υσI3(x), υσI3

(b)))

= ′subşir′('„un şir oarecare”', ′concatenare′(σI3(x), I3(b)))= ′subşir′('„un şir oarecare”', ′concatenare′('„ceva”', '„alt şir”'))= ′subşir′('„un şir oarecare”', '„cevaalt şir”'))= F.

▲Observaţie (Semantica înseamnă rezolvare directă). Definiţiile 3.3 şi 3.6 „traduc”expresiile din logica predicatelor (termeni, respectiv formule) în domeniul descris delimbaj. A determina valoarea sub interpretare şi asignare de valori înseamnă a rezolvadirect probleme în domeniul descris.

O problemă apare la formulele cuantificate. Pentru ca formula universală să fie adevă-rată, trebuie să verificăm că formula funcţionează pentru toate elementele din domeniu.La fel, pentru ca formula existenţială să fie adevărată, trebuie sa verificăm elementeledomeniului până când găsim unul care face formula adevărată. În cazul în care domeniuleste mare (infinit), acest lucru nu este posibil. Aşadar, rezolvarea directă a problemelor,aşa cum este descrisă de semantică se loveşte de un „zid infinit”. După cum vom vedeamai jos, lucrurile stau şi mai rău, când considerăm întrebări tipice pe care le putem punedespre formule. ▲

41

3.2. Semantica şi substituţiileIntuitiv, substituţia ne permite să înlocuim variabile cu termeni. Când vine vorba desensul (semantica) expresiilor, ceea ce se spune despre variabilă ar trebui să se spună şidespre termenul cu care s-a înlocuit variabila respectivă.

Exemplul 3.4 (Exemplu din [Buc91]). Fie următoarea formulă ce vorbeşte desprenumere naturale, unde simbolurile au interpretarea tradiţională:

P : ∃y(x = 2y).

Intuitiv, aceasta spune că x este un număr par.Considerăm acum

P{x←y+1} : ∃y(y + 1 = 2y).

Sensul formulei s-a schimbat. Acum spune că y = 1. Motivul pentru aceasta are de-aface cu faptul că variabila y din {x← y+1}, care este liberă, devine legată atunci cândtermenul în care apare este inserat în formula cuantificată.

▲Substituţia nu poate fi făcută atunci când ar schimba sensul expresiei asupra căreia

acţionează.

Definiţie 3.7 (Substituibilitate). Fie x ∈ V şi t ∈ T(L,V) şi σ ∈ SL,V astfel încâtx ← t ∈ σ şi F ∈ F(L,V). Termenul t este substituibil pentru variabila x în Fse defineşte în felul următor:

• Dacă F este formulă atomică, t este substituibil pentru x în F .

• Dacă F , G sunt formule, atunci:– t este substituibil pentru x în (¬F ) dacă şi numai dacă t este substituibil

pentru x în F .– t este substituibil pentru x în (F□G) dacă şi numai dacă t este substituibil

pentru x în F şi în G, unde □ ∈ {∧,∨,⇒,⇔}.

• Dacă x, y ∈ V, F este o formulă şi Q ∈ {∀,∃}, atunci– t este substituibil pentru x în QxF ,– t este substituibil pentru x în QyF dacă şi numai dacă y nu este liberă în t şi

t este substituibili pentru x în F .

■Substituţia nu este o problemă în termeni, pentru că aşa cum i-am definit, termenii

conţin numai variabile libere.

Exemplul 3.5 (Substituibilitate).

42

• Este y + 1 substituibil pentru y în ∃y(x = 2y)?Da, conform definiţiei (dar substituţia nu va avea efect, variabila y fiind legată înformulă).

• Este vw substituibil pentru x în ∃y(x < vx⇒ (∃w(w < v)))?Da, x este liber în formula de după cuantificator, dar y nu este liber în vw şi vweste substituibil în formula după primul cuantificator.

• Este vw substituibil pentru v în ∃y(x < vx⇒ (∃w(w < v)))?Nu, în a doua subformulă cuantificată, înlocuirea lui v cu vw face variabila w careera liberă în termenul substituit, devine legată.

• Is vw substitutable for w in ∃y(x < vx⇒ (∃w(w < v)))?Da. (De ce?)

▲

3.3. Întrebări legate de înţelesul formulelorPrimul tip de întrebări legat de înţelesul unei formule este în ce condiţii este adevăratăsau falsă.

Definiţie 3.8 (Validitate în logica predicatelor). Fie F ∈ F(L,V).Formula F este validă dacă şi numai dacă pentru orice domeniu, D, orice interpretareI a limbajului L în D, orice asignare de valori variabilelor σI , avem υσI (F ) = A.

Formula F este invalidă dacă şi numai dacă există un domeniu D, o interpretare I alimbajului L în D, o asignare de valori variabilelor σI astfel încât υσI (F ) = F.

■Definiţie 3.9 (Satisfiabilitate în logica predicatelor). Fie F ∈ F(L,V).

Formula F este satisfiabilă dacă şi numai dacă există un domeniu D, o interpretareI a limbajului L în D, o asignare de valori variabilelor σI astfel încât υσI (F ) = A.

Formula F este nesatisfiabilă dacă şi numai dacă pentru orice domeniu, D, oriceinterpretare I a limbajului L în D, orice asignare de valori variabilelor σI , avem υσI (F ) =F.

■Al doilea tip de întrebări se referă la relaţia dintre înţelesul unor formule.

Definiţie 3.10 (Echivalenţă logică în logica predicatelor). Fie F,G ∈ F(L,V).Formulele F şi G sunt logic echivalente, şi scriem F ≡ G dacă şi numai dacă,

pentru orice domeniu, D, orice interpretare I a limbajului L în D, orice asignare devalori variabilelor σI , avem υσI (F ) = υσI (G).

■Definiţie 3.11 (Consecinţă logică în logica predicatelor). Fie F1, . . . , Fn, G ∈ F(L,V).

43

Formula G este consecinţă logică a formulelor F1, . . . , Fn , şi scriem F1, . . . , Fn ⊨ G,dacă şi numai dacă, pentru orice domeniu, D, orice interpretare I a limbajului L în D,orice asignare de valori variabilelor σI , dacă

υσI (F1) = . . . υσI (Fn) = A,

atunci υσI (G) = A. ■A rezolva direct aceste probleme este lipsit de orizont în cele mai multe cazuri. Zidul

infinit de care vorbeam referindu-ne la Definiţia 3.6 se multiplică. Un limbaj poatedescrie o infinitate de domenii, pentru fiecare domeniu (care poate fi infinit, cu un numărinfinit de concepte - valori, funcţii, relaţii), se pot defini infinit de multe interpretări, şiasignări de variabile. Oricare din întrebările de mai sus necesită „vizitarea” unui numărinfinit de combinaţii.

Deşi aceste mănunchiuri de infinităţi pot fi adresate construind un univers artificial,universul lui Herbrand, ale cărui obiecte sunt termeni (fără variabile) peste limbajul L.În esenţă, însă, problema nu este adresată satisfăcător, şi discuţia despre universul luiHerbrand este dincolo de scopul acestor note de curs. Vezi însă, de exemplu, [BA12]pentru detalii.

Aşadar avem nevoie de un alt instrument pentru rezolvarea problemelor în logicapredicatelor, de un sistem de raţionament.

44

Bibliografie[BA12] M. Ben-Ari. Mathematical Logic for Computer Science. Springer London,

2012.

[Bou04] Nicolas Bourbaki. Description of Formal Mathematics. Springer, 2004.

[Buc91] Bruno Buchberger. Logic for computer science. Unpublished lecture notes,Copyright Bruno Buchberger, 1991.

[Chu36] Alonzo Church. An unsolvable problem of elementary number theory. Ame-rican Journal of Mathematics, 58(2):345–363, 1936.

[Göd30] Kurt Gödel. Die vollständigkeit der axiome des logischen funktionenkalküls.Monatshefte für Mathematik, 1(37):349–360, 1930.

[Göd31] Kurt Gödel. Über formal unentscheidbare sätze der principia mathemati-ca und verwandter systeme, I. Monatshefte für Mathematik und Physik,(38):173–198, 1931.

[KLRV49] E. L. Kaufman, M. W. Lord, T. W. Reese, and J. Volkmann. The discrimina-tion of visual number. The American Journal of Psychology, 62(4):498–525,1949.

[Rus03] B. Russell. The Principles of Mathematics. Number vol. 1 in The Principlesof Mathematics. University Press, 1903.

[Tur37] Alan M Turing. On computable numbers, with an application to the entschei-dungsproblem. Proceedings of the London mathematical society, 2(1):230–265, 1937.

45