LogicamatematicaGeorgeGeorgescu1,AfroditaIorgulescu21UniversitateadinBucuresti,CatedradeFundamenteleInformaticii2AcademiadeStudiiEconomice,CatedradeInformaticaEconomicaOctober1,20092345Prefat aLogica se ocupa de legile gandirii (rat iunii) si anume de acele proprietat i struc-turale formale ale gandirii care apar n reectarea proprietat ilor lumii reale. Deciavem gandirea, realitatea si legatura dintre ele. In logica exista substituient i abstract ipentru gandire, pentru realitate si pentru legatura dintre ele si anume, limbajul 1substituie gandirea, structuraosubstituie realitatea (undeoeste mai mult decato colect ie de lucruri susceptibile de a corelate, ca nt eles, diferitelor expresii dinlimbaj), iar interpretarea1substituie legatura (1este o funct ie).Limbajul 1 este xat, dar se considera mai multe interpretari ale lui 1n diferitestructuri; aceasta pentru ca, pe de-o parte, nu stim n care realitate (lume) partic-ulara ne regasim cu adevarat, pe de alta parte pentru ca logicienii sunt interesat ide principiile universale, care sunt adevarate n orice lume posibila.O teorie (n sens tehnic) este un limbaj 1mpreuna cu o mult ime Tde propozit iisau formule din 1. In practica, o teorie este denita e sintactic, e semantic, adica:-Tpoateformatadintoateformulelecarerezultaprintr-orelat iedeimplicaresintactica dintr-o mult ime de axiome sau-Tpoate formata din toate formulele care sunt adevarate n orice interpretareconsiderata.Scopul principal al logicii este studiul n paralel al relat iei de implicare sintactica(formala):j c (c se deduce dinj conform unor reguli prestabilite)si al relat iei de implicare semantica (reala):j [= c (dacaj este adevarata, atuncic este adevarata).Logicaclasicaeste bivalenta, nsensul camult imeavalorilor de adevar aredoua elemente: adevarul si falsul. Logicapropozit iilor este teoriaTa tuturor for-mulelor valide(i.e. caresunt adevarate noriceinterpretare) ntr-unlimbaj 1al propozit iilor. Aceastateorieestedecidabila(existaunalgoritmcare, aplicatoricarei formule, nespunedacaeaestedinT). LogicapredicateloresteteoriaTatuturorformulelorvalide ntr-unlimbaj 1al predicatelor. Presupunandca1are cel put in un simbol de funct ie de rang cel put in 1 sau un simbol de relat ie derang cel put in 2,atunci Tnu este decidabila,dar este axiomatizabila (i.e. existao axiomatizare a lui T(cu axiome si reguli de inferent a) sub care formulele lui Tsunt demonstrabile).In secolul al 19-lea apar primele sisteme de logica polivalenta.In evolut ia unei teorii stiint ice se disting patru etape succesive: etapa descrip-tiva,etapainductiva,etapadeductiva sietapaaxiomatica. Organizarea stiintei nteorii deductiveestelegatadeevolut iamatematiciisi deexpansiuneametodelorsale n celelalte stiint e.Eu arm can orice disciplina a naturii se gaseste de fapt numai atata adevaratastiint a cata matematica se cuprinde n ea (Immanuel Kant).6Logica matematica este stiint a care are ca obiect studiul formelor propozit ionalesi al legilor de rat ionare cu expresii propozit ionale, precum si metodele care permitrealizarea acestui studiu.In studiul propozit iilor sau al expresiilor propozit ionale, logica matematica esteinteresata numai de valoarea logica.R. Descartes, prin ncercarea de a forma o stiint a matematica generala, a stim-ulat cercetarile logice n direct ia simbolismului matematic, lucru realizat part ial deG. Leibniz.La jumatatea secolului al 19-lea, George Boole si Augustus De Morgan au in-trodusmetodelematematice nlogica, creandlogicamatematica. Calculul logical lui G. Booleestebivalentsi sefacedupareguliledinalgebra; el stalabazacalculatoarelor actuale.Contribut ii ulterioare au adus G. Frege, G. Peano, B. Russell si Godel. Primultratatmoderndelogicamatematica, PrincipiaMathematicaafostscrisdeB.Russell si A.N. Whitehead, ntre 1910-1913.Intr-o etapa ulterioara apare logica polivalent a (cu mai multe valori de adevar),prinlucrarilelui J.Lukasiewiczsi L.E. Post, apoi alelui C.C. Chang. Int aranoastra, cercetarile de logica matematica au fost init iate de Gr. C. Moisil n 1933si cunosc n prezent o mare dezvoltare.Aplicat iilelogiciimatematiceseregasesclateoriaalgebricaaautomatelor, laprogramareaautomata, laprogramarealogica, labazelededaterelat ionale, ninteligent a articiala. Cercetarile contemporane tind sa extinda considerabil sferaaplicat iilor (logica fuzzy se aplica n economie, de exemplu).In paralel cu logica matematica, si n stransa legatura cu ea, s-a dezvoltat alge-bralogicii matematice (teoria algebrelor Boole, teoria algebrelor MV, a algebrelor Lukasiewicz-Moisil, etc.), care constituie n prezent un capitol separat din algebra.Inaceastalucraresuntprezentatelogicaclasica, cudouavalori deadevar,simodelul ei algebric, algebraBoole. Algebrelelogicilorcumai multevalori suntprezentate in [29].Lucrarea se adreseaza student ilor facultat ilor de matematica informatica si in-formatica economica, dar si unui public mai larg.Bucuresti, Septembrie 2009AutoriiContents1 Calcululpropozit iilor(Prez. neformalizata) 111.1 Propozit iile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.2 Valorea de adevar a unei propozit ii . . . . . . . . . . . . . . . . . . . 122 Calcululpredicatelor(Prez. neformalizata) 232.1 Predicatele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.2 Valoarea de adevar a unui predicat . . . . . . . . . . . . . . . . . . 283 Latici 333.1 Mult imi (pre)ordonate . . . . . . . . . . . . . . . . . . . . . . . . . . 333.1.1 Principiul dualitat ii. Diagrama Hasse . . . . . . . . . . . . . 343.1.2 Reprezentareaunei relat ii binarepeomult imenitaprinmatrice booleana. . . . . . . . . . . . . . . . . . . . . . . . . 353.1.3 Prim (ultim) element, minorant (majorant), inmum (supre-mum). Axioma lui Zorn . . . . . . . . . . . . . . . . . . . . . 363.2 Latici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.2.1 Latici Ore si latici Dedekind. Echivalent a lor . . . . . . . . . 383.2.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.2.3 Latici distributive. Latici marginite complementate . . . . . . 444 AlgebreBoole 494.1 Algebre Boole: denit ie, exemple, proprietat i . . . . . . . . . . . . . 494.1.1 Denit ia algebrei Boole . . . . . . . . . . . . . . . . . . . . . 494.1.2 Exemple de algebre Boole . . . . . . . . . . . . . . . . . . . . 514.1.3 Proprietat i ale algebrelor Boole. . . . . . . . . . . . . . . . . 534.1.4 Implicat ia si echivalent a booleana . . . . . . . . . . . . . . . 544.2 O denit ie echivalenta a algebrelor Boole . . . . . . . . . . . . . . . 554.2.1 Axiomele (B1) - (B7) implica (A1) - (A4) . . . . . . . . . . . 564.2.2 Axiomele (A1) - (A4) implica (B1) - (B7) . . . . . . . . . . . 574.2.3 Aplicat iile sisunt mutual inverse . . . . . . . . . . . . . 634.3 Inel Boole. Echivalent a cu algebra Boole . . . . . . . . . . . . . . . . 644.4 Subalgebre, homomorsme . . . . . . . . . . . . . . . . . . . . . . . . 664.5 Filtre (ideale) si congruent e. Algebre Boole cat . . . . . . . . . . . . 7078 CONTENTS4.5.1 Filtre (ideale) si sisteme deductive . . . . . . . . . . . . . . . 704.5.2 Congruent e. Corespondent a ltre - congruent e . . . . . . . . 714.5.3 Algebra Boole cat . . . . . . . . . . . . . . . . . . . . . . . . 734.5.4 Filtru generat de o mult ime . . . . . . . . . . . . . . . . . . . 764.6 Teorema de reprezentare a lui Stone . . . . . . . . . . . . . . . . . . 774.7 Algebre Boole atomice . . . . . . . . . . . . . . . . . . . . . . . . . . 804.8 Dualitatea algebrelor Boole . . . . . . . . . . . . . . . . . . . . . . . 824.9 Algebre Boole injective . . . . . . . . . . . . . . . . . . . . . . . . . . 874.10Filtre fuzzy ale unei algebre Boole . . . . . . . . . . . . . . . . . . . 914.10.1 Mult imi fuzzy . . . . . . . . . . . . . . . . . . . . . . . . . . . 914.10.2 Filtre fuzzy ale unei algebre Boole . . . . . . . . . . . . . . . 935 Mult imi 955.1 Conceptele fundamentale ale teoriei mult imilor:clasa si apartenent a;mult imea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955.2 Relat ia de incluziune si relat ia de egalitate ntre clase (mult imi) . . 985.2.1 Relat ia de incluziune ntre clase (mult imi). . . . . . . . . . . 985.2.2 Relat ia de egalitate ntre clase (mult imi) . . . . . . . . . . . . 995.3 Operat ii cu mult imi. Algebra Boole a mult imilor . . . . . . . . . . . 1005.3.1 Reuniuneasi intersect iaadouamult imi. Complementaraunei mult imi . . . . . . . . . . . . . . . . . . . . . . . . . . . 1015.3.2 Generalizare: reuniunea si intersect ia an mult imi . . . . . . 1035.3.3 Generalizare: reuniunea si intersect ia unei familii de mult imi 1045.3.4 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1046 Relat ii 1076.1 Produs cartezian a doua mult imi. Relat ii binare . . . . . . . . . . . 1076.1.1 Produs cartezian a doua mult imi . . . . . . . . . . . . . . . . 1076.1.2 Relat ii binare . . . . . . . . . . . . . . . . . . . . . . . . . . . 1086.2 Generalizare: Produs cartezian an mult imi (n 2). Relat iin-are . . 1096.2.1 Produs cartezian an mult imi . . . . . . . . . . . . . . . . . . 1096.2.2 Relat iin-are (n 2) . . . . . . . . . . . . . . . . . . . . . . . 1106.3 Operat ii cu relat ii. Algebra Boole a relat iilor . . . . . . . . . . . . . 1116.3.1 Disjunct ia, conjunct ia si negat ia unei relat ii binare . . . . . . 1116.3.2 Implicat ia si echivalent a relat iilor binare. . . . . . . . . . . . 1126.3.3 Algebra Boole a relat iilor . . . . . . . . . . . . . . . . . . . . 1136.4 Algebra relat ionala a relat iilor . . . . . . . . . . . . . . . . . . . . . . 1146.4.1 Compunerea si inversarea relat iilor binare . . . . . . . . . . . 1146.5 Baze de date relat ionale . . . . . . . . . . . . . . . . . . . . . . . . . 1186.5.1 Reprezentarea relat iilor. Denit ii . . . . . . . . . . . . . . . . 1186.5.2 Limbajele de prelucrare a datelor. . . . . . . . . . . . . . . . 120CONTENTS 97 Sistemulformalalcalcululuipropozit ional(L) 1217.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1227.2 Sintaxa si algebra calculului propozit ional . . . . . . . . . . . . . . . 1257.2.1 Proprietat i sintactice ale lui1 . . . . . . . . . . . . . . . . . 1287.2.2 Algebra Lindenbaum-Tarski - varianta 1. . . . . . . . . . . . 1417.2.3 Algebra Lindenbaum-Tarski - varianta 2. . . . . . . . . . . . 1457.2.4 Prealgebre Boole. Algebrele Boole ca prealgebre Boole cat . . 1497.3 Semantica calculului propozit ional1. . . . . . . . . . . . . . . . . . 1557.3.1 Mult imi consistente. Teorema de completitudine extinsa (tare)1597.4 Teorema de completitudine versus Teorema lui Stone. . . . . . . . . 1637.5 Exemple de deduct ii formale . . . . . . . . . . . . . . . . . . . . . . . 1658 Sistemulformalalcalcululuicupredicate 1758.1 Structuri si limbaj . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1778.2 Semantica calculului cu predicate. . . . . . . . . . . . . . . . . . . . 1838.3 Exemple de enunt uri universal adevarate . . . . . . . . . . . . . . . . 1938.4 Sintaxa calculului cu predicate . . . . . . . . . . . . . . . . . . . . . 1988.5 Algebra Lindenbaum-Tarski a calculului cu predicate . . . . . . . . 2088.5.1 Algebre Boole monadice. Algebre Boole cilindrice . . . . . . . 2118.6 Teorema de completitudine. Modele Henkin. . . . . . . . . . . . . . 2138.7 Cum se stabileste daca o formula este teorema formala. . . . . . . . 2239 Dimensiuneaprobabilistaalogiciiclasice 2279.1 Probabilitat i pe algebre Boole. . . . . . . . . . . . . . . . . . . . . . 2289.1.1 Evenimente si probabilitat i . . . . . . . . . . . . . . . . . . . 2289.1.2 Proprietat i ale probabilitat ilor . . . . . . . . . . . . . . . . . 2309.1.3 -algebre si-probabilitat i . . . . . . . . . . . . . . . . . . . 2329.1.4 Teorema lui Caratheodory . . . . . . . . . . . . . . . . . . . . 2359.1.5 Teorema Horn-Tarski . . . . . . . . . . . . . . . . . . . . . . 2409.2 Modele probabiliste ale calculului cu predicate . . . . . . . . . . . . 2449.2.1 Structuri probabiliste . . . . . . . . . . . . . . . . . . . . . . 2449.2.2 Teorema de completitudine a lui Gaifman . . . . . . . . . . . 2499.2.3 Catre o teorie a modelelor probabiliste. . . . . . . . . . . . . 25110 CONTENTSChapter1Calcululpropozit iilor(Prezentareneformalizata)Vom face aici o prezentare neformalizata a calculului propozit iilor clasic (biva-lent), prezentarea formalizata ind facuta mai tarziu. Se spune, echivalent, Calcululpropozit iilor (propozit ional) sau Logica propozit iilor.In calculul propozit iilor se studiaza propozit iile (=propozit ii nchise) din punctulde vedere al adevarului sau falsitat ii lor, neluandu-se n seama cont inutul lor.1.1 Propozit iileDenit ie1.1.1Un enunt este un text lingvistic care se refera la un anumit dome-niul, numit univers al discursului si exprima o proprietate a unui obiect ( sau aunui grup de obiecte) din universul respectiv.Subiectul (subiectele) enunt ului exprima obiectul (obiectele).Partea predicativ a a enunt ului exprima proprietatea.Denit ie1.1.2Propozit ia este enunt ul cu sens, n care toate subiectele sunt de-terminate.Vom nota propozit iile cuj. c. :. :. t. . . ..Vom nota cu 10 mult imea propozit iilor init iale, date, primitive. Din propozit iiledate n10seconstruiescpropozit iinoi, compuse, cuajutoruloperatorilorlogici,propozit ionali (=conectorilor logici, propozit ionali): . . . . . Astfel,pentruj. c propozit ii, avem urmatoarele denit ii.Denit ie1.1.3Senumestenegat iapropozit iei j, si senoteaza: j(secitestenon p), propozit ia care arma proprietatea contrara celei exprimate dej si carese construieste lingvistic dinj prin intercalarea particuleinegative nu n fat apart ii predicative a luij.1112CHAPTER1. CALCULULPROPOZIT IILOR(PREZ.NEFORMALIZATA)Denit ie1.1.4Senumestedisjunct iapropozit iilorj. c(naceastaordine),sisenoteaza: j c (se citeste p sau q), propozit ia care arma ca celput inuna dinproprietat ile exprimate dej sic are loc si care se construieste lingvistic alaturandtextelecelordouapropozit ii nordinea(j. c)si intercaland ntreeleparticuladisjunctiva sau.Denit ie1.1.5Se numeste conjunct iapropozit iilorj. c(n aceasta ordine), si senoteaza: jc (se citeste p si q), propozit ia care arma ca ecare din proprietat ileexprimate dej sic are loc si care se construieste lingvistic alaturand textele celordouapropozit ii nordinea(j. c)si intercaland ntreeleparticulaconjunctivasi.Denit ie1.1.6Senumesteimplicat iapropozit iilorj. c(naceastaordine),sisenoteaza: j c (se citeste p implica q sau daca p atunci q), propozit ia: jc.Denit ie1.1.7Se numeste echivalent a propozit iilorj. c (n aceasta ordine), si senoteaza: j c(secitestepechivalentcuqsaupdacasi numai dacaq),propozit ia: (j c) (c j). Deci, echivalent a este conjunct ia a doua implicat iide sens contrar.Observat ii1.1.81)Implicat iasi echivalent asedenesccuajutorul operatorilorpropozit ionali. . .2) Operatorii propozit ionali afecteaza partea predicativa a enunt urilor, nu sisubiectul (subiectele).3) Obiectul de studiual calculului propozit iilor este mult imea 1 atuturorpropozit iilor, careseobt inplecanddelapropozit iiledin10si aplicandrepetat,ntoatemodurileposibile, conectorii logici . . . . . Mai exact spus,mult imea1se deneste prinrecurent a astfel:(R1) Dacaj 10, atuncij 1.(R2) Dacaj. c 1, atunci j. j c. j c. j c. j c 1.(R3) Orice propozit iej 1se obt ine aplicand regulile (R1) si (R2) de un numarnit de ori.4) Daca j. c sunt propozit ii n sensul logicii matematice, atunci j c. j c etc.sunt propozit ii n sensul logicii matematice, dar din punctul de vedere al gramaticiinu sunt propozit ii, ci fraze. Deci, not iunea de propozit ie cu care lucreaza calcululpropozit iilor este diferita de notiunea de propozit ie din gramatica.1.2 Valoreadeadevarauneipropozit iiLogica (clasica a) propozit iilor este bivalenta, adica studiaza doar propozit iile caresunteadevarate, efalse, adicacareauceledouavalori deadevarextreme:adevarat si fals.1.2. VALOREADEADEVARAUNEIPROPOZIT II 13Observat ii1.2.11) Ipoteza este ca ecare propozit ie are o valoare de adevar. Este clar capropozit iileinterogative (Ce mai faci? etc. ),celeexclamative (Ce frumoseste afara! etc.) precum si cele imperative (Fii atent! etc.) nu au valoare deadevar. Deci, doarpropozit iiledeclarativefacobiectul studiului logiciimatematice,suntpropozit ii nsensulcalcululuipropozit iilor.2) Problema determinarii valorilor de adevar ale propozit iilor din mult imea10data la nceput nu apart ine logicii matematice. De exemplu, daca o propozit iej 10 este din domeniul chimiei, atunci stabilirea valorii de adevar a propozit iei jeste o problema a chimiei etc.Nu se presupune ca am cunoaste efectiv valorile de adevar ale tuturor propozit iilordin10.Denit ie1.2.2Opropozit ieesteadevaratadacasi numai dacastareadefaptdescrisa de propozit ie are loc.Stabilirea adevarului unei propozit ii se poate face si in raport cu adevarul altorpropozit ii.Sa denim acum valorile de adevar ale propozit iilor compuse j. jc. jc. j c. j c n funct ie de valorile de adevar ale propozit iilor componente,j sic.Denit ie1.2.3Propozit ia j este adevarata daca si numai daca propozit ia j estefalsa. Rezultacapropozit ia jestefalsadacasi numai dacapropozit iajesteadevarata.Denit ie1.2.4Propozit ia jc este adevarata daca si numai daca cel put in unadin propozit iilej. ceste adevarata. Rezulta caj ceste falsa daca si numai dacaambele propozit iij. c sunt false.Denit ie1.2.5Propozit ia jc este adevarata daca si numai daca ambele propozit iij. c sunt adevarate. Rezulta caj c este falsa daca si numai daca celput inunadin propozit iilej. c este falsa.Pentru orice propozit iej 10, sa asociem 1 valorii de adevar adevarat si 0valorii de adevar fals, adica sa denim funct ia de adevar (de evaluare)0 : 10 0. 1astfel: pentru oricej 10,0(j) =

1. daca j este adevarata.0. daca j este falsa.Funct iadeadevar0: 10 0. 1seextinde(prelungeste) nmoduniclafunct ia de adevar : 1 0. 1 astfel: pentru oricej. c 1,(j) =

1. (j) = 0.0. (j) = 1.14CHAPTER1. CALCULULPROPOZIT IILOR(PREZ.NEFORMALIZATA)(j c) =

1. (j) = 1 sau(c) = 1.0. (j) = 0 si(c) = 0.(j c) =

1. (j) = 1 si(c) = 1.0. (j) = 0 sau(c) = 0.Deducem ca(j c) = (jc) =

1. (j) = 1 sau(c) = 1.0. (j) = 0 si(c) = 0.=

1. (j) = 0 sau(c) = 1.0. (j) = 1 si(c) = 0.si(j c) = ((j c) (c j)) =

1. (j c) = 1 si(c j) = 1.0. (j c) = 0 sau(c j) = 0.=

1. [(j) = 0 si(c) = 0] sau [(j) = 1 si(c) = 1].0. [(j) = 1 si(c) = 0] sau [(j) = 0 si(c) = 1].Obt inem atunci urmatoarele tabeledeadevar:(1)(j) (j)0 11 0(2)(j) (c) (j c) (j c) (j c) (j c)0 0 0 0 1 10 1 1 0 1 01 0 1 0 0 01 1 1 1 1 1sau urmatoarele matricideadevar:(j c) v(q)=0 v(q)=1v(p)=0 0 1v(p)=1 1 1(j c) v(q)=0 v(q)=1v(p)=0 0 0v(p)=1 0 1(j c) v(q)=0 v(q)=1v(p)=0 1 1v(p)=1 0 1(j c) v(q)=0 v(q)=1v(p)=0 1 0v(p)=1 0 11.2. VALOREADEADEVARAUNEIPROPOZIT II 15Observat ie1.2.6Dintr-o premiza (ipoteza) falsa,j, se poate obt ine o concluzie,c, adevarata sau falsa, implicat ia ind adevarata. Deci, atent ie la ipoteze.Rezulta ca ecarei propozit ii j 1 i asociem o valoare de adevar (j) 0. 1dupa urmatoarele reguli:1) Dacaj 10, atunci(j) = 0(j),2) Dacaj. c 1si am asociat propozit iilorj. cvalorile de adevar(j). (c),atunci asociempropozit iilor j. j c. j c. j c. j cvaloriledeadevar(j). (j c). (j c). (j c). (j c) date de tabelele sau matricile de maisus.Sadenimpemult imea12= 0. 1 1operat iaunara L2si operat iilebinare L2. L2. L2. L2astfel: pentru oricer. n 12,

L2rdef.=1 r. . r L2ndef=max(r. n). r L2ndef.=min(r. n).andr L2ndef.=(L2r) L2n. r L2ndef.=(r L2n) L2(n L2r).Deducem urmatoarele tabele de valori:(3)r L2r0 11 0(4)r n r L2n r L2n r L2n r L2n0 0 0 0 1 10 1 1 0 1 01 0 1 0 0 01 1 1 1 1 1Din tabelele (1), (2) si (3), (4), se vede ca funct ia : 1 12este un homo-morsm(adica pentru oricej. c 1,(j) = L2(j),(j c) = (j) L2(c),si (j c)=(j) L2(c); rezultaca(j c)=(j) L2(c) si (j c)=(j) L2(c)). Se observa ca este surjectiv, dar nu este injectiv.Propozit ia1.2.7Structura L2= (12= 0. 1. L2. L2. L2. 0. 1)esteoalgebraBoole cu doua elemente, numita algebraBoolecanonica.Dem. Rutina. 2Denit ie1.2.8Opropozit iecompusaj 1careesteadevarataindependentdevaloriledeadevar ale propozit iilor componente se numeste propozit ie universal adevarata sautautologie.O propozit ie compusaj 1care este falsa independent de valorile de adevarale propozit iilor componente se numeste contradict ie sau antilogie.16CHAPTER1. CALCULULPROPOZIT IILOR(PREZ.NEFORMALIZATA)Se observa ca o propozit iej 10nu poate tautologie sau antilogie, caci nu estecompusa.Exemplu1.2.9Exempludeantilogie Pentru oricej 1,j j Principiul contradict iei.Exemple1.2.10Exemple de tautologii Vom grupa unele exemple n grupe sausistemedetautologii, notate /1, /2, /3, /4, /5, sistemecorespunzatoarecelormai utilizate sisteme de axiome ale sistemului formal al calculului propozit iilor.Sa notam cu O propozit iaj j si cu I propozit iaj j, pentru oricej 1.Atunci Sistemul /1(. . . . O,I):(P1)j j j. j j j (idempotent a lui . ),(P2)j c c j. j c c j, (comutativitatea lui . ),(P3)j (c :) (j c) :. j (c :) (j c) :,(asociativitatealui. ),(P4)j (j c) j. j (j c) j, (absorbt ia),(P5) j(c:) (jn)(j:). j(c:) (jn)(j:), (distributivitatealui fat a de si invers),(P6)j O j. j I j,(P7)j j, adica I (Principiul tert ului exclus), (j j) adica O (Prin-cipiul contradict iei). Sistemul /2(. ):(G1)j (c j),(G2) [j (c :)] [(j c) (j :)],(G3) (c j) (j c). Sistemul /3(. . . ):(G1)j (c j),(G2) [j (c :)] [(j c) (j :)],(G3) (c j) (j c),(T4)j c j,(T5)j c c,(T6)j j c,(T7)c j c,(T8) (: j) [(: c) (: (j c))],(T9) (j :) [(c :) ((j c) :)]. Sistemul /4(. ):1.2. VALOREADEADEVARAUNEIPROPOZIT II 17(S1) (j j) j,(S2)j (j c),(S3)j c c j,(S4) (j c) [(: j) (: c)]. Sistemul /5(, O):(V1)j (c j),(V2) [j (c :)] [(j c) (j :)],(V3) [(j O) O] j.Alte tautologii remarcabile sunt urmatoarele:(P8) (j c) j c. (j c) j c(Legile De Morgan),(P9) j j (Principiul dublei negat ii),(P10) (j c) [(j c) (j j)]. (j c) [(j c) (j j)],(P11)j j,(P12)[(j c) j] (j c). [(j c) c] (j c)(douadinschemele reducerii la absurd),(P13) (j c) (c j) (se foloseste n demonstrat ii),(P14) (j c) j c(arata cum se neagaj c),(P15)j (j c) j c,(P16) [j (j c)] (j c),(P17) [(j c) c] j c,(P18) [j (c :)] [(j c) :] (sta la baza Teoremei deduct iei),(P19)j (c j),(P20) [(j c) :] [j (c :)],(P21) [(j c) (j :)] [j (c :)],(P22) (j c) [(: j) (: c)],(P23) [j (j c)] c(Modus ponens).In general, aam daca o propozit ie compusa oarecarej 1este tautologie saunu cu ajutorul urmatorului algoritm:Daca propozit iaj 1se descompune n propozit iile componentej1. j2. . . . . jn 10, atunci vectorul ((j1). (j2). . . . . (jn)) 0. 10. 1. . . 0. 1 = 0. 1n.Mult imea 0. 1nare 2nelemente. Parcurgem atunci un ciclu care genereaza cele2nelemente(vectori); pentruecareelement(o1. o2. . . . . on) 0. 1ncalculam(j) folosind valorile(ji) = oi,i = 1. . . . . n si:- daca pentru un anumit element (o1. o2. . . . . on) 0. 1nobt inem (j) = 0, atunciciclul se opreste, cu raspunsul j nu este tautologie;- dacaciclul setermina, adicadacapentrutoatecele2nelementedin 0. 1nobt inem(j) = 1, atunci raspunsul este j este tautologie.Daca nalgoritmulprezentatcontinuamsacalculam(j) sidupace ntalnimvaloarea 0, deci daca ducem ciclul pana la capat, atunci realizam tabela de adevara propozit iei datej.18CHAPTER1. CALCULULPROPOZIT IILOR(PREZ.NEFORMALIZATA)Faptul ca se poate stabili algoritmic daca o propozit ie oarecare este tautologiesaunuconstituieoproprietateimportanta, careseenunt asubforma: calcululpropozit iilorestedecidabil.Tabelele de adevar, sau matricile de adevar, constituie deci o modalitate algo-ritmica de a determina valoarea de adevar a unei propozit ii compuse. Mai existasi alte modalitati,nealgoritmice, si anume bazate pe proprietat i deja stabilite alealtor propozit ii.Sa denim pe mult imea1o relat ie binara astfel: pentru oricej. c 1,j c daca si numai dacaj c este tautologie.deci daca si numai daca(j c) = 1 ntotdeauna. Vom nota astfel:j cdefj c este tautologie, sauj cdef(j c) = 1.Atunci sunt adevarate urmatoarele doua Propozit ii.Propozit ia1.2.11Relat ia este o relat ie de echivalent a pe1.Dem.(i) estereexiva, adicapentruoricej 1, j j. Intr-adevar, ej 1,propozit iexata, altfel arbitrara; j jdefj jestetautologie, ceeaceesteadevarat, conform (P11). Conform Principiului Generalizarii , (PG) pe scurt,rezulta ca pentru oricej 1,j j; deci (i) are loc.(ii) estesimetrica, adicapentruoricej. c 1, j cimplicac j. Intr-adevar, e j. c 1propozit ii xate, altfel arbitrare; j cdef(j c) = 1; atunci(c j) = 1, adicac j, decij c implicac j. Conform (PG), pentru oricej. c 1,j c implicac j, deci (ii) are loc.(iii) estetranzitiva, adicapentruoricej. c. : 1, j csi c :implicaj :. Intr-adevar, e j. c. : 1propozit ii xate, altfel arbitrare; (j csic :)def((j c) = 1 si(c :) = 1); atunci(j) (c) (j c)0 0 11 1 1(c) (:) (c :)0 0 11 1 1Atunci obtinem:1.2. VALOREADEADEVARAUNEIPROPOZIT II 19(j) (:) (j :)0 0 11 1 1deci(j :) = 1, adicaj :, decij c sic : implicaj :. Conform (PG),pentru oricej. c. : 1,j c sic : implicaj :, deci (iii) are loc. 2Propozit ia1.2.12Pentru oricej. c. j

. c

1, avem proprietat ile:1) dacaj catunci j c,2) dacaj j

sic c

, atunci (j c) (j

c

) si (j c) (j

c

),3) (j j) (c c) si (j j) (c c).Dem.1) Fiej. c 1, xate, altfel arbitrare;j cdef(j c) = 1; atunci avem:(j) (c) (j c) (j) (c) (j c)0 0 1 1 1 11 1 1 0 0 1adica j c. Rezulta, conform(PG), capentruoricej. c 1, dacaj c,atunci j c.2) Fie j. c. j

. c

1, xate, altfel arbitrare; (j j

si c c

)def((j j

) = 1si(c c

) = 1), adica:(j) (j

) (j j

)0 0 11 1 1si(c) (c

) (c c

)0 0 11 1 1de unde obt inem:(j) (j

) (c) (c

) (j c) (j

c

) ((j c) (j

c

))0 0 0 0 0 0 10 0 1 1 1 1 11 1 0 0 1 1 11 1 1 1 1 1 1adicaj c j

c

. Rezulta, conform(PG), capentruorice j. c. j

. c

1,dacaj j

si c c

, atunci (j c) (j

c

). Analogsedemonstreazaca(j c) (j

c

).3)Fie j. c 1, xate, altfel arbitrare; j j c cdef((j j) (c c)) = 1; atunci avem:20CHAPTER1. CALCULULPROPOZIT IILOR(PREZ.NEFORMALIZATA)(j) (c) (j) (c) (j j) (c c) ((j j) (c c))0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 1 1 11 1 0 0 1 1 1adicaj j c c. Rezulta, conform (PG), ca pentru oricej. c 1,j j c c. Restul se demonstreaza la fel. 2Observat ii1.2.131) Propozit ia 1.2.12 spune ca relat ia este o relat ie de congruent ape (1. . . ).2) In mod uzual, relat ia se mai noteaza .Deoarece este o relat ie de echivalent a pe 1, sa formam clasele de echivalent a;vom nota cu

jclasa luij, pentru oricej 1, i.e.

j= c 1 [ c j.Lema1.2.14

j=

cj c.Dem.=:

j=

cimplicaj

c, decij c.=: j c implica

j

csi

c

j, adica

j=

c. Intr-adevar,

j

cnseamna capentru orice:,:

j :

c. Fie: cu:

j; deci,: j; darj c; rezulta: c,adica:

c. 2Fie1=

j[j 1. Atunci sa denim pe1doua operat ii binare, si

, o operat ie unara,1G astfel: pentru orice

j.

c 1,

j

cdef.=

j c.

j

cdef.=

j c.1G

jdef.=

j .Acestetrei operat ii suntbinedenite(adicanudepinddereprezentant ii alesi aiclaselor), conform Propozit iei 1.2.12(1),(2). Sa consideram, de asemenea, urmatoareleelemente remarcabile din1(conform Propozit iei 1.2.12(3)):

1def.= j j [ j 1si

Odef.= j j [ j 1.Obt inem atunci urmatoarea1.2. VALOREADEADEVARAUNEIPROPOZIT II 21Teorema1.2.15Structura (1.

.

. 1G.

O.

1 ) este o algebra Boole.Dem. Trebuie sa demonstram ca, pentru orice

j.

c.

: 1:(B1)

j

j=

j.

j

j=

j,(B2)

j

c=

c

j.

j

c=

c

j.(B3)

j (

c

: ) = (

j

c) : .

j (

c

: ) = (

j

c) : .(B4)

j (

j

c) =

j.

j (

j

c) =

j.(B5)

j (

c

: ) = (

j

c)

(

j

: ).

j (

c

: ) = (

j

c)

(

j

:),(B6)

j

O=

j.

j

1 =

j.(B7)

j 1G

j=

1 .

j 1G

j=

O.Vom demonstra prima egalitate din (B1):

j

j=

jdef

j j=

jegal. claselor j j jdef.(j j) j este o tautologie,ceea ce este adevarat, conform primei tautologii (P1) din sistemul /1 de tautologii.Restul proprietat ilor se demonstreaza folosind, similar, restul tautologiilor din/1. 2Dacan algebra Boole 1 consideram submult imea 12 =

O.

1 , atunci struc-tura(12..

. 1G.

O.

1 )este osubalgebra aalgebreiBoole1,deciestelarandul eioalgebra Boole, sianume o algebra Boole cu doua elemente (deci izomorfa cu algebra Boole canonica,12).Daca facem asocierile:

O-11o1,

1 -T1l1, -O1, -1, 1G -OT, atunci obt inem algebra Boole cu doua elemente,(1

2 = 11o1. T1l1. O1. 1. OT. 11o1. T1l1).care este implementata n limbajul PASCAL prin tipul de date BOOLEAN.Observat ii1.2.161) Am facut o prezentare semantica, neformalizata, a calculului propozit iilor.2)Oricelimbaesteconstituitadintr-unvocabular, ogramaticasi totalitateafrazelor posibile ale limbii, construite pe baza vocabularului, cu respectarea regulilorgramaticale.Prin analogie, vorbim de limbajul calculului propozit iilor, al carui vocabular esteformatdinelementelemult imii 10, dinconectoriilogici(. . . . ) sidinparantezele rotunde stanga si dreapta, (, ), gramatica ind data de regulile (R1) -(R3), iar rolul frazelor este jucat de propozit iile din1.3) Semnul nu face parte din limbajul calculului propozit iilor, iar armat iilede forma: j c,j (c :) sunt armat ii despre limbajul calculului propozit iilor;spunem ca aceste armat ii fac parte din meta-limbajul calculului propozit iilor.22CHAPTER1. CALCULULPROPOZIT IILOR(PREZ.NEFORMALIZATA)Armatiiledeforma: dacaj catunci j c, dacaj j

si c c

,atunci (jc) (j

c

) sunt armat ii despre metalimbajul calculului propozit iilor;spunem ca ele fac parte meta-meta-limbajul calculului propozit iilor; deci, este gresitsa notam cuvintele daca ... atunci cu semnul din limbaj.Chapter2Calcululpredicatelor(Prezentareneformalizata)Calculul predicatelor este o extensie a calculului propozit iilor. In calculul predi-catelor (logica predicatelor) se studiaza, n afara propozit iilor, predicatele (= funct iipropozit ionale = propozit ii variabile = propozit ii deschise).2.1 PredicateleDenit ie2.1.1Predicatul este enunt ul cu sens care are printre subiectele sale celput in unul care este nedeterminat. Un subiect nedeterminat se numeste variabilalibera.Predicatele se noteaza astfel:-cu1(r), dacaesteunpredicatunar(monadic)(=cuunlocliber); restevariabila libera.- cu1(r. n), dacaestebinar(=cu2locuri libere), cu1(r. n. .), dacaesteternar(= cu 3 locuri libere), ..., cu1(r1. r2. . . . . rn), daca este n-ar (= cun locurilibere); dacaunpredicatnuestemonadic, sezicecaestepoliadic. r1. r2. . . . . rnsunt variabile libere.Exemple2.1.21) Enunt urile Socrate este muritor, Platon este muritor suntpropozit ii, adevarate, iar enunt ul r este muritor este un predicat unar, pe care-lvom nota cu muritor(r) sau cu1(r).2) Enunt urile 3 < 5, 10 < 5 sunt propozit ii, prima adevarata, a doua falsa,iar enunt ul n < 5 este un predicat unar, pe care-l vom notaQ(n).3) Enunt urile 2 3, 5 1 sunt propozit ii, prima adevarata, a doua falsa,iar enunt ul r n este un predicat binar, pe care-l vom nota cu1(r. n).2324CHAPTER2. CALCULULPREDICATELOR(PREZ.NEFORMALIZATA)Observat ii2.1.31) Daca 1este un predicat care cont ine, de exemplu, trei variabile libere, atunciin funct ie de situat ie, putem pune n evident a una, doua sau toate trei variabilele,sau chiar niciuna, n care caz se scrie respectiv:1(r). 1(r. n). 1(r. n. .). 1.2) Propozit iile pot considerate cazuri particulare (limita) de predicatesianume: predicate cu 0 locuri.3)Daca ntr-unpredicat n-ar(n 1) nlocuimtoatecelenvariabilelibere(=subiectenedeterminate)cusubiectedeterminate(=obiecte), atunciobt inemopropozit ie. Deci, nlocuirea(=substitut ia, xarea)tuturorvariabilelorliberealeunui predicat este o modalitate de trecere de la predicate la propozit ii. Vom vedeac a mai exista o modalitate: cuanticarea.4) Locul variabilelor libere nu este indiferent. De exemplu, daca 1(r. n) r n, atunci1(r. n) 1(n. r).Mult imea(mult imile)deobiecte(domeniul)a(ale)unuipredicatDenit ie2.1.4Fie1(r)unpredicatunar. Vomspunecavariabilaliberariavalori nmult imea1deobiectedinuniversuldediscurslsivomnota: r 1,daca pentru orice obiect o 1, 1(o) este o propozit ie cu sens, adevarata sau falsa.Exemple2.1.5(1) Daca 1(r) r este muritor, atunci propozit ia ooc:otc este muritor aresens si este adevarata, iar propozit ia Numarul 5 este muritor nu are sens. Deci,1 este mult imea oamenilor sau mult imea animalelor.(2) DacaQ(r) n < 5, atunci propozit ia 10 < 5 are sens si este falsa, iarpropozit ia ooc:otc < 5 nu are sens. Deci,1 este N sau Q sau 1.Denit ie2.1.6Fie1(r1. r2. . . . . rn) un predicatn-ar (n1).(i)Vomspunecavariabileleliberer1. r2. . . . . rniauvalori nmult imeadeobiecte1 din universul de discursl(sau, echivalent, catuplul devariabilelibere(r1. r2. . . . . rn)iavalori nprodusulcartezian1 1 . . . 1 = 1n, generat de mult imea de obiecte1)si vom nota aceasta cu: ri 1. i = 1. n(sau, echivalent, cu (r1. r2. . . . . rn) 1n)daca pentru orice obiecteoi 1. i = 1. n(sau, echivalent, pentru orice tuplu de obiecte (o1. o2. . . . . on) 1n)avem ca 1(o1. o2. . . . . on) este o propozit ie cu sens, adevarata sau falsa. Vom spunen acest caz ca predicatul1este unisort (cu un singur sort).(ii) Vomspunecavariabilele libere r1. r2. . . . . rniauvalori respectivnmult imile de obiecte11. 12. . . . . 1ndin universul de discursl(sau, echivalent, catuplul devariabilelibere(r1. r2. . . . . rn)iavalori nprodusulcartezian 1112. . .1n =ni=11i, generat de mult imile de obiecte 11. 12. . . . . 1n)2.1. PREDICATELE 25si vom nota aceasta cu: ri 1i. i = 1. n(sau, echivalent, cu (r1. r2. . . . . rn) ni=11i)daca pentru orice obiecteoi 1i. i = 1. n(sau, echivalent, pentru orice tuplu de obiecte (o1. o2. . . . . on) ni=11i)avem ca 1(o1. o2. . . . . on) este o propozit ie cu sens, adevarata sau falsa. Vom spunen acest caz ca predicatul1este plurisort (cu mai multe sorturi).Observat ii2.1.7(1)Mult imeadeobiecte1(mult imiledeobiecte11. 12. . . . . 1n)depinde(depind) de1:1 = 1P(11 = 1P1 . . . . 1n = 1Pn).(2) Semnul din scrierea: 1(r) r este muritor nseamna ca1(r) este onotat ie pentru r este muritor.Predicatpart ialDenit ie2.1.8Fie1(r1. r2. r3. . . . . rn)unpredicat n-ar(n1). Dacaxam(precizam) variabilele r2. r3. . . . . rnntr-un mod oarecare (de exemplu, prinnlocuirealorcuobiecteleo2. o3. . . . . ondinmult imea(mult imile)deobiectea(ale)lui 1),atunci enunt ul obt inut,1(r1. o2. o3. . . . . on), este un predicat unar, cont inand doarvariabilar1, care se numeste predicatul part ial n raport cur1obt inut din1prinxarea variabilelorr2. r3. . . . . rn.Propozit iicomplexe(enunt uricomplexe)Din predicate date (sau din predicate si propozit ii) se construiesc propozit ii com-plexe cu ajutorul operatorilor propozit ionali (. . . . ) si al cuanticatorilor(. ), si anume:(1) Fie, pentru nceput, predicatele unare1(r) siQ(r).Enunt urile 1(r). 1(r) Q(r). 1(r) Q(r). 1(r) Q(r). 1(r) Q(r)seconstruiesclingvisticca ncazul propozit iilor, operatorii propozit ionaliafectand part ile predicative, nu si subiectele. Aceste enunt uri sunt de aseme-nea predicate.Enunt urile (r)1(r) si (r)1(r) se construiesc lingvistic astfel:se scrientregtextul predicatului (enunt ului)1(r) si se adauga n fat a lui textul: Oricarear r, , respectiv textul exista (cel put in un )r, astfel ncat. Deci, enunt ul(r)1(r) se citeste: Oricare ar r,1(r), iar enunt ul (r)1(r) se citeste:existar, astfel ncat1(r).Enunt urile(r)1(r) si(r)1(r)nusemaireferalaobiectulnedeterminatr, cilamult imeadeobiecte1 ncarevariabilariavalori, exprimandoproprietatealui1, si anume:Toateobiectele din1 au proprietatea1,respectiv26CHAPTER2. CALCULULPREDICATELOR(PREZ.NEFORMALIZATA)existacelput inunobiect n1 care are proprietatea1.Observat ii2.1.9(1) Cuanticatorii lucreaza asupra subiectului (subiectelor) unui enunt .(2)Princuanticareapredicatului unar 1(r), numarul locurilorliberedinenunt ul astfel obt inut s-a redus la 0. Deci, enunt urile (r)1(r) si (r)1(r)suntpropozit ii, ncarersenumestevariabilalegata. Deci, cuanticareaeste a doua modalitate de trecere de la predicate la propozit ii.(3) Cuanticatorii si nu sunt independent i (dupa cum nici si nu suntindependent i).(2)Fieacum1(r. n) si Q(r. n)douapredicatebinare(sauunulunar sicelalaltbinar).Construct iile lingvistice ale enunt urilor:1(r. n). 1(r. n) Q(r. n). 1(r. n) Q(r. n). 1(r. n) Q(r. n). 1(r. n) Q(r. n)sunt evidente. Toate aceste enunt uri sunt predicate.Construct iile lingvistice ale enunt urilor:(a) (r)1(r. n). (n)1(r. n). (r)1(r. n). (n)1(r. n),(b) (r)(n)1(r. n). (r)(n)1(r. n). (r)(n)1(r. n). (r)(n)1(r. n).(n)(r)1(r. n). (n)(r)1(r. n). (n)(r)1(r. n). (n)(r)1(r. n)suntevidente, celegrupate n(a)indpredicate, celegrupate n(b)indpropozit ii.(3) Construct iile propozit iilor complexe n cazul predicatelor ternare, . . ., n-are segeneralizeaza ntr-un mod evident.Observat ii2.1.10(1) Fie1(r1. r2. . . . . rn) un predicatn-ar (n1). Prin o cuaticare, numarullocurilor libere din predicat scade cu o unitate. Deci, enunt urile:(r1)1(r1. r2. . . . . rn). (r1)1(r1. r2. . . . . rn). (r2)1(r1. r2. . . . . rn). (r2)1(r1. r2. . . . . rn)s.a.m.d. sunt predicate (n 1)-are, enunt urile:(r1)(r2)1(r1. r2. . . . . rn).(r1)(r2)1(r1. r2. . . . . rn).(r1)(r2)1(r1. r2. . . . . rn).(r1)(r2)1(r1. r2. . . . . rn)s.a.m.d. sunt predicate (n 2)-are, s.a.m.d., iar enunt urile:(r1)(r2) . . . (rn)1(r1. r2. . . . . rn),(r1)(r2) . . . (rn)1(r1. r2. . . . . rn),..........................................................................(r1)(r2) . . . (rn)1(r1. r2. . . . . rn),s.a.m.d. sunt predicate 0-are, adica sunt propozit ii.2.1. PREDICATELE 27Variabila care apare langa un cuanticator (= aatan aria de cuprindere a unuicuanticator) disparedinpredicat,nu maiestelibera,cilegata. Evident,aceeasivariabila nu poate legata de mai multe ori ntr-un predicat.(2) Avem deci doua modalitat i de trecere de la predicate (= propozit ii deschise)la propozit ii (= propozit ii nchise), numite si modalitat i de nchidere a unui predi-cat:MOD1 - prin nlocuirea tuturor variabilelor libere cu obiecte,MOD2 - prin cuanticarea (legarea) tuturor variabilelor libere.(3) Daca1, mult imea de obiecte a unui predicat unar1(r), este nita:1 = o1. o2. . . . . on.atunci(r)1(r) (1(o1) 1(o2) . . . 1(on)).(r)1(r) (1(o1) 1(o2) . . . 1(on)).adica cuanticatorul universal coincide cu o conjunct ie, iar cuanticatorulexistent ialcoincidecuodisjunct ie.(4)Rezultatul unei cuanticari nudepindedenotat ia(numele)variabilei nraport cu care se face cuanticarea, adica, de exemplu:(r)1(r) (n)1(n) si (n)1(r. n. .) (n)1(r. n. .) (este corect),dar(r)1(r. n) (n)1(r. n) si (n)1(r. n. .) (r)1(r. r. .) (gresit).(5) In cazul unei cuanticarirepetate nu putem nlocui variabila unei cuan-ticari cu o variabila care intervine n alta cuanticare. Deci,(r)(n)1(r. n. .) (r)(n)1(r. n. .) (este corect),(r)(n)1(r. n. .) (r)(r)1(r. r. .) (este gresit).Convent iidescriere(1)Vomscrie: (r)1(r) nlocde: r1(r)si vomscrie: (r)1(r) nlocde:r1(r). Dar scrierea: ()r1(r) este gresita, ca si scrierea: ()r1(r).(2) Pentru a usura scrierea unei propozit ii complexe, vom presupune urmatoarele:(i) cuanticatorii (. ) auprioritatenfat aoperatorilor propozit ionali(leaga mai tare), ei avand aceeasi prioritate (leaga la fel de tare);(ii) operatorii propozit ionali au prioritat ile urmatoare:(I):( leaga cel mai tare),(II): ,(III): ,(IV): ,(V): ( leaga cel mai slab).28CHAPTER2. CALCULULPREDICATELOR(PREZ.NEFORMALIZATA)2.2 ValoareadeadevaraunuipredicatUnpredicat unar, 1(r), poateadevarat, fals, sauambivalent. Lafel unpredicatn-ar (n1).Denit ie2.2.1Fie1(r) un predicat unar si1 mult imea sa de obiecte.Spunemca1(r)esteadevaratdacapentruoriceo 1,propozit ia1(o)esteadevarata.Spunem ca1(r) este fals daca pentru oriceo 1, propozit ia1(o) este falsa.Spunem ca 1(r) este ambivalent daca exista o 1, astfel ncat propozit ia 1(o)este adevarata si exista/ 1, astfel ncat propozit ia1(/) este falsa.Exemple2.2.2Fie1=Nsi epredicateleunareurmatoarecareaupe1cadomeniu:(1)1(n) n 0 - este un predicat adevarat;(2)1(n) n < 0 - este un predicat fals;(3)1(n) n 5 - este un predicat ambivalent.Fie 1(r)unpredicat unaroarecare. Enunt urile(r)1(r)si (r)1(r)suntpropozit ii, a caror valoare de adevar se deneste astfel:Denit ie2.2.3(i) Propozit ia (r)1(r) este adevarata daca si numai daca predicatul 1(r) esteadevarat;propozit ia (r)1(r) este falsa daca si numai daca predicatul 1(r) estefals sau ambivalent.(ii) Propozit ia(r)1(r) esteadevaratadacasi numai dacapredicatul 1(r)esteadevaratsauambivalent; propozit ia(r)1(r)estefalsadaca sinumaidacapredicatul1(r) este fals.Fie1(r1. r2. . . . . rn) un predicatn-ar (n 1) oarecare. El poate adevarat,fals sau ambivalent, denit iile ind evidente.Exercitii(1) Fie 1(r) un predicat unar. Sa se demonstreze ca urmatoarea propozit ie estentotdeauna adevarata:/ [(r)1(r)] (r)[1(r)].Dem./ ([(r)1(r)] (r)[1(r)]) ([(r)(1(r))] [(r)1(r)]) .Sa notam cei doi termeni ai conjunct iei astfel:/1 [(r)1(r)] (r)[1(r)] (r)1(r) r)[1(r)].deoarece j j si/2 [(r)(1(r))] [(r)1(r)].2.2. VALOAREADEADEVARAUNUIPREDICAT 29/ este atunci adevarata daca si numai daca /1 este adevarata si /2 este adevarata.Sa notamj (r)1(r). Sa aratam ca propozit ia/1este adevarata:- daca propozit iaj este adevarata, atunci/1este adevarata;- dacapropozit iajestefalsa, atunci predicatul 1(r) estefals sauambivalent;rezulta ca predicatul 1(r) este adevarat sau ambivalent; deci propozit ia (r)[1(r)]este adevarata; rezulta ca/1este adevarata. Sa aratam ca propozit ia/2este adevarata:-dacapropozit iajesteadevarata, atunci predicatul 1(r)esteadevarat; atuncipredicatul 1(r) este fals; deci propozit ia (r)[1(r)] este falsa; rezulta ca propozit ia[(r)(1(r))] este adevarata si, deci,/2este adevarata;-dacapropozit iajestefalsa,atuncipropozit ia jesteadevarata sideci /2esteadevarata.Deci,/ este adevarata ntotdeauna.(2) Fie 1(r) un predicat unar oarecare. Sa se demonstreze ca predicatul urmatoreste adevarat:H(n) (r)1(r) 1(n).Dem.Conformdenit iei, predicatul H(n)esteadevaratdaca sinumaidaca, pentruorice obiecto 1H(1Heste domeniul luiH),H(o) este o propozit ie adevarata.Fie atunci o 1Hun obiect oarecare, xat, altfel arbitrar; sa aratam ca H(o) esteo propozit ie adevarata:H(o) (r)1(r) 1(o) [(r)1(r)] 1(o).Sa notamj (r)1(r); atunci- dacapropozit iajesteadevarata, atunci 1(r)esteunpredicatadevarat, deci1(o) este o propozit ie adevarata si, prin urnare,H(o) este o propozit ie adevarata;- daca propozit ia j este falsa, atunci propozit ia j este adevarata si, deci, propozit iaH(o) este adevarata.Deci, n ambele cazuri posibile, H(o) este o propozit ie adevarata. Rezulta, conform(PG), ca pentru orice obiecto 1H, propozit iaH(o) este adevarata, deci H(n)este un predicat adevarat.(3) Fiej o propozit ie siQ(r) un predicat unar oarecare. Sa se demonstreze caurmatoarea propozit ie este ntotdeauna adevarata:/ [(r)(j Q(r))] [j (r)Q(r)].Dem./ [(r)(j Q(r))] [j (r)Q(r)](r)[(j Q(r))] [j (r)Q(r)](r)[j Q(r)] [j (r)Q(r)],conform primului exercit iu, faptului ca j j si conform legilor De Morgan.30CHAPTER2. CALCULULPREDICATELOR(PREZ.NEFORMALIZATA)- Dacaj este falsa, atunci j este adevarata si deci/ este adevarata.- Dacaj este adevarata, atunci sa notam:/1 (r)[j Q(r)]. /2 [j (r)Q(r)].-dacapredicatul Q(r)esteadevarat,atuncipropozit ia(r)Q(r)esteadevarata,deci/2este adevarata; rezulta/ adevarata;- daca predicatulQ(r) este fals, atunci predicatul Q(r) este adevarat; rezulta caj Q(r) este un predicat adevarat, de unde obt inem ca /1 este adevarata, deci /este adevarata;- daca predicatul Q(r) este ambivalent,atunci predicatul Q(r) este ambivalent;rezultacaj Q(r) esteunpredicat ambivalent, deundeobt inemca/1esteadevarata, deci/ este adevarata.Deci,/ este ntotdeauna o propozit ie adevarata.Denit ie2.2.4Se numeste lege logica orice enunt complex (adica format cu ajutorul operato-rilor propozit ionali (. . . . ) si al cuanticatorilor (. ) din alte enunt uri,numiteenunt uricomponente)careareproprietateacaesteadevaratindependentde valorile de adevar ale enunt urilor componente. O lege logica care se construiestefara cuaticatori se numeste tautologie. O lege logica n construct ia careia intervinsi cuanticatorii nuareunnumespecial nliteraturadespecialitate; noi ovomnumi tautologie cuanticata.Un enunt complex care este fals, oricare ar valorile de adevar ale enunt urilorcomponente, se numeste antilogie - daca nu cont ine cuanticatorii, si antilogie cuan-ticata - daca cont ine cuanticatori.Exemple2.2.5Exempledeantilogiicuanticate1. (r)1(r) (r)[1(r)].2. (r)1(r) (r)[1(r)].Exemple2.2.6ExempledetautologiicuanticateVom grupa exemplele de tautologii cuanticate n opt grupe:(I) echivalent ele cuanticatorilor:1. [(r)1(r)] [(r)(1(r))],2. [(r)1(r)] [(r)(1(r))],3. [(r)1(r)] (r)[1(r)], (vezi exercit iul 1)4. [(r)1(r)] (r)[1(r)].(II):1. (r)1(r) (r)[1(r)].2. (r)1(r) (r)[1(r)].(III):2.2. VALOAREADEADEVARAUNUIPREDICAT 311. [(r)1(r) (r)(1(r))].2. [(r)1(r) (r)(1(r))].(IV):1. (r)1(r) 1(n), (vezi exercit iul 2)2. 1(n) (r)1(r).(V) (o consecint a a (IV)):(r)1(r) (r)1(r).(VI) Fiej o propozit ie siQ(r) un predicat unar:1. [(r)(j Q(r))] [j (r)Q(r)], Regula () (vezi exercit iul 3)2. [(r)(Q(r) j)] [(r)Q(r) j], Regula ().(VII):1. (r)[1(r) Q(r)] [(r)1(r) (r)Q(r)],2. (r)[1(r) Q(r)] [(r)1(r) (r)Q(r)],3. (r)[1(r) Q(r)] [(r)1(r) (r)Q(r)],4. (r)[1(r) Q(r)] [(r)1(r) (r)Q(r)].(VIII):1. (r)(n)1(r. n) (n)(r)1(r. n),2. (r)(n)1(r. n) (n)(r)1(r. n),3. (r)(n)1(r. n) (n)(r)1(r. n).Observat ie2.2.7Toatereguliledededuct iesuntconsecint eatreiregulifunda-mentale: modus ponens, , . Se poate arata ca pentru nevoile uneiteorii deductive ne putem rezuma doar la doua reguli: modus ponens si una dincelelalte doua.Observat ie2.2.8Semnicat iascrierilordinmatematica r0. 1(r)si r0. 1(r) este urmatoarea:r0. 1(r) (r)(r0 1(r)).r0. 1(r) (r)(r0 1(r)).In consecint a, daca le negam, obt inem respectiv:(r0. 1(r)) ((r)(r0 1(r))) (r)(r0 1(r)) (r)((r0) 1(r)) (r)(r0 1(r)) r0. 1(r).32CHAPTER2. CALCULULPREDICATELOR(PREZ.NEFORMALIZATA)(r0. 1(r)) ((r)(r0 1(r))) (r)(r0 1(r)) (r)((r0) 1(r)) (r)(r0 1(r)) r0. 1(r).Calculul predicatelor prezentat se mai numeste calculul predicatelor de ordinul I.Daca variabilele liberer. n. .. . . . din predicate sunt mult imi, atunci calculul pred-icatelor corespunzator sezicedeordinul II; dacaelesunt mult imi demult imi,calculul se zice de ordinul III s.a.m.d.Chapter3Latici3.1 Mult imi(pre)ordonateDenit ii3.1.1Fie o mult ime nevida.O relat ie binara1 pe se numeste relat iedeordine(part iala) daca sunt ver-icate urmatoarele axiome: pentru oricer. n. . ,(O1)r1r (reexivitatea),(O2) dacar1n sin1r, atuncir = n (antisimetria),(O3) dacar1n sin1., atuncir1. (tranzitivitatea).Daca1 mai verica si axioma:(O4) pentru oricer. n ,r1n saun1r (r sin sunt compatibile),atunci1 se numeste relat ie de ordine totala.Orelat iebinara1pesenumesterelat iedepreordinedacaverica(O1) si(O3).O pereche (. 1) se numeste- mult ime (part ial) ordonat a, daca1 este o relat ie de ordine (part iala) pe,-mult imetotal ordonatasaumult imeliniara(liniarordonata)saulant , daca1este o relat ie de ordine totala pe,- mult ime preordonata, daca1 este o relat ie de preordine pe.Exemple3.1.2(1) Mult imile (R. ), (Q. ), (Z. ), (N. ) sunt lant uri.(2) DacaAeste o mult ime nevida, atunci ({(A). ) este o mult ime ordonata;ea este total ordonata daca si numai dacaAeste formata dintr-un singur element.(3) DacaAeste o mult ime nevida, atunci (A. =) este o mult ime ordonata (nacest caz1 este = (r. r) [ r A).(4) Daca pe mult imea N = N`0 denim, pentru orice r. n, r _ n r [ n (reste divizibil cu n), atunci (N. _) este o mult ime ordonata, dar nu total ordonata.3334 CHAPTER3. LATICI(5)Dacapemult imeaCdenimrelat iabinara _astfel: pentruorice.1=o1 +i/1,.2 = o2 +i/2 C,.1 _ .2 (o1 o2. /1 /2).atunci (C.j:cccd) este o mult ime ordonata, dar nu total ordonata.(6)Relat iar _n r [ n, denitapeZ,esteorelat iedepreordine, carenueste relat ie de ordine.(7) Fie mult imea ot erilor dintr-o unitate militara. Pentrur. n , spunemc ar ndacagradullui restemaimicsauegalcugradullui n. Atunci(. )este o mult ime preordonata, care nu este ordonata.3.1.1 Principiuldualitat ii. DiagramaHassePrincipiuldualitat iipentrumult imi(pre)ordonateesteurmatorul:Orice enunt cu privire la mult imea (pre) ordonata (. ) ramane valabil daca pestetot n cuprinsul sau schimbam relat ia de (pre) ordine cu relat ia de (pre) ordineinversa, (n r r n, pentru orice r. n ). Structura (. ) astfel obt inutaeste tot o mult ime (pre) ordonata, numita duala lui (1. ).DiagramaHasseOrelat iebinara peomult imenitasevareprezentagracprindiagramaHasse astfel: elementele mult imii sunt reprezentate prin puncte, iar faptul ca r < n(adicar n sir = n) si nu exista.cur < .< nse reprezinta printr-o linie careleaga cele doua puncte,n ind situat mai sus car:xyDiagrama Hasse este utila pentru recunoasterea proprietat ilor relat iei binare.ExempludediagramaHasse.Daca = o. /. c. d si 1 = (o. o). (/. /). (c. c). (d. d). (o. /). (o. c). (o. d). (/. c). (/. d),atunci (. 1)esteomult imeordonata, cevareprezentatagracdediagramaHasse din Figura 3.1.Convent ie. O relat ie de (pre)ordine arbitrara pe o mult ime va notata deacum nainte prin .3.1. MULT IMI(PRE)ORDONATE 35a``

bcdFigure 3.1: Diagrama Hasse a mult imii ordonate (. 1)3.1.2 Reprezentareaunei relat ii binarepeomult imenitaprinmatricebooleanaSa observam ca oricarei mult imi nite, concrete r1. r2. . . . . rn i putem asociao singura mult ime nita, abstracta 1. 2. . . . . n, abstract ie facand de un izomor-sm, si ca oricarei mult imi nite abstracte 1. 2. . . . . ni putem asocia o innitatede mult imi nite concrete r1. r2. . . . . rn.Fie o mult ime nita = r1. r2. . . . . rn ( = 1. 2. . . . . n) si 1 o relat ie bi-nara pe. Vom asocia lui1 o matrice booleana`R = (:ij)i,j{1,2,...,n}astfel::ij ==

1. daca (ri. rj) 1 ((i. ,) 1)0. daca (ri. rj) 1 ((i. ,) 1).Se observa ca mult imea relat iilor binare pe o mult ime nita cun elemente esten corespondent a biunivoca cu mult imea matricilor booleene de ordinuln. Deci, orelat ie binara pe o mult ime nita cun elemente poate data, alternativ, printr-omatrice booleana de ordinn.De exemplu, relat ia 1, denitamai sus pe mult imea =o. /. c. d, areurmatoarea matrice booleana asociata:`R =

1 1 1 10 1 1 10 0 1 00 0 0 1

Condit iile(O1)- (O4)dinDenit iile1, vericatedeorelat iebinara1peomult ime nitacunelemente, pot reformulate echivalent pentrumatriceabooleana asociata,`R, astfel:(O

1) pentru oricei 1. 2. . . . . n,:ii = 1,(O

2)`Resteomatriceantisimetrica(pentruoricei. , 1. 2. . . . . n, :ij=1implica:ji = 0),(O

3) pentru oricei. ,. / 1. 2. . . . . n,:ij = 1 si:jk = 1 implica:ik = 1,(O

4) pentru oricei. , 1. 2. . . . . n,:ij = 1 sau:ji = 1.Exercit iu3.1.31. Sasescrieunprogrampentrudeterminareatuturorrelat iilordeordinepeo36 CHAPTER3. LATICImult ime nita.2. Se da o relat ie binara pe o mult ime nita prin matricea booleana asociata. Sa sescrie un program pentru a verica daca relat ia este de ordine, part ial a sau totala,sau este o relat ie de preordine.3.1.3 Prim(ultim)element, minorant(majorant), inmum(supremum). AxiomaluiZornFie(. ), (1. )douamult imi ordonate. Ofunct ie1: 1senumesteizotona dacar n implica1(r) 1(n), pentru oricer. n .Fie(. )omult imeordonata. Unelementn senumesteprimelementsaucel mai micelement (ultimelement saucel mai mareelement)dacan r(respectivr n) pentru oricer .Atat primul element, cat si ultimul element, al unei mult imi ordonate sunt unici(atunci cand exista). Primul element va notat de obicei cu 0, iar ultimul elementcu 1.O mult ime ordonata cu 0 si 1 se numeste marginita.Exemple3.1.4Consideram mult imile ordonate din Figura 3.2. In cazul a) existaprim si ultim element (este mult ime ordonata marginita), n cazul b) exista numaiultim element, iar n cazul c) exista numai prim element.``

``0a)x yz1

``x yz1b)``

zx y0c)Figure 3.2: Exemple de mult imi ordonate cu prim si/sau ultim elementDenit ii3.1.5Fie (. ) o mult ime part ial ordonata.FieAo submult ime a lui. Un elemento este un minorant (majorant) alluiAdacao r (respectivr o) pentru oricer A.Sau, echivalent, e (ri)iIo familie oarecare de elemente din indexata de1,1o mult ime oarecare, eventual innita (adica un element al lui I(adica o funct ie1: 1 )). Se stie ca familiei (ri)iI i corespunde submult imea ri [ i 1a lui , iar submult imii A a lui i corespunde familia particulara (r = rx)xXde3.1. MULT IMI(PRE)ORDONATE 37elemente din. Un element o este un minorant (majorant) al familiei (ri)iI,dacao ri(respectivri o), pentru oricei 1.Exemplu3.1.6Consideram mult imea ordonata ( = o. /. c. d. c. 1. ) din Figura3.3, fara prim si ultim element. Daca A = c. d, atunci mult imea minorant ilor luiAeste o. /. c, iar mult imea majorant ilor luiAeste d. c. 1.c``

`` abdefFigure 3.3: Mult ime ordonataAtat mult imea minorant ilor, cat si mult imea majorant ilor, pot vide.Denit ie3.1.7Fie (. ) o mult ime part ial ordonata.FieAosubmult imealui . Inmumullui Aestecelmaimareminorantallui Asi senoteazainf A. Atunci relat iao=inf A()estecaracterizatadeproprietat ile:(i)o este un minorant al luiA(adicao r pentru oricer A),(ii)o este cel mai mare minorant al luiA, adica, daca/ este un minorant al luiA(dac a/ r pentru oricer A), atunci/ o.Echivalent, e (ri)iIo familie oarecare de elemente din, indexata de1(1omult ime oarecare, eventual innita). Inmumul familiei (ri)iIeste cel mai mareminorantal ei si senoteazainfiI ri. Deci, unelement o esteinmumulfamiliei (ri)iIdaca verica proprietat ile:(i)o este un minorant al familiei (ri)iI(adicao ri, pentru oricei 1);(ii) o este cel mai mare minorant al familiei (ri)iI, adica daca / este un minorantal familiei (ri)iI(daca/ ripentru oricei 1), atunci/ o.Dual, avem urmatoarea denit ie a supremumului:Denit ie3.1.8Fie (. ) o mult ime part ial ordonata.FieAo submult ime a lui . Supremumul lui Aeste cel mai mic majorant allui Asi senoteazasup A. Atunci relat iao=sup A()estecaracterizatadeproprietat ile:(i)o este un majorant al luiA(adicar o pentru oricer A),(ii)o este cel mai mic majorant al luiA, adica, daca/ este un majorant al luiA(dac ar / pentru oricer A), atuncio /.38 CHAPTER3. LATICIEchivalent, e (ri)iIo familie oarecare de elemente din, indexata de1,1omult ime oarecare, eventual innita. Supremumul familiei (ri)iIeste cel mai micmajorantalei sisenoteazasupiI ri. Deci, unelemento estesupremumulfamiliei (ri)iIdaca verica proprietat ile:(i)o este un majorant al familiei (ri)iI(adicari o, pentru oricei 1);(ii)o este cel mai mic majorant al familiei (ri)iI, adica daca/ este un majorantal familiei (ri)iI(dacari / pentru oricei 1), atuncio /.Observat ii3.1.91) Deci, elementul infiI rial lui este caracterizat de:(i) infiI ri ri, pentru oricei 1si(ii) pentru orice / care verica / ri pentru orice i 1, avem / infiI ri,iar elementul dual, supiI ri, al lui este caracterizat de:(i)ri supiI ri, pentru oricei 1si(ii) pentru orice / care verica ri / pentru orice i 1, avem supiI ri /.2) Inmumul mult imii nite (familiei nite) r1. r2. . . . . rn = (ri)i{1,2,...,n}va notat inf(r1. r2. . . . . rn) sau infi=1,nri, iar supremumul ei va notat sup(r1. r2. . . . . rn)sausupi=1,nri. Daca n=2, inmumul familiei (mult imii) r. nvanotatinf(r. n), iar supremumul ei va notat sup(r. n).Fie (. ) o mult ime ordonata. Un element maximal (minimal) este un element: al lui cu proprietatea ca: o (respectivo :) implicao = :.O mult ime ordonat a poate avea mai multe elemente maximale si/sau mai multeelemente minimale.Exemple3.1.101) (1. ) nu are niciun element maximal si niciun element minimal.2)In({(A). )elementeleminimalesuntdeforma r, r A, iar Aesteelement maximal.3) Ultimul element al unei mult imi ordonate este si element maximal, iar primulelement este si element minimal. Reciproca nu este adevarata.O mult ime ordonata (. ) se numeste inductiva daca orice parte total ordonataa sa admite un majorant.Axioma lui Zorn:Orice mult ime ordonata inductiva admite un element max-imal.3.2 Latici3.2.1 LaticiOresilaticiDedekind. Echivalent alor3.2. LATICI 39Denit ie3.2.1O mult ime ordonata L = (1. ) se numeste laticeOre daca pentru orice douaelementer. n din1 exista inf(r. n) si sup(r. n).Propozit ia3.2.2Intr-o latice Ore L, urmatoarele armat ii sunt echivalente:pen-tru oricer. n 1,(i)r n,(ii) sup(r. n) = n,(iii) inf(r. n) = r.Dem.(i) (ii): Intr-adevar, presupunand car n, atunci deoarece avem sin n,conform reexivitat ii lui , rezulta ca n este majorant al r. n. Fie . un majorantoarecareal r. n, deci r .si n .. Deci n ., adicanestecel mai micmajorant al r. n, deci sup(r. n) = n.(ii) (i): Intr-adevar, sup(r. n) = n nseamna printre altele car n sin n;decir n.Similar se demonstreaza ca (i) (iii). 2Propozit ia3.2.3Fie L o latice Ore. Urmatoarele propriet at i sunt vericate:pen-tru oricer. n. . 1,(O1) inf(r. r) = r, sup(r. r) = r (idempotent a lui inf, sup)(O2) inf(r. n) = inf(n. r), sup(r. n) = sup(n. r) (comutativitatea lui inf, sup)(O3) inf(r. n. .) = inf(r. inf(n. .)) = inf(inf(r. n). .),sup(r. n. .) = sup(r. sup(n. .)) = sup(sup(r. n). .) (asociativitatea lui inf,sup)(O4) inf(r. sup(r. n)) = r, sup(r. inf(r. n)) = r (cele doua proprietat i de absorbt ie).Dem.(O1): Sa demonstram ca sup(r. r) = r. Fieo = sup(r. r); decir n si pentruorice/ 1carevericar /avemo /. Dar, r 1vericar r, conformreexivitat ii; luam/ =r;rezultao r. Deci, o =r, adica sup(r. r) =r. La felse demonstreaza ca inf(r. r) = r.(O2): Sademonstramcasup(r. n) =sup(n. r). Fie n=sup(r. n) si =sup(n. r); deci avem: r n, n n si n , r si, pentru orice.care vericar. n ., avemn . si .. Se observa can. sunt un astfel de., decin si n, de unde obt inemn = . La fel se demonstreaza ca inf(r. n) = inf(n. r).(O3) Sa demonstram ca sup(r. n. .) = sup(r. sup(n. .)). Sa notam t = sup(n. .),n = sup(r. n. .), = sup(r. t); atunci avem:(i)n. . t si pentru orice7 1 cun. . 7, avemt 7,(ii)r. n. . n si pentru orice7

1 cur. n. . 7

, avemn 7

,(iii)r. t si pentru orice7

1 cur. t 7

, avem 7

.Sa aratam can = :Din n. . t si t obt inem ca n. . ; dar avem si r . Rezulta ca r. n. . ;lu am7

= n (ii) si obt inem can .40 CHAPTER3. LATICIDinn. . n, luand7=n n(i), obt inemcat n. Daravemsi car n;deci, r. t n;luand7

=n n (iii),obt inem ca n. Astfel, n =. Restul sedemonstreaza similar. 2Denit ie3.2.4Fie L=(1. . ) structuraformatadinmult imea 1si douaoperat ii binare denite pe1. L se numeste latice Dedekind daca urmatoarele pro-prietat i (axiome) sunt vericate: pentru oricer. n. . 1,(L1)r r = r,r r = r (idempotent a lui . )(L2)r n = n r,r n = n r (comutativitatea lui . )(L3) r(n .) = (rn) ., r(n .) = (rn) .) (asociativitatea lui . )(L4)r (r n) = r,r (r n) = r (cele doua proprietat i de absorbt ie).Propozit ia3.2.5Intr-o latice Dedekind L, urmatoarele armat ii sunt echivalente:pentru oricer. n 1,(i)r n = r,(ii)r n = n.Dem. Dacar n = r, atuncir n = (r n) n(L2)= n (n r)(L4)= n. Dacar n = n, atuncir n = r (r n)(L4)= r. 2Echivalent a demonstrata ne permite sa denim urmatoarea relat ie binara pe olatice Dedekind L: pentru oricer. n 1,(3.1) r n r n = r r n = n.Vom arata acum ca cele doua denit ii, Ore si Dedekind, ale laticilor sunt echiva-lente.Teorema3.2.6(1) Fie (1. ) o latice Ore. Sa denim(L)def=(1. . ).unde pentru oricer. n 1,(3.2) r ndef=inf(r. n). r ndef=sup(r. n).Atunci structura (L) este o latice Dedekind.(1) Fie (1. . ) o latice Dedekind. Sa denim(L)def=(1. ).unde pentru oricer. n 1,(3.3) r n daca si numai daca r n = n.3.2. LATICI 41Atunci relat ia este de ordine, iar structura (L) este o latice Ore, unde pentruoricer. n 1,(3.4) inf(r. n) = r n. sup(r. n) = r n.(2) Cele doua aplicat ii, si , sunt inverse una alteia.Dem.(1): Cele douaoperat ii sunt bine denite (adicaexista r nsi r n pentruorice r. n1, conformdenit iei laticii Ore). Trebuiesademonstramcaceledouaoperat ii vericaaxiomele(L1)-(L4). Intr-adevar, r r=inf(r. r)=rsir r = sup(r. r) = r, conform (O1) din Propozit ia 3.2.3, deci (L1) este vericata.Similar, (L2)-(L4) rezulta respectiv din (O2)-(O4).(1): Trebuie sa aratam ca relat ia este reexiva, antisimetrica si tranzitiva. este reexiva,adica pentru oricer 1, r r: er 1 xat,altfel arbitrar;r rdefr r = r, ceea ce este adevarat, conform (L1). Rezulta, conform (Prin-cipiului Generalizarii),capentruoricer 1, r r. Restulsedemonstreazasimilar. Deci, (1. ) este o mult ime part ial ordonata.Trebuiesademonstramacumcapentruoricer. n 1, sup(r. n)=r n.Fie r. n 1, obiecte(elemente)xate, altfel arbitrare; pentruademonstracasup(r. n) = r n, trebuie sa aratam doua lucruri:(i)r n este majorant al r. n, adicar. n r n; ntr-adevar,r (r n)(L3)=(rr) n(L1)= rn, deci r rn, conform (3.3), si n (rn)(L2)=(rn) n(L3)=r (n n)(L1)= r n, decin r n.(ii) Fie 7 1 astfel ncat r. n 7, adica r7 = 7 si n7 = 7, conform (3.3);trebuie sa demonstram ca rn 7. Intr-adevar, (rn)7 = (rn)(r7)(L3)=r (n r) 7(L2)= r (r n) 7(L3)= (r r) (n 7)(L1)= r 7=7, decir n 7, conform (3.3).Rezulta, conformPrincipiului Generalizarii, ca pentru orice r. n 1, sup(r. n) =r n.Similar se demonstreaza ca inf(r. n) = r n.(2): Rutina. 2Observat ie3.2.7Relat ia de ordine din Teorema 3.2.6 poate denita, echivalent,prin(3.5) r n daca si numai daca r n = r.conform Propozit iei 3.2.5.42 CHAPTER3. LATICITeoremaprecedentaaratacaceledouadenit ii alelaticilorsunt echivalente. Incontinuare, vomlucrangeneral cudenit iaDedekindalaticii, pecareovomnumi pe scurt latice.Olatice(Ore) Lsenumestecompletadacaoricefamiliedeelementedin1(submult ime a lui 1, echivalent) admite inmum si supremum. Intr-o latice com-plet a L, daca (ri)iIeste o familie de elemente din1, vom nota

iIri = infiIri.iIri = supiIri.Orice latice nita este completa.Principiul dualitat ii pentrulaticirezultadinprincipiul dualitat ii pentrumult imi ordonate:Orice enunt cu privire la laticea (1. . ) ramane valabil daca peste totn cuprin-sul sau schimbam pe cu si pe cu . Structura (1. . ) astfel obt inuta estetot o latice, numita laticea duala a lui (1. . ).DiagramaHasseauneilatticiDiagrama Hasse permite o reprezentare graca a unei mult imi ordonate, si decia unei latici.3.2.2 ExempleExemple3.2.8(Exempledelaticimarginite(cu0 si1))1) Mult imea cu 2 elemente 12 = 0. 1 si mult imea cu 3 elemente 13 = 0. o. 1genereazalaticileliniare(adicatotalordonate) L2(vomvedeacaeaestealgebraBooleana) si respectiv L3din Figura 3.4.01L20aL31Figure 3.4: Laticile liniar ordonate L2 si L32) Mult imea cu 4 elemente1 = 0. o. /. 1 genereaza urmatoarele doua latici: laticea liniar ordonata (total ordonata) L4, a carei diagrama Hasse este prezen-tata n Figura 3.5;laticea L22, ordonataneliniarca ndiagramaHassedinFigura3.5(vomvedea ca ea este o algebra Booleana):3.2. LATICI 430a b1L4``

``0ab1L22Figure 3.5: Laticea liniara L4 si laticea neliniara L22sau, echivalent, cu operat iile . denite astfel:L22 0 a b 10 0 0 0 0a 0 a 0 ab 0 0 b b1 0 a b 1 0 a b 10 0 a b 1a a a 1 1b b 1 b 11 1 1 1 13) Mult imea cu 5 elemente1 = 0. o. /. c. 1 genereaza cele 5 latici din Figura3.6, prima liniar ordonata, celelalte patru ordonate neliniar.0a b c1L50``

``abc1L2,22``

``0abc1L22,2``

``0a cb1L

````

``0cba1LpentagonFigure 3.6: Laticile generate de 5 elementeExemple3.2.9(Exempledelaticinemarginite)1) Mult imea ordonata (N. ) este o latice numai cu prim element, numarul 0.2) Daca notam cu Z mult imea numerelor ntregi care sunt mai mici sau egalecu0, atunci mult imeaordonata(Z. ) esteolaticenumai cuultimelement,numarul 0.44 CHAPTER3. LATICI3) Mult imea ordonata (Z. ) este o latice fara prim si ultim element.Exemple3.2.10(Exempledemult imiordonatecarenusuntlatici).Mult imile 160,1, 151si 150, ordonate ca n diagramele Hasse din Figura 3.7, nusunt latici, pentru ca nu exista infc. d si sup(o. /). 160,1este o mult ime ordonatamarginita, 151esteomult imenumai cuprimelement, iar 150esteomult imeordonata numai cu prim element.``

````

``0abcd1160,1

````

``abcd1151``

```` 0abcd150Figure 3.7: Mult imi ordonate care nu sunt laticiPropozit ia3.2.11Orice latice nita are 0 si 1 (adica este marginita).Existamult imiordonatenitecaresuntmarginite,darnusuntlatici. De ex-emplu, mult imea ordonata160,1din Figura 3.7.3.2.3 Laticidistributive. LaticimarginitecomplementateObservat ii3.2.12Daca L = (1. . ) este o latice, atunci pentru orice r. n. o. / 1 avem:(i)r n r. r n n sir r n. n r n.(ii)r n implicar o n o sir o n o,(iii)r n,o / implicar o n / sir o n o.Propozit ia3.2.13Intr-o latice L cu 0 si 1 urmatoarele armat ii sunt echivalente,pentru oricer 1:(1)r 0 = 0,(2)r 0 = rsi, dual, urmatoarele armat ii sunt echivalente, pentru oricer 1:(1)r 1 = 1,(2)r 1 = r.3.2. LATICI 45Dem. Intr-adevar, (1)si (2)suntechivalentecu0 r, iar(1)si (2)suntechivalente cur 1, pentru oricer 1. 2Notat ie. Conformasociativitat ii operat iilor . dintr-olatice, vomputeanota:n

i=1ri = r1 r2. . . rn = r1 (r2 . . . (rn1 rn) . . .) = inf(r1. . . . . rn).ni=1ri = r1 r2. . . rn = r1 (r2 . . . (rn1 rn) . . .) = sup(r1. . . . . rn).Propozit ia3.2.14Intr-o latice L, urmatoarele armat ii sunt echivalente:(i)r (n .) = (r n) (r .), pentru oricer. n. . 1,(ii)r (n .) = (r n) (r .), pentru oricer. n. . 1,(iii) (r n) . r (n .), pentru oricer. n. . 1.Dem.(i) = (ii):(o /) (o c)(i)=[(o /) o] [(o /) c](L2)= [o (o /)] [(o /) c](L4)=o[(o/) c](L2)= o[c(o/)](i)=o[(co) (c/)](L3)=[o(co)] (c/)(L2)=[o (o c)] (c /)(L4)= o (c /)(L2)= o (/ c).(ii) = (iii):Deoarece. r ., rezulta (r n) . (r n) (r .)(ii)=r (n .).(iii) = (i): Sa demonstram mai ntai ca:(3.6) o (/ c) (o /) (o c).Pe de o parte, avem ca:(3.7) (o /) (o c)(L2)=(o /) (c o)(iii)[(o /) c] o.Pe de alta parte, din (o /) c(L2)= c (/ o)(iii)(c /) o rezulta ca:[(o /) c] o [(c /) o] o(L3)=(c /) (o o)(L1)=(c /) o(L2)= o (/ c).adica avem:(3.8) [(o /) c] o o (/ c).Din (3.2.2) si (3.8) rezulta (3.6). Sa demonstram acum ca:(3.9) o (/ c) (o /) (o c).46 CHAPTER3. LATICIDeoarece o / / si o c c, rezulta ca (o /) (o c) / c si de aici obt inemca:(3.10) o [(o /) (o c)] o (/ c).Pe de alta parte, deoarece o/ o si oc o, rezulta ca (o/)(oc) oo(L1)= osi de aici obt inem ca:(3.11) o [(o /) (o c)] = (o /) (o c).Din (3.10) si (3.11) rezulta (3.9). 2Denit ie3.2.15Olatice Lestedistributivadacaunadincondit iileechivalente(i) - (iii) din Propozit ia 3.2.14 are loc.Exemple3.2.16(Exempledelaticidistributive)(1) Orice lant (1. ) este o latice distributiva, n care:r n =

r. dacar nn. dacan rsi r n =

n. dacar nr. dacan r.(2) DacaAeste o mult ime, atunci ({(A). ) este o latice marginita, distribu-tiva.(3)Fienunnumarnatural, n 2, si 1nmult imeadivizorilornaturaliailuin. Denim o relat ie binara _ pe1nastfel: r _ n r [ n (r divide pen). Atunci(1n. _) este o latice marginita (cu prim element 1 si ultim element n), distributiva,n care:r n = (r. n) (cel mai mare divizor comun al luir sin),r n = [r. n] (cel mai mic multiplu comun al luir sin).(4) (Z. ) este o latice distributiva, fara prim si ultim element.(5)Laticeamarginita L22dinFigura3.5 silaticilemarginitedinFigura3.8sunt distributive.Denit ie3.2.17(i) Fie L o latice marginita. Un elemento 1 se numeste complementat dacaexista cel put in un element/ 1, numit complementul luio, astfel ncato / = 0sio / = 1.(ii) O latice marginita este complementata daca orice element al sau este com-plementat (admite un complement).Lema3.2.18Intr-olaticemarginita, distributiva, oriceelement poateaveacelmult uncomplement (altfel spus, complementul unui element, dacaexista, esteunic).Dem. Fieo 1 si sa presupunem ca are doi complement i,/ sic, adica:o / = 0. o / = 1 sio c = 0. o c = 1.3.2. LATICI 47``

``0dabc1L2,22,2````` `

```` ``

L8Figure 3.8: Latici distributiveAtunci / =/ 1 =/ (o c) = (/ o) (/ c) = 0 (/ c) =/ c, si analog,c = c /, deci/ = c. 2Intr-o latice distributiva cu 0 si 1, vom nota cuosau cu o complementul luio, atunci cand exista.Exemple3.2.19(Exempledelaticimarginitecarenusuntdistributive)(1) Consideram laticea marginita pentagon Lpentagon din Figura 3.6. Se observac ao si/ sunt complement ii luic, deci laticea nu este distributiva, conform Lemei3.2.18.(2) Consideram laticea marginita diamant L

din Figura 3.6. Se observa ca:o,/ sunt complement ii luic,o,c sunt complement ii lui/,/,c sunt complement ii luio,deci laticea nu este distributiva, conform Lemei 3.2.18.Propozit ia3.2.20Oricelaticecarecont inelaticilepentagon sidiamantcasub-latici nu este distributiva.Fie Lolaticemarginita, distributiva, si eC(1)mult imeaelementelorsalecomplementate. Evident, 0. 1 C(1).Propozit ia3.2.21Dacao. / C(1), atuncio /. o / C(1) si:(o /) = o /. (o /) = o /.Dem. Pentru a demonstra prima egalitate, este sucient sa demonstram ca:(o /) (o /) = 0. (o /) (o /) = 1.Intr-adevar, (o /) (o /) = [(o /) o] [(o /) /] = 0 0 = 0 si(o /) (o /) = [o (o /)] [/ (o /)] = 1 1 = 1.A doua egalitate se demonstreaza similar. 248 CHAPTER3. LATICIDenit ie3.2.22Fie Lsi L

doualatici marginite. Ofunct ie 1 : 1 1

senumestemorsmdelaticimarginitedacaurmatoareleproprietat isuntvericate:pentru oricer. n 1,(a)1(r n) = 1(r) 1(n),(b)1(r n) = 1(r) 1(n),(c)1(0) = 0,1(1) = 1.Vom nota cu Ld(0,1) categoria laticilor distributive marginite si a morsmelorde astfel de latici.Observat ie3.2.23Orice morsm din Ld(0,1) este o funct ie izotona:pentru oricer. n 1,r n r n = r 1(r) 1(n) = 1(r) 1(r) 1(n).Un morsm de forma1: 1 1 se numeste endomorsmal lui L.Un morsm din Ld(0,1) se numeste izomorsm daca este o funct ie bijectiva.Un izomorsm de forma1: 1 1 se numeste automorsm al lui L.Exemplu3.2.24(Exemplu de automorsm) Fie laticea marginita L = L2,22,2din Figura 3.8. Ea are doua automorsme,11 si12: 11este morsmul identic 1L,iar12este dat de: 12(0) = 0,12(d) = d,12(o) = /,12(/) = o,12(c) = c,12(1) = 1.Argumentul are la baza observat ia ca daca este o latice distributiva cu 0 si 1 si1: este un automorsm, atunci pentru oricer. n ,r < n daca si numaidac a1(r) < 1(n).Exercit iu3.2.25Sa se determine toate endomorsmele pentru laticea din exem-plul precedent.Chapter4AlgebreBooleTeoriaalgebrelorBooles-anascutcaurmareadescopeririianalogiei perfectecareexista ntrelegilelogicii si anumitereguli alecalculului algebric. Aceastadescoperire este unanim atribuita lui George Boole (An investigation into the lawsof thought, 1854).Dintrematematicienii careauaduscontributii mari ladezvoltareateoriei al-gebrelor Boole trebuie mentionati: M.H. Stone, pentrucelebrasateoremadereprezentare (1936) si pentru teoria dualitatii algebrelor Boole (1937) si A. Tarski,care a obtinut rezultate remarcabile atat pe linia algebrica a acestui domeniu, catmai ales pe linia legaturilor sale cu logica.Algebrele Boole constituie reectarea algebrica a calculului propozit iilor,indmodele algebrice ale calculului propozit iilor. Algebrele Boole monadice si poliadicesunt modele algebrice ale calculului predicatelor.Astazi, teoria algebrelor Boole se prezinta ca un capitol important al algebrei, desine statator, care are puternice conexiuni cu logica si care are aplicat ii n analiza,topologie, calcululprobabilitatiloretc., celemaispectaculoaseaplicat iiind nsan domeniul calculatoarelor electronice, deci n informatica.4.1 AlgebreBoole: denit ie,exemple,proprietat i4.1.1 Denit iaalgebreiBooleUrmatoarea denit ie a algebrei Boole este cel mai des ntalnita.4950 CHAPTER4. ALGEBREBOOLEDenit ie4.1.1O algebra Boole este o latice distributiva, cu prim si ultim element,complementata, adica este o structuraB = (1. . .. 0. 1)care verica urmatoarele proprietat i (axiome): oricare ar r. n. . 1,(B1)r r = r. r r = r (idempotent a lui . ),(B2)r n = n r. r n = n r (comutativitatea lui . ),(B3)r (n .) = (r n) .. r (n .) = (r n) .(asociativitatealui. ),(B4)r (r n) = r. r (r n) = r (absorbt ia),(B5) r(n.) = (rn)(r.). r(n.) = (rn)(r.) (distributivitatealui fat a de si invers),(B6)r 0 = r. r 1 = r (adica 0 r 1),(B7)r r = 1. r r = 0.Observat ie4.1.2Sepot dasi altedenit ii alealgebrei Boole, echivalentecuaceasta. Seobservaca ndenit iadata, setul deaxiome(B1)-(B7)corespundecelor 7 tautologii din sistemul /1 de tautologii din Capitolul Calculul propozit iilor(prezentare neformalizata); deci denit ii echivalente se obt in daca se considera ax-iomele corespunzatoare sistemelor /2- /5de tautologii, de exemplu.Alte denit ii echivalente pot gasite n [40].Exemple de denit ii echivalente (a se vedean sect iunea urmatoare demonstrat iile):Denit ie4.1.3[30], [29]O algebra Boole este o algebraB = (1. .. 1)de tip (2. 1. 0), vericand urmatoarele axiome: pentru tot ir. n. . 1,(A1)r (n r) = 1,(A2) [r (n .)] [(r n) (r .)] = 1,(A3) (n r) (r n) = 1,(A4)r n = 1 sin r = 1 implicar = n,under ndef=(r n) = r n si invers,r ndef=(r n),r ndef=(r n), 0def=1.Denit ie4.1.4[30], [29]O algebra Boole este o algebraB = (1. R.. 0)de tip (2. 1. 0), vericand urmatoarele axiome: pentru tot ir. n. . 1,(A1-R)r R(n Rr) = 0,(A2-R) [r R(n R.)] R[(r Rn) R(r R.)] = 0,(A3-R) (n Rr) R(r Rn) = 0,(A4-R)r Rn = 0 sin Rr = 0 implicar = n,4.1. ALGEBREBOOLE:DEFINIT IE,EXEMPLE,PROPRIETAT I 51under Rndef=(r n) = r n si invers,r ndef=(r Rn),r ndef=(r n), 1def=0.Exista alte denit ii ale algebrei Boole:ca algebre (1. .. 1), ca algebre (1. .. 0)etc. (see [40]).4.1.2 ExempledealgebreBooleExemplul1.Dac aAeste o mult ime, atunci ({(A). . . C. . A) este o algebra Boole.Exemplul2. (AlgebraBoolestandard)Algebra L2 = (12 = 0. 1 R. = min. = max.. 0. 1), cur = 1 r, pentrur 12, este o algebra Boole, numita algebra Boole standard.Examplul3. (Rombul)Mult imea122 = 0. o. /. 1= 1212 = 122 = 0. 1 0. 1 = (0. 0). (0. 1). (1. 0). (1. 1).organizatacalaticeca ndiagramaHassedinFigura4.1 sicunegat iadenitape prima coloana a tabelei implicat iei (r = r 0, pentru orice r), este o algebraBoole, notata L22, numita si romb.``

``0ab1Figure 4.1: Algebra Boole L22(rombul)L22 0 a b 10 1 1 1 1a b 1 b 1b a a 1 11 0 a b 1Exemplul4. (Cubul)Mult imea1222 = 0. o. /. c. d. c. 1. 1= 121212 = 132 = 0. 1 0. 1 0. 1 =(0. 0. 0). (0. 0. 1). (0. 1. 0). (0. 1. 1). (1. 0. 0). (1. 0. 1). (1. 1. 0). (1. 1. 1).organizata ca latice ca n diagrama Hasse din Figura 4.2 si cu negat ia denita can prima coloana a tabelei urmatoare a implicat iei , este o algebra Boole, notataL222, numita si cub.52 CHAPTER4. ALGEBREBOOLE``````

///////``````

``````///////

//////////////``````0adebfc1Figure 4.2: Algebra Boole L222(cubul)L222 0 a b c d e f 10 0 a b c d e f 1a a a c c e e 1 1b b c b c f 1 f 1c c c c c 1 1 1 1d d e f 1 d e f 1e e e 1 1 e e 1 1f f 1 f 1 f 1 f 11 1 1 1 1 1 1 1 1 0 a b c d e f 10 0 0 0 0 0 0 0 0a 0 a 0 a 0 a 0 ab 0 0 b b 0 0 b bc 0 a b c 0 a b cd 0 0 0 0 d d d de 0 a 0 a d e d ef 0 0 b b d d f f1 0 a b c d e f 1L222 0 a b c d e f 10 1 1 1 1 1 1 1 1a f 1 f 1 f 1 f 1b e e 1 1 e e 1 1c d e f 1 d e f 1d c c c c 1 1 1 1e b c b c f 1 f 1f a a c c e e 1 11 0 a b c d e f 1Exemplul5.Alte exemple de algebre Boole sunt L2222etc.Exemplul6.Mult imea evenimentelor asociate unei experient e aleatoare este o algebra Boole.Exemplul7.4.1. ALGEBREBOOLE:DEFINIT IE,EXEMPLE,PROPRIETAT I 53DacaAeste un spat iu topologic, atunci familia1(A) a part ilor simultan nchisesi deschise ale luiAformeaza o algebra Boole.Exemplul8.Dac a (1. . . 0. 1) este o latice distributiva cu primsi ultim element, atunci mult imeaC(1) a elementelor complementate ale lui1 este o algebra Boole.Exemplul9.OriceprodusdirectdealgebreBooleareostructuracanonicadealgebraBoole(operat iile se denesc pe componente). In particular, daca A este o mult ime nevida,atunci1X2= 1: A 0. 1 este o algebra Boole.4.1.3 Proprietat ialealgebrelorBoolePropozit ia4.1.5InoricealgebraBoole B= (1. . .. 0. 1)avemurmatoareleproprietat i: pentru oricer. n. r

. n

1,(B8) (r n) = r n. (r n) = r n(legile De Morgan),(B9) (r) = r (Principiul contradict iei) (proprietatea de dubla negat ie (DN)),(B10)r n n r,(B11)r n r n = 0,(B12)r n sir

n

implicar r

n n

sir r

n n

,(B13)r n r n = 0 r n = 1.Dem.(B8): Pentru a demonstra prima lege De Morgan, trebuie sa demonstram ca:(r n) (r n) = 1 si (r n) (r n) = 0.Intr-adevar,(r n) (r n) = (r n r) (r n n) = 1 1 = 1 si(rn)(rn) = (rrn)(nrn) = 00 = 0. La fel se demonstreazapartea a doua a lui (B8).(B9) este o alta interpretare a lui (B7).(B10): r n r n=n (r n)=n r n=n n r,conform (B9), (B8).(B11) : r n r n = n (r n) = n r n = n; rezulta car n = r (r n) = 0; decir n r n = 0.: dacar n= 0,atunci r =r 1 =r (n n) = (r n) (r n) =(r n) 0 = r n, decir n.(B12): (r n sir

n

) (r n =n sir

n

=n

) (r r

) (n n

) =(r n) (r

n

) = n n

, adicar r

n n

. La fel se demonstreaza partea adoua a lui (B12).(B13): r n r n n n = 0 r n = 0.rn = 0 n = n0 = n(rn) = (rn)(nn) = (rn)1 = rn r n.A doua parte se demonstreaza similar. 254 CHAPTER4. ALGEBREBOOLE4.1.4 Implicat iasiechivalent abooleanaDenit ie4.1.6Intr-o algebra Boole B = (1. . .. 0. 1) se deneste operat ia ,numita implicat ia boolean a, astfel:r ndef.=(r n) = r n. pentru oricer. n 1.si se deneste operat ia , numita echivalent a booleana, astfel:r ndef.=(r n) (n r). pentru oricer. n 1.Observat ie4.1.7AlgebraBoole, indostructuracare are proprietateadubleinegat ii (DN), mai areoimplicat ie, R, numitadualaimplicat iei , careesteasociata lui : pentru oricer. n 1,r Rndef.=(r n) = r n.Cele doua implicat ii sunt dependente una de cealalta:r Rn = (r n). r n = (r Rn).de aceea se foloseste doar . Avem:r = r 0 = r R1.Lema4.1.8Pentru oricer. n 1,r n = 1 (r = 1 sin = 1).Dem. Dacar n=1, atunci deoarecer n r. n, rezultaca1 r. n, decir = 1 = n. Dacar = n = 1, atunci evident,r n = 1. 2Propozit ia4.1.9r n = 1 daca si numai dacar n, pentru oricer. n 1.Dem. Dacar n = 1, adicar n = 1, atunci n =n 0 =n (r r) =(n r) (n r) = (n r) 1 =n r, adicar n. Invers, dacar n, atunci1 = r r r n = r n; rezulta car n = 1. 2Propozit ia4.1.10r n = 1 daca si numai dacar = n, pentru oricer. n 1.Dem. r n = 1 (r n) (n r) = 1 (r n = 1 sin r = 1) (r n sin r) r = n, conform Lemei 4.1.8. 24.2. ODEFINIT IEECHIVALENTAAALGEBRELORBOOLE 55Exercit ii4.1.11(1) Sasetranscrietoatetautologiiledinsistemele /2- /5detautologii nproprietat i ale algebrei booleene B si sa se demonstreze; de exemplu, (G1) devine:r (n r) = 1, pentru oricer. n 1.(2) De asemenea, sa se demonstreze urmatoarele proprietat i:pentru orice r. n. . 1,(r (r n)) (r n) = 1,(r n) ((n .) (r .)) = 1,(r n) (r n) = 1,(r n) ((n r) (r n)) = 1,r n = r n,(r n) . = r (n .).Deexemplu, adouaproprietatesedemonstreazaastfel: estesucientsademon-stramcar n(n.) (r .). Uncalcul simpluarataca: (n.) (r .) = (n .) r .= (n .) r .=n r .,deunder n = r n n r . = (n .) (r .).(3)Sasetranscriedeasemeneatautologiile(P10)-(P24) nproprietat ialeal-gebreiBoole Bsisasedemonstreze; deexemplu, (P11)devine: r r = 1sau,echivalent, conform Propozit iei 4.1.9,r = r, pentru oricer 1.4.2 Odenit ieechivalentaaalgebrelorBooleCont inutul acestei sect iuni este preluat din [30].In mod uzual, am vazut ca algebrele Boole sunt denite ca algebre (1. . .. 0. 1)de tip (2. 2. 1. 0. 0), vericand axiomele (B1) - (B7), unde: pentru oricer. n. . 1,(B1)r r = r. r r = r,(B2)r n = n r. r n = n r,(B3)r (n .) = (r n) .. r (n .) = (r n) .,(B4)r (r n) = r. r (r n) = r,(B5) (r n) . = (r .) (n .). (r n) . = (r .) (n .),(B6)r 0 = r. r 1 = r,(B7)r r = 1. r r = 0.Prezentam o denit ie echivalenta, motivata de sistemul uzual de axiome al sis-temului formal al calculului clasic al propozit iilor:(G1) ( ),(G2) ( ( )) (( ) ( )),56 CHAPTER4. ALGEBREBOOLE(G3) ( ) ( ),sianumecaalgebre(1. .. 1)detip(2. 1. 0), vericandaxiomele(A1)-(A4),unde: pentru oricer. n. . 1,(A1)r (n r) = 1,(A2) [r (n .)] [(r n) (r .)] = 1,(A3) (n r) (r n) = 1,(A4) dacar n = 1 sin r = 1, atuncir = n.Vom demonstra deci n aceasta sect iune urmatoarea teoremaTeorema4.2.1(1)Fie B=(1. . .. 0. 1)oalgebravericandaxiomele(B1)- (B7). Sadenim(B) = (1. .. 1)astfel: pentru oricer. n 1,r n = (r n) = r n.Atunci(B) verica (A1) - (A4).(1) Invers, e B = (1. .. 1) o algebra vericand axiomele (A1) - (A4). Sadenim(B) = (1. . .. 0. 1)astfel: pentru oricer. n 1,r n = (r n). r n = (r n) = r n. 0 = 1.Atunci(B) verica (B1) - (B7).(2) Aplicat iile sisunt mutual inverse.Demonstrat ia va facuta n trei subsect iuni:1. Axiomele (B1) - (B7) implica (A1) - (A4)2. Axiomele (A1) - (A4) implica (B1) - (B7)3. Aplicat iile sisunt mutual inverse.4.2.1 Axiomele(B1)-(B7)implica(A1)-(A4)In aceasta subsect iune, consideram structura de algebra Boole (1. . .. 0. 1)cu axiomele (B1) - (B7) si vom demonstra ca (A1) - (A4) au loc. Pentru aceasta,sa amintim urmatoarele proprietat i.(B8) (r n) = r n, (r n) = r n(Legile De Morgan),4.2. ODEFINIT IEECHIVALENTAAALGEBRELORBOOLE 57(B9) (r) = r.Sa denim o relat ie binara pe1astfel: pentru oricer. n 1,r n r n = r r n = n.Atunci avem(B10) este o relat ie de ordine part iala si (1. ) este o latice, unde sup(r. n) = rnsi inf(r. n) = r n.Sa denim implicat ia booleana (asociata lui ) astfel: pentru orice r. n 1,r n = (r n) = r n.Atunci avem(B11)r n r n = 1.Suntem acum n masura sa demonstram ca (A1) - (A4) sunt ndeplinite.Teorema4.2.2Axiomele (B1) - (B7) implica (A1) - (A4).Dem.(A1): r (n r) = r (n r) = (r r) n = 1.(A2): [r (n .)] [(r n) (r .)] = [r (n .)] [(r n)(r .)] =[r n .] [(r n) r .] = [r n .] [(r r .) (n r .)] =[r n .] [1 (n r .)] = [r n .] [n r .] =[r n .] [n r .] = 1.(A3) (n r) (r n) = (n r) (r n) = (n r) r n =(n r n) (r r n) = 1 1 = 1.(A4) daca r n = 1 si n r = 1, adica r n si n r, atunci r = n, conformantisimetriei lui . 24.2.2 Axiomele(A1)-(A4)implica(B1)-(B7)Inaceastasubsect iune, consideramstructura(1. .. 1)cuaxiomele(A1)-(A4) si vom demonstra ca (B1)-(B7) au loc. Pentru aceasta, vom demonstra maimulte proprietat i intermediare.Lema4.2.3(MP) r = 1 sir n = 1 implican = 1.Dem. r = 1 sir n = 1 implica 1 n = 1.Pe de alta parte, din (A1), avem can (1 n) = 1, prin urmaren 1 = 1.Apoi, din (A4), obt inem can = 1. 258 CHAPTER4. ALGEBREBOOLEPropozit ia4.2.4Urmatoarele propriet at i au loc, pentru oricer. n. . 1:(A5)r 1 = 1,(A6)r r = 1 (reexivitea),(A7) dacar n = 1 sin . = 1, atuncir . = 1 (tranzitivitatea).Dem. (A se vedea [6], [39]):(A5): Deoarecedin(A1)avem1 (r 1) = 1, rezulta, din(MP),car 1 = 1.(A6): Conform (A1),r ((r r) r) = 1;conform (A2), [r ((r r) r)] [(r (r r)) (r r)] = 1.Atunci din (MP), (r (r r)) (r r) = 1.Dar, conform(A1)dinnou, r (r r)=1. Rezulta, din(MP)dinnou, car r = 1.(A7): Fier n = 1 sin . = 1.Deoarecen . = 1, rezulta, conform (A5), car (n .) = 1.Dar, conform (A2), [r (n .)] [(r n) (r .)] = 1.Rezulta, aplicand (MP), ca (r n) (r .) = 1.Deoarecer n = 1, rezulta, prin (MP) din nou, car . = 1. 2Denit ie4.2.5Sa denim pe1o relat ie binara astfel: pentru oricer. n 1,(4.1) r n r n = 1.Atunci din (A6), (A4) si (A7) obt inem:(A6)r r, pentru oricer 1, adica este reexiva,(A4)dacar nsi n r, atunci r=n, pentruoricer. n 1, adica esteantisimetrica,(A7)dacar nsi n ., atunci r ., pentruoricer. n. . 1, adica estetranzitiva.Observat ii4.2.61)Din(A6), (A4), (A7), rezultacarelat iabinara pe1esteorelat iedeordine part iala.2) Proprietatea (A5) spune ca:(A5)r 1, pentru oricer 1,adica 1 este cel mai mare element (ultimul element) al lui1.Propozit ia4.2.7Urmatoarele propriet at i au loc, pentru oricer. n. . 1:(A8) dacar n ., atuncir n r .,(A9)r n r,(A10)r n .n r .,4.2. ODEFINIT IEECHIVALENTAAALGEBRELORBOOLE 59(A11)n . (r n) (r .),(A12)r n (n .) (r .).(A13) dacar n, atuncin . r .,(A14)r (n .) = n (r .),(A15) dacar n, atunci. r . n.Dem. (A se vedea [6] si [39])(A8): Conform (A2), [r (n .)] [(r n) (r .)] = 1;dacar n ., adicar (n .)=1, atunciaplicand(MP),obt inem(r n) (r .) = 1, adicar n r ..(A9): rezulta direct din (A1).(A10): =: dacar n ., atunci din (A8), avemr n r .;dar din(A9),n r n; atunci din (A7), obt inemn r ..=: rezulta prin simetrie.(A11): Din (A2), avemr (n .) (r n) (r .).Pe de alta parte, din (A9), avemn . r (n .).Rezulta, aplicand (A7), can . (r n) (r .), adica (A11) are loc.(A12) rezulta din (A11), aplicand (A10).(A13): Din (A12),r n (n .) (r .). Dacar n, adicar n = 1,atunci din (A5), obt inem ca (n .) (r .) = 1, adican . r ..(A14) Din (A2), avem car (n .) (r n) (r .).Pe de alta parte, deoarece din (A9) avemn r n, rezulta, din (A13), ca avem(r n (r .) n (r .).Prin urmare,din (A7),obt inem car (n .) n (r .). Prin simetrie,obt inemdeasemeneacan (r .) r (n .). Prinurmare, conform(A4), (A14) are loc.(A15): Dacar n, adicar n = 1, atunci din (A5), avem ca. (r n) =1.Pe de alta parte, din (A2), avem ca [. (r n)] [(. r) (. n)] = 1.Prin urmare, aplicand (MP), obt inem (. r) (. n) = 1, adica. r . n. 2Propozit ia4.2.8Urmatoarele proprietat i au loc, pentru oricer. n 1:(A16)n r r n,(A17) (a)r r n, (b)r r n,(A18) (r) r,(A19)r (r),(A20) (r) = r.Dem.(A16): Urmeaza direct din (A3).(A17)(a): Din(A9), r n rsi,din(A16), n r r n; prinurmare, aplicand (A7), obt inemr r n. (A17) (b) este echivalent cu (A17)(a), prin (A10).60 CHAPTER4. ALGEBREBOOLE(A18): Din (A9) si (A16) avem:(r) (((r))) (r) r ((r)) (r) r.Prinurmare, prin(A7), obt inem(r)(r)r, careprin(A8) neda(r) (r) (r) r. Dar, prin (A6), (r) (r) = 1, prin urmare,prin (A5), obt inem (r) r = 1, adica (r) r.(A19): Din (A18), ((r)) r, adica ((r)) r = 1.Pe de alta parte, din (A3), [((r)) r] [r (r)] = 1.Prin urmare, aplicand (MP),r (r) = 1, adicar (r).(A20): Din (A18), (r) r si din (A19), r (r); prin urmare, prin (A4),(r) = r. 2Propozit ia4.2.9Urmatoarele propriet at i au loc, pentru tot ir. n 1:(A21)r (r n) n,(A22) 1 r = r.Dem.(A21): Din(A6), r n r nesteadevarata. Prinurmare, din(A10),r (r n) n.(A22): Conform (A4), trebuie sa demonstram ca:(a)r (1 r) = 1 si (b) (1 r) r = 1.Intr-adevar, (a) esteadevarataconform(A1). Pentruademonstra(b), saob-servamca, din(A21), avem1 (1 r) r, prinurmare, din(A5), avem(1 r) r = 1, adica (b) este adevarata de asemenea. 2Sa denim un nou element al lui1astfel:(4.2) 0 = 1si sa denim doua noi operat ii . astfel: pentru oricer. n 1,(4.3) r n = (r n). r n = (r n) = r n.Propozit ia4.2.10Urmatoarele proprietat i au loc, pentru tot ir. n 1:(A23)r n n r,(A24)n r = r n,(A25) 0 = 1,(A26)r nn r,(A27) 0 r,(A28)r = r 0,(A29)r r = rsau, echivalent,r r = r,(A30)r n = n r,(A31)r n = n r,4.2. ODEFINIT IEECHIVALENTAAALGEBRELORBOOLE 61(A32) (r n) r = r (condit ia implicativa),(A33)r (n .) = (r n) .,(A34)r n (r n).Dem.(A23): Din (A20) si (A16),r n = (r) (n) n r.(A24): Din(A16), n r r nsidin(A23), r n n r; prinurmare, prin (A4),n r = r n.(A25): 0 = (1) = 1, din (A20).(A26): Din (A3), (n r) (r n) = 1 si din (A23), (r n) (n r) = 1.Prin urmare, aplicand (MP), daca n r, adica n r = 1, atunci r n = 1,adicar n sidacar n, adicar n = 1, atuncin r = 1, adican r.(A27): Din (A26), (A25), 0 rr 0 r 1. Dar, din (A5),r 1 este adevarata, prin urmare 0 r.(A28): Din (A24), (A25), (A22), avemr 0 = 0 r = 1 r = r.(A29): Din(A9), avemr r r; din(A28), (A2), (A6), (A28), (A22),avemr r=r (r 0) (r r) (r 0) =1 r=r, adicar r r, conform(A7). Rezultacar r=r, prin(A4). Atuncisanlocuimr cur.(A30): Din (A20), (A24), avemr n = r (n) = n r.(A31): Din (A20), (A24), obt inemr n = (r) n = n r.(A32): Conform (A4), trebuie sa demonstram:(a)r [(r n) r] = 1 si (b) [(r n) r] r = 1.Intr-adevar, (a)rezultadin(A1). Pentruademonstra(b), ntai saobservamca(r n) r = r (r n), din (A24). Dar, prin (A17)(a), avem r r n;din (A26), (A20), avemr r n (r n) (r) (r n) r.Acum, prin(A15), obt inemr (r n) r r(A29)= r. Prinurmare,(r n) r r.(A33): (r n) . = (r n) . = . (r n) = r (. n) =r (n .), prin (A24), (A20), (A14), (A24).(A34): Din (A21), (A16), avemr (r n) n = n (r n). 2Propozit ia4.2.11Urmatoarele proprietat i au loc, pentru tot ir. n 1:(A35) (r n) = r n(legea De Morgan),(A36) (r n) = r n(legea De Morgan).Dem.(A35): (r n) = ((r n)) = r n sir n = (r) n = r n, din (A20).62 CHAPTER4. ALGEBREBOOLE(A36): (r n) = (r n) sir n = (r (n)) = (r n), din(A20). 2Suntem acum n masura sa demonstram ca (B1) - (B7) sunt ndeplinite.Teorema4.2.12Axiomele (A1) - (A4) implica (B1) - (B7).Dem.(B1): r r = r r r = r, conform (A29).r r = r (r r) = r si din (A29), (A20), (r r) = (r) = r.(B2): r n = n r r n = n n, conform (A30).r n = n r (r n) = (n r), conform (A31).(B3): r (n .) = r (n .) = r (n .).(r n) . = . (r n) = . (r n) = . (r n), din (B2), (A30).Dar,r (n .) = r (. n) = . (r n), din (A30), (A14).r (n .) = r (n .) = (r (n .)), din (A20).(rn) . = . (r n) = (. (r n)) = (r (. n)) = (r (n .)), prin (B2), (A20), (A14), (A31).(B4): r (r n) = (r n) r = (r n) r = r, din (B2), (A20), (A32).r (r n) = (r n) r = (r n) r = ((r n) r) = (r) = r, din(B2), (A32).Saobservamcadin(B1)-(B4),rezultaca(1. )esteolatice;prinurmare,r n r r n, iaro / sio

/

implicao o

/ /

,o o

/ /

.(B5): Conform (A4), trebuie sa demonstram:(a) (r .) (n .) (r n) . si (b) (r n) . (r .) (n .).Intr-adevar, pentruademonstra(a): deoarece r ..si n .., atunci(r.) (n .) . si deoarece r. r si