Introducere În LOGICA SIMBOLICĂ introducere în logica simbolică TEODOR STIHI Copyright © 1999 - BIC ALL Toate drepturile sunt rezervate Editurii BIC ALL Nici o parte din acest volum nu poate fi copiată fără permisiunea scrisă a Editurii BIC ALL Drepturile de distribuție în străinătate aparțin în exclusivitate editurii. Copyright © 1999 by BIC ALL AII rights reserved. The distribution of this book outside Romania, without the written permission of BIC ALL is strictly prohibited. Descrierea CIP a Bibliotecii Naționale STIHI, TEODOR Introducere în logica simbolică / Teodor Stihi - București: Editura BIC ALL, 1999 104 p.; 20 cm (ACCENTE) Bibliogr. Index ISBN 973-571-286-5 16 Editura BIC ALL București, Bd. Timișoara nr. 58, sector 6, cod 76548 ® 402 26 00 Fax: 402 26 10 Departamentul 402 26 20 difuzare Fax: 402 26 30 Redactor: Radu Slobodeanu Coperta: Dominic Cernea Printed in Romania Colecția Accente apare sub îngrijirea Prof. Univ. Dr. Paul Flondor Teodor Stihi Introducere în Logica Simbolică 411 In această colecție au apărut: Cum ne țesem eul - argument, selecție și traducere G.G. Constandache Algoritmi genetici - ediție îngrijită de Paul Flondor și Cezar lonescu Urmează să apară: Genetică și patologie - Marina Anton și Minerva Muraru Mulțimi, funcții recursive, aplicații - Ionel Țevy Conștiința și identitatea umană - ediție îngrijită de G.G. Constandache CĂTRE CITITOR Limbajul logico-simbolic a devenit, prin introducerea în ma- nualele de liceu, element de cultură generală. Ceea ce este firesc, ținând seama de faptul că în această haină, croită după moda sfârșitului mileniului nostim, s-a îmbrăcat și o bună parte din tra- diționala logică aristotelică, la cei peste 2200 de ani de existență. Dăndu-și mâna, două dintre artele liberale ale învățămân- tului medieval - logica și matematica - au produs, în ultimul secol și jumătate, ceea ce gânditori și mari creatori de talia lui G. W. Leibniz au imaginat fără a putea realiza: un „ calculus raliocinator” (calcul argumentator). In paginile următoare vom încerca să prezentăm, chiar pentru cititorul cu un nivel minim de cunoștințe matematice, elementele de bază ale calculului logic. Ce i se cer acestui citi- tor sunt mai puțin aceste cunoștințe, cât răbdarea și perseve- rența de a urmări definițiile, proprietățile și mai ales exem- plele cu care le-am ilustrat. Cei doritori de amănunte și justi- ficări. complete (demonstrații) pot consulta, desigur cu folos, una dintre excelentele expuneri detaliate pe această temă (câteva sunt menționate într-o scurtă bibliografie la pag. 100) In plus, pentru a-i oferi aceluiași cititor conștiincios prile- jul și satisfacția de a-și vedea puse în lucru cunoștințele do- bândite prin efortul acestei lecturi, am adăugat, în finalul fiecăreia dintre cele două părți din care este alcătuită cartea, câteva exerciții având rezolvarea în anexa I. Nutrim speranța că prin această poartă deschisă spre un domeniu tradițional și, în același timp, actual, vor pătrunde cât mai mulți. Și mai sperăm că această experiență îi va ajuta să-și dezvolte rigoarea în gândire și în exprimare. Le urăm tuturor succes și așteptăm cu interes reacțiile și sugestiile citi- torilor noștri. Autorul CUPRINS L CALCULUL PROPOZIȚIONAL A. Idei introductive.................................1 §1. Calcul logic...................................1 §2. Propoziții logice..............................1 §3. Operatori logici...............................2 §4. Limbaj natural și limbaj logic.................3 §5. Funcții de adevăr..............................5 §6. Implicația și echivalența logică...............7 B. Dezvoltarea calculului prepozițional.............10 §7. Formule propoziționale........................10 §8. Validitate prepozițională.....................13 §9. Substituție și detașare.......................18 §10. Echivalența formulelor propoziționale..........20 §11. Dualizarea formulelor propoziționale...........24 §12. Forme normale..................................26 C. Axiomatizarea calculului propozițional...........28 §13. Metoda axiomatică..............................28 §14. Axiome și reguli deductive.....................29 §15. Demonstrație și deducție.......................31 §16. Elemente de teoria demonstrației...............33 §17. Necontradicția calculului propozițional........38 §18. Reguli deductive derivate......................39 §19. Completitudinea calculului propozițional.......43 EXERCIȚII............................................47 VIII Cuprins II. CALCULUL PREDICATELOR D. Idei introductive.................................50 §20. Insuficiențe ale calculului prepozițional......50 §21. Structura logică a propozițiilor simple........51 §22. Cuantificarea subiectului logic................53 §23. Argumente exprimate în limbajul calculului predicatelor.........................54 E. Dezvoltarea calculului predicatelor.............. 56 §24. Formule cu predicate...........................56 §25. Validitate în calculul predicatelor............58 §26. Substituții în calculul predicatelor...........63 §27. Echivalența formulelor cu predicate............66 §28. Dualizarea formulelor cu predicate.............69 §29. Reguli de cuantificare.........................71 F. Axiomatizarea calculului predicatelor.............73 §30. Axiome și reguli deductive.....................73 §31. Demonstrație și deducție în calculul predicatelor... 75 §32. Proprietăți ale relației de deductibilitate....77 §33. Consistență și completitudine..................79 §34. Reguli deductive derivate..................,...82 EXERCIȚII.............................................85 Anexa I: Soluțiile exercițiilor..........................88 Anexa II: Echivalențe logice.............................94 Anexa III: Logică și metamatematică......................97 Bibliografie............................................100 Simboluri utilizate.....................................101 Index...................................................102 I. CALCULUL PROPOZITIONAL A. Idei introductive §1. Calcul logic Ideea unui calcul logic a apărut în lucrările lui R. Lullus (1235-1315) și G.W. Leibniz (1646-1716). Dar pasul decisiv a fost făcut de G. Boole (1815-1864) care pune bazele unui calcul logic asemănător celui algebric. Calculul boolean - numit astfel în onoarea sa — a fost apoi dezvoltat prin lucrările unor logicieni și matematicieni remarcabili; astăzi calculul logic este un instru- ment de lucru atât în științele exacte, cât și în unele discipline umaniste. Principiile sale generale sunt studiate într-o serie de școli și facultăți: de la cele de matematică și calculatoare la cele de psihologie și filozofie. Vom prezenta în paginile următoare aceste principii împăr- țind expunerea în două secvențe: -calculul propozițiilor, sau propozițional, și - calculul predicatelor. §2. Propoziții logice1 Acestea sunt elementele constitutive ale calculului propo- zițional. IA. Definiție O propoziție logică este o propoziție sau fraza gramaticală având un conținut enunțiativ ce poate fi caracterizat — într-un context dat — drept adevărat sau fals (nu dintr-o dată). 1 Atributul „logic” este utilizat în această lucrare într-un sens mai restrâns decât în vorbirea curentă. 2 Calculul propozițional Exemple. Plouă. E soare. E soare, deci nu plouă. O interogație (îmi poate folosi logica la ceva?), o excla- mație (Gândește-te!) etc. nu pot fi caracterizate — în nici un context - drept adevărate sau false. Prin urmare, nu sunt propoziții logice. Precizăm că nu ne vor interesa condițiile - obiective sau subiective - de care depind adevărul sau falsitatea propozițiilor logice. Trebuie doar ca fiecare dintre aceste propoziții să fie sau A (adevărată) sau F (falsă). A și F se vor numi valori de adevăr. §3. Operatori logici Calculul logic utilizează noțiuni și simboluri de sorginte ma- tematică. Majusculele P, Q, R etc. eventual indexate, vor reprezenta propoziții logice. Dar simbolizând prin P, Q, R cele trei propoziții logice, date mai sus drept exemple, facem un pas neadecvat către instituirea unui calcul logic. Aceasta deoarece pierdem astfel din vedere faptul că ultima dintre cele trei (E soare, deci nu plouă) se poate obține din primele două prin anumite transformări. Cea mai simplă dintre transformări este Negația logică1. Propoziția P (Plouă) se transformă prin negație în ~| P (Nu plouă). 1 este simbolul operatorului logic de negație. Conjuncția logică transformă propozițiile P (Plouă) și Q (E soare) în propoziția logică P kQ (Plouă și e soare). 1 în limbaj matematic o astfel de transformare se numește operator, aici fiind vorba de un operator logic\ în speță operatorul logic de negație. A. Idei introductive 3 a este simbolul acestui operator logic. Disjuncția logică transformă aceleași propoziții P și Q în P v 0 (Plouă sau e soare), având v ca simbol al său. Implicația logică transformă P și Q în P => Q (P implică Q) și are ca simbol =>. Echivalența logică transformă P și 0 în P <=> Q (P echivalent Q) având ca simbol <=>. Să revenim acum la ultimul dintre cele trei exemple anterioare: E soare, deci nu plouă. Asimilând pe „deci” cu „implică” o vom simboliza, con- form celor explicate, prin §4. Limbaj natural și limbaj logic Limbajul logicii simbolice este un fragment al celui natural (limba scrisă și vorbită). Prin introducerea sa logicienii au urmărit eliminarea unor imprecizii și echivocuri ale acestuia din urmă. Desigur că prin aceasta limbajul logicii simbolice pierde expresivitatea și nuanțările specifice limbajului natural. El se apropie, de fapt, de limbajul calculatoarelor (pentru care a servit inițial drept model). Este important de remarcat, cu toate acestea, că într-un asemenea limbaj dispunem de suficiente mijloace de expresie pentru a reda adevărurile formulate în științele exacte, cu deo- sebire a celor din matematică. Dar în cele ce urmează am ales drept exemple două extrase din literatura clasică: Eminescu și Caragiale. 4 Calculul propozițional 2 A. Iar m lumea cea comună a visa e un per icul, Căci de ai cumva iluzii, ești pierdut și ești ridicul M. Eminescu Scrisoarea a Il-a Pentru a transcrie în limbaj simbolic aceste două versuri eminesciene vom utiliza următoarele notații („dicționar”) P: de ai cumva iluzii, ești pierdut jz ești ridicul'. Q\ Iar în lumea cea comună a visa e un pericul. Fragmentul ales constituie propoziția logică Q căci P transcrisă drept implicația P^Q. Dar, în timp ce Q este o propoziție simplă}. P se poate scrie ca rezultat al transformării unor propoziții logice; adică este compusă. Continuăm „dicționarul” notând cu R\ ai cumva iluzii'. S: ești pierdut și ești ridicul. Astfel, P va putea fi redată în limbajul logicii simbolice prin R^S. Analizând la fel ca mai sus cele două componente ale implicației, constatăm că prima este simplă în timp ce a doua se descompune în Si: ești pierdut. ești ridicul. Anume, S va fi redată simbolic sub forma: S] A Si Numim simplă o propoziție logică ce nu poate fi obținută transformând alte propoziții logice prin intermediul unor operatori logici. A. Idei introductive 5 Refăcând din aceste „piese” întregul fragment obținem: Parantezele au același rol ca și în algebră: indică ordinea aplicării operațiilor (aici: a operatorilor logici). 3 A. ... eu am, n-am înfățișare, la douăsprece trecute fix mă duc la tribunal). I.L. Caragiale O scrisoare pierdută (Actul I, scena a Vl-a) Textul fiind eliptic, reconstrucția sa logică presupune și o anumită interpretare1. O vom face astfel: {Dacă} eu am (sau) n-am înfățișare, (atunci) la douăsprece trecute fix mă duc la tribunal! Propozițiile logice simple sunt P: eu am (înfățișare)} Q: la douăsprece trecute fix mă duc la tribunal. iar fragmentul capătă, în interpretarea dată, forma logică: §5. Funcții de adevâr Scopul principal pentru care a fost creat limbajul logic este acela de a servi ca „vehicul al adevărului” de la premisele la concluzia oricărui raționament exprimat cu mijloacele lui. Legile logicii stabilesc condițiile în care, din adevărul anu- mitor propoziții decurge adevărul altei propoziții. Controlul asupra acestui „transfer” de adevăr este menținut impunând operatorilor logici o condiție destul de severă: aceea de a fi funcții de adevăr. In matematică funcția este o corespondență între elementele unei mulțimi și elementele altei (sau aceleiași) mulțimi. O 1 Precizia limbajului logic impune asemenea interpretări, chiar dacă uneori ele pot fi forțate. 6 Calculul prepozițional funcție asociază fiecărui element al primei mulțimi câte un singur element din a doua mulțime. NEGAȚIA logică definește o astfel de funcție. Când propo- ziția „plouă” este adevărată (A), propoziția „nu plouă” este falsă (F). Iar când „plouă” este falsă (F), „nu plouă” este ade- vărată (A). Exprimarea sintetică a acestei corespondențe între mulțimea valorilor de adevăr {A, F} și ea însăși este tabela: p 1P A F F A TAB 1 Prin ea se definește funcția de adevăr a negației logice. Nu a negației propoziției P, ci a negației oricărei propoziții logice. CONJUNCȚIA logică definește la rândul său o anumită funcție de adevăr. Deoarece conjuncția - ca operator - transformă o pereche de propoziții (P, Q) într-o propoziție P a Q, funcția de adevăr corespunzătoare conjuncției va transforma fiecare dintre cele patru perechi de valori de adevăr (A, A), (A, F), (F, A), (F, F) într-o valoare de adevăr. Tabela de adevăr a conjuncției este următoarea: P Q P*Q A A A A F F F A F F F F TAB a A. Idei introductive 7 Ceea ce ne arată că propoziția „P și Q” este adevărată într- un singur caz: când cele două propoziții P și Q sunt simultan adevărate. DISJUNCȚIA logică definește funcția de adevăr redată* în tabela p Q P^Q A A A A F A F A A F F F TAB v Propoziția „P sau Q” este adevărată în toate cazurile cu excepția celui în care cele două propoziții P și Q sunt false. Observație. Această funcție de adevăr corespunde unui „sau” neexclusiv. In limba română apare și un „sau” exclusiv (ca în expresia: totul sau nimic). Despre funcții de adevăr vom discuta și în continuare. §6. Implicația și echivalența logica Intre două propoziții logice P și 0 pot exista două tipuri de relații logice importante: implicația și echivalența. IMPLICAȚIA logică P => Q este exprimată în limbajul curent prin expresii ca: dacă P, atunci Q; Q dacă P; Q deoarece P; P numai dacă Q. In matematică sunt utilizate și sintagmele: P este o condiție suficientă pentru Q, Q este o condiție necesară pentru P. In logică este preferată exprimarea: P implică Q. 8 Calculul prepozițional ECHIVALENȚA logică P <=> Q se exprimă prin: P dacă și numai dacă Q, P exact atunci când Q etc., iar în matematică și prin sintagma: P este condiția necesară și suficientă pentru Q. In logică apare mai frecvent exprimarea: P este echivalentă cu Q. Fiind operatori logici, atât implicația cât și echivalența sunt asociate unor funcții de adevăr. Pentru echivalență această funcție este definită prin tabela: p Q A A F F A F A F A F F A TAB <=> Așadar P <=> Q este adevărată exact atunci când P și Q au aceeași valoare de adevăr. Pentru a înțelege cum s-a ajuns la tabela de adevăr a impli- cației vom discuta în prealabil un exemplu de implicație logică. Dacă am de lucru, (atunci) vin târziu acasă. Descifrăm semnificația logică a acestei propoziții analizând cele patru variante posibile. 1) am de lucru și vin târziu acasă; 2) am de lucru și nu vin târziu acasă; 3) nu am de lucru și vin târziu acasă; 4) nu am de lucru și nu vin târziu acasă. în mod clar propoziția considerată este adevărată în primul caz și falsă în al doilea caz. Mai puțin clare sunt valorile sale de adevăr în ultimele două cazuri. întrucât există patru variante de alegere a lor, vom analiza fiecare variantă în parte. A. Idei introductive 9 p Q Varianta a Varianta b Varianta c Varianta d A A A A A A A F F F F F F A F A F A F F F F A A Linia întreruptă desparte situațiile clare de cele problematice. In varianta a, semnificația logică a propoziției date ar coin- cide cu semnificația propoziției: Am de lucru și vin târziu acasă. (A se compara valorile de adevăr din varianta a cu TAB a) în varianta b această semnificație ar coincide cu cea a pro- poziției: Vin târziu acasă. (A se compara valorile de adevăr din coloanele a doua și a patra). în varianta c semnificația logică ar fi aceeași cu a pro- poziției: Am de lucru dacă și numai dacă vin târziu acasă. (A se compara varianta c cu TAB <=^>) Toate aceste soluții sunt greu de acceptat. Ne oprim așadar la varianta d, iar funcția de adevăr a implicației logice este fixată prin tabela P Q P^Q A A F F A F A F A F A A TAB => 4A. Observație. în legătură cu relația P => Q precizăm că propoziția P se numește antecedent sau premisă a implicației, iar propoziția Q se numește consecvent sau concluzie a sa. Așadar relația de implicație este falsă numai în cazul în care antecedentul (premisa) este A și consecventul (concluzia) este 10 Calculul propozițional Implicația Q => P se numește conversa implicației P => Q. Implicația 1Q =>"] p se numește transpusa implicației P => Q. B. Dezvoltarea calculului propozițional §7. Formule prepoziționale Revenim la limbajul simbolic al logicii. El conține multe elemente specifice limbajului matematic. Printre acestea pe cea de variabilă; aici de variabilă prepozițională. Notăm cup, q, r, p\ etc. aceste variabile. Dacă în propoziția logică (Ă=>(S! aS2))=>0 ce exprimă în limbaj logic cele două versuri eminesciene (cf. 2A), înlocuim propozițiile R, Si, S2, Q prin variabilele prepoziționale r, st, s2, q obținem: (r =$ (5i a 52)) => q Aceasta nu reprezintă propoziția logică de mai sus, ci structura ei logică. Și nu numai pe a ei, ci și a altora având aceeași „formă” cu ea. De aceea se va numi formulă propozițională. B. Dezvoltarea calculului propozițional 11 Spre exemplu, structura propoziției logice: prin care am transcris celebra frază a lui Farfuridi din „Scrisoarea pierdută” (cf. 3A) se obține înlocuind P cu p în fiecare dintre cele două apariții ale sale și Q cu q. Ea va fi exprimată prin formula: (P v l/>) => 7- 3B. Construirea pas cu pas a formulelor. Calculul logic operează cu formule logice la fel cum cel algebric operează cu formule algebrice. De aceea formulele (propoziționale) trebuie definite independent de propozițiile logice a căror structură o exprimă. Este ceea ce vom face în continuare plecând de la cele mai simple și trecând, pas cu pas, spre cele mai complexe. Metoda aceasta se numește inductivă și se rezumă la două reguli. Rl. Baza inducției. Orice variabilă prepozițională este o formulă prepozițională. R2. Pasul inducției. Dacă o: și £ sunt formule propozițio- nale1 atunci 1 a, a a £, a v £, a => £, a £ sunt formule propoziționale. Ilustrăm această metodă prin Exemple. Variabilele propoziționale q, r}, r2, s sunt formule propoziționale (Rl). Din aceste formule obținem (cf. R2) formulele: 1 q rx a r2; Aplicând din nou R2 construim formulele: q v 1 q q=>(r} a r2); 1 Notăm a, P, y etc. formulele construite cu ajutorul celor două reguli. 12 Calculul prepozițional După al treilea pas inductiv obținem formulele: (7 v 1 q) => s (q=>(r} a r2)) => s etc. Operatorul (tipărit îngroșat) introdus de regula R2 se numește operatorul principal al formulei respective. Parantezele pe care le-am introdus au rolul de a delimita operatorul principal, al fiecărei formule, de restul formulei. Pentru a nu supraîncărca notația putem renunța la o parte din ele adoptând următoarea 4B. Convenție. într-o formulă în care apare un singur <=} acesta este operatorul principal. Dacă <=> nu apare și apare un singur =>, acesta va fi opera- torul principal, ș.a.m.d. Astfel am introdus pentru fiecare dintre cei cinci operatori câte un ordin de prioritate: cel maxim pentru <=>, apoi => etc. până la "|. Iată ordinea completă a lor <=>, =>, v, a, 1 Exemple. în formula (fără paranteze) pvqAr<=>~]p=>qAr operatorul principal este <=>. Cele două formule din care s-a obținut, prin aplicarea regulei R2, această formulă sunt pvq/\r și 1/2 => q Ar Ele au ca operatori principali v și respectiv =>. Scrisă cu paranteze, formula inițială va fi (p v (9 a r)) <=> ((I/2) => (q A r))1 Observație. Sunt cazuri în care parantezele devin indispen- sabile: 1 De multe ori se adoptă o variantă intermediară de scriere; de pildă în cazul de față ea poate fi B. Dezvoltarea calculului propozițional 13 când apar doi operatori identici sau când operatorul princi- pal nu are, printre ceilalți operatori ai formulei, ordinul maxim de prioritate. Exemple. Y)p=$q=$p/\q poate fi citită drept (p => 7) => (p /\ q) sau dreptp =5 (q => p a q). 2) Formula p => (7 <=> p a q\ în absența parantezelor ar trebui citită drept (p => q) <=> (p a q). §8. Validitate propozitionalâ La fel cum calculul algebric se dezvoltă pe baza identităților algebrice, calculul logic se dezvoltă pe baza identităților logice. In calculul propozițional acestea sunt formulele propozițional valide. în fața fiecăreia dintre ele vom pune simbolul: [= Exemple'. |=pv"|p (terțul exclus) |= p_ <=> ”| 1 p (negarea negației) |= p /\(p q)=> q (modus ponens) în paranteză am adăugat denumirile principiilor logice pe care fiecare dintre aceste formule le transcriu în limbaj simbolic. Astfel, principiul terțului exclus afirmă că orice propoziție logică este adevărată sau falsă; principiul negării negației (sau dublei negații) afirmă că orice propoziție este echivalentă negării negației sale; asupra principiului modus ponens ne vom opri în paginile următoare. Pentru a exprima un astfel de principiu ar trebui să-l enunțăm pentru fiecare propoziție logică P, Q, R etc. în parte; să scriem de pildă P v 1P, C v 10 P v 1P etc. Aceasta se va putea realiza înlocuind P cu variabila pre- pozițională p, variabilă ce ține locul oricărei propoziții logice. Când spunem că formula P vlp 14 Calculul propozițional este propozițional validă înțelegem faptul că orice propoziție logică (P, Q, R etc.) am pune în locul lui p. propoziția logică obținută prin această înlocuire este adevărată. De pildă „plouă sau nu plouă”, „e soare sau nu e soare” sunt adevărate. Deși astfel de exprimări nu oferă nimic interesant din punct de vedere al cunoașterii, filosoful și logicianul austriac L. Wittgenstein le consideră „osatura lumii”1. Rămâne deschisă problema: cum putem stabili că o astfel de formulă este, după expresia lui Wittgenstein, o tautologie. dacă nu avem posibilitatea de a înlocui p cu fiecare dintre propozițiile logice (acestea fiind în număr nelimitat)? 5B. Tabela și funcția de adevăr a unei formule prepozi- ționale. Deși în număr-potențial infinit, propozițiile logice se împart în două categorii: adevărate și false. Dacă P este adevărată, 1 P este falsă (TAB 1), iar P v ~| P este A v F adică A (TAB v). Dacă P este falsă, 1P este adevărată, iar P v 1P este F v A, adică A. Prin urmare, deoarece negația și disjuncția logică sunt funcții (numai) de valoarea de adevăr a lui P, este suficient să verificăm că propoziția P v ~| P este adevărată pentru o singură propoziție adevărată și - respectiv - pentru o singură propoziție falsă pentru a trage concluzia că formulap v ~\p este validă. Concluzia, mai generală, ce se poate trage dintr-un astfel de raționament este că fiecare formulă propozițională a definește câte o funcție de adevăr. De pildă, formulele ^\p,p /\q.pv q.p=> q.p <=$ q definesc funcțiile de adevăr explicitate prin TAB 1 , TAB a , TAB v, TAB =>, TAB <=> respectiv. în general notăm TAB a tabela de adevăr a formulei a — tabelă ce explicitează funcția de adevăr definită de oc. 1 Tractatus Logico-Philosophicus, propoziția 6.124. B. Dezvoltarea calculului prepozițional 15 Exemple. 1) Pentru a: p v "| p tabela va fi conform celor de mai sus p pv~\p A F A F A A TAB pv~\p 2) Pentru a: p /\ (p => q) tabela va fi P <1 P=^<1 p^(p = A A K A A F F F F A A F F F A F TAB p a (p => q) 3) Pentru a: p a (p => q) => q (modus ponens) tabela de adevăr va fi P q /?A(p =>q A A A A A A F F F A F A F A A F F F A A TAB p /\(p=> q)=$ q Am condensat în această tabelă - sub forma celor trei co- loane finale — rezultate pe care, în tabela anterioară le-am repre- zentat separat. Sub fiecare dintre cei trei operatori ai formulei oc am așezat coloana valorilor de adevăr corespunzătoare. 16 Calculul prepozițional în concluzie, formula modusponens p a (p^q)=^q este propozițional validă, având pe coloana operatorului său principal (cf. 3B) un șir neîntrerupt de A. IXV 6B. Definiție Formula prepozițională pc este propozițional validă seiu identic adevărată dacă în TAB a coloana cores- punzătoare luia este alcătuită numai dinA. Y: 7B. După structura ultimei coloane din TABoc formulele prepoziționale a se împart în valide, contingente și inconsis- tente. Astfel, când ultima coloană conține a) numai A: a este validă'. b) și A și F: oc este contingență'. c) numai F: oc este inconsistentă. în primele două cazuri oc se numește consistentă, iar în ultimele două - nevalidă. Exemplu. Formulap a ~\p având tabela de adevăr p P a A F F A F F TAB p a ~\p este inconsistentă. Formula "] (p a 1 p) va fi deci, cf. TAB 1, validă h 1 (p a V). Ea traduce simbolic principiul necontradicțiev. o propoziție logică nu este în același timp adevărată și falsă. B. Dezvoltarea calculului prepozițional 17 8B. Căutarea unui contraexemplu. Alcătuirea tabelei unei formule clarifică deplin statutul său (validă, contingență sau in- consistentă). Când ea conține, de pildă, cinci variabile prepo- ziționale, tabelul va avea 25 = 32 de linii, presupunând foarte multe calcule. Câteodată putem clarifica mai ușor statutul lui oc, căutând un sistem de valori de adevăr ale variabilelor sale prepozițio- nale pentru care oc ia valoarea F. In caz că el există, poartă nu- mele de contraexemplu al lui oc și probează că oc este nevalidă. Când căutarea se blochează, arătând că nici un contraexemplu nu există, aceasta dovedește că formula a este validă. Exemplu', (p v q) a (p v r) => p v (q a r) Notăm oc: (p v q) a (p v r), (3: p v (q a r). O formulă oc => P este F dacă oc este A și P este F (TAB=>). Pentru ca oc să fie A trebuie (TAB a) ca (1) p v q și p v r să fie A. Pentru ca P să fie F trebuie (TAB v) ca (2) p și q a r să fie F. Trebuie, deci, găsite valorile pentru p, q, r care satisfac (1) și (2). Imposibil, deoarece q Ar este F dacă sau q sau r este F. Dar p fiind F (cf.(2)), fie p v q, fiep v r va fi F contrazicând (1). Blocajul apărut dovedește că formula considerată este validă. Pentru a compara metoda căutării unui contraexemplu eu cea a tabelei de adevăr, vom trata, cu aceasta din urmă, implicația conversă Y : P => oc. 18 Calculul prepozițional Tabela corespunzătoare este p q r q /\r p v (g A r) P q p v r (p v ^)a(p V r) 1 a V 0=>a A A A A A F F A A A A A A F A F A A A F F F A F F F A F F A F F A F F F TABy în ea cititorul trebuie să completeze cele șase linii rămase libere după modelul celor două completate. Utima coloană va fi alcătuită numai din A. Ceea ce dovedește că și y este validă. Observație. Validitatea celor două implicații conduce la validitatea echivalenței a <=> P, adică |= v(^ Ar)«(p v?) A(p v r)1. §9. Substituție și detașare Principiile logicii prepoziționale se exprimă simbolic numai prin formule valide. De aceea descoperirea celor dintâi se face, în logica simbolică, prin determinarea formulelor valide. Atât tabela de adevăr, cât și variantele sale (căutarea de contraexemple etc.) sunt doar căi de verificare a validității unor formule date. în timp ce noi trebuie să descoperim formu- lele valide. Printre metodele unei asemenea activități se înscriu substituția și detașarea. a) Substituția. Pentru a proba validitatea formulei prepo- ziționale 1 S-a demonstrat, astfel, echivalența E26 de la pag. 95. B. Dezvoltarea calculului prepozițional 19 (1) (p a (q v r)) v ~\(p a (q v r)) cititorul se poate aștepta la completarea unei tabele de adevăr complicate, în genul celei de mai sus. Dar privind mai atent, el poate să observe că de fapt această formulă are o structură mult mai simplă, perfect similară cu a formulei (2) p^p. Legătura dintre ele se stabilește printr-o operație numită substituție. Ea constă, în cazul de față, în înlocuirea fiecăreia dintre cele două apariții ale variabilei prepoziționale p din (2) cu formulap/\(qv r). întrucât (2) este validă (cf. TAB p v lp) formula (1) va fi și ea validă. De ce? Foarte simplu. Când determinăm, pentru valori de adevăr ale lui p, q și r date, valoarea de adevăr a lui (1), calculăm mai întâi valoarea de adevăr a formulei p a (q v r). apoi o introducem ca valoare a lui p în tabela de adevăr a lui (2). De aceea, în coloana finală găsim întotdeauna A. 'Su bstiîuim ■ o> yațiaȘi {fonhWT-eșpdc^ 10B. Observație. Această proprietate nu are loc dacă sub- stituția nu se face peste tot sau uniform. Spre exemplu, dacă înlocuim în p v"!p numai primul p cu p a (q v r), iar al doilea îl lăsăm neînlocuit, obținem formula {p/\(q vr)) v~\p. Ea este falsă cândp este A, iar q și r sunt F (verificați!) 20 Calculul prepozițional b) Detașarea k llB. -Pro/?rzeza/e Dacă a și p sunt formule prepoziționale atunci - >3 . Proprietatea decurge direct din TAB=>: când propozițiile logice P și P => Q sunt adevărate, propoziția Q este adevărată. Ea se numește detașare (sau modus ponens — după prin- cipiul logic pe care se bazează) deoarece permite desprinderea (validității) concluziei (3 din ipotezele (valide) a și a => p. §10. Echivalența formulelor prepoziționale 12B. Definiție. Formulele prepoziționale a și P se numeșii Utilizăm în acest caz notația a- p. ■ ; 13^. Proprietate. Relația a - P are loc dacă pentru orice valori de adevăr ale variabilelor prepoziționale;ce apar ,în; cele ;douu; formule, valorile de (din TABa și respectiv TABp) coincid. T;>■ Constatarea echivalenței se poate face alcătuind o tabelă de adevăr pentru amândouă formulele plecând de la toate variabilele prepoziționale ce apar în ele. Exemplu. Dacă a: p o 1/? q și /) : q, B. Dezvoltarea calculului propozițional 21 atunci tabela de adevăr a celor două pleacă de la variabilele propoziționale p șiq p 7 p vl p=>q A F F A F A F A A A F A A A F Echivalența oc ~ P rezultă în urma constatării că a doua și ultima coloană coincid1. Observație. Dacă am fi alcătuit separat tabela formulei q — care este ...g_ A F - o comparație directă între coloanele lui oc și P nu se putea face! Relația de echivalență joacă în calculul logic rolul pe care identitatea îl joacă în calculul algebric. Ea are trei proprietăți importante și anume: a) pentru orice formulă oc: oc ~ oc; b) pentru orice formule oc și P: dacă oc ~ P, atunci P - oc; c) pentru orice formule a, P, y: dacă oc ~ P și P ~ y, atunci oc ~y. Prima se numește reflexivitate, a doua simetrie, iar a treia tranzitivitate. 1 în virtutea acestei echivalențe când spune „... eu am, n-am înfățișare, la douăsprece trecute fix mă duc la tribunal!...”, Farfuridi afirmă de fapt „la douăsprece trecute fix mă duc la tribunal!” (a se vedea 3A). Calculul prepozițional 22 O relație având aceste trei proprietăți se numește echiva- lență (în cazul nostru - una logică) și împarte formulele propoziționale în clase de echivalență. Orice două formule din aceeași clasă sunt echivalente între ele, iar formulele din clase diferite sunt neechivalente. Astfel, toate formulele valide alcătuiesc o singură clasă; la fel și cele contradictorii (inconsistente); p și "| ~| p se află în aceeași clasă, dar p și q se află în clase diferite etc. Plecând de la o echivalență cunoscută a~ P putem descoperi noi echivalențe în virtutea unei proprietăți de înlocuire a expresiilor echivalente. Astfel, dacă Y« este o formulă propozițională în care apare - ca parte alcătuită din simboluri consecutive ale sale - formula propozițională oc, vom nota Yp rezultatul înlocuirii lui oc cu p (în una sau mai multe dintre aparițiile sale în y«)- Exemplu. (p => p v q) a (p v q) a: pv q, P : q v p Atunci Yp poate fi oricare dintre formulele: O => q v/7) a (p v 7), (p =>p vq) a (q vp), (p^qvp)/\(gvp). Iii® Astfel, deoarece conform E71 p vq~q vp, rezultă Ya~Yp pentru oricare Yp dintre cele trei de mai sus. Proprietatea are multe consecințe utile, printre care și urmă- toarea: 1 La pagina 94 găsiți o listă cu 50 de echivalențe logice valide notate Eb E50. B. Dezvoltarea calculului propozițional 23 ^djiBiațnegațîe)<: Suprimând sau introducând o > dublă. fpir|iuie;a;șe obpnb o formulă echivalentă cu a. 15B. Observație. Formulele calculului propozițional au fost construite cu ajutorul a cinci operatori logici 1, a, v, =>, în virtutea proprietății 14B și a unora dintre echivalențele Ew, £!b £I3, Eu, Eu, E\s fiecare dintre ele este echivalentă cu câte o formulă conținând doar operatorii 1, a respectiv 1, v. Exemplu. ya.' p =$ (q r) a: r a) Dacă notăm Ș:l(^ a >), conform £14 a~ p, deci, aplicând 14B, y«~YP’ unde Yp : p 1 {q a ”1 r). Substituind i» ? cu 1 te a 1 obținem conform 9B Astfel, prin tranzitivitatea echivalenței v ~1(pA(?Alr)). ja 1 . o 1 zv v/ r conform El3 b) Dacă notam (3 • I q v a~ P> deci aplicând 14B: H Y«~Yp, , . n => 1 q v r. unde Y/5 • ? -| z7 v r, obținem conform 9B Substituind în Eu, q cU 24 Calculul propozițional Yp - v ("] q v r), iar prin tranzitivitatea echivalenței Ya ~ "Ip v (1 q v r). §11. Dualizarea formulelor propoziționale Echivalențele E8:1(a a P)~1a v lp E9:1 (a v P) ~ 1 a a 13 (cf. pag. 94) numite legile De Morgan' evidențiază o simetrie între operatorii a și v. Ea poate fi utilizată în scopul transfor- mării unei formule propoziționale a care conține doar cei doi operatori și variabile propoziționale simple sau negate. Exemplu'. Y : p v (q a "] r). 1Y ~ 'lpA'l(îAlr) ~ "lp a ("] ^ v "I "I r) Notăm y : A ("19 v Ș' rezultă 1y~ Y • 1 Logicianul care, deși nu le-a descoperit, le-a arătat utilitatea. B. Dezvoltarea calcululuipropozițional 25 Numim duala unei formule prepoziționale oc ce conține doar operatorii a, v și variabile prepoziționale simple și/sau negate, formula oc' obținută din ea inversând operatorii a și v între ei. Exemplu. Dacă oc: p v (p a 1 q), atunci oc': p a (p v 1 q)- Să observăm că (oc')' este oc. 17B. Prppne/a/e. Dacă a și 0 sunt formule prepoziționale de tipul descris în proprietatea 16B, iar a' și 0' sunt dualele lor și : Reciproca, se obține din proprietatea directă utilizând faptul că (a1)' este a și (0')' este 0. Vom demonstra proprietatea 17B în cazul formulelor a : p v (q a r), 0 : (p v ?) A W Din a ~ 0 (vezi observația de la pag. 16) rezultă, cf. 14B, că: Icr-lp. Pe de altă parte, cf. 16B, avem: "la-ași^-P- Deci a ~ 0, adică lfA<1?v»-(Va Ia Substituind p cu V, ? cu 1r cu 1 r, conform 9B rezultă: in final, suprimând dublele negații pe baza regalei DN, obținem: 26 Calculul propozițional p /\ (qvr)~(p q) v (p /\ r). Aceasta este proprietatea de distributivitate a conjuncției față de disjuncție. Așadar, cele două legi de distributivitate (a față de v, v față de a) sunt duale una celeilalte. Validitatea uneia o implică, în virtutea proprietății 17B, pe a celeilalte. §12. Forme normale a) Forma normală conjunctivă. Verificarea validității unei formule propoziționale prin tabele corespunzătoare de adevăr este un procedeu incomod. Pentru anumite formule însă, vali- ditatea (sau nevaliditatea) se poate observa direct. Acesta este cazul dișjuncțiilor de două sau mai multe varia- bile propoziționale simple sau negate. Exemple. 1) Disjuncția1 p v q v ~\p conține aceeași variabilă prepozițională (p) simplă și negată. Deci tabela ei de adevăr va avea pe ultima coloană valoarea A și când p este A și când p este F; disjuncția este validă. 2) Dimpotrivă, disjuncția p x/ q v ”]r este F când p, q sunt F și r este A. Concluzie. O disjuncție de variabile propoziționale simple și/sau negate este validă dacă și numai dacă aceeași variabilă apare simplă și negată. 3) Formula oc: p v ~] q v (q a ~| p) este echivalentă, în virtutea distributivității disjuncției față de conjuncție (E26 de la pag. 95) cu 1 în virtutea echivalenței E23. a v (0 v y) ~ (a v |3) v y (asociativitatea disjuncției) parantezele pot fi, în acest caz, omise. B. Dezvoltarea calculului propozițional 27 (p v h v ?) a (/? v v lp). O conjuncție este validă numai atunci când fiecare termen al său este o formulă validă. Ceea ce este, în cazul de față, ade- vărat. Așadar oc este validă. în general, orice formulă prepozițională oc poate fi transformată într-o formulă, echivalentă cu ea, de forma1 OCj A 0C2 A ... A 0C„ în care fiecare oc, este o disjuncție de variabile prepoziționale simple și/sau negate. Aceasta se numește forma normală conjunctivă a lui oc. Dacă în fiecare oc, figurează cel puțin o variabilă prepozițio- nală atât simplă cât și negată, atunci oc este validă. Dacă în cel puțin un oc, acest lucru nu se întâmplă, atunci a nu este validă. b) Forma normală disjunctivă. Formula 1 oc este validă dacă oc este inconsistentă (sau identic falsă) și reciproc. Proprietatea unei formule propoziționale oc de a fi identic falsă se poate constata — fără alcătuirea unei tabele de adevăr — prin transformarea ei într-o formulă echivalentă de tipul 0C1 V oc2 v ... V oc„ unde fiecare oc, este o conjuncție de variabile propoziționale simple și/sau negate. Conform TAB v, oc este identic falsă numai atunci când fiecare oc, este identic falsă. La rândul său formula oc, este identic falsă atunci și numai atunci când în ea figurează o aceeași variabilă propozițională atât simplă cât și negată. Exemplu. Formula oc: p a q a (1 p v 1 r) se transformă în virtutea distributivității conjuncției față de disjuncție (E25 de la pag. 95) în formula echivalentă 1 Omiterea parantezelor se datorează echivalenței E22- a a (P a y) ~ (a a p) a y (asociativitatea conjuncției) 28 Calculul propozițional (p A ț A l/î) V (/? A <7 A r) Ea reprezintă o formă normală disjunctivă a lui oc. întrucât al doilea termen al disjuncției nu este inconsistent (ia valoarea A când p și q sunt A, iar r este F) nici oc nu este inconsistentă (fiind A pentru aceleași valori ale lui p, q și r). Prin urmare ~| oc nu este validă. C. Axiomatizarea calculului propozițional §13. Metoda axiomatica în lucrarea „Elementele”, Euclid din Alexandria face, apro- ximativ cu 300 de ani înainte de Hristos, o expunere sistema- tică a propozițiilor fundamentale ale geometriei din vremea sa. Plecând de la un număr restrâns de axiome și postulate el deduce, pe cale logică, toate celelalte propoziții. Deși, rapor- tată la standardele de azi, lucrarea conține unele imperfecțiuni, ea a rămas modelul de conciziune și rigoare în prezentarea unui ansamblu de cunoștințe teoretice. S-a bucurat de un așa de mare succes încât, în secolul al XVII-lea, filosoful olandez B. Spinoza își scria tratatul său de etică în forma axiomatic deductivă a Elementelor. Apogeul metodei axiomatice urma să fie atins tot în geo- metrie, 2200 de ani după Euclid, prin cercetări legate de postu- latul paralelelor1. Apariția unor geometrii „neeuclidiene”, în care acest postulat este fals, a condus la o răsturnare a concep- ției despre „adevărat” și „fals” în științele deductive. 1 într-o formulare modernă, acest postulat afirmă „La o dreaptă dată, printr-un punct dat care nu se află pe dreaptă, trece o paralelă și numai una”. C. Axiomatizarea calculului prepozițional 29 Concomitent, apariția unor paradoxuri în teoria mulțimilor1 a focalizat atenția cercetătorilor domeniului asupra demon- strației matematice, introducând standarde ridicate de rigoare formală. S-a impus astfel ideea după care însăși logica - com- ponentă esențială a oricărei demonstrații — să fie organizată după modelul axiomatic deductiv propus de Euclid. Aceasta presupune o ierarhizare a principiilor logice, unele fiind alese drept axiome din care toate celelalte se deduc pe baza unor reguli explicit formulate. Deducția capătă caracterul unor transformări ce se fac în virtutea formei și nu a con- ținutului.2 §14. Axiome și reguli deductive a) Axiome. în orice știință deductivă un adevăr este recu- noscut ca atare dacă producem o demonstrație a sa. Cum orice demonstrație pleacă de la adevăruri anterior recunoscute, vor exista, cu necesitate, adevăruri fără demonstrație. Acestea sunt axiomele. Alegerea axiomelor calculului propozițional nu este arbi- trară, deși există mai multe alegeri posibile. în primul rând, axiomele trebuie să fie formule valide. Axiomele trebuie să fie „suficiente” în sensul de a putea de- duce din ele toate formulele valide. întotdeauna verifică și con- diția de a reprezenta „minimul” suficient (adică să nu putem deduce pe una din celelalte). Prezentăm în cele ce urmează un sistem alcătuit din 13 axi- ome, propus de logicianul german G. Gentzen3. Ele se împart 1 A se vedea anexa III. 2 Acest tip de exigențe au fost formulate în cadrul unui program de fundamentare a întregii matematici inițiat și condus de matematicianul german D. Hilbert (1862-1943). El s-a numit „programul formalist” (cf. anexa III). 3 Untersiichungen liber das Logische Schliessen, Mathematische Zeitschrift, voi. 39, pg. 176-210, 405-431. 30 Calculul propozițional în 5 grupe, fiecare corespunzând câte unuia dintre cei 5 opera- tori logici. Primele două sunt axiomele de introducere a operatorului => într-o formulă logică (pe scurt: axiome de => - introducere): 8SS) W se împart în: una de <=>-introducere Jă(a£.W și două de <=> - eliminare C. Axiomatizarea calculului prepozițional (qx9a) (p <=> q) =4(p => q), (ax 9b) (p <=>q) =$ (q=>p). b)Reguli deductive Regula S (substituția). Din formula propozițională a se deduce formula obținută substituind în a variabilele prepoziționale distincte pb ...,pm cu formulele prepoziționale pb ..., (3„ respectiv. Regula Z> (detașarea) Din formulele prepoziționale oc și oc => (3 se deduce formula Observație. Regula D, numită și => - eliminare ține locul unei axiome de => - eliminare ce nu figurează printre cele 13 axiome de mai sus. §15. Demonstrație și deducție înainte de a preciza ce este demonstrația să considerăm un: IC. Exemplu de demonstrație în calculul prepozițional. (1)p => (p =>p) ax\a (q/p) S (2) (p => (p =^p)) => ((p => ((p =>p) => p)) =^> (p =>p)) ax 1 b (q/'p^p, r/p) S (3) (p => ((p =^>p) =>p)) (p =>P) (4)/2=>((p=>/>)=>p) (^P=^P ax 1 a (qlp=sp) S 4,3 D 32 Calculul propozițional Așadar, un șir de 5 formule propoziționale obținute fiecare, fie prin substituție dintr-o axiomă, fie prin detașare din două formule anterioare ei în șir. Șirul de mai sus este demonstrația formulei p => p, ce devine — în virtutea existenței acestei demonstrații — o teoremă a calculului propozițional. |ioitialăun șiț: finit de formule propoziționale, fiecare dititre acestea fiind " ' H;.x; ț£gă).fiă’O axiomă sau obținută priit substituție dintf-p;axipmă;' > ■i: ;b). fîe:pbțipută că rezultat al aplipărîț peguîii î) petitiîi;sdpuă formule anterioare ei în șir.; o"'-r ' ' X.‘ prinuiă-finală ă unei demonstrații .se numește -teoremă. j V i]Hăț.... Definiție; Șe * numește. deducție ' —: în'.' călcUlul ’pfopS: Szițibnal X din formulele propdzițioriaie oct,uif șir finit ^ărfonțiule prepoziționale, fiecare dintre ele fund ;> • = X-; a) fie o formulă țq => r) |- r este o relație de deductibilitate. Iată deducția corespunzătoare: 1) q ipoteză 2) p ipoteză 3) p => (q => r) ipoteză C. Axiomatizarea calculului propozițional 33 4) q => r 2,3 D 5) r 1,4 D Se observă că o demonstrație este cazul particular al unei deducții fără ipoteze. Așadar, fiecare teoremă este concluzia unei deducții fără ipoteze. Motiv pentru care vom pune înain- tea fiecărei teoreme semnul De pildă: \-p=*p- De obicei, prin extensie, același semn se pune și în fața axiomelor, ce pot fi considerate ca un caz limită de teoreme a căror demonstrație se reduce la o singură formulă: axioma însăși. §16. Elemente de teoria demonstrației Proprietățile relației de deductibilitate și ale cazului său particular - demonstrabilitatea - formează obiectul teoriei demonstrației. Ea s-a dezvoltat ca o combinatorică a șirurilor finite de simboluri ce se transformă după reguli clare și explicite. Enunțăm în continuare proprietăți ale relației de deducti- bilitate, în care oc, P, y, ot], Pi, ... sunt formule propoziționale. 5C. oci, ..., oc„ oc/n |- ce, pentru orice i = 1,m. 6C. Dacă ab a„, F Pi; ... ; ab ..., a„, F PF și dacă pb ..., P/7 F Y> atunci ocb •••> FY- 7C. Dacă F a => P> atunci a F P- 8C. Dacă ab ■ otm-i F a«> =* P> atunci ab am-b F P- 9C. Dacă a F P’ atunci F a => P- 34 Calculul prepozițional IOC. Dacă (Xî, ct„, P, atunci ai, •••, am-i |- a„, => B. Prima dintre proprietăți se referă Ia cazul unei deducții în care concluzia coincide cu una dintre ipoteze. Deducția se reduce, în acest caz, la ipoteza a,. Pentru 6C plecăm de la o deducție a lui y din Pi, ..., Pp. în acest șir de formule intercalăm, în fața fiecărui P„ un șir repre- zentând deducția lui P, din ipotezele aj,..., a,„. Noul șir de for- mule astfel obținut va reprezenta deducția lui y din aj,..., am. Exemplu. în deducția p(ipoteză), r(ipoteză), p => (r => p a r) (ax 2), r => p a r (D), P^r(D) justificând relația de deductibilitate p, r \-p /\r, intercalăm, în fața primei ipoteze, deducția P a (7 => r) (ip.), p * (q => r) => p (ax 3a), p (D), justificând relația de deductibilitate <7- P a (q => r) f-p. In fața celei de a doua ipoteze intercalăm deducția p a (4 => r) (ip.), p a (q => r) => (q => r) (ax 3b), q=>r (D), q (ip.), r(D), justificând relația de deductibilitate g'.pAț^r) |-r. Șirul de formule obținut prin aceste intercalări (1) p A(^=>r) (2) p a (<7 => r) =>p ip. ax 3a S C. Axiomatizarea calculului prepozițional 35 (3)/? 1,2 D (4) p(q r) =} (q => r) ax 3b 5 (,5)q=^r 1,4 D (6)7 ip. (7)r 5,6 D (8) p => (r => p a r) ax 2 (9) r => p a r 3,8 D (10)p a r 7,9 D justifică relația de deductibilitate 7, p a (q => r) }-p A r. 7C este un caz particular al proprietății 8C. în cazul celei din urmă, pentru a găsi o deducție a formulei 0 din ipotezele oc15 aw pornim de la deducția lui => 0 din ipotezele 0Cj, oc„,_i, deducție pe care o completăm astfel (*) (k+ 1) (k + 2) C£m 0 otnj 0 ip. k, k + 1 D Acest șir de k + 2 formule reprezintă deducția lui 0 din aceleași ipoteze și justifică relația de deductibilitate ab am_,, a„, |-0. 9C este un caz particular al proprietății IOC numită și teorema deducției. Ea fundamentează una dintre cele mai larg răspândite metode de demonstrare a unei implicații oc => 0; anume aceea prin care, plecând de la ipoteza oc deducem concluzia 0. Ilustrăm printr-un exemplu metoda de a demonstra IOC. 36 Calculul prepozițional Plecând de la deducția (cf. 4C) corespunzătoare relației de deductibilitate P> P =* (q => r) |-r vom construi deducția corespunzătoare relației de deductibilitate 7. p (q => r) \-p => r Reamintim că prima deducție este alcătuită din 5 formule: 7, p, p => (q => r), q => r, r. Pentru a o construi pe cea de a doua plecăm de la șirul de 5 formule: (*) p => q,p=>p,p=>(p=>(q=>ry),p=>(q=>r),p^r Deși se termină cu formula-concluzie a celei de-a doua relații de deductibilitate, el nu este, cum se poate observa, o deducție din ipotezele q și p => (q ==> r). în schimb, reprezintă „scheletul” pe care vom construi o astfel de deducție. Și anume intercalând înaintea fiecăreia dintre formulele șirului (*) o deducție a formulei respective din ipotezele q și p => (q => r). Pentru a putea urmări mai lesne procedeul, așezăm în coloane paralele deducția inițială și pe cea obținută din (*) prin intercalare. (15) (p=>p)=> [(p=>(^=>r))=»(p=>r)] ax\b (16) (p => (q => r)) => (p => r) 8,15 (17) p=>r 14,16 Deducția inițială Deducția obținută din (*) prin intercalare 38 Calculul propoziționa! §17. Necontradicția calculului prepozițional Cititorul și-a putut face deja o părere asupra metodelor prin care se obțin demonstrațiile în calculul prepozițional. Unul dintre primele scopuri ale teoriei demonstrației este de a arăta că în urma procesului demonstrativ nu se poate ajunge la o teoremă oc și în același timp la teorema 1 oc. Proprietatea în cauză se numește necontradicția sau consistența calculului prepozițional. Ea decurge din următoarea 11C. Proprietate Orice teoremă a calculului propozițional este o formulă prepozițional validă. pentru orice formulă prepozițională a. ;7 Această proprietate este consecința următoarelor fapte. a) Cele 13 axiome ale calculului propozițional sunt formule prepozițional valide. b) Conform 9B o formulă obținută prin regula substituției dintr-o formulă validă este, la rândul ei, validă. c) Conform 11B o formulă obținută prin regula de detașare din două formule valide este și ea validă. Prin urmare, teoremele calculului propozițional, care se ob- țin din axiome prin cele două reguli deductive, vor fi propo- zițional valide. ; 12C, Consistența (sau necontradicția) calcului < Pentru orice formulă prepozițională O, nu sunț simultan adevărate !< . y? y-y\- Conform 1 IC, dacă |- a și a ar fi adevărate, atunci a și 1 a ar fi propozițional valide, ceea ce contrazice definiția validității prepoziționale (6B) și TAB~|. C. Axiomatizarea calculului prepozițional 39 13C. Observație. în calculul prepozițional are loc, pentru orice formule propoziționale oc și P, relația de deductibilitate oc, loc |- P (1 - eliminarea, vezi § 18) Așadar, dacă pentru o formulă propozițională oc, atât oc cât și 1 oc ar fi demonstrate, atunci toate formulele propoziționale ar fi demonstrabile. Astfel încât demonstrabilitatea n-ar mai putea servi drept criteriu al adevărului. Consistența sau necontradicția implică așadar existența a cel puțin unei formule nedemonstrabile. §18. Reguli deductive derivate Pe măsură ce avansăm în procesul de demonstrare a teore- melor calculului prepozițional, demonstrațiile devin lungi și de aceea greu de construit și chiar de urmărit. Motivul stă în numărul mic al regulilor deductive (două) pe care Ie putem utiliza. Putem lărgi însă acest număr asociind fiecărei axiome câte o regulă deductivă corespunzătoare. Acestea sunt de fapt proprietăți ale relației de deductibilitate (similare celor din §16) și care se pot demonstra. Ele se numesc reguli deductive derivate. Pentru fiecare din cei 5 operatori logici dispunem de reguli de introducere și de reguli de eliminare a operatorului respectiv. Astfel, pentru operatorul => : - introducere r,atp r|-a=>/3 Această regulă în care T reprezintă o listă, posibil vidă, de formule propoziționale, corespunde proprietății IOC1. 1 Linia de fracție, cu ajutorul căreia am exprimat regula de => -introd. înlocuiește expresia .,dacă... atunci...". 40 Calculul propozițional =>-eliminare a, a => P f- P Aceasta este regula de detașare sau modus ponens. Pentru operatorul a: a — introducere a, P a a P oca p (-a și oca p |-P Așadar, o regulă de introducere și două de eliminare. Pentru operatorul v: oc |- oc v p și P |- oc v p r, ocH___________r, P|~y r, ocvp |-y r are aceeași semnificație ca în regula => - introducere. Pentru operatorul 1: 0 - introducere r,oc|-p r,ocFlP r|--|a 1 — eliminare TI oc |- oc și a, 1 a P Prima dintre cele două reguli de ~| -eliminare se mai nu- mește „eliminarea dublei negații” (DN-elimin.) C. Axiomatizarea calculului propozițional 41 Pentru operatorul <=>: — introducere / a=> 0, 3 => a F a<=> 3 a<=>3Fa^>3 Ș' a.-j=> 3 h 3 => a Având la îndemână proprietățile 5C-10C și cele 14 reguli de deducție dispunem de mai multă libertate de mișcare în pro- cesul de demonstrație. Iată, de exemplu, demonstrarea regulii transpoziției'. a=>3 13 => la (1) a=> 3, a, 13 |-a=> 3 (2) a => 3, a, 13 pa (3) a, a=> 3 F 0 (4) a => 3, a, 13 F 0 (5) a => 3, a, 13 F10 (6) a=>0,10 Fia (7) a^3F13=>la 5C 5C => -elim. 1,2,3 6C 5C 4, 5 1 -introd. 6 IOC 14C. Comentariu. Vizând acest șir de relații deductive, cititorul poate fi derutat în privința „strategiei” construirii sale. încercând să-1 lămurim vom parcurge aceste relații de la ultima spre prima; începem cu cea de demonstrat: a=>0 F10 => 1 a. 1 Reamintim că implicația ~| [3 cx se numește transpusa implicației a=> (3. 42 Calculul propozițional Trecând în revistă cele 14 reguli deductive vom constata că singurele ce au în dreapta simbolului |- operatorul =>, sunt => - introd. și <=> - elim. Deoarece în ipoteza relației de demonstrat nu figurează <=> ne fixăm asupra => - introd. în temeiul acestei reguli, relația de demonstrat se obține din relația cx => p, "| P "| a1. în concluzia noii relații apare operatorul "I , pentru a cărui introducere sunt necesare - prin regula 1 -introd. - două relații de forma a p, 1 p, a P y și oc => P, 1P, oc |-1Y- Rămâne să găsim o formulă y pentru care cele două relații să fie adevărate. Nu este greu de observat că o astfel de formulă este chiar p. într-adevăr relațiile ce => p, 1 P? oc |- P și a P, 1P, oc IP se obțin pe baza regulii de => -eliminare și a proprietății 5C. Primele patru linii din demonstrație nu sunt decât o cale de a face acest lucru (utilizând și proprietatea 6C). Iată, cu aceleași mijloace, demonstrația principiului tertium non datur (terțul exclus). |-(xv |a unde a este o formulă prepozițională. (1) a |- a v 1 a v - introd. (2) 1 (a v 1 a) |-1 a 1 transp. (3) la l-avla v-introd. (4) l(av"|a) hlla 3 transp. (5) |- TI (a v 1 a) 2, 4 1 -introd 1 Această relație deductivă corespunde unui principiu deductiv pe care primii logicieni, începând chiar cu Aristotel (384-322 înainte de Hristos) l-au remarcat, alături de modus ponens. El s-a numit modus tollens. C. Axiomatizarea calculului propozițional 43 (6) H (a v 1 a) j- a v 1 a DN-elim. 5,6 6C (7) |- a v 1 a §19. Completitudinea calculului propozițional Consistența calculului propozițional este, conform 13C, con- diția de a nu putea demonstra toate formulele propoziționale. Completitudinea este condiția de a putea demonstra toate formulele valide și se mai numește de aceea completitudine în raport cu validitatea. Demonstrarea sa se bazează pe urmă- toarea constatare: Vom exemplifica afirmația redând relațiile de deductibi- litate corespunzătoare celor două linii din TAB 1: p b F F A P HI/? F"!^ și ceior patru linii din TAB a P <1 p^q A A A p> q F p a q A F F p,~\q F 1 (p a q) F A F 1A q F1 (P a q) F F F Ip, ~\q F l(p a q) 44 Calculul propozițional Iată, ca exemplu, deducția corespunzătoare relației de deductibilitate p, ~\q |- (p a q): (1) /?, ~\q,p Aq |-1 q 5C (2) p, 1 q, p a q |-/> a q 5C (3) p a q |- q A-elim. (4) p, 1 q, p a q |- q 2, 3 6C (5) p, ~\q |- l(p a q) 1,4 1-introd. Se obțin astfel 18 relații de deductibilitate adevărate, cores- punzătoare celor 18 linii din aceste 5 tabele. Prin extensie, pentru fiecare formulă prepozițională se obține - corespunzător fiecărei linii din tabela sa de adevăr - câte o relație de deductibilitatate. Spre exemplu, pentru formula p a (p => q) având tabela la pag. 14, corespunzător celor patru linii ale acesteia se pot obține relațiile de deductibilitate: p, q \-p *(p=>q) p,~\q |-1 (/? a (p => ?)) 1/?, q |-1 (p ~\pj\q |-1(P A(p=> q)) Iată, de pildă, cum se obține a doua dintre aceste deducții: (1) p, 1 q,p a (p => q) F 1 q 5C (2) \-p A-elim. (3) p A(p^ q) \-p^ q A-elim. (4) p, P => q F q => - elim. (5) p a (p => q) F q 2,3,4 6C C. Axiomatizarea calculului prepozițional 45 (6) 77, ~\q, p/\ (p => q) l-p A.(p=>q) 5C (7) p, ~\q,p/\ (p => q) \-q 5,6 6C 7>,1 <1 F "I (P A (P => ?)) 1,7 1-introd. In cazul unei formule a prepozițional valide și care conține doar variabilele propoziționale p și q, relațiile de deducție corespunzătoare celor patru linii din TAB a vor fi: (1) P,q |-a (2) p, 1 q F a (3) q F a (4) 1a19 Fa, din care deducem: (5) p, q v 1 q l-a 1,2 v-elim. (6) ~\p, q V 1 q Fa 3,4 v-elim. (J)p v~\p,qv~\q Fa 5,6 v-elim. în mod analog: Observație. Drept caz particular al proprietății 6C (când m = 0) din F3i,F Ppși Pi,..., PP FY rezultă: FY- în virtutea demonstrației de la pag. 42 F/?l V Ipi, ..., FPnVlpn- 46 Calculul prepozițional Deci pentru orice formulă prepozițional validă a, conf. 16C, rezultă: I- oc. Exerciții 47 Exerciții (Soluții la pag. 88) 1. Urmăriți raționamentul următor: Animalele îl iubesc dacă le hrănește sau (măcar) nu Ie lovește. El le hrănește și (totuși) animalele nu îl iubesc. Deci le lovește. a) Utilizați următorul dicționar: I: animalele îl iubesc, H: le hrănește, L : le lovește, pentru a transcrie în limbaj simbolic cele trei propoziții ale raționa-mentului. Cuvintele-cheie — scrise cursiv — indică utilizarea câte unui operator logic. Determinați-1 bazându-vă pe cele discutate în capitolul A. b) înlocuind fiecare dintre cele 3 propoziții simple I, H și L prin variabilele propoziționalep, q și r, scrieți formulele cei, a2, P corespunzătoare celor trei propoziții ale raționamentului. c) Verificați validitatea logică a raționamentului ca validitate propozițională a implicației ocj a a2 => P- d) Arătați că formula (Xj a oc2 este inconsistentă. Ce rezultă de aici cu privire la validarea raționamentului când se înlocu- iește concluzia sa („le lovește”) cu orice altă propoziție logică? 2. Se consideră raționamentul: Dacă impozitele nu cresc, atunci se înregistrează un deficit bugetar. Dacă se înregistrează un deficit bugetar, sumele alocate asistenței sociale scad. 48 Calculul propozițional Impozitele cresc. Deci sumele alocate asistenței sociale nu scad. a) Determinați propozițiile simple și operatorii logici prin aplicarea cărora puteți transcrie în limbaj propozițional cele patru propoziții ale raționamentului. b) Construiți cele patru formule propoziționale (A, (fe P corespunzătoare acestor patru propoziții. c) Verificați validitatea propozițională a formulei ot] a a2 A oc3 => p. Ce rezultă de aici cu privire la validitatea logică a raționa- mentului în cauză? 3. Utilizând descompunerea în propoziții simple și notațiile in- dicate în paranteze pentru acestea, stabiliți validitatea propo- zițională a următorului raționament: Dacă suspectul comitea jaful (5), atunci utiliza un plan (P) sau avea un complice în interior (Q. Dacă utiliza un plan, atunci fura valori importante (T). Dacă avea un complice în interior, acesta ar fi fost desco- perit (D). Nu a furat valori importante și nici un complice nu a fost descoperit. Deci suspectul nu a comis jaful. 4. (după Keisler). Trei persoane X}, X2, X3, bănuite de evaziune fiscală, declară fiecare sub prestare de jurământ: X] : X2 este vinovat și X3 este nevinovat; X2: dacă X] este vinovat, atunci X3 este vinovat; X3 : sunt nevinovat și cel puțin unul dintre ceilalți doi este vinovat. a) Transcrieți în limbaj propozițional cele trei declarații utilizând dicționarul P,: Xi este vinovat, (z = 1, 2, 3) și operatorii logici. Exerciții_____________________________________________________— b) Construiți cele trei formule propoziționale (Xi, «2, corespunzătoare acestor declarații și verificați dacă ele sunt consistente, verificând consistența (necontradicția) formulei OC] A 0C2 A OC3 (cf 7B). c) Pentru a verifica dacă declarația unuia dintre suspecți rezultă din declarația altuia, verificați care dintre cele șase formule a, 09 (z ^7) este propozițional validă. d) Dacă cele trei persoane sunt nevinovate, care dintre ele a depus mărturie falsă? e) Presupunând că cei nevinovați au spus adevărul, iar cei vinovați au mințit puteți preciza cine sunt vinovați și cine nu? 5. Construiți deducțiile (cf 9C) care să justifice următoarele relații de deductibilitate: a) p, q \-p^q \-p c) p [pvq d) 11/? (-/? e) A ~\p\-q (a - introducere) (a - eliminare) (v - introducere) (11 - eliminare) (1 - eliminare) II. CALCULUL PREDICATELOR D. Idei introductive §20. Insuficiențe ale calculului propozițional în prima parte am studiat un instrument logic capabil de a justifica validitatea anumitor raționamente. Dar nu a tuturor acelora pentru care avem motive întemeiate să le considerăm drept corecte din punct de vedere formal. Spre exemplu, când din propoziția Toți peștii trăiesc în apă deducem propoziția Peștii răpitori trăiesc în apă, o facem în virtutea unui principiu după care ceea ce este adevărat în toate cazurile, este adevărat și în cazuri speciale. Formal însă, cele două propoziții sunt propoziții simple, adică nu pot fi obținute transformând alte propoziții prin intermediul celor cinci operatori logici. Simbolizându-le prin P și respectiv Q, structura logică a celor două afirmații este redată de formulele p și q. care sunt variabile prepoziționale distincte. Relația de deductibilitate p [q este echivalentă, în virtutea 7C și 9C, cu \-p^q- Ceea ce, conform 1 IC și 17C, echivalează cu ¥p=>q- D. Idei introductive 51 Această condiție nu este îndeplinită, deoarece formula p => q nu este validă. Ceea ce nu reprezintă un argument împotriva validității logice a deducției din exemplu, ci doar o dovadă că mijloacele calculului prepozițional sunt insuficiente pentru a o justifica. Rămâne să vedem cum pot fi dezvoltate aceste mijloace pentru atingerea unui asemenea scop. §21. Structura logica a propoziției simple Tratate ca propoziții simple, între P și Q din exemplul anterior nu apare nici o legătură logică. Totuși o astfel de legă- tură există și va trebui pusă în evidență. Vom face de aceea o analiză logică a structurii unei astfel de propoziții. Analiza gramaticală o descompune în subiect, predicat, atribut, complement etc. Analiza logică distinge doar două componente: subiectul logic și predicatul logic. De exemplu, propoziția Andrei este apreciat, este alcătuită din subiectul logic „Andrei” și predicatul logic „este apreciat”. Dar, dacă dorim ca acest predicat să poată fi aplicat și altor subiecte logice, vom scrie (1) x este apreciat unde variabila x poate lua anumite valori, pentru fiecare dintre ele expresia (1) devenind o propoziție logică. Este ceea ce în matematică reprezintă o funcție; aici este vorba de o funcție prepozițională. Notația pe care o adoptăm este legată de notația unei funcții matematice, anume F(x) 52 Calculul predicatelor care, în cazul funcției propoziționale (1) va fi Ax. înlocuirea lui x prin subiectul logic „Andrei”, notat a, conduce la notarea propoziției date cu Aa]. Să trecem la un alt exemplu: Andrei este apreciat de Ileana. Aici putem considera diverse predicate logice (funcții pro- poziționale): x este apreciat de Ileana; Andrei este apreciat dej; x este apreciat dej. Observăm că ultimul dintre ele este mai general deoarece permite obținerea primelor două prin înlocuirea uneia dintre variabilele x și j prin câte un subiect logic. Dacă îl vom nota cu propoziția din exemplu va căpăta forma A ai (i reprezentând subiectul logic Ileana). Continuăm seria exemplelor cu încă două propoziții Andrei se autoapreciază; (2) Andrei este apreciat de toți. în primul caz putem considera un nou predicat „x se auto- apreciază”, dar credem că este mai adecvată, în acest context, utilizarea predicatului Axy sub forma Aaa (Andrei este apreciat de-Andrei). 1 Notația aceasta inversează ordinea naturală: subiect-predicat. Este preferată deoarece poate fi mai comod generalizată la cazul predicatelor care acceptă mai multe subiecte, așa cum se va vedea în cele ce urmează. D. Idei introductive 53 Reușim astfel să punem în evidență scheletul comun al propozițiilor anterioare. Vom discuta acum propoziția (2). §22. Cuantificarea subiectului logic Considerând „toți” ca subiect logic - să-l notăm t - putem utiliza același predicat Axy pentru a reprezenta (2) sub forma Aut. Realizăm astfel ceea ce se numește o formă în dezacord cu conținutul! Căci „toți” nu reprezintă în (2) un subiect (per- soană sau colectiv de persoane) care îl apreciază pe Andrei, ci expresia sintetică a afirmațiilor simultane: Andrei este apreciat de Ileana, Andrei este apreciat de Andrei etc. Cu alte cuvinte că pentru fiecare x (persoană), Andrei este apreciat de x. Această idee — de cuantificare a subiectului logic x într-o funcție propozițională (aici Aax) - se exprimă simbolic prin așezarea cuantificatorului general sau universal Vx1 în fața acelei funcții propoziționale Vx Aax. Expresia se citește pentru toți x: Andrei este apreciat de x. Cuantificarea subiectului logic este una dintre cele mai fecunde idei pe care se bazează calculul predicatelor. Cu aju- torul ei putem exprima, utilizând predicatul Axy, și prima dintre propozițiile analizate Andrei este apreciat. Pentru aceasta vom apela însă la celălalt tip de cuantificare: particulară sau existențială. Ea se exprimă simbolic punând în fața predicatului Aax cuantificatorul particular sau existențial 3x 3 x Aax. 1 A răsturnat - (V) - este inițiala cuvântului all = toți (în 1. engleză). 54 Calculul predicatelor Expresia se citește pentru unii x: Andrei este apreciat de x, sau există unii x pentru care: Andrei este apreciat de x. Regăsim aici o formulare explicită a ceea ce, într-o formă eliptică, se găsea exprimat prin Andrei este apreciat. Observație. Reținem condiția de existență — a unor per- soane care îl apreciază pe Andrei - conținută în această formă de exprimare. §23. Argumente exprimate în limbajul calculului predicatelor Continuăm să transcriem în acest nou limbaj, judecăți și raționamente din limbajul natural. 1D. Unii (oameni) sunt apreciați. Unii sunt capabili. Deci: unii sunt apreciați și capabili. Notând: Ax : x este apreciat Cx : x este capabil obținem, pe baza calculului propozițional: Ax a Cx : x este apreciat și (x este) capabil. Astfel, transcrierea simbolică a argumentului alcătuit din cele trei afirmații este 3x Ax, 3x Cx 3x (Ax a Cx). 2D. Observație (universul sau domeniul discursului). Toți cuantificatorii (V și 3) ce apar într-o expresie simbolică, într-un D. Idei introductive 55 argument, sau chiar într-un șir de argumente corelate între ele, se referă întotdeauna la o aceeași colecție de indivizi (persoane, obiecte etc.) precizată în fiecare caz în parte. Ea poartă numele de domeniu sau univers al discursului. 3D. O problemă importantă legată de transcrierea diverselor argumente este aceea a exprimării în limbaj simbolic a celor patru tipuri de propoziții din logica clasică: A: toți P sunt R (universal afirmativă); I: unii P sunt R (particular afirmativă); E: nici un P nu este R (universal negativă); O: unii P nu sunt R (particular negativă)1. Vom face această transcriere ținând seama că P și R sunt predicate cu un singur subiect logic Px : x este P, Rx : x este R. Astfel, „toți P sunt 7?” va fi interpretată sub forma condițio- nală „pentru orice x: dacă x este P, atunci x este P”. Simbolic: A : Vx (Px => Px). Propoziția „unii P sunt P”, va fi interpretată drept „pentru unii x: x este P și x este P” și redată simbolic 1: 3x (Px a Rx). Cele două propoziții negative E și O sunt interpretate în același mod, dar schimbând predicatul Rx cu negația sa 1 Px; astfel E: Vx (Px => 1 Px) O: 3x (Px a 1 Rx) 1 A și I sunt primele două vocale din AFFIRMO, iar E și O sunt vocalele din NEGO. 56 Calculul predicatelor Rămâne să vedem mai târziu în ce măsură aceste transcrieri sunt sau nu adecvate. Revenind la exemplul de la pag. 50 să transcriem simbolic în acest mod cele două propoziții pe care le conține. Conside- rând predicatele Px: x este pește, Ax: x trăiește în apă, Rx\ x este răpitor, vom transcrie prima propoziție sub forma \Jx (Px => Axf iar pe a doua, sub forma Vx (Px a Rx => Ax). Relația de deductibilitate între cele două propoziții va fi, conform exemplului 4D. Vx (Px => Ax) P Vx (Px aRx^ Ax). E. Dezvoltarea calculului predicatelor §24. Formule cu predicate Sub acest nume includem formulele propoziționale, dar și pe cele în care pot apare două noi tipuri de variabile: variabile individuale (notate x, y, z, Xi etc.), variabile de predicat. Acestea din urmă vor fi notate cu aceleași litere ca și variabilele propoziționale (p, q, r, p} etc.) fiind însă urmate de una, două, trei etc. variabile individuale și alcătuind așa- numitele formule atomice. Iată exemple de formule atomice 72, p(x\ p(x, x), p(x, y), q(y, y) etc. E. Dezvoltarea calculului predicatelor 57 IE. Formulele cu predicate se construiesc pas cu pas, similar cu cele propoziționale (conf. 3B) în baza a două reguli inductive. Rl. Baza inducției. Formulele atomice sunt formule cu predicate. R2. Pasul inducției, a) Dacă oc și (3 sunt formule cu predicate, atunci ~! oc, oc a P, oc v p, oc => P, oc <=> P sunt formule cu predicate; b) Dacă x este o variabilă individuală1 2 și oc este o formulă cu predicate, atunci Vx oc și 3x oc sunt formule cu predicate. 2E. Convenția 4B cu privire la paranteze rămâne valabilă fiind completată cu o clauză prin care cuantificatorii V și 3 au aceeași prioritate ca și Spre exemplu formula 3x p(x) a q(x) va însemna (3x p(x)) a q(x) [și nu 3x (p(x) /\ #(x))]. 3E. Apariții libere și legate ale unei variabile individuale. Formula oc din R2b se numește domeniul cuantificatorului Vx, respectiv 3x, și fiecare dintre aparițiile lui x în oc se numește legata. 1 x poate fi oricare din variabilele x, y, z etc. 2 în terminologia generală a calculului, variabila este un simbol ce poate fi înlocuit cu valori dintr-o mulțime dată de valori. Este ceea ce corespunde aici noțiunii de variabilă liberă. Dar în expresii ca rt=l da valori, doarece expresiile desemnează valori fixate. Ele se numesc variabile legate sau aparente. — sau j^sinxdx , variabilelor n și x nu li se pot 58 Calculul predicatelor Orice apariție a unei variabile care nu este legată se numește apariție liberă. Exemplu. apariții legate 3x p(x) /\ Vy (p(y) a #(x, y)) apariție liberă Fiecare apariție legată a unei variabile, se leagă de un anu- mit cuantificator. Astfel, în formula din exemplu, prima apari- ție legată (a lui x) se leagă de primul cuantificator, iar următoa- rele două apariții legate (ale iui y) se leagă de al doilea cuantificator. §25. Validitate în calculul predicatelor Interpretarea unei formule cu predicate. Limbajul calculului cu predicate extinde pe cel prepozițio- nal, iar validitatea formulelor cu predicate extinde validitatea formulelor propoziționale. Formulele propoziționale sunt alcătuite din variabile propo- ziționale și operatori logici. O variabilă propozițională poate fi interpretată ca propoziție logică adevărată sau falsă. Interpre- tând astfel toate variabilele formulei propoziționale și utilizând tabelele de adevăr ale operatorilor logici putem determina va- loarea de adevăr a formulei pentru fiecare asemenea interpre- tare (cf. §8). Pentru a interpreta o formulă ce conține variabile indivi- duale și de predicat, pornim de la o mulțime nevidă U numită univers al discursului (cf. 2D). 4E. Exemplu. oc(x, y): p(x) v (q (x, y) => p(x)) Consider U alcătuit din două elemente (le notăm 1 și 2). în acest U variabila de predicat p(x) poate avea 22 = 4 interpretări: E. Dezvoltarea calculului predicatelor 59 X I II iii IV 1 A A F F 2 A E A F TAB p(x) iar variabila de predicat q(x, y) poate avea 24 = 16 interpretări y) T X y I 11 III IV V VI VII VIII IX X XI XII XIII XIV XV XVI 1 1 A A A A F A A A F F F A F F F F 1 2 A A A F A A F F A A F F A F F F 2 1 A A F A A F A F F 0 A F F A F F 2 2 A F A A A F F A A F A F F F A F TAB q(x, v) Fixând interpretări pentru variabilele libere x, y cât și pentru variabilele de predicat p(x) și q(x, y) vom putea determina, utilizând tabelele TAB => și TABv, valoarea de adevăr a formulei date la fel ca în calculul propozițional. De pildă, pentru x = 2 și y = 1, p(x) având interpretarea II, iar q(x, y) interpretarea X, găsim în tabele că p(2) este F și q(2, 1) este A. Așadar, formula p(x) v (q(x, v) => /?(*)) devine F v A, adică A. Formula dată este validă în U sa\±2-validă}, dacă în fiecare dintre cele 256 astfel de interpretări ea capătă valoarea^. 5E. Observație. întrucât nu conține cuantificatori și variabile legate, validitatea (sau nevaliditatea) acestei formule poate fi 1 Natura elementelor lui U nu va juca nici un rol în cele ce urmează. Ceea ce va conta este doar numărul acestor elemente. 60 Calculul predicatelor verificată mult mai simplu: pe baza calculului propozițional. Anume, tratând fiecare formulă atomică distinctă ca o variabilă propozițională distinctă și alcătuind o tabelă corespunzătoare de adevăr. în cazul de față ea este /?(x) y) 7(x, y) => !/?(*) X*) v (q(x, y) = * 1X*)) A A F A A F A A F A A A F F A A TAB oc(x, y) și ne arată, prin numai două coloane de calcul, că oricum am alege valorile x, y în U și valorile corespunzătoare de adevăr pentru p(x) și q(x, y), formula este adevărată. Și aceasta nu numai când U are două elemente, ci un număr oricât de mare (chiar infinit !) de elemente. Este ceea ce, în calculul cu predicate, vom numi formulă validă în orice univers (al discursului); într-o expresie - for- mulă universal validă. Nu la fel stau lucrurile cu o formulă care conține cuanti- ficatori. Căci pentru determinarea valorii sale de adevăr trebuie să ținem seama de interpretarea acestor cuantificatori. 6E. Exemplu. \/x p(x) => p(y) Astfel, de pildă, dacă U = {1, 2}, iar predicatul p(x) capătă interpretarea I din TAB p(x), formula Vxp(x) va fi A [deoarece atâtt?(1) cât șip(2) sunt A]. Pentru determinarea valorii de adevăr a formulei p(y) fixăm o interpretare a variabilei individuale^ în U, de exemplu^ = 1. întrucât /?(!) este A în interpretarea aleasă formula din exemplu este A => A deci A. Pentru a constata însă că formula din 6E este universal validă vom pleca de la un univers nevid U având un număr finit sau nu de elemente. Nu mai putem tabela, ca mai sus, E. Dezvoltarea calculului predicatelor 61 interpretările predicatului p(x). Nici nu ne-ar fi de folos. Vom împărți aceste interpretări în două categorii: a) cele în care formula \/x p(x) este adevărată (cu alte cuvinte, în care p(x) este adevărat oricare ar fi x în U) și b) cele în care formula Vx p(x) este falsă. în prima situație, oricum am interpreta variabila individuală y în U, p(y) este adevărat, deci formula 6E este adevărată. în cazul b) formula 6E poate fi F => A sau F => F, după cum este interpretat y în L7; dar în ambele cazuri 6E este, conform TAB=>, adevărată. 7E. Exemplu. p(y) => 3x p(x) De data aceasta interpretările lui p(x) în diversele universuri nevide U se vor împărți în a) cele pentru care formula 3x p(x) este A și b) cele pentru care 3x p(x) este F. Lăsăm cititorului plăcerea de a descifra, în fiecare dintre cele două cazuri, motivul pentru care formula 7E este adevărată. Marcăm validitatea universală a unei formule cu predicate, așezând în fața ei, ca și în calculul propozițional, semnul |= . Astfel, din cele discutate până acum v ( 1/>(%)) |= Vxp(x)=t>p(y) >Xy) => Bxp(x) 8E. Căutarea unui contraexemplu pentru o formulă cu predicate. Un astfel de contraexemplu este alcătuit dintr-un univers nevid pe care sunt definite interpretări pentru fiecare din variabilele (libere și de predicat) ce apar în formula respec- tivă. Condiția este ca în aceste interpretări formula să capete valoarea de adevăr F. Când un astfel de contraexemplu există formula este nevalidă. 62 Calculul predicatelor Vom căuta în continuare un conlraexemplu pentru formula a: 3.x p(x) a 3.x q(x) => 3x (/?(x) a , interpretările celor două variabile de predicatp(x) și g(x) trebuie alese astfel încât a) 3x p(x) a 3x t/(x) să fie A, b) 3x (p(x) a r/(x)) să fie F. Conform TABa prima condiție se poate reformula astfel az) 3x p(x) să fie A și 3x q(x) să fie A. Fie U universul în care considerăm aceste interpretări. Conform condiției az există în U elementele i și j astfel încât /?(/) și 1. E. Dezvoltarea calculului predicatelor 63 < 10E. Definiție. O formulă cu predicate a conținând varia- bilele propoziționale distincte variabilele de predicat distincte q^ ,;qm] și variabilele individuale libere xn este: (universal) validă dacă pentru orice univers nevid U, orice valori de adevăr acordate variabilelor p\..... pk și orice interpretări în V ale variabilelor de predicat .... qm șî ale variabilelor sale libere xb •••> xn. capătă valoarea de adevăr A Notație 11E* O formulă cu predicate a cărei negație este (universal) validă se numește contradictorie sau inconsistentă. Exemplu. Bx (p(x) a "| ;?(x)) O formulă cu predicate care nu este nici validă, nici inconsistentă se numește contingență Acesta este cazul formulei a din 8E. : . 12E. Pentru mei o formulă cu predicate nu au loc simultan |= a și pa. Fixând valorile de adevăr pentru p\. ....p^ un univers nevid U și interpretări în U pentru q}. qm, și X], xn. conf. 10E, a și a trebuie să capete aceeași valoare de adevăr: A. Ceea ce contrazice TAB 1. §26. Substitufii în calculul predicatelor Ca și în calculul propozițional suntem în căutarea acelor operații prin care din formule (universal) valide să obținem alte 1 Fiecare dintre aceste variabile de predicat poate fi urmată de un număr oarecare de variabile individuale. 64 Calculul predicatelor formule de același tip. Printre acestea se află substituțiile variabilelor ce apar în formule. a) Substituția variabilelor propoziționale se face în modul descris în §9a, cu păstrarea proprietății de validitate. b) Substituția variabilelor individuale libere și a celor de predicat este permisă numai în anumite condiții pe care le vom preciza în continuare. Pentru a face înțeleasă „mecanica” unei asemenea substitu- ții plecăm de la un 13E. Exemplu. în formula validă 6E \/xp(x)=$p(y) substituim formula atomică p(x\ pe rând, cu fiecare dintre formulele a) p(x, x) b) Bz p(x, z) c) By p(x, y) și obținem următoarele rezultate corespunzătoare: az) Vx p(x, x) => p(y, y); bz) Vx 3z p(x, z) => 3z p(y, z); cz) Vx 3yp(x, y) => 3yp(y, y). Dar în timp ce formulele az și bz sunt, ca și formula dată, valide, pentru formula cz există următorul contraexemplu: în universul U = {1, 2} pentru variabila de predicat p(x, y) se definește următoarea interpretare X y p(x, y) 1 i F 1 2 A 2 1 A 2 2 F în această interpretare formula Vx 3y p(x, y) capătă valoarea A, iar formula 3y p(y, — valoarea F (de ce?). Conform TAB=>, formula cz va fi falsă. E. Dezvoltarea calculului predicatelor 65 Cauza alterării validității formulei 6E prin substituția c se datorează unui viciu de formă. Anume, datorită coincidenței de notație (y) între variabila liberă din 6E și variabila legată din formula c, în urma substituției, variabila liberă y din 6E devine variabilă legată în c’1. Pentru evitarea unor astfel de situații facem următoarele precizări: 14E. Variabila y este substituibilă variabilei x în formula P(x) dacă nici o parte a lui p(x) de forma Vy y sau 3y y nu conține apariții libere ale lui x Spre exemplu y este substituibil lui x în Bz p(x, z), dar nu este substituibil lui x în 3y p(x, y). 15E, Formula P(x) este substituibilă formulei atomice p(x) în a dacă la fiecare apariție cap(y)2 a lui p(x) în a, variabila v este substituibilă variabilei x în P(x). De pildă, aparițiile lui p(x) în formula 6E fiind p(x) și p(y), 3zp(x, z) este substituibilă lui p(x) în această formulă, deoarece x, și respectivy sunt substituibile lui x în Bzp(x, z). Dar Byp(x, y) nu este substituibilă lui p(x) în 6E, deoarecey nu este substituibil lui x în 3yp(x, y). In general: 16E* Formula P(xh xn) este substituibilă formulei atomice p(x^ xn) în a dacă la fiecare apariție cap(Vb —, v„)2 a lui p(x^.. , xn) în a, variabilele vn sunt substituibile respectiv variabilelor xn în P(x15x/7). Fenomenul nu se produce în cazul b când variabila legată fiind notată diferit (s), variabila liberă y din 6E rămâne și după substituție, liberă. “ v, v„ desemnează oricare dintre variabilele individuale x, v, z, a'i etc. 66 Calculul predicatelor Cu aceste precizări au loc următoarele extensii ale pro- prietății 9B la calculul predicatelor Ca aplicație considerăm o formulă cu predicate P(x) și o variabilă individuală y substituibilă lui x în (3(x); notez P(y) rezultatul acestei substituții. în baza proprietății 17Eb, din |= Vx p(x) =J> p(y) și p(y) 3x p(x) rezultă 18E. |= Vx P(x) => PO) și |= P(y) => Bx P(x). §27. Echivalența formulelor cu predicate La fel ca și formulele prepoziționale, formulele cu predicate a și P se numesc echivalente dacă (= a <=> p. Utilizăm aceeași notație ca și în calculul propozițional a ~ p. 1 Vezi nota 2 de la pag. 65. E. Dezvoltarea calculului predicatelor 67 In virtutea definiției 10E a validității (universale a) formu- lelor cu predicate și a tabelei TAB<=> rezultă următoarea ' orice''dhiye:^ individuale libere și depredicat ce?ăparîh7^i> yalbăfe Exemplu (formule congruente). Două formule cu predicate sunt congruente dacă diferă numai prin notația variabilelor legate. Astfel Vzpix, z) și Vvpix, y) sunt congruente. Tot congruente sunt și formulele 3xp(x) a Vy ipiy) v q(x, y)) și By p(y) a Vy ipiy) v q(x, y)), dar nici una nu este congruentă cu formula Bxpix) a Vy ipiy) v qiy, y)). Pentru a pune în evidență congruența sau incongruența dintre aceste formule marcăm doar pozițiile variabilelor legate precum și relația lor cu cuantificatorii care le leagă. Astfel 3 țP(~) * V - (/?(ț) v q(x, -)) este schema comună primelor două formule, iar 3 -p(~) A V - (p(-) v q(—, -)) I---1 I_________I_____L_J este schema celei de a treia. Formulele congruente au așadar aceeași schemă. în virtutea proprietății 19E: 68 Calculul predicatelor 20E. Dacă a și (3 sunt congruente, atunci a~P Proprietatea 14B se extinde pentru formulele cu predicate astfel 21E. Proprietatea de înlocuire a expresiilor echivalente Fie ya o formulă cu predicate în care apare, ca parte a sa1, formula a. Notăm yp formula obținută prm înlocuirea lut a — în una sau mai multe dintre aparițiile sale — cu formula |3 în aceste condiții, dacă a ~ P rezultă ya ~ yp. La pagina 95 am dat o listă cu 23 de echivalențe ale unor formule cu predicate, notate E2s, E5q. Aplicație', forma prenexă a unei formule cu predicate. 22E. Proprietate. Pentru fiecare formulă cu predicate y există formula ypr astfel încât toți cuantificatom ce apar în ypr să se afle în fața tuturor celor cinci operatori logici prepozițio- nali ce apar în y. în plus Y~Ypr Această proprietate este dedusă în urma aplicării unui proces prin care cuantificatorii ce apar în y sunt, treptat, trecuți în fața celor cinci operatori prepoziționali. Iată cum decurge el în cazul formulei y: 3x p(x) => 13x q(x, y). 1. Pe baza echivalenței E33 rezultă: "13x q(x, y>) ~ Vx 1 q(x, y), 1 Formula a este alcătuită din simboluri consecutive ale formulei ya. 69 E. Dezvoltarea calculului predicatelor apoi a proprietății 2IE: \ 2. Conform E30: Vx 1 q(x, y) ~ Vz 1 ^z’ apoi, conform proprietății 2IE: Y ~ 3x p(x) => Vz 1 <&’ 3. Conform E43: Y - Vx (p(x) => vzl^^ 4. Conform E40: p(x) => Vz ~l q(z, j) ~ X/5 (p(P> apoi, conform proprietății 2IE: Y ~ Vx (p(x) => Vz 1 q(z, ^)) ~ Vx Vz (p(%) =* y^' Așadar, am găsit că una dintre formele prenex Yp> mulei Y este formula Vx Vz (p(x) => 17(2, y)). Observații. Ea nu este unică. Spre exemplu - confoim E49 - o altă formă prenexă pentru Y este Vz Vx (/?(x) => 1 q(.z, y)). §28. Dualizarea formulelor cu predicate Simetria proprietăților operatorilor prepoziționali a și v este completată, în calculul predicatelor, de o simetrie a pro- prietăților cuantificatorilor V și 3. între a și V, respectiv v și 3 există, de altfel, o legătură strânsă. Astfel, afirmația „oricare x are proprietatea a”, simbolizată Vx a(x) 70 Calculul predicatelor capătă, în universul cu n elemente U = {1, 2, n}, forma conjuncției logice oc( 1) a oc(2) a ... aoc (t?)1 . Afirmația „unii x au proprietatea oc”, simbolizată 3x oc(x) capătă, în același univers, forma disjuncției oc( 1) v oc(2) v ... v oc(n). Pe baza legilor De Morgan, pe de o parte l(oc(l) a oc(2) a...a oc(??)) ~ |oc(l)v ~|oc(2) v...v ~|oc(n), iar pe de altă parte ~l(oc(l) V oc(2) v...v oc(/?)) - loc(l) a ~|oc(2) a...a loc(n). Ceea ce corespunde echivalențelor: E32.1 Vx oc(x) - 3x I oc(x) E33.13x oc(x) - Vx 1 oc(x) Proprietatea 16B se extinde la cazul unei formule cu predicate, a, astfel 23E. Proprietate. Presupunem că a conține doar formule atomice simple sau negate, operatorii a și v precum și cpâțitj- fîcaton. < oc se obține din a negând formulele atomice simple^ suprimând negația celor > negate, înlocuind a cu y, v ’CU\a. precum și V cu 3, 3 cu V. ‘ Atunci la~a« Exemplu. oc: Vx By ( "Ip(y) a 3z q(x, z)). 1 Parantezele, necesare într-o conjuncție sau disjuncție cu mai mult de doi termeni, pot fi omise în baza legilor asociativității (E22 Și E??)- E. Dezvoltarea calculului predicatelor 71 Utilizând echivalențele propoziționale E32 și £33, obținem pe rând la ~ Bx 1 By (1 p(y) a Hzq(x, z)) ~ Bx Vy 1 (.. .) ~ e32 e„ e„ ~3xVy(ll/>(y)vl3z^(x, z)) ~ Hx X/y (p(y) v \/z 1 q(x, z)). dn,e33 Formula obținută în finalul acestor transformări este a. , X:24E. a este o formulă cu predicate având structura descrisă |:ȘÎ5Șe-Kuinește duala lui a și se notează a7, formula obținută JfiloSyjnd în ar a cu v, v cu a, V cu 3 și 3 cu V Enunțăm proprietatea care extinde 17B la formulele cu predicate. Proprietate a și p sunt formule cu predicate având Structura descrisă în 23 E. |||||||||^^ Reciproc* dacă a7 ~ p7, atunci a ~ p. Exemplu. Echivalența E46. Vx oc(x) a Vx P(x) ~ Vx (ot(x) a P(x)) se transformă prin dualizare în echivalența E47. 3x oc(x) v 3x P(x) ~ 3x (ot(x) v P(x)). §29. Reguli de cuantificare Putem obține, plecând de la formule valide, alte formule valide pe o cale ce nu are corespondent în calculul propozi- țional: regulile de cuantificare. Menționăm două astfel de reguli. 72 Calculul predicatelor 26E. Regula V ași P(x) sunt formule cu predicate astfel încât variabila x nu apare liberă în a. Atunci, din |=a=>£(x) rezultă " [= (x => Vx P(a). 27E. Regula 3. a(x) și £ sunt formule cu predicate astfel încât variabila x nu apare liberă în £ Atunci, din a(x) => £ , rezultă (=3x oc(x) => P- < : Verificăm regula V. Presupunem că (1) |=oc=>p(x) Fixăm un univers nevid U și alegem interpretări pentru fiecare dintre variabilele (propoziționale, de predicat și indivi- duale libere) ce apar în formulele oc și Vx P(x). întrucât x nu apare liberă în oc, prin ipoteză, dar nici în Vx P(x), conform 3E, acestei variabile nu i-a fost acordată, prin alegerile menționate, nici o interpretare. După valoarea de adevăr pe care o ia formula oc — în interpretările alese - distingem două cazuri: a) oc ia valoarea F; b) oc ia valoarea A. în primul caz formula oc => Vx P(x) este, conform TAB=>, adevărată. în cazul b, alegând ca interpretare pentru variabila liberă x, din P(x), pe rând fiecare element i din U, valoarea de adevăr a lui oc nu se modifică (deoarece oc nu conține această variabilă liberă). întrucât oc => P(x) este validă, (conform (1)), oc => P(z) este adevărată. oc fiind adevărată, P(z) va fi adevărată (TAB=>). F. Axiomatizarea calculului predicatelor 73 Așadar, în acest caz, \/x P(x) va căpăta — în interpretările alese - valoarea A; la fel ca și formula a => \/x P(x) Verificarea regulii 3 se face utilizând aceleași principii. Presupunem (2) și alegem universul nevid U și interpretări ale variabilelor pre- poziționale, de predicat și individuale libere ce apar în formu- lele 3x oc(x) și p. Variabilei individuale x, care nu apare liberă în nici una dintre cele două formule, nu i se fixează acum nici o interpretare. a) Când P este, în aceste interpretări, A, formula Bx oc(x) => P va fi A. b) Când P este F, alegând ca interpretare pentru x, pe rând, fiecare element i din U, conform (2) și TAB=>, găsim pentru oc(z) valoarea F. Așadar, în acest caz, 3x oc(x) va lua - în interpretările alese în U- valoarea F, iar formula Bx oc(x) =^> p va fi devărată. Observație. Există, pe lângă acestea două, și alte reguli de cuantificare a variabilelor libere într-o formulă validă, cu păs- trarea validității. Dar vom vedea în capitolul următor că ele pot fi obținute, pe cale deductivă, din cele de mai sus. F. Axiomatizarea calculului predicatelor §30. Axiome și reguli deductive Calculul predicatelor este o dezvoltare a calculului prepozițional. a) Axiome. Cele 13 axiome ale calculului prepozițional (§14a) sunt axiome și pentru calculul predicatelor. Lor li se adaugă încă două axiome: 74 Calculul predicatelor b) Reguli deductive. bl) Detașarea numită și =>-eliminare este regula prin care, din formulele cu predicate oc și oc => P deducem formula (cu predicate) p. Ea se notează, pe scurt, D. b2) Regula substituției, notată 5, se referă la cele 13 axiome propoziționale și respectiv la cele două noi axiome: ax \/ și ax 3. Pe baza ei, din axiomele ax la, .... ax 9b deducem rezultatul substituției1 uneia sau mai multor variabile propoziționale prin formule cu predicate. Totodată regula 5 ne permite deducerea din ax V a formulelor Vx P(x) => P(y), și din ax 3 a formulelor P(y) => Bx P(x), în condițiile în care P(x) este orice formulă cu predicate, y este o variabilă individuală substituibilă lui x în p(x)2, iar p(y) este rezultatul acestei substituții. b3) Regulile de cuantificare Regula V ne permite să deducem din orice formulă cu pre- dicate a => P(x), unde variabila x nu apare liberă în a, formula a => Vx P(x). Regula 3 ne permite să deducem din formula cu predicate 1 Substituția trebuie să se facă, conform 10B, uniform sau peste tot unde apar acele variabile propoziționale. 2Cf. 14E. F. Axiomatizarea calculului predicatelor 75 a(x) => p, unde variabila x nu apare liberă în Ș, formula 3x cc(x) => Ș. §31. Demonstrație și deducție în calculul predicatelor alcătuit g|^gg|intr^eg5;^ tSOTftrC^^nia^-B:;^./?' •'.- Â': b) iie rezultatu( aplicării regulii £> unei perechi de formule ^.ffî^Hdșre-pi^^if' 3 3;' 7 3 3 33 3<țbrjWulâ ifinaîă a- unei demonstrații se lîtințpștbpeprentății^. 2F. Exemplu. Următoarele 7 formule cu predicate alcătuiesc o demonstrație. Menționăm, în dreptul fiecăreia, motivul includerii sale în șir (conform definiției anterioare). (1) p(y) =* 3* p(x) ax 3 (2) (p(y) => 3x p(x)) => (Vx p(x) => (p(y) => Sx p(x))) ax 1 a1 2 (3) Vx p(x) => (p(y) => 3x /?(x)) 1, 2 D (4) Vx p(x) => p(y) ax V (5) (Vx/Xx) =*p(yj) => ((VxP(x) => (p(y) => 3xX*))) => => (Vx p(x) => 3x />(x)))) (p(y) => Hx p(x))) => (Vx p(x) => 3x p(x)) 4,5 D (7) Vx p(x) => 3x/j(x) 3,6 D 3F. Definiție Se numește deducție în calculul cu predicate, din formulele (cu predicate) ab ..., am — numite ipoteze — un șir finit de formule cu predicate, fiecare dintre ele reprezentând a) fie una dintre cele 15 axiome sau rezultatul unei substituții într-o axiomă, b) fie o ipoteză, c) fie rezultatul aplicăm regulii D unei perechi de formule anterioare ei în șir; d) fie rezultatul aplicăm regulii V sau regulii 3 unei formule anterioare ei în șir. ‘ Formula finală a unei deducții — p — se numește concluzia deducției, iar relația între ipoteze și concluzia deducției se • I" P 4F. Exemplu. Următorul șir de formule este o deducție a formulei p => Vx q(y)). (1) Vy q(y) => q(x) axV (2) \fy q(y) => Vx q(x) 1, reg V (3) Vy (p => q(y)) ipoteză (4) Vy (p => q(y)) ^(p=> q(y)) ax V (5) p=>?(y) 3,4 d (6}p=*Vyq(y) 5, reg V (7) (Vy q(y) => Vx q(x)~) => (p (Vy q(y) => Vx q(x)) ax la (8) p =$ (Vy Vx q(x)) 2,7 D (9) (p => Vj/ q(y~)) =>((p=> (Vy q{y) => Vx (/?=> Vx (Vy 7(y) => Vx 7(x))) => (p => Vx r/(x)) 6, 9 D (11) p => Vx ^(x) 8, 10 D Așadar, vom putea scrie: Vy O => <7O)) [p => Vx 7(x). Relația |- din definiția 3F se numește relație de deductibi- litate în calculul cu predicate. §32. Proprietăți ale relației de deductibilitate Deși notate la fel, relația de deductibilitate din calculul prepozițional (cf. 3C) și cea din calculul cu predicate sunt diferite. O parte dintre proprietățile celei dintâi rămân adevă- rate și pentru cea de-a doua, iar altele se modifică în sens restrictiv. Vom observa astfel că dacă 0C], ..., a,„, P sunt formule cu predicate pentru care ab a„, (- 3 are loc în calculul propozițional (adică în virtutea definiției 3C), atunci ea are loc și în calculul cu predicate. In schimb proprietatea: dacă oc P, atunci oc => P, valabilă pentru deductibilitatea în calcul propozițional (cf. 9C), nu mai este valabilă și în calculul predicatelor, lată în acest sens un Exemplu. Incluzând în deducția anterioară formula 5 ca ipo- teză, putem renunța la formulele 3 și 4, pe care se bazează de- ducția lui 5. Astfel încât cele 9 formule rămase constituie o deducție în calculul predicatelor. In virtutea acestei deducții are loc relația 78 Calcului predicatelor Dar formula (!)(/?=> ?O)) => (p => Vx q(x)) este nevalidă. întrucât - așa cum vom arăta (§33) - orice teoremă din calculul predicatelor este o formulă validă, rezultă că relația F (p => q (y)) => (p => Vx #(x)) nu are loc. Nevaliditatea formulei (1) se poate proba astfel: alegem pentru p valoarea de adevăr A, iar în universul t/={l,2} predicatul q(x) să aibă interpretarea X q(y) este cuantificată universal (în baza regulii V) pe parcursul deducției. Când însă aceeași formulă apare nu ca ipoteză, ci dedusă din ipoteză (în deducția din exemplul 4F), deci regula de cuantificare nu se mai aplică unei variabile libere dintr-o ipoteză, atunci toate proprietățile 5C-10C rămân adevărate pentru această nouă relație de deductibilitate. 5F. Convenție în cele ce urmează vom consideră ea relație de deductibilitate în calculul predicatelor, relația (noțataâ^ existentă între formulele cu predicate ai, , și formulă cu predicate (3 atunci când există o deducție a lui (3 din ipotezele: , am (conf. 3F) în care regulile de cuantificare V;-și?3..Snf se aplică unor variabile libere din formulele-ipotezei F. Axiomatizarea calculului predicatelor 79 §33. Consistența și completitudine Axiomele calculului predicatelor sunt formule valide (pri- mele 13 sunt propozițional valide, iar ax V și ax 3 sunt - conf. 6E și 7E - universal valide). Orice teoremă a calculului predicatelor se obține din (unele dintre) aceste axiome prin mai multe transformări succesive constituind demonstrația sa. în baza definiției 1F, aceste trans- formări pot fi a) substituții (cf. regulii deductive S), b) detașări (cf. regulii deductive D), c) aplicări ale regulilor V sau 3. Fiecare dintre aceste transformări păstrează proprietatea de validitate (universală) pe care o au formulele de la care pleacă: a) Substituțiile făcute în primele 13 axiome conduc la for- mule universal valide. Ne oprim un moment asupra acestei proprietăți. Când într-o formulă propozițional validă substituim o varia- bilă propozițională printr-o formulă prepozițională, validitatea formulei astfel obținute se bazează pe faptul că tabela sa de adevăr este dedusă din tabela de adevăr a formulei în care s-a făcut substituția (§ 9a). Același fapt are loc și atunci când variabila propozițională este substituită printr-o formulă cu predicate. Exemplu. Substituind în formula propozițional validă (1) pv~]p variabila propoziționalăp cu formula cu predicate 3x (p(x) a q(x, y)) obținem (2) 3* (/?(*) a q(x, y)) v ~| 3x (/?(x) a q(x, y)) Validitatea universală a formulei (2) decurge din validitatea propozițională a formulei (1) astfel: în orice univers (nevid) U și orice interpretare în U a variabilelor de predicat p(x), q(x, y) și a variabilei (individuale) 80 Calculul predicatelor libere^, formula E.v (p(x) a q{x, _y)) ia valoarea A sau F; odată determinată, această valoare de adevăr este introdusă în tabela de adevăr a formulei (1); ceea ce ne conduce - conform TABy? v ~]p - la valoarea A (pentru (2)). Substituțiile făcute în ax V și ax 3 ne conduc la formule de tipul Vx P(x) => P(y), respectiv P(y) => 3x P(x), care sunt universal valide (18E). b) Detașarea: dacă formulele cu predicate oc și oc => 3 sunt universal valide, atunci formula 3 este și ea universal validă. Acest fapt decurge direct din TAB=>: când într-o anumită interpretare a variabilelor ce apar în oc și oc => 3 (deci și în 3), acestea iau valoarea A, 3 capătă aceeași valoare de adevăr. c) Conform 26E și 27E, dacă premiza regulii (V sau 3) este universal validă, atunci concluzia sa are aceeași proprietate. In final așadar 6F<\ Pentru orice formulă cu predicate oc, dacă |- a (i.e. oc este o teoremă a calculului predicatelor), atunci a (i. e. a este universal validă). Deoarece, cf. 12E, pentru nici o formulă cu predicate oc: |= oc și |= 1 oc, rezultă: Consistență (sau necontradicția) calculului predicatelor Pentru orice formulă cu predicate oc, afimatiile 1® IO IO W® •nîifpot'fî simultan adevărate ' , F. Axiomatizarea calculului predicatelor 81 Reciproca proprietății 6F este un rezultat fundamental al logicii predicatelor1. 8F. Completitudinea calculului predicatelor Pentru orice formulă cu predicate a, dacă |= a, atunci Demonstrația completitudinii calculului predicatelor nu are caracterul elementar al celei din calculul propozițional (§19) și de aceea nu o expunem aici. Reîntorcându-ne la rezultatul în sine, 6F și 7F stabilesc echivalența, pentru orice formulă cu predicate oc, a condițiilor [= oc și |- oc. Când oc este o formulă prepozițională, prima condiție poate fi verificată printr-o metodă care, chiar dacă este laborioasă, con- duce, după un număr finit de operații2 la răspunsul definitiv. Când însă oc este o formulă cu predicate, verificarea condiției boc presupune determinarea valorii de adevăr a lui oc într-o infini- tate de interpretări posibile ale variabilelor, libere și de predicat, ce le conține. Aceasta deoarece interpretările trebuie făcute în fiecare univers nevid U, Verificarea nu se încheie practic niciodată, astfel încât noi nu ne aflăm în situația de a putea da un răspuns definitiv chestiunii propuse. Problema în cauză face parte din clasa problemelor nedecidabile3. 1 Demonstrat de logicianul austriac K. Gbdel în 1930 („Die Vollstăndigkeit der Axiome des logischen Funktionenkalkuls'? în Monatschefte fur Mathematik und Physik, voi. 37, pp. 349-360). 2 Este vorba de alcătuirea unei tabele de adevăr. 3 Problema nu este nedecidabilă în cazul fiecărei formule cu predicate. Am determinat, de altfel, pe parcursul acestui capitol, validitatea sau nevali- ditatea mai multor formule cu predicate. Ea este nedecidabilă în sensul impo- sibilității găsirii unui mecanism (algoritm) prin care, pentru fiecare formulă cu predicate oc să putem - aplicând acest algoritm - să decidem, după un număr cunoscut de operații, dacă oc este universal validă sau nu. 82 Calculul predicatelor Ținând seama de aceste dificultăți, în loc de a verifica vali- ditatea (universală a) unei formule cu predicate, este de preferat a încerca să descoperim o demonstrație a formulei respective. §34. Reguli deductive derivate Sistematizarea și simplificarea demonstrațiilor în calculul predicatelor se face, ca și în cel propozițional, prin înlocuirea axiomelor cu reguli deductive (derivate din acestea). Alături de cele 13 reguli de introducere și eliminare a fiecăruia dintre cei 5 operatori propoziționali, mai apar astfel 4 reguli de introducere și eliminare a celor doi cuantificatori. Astfel r |- oc(x) r(- Vxoc(x) unde r reprezintă o listă, posibil vidă, de formule cu predicate în care variabila x nu apare lieră. Vx a(x) [- cx(v) unde v desemnează o variabilă individuală substituibilă lui x în oc(x) (cf. 14E), iar cx(v) rezultatul acestei substituții. oc(v) |- 3x a(x) unde v are aceeași semnificație ca în regula de V-eliminare. ............... r q(x)|- p r, 3xa(x)|-p unde (3 este o formulă cu predicate ce nu conține variabila liberă x, iar r are aceeași semnificație ca în regula de V-introducere. F. Axiomatizarea calculului predicatelor 83 Ele sunt proprietăți ale relației de deductibilitate din cal- culul predicatelor și se pot demonstra ca atare. Aceste reguli se utilizează în demonstrații, împreună cu celelalte 13 din §18 și cu proprietățile 5C-10C (§16). Exemplu. Reluăm relația de deductibilitate 4D (pag. 56) [în care constantele de predicate Px, Rx și Ax au fost înlocuite cu variabilele de predicatep(x\ r(x) și a(x)\\ Vx (p(x) => ct(x)') |- Va (p(x) a r(x) a(x)) (1) Vx (p(x) =: >«(*)) |-p(x) = * a(x) (2) P(x) a r(x) |-/?(x) (3) p(x),p(x) = => tf(x) |- a(x) (4) Vx (p(x) => a(x)), p(x) a r(x) [- a(x) (5) Vx (p(x) => a(x)) |-p(x) a r(x) => a(x) \/x (p\x) => ci(xȘ) V-elimin. A-elimin. =>-elimin. 1,2,3 C1 4, =>-introd. V-introd. Această deducție reprezintă justificarea formală a deducției din §20, făcută în temeiul legilor logice ale calculului cu predicate. Exemplu. Vx (p(x) => q(x)), Vx (q(x) => r(x)) |- Vx (p(x) => r(x)). Această deducție poartă, în tratatele de logică, numele de silogism în figura întâia (modul AAA). EI este alcătuit din două ipoteze (premize) universal afirmative, care se pot exprima neformal astfel: toți P sunt Q toți 0 sunt R. De aici rezultă concluzia, de asemenea universal afimativă, toți P sunt R. Să arătăm validitatea sa (universală) producând o demons- trație a relației de deductibilitate prin care se exprimă simbolic. 1 Prin C înțelegem utilizarea proprietăților 5C-10C ale relației de deductibilitate. 84 Calculul predicatelor Notăm cu r mulțimea celor două premize ale silogismului Vx (p(x) => q(x)), \/x (q(x) => r(x)). Atunci: (!) r \-p(x)=>q(x) (2) T [- r(x) (3) r,p(x) \-q(x) (4) T,Xx) |-r(x) (5) r ^jt?(x)=>r(x) r Vx (p(x) => r(x)) V - elimin, C V - elimin, C 1, => - elimin, C 2, 3, - elimin, C 4 C 5 V - introd. Exerciții 85 Exerciții (Soluții la pag. 92) 6. Cu ajutorul predicatului Axy : x este apreciat de% a operatorilor logici (propoziționali) și a cuantificatorilor, tran- scrieți simbolic fiecare dintre următoarele propoziții: a) Oricine este apreciat de cineva. b) Oricine apreciază pe cineva. c) Oricine este apreciat sau apreciază pe cineva. d) Oricine este apreciat, apreciază pe cineva. 7. Pentru fiecare variabilă de predicat q(x) se consideră formulele A\ \fx q(x\ I: 3x q(x), E: Vx 1 ^(x), O. 3x 1 q(x)x Justificați validitatea universală a următoarelor formule a)^^7? E^>0 (relații în virtutea cărora I este subalterna lui A, și O subalterna lui £). (relații în virtutea cărora A și O, respectiv E și /, se numesc contradictorii)’, (relație în virtutea căreia^ și E se numesc contrare) d) IvO (relație în virturea căreia I și O se numesc subcontrare)2. 1 Ele sunt echivalente, respectiv, cu cele patru tipuri de propoziții A, E, I, O din 3D în cazul când p(x) ia valoarea A pentru orice x (ceea ce se întâmplă, de pildă, dacă substituim p(x), cu formulapv~\p). 2 Aceste patru tipuri de relații se numesc inferențe imediate. Ele pot fi sistematizate într-o diagramă numită „pătrat logic” (Boethius, 480-524). contrare sub-contrare 86 Calculul predicatelor 8. Forma completă a celor patru tipuri de propoziții A, 7, E, O este (conform 3D) următoarea: A \ \/x (p(x) => q(x)), h 3x (p(x) a 1 q(x)\ O: 3x (p(x) a 1 g(x)), a) Justificați validitatea universală a echivalențelor lAdO și Ie di. b) Arătați nevaliditatea formulelor A dl, EdO, 1(Ja£), /vO într-un univers alcătuit dintr-un singur element £/={!}■ c) Validitatea universală a formulei 3x p(x) => (A => 7) poate fi probată cu ajutorul următorului șir de nouă relații deductive: (!) A \-p(y)dq(y) (2) p(y),p(y)dq(y) p(y) O) p(y),p(y)dq(y) (- q(y) (4) p(y\ q(y) \-p(y)^q(y) (5) p(y) a q(y) p I (6) A, p(y) |-1 (2) A, 3xp(x) 1 (8) 3x p(x) j-A => I p(x) d(A d I). Justificați-o pe fiecare dintre ele după modelul exemplelor din §34. 87 Exerciții d) Construiți un șir corespunzător de asemenea relații pentru a justifica validitatea universală a formulei e) Justificați validitatea universală a formulelor: 3xp(x)=> 1(^ și ^xp(x)=> (I v O). 88 Soluțiile exercițiilor Anexa I: SOLUȚIILE EXERCIȚIILOR 1. a) Transcris în limbaj simbolic raționamentul devine //vl/.=>/, deci L. c) Validitatea prepozițională a implicației (q v 1 r => p) a (7 a 1 p) =3 r se poate proba cu ajutorul tabelei de adevăr p r (<7 v |r=> p) a (7 a lp) => r A A A A A F F A A A F A A F F A A F A F A F F A F A A A F F A A A F F A A F F A F A F A F F A A F F A F A F F A F F F A F F F A d) Coloana formulei (7 v ”| r => p) /\ (q a 1 p), alcătuită numai din F, arată că această formulă este inconsistentă (cf.7B). Conform TAB=> ea implică orice formulă. Prin urmare, raționa- mentul - având-o ca ipoteză - este propozițional valid, indepen- dent de concluzia sa. 2. a) Dicționar I: impozitele cresc, D\ se înregistrează deficit bugetar, S: sumele alocate asistenței sociale scad. Raționamentul este alcătuit din propozițiile logice V=>D, D => S, I, deci 15. c) Formula în cauză — înlocuind / cu p, D cu q, S cu r — va fi Soluțiile exercițiilor 89 (1/? => q) a (q => r) a p => 1 r și are valoarea F când p și r sunt A. Concluzia raționamentului nu rezultă așadar din premisele sale; cel puțin nu în virtutea legilor logicii prepoziționale. 3. Raționamentul este alcătuit din propozițiile logice S^PvC, P^V, C=>D, 1Ka1Z), deci 15. Formula prepozițională corespunzătoare va fi - înlocuind 5 cu p. P cu q, C cu r, V cu s, D cu t (1) (p =$ q v r) /\ (q => 5) a (f=> Z) a Ts’ a ~]t => ~\p întrucât tabela sa de adevăr are 25 = 32 de linii (!) vom face verificarea validității prin căutarea sistematică a unui contra- exemplu (cf. 8B). Pentru ca implicația (1) să fie falsă trebuie ca (2) p=> q y r, q => 5, r => Z, ”| 5,1Z să fie A, iar ~\p să fie F. Deoarece p și 77 => 7 v r sunt A, qv r este A. Dacă q este A, întrucât q => s este A (cf. (2)), 5 este A, deci 15 este F; ceea ce contrazice (2). Dacă r este A, întrucât r => t este A (cf. (2)), Z este A, deci Z este F contrazicând (2). Așadar (1) nu poate fi falsă; ea este validă. 4. a) Transcrise în limbaj propozițional - conform dicționa- rului propus — cele trei declarații vor fi Xi:P2aM Xp.P^P., %3:1Aa(P, vP2). 90 Soluțiile exercițiilor b) Formulele prepoziționale corespunzătoare fiind ai:/22Al/>3, a2'.pi=^p3, «3:1/>3 a (p, v p2) consistența formulei ai a a2 a a3 presupune găsirea unor valori de adevăr pentru pi, p2, pi astfel încât valoarea acestei conjuncții — deci și a fiecărei formule în parte - să fie A. CC] este A atunci când p2 este A și pi este F. în acest caz , a2 este A numai dacăpt este F (de ce?). Pentru valorile găsite, a3 este 1 F a (F v A) adică A. Ceea ce probează consistența. c) Relația de deductibilitate a, |- a3 se poate obține astfel (1) (2) ^2AljP3 [pi - a -elim. P2^1p3 |- 1^3 (3) P2 |-P1 vp2 (4) 1 p3, , V p2 |- 1 p3 A (/?] V p2) v -introd. a -introd. 1,2,3,4 C ^2Al/>3 |-lp3 /\(p\ V#) Deci «i ==> a3 este validă (de ce?). Verificați, căutând contraexemple, că celelalte cinci formule a, => a7 sunt nevalide. Observație. Pentru obținerea acestor rezultate cititorul poate utiliza și tabele de adevăr. d) Dacăp\,p2,Pi sunt F, atunci ai și a3 sunt F, iar a2 este A. e) Presupunerea făcută revine, în cazul lui la implicațiile Ipi => a! și pi => l«i- în baza transpoziției și a eliminării dublei negații (DN), din prima implicație deducem conversa celei de a doua la, =>pt Soluțiile exerciț iilor 91 Deci, conform <=> -introd., rezultă echivalența: P\ <=> lab Similar, în celelalte două cazuri: £>2 <=> 1 0C2, Pi <=> "| OC3 . Construind tabela de adevăr: P\ P2 Pi lai la2 la3 A \ A A F A A A F F A F ■„A. F Aj i A F Ai F A A A F A A F F A A F F A F F F F F F A A F A F F F A F A constatăm că singura linie în care valorile primelor trei coloane coincid - respectiv — cu valorile ultimelor trei, este a treia (în chenar punctat). Vinovați vor fi, în acest caz, doarJG și X3. 5e). (1)/? ipoteză (2) ~^P ipoteză (3) p=^(]q=>p) axIaS (4) “I/? => (“Itf => "IjO OTlaS (5) (lfl=>p)=>((l?=>l/2)=>ll q) ax6 S (6) ^q=>p 1,3 jj (7) 1?=> ~\p 2,4 D (8) (~|^ =>1p)=>J1^ 5,6 D (9) 11<7 7,8 D 92 Soluțiile exercițiilor (10) "] 1 q => q ax 7 (11) <7 9,10 D 6. a) Vx By Axy b) X/y 3x Axy c) Vx (3j/ Axy v By Ayx), ceea ce - în baza echivalenței E47 - se mai poate scrie sub forma (prenexă); Vx By (Axy v Ayx) d) Vx (3y Axy => By Ayx). 7. a) A => / este teoremă a calculului predicatelor (cf. 2F); în virtutea proprietății 6F ea este universal validă. E => O se obține din formula precedentă substituind q(x) prin 1 ^(x); conform 17E, din validitatea celei dintâi rezultă și a celei de a doua. b) Aceste echivalențe sunt cazuri particulare ale echiva- lențelor E32 și E35. c) Conform b: 1E ~ I. în virtutea proprietății de înlocuire a expresiilor echivalente (2IE) rezultă (A => I) - (A => 1E) în baza echivalenței El3 vl£) și, conform Es fU v"|£)~"IU a£). Așadar (A => 7) ~ 1 (A a E) ceea ce, conf. 19E, face ca din validitatea (universală) a primei formule să rezulte și validitatea celei de a doua. d) (A => I) ~ ^13 Aplicând proprietatea de înlocuire a expresiilor echivalente și ~\A ~ O rezultă Ia v i~Ov 1. Soluțiile exercițiilor 93 în final, utilizând comutativitatea v (E7), găsim: 8. a) Conform E32: (1) 1 Vx (p(x) => q(x)) ~ 3x (p(x) a 1 I. b) Se alegep(V) fals. c) (1) V-elim; (2) 5C; (3) => -elim.; (4) A-introd.; (5) 3-introd.; (6) 1,2, 3, 4, 5 C; (7) 6, ax 3; (8) 7, 10 C; (9) 8, 9 C. d) Se înlocuiește q(x) prin 1 q(x) în relațiile de la punctul c. e) Au loc echivalențele 1 (A a E) ~ (1J v 1E) ~ (A 1E) și, conform a) 1E ~ I, E8 E13 de unde deducem: 1 (A a E) - (A => I). Deci validitatea universală a formulei 3x p(x) => "] (A a E) rezultă din validitatea universală a formulei 3x/?(x) => (A => I), conform proprietății de înlocuire a expresiilor echivalente (2 IE). Deoarece ~\A ~ O (punctul a), rezultă: (7vO)-(Zv^) ~ CU vZ) ~ (A=>I). E? E13 De unde rezultă, ca mai sus, validitatea universală a formulei: 3x p(x) => / v O. 94 Echivalențe logice Anexa II. ECHIVALENTE LOGICE oc, P, y reprezintă formule prepoziționale sau cu predicate. Ej. oc~11oc E2. a - oc a oc n E3. oc ~ oc v oc J E4. oc~("|oc=^ oc) E5. loc~(oc=^> P A 1P) E6. OC a P ~ P a oc E7. a v p ~ p v a E8. 1 (oc a P) ~ 1 oc v 1P j E9. 1 (oc v P) ~ 1 a a 1P Ejo- oc v p ~ 1 ("] a a 1P) Eu. oc a p ~ ("] a v 1P) E]2. oc => p ~ ~| p => 1 oc E]3. a=^p~1avp E14. oc=>P~”|(oca"IP) Ej5. ~| (oc => P) ~ OC A 1 P E16 OC <=> p ~ p <=> oc E|7. oc <=> p ~ (oc => P) A (P Eig. OC <=> p ~ (oc A P) v ("1 a A E19. OC <=> P ~ ~] OC <=> 1P E20. 1 (oc <=> P) ~ "|oc <=> P E2j. ~| (oc <=> p) ~ oc <=> P legea negării negației (DN) legile simplificării consequentia mirabilis reductio ad absurdum legile comutațivității legile De Morgan definiția v prin ”|, a definiția a prin ”|, v traspoziția definiția => prin ~|, v definiția => prin ~|, a negarea implicației simetria echivalenței definiția <=> prin a, => 'l P) definiția <=> prin ~|, a, v legea complementarității negarea echivalenței negarea echivalenței Echivalențe logice 95 E22- a a (p a y) ~ (a a P) a y legile asociativității E23. a v (P v y) ~ (a v P) v y ~l E24. oc => (P => y) ~ (OtA P) => y exportare E25. a a (P v y) ~ (a a P) v (a a y) “I legile distributi vității E26. a v (P a y) ~ (a v P) a (a v y) J E27. (a=> p) a a~a a p absorbția în echivalențele E2s și E29 formula a nu conține variabila liberă x E28. Vx a ~ a E29. 3x a ~ a în echivalențele E30 și E3) variabilei x în cc(x) [cf. 14E] variabila v este substituibilă E30. Vx a(x) ~ Vy a(y) E31. 3x a(x) ~ By a(y) E32. ”! Vx a(x) ~ 3x 1 oc(x) E33. 13x a(x) ~ Vx 1 a(x) E34. Vx a(x) -13x 1 a(x) E35. 3x a(x) ~ 1 Vx 1 a(x) negarea cuantificatorului V negarea cuantificatorului 3 definiția V prin 3 definiția 3 prin V în echivalențele E36-E45 formula a nu conține variabila liberă x. E36. a a Vx p(x) - Vx (a a P(x)) E37 a a Sx P(x) - 3x (a a P(x)) E3g. a v Vx P(x) ~ Vx (a v P(x)) E39. a v 3x P(x) ~ 3x (a v P(x)) E4o. a Vx P(x) - Vx (a => P(x)) 96 Echivalențe logice E41. a => 3x (3(jv) ~ 3x (oc => P(x)) E42. Vx P(x) a ~ 3x (P(x) => a) E43. 3x P(x) => OL ~ Vx (P(x) => ot) E44. OL <=> Vx P(x) ~ Vx (oc <=> P(x)) E45. ol <=^> 3x P(x) ~ 3x (a <=> P(x)) E46. Vx oc(x) a Vx P(x) ~ Vx (oc(x) a P(x)) E47. 3x cx(x) v 3x P(x) ~ 3x (oc(x) v P(x)) E48. Vx a(x) => 3x P(x) ~ 3x (oc(x) => P(x) E49. Vx \/y ol(x, y) - Vy Vx oc(x, y) E50. 3x 3y cx(x, y) - By 3x cx(x, y) Logică și metamatematică 97 Anexa III: LOGICĂ Șl METAMATEMATICĂ Orice știință sau sistem organizat de gândire își probează adevărurile prin recurs la regulile - general admise - ale deduc- ției logice. Matematica a fost prima care a utilizat în mod sistematic acest instrument („organon”) în demonstrarea teoremelor ei. Și nu întâmplător majoritatea exemplelor de demonstrație utilizate de Aristotel în scrierile lui de logică sunt exemple matematice. A trebuit să treacă peste 2000 de ani ca rolurile să se inver- seze și matematica, mai precis algebra, să devină din câmp de aplicație al logicii - instrument de investigație a sa. Cercetările făcute în acest sens de tânărul matematician englez G. Boole au condus Ia apariția unui calcul logic (cu propoziții) similar, în multe privințe, celui algebric cu numere. Următorul pas major este făcut de logicianul german G. Frege (1848-1925) care dezvoltă primul sistem cuprinzător de logică simbolică. Deși notațiile complicate pe care le utiliza i- au întârziat răspândirea, opera sa a influențat hotărâtor apariția primului volum (în 1910) din monumentala lucrare Principia Mathematica a lui A.N. Whitehead și B. Russell1. Trebuie precizat că atât Frege, cât și autorii Principiilor au urmărit „reducerea” unor părți din matematică - în special arit- metica - la logică. Cu alte cuvinte, au urmărit să arate că prin- cipiile acestor discipline matematice își au originea în principii de logică. încercarea s-a dovedit lipsită de succes, dar nu și de consecințe, căci a permis construirea primelor sisteme axio- matice formale. Astfel, discipline matematice importante, ca aritmetica și teoria mulțimilor, au căpătat fundamente axioma- tice în cadrul unor sisteme formale de logică (calcul cu predicate). 1 Primul dintre cei doi a fost matematician, iar al doilea logician și filozof. 98 Logică și metamatematică Necesitatea de a fundamenta astfel matematica a izvorât și din dorința de a pune ordine în bazele unor părți ale sale ca reacție la apariția - în cadrul acestor părți - a unor concepte cu caracter paradoxal (contradictoriu). Un exemplu de asemenea concept din teoria mulțimilor i-a fost semnalat lui Frege de către Russell. Reunind într-o aceeași colecție obiectele având o proprie- tate comună, ajungem la următoarele constatări. In unele cazuri însăși colecția acestor obiecte este un obiect având proprietatea comună elementelor sale. Astfel, de pildă, colecția noțiunilor abstracte este ea însăși o noțiune abstractă. în limbajul teoriei mulțimilor colecția A, a noțiunilor abstracte, este un element al lui A, fapt notat prin A G A. Dimpotrivă, colecția C - a noțiunilor concrete - nu este o noțiune concretă, ceea ce în limbajul menționat înseamnă 1 (C e Q, fapt notat de obicei prin C <£ C. Reunim într-o colecție - notată R - toate obiectele X având proprietatea X<£ X. în virtutea principiului terțului exclus Re R sau R<£ R în primul dintre cele două cazuri, R fiind element al colec- ției definită prin proprietatea X £ X, rezultă R£ R. în al doilea caz, având chiar această proprietate, R trebuie să fie element al colecției definită prin ea, adică al colecției Ă; deci Re R. Plecând așadar de la oricare dintre cele două afimații dedu- cem - pe cale logică - negația sa! Era firesc ca o astfel de provocare1 să nască aprinse contro- verse printre logicieni și matematicieni. O parte dintre aceștia (B. Russell, E. Zermelo și alții) consi- derând că principiile cantoriene2 ale teoriei mulțimilor trebuie 1 Au fost descoperite mai multe asemenea enunțuri contradictorii. Citi- torul poate găsi informații suplimentare în lucrarea lui A. Dumitriu: Istoria Logicii, București, 1975, cap. XLIII. 2 Matematicianul german G. Cantor (1845-1918) este creatorul teoriei moderne a mulțimilor. Logică și metamatematică 99 amendate, au creat sisteme axiomatice limitative în care, spe- rau ei, astfel de contradicții nu vor mai apare. L.E.J. Brouwer matematician olandez și creator al școlii de gândire numită „intuiționism” face o critică severă modului în care matematicienii utilizează în raționamentele lor noțiunea de mulțime infinită și - în legătură cu ea - o serie de principii logice (terțul exclus, dubla negație etc.). Critica intuiționistă avea drept consecință indirectă abando- narea unor rezultate și metode de lucru ce intraseră deja în patrimoniul matematicii începutului de secol. Considerată de mu Iți drept prea radicală, ea nu s-a bucurat de o adeziune largă (deși a fost susținută de unii matematicieni importanți). Cel care a luat imediat poziție în favoarea matematicii cla- sice a fost un reprezentant strălucit al acesteia - D. Hilbert. După ce, în 1899 reușise construirea primei axiomatizări satis- făcătoare a geometriei euclidiene, în 1904 el propune - pentru a salva „paradisul pe care ni l-a făurit Cantor” - crearea unui sistem formal axiomatic care să cuprindă matematica clasică. Hilbert spera că făcând din acest sistem un obiect de studiu - al așa-numitei teorii a demonstrației sau „metamatematicii” - să se poată demonstra cu mijloacele finitiste ale aritmeticii, admise și de intuiționiști, necontradicția sistemului însuși. „Programul formalist” de fundamentare a matematicii, cum s-a numit proiectul hilbertian, demarat după 1920, a înregistrat câteva succese1. Dar o limitare de principiu, descoperită în 1931 de K. Gbdel, a arătat că demonstrații -în sensul finitist propus de Hilbert - pentru consistența unor părți importante ale matematicii - în prealabil axiomatizate și formalizate - nu sunt posibile. Cercetările s-au orientat atunci către demonstrarea consistenței unor fragmente de matematică luând ca ipoteză consistența altora. Rezultate remarcabile obținute în această direcție au făcut ca, între timp, metamatematica să devină o disciplină cu statut bine definit în ansamblul celorlalte ramuri ale matematicii. 1 Cel mai promițător a fost demonstrația - cu mijloace nefinitiste - a necontraclicției sistemului formal axiomatic al aritmeticii, dată de G. Gentzen în 1936. 100 Bibliografie BIBLIOGRAFIE 1. Ambrose A., Lazerowitz M.: Fundamentals of symbolic logic,Y\ewYQv\g 1948 2. Clark R., Welsh P.: Introduction to logic, Princeton, 1962 3. Johnson D.L.: Elements of logic via numbers and sets, New York, 1998 4. Kleene S.C.: Mathematical logic, New York, 1967 5. Lewis Caroll: Mathematical recreations, New York, 1958 6. Lewis C.L, Langford C.H.: Symbolic logic, New York, 1951 7. Purtill R.: Logic for philosophers, New York, 1971 8. Quine W.V.O: Mathematical logic, New York, 1940 9. Stob M.: Undergraduate logic, Michigan, 1996 10. Strawson P.F.: Introduction to logical theory, London, 1952 11. Suppes P.: Introduction to logic, Princeton, 1957 Simboluri utilizate 101 SIMBOLURI UTILIZATE 1, A, V, => r F V,3 pag. 2 Pag- 3 pag. 12,56 pag. 18,61 pag. 29, 70 pag. 49 102 Index INDEX contraexemplu 15,57 cuantifi câtor 49 domeniul unui - 53 D (detașare) 28, 68 DN (dubla negație) 20 formulă contingență 15, 58 - inconsistentă 15, 58 - interpretarea unei - 54 - universal validă 55 modus ponens 12, 14, 18 - tollens 39 principiul necontradicției 15 propoziție simplă/compusă 4 S (regula substituției) 28, 68 TAB 1 5 TAB a, TAB v 6 TAB4=> 7 TAB => 8 tautologie 13 teoremă 29, 69 teorema deducției 32 terțul exclus 12, 39 transpoziția 38 univers 54 valori de adevăr 2 variabilă prepozițională 9 - individuală 52 - liberă/legată 53 EDITURILE ALL ALL I ALL BECKIALLFA ALL EDUCAȚIONAL I Bd. Timișoara nr. 58, sector 6,76548 - București sau C.P. 12-107 C0RSSsNTĂ Tel.: (01) ■ 402 26 00; (01) ■ 402 2611; (01) ■ 402 26 20 Fax: (01) ■ 402 26 10 - Fax Distribuție: (01) ■ 402 26 30 TALON DE COMANDA Trimiteți talonul de comandă, completat conform dorinței dumneavoastră, pe adresa Editurilor ALL: București, O.P. 12, C.P. 107, beneficiind de o reducere de din prețul cărților pe care vi le oferim. C.R. SE TAXEAZĂ LA DESTINAȚIE EXP E D !TORvĂ rugâm s completat| cât ma| c|tet posibil) Nume și adresă (persoană fizică): DESTINATAR Editările ALL București, O.P. 12, C.P. 107 Telefon: Nume și adresă (instituție, firmă, școală): Te I ef o n: Cod client: Profesie: Plata va fi efectuată de: I I I I (persoană fizică) (instituție, firmă, școală) Menționați domeniile pentru care doriți să primiți, GRATUIT* buletinul informativ semestrial: □ ȘTIINȚE MEDICALE □ BELETRISTICĂ □ ȘTIINȚE JURIDICE / ȘTIINȚE ECONOMICE □ ȘTIINȚE EXACTE / INFORMATICĂ □ ȘTIINȚE UMANISTE PLATA SE VA FACE RAMBURS (LA PRIMIREA COLETULUI POȘTAL), TAXELE POȘTALE DE EXPEDIȚIE FIIND SUPORTATE DE EDITURĂ. PENTRU COMENZI MAI MARI DE 10 EXEMPLARE, CUMULAT, BENEFICIAT! DE O REDUCERE DE PREȚ DE OAO/ Cod Titlu / Autor Preț Nr. ex. Colecția FIOSOFIE POLITICĂ 1399 CONSERVATORISMUL ANGLO-SAXON Adrian-Paul lliescu 14900 lei 1400 DINCOLO DE LIBERALISM ȘI CONSERVATORISM John Gray 49000 lei 1401 LIMITELE PUTERII Adrian-Paul lliescu, Mihail-Radu Solcan 14000 lei 1402 MIZERIA ISTOR1CISMULUI - Karl R. Popper 34900 lei 1403 OAMENI DE STAT ÎNTR-0 LUME INTERDEPEN- DENTĂ. ADENAUER, DE GAULLE, THATCHER, REAGAN ȘI GORBACIOV - Ghiță lonescu 69000 lei 1404 RAȚIONALISMUL ÎN POLITICĂ Michael Oakeshott 14000 Iei Colecția ANTHROPOS 1405 FRAGILITATEA UMANĂ ÎN GÂNDIREA ANTROPOLOGICĂ - Ecaterina Morar 44000 lei Colecția ACCENTE 922 CUM NE ȚESEM EUL - G. G. Conslandache 19900 lei 1071 INTRODUCERE ÎN ALGORITMI GENETICI Paul Flondor, Cezar lonescu 24900 lei POLITOLOGIE 1406 ARHEOLOGIA TERORII - Vladimir Tismăneanu 34000 lei 1407 CHURCHILL. O VIAȚĂ DE REBEL Norman Rose 139000 lei 1408 DIPLOMAȚIA - Henry Kissinger 169000 lei 374 LIBERTATEA. DOUĂ SAU TREI LUCRURI PE CARE LE ȘTIU DESPRE EA... - Christian Michel 7900 lei Colecția ȘTIINȚE POLITICE 614 PLURIPARTIDISMUL. O TEORIE A DEMOCRAȚIEI George Voicu 39900 lei 965 TRADIȚIA CONSERVATOARE ÎN GÂNDIREA AMERICANĂ, 1783-1860 - Octavian Roske 69900 lei 1029 VIOLENȚĂ, MIT ȘI REVOLUȚIE. DE LA VIOLENTA RITUALA LA VIOLENȚA SIMBOLICĂ ȘI DONJUAN1SMUL POLITIC - Ștefan Stănciugelu 50000 lei Colecția REPERE 1395 F1LOSOFIE FĂRĂ HAINE DE GALĂ. DESPRE FILOSOFIE ȘI POLITICĂ - Adrian Miroiu 54000 lei 1396 TEMEIURI ALE COGNIȚIEI. CUM ESTE MODELATĂ MINTEA DE CĂTRE COMPORTAMENTUL TELEOLOGIC - Radu J. Bogdan 49000 lei 1011 TRANZIȚII ONTOLOGICE Gheorghe-Sorin Părăoanu 29900 lei Editurile ALL își rezervă dreptul de a face modificări asupra prețurilor menționate!