Logică computațională O introducere practică pentru...
93
Logică computațională O introducere practică pentru studenți la informatică Note de curs Adrian Crăciun [email protected] 21 ianuarie 2020 1
Transcript of Logică computațională O introducere practică pentru...
Logică computaționalăO introducere practică pentru studenți la
informatică
Note de curs
Adrian Cră[email protected]
21 ianuarie 2020
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
II. Logica propoziţiilor 15
2. Sintaxa logicii propoziţiilor 172.1. Expresiile logicii propoziţiilor . . . . . . . . . . . . . . . . . . . . . . . . . 172.2. Parcurgerea expresiilor logicii propoziţiilor . . . . . . . . . . . . . . . . . . 18
2.2.1. Recunoaşterea şi parcurgerea sintaxei logicii propoziţiilor: sintaxaabstractă . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3. Relaxarea sintaxei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3. Semantica logicii propoziţiilor 273.1. Valori de adevăr, interpretări, valoare sub interpretare . . . . . . . . . . . 273.2. Probleme în logica propoziţiilor: validitate, satisfiabilitate . . . . . . . . . 293.3. Probleme în logica propoziţiilor: echivalenţa logică . . . . . . . . . . . . . 303.4. Probleme în logica propoziţiilor: consecinţă logică . . . . . . . . . . . . . 333.5. Limitările abordării directe (semantice) . . . . . . . . . . . . . . . . . . . 36
4. Aplicaţii ale logicii propoziţiilor: proiectarea circuitelor digitale 384.1. Logica propoziţiilor descrie funcţiile de adevăr . . . . . . . . . . . . . . . . 38
4.1.1. Conjuncţii şi disjuncţii de formule . . . . . . . . . . . . . . . . . . 384.1.2. Funcţii booleene descrise de formule propoziţionale . . . . . . . . . 39
i
4.2. Designul şi tranformarea circuitelor digitale . . . . . . . . . . . . . . . . . 404.2.1. Circuite digitale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.2.2. Designul circuitelor digitale . . . . . . . . . . . . . . . . . . . . . . 404.2.3. Transformarea şi simplificarea circuitelor digitale . . . . . . . . . . 424.2.4. Mulţimi complete de conectori logici . . . . . . . . . . . . . . . . . 42
5. Raţionament în logica propoziţiilor 445.1. Forme normale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.2. Metoda rezoluţiei şi metode bazate pe rezoluţie . . . . . . . . . . . . . . . 49
III. Logica predicatelor 50
6. Sintaxa logicii predicatelor de ordinul întâi 526.1. Expresiile logicii predicatelor de ordinul întâi . . . . . . . . . . . . . . . . 526.2. Parcurgerea expresiilor logicii predicatelor de ordinul întâi . . . . . . . . . 54
6.2.1. Recunoaşterea expresiilor logicii predicatelor folosind definiţia sin-taxei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.2.2. Recunoaşterea şi parcurgerea sintaxei logicii predicatelor: sintaxaabstractă . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.3. Relaxarea sintaxei (I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666.4. Substituţii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676.5. Relaxarea sintaxei (II) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7. Semantica logicii predicatelor 717.1. Interpretare, asignare de valori variabilelor, valoarea expresiilor . . . . . . 717.2. Semantica şi substituţiile . . . . . . . . . . . . . . . . . . . . . . . . . . . 747.3. Probleme în logica predicatelor . . . . . . . . . . . . . . . . . . . . . . . . 75
8. Raţionament în logica predicatelor 778.1. Proving. Proof techniques. Definitions. Theories. . . . . . . . . . . . . . . 77
8.1.1. Reasoning in Predicate Logic . . . . . . . . . . . . . . . . . . . . . 778.1.2. Proof Situations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 778.1.3. Basic Approaches to Proving . . . . . . . . . . . . . . . . . . . . . 788.1.4. Definitions in Predicate Logic . . . . . . . . . . . . . . . . . . . . . 82
8.2. Theories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 838.2.1. Equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.3. Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
ii
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 propoziţiilor) . . . . . . . . . . . . . . . . . . 172.2. Definiţie (Formule propoziţionale bine formate) . . . . . . . . . . . . . . . 172.3. Definiţie (Arbori (ordonaţi)) . . . . . . . . . . . . . . . . . . . . . . . . . . 192.4. Definiţie (Sintaxa abstractă a formulelor logicii propoziţiilor) . . . . . . . 20
3.1. Definiţie (Domeniu de valori de adevăr) . . . . . . . . . . . . . . . . . . . 273.2. Definiţie (Funcţii de adevăr corespunzătoare conectorilor logici) . . . . . . 273.3. Definiţie (Interpretare pentru variabile propoziţionale) . . . . . . . . . . . 273.4. Definiţie (Valoarea unei formule sub interpretare) . . . . . . . . . . . . . . 283.5. Definiţie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.6. Definiţie (Formule valide, formule invalide) . . . . . . . . . . . . . . . . . 293.7. Definiţie (Formule satisfiabile, formule nesatisfiabile) . . . . . . . . . . . . 293.8. Definiţie (Tabele de adevăr) . . . . . . . . . . . . . . . . . . . . . . . . . . 293.9. Definiţie (Echivalenţă logică) . . . . . . . . . . . . . . . . . . . . . . . . . 303.10. Definiţie (Formula falsă, formula adevărată) . . . . . . . . . . . . . . . . . 313.11. Definiţie (Consecinţă logică în logica propoziţiilor) . . . . . . . . . . . . . 33
4.1. Definiţie (Conjuncţie de formule) . . . . . . . . . . . . . . . . . . . . . . . 384.2. Definiţie (Disjunction of formulae) . . . . . . . . . . . . . . . . . . . . . . 384.3. Definiţie (Funcţii de adevăr descrise de formule propoziţionale.) . . . . . . 394.4. Definiţie (Circuite digitale) . . . . . . . . . . . . . . . . . . . . . . . . . . 404.5. Definiţie (Mulţimi complete de conectori logici) . . . . . . . . . . . . . . . 42
6.1. Definiţie (Vocabularul logicii de ordinul întâi) . . . . . . . . . . . . . . . . 526.2. Definiţie (Termenii logicii predicatelor de ordinul întâi) . . . . . . . . . . . 536.3. Definiţie (Simboluri dominante, subtermeni) . . . . . . . . . . . . . . . . . 536.4. Definiţie (Formulele logicii predicatelor de ordinul întâi) . . . . . . . . . . 536.5. Definiţie (Simboluri dominante, subformule) . . . . . . . . . . . . . . . . . 546.6. Definiţie (Sintaxa abstractă a termenilor logicii predicatelor) . . . . . . . 556.7. Definiţie (Sintaxa abstractă a formulelor logicii predicatelor) . . . . . . . . 566.8. Definiţie (Substituţie) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
iii
6.9. Definiţie (Substituţie aplicată unei expresii) . . . . . . . . . . . . . . . . . 676.10. Definiţie (Compunerea substituţiilor) . . . . . . . . . . . . . . . . . . . . . 69
7.1. Definiţie (Interpretare) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 717.2. Definiţie (Asignare de valori variabilelor) . . . . . . . . . . . . . . . . . . . 727.3. Definiţie (Valoarea termenilor) . . . . . . . . . . . . . . . . . . . . . . . . 727.4. Definiţie (Domeniu de valori de adevăr) . . . . . . . . . . . . . . . . . . . 737.5. Definiţie (Funcţii de adevăr) . . . . . . . . . . . . . . . . . . . . . . . . . . 737.6. Definiţie (Valoarea formulelor) . . . . . . . . . . . . . . . . . . . . . . . . 737.7. Definiţie (Substituibilitate) . . . . . . . . . . . . . . . . . . . . . . . . . . 747.8. Definiţie (Validitate în logica predicatelor) . . . . . . . . . . . . . . . . . . 757.9. Definiţie (Satisfiabilitate în logica predicatelor) . . . . . . . . . . . . . . . 757.10. Definiţie (Echivalenţă logică în logica predicatelor) . . . . . . . . . . . . . 757.11. Definiţie (Consecinţă logică în logica predicatelor) . . . . . . . . . . . . . 76
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 șiservicii, cutii negre: avem o aplicație pentru orice, alunecăm degetul pe ecranul unuidispozitiv mobil și ca prin minune, avem soluția (o aplicaţie pentru a comanda pizzaonline ar rezolva problema (h)om(inid)ului din Exemplul 1.1). Aproape nimeni nu maiare 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ă ca instrument derezolvare a problemelor, î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 pot
10
fi descrise și au soluții). Un astfel de limbaj este limbajul logicii predicatelor,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.
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-
13
chberger. Acest prim capitol urmează structura din notele de curs (nepublicate) ale luiBuchberger, vezi [Buc91].
14
Partea II.
Logica propoziţiilor
15
Logica propoziţiilor este o logică cu un limbaj care modelează afirmaţii simple:
• „Afară plouă.”
• „Păsările zboară spre vest.”
• „Astăzi este miercuri.”
În acest limbaj, domeniul, contextul afirmaţiilor nu este relevant, ne interesează doardacă afirmaţia este adevărată sau falsă. Aşadar, domeniu de interes, universul dediscurs al logicii propoziţiilor este domeniul valorilor de adevăr, ce conţine douăobiecte adevărat şi fals. Afirmaţiile simple sunt considerate atomice în acest sens, elenu pot fi descompuse. În fiecare caz, a Afirmaţiile simple pot fi combinate:
• „Dacă afară plouă, atunci azi este miercuri.”
• „Afară plouă şi azi este miercuri dacă şi numai dacă păsările zboară spre vest.”
În această parte, vom defini sintaxa şi semantica logicii propoziţiilor, vom defini pro-blemele ce pot fi exprimate în acest limbaj şi vom investiga ce înseamnă abordarea di-rectă a rezolvării lor, lucru posibil în logica propoziţiilor. Vom vedea limitările abordăriidirecte şi vom defini un sistem de raţionament ce adresează aceste limitări.
De asemenea, vom ilustra unele aplicaţii ale logicii propoziţiilor.
16
2. Sintaxa logicii propoziţiilor
2.1. Expresiile logicii propoziţiilorDefiniţie 2.1 (Vocabularul logicii propoziţiilor). Simbolurile logicii propoziţiilorsunt:
• V mulţimea (numărabilă) a variabilelor propoziţionale (nume de propoziţii). Vomnota propoziţiile folosind majuscule, eventual cu indecşi A,B, P,Q, P1, P2 . . ..
• Simbolurile rezervate:– conectori logici: ¬ (negaţia), ∧ (conjuncţia), ∨ (disjuncţia),⇒ (implicaţia), ⇔ (echivalenţa),
– ( ) paranteze.
■Observaţie. Faptul că mulţimea variabilelor propoziţionale este numărabilă ne va per-mite în orice moment să luăm o variabilă nouă, nefolosită până la acel moment. ▲Definiţie 2.2 (Formule propoziţionale bine formate). Mulţimea formulelor propo-ziţionale bine formate peste mulţimea de variabile V, P(V), este definită dupăcum urmează:
• Dacă A ∈ V desemnează o propoziţie atomică, atunci A ∈ P(V).
• Dacă P,Q ∈ P(V), atunci formulele compuse sunt formate în modul următor:– (¬P ) ∈ P(V),– (P ∧Q) ∈ P(V),– (P ∨Q) ∈ P(V),– (P ⇒ Q) ∈ P(V),– (P ⇔ Q) ∈ P(V).
Vom citi P ∈ P(V) ca „P este o formulă propoziţională bine formată peste mulţimeavariabilelor propoziţionale V”. Alternativ, P este o formulă propoziţională, P este opropoziţie.
Pentru propoziţiile compuse, citim:
• (¬P ), negaţia lui P ,
• (P ∧Q), conjuncţia lui P şi Q, „P şi Q”,
17
• (P ∨Q) disjuncţia lui P şi Q, „P sau Q”,
• (P ⇒ Q), implicaţia dintre P şi Q, „P implică Q”, „dacă P atunci Q”,
• (P ⇔ Q), echivalenţa lui P şi Q, „P echivalent cu Q”, „P dacă şi numai dacă Q”.
Propoziţiile P şi Q sunt subformule în formulele compuse, respectiv ¬, ∧, ∨, ⇒, ⇔sunt simbolurile dominante pentru formulele corespunzătoare.
■Observaţie. Rolul variabilelor propoziţionale este să ofere un mod prin care să neputem referi la propoziţii (nume pentru propoziţii). Ele pot fi folosite pentru a denumipropoziţii atomice, sau propoziţii compuse. Vom preciza acolo unde este necesar modul încare acestea sunt folosite. Implicit, dacă nu se specifică altfel, variabilele propoziţionalevor reprezenta propoziţii atomice. ▲
2.2. Parcurgerea expresiilor logicii propoziţiilorDefiniţia 2.2 ne permite să recunoaştem propoziţiile.
Exemplul 2.1 (Recunoaşterea propoziţiilor).
1. Dacă A este atom, atunci conform definiţiei, este propoziţie.
2. Pentru a vedea dacă ((P ∧Q)⇒ (¬R)) este o propoziţie,• identificăm simbolul dominant: ⇒,• conform definiţiei, avem nevoie de paranteză deschisă (✓), o propoziţie la
stânga implicaţiei, una la dreapta şi o paranteză închisă (✓):– (P ∧Q) este o propoziţie (conjuncţie), conform definiţiei, (✓)– (¬R) este o propoziţie, conform Observaţiei de mai sus. (✓)
Aşadar avem o propoziţie, conform definiţiei.▲
Observaţie (Subitare). De notat că în Exemplul 2.1 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. Acesta este identificat imediat, fără a indica explicit cum am făcut asta. Deşiar putea părea simplu, acest pas poate să nu fie verificabil pentru oricine (mai ales pentruun 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.
18
Avem nevoie, aşadar, pentru aceste situaţii, de o metodă în care structura expresieiparcurse este identificată pas cu pas. ▲
2.2.1. Recunoaşterea şi parcurgerea sintaxei logicii propoziţiilor: 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.3 (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.2 (Arbori). Mai jos, vom considera că nodurile arborilor ilustraţi conţinnumere naturale.
• arbore cu un singur nod (rădăcină):
1
• arbore cu mai multe noduri:
1
6
117
9
10
8
2
543
19
r
subarboren· · ·subarbore1
Figura 4.: Un arbore cu rădăcina r şi n subarbori.
Vom folosi o reprezentare generică pentru un arbore cu n subarbori, vezi Figura 4.Fiecare subarbore este la rândul său un arbore.
▲În continuare, vom folosi arborii pentru a reprezenta expresiile logicii propoziţiilor.
Vom numi aceşti arbori sintaxa abstractă, sau arbori sintactici pentru logicapropoziţiilor.
Definiţie 2.4 (Sintaxa abstractă a formulelor logicii propoziţiilor). Fie P(V) mulţimeapropoziţiilor peste variabilele propoziţionale V. Atunci sintaxa abstractă a formulelorlogicii propoziţiilor este reprezentată de următorii arbori:
• Dacă A ∈ P(V) este formulă atomică:
A
• Dacă F,G ∈ P(V), pentru formulele compuse (¬F ), (F□G), unde □ ∈ {∧,∨,⇒,⇔}:
¬
F
□
GF
■Vom prezenta o metodă prin care se pot recunoaşte expresiile (şi în acelaşi
timp construi arborele sintactic) pentru propoziţii.
20
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ţia 2.2),
avem eşec.
Exemplul 2.3 (Recunoaşterea expresiilor logicii propoziţiilor şi construcţia arboreluisintactic). Pentru a ilustra această metodă, reluăm Exemplul 2.1:
((P ∧Q)⇒ (¬R)).
Vom numerota fiecare simbol în expresia ce trebuie parcursă:
(
1(
2P3∧4
Q
5)
6⇒7
(
8¬9
R
10)
11)
12
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:• dacă într-un nod sau subarbore avem ghilimele („· · · ”), acestea indică faptul
că în acel loc avem se aşteaptă:– „F”: un subarbore ce reprezintă o formulă propoziţională,– „¬”, „□”: negaţie, respectiv conector binar (unul din ∧,∨,⇒,⇔),
21
• Un nod sau subarbore reprezentat cu linie întreruptă reprezintă poziţia înarborele incomplet, unde vom completa la pasul următor.
(2): ( – paranteză deschisă. Prima variantă (în care formula este o negaţie) cade, lucrămpe varianta a doua.Paranteza deschisă poate fi începutul unei formule compuse, negaţie sau formulăcompusă folosind un conector binar.Avem două posibilităţi:
„□”
„F”„¬”
„F”
„□”
„F”„□”
„F”„F”
(3): P – este o variabilă propoziţională, astfel că prima variantă (în care căutăm onegaţie) cade, lucrăm pe varianta a doua. Variabila propoziţională închide ramuraarborelui, mutăm poziţia la nivelul părintelui.
„□”
„F”„¬”
„F”
„□”
„F”„□”
„F”P
(4): ∧ – este un conector logic binar, îl scriem în nodul curent şi ne mutăm pe ramuraurmătoare .
22
„□”
„F”∧
„F”P
(5): P – este o variabilă propoziţională, închidem ramura arborelui, mutăm poziţia lanivelul părintelui.
„□”
„F”∧
QP
(6): ) – paranteză închisă, ne mutăm pe poziţia părintelui, ramura curentă este închisă.
„□”
„F”∧
QP
(7): ⇒ – conector propoziţional binar, îl scriem în nodul curent, mutăm poziţia pesubarborele următor.
23
⇒
„F”∧
QP
(8): ( – 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”
∧
QP
⇒
„□”
„F”„F”
∧
QP
(9): ¬ – conectorul negaţie, prima variantă este cea considerată, a doua cade, completămnegaţia şi ne mutăm la subarbore.
⇒
¬
„F”
∧
QP
⇒
„□”
„F”„F”
∧
QP
(10): R – variabilă propoziţională, o scriem la poziţia curentă, şi ne mutăm la nivelulpărintelui.
24
⇒
¬
R
∧
QP
(11): ) – paranteză închisă, subarborele curent este complet, ne mutăm la nivelul părin-telui.
⇒
¬
R
∧
QP
(12): ) – paranteză închisă, subarborele curent este complet, ne mutăm la nivelul pă-rintelui. Cum nodul curent este rădăcina, înseamnă că marcajul poziţiei următoareiese din arbore, deci avem un arbore închis, am terminat, expresia parcursă este opropoziţie, şi avem arborele ce reprezintă sintaxa abstractă.
⇒
¬
R
∧
QP
▲
2.3. Relaxarea sintaxeiO consecinţă a Definiţiei 2.2 este că pentru formule propoziţionale mari, numărul pa-rantezelor poate deveni o problemă (mai ales pentru oameni, în mai puţină măsură dacă
25
formulele propoziţionale sunt folsite de calculator). În practică, oamenii au tendinţa dea folosi paranteze doar când este neapărat necesar.
Exemplul 2.4. Să considerăm expresia P ∧Q⇒ ¬R. Aceasta este evident mai com-pactă decât formula din Exemplul 2.1. Problema este că această formulă este ambiguă:
• reprezintă ((P ∧Q)⇒ (¬R))
• sau (P ∧ (Q ∧ (¬R)))
• şi contează asta, există o diferenţă?
După cum vom vedea în Secţiunea 3, într-adevăr există o diferenţă, iar pentru a evitaambiguităţile, trebuie să ţinem cont de anumite aspecte discutate în continuare. ▲
Precedenţa conectorilor logiciPentru a evita ambiguităţile, definim o precedenţă pentru conectorii propoziţionali:
¬, {∧,∨},⇒,⇔
(conjuncţia şi disjuncţia au aceeaşi precedenţă).Aceasta înseamnă că atunci când încercăm să parcurgem o expresie fără paranteze
vom considera negaţia şi încercăm să formăm o formulă în jurul ei, apoi conjuncţia şidisjuncţia (din moment ce acestea au aceeaşi precedenţă se poate să fie nevoie să folosimparanteze când acestea sunt amestecate), apoi implicaţia şi în ultimul rând echivalenţa.
Considerând precedenţa conectorilor logici, formula din Exemplul 2.4 este
((P ∧Q)⇒ (¬R)).
Asociativitatea conectorilor logiciExemplul 2.5. Considerăm expresia P ⇒ Q⇒ R. Această expresie este ambiguă:
• reprezintă (P ⇒ (Q⇒ R))
• sau ((P ⇒ Q)⇒ R)?
Răspunsul depinde de asociativitatea conectorilor. Conectorii propoziţionali vor fiasociativi la dreapta, deci prima variantă este cea corectă în Exemplul 2.5. ▲
Considerând precedenţa şi asociativitatea conectorilor logici, din acest moment vomaccepta o relaxare a sintaxei, în sensul în care vom accepta (cât timp nu sunt ambiguităţi)propoziţii care nu folosesc paranteze.
Observaţie. Recunoaşterea propoziţiilor în sintaxa relaxată devine mai complicată de-cât metoda pentru sintaxa strictă. ▲
26
3. Semantica logicii propoziţiilor
3.1. Valori de adevăr, interpretări, valoare sub interpretareDefiniţie 3.1 (Domeniu de valori de adevăr). Considerăm două obiecte (valori) dis-tincte A, F. Domeniul valorilor de adevăr este reprezentat de mulţimea {A,F}.Această mulţime este considerată total ordonată, F < A. ■
Domeniul valorilor de adevăr reprezintă universul de discurs pentru logica propoziţii-lor.
Definiţie 3.2 (Funcţii de adevăr corespunzătoare conectorilor logici). Definim urmă-toarele funcţii de adevăr corespunzătoare conectorilor propoziţionali:
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)
A A F A A A AA F F A F FF A A F A A FF F F F A A
■Definiţie 3.3 (Interpretare pentru variabile propoziţionale). Fie (V ) mulţimea varia-bilelor propoziţionale. O interpretare pentru variabilele propoziţionale din V esteo funcţie
I : V −→ {A,F}.
■Când vom descrie o interpretare I, vom preciza valorile doar pentru variabilele folosite
(de exemplu în formulele considerate).
Exemplul 3.1. Fie P,Q,R ∈ V. Următoarele sunt interpretări pentru variabileleconsiderate:
• I1: I1(P ) = F, I1(Q) = F, I1(R) = A,
• I2: I2(P ) = A, I2(Q) = F, I2(R) = F.
▲
27
Observaţie (Reprezentarea compactă a interpretărilor). Putem reprezenta interpretă-rile compact, ca mulţimi de atomi sau negaţii de atomi, în felul următor:
• I1 − {¬P,¬Q,R},
• I1 − {¬P,¬Q,R},
sunt reprezentările interpretărilor de la Exemplul 3.1. Dacă unei variabile P i se ataşeazăvaloarea A atunci va apărea în reprezentarea sub formă de mulţime ca P , altfel va apăreaca ¬P .
▲Avem elementele necesare pentru a defini înţelesul unei formule propoziţionale.
Definiţie 3.4 (Valoarea unei formule sub interpretare). Fie F ∈ P(V) o propoziţie,I : V −→ {A,F} o intepretare. Valoarea propoziţiei F sub intepretarea I, υI(F ), estedefinită după cum urmează:
• Dacă A este un atom, υI(A) = I(A).
• Dacă F,G ∈ P(V), atunciυI(¬F ) = B¬(υI(F )),υ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 ), υT (F )).
■Exemplul 3.2 (Valoare sub interpretare).
Considerăm propoziţia G.= ((P ∧ Q) ⇒ (R ⇔ (¬S))) şi intepretarea I(P ) = A,
I(Q) = F, I(R) = A, I(S) = A.Atunci, folosind Definiţia 3.4:
υI(G) =
υI(((P ∧Q)⇒ (R⇔ (¬S)))) =B⇒(υI((P ∧Q)), υI((R⇔ (¬S)))) =B⇒(B∧(υI(P ), υI(Q)),B⇔(υI(R), υI((¬S)))) =B⇒(B∧(I(P ), I(Q)),B⇔(I(R), υI((¬S)))) =B⇒(B∧(A,F),B⇔(A,B¬(υI(S)))) =B⇒(B∧(A,F),B⇔(A,B¬(I(S)))) =B⇒(F,B⇔(A,F)) =B⇒(F,F) = A.
28
▲Definiţie 3.5. Fie F ∈ P(V) o propoziţie, I : V −→ {A,F} o intepretare.
Dacă υI(P ) = A, spunem că I satisface P , sau P este satisfăcută de I.Dacă υI(P ) = F, spunem că I falsifică F , sau F este falsificată de I.
■Observaţie (Numărul posibil de interpretări). Pentru n variabile propoziţionale, nu-mărul total de interpretări este 2n.
▲
3.2. Probleme în logica propoziţiilor: validitate, satisfiabilitateProblemele ce pot fi exprimate în logica propoziţiilor au de-a face cu valoarea de adevăra unei propoziţii.
Definiţie 3.6 (Formule valide, formule invalide). Formula P este validă în logicapropoziţiilor dacă şi numai dacă, pentru orice interpretare I, υI(P ) = A (adică formulaeste adevărată pentru orice interpretare).
Formula P este invalidă dacă şi numai dacă nu este validă, adică dacă există ointerpretare I astfel încât I, υI(P ) = F. ■Definiţie 3.7 (Formule satisfiabile, formule nesatisfiabile). Formula P este satisfiabi-lă în logica propoziţiilor dacă şi numai dacă există o interpretare I astfel încât υI(P ) = A(adică formula este adevărată pentru unele interpretări).
Formula P este nesatisfiabilă dacă şi numai dacă nu este satisfiabilă, adică pentruorice interpretare interpretare I, υI(P ) = F. ■Observaţie (Satisfiabilitate – terminologie). În literatura de specialitate în limba ro-mână, se foloseşte termenul de formulă realizabilă, respectiv formulă nerealizabilă pentruceea ce am numit mai sus formulă satisfiabilă, respectiv formulă nesatisfiabilă. ▲
Rezolvarea problemelor definite mai sus poate fi destul de laborioasă, având în vederenumărul mare de interpretări posibile. Următorul instrument va uşura reprezentareasoluţiilor problemelor definite.
Definiţie 3.8 (Tabele de adevăr). Fie P ∈ P(V). Un tabel de adevăr corespunzătorunei formule propoziţionale este un tabel construit după cum urmează:
1. Pe primul rând se listează toate variabilele propoziţionale ce apar în formulă, apoi selistează toate subformulele (de exemplu parcurgând arborele abstract corespunzătorformulei de la frunze spre rădăcină), începând cu cele mai mici, ultima fiind formulaP .
2. În coloanele corespunzătoare variabilelor propoziţionale se listează toate interpre-tările variabilelor propoziţionale:
a) prin enumerare, pornind de la valorile F,F, · · · ,F până la A,A, · · · ,A, folosindcorespondenţa F↔ 1,A↔ 1 şi faptul că o astfel de secvenţă poate fi văzută ca
29
un număr în reprezentare binară: fiecare secvenţă este obţinută din precedentaadăugând 1 la reprezentarea binară corespunzătoare;
b) prin înjumătăţire, pentru prima coloană, punem jumătate din valori (2n−1
pentru n variabile) F şi jumătate A, apoi pentru următoarea înjumătăţimfiecare secvenţă, dacă în coloana din stânga avem o secvenţă de valori F,atunci în coloana curentă punem jumătate din ele F şi jumătate A, pânăcând, pe ultima coloană avem alternanţă F,A.
De notat că ambele metode vor genera aceeaşi secvenţă de intepretări corespunză-toare variabilelor.
3. În coloanele corespunzătoare subformulelor compuse vom pune valoarea subformuleisub interpretarea corespunzătoare fiecărei linii. În mod convenabil, dacă fiecare liniese completează de la stânga la dreapta, valorile componentelor se pot lua din tabel.
■Exemplul 3.3 (Tabel de adevăr). Tabelul de adevăr (P ⇒ Q) ∨R.
P Q R P ⇒ Q (P ⇒ Q) ∨R
F F F T TF F T T TF T F T TF T T T TT F F F FT F T F TT T F T TT T T T T
Conform definiţiilor de mai sus, (P ⇒ Q) ∨R este satisfiabilă şi nevalidă.▲
Observaţie. În ciuda aparenţelor, tabelele de adevăr nu sunt mai eficiente (din punctde vedere al numărului de paşi) în comparaţie cu paşii descrişi de Definiţia 3.4. Numărulde paşi este exact acelaşi, doar reprezentarea este mai compactă. ▲
3.3. Probleme în logica propoziţiilor: echivalenţa logicăAl doilea tip de probleme în logica propoziţiilor consideră relaţiile dintre valoarea pro-poziţiilor. În primul rând dacă două propoziţii diferite au acelaşi înţeles.
Definiţie 3.9 (Echivalenţă logică). Fie P,Q ∈ P(V). Propoziţiile P şi Q sunt echi-valente logic, şi scriem P ∼ Q dacă şi numai dacă, pentru orice interpretare I,υI(P ) = υI(Q). ■Exemplul 3.4. Considerăm formulele (P ⇒ Q) şi (¬P ∨Q).
30
P Q (P ⇒ Q) ¬P (¬P ∨Q)
F F A A AF A A A AA F F F FA A A F A
Conform definiţiei, din tabelul de adevăr, vedem că cele două formule sunt logic echi-valente. ▲
Formulele propoziţionale pot avea structură diferită, dar acelaşi înţeles. Aceasta esteintuiţia din spatele conceptului de echivalenţă logică.
Vom extinde limbajul logicii propoziţiilor adăugând două simboluri speciale care vordenota două propoziţii atomice particulare.
Definiţie 3.10 (Formula falsă, formula adevărată). ⊥,⊤ ∈ P(V), unde pentru oriceinterpretare I,
• υI(⊥) = F
• υI(⊤) = A.
⊥ este formula (întotdeauna) falsă (contradicţia), ⊤ este formula (întotdeau-na) adevărată (tautologia).
■Observaţie.
• F ∼ ⊥ dacă şi numai dacă F este nesatisfiabilă.
• F ∼ ⊤ dacă şi numai dacă F este validă.
▲
Un catalog de formule logic echivalenteÎn cele ce urmează, fie F,G,H ∈ P(V) formule propoziţionale.
• Legi de reducere:
(a) (F ⇔ G) ∼ (F ⇒ G) ∧ (G⇒ F ),(b) (F ⇒ G) ∼ (¬F ∨G).
• Legi comutative:
(a) F ∨G ∼ G ∨ F ,(b) F ∧G ∼ G ∧ F ,
(c) F ⇔ G ∼ G⇔ F .
31
• Legi asociative:(a) (F ∨G) ∨H ∼ F ∨ (G ∨H),(b) (F ∧G) ∧H ∼ F ∧ (G ∧H),(c) (F ⇔ G)⇔ H ∼ F ⇔ (G⇔ H).
• Legi distributive:
(a) F ∨ (G ∧H) ∼ (F ∨G) ∧ (F ∨H),(b) F ∧ (G ∨H) ∼ (F ∧G) ∨ (F ∧H),
(c) (F ∨G)⇒ H ∼ (F ⇒ H) ∧ (G⇒ H),(d) (F ∧G)⇒ H ∼ (F ⇒ H) ∨ (G⇒ H),(e) F ⇒ (G ∨H) ∼ (F ⇒ G) ∨ (F ⇒ H),(f) F ⇒ (G ∧H) ∼ (F ⇒ G) ∧ (F ⇒ H),(g) (F ∧G)⇒ H ∼ F ⇒ (G⇒ H).
• Legi pentru „adevărat” şi „fals”:
(a) ¬⊤ ∼ ⊥,(b) ¬⊥ ∼ ⊤,(c) F ∨ ⊥ ∼ F ,(d) F ∧ ⊤ ∼ F ,(e) F ∨ ⊤ ∼ ⊤,(f) F ∧ ⊥ ∼ ⊥,(g) ⊥ ⇒ F ∼ ⊤,(h) F ⇒ ⊤ ∼ ⊤.
• Reguli de idempotenţă:
(a) F ∧ F ∼ F ,(b) F ∨ F ∼ F .
• Reguli de absorbţie (subsumpţie):
(a) F ∨ (F ∧G) ∼ F ,(b) F ∧ (F ∨G) ∼ F .
• Reguli de anihilare:
(a) F ∨ ¬F ∼ ⊤, („tertium non datur”)(b) F ∧ ¬F ∼ ⊥,
(c) F ⇒ F ∼ ⊤.
32
• Reguli pentru negaţie:
(a) ¬(¬F ) ∼ F , („negaţie dublă”)(b) ¬(F ∨G) ∼ ¬F ∧ ¬G, („De Morgan”)(c) ¬(F ∧G) ∼ ¬F ∨ ¬G, („De Morgan”)
(d) ¬(F ⇒ G) ∼ F ∧ (¬G),(e) ¬(F ⇔ G) ∼ F ⇔ (¬G).
• Alte reguli:(a) F ⇒ G ∼ F ⇔ (F ∧G),(b) F ⇒ G ∼ G⇔ (F ∨G).
Faptul că aceste echivalenţe au loc este lăsat ca exerciţiu cititorilor.
3.4. Probleme în logica propoziţiilor: consecinţă logicăNe interesează dacă o anumită propoziţie are o valoare care depinde de valoarea altorpropoziţii.
Definiţie 3.11 (Consecinţă logică în logica propoziţiilor). Fie F1, . . . , Fn, G ∈ P(V),propoziţii. G este o consecinţă logică a propoziţiilor F1, . . . , Fn, şi notăm F1, . . . , Fn ⊨ Gdacă şi numai dacă pentru orice interpretare I, dacă
υI(F1) = . . . = υI(Fn) = A,
atunci υI(G) = A. ■Exemplul 3.5. F, F ⇒ G ⊨ G. Construim următorul tabel:
F G F ⇒ G
F F AF A AA F FA A A
Conform definiţiei, tabelul arată că avem consecinţă logică.▲
Teorema de deducţie
Teorema 3.1 (Teorema de deducţie pentru logica propoziţiilor).Fie F1, . . . , Fn, G ∈ P(V), formule propoziţionale.
F1, . . . , Fn ⊨ G dacă şi numai dacă ((F1 ∧ . . . ∧ Fn)⇒ G) este validă.
33
Demonstraţie. “⇒”(implicaţia directă).
Pentru implicaţia directă (dacă),
presupunem F1, . . . , Fn ⊨ G şi
demonstrăm că ((F1 ∧ . . .∧ Fn)⇒ G) este validă, adică, conform definiţiei validităţii,pentru orice interpretare I,
υI(((F1 ∧ . . . ∧ Fn)⇒ G)) = A.
Pentru a demonstra aceasta, luăm o interpretare arbitrar fixată I0 şi demonstrăm
υI0(((F1 ∧ . . . ∧ Fn)⇒ G)) = A.
Din definiţia valorii unei propoziţii sub interpretare,
υI0(((F1 ∧ . . . ∧ Fn)⇒ G)) =B⇒(υI0((F1 ∧ . . . ∧ Fn)), υI0(G)) =B⇒(B∧(υI(F1), . . . , υI0(Fn)), υI0(G)),
adică trebuie să demonstrăm
B⇒(B∧(υI0(F1), . . . , υI0(Fn)), υI0(G)) = A. (⋆)
Avem două cazuri:
Caz: υI0(F1) = . . . = υI0(Fn) = A.Din moment ce F1, . . . , Fn ⊨ G, conform definiţiei consecinţei logice, υI0(G) = Aşi
B∧(υI0(F1), . . . , υI0(Fn)) = A, astfel că (⋆) este adevărată (B⇒(A,A) = A).
Caz: nu avem (υI0(F1) = . . . = υI0(Fn) = A) (cel puţin o valoare este falsă).B∧(υI0(F1), . . . , υI0(Fn)) = F, astfel că (⋆) este adevărată (B⇒(F, υI0(G)) = A).
Demonstraţie.“⇐”(implicaţia inversă).Pentru a demonstra implicaţia inversă,
presupunem că ((F1 ∧ . . . ∧ Fn)→ G) este validă şidemonstăm F1, . . . , Fn ⊨ G.
Pentru aceasta, conform definiţiei, considerăm o interpretare arbitrar fixată I0,presupunem υI0(F1) = . . . = υI0(Fn) = A şidemonstrăm υI0(G) = A.
34
Din presupunerea făcută ştim în particular că
υI0(((F1 ∧ . . . ∧ Fn)⇒ G)) = A.
DarυI0(((F1 ∧ . . . ∧ Fn)⇒ G)) =B⇒(υI0((F1 ∧ . . . ∧ Fn)), υI0(G)) =B⇒(B∧(υI0(F1), . . . , υI0(Fn)), υI0(G)) =B⇒(B∧(A, . . . ,A), υI0(G)) =B⇒(A, υI0(G)),
deci, B⇒(A, υI0(G)) = A.
Din definiţia funcţiei de adevăr B⇒ avem că υI0(G) = A.
Exemplul 3.6. Reluând Exemplul 3.5, folosind teorema de deducţie:
F G F ⇒ G F ∧ (F ⇒ G) (F ∧ (F ⇒ G))⇒ G
F F A F AF A A F AA F F F AA A A A A
▲Teorema 3.2 (Caracterizare alternativă a consecinţei logice).
Fie F1, . . . , Fn, G ∈ P(V), formule propoziţionale.F1, . . . , Fn ⊨ G iff (F1 ∧ . . . ∧ Fn ∧ ¬G) este nesatisfiabilă.
Demonstraţie. Exerciţiu.
Teorema 3.3 (Caracterizarea echivalenţei logice). Fie F,G ∈ F(V) propoziţii. AtunciF ∼ G dacă şi numai dacă (F ⇔ G).
Demonstrație. Exerciţiu.
Observaţie (Semnificaţia teoremei de deducţie). Teoremele de mai sus sunt semnifica-tive în sensul în care simplifică rezolvarea problemelor din logica propoziţiilor cu ajutorultabelelor de adevăr:
• orice echivalenţă logică se reduce la validitatea unei formule, ceea ce înseamnă căîn loc să se compare două coloane într-un tabel de adevăr (corespunzătoare celordouă formule), se verifică doar dacă coloana corespunzătoare echivalenţei conţinedoar valoarea A;
35
• orice consecinţă logică se reduce validitatea sau nesatisfiabilitatea unei formule, ceeace înseamnă că se verifică doar dacă o coloană (corespunzătoare unei implicaţii,respectiv unei conjuncţii) conţine doar o anumită valoare de adevăr (A, respectivF), în loc să se caute în tabel linii în care anumite elemente au valoarea A.
Teoremele de mai sus arată că orice problemă din logica propoziţiilor se poate reduce lavaliditate (sau nesatisfiabilitate).
▲
3.5. Limitările abordării directe (semantice)Soluţiile bazate pe abordarea semantică (valoare sub interpretare, tabele de adevăr)reprezintă o abordare directă, în sensul discutat în Capitolul 1. Pentru a rezolva oproblemă lucrăm cu obiectele domeniului de interes, valorile de adevăr. Am discutatlimitările abordării directe. În cazul logicii propoziţionale, având în vedere că domeniulde interes este unul foarte simplu, cu două obiecte, am văzut că pentru orice proble-mă putem găsi o soluţie în timp finit (pentru că avem de verificat un număr finit deposibilităţi – interpretări). Logica propoziţională este decidabilă!
Cu toate acestea, abordarea directă nu este o idee bună dincolo de cele mai simpleprobleme. Să considerăm tabelul următor, preluat din [KT06]:
n nlog2n n2 n3 1.5n 2n n!n = 10 < 1 sec < 1 sec < 1 sec < 1 sec < 1 sec < 1 sec 4 secn = 30 < 1 sec < 1 sec < 1 sec < 1 sec < 1 sec 18 min 1025 anin = 50 < 1 sec < 1 sec < 1 sec < 1 sec 11 min 36 ani f. lungn = 100 < 1 sec < 1 sec < 1 sec 1 sec 12892 ani 1017 ani f. lungn = 1000 < 1 sec < 1 sec 1 sec 18 min f. lung f. lung f. lungn = 10000 < 1 sec < 1 sec 2 min 12 zile f. lung f. lung f. lungn = 100000 < 1 sec 2 sec 3 hours 32 ani f. lung f. lung f. lungn = 1000000 1 sec 20 sec 12 zile 31710 ani f. lung f. lung f. lung
Prima coloană reprezintă mărimea unei probleme, celelalte reprezintă estimarea tim-pului necesar pentru obţinerea soluţiei în următoarele condiţii pentru clasa corespunză-toare de complexitate (din capul coloanei):
• timpul de execuţie este estimat pentru un procesor capabil de 1 milion de instru-cţiuni pe secundă (MIPS),
• „f. lung” este considerat un timp de execuţie care depăşeşte 1025 ani.
Soluţiile directe în logica propoziţiilor au complexitatea 2n, ceea ce înseamnă că pentruorice problemă netrivială, calculatoarele vor fi compleşite, şi calcularea răspunsurilor valua prea mult timp.
Pentru comparaţie, procesoarele curente sunt capabile să efectueze mult mai multeoperaţii (aprox 300 000 MIPS1 .). Chiar şi cu această diferenţă, observaţi că pentruprobleme netriviale (mai mult de 100 de variabile) timpul de aşteptare este nerezonabil.
1Vezi http://en.wikipedia.org/wiki/Instructions_per_second
36
Avem nevoie de un mod diferit pentru a rezolva problemele în logica propoziţiilor, deun sistem de raţionament.
37
4. Aplicaţii ale logicii propoziţiilor:proiectarea circuitelor digitale
Înainte de a investiga raţionamentul în logica propoziţiilor, vom discuta aplicaţii alelogicii propoziţiilor în practică.
4.1. Logica propoziţiilor descrie funcţiile de adevăr4.1.1. Conjuncţii şi disjuncţii de formuleObservaţie. Pe baza legilor de asociativitate prezentate în catalogul de formule logicechivalente introduse în Secţiunea 3.3, putem renunţa la paranteze, de exemplu în (F ∨G)∨H sau în F∨(G∨H). În acest sens, vom extinde limbajul (sintaxa şi semantica). ▲Definiţie 4.1 (Conjuncţie de formule). Fie F1, . . . , Fn ∈ P(V) formule propoziţionale.Atunci F1 ∧ . . .∧ Fn ∈ P(V), unde n ≥ 1. Formula se cheamă conjuncţia formulelorF1, . . . , Fn.
Valoarea formulei sub interpretarea I este:
υI(F1 ∧ . . . ∧ Fn) = B∧(υI(F1), . . . , υI(Fn)),
undeB∧(x1, . . . , xn) =
{A, dacă x1 = . . . = xn = AF, altfel .
■Definiţie 4.2 (Disjunction of formulae). Fie F1, . . . , Fn ∈ P(V) formule propoziţionale.Atunci F1 ∨ . . . ∨ Fn ∈ P(V), unde n ≥ 1. Formula se cheamă disjuncţia formulelorF1, . . . , Fn.
Valoarea formulei sub interpretarea I este:
υI(F1 ∨ . . . ∨ Fn) = B∨(υI(F1), . . . , υI(Fn)),
undeB∨(x1, . . . , xn) =
{F, dacă x1 = . . . = xn = FA, altfel .
■Conjuncţiile şi disjuncţiile cu număr arbitrar de argumente sunt o extensie naturală a
propoziţiilor corespunzătoare cu două componente.
38
Observaţie (Conjuncţii şi disjuncţii cu o componentă). Dacă în definiţiile de maisus n = 1, conjuncţia, respectiv disjuncţia cu o singură componentă se identifică cucomponenta respectivă. ▲
4.1.2. Funcţii booleene descrise de formule propoziţionaleFie V mulţimea variabilelor propoziţionale. Să considerăm domeniul de valori de adevăr{A,F}, şi fie a1, a2 . . . ∈ {A,F} şi A1, A2 . . . ∈ V. Formulele propoziţionale descriu funcţiide adevăr într-un mod natural.
Definiţie 4.3 (Funcţii de adevăr descrise de formule propoziţionale.). Fie F ∈ P(V)o formulă propoziţională. Fie A1, . . . , An ∈ V atomii ce apar în F . Atunci funcţia deadevăr descrisă de formula F , [F ]n este definită după cum urmează:
[F ]n : {A,F}n −→ {A,F},[F ]n(A1, . . . ,An) = υT (F ),pentru toate interpretările I, unde 1 ≤ i ≤ n.
■Observaţie. Funcţia de adevăr descrisă de o formulă propoziţională poate fi extrasădin tabelul de adevăr corespunzător formulei: argumentele sunt interpretările, valoareareturnată se citeşte de pe ultima coloană a tabelului. ▲
Definiţia ne spune că formulele propoziţionale pot descrie unele funcţii de adevăr, dareste limbajul suficient de expresiv pentru a descrie orice funcţie de arevăr? Răspunsuleste pozitiv.
Teorema 4.1. Pentru orice funcţie de adevăr cu n argumente f : {A,F}n −→ {A,F}există o formulă propoziţională F astfel încât f = [F ]n.
Demonstrație. Fie f funcţia booleană cu n argumente, şi
(a11, . . . , an
1), (a12, . . . , an
2), . . . , (a1m, . . . , an
m)
perechile de n elemente din {A,F}n pentru care f returnează valoarea A. Atunci funcţia f poateeste descrisă de următoarea formulă, ce foloseşte variabilele A1, . . . , An:
F = C(a11,...,an
1) ∨ C(a12,...,an
2) ∨ . . . ∨ C(a1l,...,an
l),
unde C(a11,...,an
1) = A1a1 ∧ . . . ∧An
an , şi Aia =
{Ai dacă a = A¬Ai altfel
.
Prin construcţie, formula F este astfel încât [F ]n = f .
Construcţia formulei ce descrie o funcţie dată porneşte de la tabelul ce reprezintă intrările şiieşirile funcţiei:
• se identifică valorile pentru care funcţia returnează A,
• pentru fiecare astfel de linie se construieşte conjuncţia corespunzătoare,
39
• se ia disjuncţia conjuncţiilor rezultate.
Exemplul 4.1 (Funcţia majoritate). Să considerăm funcţia majoritate cu trei argumente, cereturnează A dacă majoritatea argumentelor sale este A, descrisă de următorul tabel:
a1 a2 a3 f(a1, a2, a3)A A A AA A F AA F A AA F F FF A A AF A F FF F A FF F F F
Formula corespunzătoare lui f este:
F = (A1 ∧A2 ∧A3) ∨ (A1 ∧A2 ∧ ¬A3) ∨ (A1 ∧ ¬A2 ∧A3) ∨ (¬A1 ∧A2 ∧A3).
▲Aşadar, am stabilit că logica propoziţiilor este un limbaj suficient de expresiv pentru a descrie
funcţiile de adevăr.
4.2. Designul şi tranformarea circuitelor digitale4.2.1. Circuite digitaleDefiniţie 4.4 (Circuite digitale). Circuitele digitale sunt circuite electronice ale căror intrărişi ieşiri sunt semnale electrice de voltaje diferite, de obicei distingându-se 2 valori (voltaj ridicatsau voltaj scăzut). Circuitele digitale combinatoriale sunt circuite digitale ale căror ieşirisunt determinate exclusiv de valorile de intrare. ■
Exemple de circuite digitale: circuite aritmetic-logice (combinatoriale), circuite de memorie(acestea nu sunt combinatoriale, deoarece ieşirea nu depinde doar de intrare, ci şi de valoareastocată în circuit).
Din moment ce avem două valori distincte pe intrările/ieşirile circuitelor, le putem identificacu valorile de adevăr (de exemplu A pentru voltaj înalt şi F pentru voltaj scăzut).
Mai mult, fiecare circuit combinatorial poate fi văzut ca o funcţie de adevăr. Aşadar, putemfolosi logica propoziţională pentru a descrie circuitele combinatoriale. Acest fapt a fost remarcatde Claude E. Shannon şi descris în teza sa de masterat („posibil cea mai importantă şi cea maifaimoasă teza de masterat a secolului” XX), publicată mai târziu ca [Sha38], şi care a avut unimpact major în dezvoltarea calculatoarelor.
Circuitele digitale sunt implementate folosind porţi logice – dispozitive electronice simple,ce corespund conectorilor logici de bază în logica propoziţiilor.
Exemplul 4.2 (Porţi logice). În Figura ?? (sursă: resurse didactice din [TA13]) 0 şi 1 suntfolosite pentru F şi T, respectiv. ▲
4.2.2. Designul circuitelor digitaleCircuitele digitale combinatoriale sunt construite după cum urmează:
40
Figura 5.: Porţi logice: negaţie, nşi (negaţia conjuncţiei), nsau (negaţia disjuncţiei),conjuncţie, disjuncţie.
• Se porneşte cu funcţia de adevăr, descrisă sub forma unui tabel. Aceasta poate fi conside-rată specificaţia circuitului, pentru că descrie comportamentul circuitului.
• Se construieşte formula corespunzătoare funcţiei de adevăr. Aceasta va fi o disjuncţiede conjuncţii de atomi sau negaţii ale unui atom. Această formulă reprezintă designulcircuitului.Pentru reprezentarea circuitului:
– se reprezintă câte o linie pentru fiecare intrare (orizontal),– pentru fiecare din acestea se leagă o linie pe care se pune o poartă logică negaţie,– fiecare dintre intrări şi negaţiile acestora se leagă la o linie corespunzătoare (verticală),– pentru fiecare conjuncţie din formula corespunzătoare, se ia o poartă şi, care se leagă
la intrările corespunzătoare din liniile verticale,– ieşirile din porţile şi devin intrare într-o poartă sau, a cărei ieşire reprezintă ieşirea
din circuit.
Exemplul 4.3 (Circuitul majoritate). Funcţia majoritate returnează A dacă majoritatea in-trărilor au valoarea A. Designul circuitului corespunzător este prezentat în Figura 4.3.
Figura 6.: Circuitul majoritate. Sursă: resurse didactice asociate cu [TA13]. 0 şi 1 suntfolosite pentru F and A, respectiv, A pentru ¬A, ABC reprezintă A∧B ∧C,A+B reprezintă A ∨B.
▲
41
4.2.3. Transformarea şi simplificarea circuitelor digitaleÎn practică, designul circuitelor obţinute din specificaţie (funcţia de adevăr) nu este folosit: porţilogice cu număr variabil de intrări nu sunt practice, circuitele vor folosi porţi logice standard, deexemplu porţi şi/sau cu două intrări.
Pentru a înlocui porţile cu număr variabil de intrări, circuitul se transformă folosind echivalenţalogică (de exemplu regulile de distributivitate, etc).
Mai mult, din motive de performanţă, circuitele trebuie să fie cât mai simple (să folosească unnumăr cât mai mic de porţi logice, să aibă o adâncime cât mai mică). Transformările echivalentesunt folosite şi în acest scop. Figura ?? ilustrează un astfel de caz.
Figura 7.: Circuit simplification.
Exemplul 4.4 (Simplificarea circuitelor (reducerea numărului de porţi logice)). Simplificareacircuitelor prin transformări echivalente. Sursă: resurse didactice asociate cu [TA13]. ▲Exemplul 4.5. Reluând formula care descrie circuitul majoritate de la Exemplul 4.1:
(A1 ∧A2 ∧A3) ∨ (A1 ∧A2 ∧ ¬A3) ∨ (A1 ∧ ¬A2 ∧A3) ∨ (¬A1 ∧A2 ∧A3) ∼
((A1 ∧A2) ∧ (A3 ∨ ¬A3)) ∨ (((A1 ∧ ¬A2) ∨ (¬A1 ∧A2)) ∧A3)) ∼
((A1 ∧A2) ∧ ⊤) ∨ (((A1 ∧ ¬A2) ∨ (¬A1 ∧A2)) ∧A3)) ∼
(A1 ∧A2) ∨ (((A1 ∧ ¬A2) ∨ (¬A1 ∧A2)) ∧A3)).
▲
4.2.4. Mulţimi complete de conectori logiciDefiniţie 4.5 (Mulţimi complete de conectori logici). Fie M o mulţime de conectori logici.Spunem că M este o mulţime completă de conectori logici dacă şi numai dacă pentru oriceF ∈ P(V) există G ∈ P(V) astfel încât F ∼ G şi G foloseşte doar conectori din M. ■Exemplul 4.6 (Mulţimi complete de conectori logici). Următoarele sunt mulţimi complete deconectori logici:
1. {¬,∧,∨,⇒,⇔} (prin definiţie),
2. {¬,∧,∨} (pentru orice formulă, construim tabelul şi din tabel construim formula cores-punzătoare care este o disjuncţie de conjuncţii de atomi sau negaţii ale acestora),
3. {¬,∧} (exerciţiu),
4. {¬,∨} (exerciţiu),
5. {⊥,⇒} (exerciţiu),
6. {|} unde F |G = ¬(F ∧G), | este conectorul nşi,
42
7. {▽}, unde F▽G = ¬(F ∨G), ▽ este conectorul „nsau” (exerciţiu).Vom demonstra că {|} este completă prin inducţie după structura formulelor:Cazul de bază: Dacă A este atom, atunci A ∼ A.Pasul de inducţie: Fie F şi G propoziţii arbitrare. Presupunem că pentru cele două pro-
prietate este adevărată.Demonstrăm proprietatea pentru:
• ¬F :¬F ∼ ¬(F ∧ F ) ∼ F |F ,
• F ∧G:F ∧G ∼ ¬¬(F ∧G) ∼ ¬(F |G) ∼ (F |G)|(F |G),
• F ∨G:F ∨G ∼ ¬¬(F ∨G) ∼ ¬(¬F ∧ ¬G) ∼ (¬F )|(¬G) ∼ (F |F )|(G|G).
• F ⇒ G: exerciţiu,• F ⇔ G: exerciţiu,• ⊥:⊥ ∼ (F ∧ ¬F ) ∼ . . . (exerciţiu),
• ⊤: exerciţiu.
▲Faptul că există mulţimi complete de conectori logici cu un singur element este important
pentru aplicaţia logicii propoziţiilor în domeniul circuitelor digitale: circuitele pot fi realizatefolosind un singur tip de poartă logică, ceea ce simplifică semnificativ construcţia acestora. Folo-sind transformările echivalente, designul unui circuit este transformat într-un circuit echivalentce foloseşte un singur tip de poartă logică.
43
5. Raţionament în logica propoziţiilor
5.1. Forme normaleNegation Normal FormDefinition 1 (Literal). A literal is an atom or the negation of an atom. Atoms are calledpositive literals, negations of atoms are called negative literals.
Definition 2 (Negation Normal Form). A formula F is said in negation normal form (NNF) ,iff:
• F is ⊤ or F is ⊥;
• F is constructed from literals, using only the binary connectives ’∧’ and ’∨’.
Example 3. Let P, Q, R, S be atoms. The following are in NNF:
⊤,
P ,
P ∧ (Q ∧ (¬R ∨ S)),
however,¬(¬P ),
¬(P ∨ ¬Q) ∧R,
are not.
Transformation to NNFRemark. Any propositional logic formula can be transformed into an equivalent formula inNNF.
Transformation to NNF
1. use the reduction laws (given in the catalog of equivalent formulae) to eliminate ’↔’, ’→’;
2. repeatedly use the double negation and De Morgan’s laws to eliminate ’¬¬’s and ’¬(. . .)’s.
3. at each of the steps above, it is useful to perform simplifications of ⊤ and ⊥ (using thelaws of true and false, annihilation, idempocy).
44
Disjunctive Normal Form, Conjunctive Normal FormDefinition 4 (Disjunctive Normal Form). A formula F is said to be in disjunctive normal form(DNF) iff F has the form F
.= F1 ∨ . . . ∨ Fn, n ≥ 1 , and each of F1, . . . , Fn is a conjunction of
literals.
Example 5 (Formulae in DNF). Let P,Q,R be atoms,
(¬P ∧Q) ∨ (P ∧ ¬Q ∧ ¬R)
P ,
P ∧Q,
P ∨Q ∨R,
are in DNF.Remark. Any formula which is in DNF is also in NNF.
Definition 6 (Conjunctive Normal Form). A formula F is said to be in conjunctive normal form(CNF) iff F has the form F
.= F1 ∧ . . . ∧ Fn, n ≥ 1 , and each of F1, . . . , Fn is a disjunction of
literals.
Example 7 (Formulae in CNF). Let P,Q,R be atoms,
(¬P ∨Q) ∧ (P ∨ ¬Q ∨ ¬R)
P ,
P ∧Q,
P ∨Q ∨R,
are in CNF.Remark. Any formula which is in CNF is also in NNF.
Normal Form TransformationsSo far, we have seen that any formula can be transformed into its NNF equivalent, then
defined DNF, CNF. The question now is how to transform the formula from NNF into DNF (orCNF) and if we can do that, what does that tell us? For once, if two formulae have the samenormal form, they are equivalent, but, does it help in detecting tautologies, satisfiable formulae,unsatisfiable formulae? And is it better than truth tables?
DNF TransformationsDNF Transformation via Truth TablesGiven a formula, one method to obtain a DNF equivalent formula is through truth tables, by:
• selecting all the rows that evaluate to T,
• for each such row, constuct a conjunct of literals in the following way: positive literals forcorresponding T values for the propositional variable, and negative literals otherwise.
• the DNF is the disjunctions of all these conjunctions.
Example 8. DNF from truth tables
45
P Q P → QT T TT F FF T TF F T
The corresponding equivalent DNF formula:(P ∧Q) ∨(¬P ∧Q) ∨ (¬P ∧ ¬Q).
Remark.
• In the above example, the DNF equivalent form is quite different from the well-knownequivalent (¬P ∨Q), i.e. it is not the simplest DNF (also DNF’s are not unique).
• In general, getting the DNF from the truth table is expensive: one has to construct thetruth tables.
DNF Transformation
Transformation to DNFAn arbitrary propositional formula can be transformed in an equivalent DNF by carrying outthe following steps:
• bring the formula into NNF;• repeatedly apply the tautologies:
F ∧ (G ∨H) ∼ (F ∧G) ∨ (F ∧H),
(F ∨G) ∧H ∼ (F ∧H) ∨ (G ∧H),starting with the outermost ’∧’, until the normal form is reached.
Example 9 (DNF transformation). Transform the following formula into its DNF:
(F ∧ (G ∨H)) ∧ (¬F ∨ ¬G).
The formula is already in NNF.
(F ∧ (G ∨H)) ∧distr
(¬F ∨ ¬G) ∼(((F ∧ (G ∨H)) ∧
distr¬F ) ∨ ((F ∧ (G ∨H)) ∧
distr¬G)) ∼
(((F ∧G) ∨ (F ∧H)) ∧distr¬F ) ∨ ((F ∧G) ∨ (F ∧H)) ∧
distr¬G)) ∼
(((F ∧G ∧ ¬F )ann
∨ (F ∧H ∧ ¬F ))ann
∨ ((F ∧G ∧ ¬G)ann
∨ (F ∧H ∧ ¬G))) ∼
(⊥ ∨⊥ ∨⊥(F ∧H ∧ ¬G)) ∼(F ∧H ∧ ¬G).
Remark. In the above, distr, ann indicate the place where the distributive law (of ’∧’ over ’∨’)and the annihilation law (for ’∧’) were applied, respectively, at each step.
When transforming a formula into its DNF equivalent, it is a good idea to perform, after eachtransformation, simplification steps:
• contradictions within conjunctions:– if both a subformula and its negation show up in the same conjunction, then the
conjunction is a contradiction (i.e. equivalent to ⊥),– since P ∨ ⊥ ∼ P , contradictions can be discarded;
46
• subsumption:– since (F ∧ G) ∨ F ∼ (F ∨ F ) ∧ (G ∨ F ) ∼ F ∧ (G ∨ F ), we see that if F is true
then the initial formula is true, and if F is false then the initial formula is false (readevaluated to false under some interpretation), i.e. the truth value of G plays no partin the result of the evaluation,
– therefore, in fact (F ∧G) ∨ F ∼ F ,– therefore, (F ∧G) can be safely removed from the disjunct (we say that (F ∧G) is
subsumed by F ),– due to the associativity of ’∧’ this can be generalized (i.e. F and G can stand in for
conjunctions of literals).Example 10 (DNF transformation, with contradiction checking.). Transform the following for-mula into its DNF:
(F ∧ (G ∨H)) ∧ (¬F ∨ ¬G).
(F ∧ (G ∨H)) ∧distr
(¬F ∨ ¬G) ∼(((F ∧ (G ∨H)) ∧ ¬F )
assoc and ann
∨ ((F ∧ (G ∨H)) ∧distr¬G)) ∼
((F ∧G) ∨ (F ∧H)) ∧distr¬G)) ∼
((F ∧G ∧ ¬G)ann
∨ (F ∧H ∧ ¬G))) ∼
(F ∧H ∧ ¬G).Remark. Note that applying after each transformation a check for contradiction (i.e. lookingto apply the annihilation law for ’∧’) can lead to much shorter derivations.
DNF and satisfiability• Given a formula in DNF, the formula is satisfiable precisely if one of its disjuncts is
satisfiable,• a DNF disjunct (which is a conjunction) is satisfiable precisely if it does not contain
complementary literals,• therefore, transformation into DNF represents a method to establish satisfiablity of pro-
positional formulae,• however, in general, DNF does not offer a simple way to establish validity.
CNF Transformation
Transformation to CNFAn arbitrary propositional formula can be transformed in an equivalent DNF by carrying outthe following steps:
• bring the formula into NNF;• repeatedly apply the tautologies:
F ∨ (G ∧H) ∼ (F ∨G) ∧ (F ∨H),
(F ∧G) ∨H ∼ (F ∨H) ∧ (G ∨H),starting with the outermost ’∨’, until the normal form is reached.
47
When transforming into CNF, one should check at each step for valid conjuncts, i.e. disjunc-tions that contain complementary subformulae.
• validity within conjunctions:– if both a subformula and its negation show up in the same disjunction, then the
disjunction is a valid (i.e. equivalent to ⊤),– since P ∨ ⊤ ∼ P , valid conjuncts can be discarded;
• absorbtion:– F ∧ (F ∨G) ∼ F .
Remark. DNF and CNF transformations are similar.Example 11 (CNF transformation). Transform the following formula into its CNF:
(F ∨ (G ∧H)) ∨ (¬F ∧ ¬G).The formula is already in NNF.
(F ∨ (G ∧H)) ∨distr
(¬F ∧ ¬G) ∼(((F ∨ (G ∧H)) ∨ ¬F )
assoc and ann
∧ ((F ∨ (G ∧H)) ∨distr¬G)) ∼
((F ∨G) ∧ (F ∨H)) ∨distr¬G)) ∼
((F ∨G ∨ ¬G)ann
∧ (F ∨H ∨ ¬G))) ∼
(F ∨H ∨ ¬G).
CNF and validity• Given a formula in CNF, the formula is valid iff each conjunct is valid,• i.e. each disjunction contains complementary literals.• If discarding of valid conjuncts is performed, then a formula is valid iff its CNF equivalent
is ⊤.• However, in general, it is not easy to establish satisfiability, given a CNF formula.• In fact, the SAT problem (boolean satisfiability problem) is formulated as the decision
whether a CNF formula is satisfiable,• and SAT is the first problem proved to be NP complete (see [H.G03], pp. 50–54 for a
discussion on NP and SAT).
DNF and CNF: Sharing Transformations• due to the De Morgan laws, the CNF of a formula can be obtained directly from the DNF
of its negation, by switching ’∧’s for ’∨’s, and complementing the literals (i.e. positiveliterals become negative, and vice-versa).
• this allows sharing code for the normal form transformations, if these are implemented ona computer.
• Start with a formula, and its negation,• bring them both to equivalent NNF,• then transform them both to DNF,• and finally, flip the ’∧’s and ’∨’s in the DNF of the negation, and then complement the
literals.
48
5.2. Metoda rezoluţiei şi metode bazate pe rezoluţie
49
Partea III.
Logica predicatelor
50
Logica predicatelor de ordinul întâi: sintaxăşi semanticăLogica predicatelor este limbajul matematicii. Chiar şi o versiune restrânsă pe care o vom discutaaici – logica predicatelor de ordinul întâi – este suficientă (împreună cu teoria mulţimilor) pentrua exprima tot ce se poate exprima în matematică.
Totodată, este într-un anumit sens cel mai bine înţeleasă – munca de fundamentare a mate-maticii (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 pentru informa-tică (matematică, raţionament automat).
În ceea ce urmează, vom introduce limbajul logicii predicatelor de ordinul întâi. Vom prezentasintaxa şi semantica, vom vedea că a rezolva probleme direct folosind logica predicatelor estenepractic.
51
6. Sintaxa logicii predicatelor de ordinulîntâi
Rolul unui limbaj (în particular al limbajului considerat aici) este să descrie un univers de interes.Pentru a forma expresii avem nevoie de simboluri, care vor juca diferite roluri în expresiilelimbajului.
6.1. Expresiile logicii predicatelor de ordinul întâiDefiniţie 6.1 (Vocabularul logicii de ordinul întâi). Simbolurile limbajului logicii de ordinulîntâi sunt:
• V - mulţimea (numărabilă) de variabile obiect. Faptul că mulţimea este numărabilă neasigură 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şitul alfabetului,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 uni-
versul de interes. Pentru fiecare astfel de nume, vom ataşa aritatea, numărul deargumente a funcţiei descrise de fiecare nume.
– P - simbolurile predicative (predicate, nume de relaţii): nume pentru rela-ţii din universul de interes. Pentru fiecare astfel de predicat vom ataşa aritatea,numărul de argumente din relaţia descrisă de predicatul respectiv.
– C - simboluri constante (nume de constante): nume pentru obiecte din universulde 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 6.1 (Simboluri ale unui limbaj). Vom considera următoarea signatură L a unuilimbaj:
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 argumente).
P ={P/2,≤/2, prim/1, par/1
},
52
unde par/2 indică faptul că predicatul pentru care am ales numele par are aritate 2 (2 argumente).
C = {a, b, 0, 12} .
▲Observaţie (constantele sunt funcţii). Tehnic, simbolurile constante sunt la fel cu simbolurilefuncţionale de aritate 0. Intuitiv, o funcţie „returnează” un obiect „în funcţie” de argumentelesale, adică modificând argumentele, se modifică rezultatul. Dacă funcţia nu are argumente, atuncirezultatul nu poate fi influenţat, aşadar este neschimbat. Atunci funcţia (cu 0 argumente) se poateidentifica cu valoarea pe care o returnează. ▲
Primul tip de expresii în logica predicatelor de ordinul întâi sunt termenii, care descriu obiectedin universul de discurs.
Definiţie 6.2 (Termenii logicii predicatelor de ordinul întâi). Fie V mulţimea de variabile,L mulţimea simbolurilor (signatura) unui limbaj al predicatelor de ordinul întâi. Mulţimeatermenilor peste L şi mulţimea de variabile V, notată T(L,V) este definită după cumurmează:
• 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 simbol funcţionalaplicat unui număr corespunzător – cu aritatea sa – de termeni este la rândul său untermen.)
În primele două cazuri avem de-a face cu termeni simpli (variabilă, constantă), iar în ultimulavem termeni compuşi (din simbol funcţional aplicat altor termeni).
■Definiţie 6.3 (Simboluri dominante, subtermeni). Fie f(t1, . . . , tn) ∈ T(L,V) un termen com-pus. Spunem că f este simbol dominant al termenului compus şi t1, . . . , tn sunt subter-meni. ■
Al doilea tip de expresii în logica predicatelor de ordinul întâi sunt formulele, care intuitivdescriu relaţii, situaţii din universul de discurs.
Definiţie 6.4 (Formulele logicii predicatelor de ordinul întâi). Fie V mulţimea de variabile,L mulţimea simbolurilor (signatura) unui limbaj al predicatelor de ordinul întâi. Mulţimeaformulelor peste L şi mulţimea de variabile V, notată F(L,V) este definită după cumurmează:
• Dacă P/n ∈ P şi t1, . . . , tn ∈ T(L,V), atunci P (t1, . . . , tn) ∈ F(L,V). (Un predicat aplicatunui 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 „nu F”.
(F ∧G) ∈ F(L,V).
Conjuncţia a două formule este o formulă, se citeşte „F şi G”.
53
(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ă Fatunci G”.
(F ⇔ G) ∈ F(L,V).
Echivalenţa a două formule este o formulă, se citeşte „F echivalent cu G” sau„F dacă şi numai dacă G”.
Aceste formule, formate din alte formule legate prin conectori logici, se cheamă formulecompuse.
• 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 numesc formu-le cuantificate, respectiv formula cuantificată universal şi formula cuantificatăexistenţial.În ambele cazuri, x se zice că este variabilă legată de cuantificator (universal, respectivexistenţial), în cadrul lui F. Aşadar, cadrul unei variabile legate este locul, formula încare aceasta apare legată.O variabilă care nu este legată se cheamă variabilă liberă.
■Definiţie 6.5 (Simboluri dominante, subformule). Considerăm formulele logicii predicatelor deordinul întâi, F(L,V):
• Pentru formule atomice P (t1, . . . , tn), P este simbolul dominant şi t1, . . . , tn sunt sub-termeni.
• Pentru formulele compuse (¬F ), (F ∧ G), (F ∨ G), (F ⇒ G), (F ⇔ G), simbolurile do-minante sunt conectorii logici, respectiv ¬,∧,∨,⇒,⇔, iar F,G sunt subformule.
■
6.2. Parcurgerea expresiilor logicii predicatelor de ordinul întâiDefiniţiile 6.2 şi 6.4 oferă instrumentele pentru a recunoaşte expresiile logicii de ordinul întâi. Încontinuare vom investiga cum se pot recunoaşte şi parcurge expresiile logicii predicatelor.
54
6.2.1. Recunoaşterea expresiilor logicii predicatelor folosind definiţia sintaxeiExemplul 6.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 setermină cu paranteze, deci conform Definiţiei 6.4, trebuie să verificăm că:
(a) P (x, y) este formulă. Acest lucru se întâmplă, conform definiţiei este o formulă atomică, unpredicat binar (P ) aplicat la doi termeni, x respectiv y (care sunt variabile, deci termeni,conform Definiţiei 6.2).
(b) ∀xP (f(a), x)) este formulă. Simbolul dominant este ∀ (subliniat în formulă), urmat de ovariabilă (x), deci conform definiţiei, trebuie să verificăm că P (f(a), x) este formulă. Acestlucru se întâmplă, conform definiţiei este o formulă atomică, un preficat binar (P ) este aplicatla doi termeni, f(x), un termen compus (simbolul funcţional f aplicat termenului constantăa, şi variabilei x).
Aşadar, conform definiţiei, expresia este o conjuncţie, formulă compusă în logica predicatelorde ordinul întâi.
▲Observaţie (Subitare). Situaţia este aceeaşi cu cea identificată în Capitolul 2. Identificareasimbolurilor dominante este un pas „mare”. Oamenii pot face acest pas pentru expresii mici,folosind capacitatea de subitare. Însă pentru exemple mai complexe, avem nevoie de o metodăcare să parcurgă expresia pas cu pas şi în care identificarea componentelor să fie explicită. ▲
6.2.2. Recunoaşterea şi parcurgerea sintaxei logicii predicatelor: sintaxaabstractă
Vom adapta sintaxa abstractă introdusă pentru logica propoziţiilor, în Capitolul 2.
Definiţie 6.6 (Sintaxa abstractă a termenilor logicii predicatelor). Fie T(L,V) mulţimea ter-menilor peste un limbaj. Atunci sintaxa abstractă a termenilor este reprezentată de următoriiarbori:
• Pentru termenii simpli (variabile şi constante) x şi c:
x c
• Pentru termeni compuşi, dacă fn(t1, . . . , tn) ∈ T(L,V):
55
f
tn· · ·t1
■Definiţie 6.7 (Sintaxa abstractă a formulelor logicii predicatelor). Fie F(L,V) mulţimea for-mulelor peste un limbaj. Atunci sintaxa abstractă a formulelor este reprezentată de următoriiarbori:
• 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
■Vom adapta metoda prin care se pot recunoaşte expresiile (şi în acelaşi timp construi
arborele sintactic) introdusă pentru propoziţii.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 simbolulconsiderat. Regula ne va spune ce adăugăm la arborele incomplet, şi la ce poziţie.
Metoda se termină cu succes când am parcurs tot şirul de caractere din expresie, şi avem unarbore sintactic complet.
În orice alt caz:
56
• ş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 arbore acceptat(de Definiţiile 6.6, 6.7),
avem eşec.
Exemplul 6.3 (Recunoaşterea expresiilor logicii predicatelor şi construcţia arborelui sintactic).Pentru a ilustra această metodă, reluăm Exemplul 6.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ă. Avem 2 variante:negaţie, sau formulă ce conţine un conector binar. Arborii incompleţi corespunzători celor2 posibilităţi sunt:
„¬”
„F”
„□”
„F”„F”
În arborii de mai sus, folosim următoarele convenţii:• dacă într-un nod sau subarbore avem ghilimele („· · · ”), acestea indică faptul că î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 în arboreleincomplet, 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 pevarianta a doua.Prezenţa lui P indică faptul că avem nevoie de o formulă atomică, cu 2 subarbori:
57
„¬”
„F”
„□”
„F”P
„T”„T”
(3): ( – paranteza deschisă după P mută poziţia pe primul subarbore după al nodului ce conţineP .
„□”
„F”P
„T”„T”
(4): x – este o variabilă, deci termen, exact ce se aştepta, subarborele este închis, se mută poziţiala părinte.
„□”
„F”P
„T”x
(5): , – virgula indică faptul că ne mutăm pe următoarea ramură:
58
„□”
„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ă lapărintele acestui subarbore.
„□”
„F”P
yx
(8): ∧ – este un conector propoziţional binar, ceea ce era aşteptat, se completează şi poziţia semuta pe al doilea subarbore:
59
∧
„F”P
yx
(9): ∀ – cuantificatorul universal, vom avea nevoie de o variabilă şi de o formulă, poziţia se 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:
∧
∀
„F”x
P
yx
(11): P – este predicat binar, vrem formulă atomică, cu două subramuri, fiecare corespunzândunui termen:
60
∧
∀
P
„T”„T”
x
P
yx
(12): ( – paranteză deschisă, trecem la primul subarbore:
∧
∀
P
„T”„T”
x
P
yx
(13): f este o funcţie unară (ok, aveam nevoie de un termen), construim o ramură nouă, undeavem nevoie de un termen:
61
∧
∀
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:
62
∧
∀
P
„T”f
a
x
P
yx
(16): ) – paranteză închisă, am terminat cu subarborele ce începe cu f , ne mutăm deasupra:
∧
∀
P
„T”f
a
x
P
yx
(17): , – virgulă, coborâm pe următoarea ramură:
63
∧
∀
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:
64
∧
∀
P
xf
a
x
P
yx
(20): ) paranteză închisă, subarborele care începe la ∧ este închis, trecem la părinte (dar ∧ esterădăcină, deci am terminat, avem arborele sintactic, avem o expresie în logica predicatelor):
∧
∀
P
xf
a
x
P
yx
▲Observaţie (Cazurile cu eşec). În cazul unui eşec, metoda descrisă mai sus oferă şi motivulpentru eşec. Acesta se găseşte la pasul la care se produce eşecul. De exemplu, dacă în expresiade mai sus, P ar fi un simbol funcţional binar (şi nu un predicat), la pasul 2 inserăm un simbolfuncţional în nodul curent, ceea ce ar contrazice definiţia formulelor compuse.
▲
65
6.3. Relaxarea sintaxei (I)Metodade parcurgere şi recunoaştere a expresiilor logicii predicatelor prezentată în secţiuneaanterioară funcţionează pentru că simbolurile funcţionale şi predicative se pun înaintea argu-mentelor. În practică, vrem să scriem lucruri ca x + y, x ≤ y, unde +,≤ sunt respectiv unsimbol funcţional şi un predicat. Acest mod de a scrie lucrurile nu este acceptat conform Defi-niţiilor 6.2, 6.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, de acumînainte vom accepta o relaxare a sintaxei care să permită folosirea simbolurilor în modul indicatmai sus. Însă acest lucru trebuie făcut tinând cont de anumite aspecte ce vor fi menţionate încontinuare, 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şa se folosescsimbolurile în Definiţiile 6.2, 6.4).
Infix: simbolurile funcţionale sau predicative sunt plasate între argumente. De obicei acest modde scriere este folosit pentru simboluri de funcţii şi predicate binare: x+ y, x ≤ y. Un cazparticular de simbol infix este cel din expresia xy. Simbolul corespunzător este □□, unde□ reprezintă poziţiile argumentelor.
Postfix: simbolurile funcţionale sau predicative sunt plasate după argumente. De obicei, acestmod 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ă. De exem-plu: x
y , n√x. De remarcat că în aceste cazuri, simbolurile funcţionale corespunză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 daca funcţia este asociativă ladreapta, 8/(2/2) înseamnă 8. În acest caz este esenţial să se precizeze asociativitatea. În general,pentru funcţii aritmetice, asociativitatea este la stânga (dar dacă nu este clar din context, atunciaceasta trebuie specificată).
De remarcat că nu toate simbolurile au proprietatea de asociativitate. De exemplu, 3 ≤ 4 ≤ 2nu 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 ⇒ esteasociativă 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 suntconsiderate, depinde de precedenţa simbolurilor. Pentru interpretarea clasică (dacă considerămexpresia ca fiind expresie aritmetică), trebuie ca simbolul □□ să aibă precedenţă mai mică (sălege mai tare) decât +.
66
Î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 specificate ele-mentele relevante (poziţia, asociativitatea, precedenţa), pentru a evita ambiguităţile. sintaxarelaxată are avantajul că permite expresii mai compacte. În practică (de ex în sursele matemati-ce, etc) se foloseşte sintaxa relaxată (sintaxa este definită implicit). Însă în cazul în care sunteţinesiguri, folosiţi parantezele!
Relativ la sintax abstractă (reprezentarea sub formă de arbori sintactici), aceasta este aceeaşipentru sintaxa relaxată, însă modul în care se construieşte nu mai este la fel (de uşor) precum afost în cazul sintaxei stricte.
6.4. SubstituţiiSubstituţia de termeni pentru variabile este un proces elementar prin care putem construi expresiinoi din cele existente. Vom defini conceptul de substituţie:
Definiţie 6.8 (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ă. ■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 corespunde apli-
caţiei unei substituţii unei expresii. Intuitiv, se înlocuiesc variabilele cu termenii corespunzătorispecificaţi în substituţie. Această înlocuire are loc în paralel (toate variabilele se înlocuiesc înacelaşi timp cu termenii corespunzători). Totuşi, înlocuirea nu poate avea loc în orice condiţii.Următoarea definiţie specifică modul în care se face substituţia.
Definiţie 6.9 (Substituţie aplicată unei expresii). Fie σ = {x1 ← t1, . . . , xn ← tn} o substitu-ţie. Aplicarea substituţiei σ unei expresii E din logica predicatelor, notată cu Eσ este definită înmodul următor:
• Pentru termeni:
– dacă x ∈ V, atunci
xσ =
{x dacă x = xi, 1 ≤ i ≤ n,
ti dacă pentru un i, x = xi.
67
– 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.
■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 termenii compuşi, formuleleatomice, formulele compuse, substituţia se face pe componente. Pentru formulele cuantificate,variabilele legate sunt protejate de la substituţie (substituţia merge pe componente, dar eliminânddin substituţie variabilele care sunt legate).
Exemplul 6.4 (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))) .
68
▲Fiind date substituţii, se pot obţine unele noi prin operaţia de compoziţie.
Definiţie 6.10 (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 com-poziţ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ă perechile
pentru care termenul substituit este acelaşi cu variabila şi se adaugă elementele din a douasubstituţie a căror variabilă nu apare în prima.
Exemplul 6.5 (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))}.
▲
Proprietăţi ale substituţiilor• Fie E o expresie şi θ, σ substituţii. Atunci E(θσ) = (Eθ)σ.• Fie θ, σ, λ substituţii. Atunci θ(σλ) = (θσ)λ.
6.5. Relaxarea sintaxei (II)Logica predicatelor este folosită implicit în matematică, informatică, etc, însă într-o formă cenu se conformează neapărat definiţiei sintaxei pe care am propus-o aici. Motivul pentru acestfapt este legat de nevoia de a exprima eficient anumite lucruri. În continuare, vom identificacâteva cazuri tipice de „prescurtări”, „zahăr sintactic” (din engl. „syntactic sugar”). Cunoaş-terea acestor notaţii, şi a altora similare, face posibilă parcurgerea mai eficientă a materialelor,translatarea în cadrul oferit de logica predicatelor (cu toată maşinăria de raţionament pe care ovom dezvolta în continuare).
• Negaţii de predicate binare: x ⋪ y este o prescurtare a lui ¬(x ◁ y), unde ◁ este unpredicat 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 prescurtare pentruP ⇒ (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).
69
• 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).
70
7. Semantica logicii predicatelorLimbajul logicii predicatelor (de ordinul întâi) este universal, în sensul în care poate exprima„orice”. Prin urmare, va putea descrie orice univers. Vom defini în continuare modul în care înţe-lesul expresiilor din limbaje de ordinul întâi poate fi determinat. Vom vedea care sunt problemelelegate de înţelesul unor astfel de expresii.
7.1. Interpretare, asignare de valori variabilelor, valoareaexpresiilor
Limbajul L va descrie un domeniu (univers de discurs, lume) D. Vom ataşa numele de simboluriunor concepte corespunzătoare din D (funcţii, relaţii, valori) – prin interpretare. Apoi vom ataşavalori variabilelor prin asignare. Cu aceste ingrediente, vom putea determina valoarea (înţelesul)expresiilor.
Definiţie 7.1 (Interpretare). Fie L = {F ,P, C} mulţimea simbolurilor unui limbaj, şi D undomeniu nevid. O interpretare I a limbajului L în domeniul D este o mapare care 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, este formatdin obiecte, concepte (funcţii şi relaţii) „concrete”. Totuşi, pentru a putea descrie procesul princare limbajul cu simbolurile L este folosit pentru a descrie domeniul de interes, suntem nevo-iţi să reprezentăm acest univers. Pentru aceasta, vom folosi ghilimele singulare ′ . . .′ (şi un fontcorespunzător, unde este cazul, care să indice faptul că suntem în domeniul D, şisă separe de limbaj). ▲Exemplul 7.1 (Interpretări). Fie un limbaj L, astfel încât ⊙/2 ∈ F , P/2 ∈ P şi a, 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′.
• I3, intepretarea limbajului în domeniul şirurilor de caractere,I3(P ) := 'subşir', I3(⊙) := 'concatenare', I3(a) := '„un şir oarecare”', I3(b) :='„alt şir”'.
▲
71
Definiţie 7.2 (Asignare de valori variabilelor). Fie I o interpretare. O asignare de valoripentru 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ările doar pentruvariabilele folosite, de exemplu în expresiile pe care le folosim.
Vom folosi următoarea notaţie: σI [x ← d] pentru o asignare σI unde în particular variabileix i se ataşează elementul d.
Observaţie (Diferenţa între substituţii şi asignări de valori variabilelor). Atenţie, cele douăconcepte sunt diferite! În primul caz, la substituţii, se ataşează variabilelor termeni (este ooperaţie sintactică), în al doilea caz, se ataşează valori de adevăr, se „traduce” limbajul îndomeniul descris. ▲
Intuitiv, termenii descriu obiecte, valori din domeniul de interes.
Definiţie 7.3 (Valoarea termenilor). Fie I o interpretare şi σI o asignare de valori variabilelor.Atunci valoarea unui termen sub intepretarea I şi asignarea de valori 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 7.2. Să considerăm interpretările I1, I2, I3 din Exemplul 7.1. Pentru următoriitermenii ((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′)
Observaţi că am trecut complet în domeniul descris de limbaj, deci avem valoarea căutată.Mai mult, în respectivul domeniu ′+′(′+′(′2′, ′4′), ′0′) = ′6′. Dar atenţie, în momentulacesta nu mai operăm cu simboluri, ci direct în domeniul N cu numere naturale.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”'.
72
▲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 7.4 (Domeniu de valori de adevăr). Alegem două valori distincte A,F (adevărat,fals). Mulţimea de valori de adevăr este mulţimea {A,F}. Acest domeniu se mai numeştedomeniu boolean. ■Definiţie 7.5 (Funcţii de adevăr). Funcţiile de adevăr pentru conectorii logici suntdefinite î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 7.6 (Valoarea formulelor). Fie I o interpretare şi σI o asignare de valori variabilelor.Atunci valoarea de adevăr a unei formule, sub intepretarea I şi asignarea de valorivariabilelor σ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 )),
υσ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 7.3 (Valoarea formulelor sub interpretare şi asignare de valori). Să considerăminterpretările I1, I2, I3 din Exemplul 7.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.
73
• 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 7.3 şi 7.6 „traduc” expresiiledin logica predicatelor (termeni, respectiv formule) în domeniul descris de limbaj. A determinavaloarea sub interpretare şi asignare de valori înseamnă a rezolva direct probleme în domeniuldescris.
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, pentruca formula existenţială să fie adevărată, trebuie sa verificăm elementele domeniului până cândgăsim unul care face formula adevărată. În cazul în care domeniul este mare (infinit), acest lucrunu 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 vedea mai jos, lucrurile stau şi mai rău, cândconsiderăm întrebări tipice pe care le putem pune despre formule. ▲
7.2. Semantica şi substituţiileIntuitiv, substituţia ne permite să înlocuim variabile cu termeni. Când vine vorba de sensul(semantica) expresiilor, ceea ce se spune despre variabilă ar trebui să se spună şi despre termenulcu care s-a înlocuit variabila respectivă.
Exemplul 7.4 (Exemplu din [Buc91]). Fie următoarea formulă ce vorbeşte despre numerenaturale, 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-a face cufaptul că variabila y din {x ← y + 1}, care este liberă, devine legată atunci când termenul încare 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 7.7 (Substituibilitate). Fie x ∈ V şi t ∈ T(L,V) şi σ ∈ SL,V astfel încât x← t ∈ σşi F ∈ F(L,V). Termenul t este substituibil pentru variabila x în F se defineşte în felulurmă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 înF .
74
– 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ţinnumai variabile libere.
Exemplul 7.5 (Substituibilitate).• 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ă în formulă).• 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 vw estesubstituibil î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 care eraliberă în termenul substituit, devine legată.
• Is vw substitutable for w in ∃y(x < vx⇒ (∃w(w < v)))?Da. (De ce?)
▲
7.3. Probleme în logica predicatelorPrimul tip de întrebări legat de înţelesul unei formule este în ce condiţii este adevărată sau falsă.
Definiţie 7.8 (Validitate în logica predicatelor). Fie F ∈ F(L,V).Formula F este validă dacă şi numai dacă pentru orice domeniu, D, orice interpretare I 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 a limbajului
L în D, o asignare de valori variabilelor σI astfel încât υσI (F ) = F.■
Definiţie 7.9 (Satisfiabilitate în logica predicatelor). Fie F ∈ F(L,V).Formula F este satisfiabilă dacă şi numai dacă există un domeniu D, o interpretare I 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, orice interpretare
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 7.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 de valori variabilelor σI ,avem υσI (F ) = υσI (G).
75
■Definiţie 7.11 (Consecinţă logică în logica predicatelor). Fie F1, . . . , Fn, G ∈ F(L,V).
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 asignarede 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 7.6 se multiplică. Un limbaj poate descrie o infinitate dedomenii, pentru fiecare domeniu (care poate fi infinit, cu un număr infinit de concepte - valori,funcţii, relaţii), se pot defini infinit de multe interpretări, şi asignări de variabile. Oricare dinîntrebările de mai sus necesită „vizitarea” unui număr infinit de combinaţii.
Deşi aceste mănunchiuri de infinităţi pot fi adresate construind un univers artificial, universullui 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 lui Herbrand este dincolo descopul acestor note de curs. Vezi însă, de exemplu, [BA12] pentru detalii.
Aşadar avem nevoie de un alt instrument pentru rezolvarea problemelor în logica predicatelor,de un sistem de raţionament.
76
8. Raţionament în logica predicatelorVestea bună este că raţionamentul, aşa cum l-am descris în capitolul introductiv, este posibilîn logica predicatelor. În acest capitol vom introduce un sistem de raţionament pentru logicapredicatelor. Vom descrie modul în care se organizează raţionamentul, cunoştinţele, vom intro-duce regulile de raţionament universale pentru logica predicatelor, şi apoi vom investiga regulispeciale de raţionament (care funcţionează doar în anumite condiţii).
8.1. Proving. Proof techniques. Definitions. Theories.8.1.1. Reasoning in Predicate Logic
• The good news is that reasoning (as defined Chapter 1)‘ is possible in predicate logic.
• In fact several calculi for reasoning in (first order) predicate logic were proposed.
• A reasoning calculus represents a way to organize reasoning:– specifies how a proof should be organized,– specifies the inference rules (i.e. rules for producing proof steps).
• Intuitively proof is a trace of reasoning.
• Notation: If KB is a set of closed formulae and G can be proved (derived) from KB bythe application of inference rules from a given calculus, we denote this as KB ⊢ G.
• For reasoning in predicate logic (natural deduction, i.e a calculus that models the humanreasoning as done by e.g. mathematicians) a remarkable result was proved by Gödel
Theorem 12 (Soundness and completeness of reasoning in first order predicate logic).
KB |= G iff KB ⊢ G.
• We will present here informally a particular calculus for reasoning in first order logic.
8.1.2. Proof Situations• Proving is stepwise arrangement of “proof situations”.
• A proof situation is characterized by the current knowledge base (i.e. sentences known tobe true, which can be used), and the current goal (i.e. sentence which should be proved).
• A proof situation is trivial if the goal occurs in the knowledge base.
• Proof steps (proof techniques, proof rules, inference rules) describe how a proof situationis transformed in (one or more) “simpler” proof situations.
• New proof situations are “simpler” in the sense that either the goal has a simpler structure,or more sentences are added to the knowledge base (i.e. we know more).
77
• A proof describes the necessary inference steps that transform the initial proof situationinto (one or more) trivial proof situations.
• (AND-OR) trees can be used to represent proofs.
• Only a few proof situations are possible.
• Each determined by the structure of its sentences.
• and proof steps can be chosen according to the “outermost construct” in the sencenceconsidered.
• Below are described such typical situatons and the proof steps that can be applied.
• This should be considered as a guideline for human proving (but note that this can beformalized to “natural deduction”, and even automated theorem proving).
8.1.3. Basic Approaches to ProvingFor proving the sentence A (when not knowing whether A is true):
• Try to prove A. If successful, :) (be happy). Otherwise:
• Assume ¬A and try to derive a contradiction. If successful, :) (be happy, A is proved).Otherwise:
• Try to prove ¬A. If successful, :) (be happy). Otherwise:
• Assume A and try to derive a contradiction. If successful, :) (be happy, ¬A is proved).Otherwise:
• Start again with the attempt to prove A. (By this time you have much more insight).
Notation: In the following, A,B,C are formulae, s, t are terms, P is a predicate, f is a functionconstant, x is a variable. A[x] is a formula where x is free, A[t] is Ax←t (when A[x] is changedinto A[t]), A[C] is a formula where C is a subformula.
∀xA[x]
• Prove ∀xA[x]:– For proving ∀xA[x],– show A[x0], where x0 is a new constant (which did not occur so far).– Announcement in proofs:
“Let x0 be arbitrary but fixed (constant). We show A[x0].”
• Use ∀xA[x]:– If ∀xA[x] is known,– then one may conclude A[t] where t is an arbitrary term.– Announcement in proofs: “Since we know that ∀xA[x], we know that, in particular,
A[t]”.– Note that the choice of t is probably going to be suggested by the goal statement.
78
∃xA[x]
• Prove ∃xA[x]:– For proving ∃xA[x],– try to find a term t for which A[t] can be shown,– Finding such a term t is many times nontrivial step, which needs creativity.
• Use ∃xA[x]:– If ∃xA[x] is known, and B has to be proved,– one may assume A[x0] where x0 is a new constant, and try to prove B.– Announcement in proofs: “Since we know that ∃xA[x], let x0 be such that A[x0].
We have to prove B”.
A ∧B
• Prove A ∧B:– For proving A ∧B
– prove A and– prove B.
• Use A ∧B:– If A ∧B is known, then– A is known and– B is known.
A ∨B
• Prove A ∨B:– For proving A ∨B
– assume ¬A and– prove B
– (or assume ¬B and– prove A).
• Use A ∨B:– If A ∨B is known, and C has to be proved then– assume A and prove C and– assume B and prove C.– Announcement in proofs: “We prove by cases: Case A: We prove C. Case B: We
prove C.”
79
A⇒ B
• Prove A⇒ B:– For proving A⇒ B
– assume A and– prove B.
• Use A⇒ B:– If B has to be proved– then look for A⇒ B (or something that “matches” it) and– prove A.– Announcement in proofs: “To prove B, since we know A ⇒ B, it suffices to prove
A”.Also (“modus ponens”). . .
– If A and A⇒ B are known,– then B can be added to the knowledge.– Announcement in proofs: “From A⇒ B and A, by modus ponens, we get B.”
A⇔ B
• Prove A⇔ B:– To prove A⇔ B,– assume A and– prove B, then– assume B and– prove A.
• Use A⇔ B:– If C[A] has to be proved, and– A⇔ B is known, then– try to prove C[B].
¬A
• Prove ¬A:– To prove ¬A,– assume A,– and derive a contradiction, i.e.– prove ¬C,– where C is in the knowledge base.
80
P (t1, . . . , tn)
• Prove P (t1, . . . , tn):– To prove P (t1, . . . , tn)
– look for an “explicit definition” ∀x1,...,xn
P (x1, . . . , xn)⇔ A[x1, . . . , xn]
– and prove A[t1, . . . , tn].• Use P (t1, . . . , tn):
– If P (t1, . . . , tn) is known and the definition:– ∀
x1,...,xn
P (x1, . . . , xn)⇔ A[x1, . . . , xn] is in the knowledge base,
– then A[t1, . . . , tn] can be added to the knowledge base.
A[f(t1, . . . , tn)]
• Prove A[f(t1, . . . , tn)]:– To prove A[f(t1, . . . , tn)]
(a) “explicit definition” case:∗ where the “explicit definition” of f :
∀x1,...,xn
f(x1, . . . , xn) = s[x1, . . . , xn] is in the knowledge base,
∗ prove A[s[t1, . . . , tn]].(b) “implicit definition” case:
∗ where the “implicit definition” of f :
∀x1,...,xn
f(x1, . . . , xn) = such a y that B[x1, . . . , xn, y]
is in the knowledge base,∗ prove ∀
yB[t1, . . . , tn, y]⇒ A[y].
• Use A[f(t1, . . . , tn)]:– If A[f(t1, . . . , tn)] is known:
(a) “explicit definition” case:∗ and the “explicit definition” of f :
∀x1,...,xn
f(x1, . . . , xn) = s[x1, . . . , xn] is in the knowledge base,
∗ then A[s[t1, . . . , tn]] can be added to the knowledge base.(b) “implicit definition” case:
∗ and the “implicit definition” of f :
∀x1,...,xn
f(x1, . . . , xn) = such a y that B[x1, . . . , xn, y]
is in the knowledge base,∗ then ∃
y(B[t1, . . . , tn, y] ∧A[y]) can be added to the knowledge base.
∗ see below, the explanation about “such a . . . that . . .”
81
8.1.4. Definitions in Predicate Logic• Definitions allow the introduction of new concepts in terms of existing ones.
• They provide a facility for concise formalization of mathematics, but they are not essential,i.e. they can be eliminated.
• However, they allow formulae to be shorter,
and help structuring the knowledge.
• Practical mathematics would hardly be conceivable without this facility.
Example 13 (Irreducible natural numbers).
∀is-nat(i)
( is-irreducible(i)︸ ︷︷ ︸“definiendum”(lat. to be defined)
⇔ ∀is-nat(n)
(n|i⇒ (n = 1 ∨ n = i))︸ ︷︷ ︸“definiens”(lat. the defining)
)
Types of definitions
• (Explicit) definitions of predicate symbols. See Example 13.
• Explicit definitions of function symbols.
Example 14 (The determinant of a 2x2 matrix.). Let A =
(a11 a12a21 a22
). Then |A| =
a11a22 − a12a21.
• Implicit non–unique definitions of function symbols.
Example 15 (Implicit non–unique definition of √). The squareroot function can be defined(e.g. in the complex numbers) by:
∀x
√x = such a y that y2 = x.
Note that this (such a . . . that . . .) is syntactic sugar for: ∀x,y
(√x = y ⇒ y2 = x
).
• Implicit unique definitions of function symbols.
Example 16 (Implicit unique definition of √). The squareroot function can be defined (e.g.in the real numbers) by:
∀x
( √x = the y such that(
(x ≥ 0⇒ (y ≥ 0 ∧ y2 = x)) ∧ (x < 0⇒ y = 0)) ) .
Note that this (the . . . such that . . .) is syntactic sugar for:
∀x,y
(√x = y ⇔
((x ≥ 0⇒ (y ≥ 0 ∧ y2 = x)) ∧ (x < 0⇒ y = 0)
)).
82
Properties of definitions
• Definitions:– are axioms,– can always be “eliminated”,– do not bring anything new to the power of the theory (conservative extensions),– do not introduce contradictions.
• Correct definitions (watchlist):– no extra variables in the definiens.
Example 17 (Extra variables). Consider the “definition”: is-factor(f) ⇔ f |x. Thisleads to a contradiction: is-factor(f), because 3|6 and ¬is-factor(f) because 3 ∤ 5.
– definitions of terms, uniqueness, pairing functions.
Example 18 (Definition of terms (wrong)). . The “definition”
is-nice-sum(x+ y)⇔ x = 2y
introduces a contradiction: 6 + 3 is a nice sum, because 6 = 2 ∗ 3, but 5 + 4 is not anice sum 5 = 2 ∗ 4. So 9 is both a nice sum and not a nice sum.Example 19 (Definition of terms (with unique pairing function)). The definitionpair-of-primes((x, y)) ⇔ (is-prime(x) ∧ is-prime(y)) is correct, because the pairingfunction (x, y) which yields the pair of x, y has the uniqueness property:
(x, y) = (x1, y1)⇒ (x = x1 ∧ y = y1).
8.2. TheoriesStructure of a Theory
• A (mathematical) theory T is described by its:– language (symbols): LT = ⟨FT ,PT , CT ⟩, i.e. its function, predicate and constant
symbols respectively. Note that, for any theory, id,= (the identity function and theequality) can always be included in the language;
– knowledge base KBT , which contains facts (formulae over the language), i.e. axiomsand propositions (theorems, lemmata, corollaries, etc.).
– inference rules, IRT . The rules for predicate logic, as well as rules for equalityproving (rewriting) may be included in any theory. Additional rules may be included(depending of the nature of objects in the theory), which make the theory morepowerful, in the sense that more facts may be proved using these additional rules.These cannot be applied outside of the theory.
Example 20 (The theory of Strict partial orderings PO.).• The symbols in the language:
– function symbols, FPO = {} (no function symbols),– predicate symbols,PPO = {p}, where p is a binary symbol,
83
– constants, CPO = {} (no constants either).• the knowledge base KBPO:
– Axioms describing strict partial orderings:∀
x,y,z(p(x, y) ∧ p(y, z)⇒ p(x, z)), (transitivity)
∀x¬p(x, x). (irreflexivity)
• The inference mechanism IRPO consists of the inference rules of predicate logic.
Development of a Theory• Theories are not static, but are developed:• from initial descriptions (such as in the previous example), where the knowledge base
contains axioms,• by adding new components:
– new formulae to the knowledge base, i.e. consequences of the existing formulae,proved using the mechanisms available,
– new symbols with their corresponding definitions (defining axioms, which are addedto the knowledge base),
– new inference rules, a very subtle point - lifting knowledge to the level of inference,as these have to be proved correct
• Questions that arise in the development of theories include:– how much of the theory is relevant? (not always all knowledge is needed, or even
useful)– ...
8.2.1. Equality• The binary predicate = (equality) plays a very important role in predicate logic: many
theories contain equality.• The language symbols (vocabulary) of a theory of equality (or containing equality) consists
of = and an unspecified number of function, predicate and constant symbols.• Any theory containing equality includes the axioms for equality:
∀x,y,z
(x = y ∧ y = z ⇒ x = z) , (transitivity)
∀x,y
(x = y ⇒ y = x) . (symmetry)
∀x(x = x) (reflexivity)
Now let f be any function symbol of arity k, p be any predicate symbol of arity l:
∀x, y, z1, . . . , zi−1,
zi+1, . . . , zk
(x = y)⇒(f(z1, . . . , zi−1, x, zi+1, . . . , zk) =f(z1, . . . , zi−1, y, zi+1, . . . , zk)
) (functional substitutivity)
84
i.e. functions applied to arguments that are equal (x and y) yield equal results.
• (functional substitutivity) is in fact an axiom scheme, that can be applied to any functionsof any arity.
• The corresponding proof technique is equality rewriting, i.e. chains of equalities from acomplex (in some measure) to a simpler (simplest) term.
• E.g. two terms are equal if they can be rewriten to the same simpler (simplest) term.
∀x, y, z1, . . . , zi−1,
zi+1, . . . , zl
(x = y)⇒(p(z1, . . . , zi−1, x, zi+1, . . . , zl)⇔p(z1, . . . , zi−1, y, zi+1, . . . , zk)
)
(predicate substitutivity)
i.e. predicates applied to arguments that are equal (x and y) are equivalent.
• (predicate substitutivity) is in fact an axiom scheme, that can be applied to any predicatesof any arity.
• The corresponding proof technique is equivalence rewriting, i.e. chains of equivalences.
• E.g. two formulae are equivalent if there is a chain of equivalences between them.
8.3. Induction• Induction is an inference rule used to prove (universal) properties of objects in domains
that are manageable,
• i.e. every object in the domain can be “constructed” in a finitary way from “basic” objects,“smaller” objects,
• e.g. apply the successor function to a natural number to get the next one, and this is theonly way to construct natural numbers (they are all successors of 0),
• all concepts in such (i.e. inductive) theories will be defined in a way which reflects thestructure of the objects (inductive definitions, “recursive”),
• universal properties of inductive objects can be proved by corresponding induction infe-rence rules, which again reflect the structure of the objects in the domain,
• induction is in general essential to prove in inductive theories, i.e. induction is strongerthan predicate logic,
• examples of inductive domains: natural numbers, strings, lists, trees, sets, bags, formulae,proofs.
85
The theory of natural numbersExample 21 (The theory of natural numbers N).
• Natural numbers start with 0, and any other natural number is obtained from 0 by suc-cessive applications of the successor function +
• the symbols in the language:– function symbols, FN = {+} the unary successor function,– predicate symbols,PN = {is-nat,=}, a unary predicate that detects natural numbers,
and equality, respectively– constants, CN = {0}.
• the knowledge base KBN:– generation axioms:
is-nat(0) (gen. zero)∀
is-nat(x)is-nat(x+) (gen. succ.)
– uniqueness axioms:
∀is-nat(x)
x+ = 0 (zero)
∀is-nat(x),is-nat(y)
(x+ = y+)⇔ (x = y) (succ.)
– induction axiom (scheme): for any formula F:(F[0] ∧ ∀
is-nat(x)(F[x]⇒ F[x+])
)⇒ ∀
is-nat(x)F[x]
• the inference mechanism IRN consists of the inference rules of predicate logic and rewri-ting.
Induction as an inference rule
• A subtle point: the induction axiom scheme cannot be expressed in first order predicatelogic, because first order logic only allows variables over objects and not over formulae (asis needed to express the induction scheme).
• One way to overcome this is to add, for each formula F used an instantiation of the scheme.This may be cumbersome, and will result in very big knowledge bases, containing manysimilar formulae.
• However, we can add an inference rule (the induction rule) to IRN:– To prove: ∀
is-nat(x)F[x] (an universal property of natural numbers),
– Prove F[0] (the base case) and(Induction step):
– Take x0 arbitrary but fixed such that is-nat(x0) andAssume F[x0] (the induction hypothesis) andProve F[x+
0 ] (the induction conclusion).
86
Inductive definitions
• In inductive domains, definitions of new concepts will reflect the inductive structure ofobjects:
– the notion has to be defined for (all) the simplest objects (the base case(s)).– the notion has to be defined for the complex objects, and it will be defined using the
notion for the simpler objects, i.e. recursion will be used.
Example 22 (Semantics of expressions in predicate logic).
• Expressions of predicate logic are an inductive domain:– For terms:
∗ variables and constants are (the simplest) terms,∗ function symbols applied to other (simpler) terms are terms (complex terms),
– For formulae:∗ atomic formulae are the simplest formulae (but not the simplest expressions),
predicates applied to terms,∗ compound formulae and quantified formulae are build from (simpler) formu-
lae/terms are (complex) formulae.
• The notion of the semantics of terms and formulae is defined recursively:– For terms:
∗ for variables it is given directly by the variable assignment, for constants, directlyby the interpretation of the constant symbol,
∗ for compound terms it is given recursively, in terms of the meaning of thesmaller terms that make up the compound term.
– For formulae:∗ for atomic formulae it is given directly by the interpretation of the function
symbol applied to meaning of the terms,∗ for compound formulae it is given recursively, in terms of the meaning of the
simpler formulae that make up the compound formula,∗ for quantified formulae it is given recursively, in terms of the meaning of
the simpler formula that (but depending of the assignment of the quantifiedvariable).
Example 23 (Recursive definitions in the theory of natural numbers).
• Consider the theory of natural numbers, as defined in Example 21.
• Now consider the following definition of a new concept (function symbol +):
∀is-nat(x)
x+ 0 = x (right zero)
∀is-nat(x),is-nat(y)
x+ y+ = (x+ y)+ (right succ.)
Notice that for the simplest object (0) the value was given directly, and for a compoundobject (y+), it was given in terms of the notion (+) for the simpler object (y).
87
• Here is a definition of a new concept (predicate symbol ≤):
∀is-nat(x)
x ≤ 0⇔ x = 0 (zero)
∀is-nat(x),is-nat(y)
x ≤ y+ ⇔ (x = y+ ∨ x ≤ y) (succ.)
Notice again the structure of the definition.
88
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, CopyrightBruno Buchberger, 1991.
[Chu36] Alonzo Church. An unsolvable problem of elementary number theory. AmericanJournal of Mathematics, 58(2):345–363, 1936.
[Göd30] Kurt Gödel. Die vollständigkeit der axiome des logischen funktionenkalküls. Monat-shefte für Mathematik, 1(37):349–360, 1930.
[Göd31] Kurt Gödel. Über formal unentscheidbare sätze der principia mathematica und ve-rwandter systeme, I. Monatshefte für Mathematik und Physik, (38):173–198, 1931.
[H.G03] Jean H.Gallier. Logic for Computer Science, Foundations of Automated TheoremProving. Copyright Jean H. Gallier, 2003.
[KLRV49] E. L. Kaufman, M. W. Lord, T. W. Reese, and J. Volkmann. The discrimination ofvisual number. The American Journal of Psychology, 62(4):498–525, 1949.
[KT06] Jon Kleinberg and Eva Tardos. Algorithm Design. Pearson International, Inc., 2006.
[Rus03] B. Russell. The Principles of Mathematics. Number vol. 1 in The Principles ofMathematics. University Press, 1903.
[Sha38] Claude Elwood Shannon. A symbolic analysis of relay and switching circuits. Tran-sactions of the American Institute of Electrical Engineers, 57, 1938.
[TA13] Andrew Tanenbaum and Todd Austin. Structured Computer Organization. Pearson,6th edition edition, 2013.
[Tur37] Alan M Turing. On computable numbers, with an application to the entscheidungs-problem. Proceedings of the London mathematical society, 2(1):230–265, 1937.
89
