Algebra Logicii

21
5/25/2018 AlgebraLogicii-slidepdf.com http://slidepdf.com/reader/full/algebra-logicii 1/21 1  ALGEBRA LOGICII - LOGICA ALGEBRICA ˘  (I) GEORGE GEORGESCU  Abstract ˆ Intre logica matematica ˘ ¸ si algebr ˘ a exista ˘ o r ela¸ tie complexa ˘. Algebra logicii ¸ si logica algebric˘ a sunt doua ˘ dintre ipostazele acestei rela¸ tii. De multe ori, nu se face o distinc¸ tie ˆ ıntre algebra logicii ¸ si logica algebric ˘ a. Scopul acestui articol este de a propune o delimitare a celor doua ˘ domenii ¸ si de a discuta, din aceast˘ a perspectiva ˘, unele conexiuni dintre logica ˘ ¸ si algebr ˘ a. Pentru fiecare sistem logic ˆ ın parte, putem vorbi despre o ”logic˘ a algebric˘ a” ¸ si despr e o ”algebr˘ a a logicii”. Studierea raportului dintre ele poate explica evolu¸ tia unor  subiecte matematice ¸ si poate influen¸ ta mi¸ scarea ideilor ˆ ın domeniu. ˆ In afara unor comentarii generale, lucrarea de fa¸ t ˘ a se concentreaza ˘ asupra rela¸ tiei dintre logica algebrica ˘ ¸ si algebra logicii ˆ ın cazul sistemelor clasice (calculul propozi¸ tional ¸ si calculul cu predicate). Partea a doua a lucra ˘rii va studia unele aspecte ale algebrei logicii ¸si logicii algebrice asociate unor logici neclasice (intui¸ tionista ˘, modala ˘, temporal˘ a, multivalent˘ a). 1 INTRODUCERE Logica matematica ˘ este o disciplina ˘ ce apar¸ tine deopotriv ˘ a ¸ si Matematicii ¸ si Logicii.  Atunci cˆ and ˆ ıncepe un curs de logica ˘ matematica ˘ se pune ˆ ın mod natural ˆ ıntrebarea urma ˘toare: (A) Ce este logica matematica ˘? ˆ In acel moment nu putem r˘ aspunde deca ˆt prin formula ˘ri tip ”ditionar” (de exemplu, con- form dic¸ tionarului Larousse, logica matematica ˘ este ”teoria ¸ stiin¸ tifica ˘ a ra¸ tionamentelor, ex-  cluza ˆnd procesele psihologice ¸ si care se divide ˆ ın calculul propozi¸ tional ¸ si calculul predicatelor ”) sau prin enumerarea unor subdomenii ale logicii matematice (de exemplu, folosind clasificarea   AMS 2000). Chiar daca ˘ nu r˘ aspundem la ˆ ıntrebare putem discuta despre unele teme ale logicii  matematice ¸ si despre modul cum aceasta se raporteaz ˘ a la alte discipline. ˆ In acest context apare ˆ ıntrebarea: (B) Care este raportul dintre logica matematica ˘ ¸ si matematica ˘? ˆ In ceea ce prive¸ste ˆ ıntrebarea (B), se pot formula urma ˘toarele ˆ ıntreb˘ ari ajuta ˘toare: (b1) La ce folose¸ ste logica matematicii?  (b2) La ce folose¸ ste matematica logicii?  ˆ Incercarea de a r˘ aspunde la ˆ ıntrebarea (b1) conduce la o discu¸ tie complicata ˘ ce se finalizeaza ˘ cu r˘ aspunsuri extrem de variate. Pentru subiectul nostru este mai interesant˘ a ˆ ıntrebarea (b2). ˆ Incercarea de a contura un raspuns la (b2) trebuie pusa ˘ ˆ ın rela¸ tie cu o alt˘ a ˆ ıntrebare: (c) Ce este un sistem logic ?  ˆ Intrebarea (c) poate fi privita ˘ ¸ si ca un substitut al lui (A); ea ˆ ıngusteaza ˘ sfera lui (A) dar ne apropie de posibilitatea de a da acesteia un r ˘ aspuns. Sistemele logice provin din logica ˘ ¸ si filosofie (logica clasica ˘ [60], logica intui¸ tionista ˘ [38], logica modala ˘ [14], [22], etc.), din matematica ˘ (sistemul Zermelo-Fraenkel al teoriei mul¸ timilor), din informatic ˘ a (logica dinamica ˘, anumite sisteme de logica ˘ temporal˘ a [49]), din fizica ˘ (logica mecanicii cuantice ), etc.   Vom r˘ aspunde la ˆ ıntrebarea (c) prin teza c˘ a un sistem logic este descris de urma ˘toarele opt dimensiuni [29]: - dimensiunea sintactica ˘; 

description

Logica matematica

Transcript of Algebra Logicii

1ALGEBRA LOGICII - LOGICA ALGEBRICA

(I)

GEORGE GEORGESCU

AbstractIntre logica matematica si algebra exista o relatie complexa. Algebra logicii si logica algebrica sunt doua dintre ipostazele acestei relatii. De multe ori, nu se face o distinctientre algebra logicii si logica algebrica. Scopul acestui articol este de a propune o delimitare a celor doua domenii si de a discuta, din aceasta perspectiva, unele conexiuni dintre logicasi algebra. Pentru fiecare sistem logic n parte, putem vorbi despre o logica algebricasi despre o algebra a logicii. Studierea raportului dintre ele poate explica evolutia unor subiecte matematice si poate influenta miscarea ideilor n domeniu.In afara unor comentarii generale, lucrarea de fata se concentreaza asupra relatiei dintrelogica algebrica si algebra logicii n cazul sistemelor clasice (calculul propozitional si calculul cu predicate). Partea a doua a lucrarii va studia unele aspecte ale algebrei logicii si logicii algebrice asociate unor logici neclasice (intuitionista, modala, temporala, multivalenta).

1 INTRODUCERELogica matematica este o disciplina ce apartine deopotriva si Matematicii si Logicii.Atunci cand ncepe un curs de logica matematica se pune n mod natural ntrebarea urmatoare:(A) Ce este logica matematica?In acel moment nu putem raspunde decat prin formulari tip dictionar (de exemplu, con- form dictionarului Larousse, logica matematica este teoria stiintifica a rationamentelor, ex- cluzand procesele psihologice si care se divide n calculul propozitional si calculul predicatelor ) sau prin enumerarea unor subdomenii ale logicii matematice (de exemplu, folosind clasificarea AMS 2000). Chiar daca nu raspundem la ntrebare putem discuta despre unele teme ale logicii matematice si despre modul cum aceasta se raporteaza la alte discipline. In acest context aparentrebarea:(B) Care este raportul dintre logica matematica si matematica?In ceea ce priveste ntrebarea (B), se pot formula urmatoarele ntrebari ajutatoare: (b1) La ce foloseste logica matematicii?(b2) La ce foloseste matematica logicii?Incercarea de a raspunde la ntrebarea (b1) conduce la o discutie complicata ce se finalizeaza cu raspunsuri extrem de variate. Pentru subiectul nostru este mai interesanta ntrebarea (b2).Incercarea de a contura un raspuns la (b2) trebuie pusa n relatie cu o alta ntrebare:(c) Ce este un sistem logic ?

Intrebarea (c) poate fi privita si ca un substitut al lui (A); ea ngusteaza

sfera lui (A) dar

ne apropie de posibilitatea de a da acesteia un raspuns. Sistemele logice provin din logica si filosofie (logica clasica [60], logica intuitionista [38], logica modala [14], [22], etc.), din matematica (sistemul Zermelo-Fraenkel al teoriei multimilor), din informatica (logica dinamica, anumite sisteme de logica temporala [49]), din fizica (logica mecanicii cuantice ), etc.Vom raspunde la ntrebarea (c) prin teza ca un sistem logic este descris de urmatoarele opt dimensiuni [29]: dimensiunea sintactica;

dimensiunea semantica; dimensiunea algebrica; dimensiunea topologica; dimensiunea categoriala; dimensiunea probabilista; dimensiunea algoritmica; dimensiunea filosofica.Fiecare din aceste dimensiuni descrie ntr-un mod specific sistemul logic. Cunoasterea sistemului logic se realizeaza cu atat mai bine cu cat sunt surprinse mai multe dintre relatiile ce se pot stabilintre aceste dimensiuni. Sintaxa si semantica sunt dimensiunile principale ale unui sistem logic.In mod necesar orice descriere a sistemului logic trebuie sa nceapa cu aceste doua dimensiuni. Adaugarea unor alte dimensiuni se va face n functie de contextul n care este studiat sistemul logic. In tratarea primelor sapte dimensiuni ale unui sistem logic ne folosim de concepte si de rezultate din matematica. Instrumentarul matematic necesar(teoreme, metode, algoritmi, etc) difera de la sistem la sistem si de la dimensiune la dimensiune. Modul cum aceste teoreme, metode, algoritmi, etc. sunt folosite n studiul sistemului logic ne da un raspuns la ntrebarea (b2).

2 REPREZENTAREA TRIDIMENSIONALA LOGIC

A UNUI SISTEM

De obicei, cursurile si manualele de logica se opresc asupra primelor trei dimensiuni din lista de mai sus. In acest caz, sistemele logice sunt studiate din perspectiva unei relatii tripartite: sintaxa, semantica, algebra.

SINTAXASEMANTICA

ALGEBRA

Sintaxa unui sistem logic S are doua componente: limbajul formal al sistemului si structura logica. Limbajul sistemului este construit pornind de la o lista de simboluri primare (alfabet). Aplicarea unor reguli de combinare a simbolurilor primare conduce la obtinerea multimii expre- siilor (formule, enunturi). Expresiile reprezinta traducerea n limbajul formal a unor propozitii din limbajul natural. Structura logica a limbajului se defineste prin axiomele si prin regulile de deductie ale sistemului. Acestea permit introducerea demonstratiilor formale, a teoremelor formale (enunturi ce admit o demonstratie formala) si a deductiilor formale din ipoteze.Fie un enunt si o multime de enunturi ale lui S. Vom nota:f- : este o teorema formala a lui S; f- : se deduce formal din ipotezele .Semantica unui sistem logic S este legata de notiunea de interpretare (care difera de la unsistem la altul si chiar pentru un acelasi sistem). O interpretare atribuie enunturilor sistemului valori de adevar. Multimea valorilor de adevar are o structura algebrica si o structura de ordine; o interpretare transforma operatiile logice (conectori, cuantificatori) n operatii algebrice. Folosind interpretarile se definesc principalele notiuni semantice: modelele unei teorii, enunturile universal

adevarate si deductia semantica din ipoteze.Daca enuntul este adevarat n orice interpretare atunci spunem ca este universal adevarat (|= ).Fie un enunt si o multime de enunturi ale lui S. Atunci se deduce semantic din ipotezele ( |= ) daca este adevarat n orice model al lui .Sintaxa si semantica sunt componentele principale ale sistemului logic. Relatia dintre ele este exprimata prin proprietatea de corectitudine (orice teorema formala este un enunt universal adevarat) si prin proprietatea de completitudine (orice enunt universal adevarat este teorema formala).Semantica este lumea reala a unor structuri matematice; sintaxa este o lume virtuala ce exprima simbolic proprietatile structurilor formulate n limbaj natural. Mecanismul inferential al sintaxei traduce formal rationamentele ce se petrec la nivelul semanticii.Algebra unui sistem logic S are la baza o constructie canonica, numita algebra Lindenbaum- Tarski a lui S. Sa presupunem ca printre conectorii sistemului se numara si implicatia . Pe multimea E a enunturilor lui S se va considera urmatoarea relatie binara: daca si numai daca f- si f- .Daca n sistemul logic sunt valabile: f- (principiul identitatii) daca f- si f- atunci f- .atunci este o relatie de echivalenta pe E. In ipoteza ca relatia de echivalenta este com- patibila cu operatiile logice ale lui S, multimea cat E/ devine o structura algebrica ale carei

3operatii sunt obtinute din operatiile logice. Aceasta structura Lindenbaum-Tarski a lui S.

algebrica se numeste algebra

Notam cu clasa de echivalenta a unui enunt din S. Pe multimea cat E/ se poate defini relatia de ordine prin: daca si numai daca f- .Exista sisteme logice pentru care metoda de constructie a algebrei Lindenbaum-Tarski nu sepoate aplica (de exemplu, sistemele modale S1, S2 si S3). In [7] este prezentata o metoda foarte generala de algebrizare a sistemelor logice.

3 CE ESTE ALGEBRA LOGICII SI CE ESTE LOGICA AL- GEBRICA ?Metodele algebrice au fost introduse n logica de catre George Boole n patru scrieri (doua carti si doua articole ) publicate n jurul anului 1850 (vezi [9], [10], [11] , [12] ). Chiar titlurile acestora vorbesc despre o analiza matematica a logicii, despre un calcul al rationamentelor deductive si despre o cercetare a legilor gandirii. Ideile lui Boole au determinat n mod deci- siv dezvoltarea ulterioara a logicii si a unei parti a algebrei. Se pune ntrebarea: cercetarile lui Boole se situeaza n algebra sau n logica? Iata ce spun doi mari ganditori despre contributiile lui Boole:Augustus de Morgan : It finds the laws of thought symbolized in the forms of algebra [21]. Bertrand Russell : Pure mathematics was discovered by Boole, in a work which he called the Laws of Thought. His book was in fact concerned with formal logic and this is the same as mathematics.Contributiile lui Boole si ale urmasilor sai directi (De Morgan, Schroder, Pierce, etc.) sunt un amestec de logica si de calcul algebric. Este important de observat ca ideea separarii calculului algebric de logica se ntalneste chiar n cartea lui Boole din 1854; autorul vorbeste chiar de o

algebra a logicii.Termenul Algebra logicii a fost impus de continuatorii lui Boole . O eleva a lui Peirce, Chris- tine Ladd, scrie n 1883 o lucrare intitulata On the Algebra of Logic, iar Schroder publicantre anii 1890 si 1905 monografia n trei volume Vorlesungen uber die Algebra der Logik. La Whitehead (1898) si Huntington ( 1904), prin algebra logicii se ntelege un calcul simbolic extras din logica propozitionala si din teoria naiva a multimilor (vezi [34]).Nu ntamplator prima lucrare de logica a lui Moisil se intituleaza Recherches sur lalg`ebre de la logique (vezi [55]) . Aceasta lucrare a inaugurat spiritul algebric n care, prin Moisil si elevii sai, s-a dezvoltat o mare parte din logica matematica romaneasca. Contributiile din [55] combina algebra cu logica fara a face o demarcatie ntre ele. Separarea celor doua planuri este proclamata de Moisil n mod explicit n lucrarea [56]:Au calcul des th`eses correspond ce quil convient dappeler lAlg`ebre de la Logique, en donnant`a ce terme la signification generale detude algebrique des syst`emes suggeres par le calcul des th`eses.Notiunea de algebra Boole n sensul folosit astazi apare prima data n monografia [88] (cf. [66], p.73). Constituirea teoriei algebrelor Boole ca un corp matematic consistent a fost realizatan principal de catre Stone, Birkhoff si Tarski n deceniul patru al secolului trecut. De atunci, algebrele Boole s-au dezvoltat continuu, n relatie cu alte tipuri de algebre, cu analiza, topologia, probabilitatile, informatica, etc. Dupa aparitia primelor sisteme logice formalizate (datorate n special lui Hilbert) s-a pus ntr-un mod explicit problema relatiei ntre sistemul logic si algebrele sale. Raspunsul a fost dat de Lindenbaum si Tarski prin constructia ce le poarta numele. Alge- brele asociate unui sistem logic S au ca prototip algebra Lindenbaum-Tarski a lui S. Studiul lor poate fi desprins de logica si poate constitui obiectul unui domeniu al algebrei de sine statator. Sursele dezvoltarii domeniului rezultat sunt probleme pur algebrice, proprietati ale sintaxei si semanticii lui S reflectate n plan algebric, precum si relatiile cu alte discipline din matematica, informatica, filosofie, etc. Urmatoarea tabela nfatiseaza structurile algebrice corespunzatoare unor sisteme logice foarte cunoscute.

Sistem logicStructuri algebrice

calculul propozitional clasicalgebre Boole

calculul propozitional intuitionistalgebre Heyting

calcule propozitionale modalealgebre modale

calcule propozitionale temporalealgebre temporale

logici L- ukasiewiczMV-algebre

logici Postalgebre Post

logici Moisilalgebre L- ukasiewicz-Moisil

logici BLBL-algebre

calculul cu predicate clasicalgebre cilindrice algebre poliadice

calculul cu predicate intuitionistalgebre Heyting poliadice

Si astazi ntalnim numeroase carti si lucrari asupra algebrei logicii. Termenul desemneaza deopotriva calcule logice n forma algebrica sau studiul algebrelor unui sistem. In ultimele decenii se vorbeste din ce n ce mai mult despre logica algebrica a unui sistem logic , mai ales pentru algebrele calculelor cu predicate (vezi [35] si [41]). In [7] se considera ca actul de nastere al logicii algebrice moderne este lucrarea lui Tarski [86]:Algebraic logic in the modern sense can be said to have begun with Tarskis 1935 paper on the foundation of the calculus of systems.Intrebuintarea celor doua notiuni (algebra logicii si logica algebrica) poate produce o anumita

4

confuzie. Se pune atunci problema precizarii celor doua notiuni printr-o delimitare mai exacta a domeniilor pe care le desemneaza.In algebra logicii vor intra toate proprietatile algebrelor asociate unui sistem logic S; logicaalgebrica va retine acele proprietati algebrice ce provin (direct sau indirect) din sintaxa sau semantica lui S. Pentru fiecare sistem logic, logica algebrica este o parte a algebrei logicii . Granitele logicii algebrice n interiorul algebrei logicii nu sunt definitiv trasate; rezultate pur algebrice pot avea un impact ulterior asupra sistemului logic.

4 ALGEBRA LOGICII VS LOGICA ALGEBRICA

Motivatia delimitarii ntre algebra logicii si logica algebrica ncepe cu un argument firesc: o suma de fapte matematice ce se constituie ntr-un ntreg trebuie sa poarte un nume. Existasi un argument ce tine de relatia dintre sistemul logic si algebrele sale. Cercetari din logica se prelungesc n probleme si rezultate pur algebrice; reciproc, prin proiectarea unor proprietati al- gebrice asupra sistemului logic se ajunge la o mai buna cunoastere a sa. Pentru a ilustra aceasta teza vom face apel la un episod semnificativ din istoria logicilor multivalente.Este cunoscut ca primele sisteme de logica multivalenta au fost introduse n mod independent de catre J. L- ukasiewicz si E. Post. Analiza judecatilor modale din textele aristoteliene l-a con- dus pe L- ukasiewicz n 1920 la considerarea unui sistem de logica cu trei valori [53]. Ulterior,L- ukasiewicz si elevii sai au studiat logici n-valente si chiar infinit valente [54]. In mod indepen-dent, Post a introdus n 1921 un sistem de logica n-valenta din ratiuni pur matematice [68]. Gr. C. Moisil a introdus n 1940 algebrele L- ukasiewicz 3-valente si n 1941 algebrele L- ukasiewicz 4-valente ca modele algebrice ale logicilor lukasiewicziene cu trei, respectiv cu patru valori (vezi [56], [57]). Apoi, prin generalizarea acestor structuri algebrice, Moisil a definit algebrele L- ukasiewicz n-valente. Scopul declarat al lui Moisil a fost construirea algebrei logicii core- spunzatoare logicilor lui L- ukasiewicz. A. Rose a gasit n 1956 un exemplu prin care demonstra ca structurile propuse de Moisil algebrizeaza n mod adecvat logicile lui L- ukasiewicz numai pen- tru valentele 3 si 4. Pentru valente de la 5 n sus implicatia lukasiewicziana nu mai poate definitan structurile definite de Moisil (vezi [8], p.471). Vom ncerca o explicatie a acestui fapt facand apel la raportul dintre algebra logicii si logica algebrica.In logica lui L- ukasiewicz implicatia are rolul central; toti ceilalti conectori se pot exprima n

5functie de implicatie.La Moisil, n primul plan sta structura de latice, o negatie slaba

si

operatiile de nuantare (endomorfismele chrysippiene). Endomorfismele chrysippiene asociaza unei propozitii din logica n-valenta n-1 propozitii din logica bivalenta (= nuante). Pentru alge- brele L- ukasiewicz 3-valente si 4-valente Moisil a demonstrat un principiu de determinare. In in- terpretare, principiul de determinare al lui Moisil afirma ca o propozitie din logica n-valenta este determinata de nuantele sale. Este important de observat ca n definitia algebrelor L- ukasiewicz n-valente principiul de determinare apare ca axioma 1. Distingem doua momente esentiale n actiunea lui Moisil de algebrizare a logicilor lui L- ukasiewicz:

- Pornind de la logicile lui L- ukasiewicz (3-valente si 4-valente), Moisil defineste algebrele L- ukasiewicz 3-valente si 4-valente, pentru care demonstreaza principiul de determinare.

Acesta este un act de trecere de la logica propozitii) se situeaza n logica algebrica.

la algebra, iar ceea ce rezulta

(definitii si

- Obtinerea definitiei algebrelor L- ukasiewicz n-valente prin generalizarea cazurilor n=3 si

n=4 se ncadreaza

n algebra logicii.Sursele logice sunt partial uitate (implicatia

1In definitia algebrelor L ukasiewicz-Moisil -valente, introduse de Moisil n 1969, un principiu de determinare apare din nou ca axioma (vezi [57], [8]).

lukasiewicziana) si, ntr-o masura oarecare, definitia noilor structuri este realizata prin mimetism algebric. Generalizarea s-a realizat ntr-un spatiu din afara logicii algebrice, ceea ce a produs despartirea de logica lui L- ukasiewicz.

Ulterior, prin ntoarcere de la algebra la logica, structurile create de Moisil au generat un nou tip de logici cu mai multe valori (logicile Moisil), distincte de sistemele propozitionale ale lui L- ukasiewicz (vezi [57], [8]). Intamplarile povestite mai sus ilustreaza modul subtil n care algebra logicii si logica algebrica se separa si se ntrepatrund.

5 LOGICA ALGEBRICA CLASIC

A CALCULULUI PROPOZIT IONAL

Pentru a delimita granitele logicii algebrice asociate unui sistem logic S trebuie sa raspundem la ntrebarea:Ce notiuni si proprietati ale algebrelor unui sistem logic S se afla n sfera logicii algebrice a lui S? Vom ncerca schita unui raspuns n cazul calculului propozitional clasic (L). Algebra Lindenbaum- Tarski a calculului propozitional L este o algebra Boole. Prin urmare, teoria algebrelor Boole constituie algebra logicii pentru sistemul L. Atunci ntrebarea de mai sus va capata o forma mai precisa:Ce notiuni si proprietati din teoria algebrelor Boole provin din notiuni si proprietati ale calcu- lului propozitional L?(a) In primul rand, logica algebrica a lui L va contine acele entitati si fapte algebrice ce tra- duc ntr-un mod direct entitati si fapte din sintaxa si semantica lui L. O asemenea situatie sentalneste n paralela dintre teoria multimilor consistente de enunturi (parte a sintaxei lui L)si teoria filtrelor n algebre Boole. In general, prin trecerea de la multimea enunturilor lui L la algebra Lindenbaum-Tarski se realizeaza o corespondenta ntre unele notiuni din sintaxa si unele notiuni algebrice. In tabelul de mai jos este prezentata corespondenta dintre unele notiuni legate de multimile consistente ale lui L si unele notiuni asupra filtrelor booleene (vezi [60]).

SintaxaAlgebra

Sistem deductivFiltru Boolean

Multime consistentaMultime cu proprietatea intersectiei finite

Sistem deductiv consistentFiltru propriu

Multime consistenta maximalaUltrafiltru

Corespondenta dintre multimi consistente si filtre se manifesta

nu numai la nivelul con-

ceptelor, ci si la nivelul rezultatelor din cele doua teorii. Pentru exemplificare, amintim doua propozitii asupra multimilor consistente maximale.

Propozitia 5.1. Orice multime consistenta se poate scufunda ntr-o multime consistenta max- imala.

Propozitia 5.2. Daca este o multime consistenta atunci sunt echivalente afirmatiile urmatoare:

(i) este consistenta maximala;(ii) Pentru orice enunturi , ale lui L, daca f- atunci f- sau f- ;(iii) Pentru orice enunt al lui L, f- sau f- .

Sa punem alaturi de aceste rezultate urmatoarele doua propozitii din teoria filtrelor booleene.Consideram o algebra Boole (B, , , , 0, 1) oarecare.Propozitia 5.3. Orice filtru propriu al algebrei Boole B se poate scufunda ntr-un ultrafiltru al lui B.Propozitia 5.4. Daca U este un filtru propriu al algebrei Boole B atunci sunt echivalente afirmatiile urmatoare:(i) U este ultrafiltru;(ii) U este filtru prim (daca a b U atunci a U sau b U );(iii) Pentru orice a B, avem a U sau a U .Propozitia 5.3 este varianta algebrica a Propozitiei 5.1, iar Propozitia 5.4 este varianta algebrica a Propozitiei 5.2. Mai mult, demonstratiile propozitiilor algebrice sunt traduceri fidele ale demonstratiilor proprietatilor sintactice corespunzatoare.(b) Exista situatii n care relatia dintre doua proprietati (una din logica si alta din algebra) nu este imediat vizibila. Un exemplu convingator este relatia dintre teorema de completitudine a calculului propozitional L si teorema de reprezentare a lui Stone [85]. Teorema de reprezentare a lui Stone se poate enunta n doua forme, raportate la doua exemple importante de algebreBoole: primul exemplu este algebra Boole P(X) a partilor unei multimi X, iar al doilea este algebra Boole standard L2 = {0, 1}.Teorema 5.5. Pentru orice algebra Boole B exista o multime nevida X si un morfism boolean injectiv d : B P(X).

2Teorema 5.6. Pentru orice algebra Boole B exista o multime nevida X si un morfism boolean injectiv d : B LX .

2Conform Teoremei 5.5, calculul ntr-o algebra Boole oarecare B se reduce la calculul n P(X); conform Teoremei 5.6, calculul n B se reduce la calculul n LX , deci n L2.In forma sa slaba, teorema de completitudine stabileste echivalenta dintre teoremele formale ale lui L si enunturile universal adevarate:Teorema 5.7. Pentru orice enunt al lui L:f- daca si numai daca |= .Teorema de completitudine tare stabileste echivalenta dintre deductia sintactica si deductia semantica:Teorema 5.8. Fie o multime de enunturi ale lui L si un enunt. Atunci: f- daca si numai daca |= .Teorema de reprezentare a lui Stone este contrapartea algebrica a teoremei de completitudine.Intelesul afirmatiei de mai sus trebuie privit n lumina a trei observatii: Teorema de completitudine este un rezultat de logica a carei demonstratie se bazeaza pe multimile consistente maximale; teorema de reprezentare a lui Stone este un rezultat de algebra demonstrat cu teoria ultrafiltrelor. Pasii demonstratiei teoremei lui Stone sunt o traducere fidela a etapelor ce alcatuiesc demonstratia teoremei de completitudine. Fiecare dintre cele doua rezultate (teorema de completitudine si teorema lui Stone) poate fi demonstrat pornind de la celalalt.

Atat demonstratia teoremei de completitudine, cat si cea a teoremei lui Stone invoca

axioma alegerii. In axiomatizarea Zermelo-Fraenkel a teoriei multimilor (fara

axioma

alegerii), teorema de completitudine si teorema lui Stone devin enunturi echivalente logic.

(c) Un al treilea caz l constituie acele proprietati algebrice ce nu au un corespondent n sistemul logic, dar care sunt folosite n studiul altor sisteme logice. Un asemenea exemplu este teorema Sikorski-Halmos de caracterizare a algebrelor Boole injective ([37], [82] ).O algebra Boole A se numeste injectiva daca pentru orice morfism boolean injectiv k : B Csi pentru orice morfism boolean f : B A exista un morfism boolean g : C A astfel ncaturmatoarea diagrama este comutativa:

kBC/

/f gA

Teorema 5.9. (Sikorski- Halmos). Pentru orice algebra Boole B sunt echivalente afirmatiile urmatoare:(i) B este o algebra Boole injectiva;(ii) B este o algebra Boole completa.

Teorema 5.9 este un rezultat algebric pur si nu pare a proveni dintr-o proprietate a calcu- lului propozitional clasic. Ea este nsa utilizata n mod esential n demonstratia unui rezultat important din teoria modelelor booleene: teorema de completitudine a lui Shorb ([84], [51]).Un al doilea exemplu este completarea McNeille a unei algebre Boole (vezi [37],[82]). Constructia nu se plaseaza n logica algebrica a calculului propozitional, dar apare n demonstratii din logica algebrica a calculului cu predicate clasic ([20]) si n teoria modelelor booleene ale sistemului Zermelo - Fraenkel ([46]).

6 ALGEBRE ALE CALCULULUI CU PREDICATE (CP)In perioada 1948-1952, A. Tarski mpreuna cu elevii sai L. Chin si F. Thomson au introdus algebrele cilindrice ca algebre asociate calculului cu predicate clasic (vezi [41]). Teoria lor a fost dezvoltata n special de A. Tarski, L. Henkin si J. D. Monk [41], apoi de D. Pigozzi, R. Maddux,H. Andreka, I. Nemeti, I. Sain, I. Hodkinson, R. Hirsch, T. Sayed Ahmed,etc.Algebrele poliadice (cu egalitate si fara egalitate), definite si studiate de P. R. Halmos (vezi [35]), constituie un alt tip de algebre asociate calculului cu predicate. Directia initiata de Halmos a fost continuata de B. A. Galler, A. Daigneault, H. Leblanc, J. D. Monk, S. Comer, etc.Prima problema n definirea algebrelor calculului cu predicate a fost obtinerea unei notiuni de cuantificator ntr-un context pur algebric. Cum era firesc, punctul de plecare al acestui demers a fost studierea modului cum actiunea cuantificatorior (existential si universal) se poate traducen algebra Lindenbaum-Tarski a lui CP. Pentru fiecare variabila din alfabetul lui CP, actiunea cuanticatorului existential asupra formulelor lui CP conduce la o operatie unara definita pe al- gebra Lindenbaum-Tarski. Pasul urmator a fost definirea notiunii de cuantificator existential pe o algebra Boole oarecare. Atat Tarski, cat si Halmos au ajuns la o aceeasi definitie a cuan- tificatorului existential prin trei axiome foarte simple. Dupa cum povesteste Halmos in [36], selectarea acestor axiome nu a fost imediata:The algebraic axioms for existential quantification are simple, but it took me months to absorb them into my bloodstream, to understand them intuitively and emotionally as well as merely technically.

Dupa cum am observat deja, fiecarei variabile a lui CP i este asociat un cuantificator existential algebric n algebra Lindenbaum-Tarski a lui CP. Actiunea cuantificatorului existential asupra formulelor lui CP este reflectata n algebra Lindenbaum-Tarski printr-o multime de operatii unare (cuantificatorii existentiali booleeni), legate ntre ele prin proprietati generate de struc- tura logica a lui CP.O a doua problema ce s-a pus n definirea algebrelor lui CP a fost stabilirea axiomelor care sa traduca algebric aceste proprietati. Aici Tarski si Halmos au dat raspunsuri diferite. Desi au aceeasi sursa de inspiratie (algebra Lindenbaum-Tarski a calculului cu predicate clasic), alge- brele cilindrice si algebrele poliadice sunt structuri matematice distincte.Algebrele cilindrice mbogatesc structura de algebra Boole printr-o familie de cuantificatori existentiali algebrici si printr-o multime de constante dublu indexata (reflectand predicatul de egalitate al lui CP).Halmos a procedat pas cu pas: a gasit ntai forma algebrica a cuantificatorilor, a studiat algebrele Boole cu un singur cuantificator (= algebre monadice), a introdus apoi algebrele poliadice si n final a ajuns la algebrele poliadice cu egalitate. Algebrele poliadice provin din calculul predi-catelor fara egalitate. In definitia lor este prezenta o familie de cuantificatori existentiali indexatade multimea tuturor partilor unei multimi nevide (ale carei elemente reprezinta variabilele) si de o familie de endomorfisme booleene (reprezentand substitutiile). Algebrele poliadice cu egalitate sunt obtinute prin adaugarea unei operatii ce algebrizeaza predicatul de egalitate din CP.

Cele doua

tipuri de algebre au o importanta parte comuna.Un rezultat al lui Galler [26]

stabileste echivalenta ntre algebrele cilindrice de dimensiune infinita, local finite si algebrele poliadice cu egalitate, local finite si de grad infinit. Teorema lui Galler nu este intamplatoare. Dupa cum vom vedea, algebrele cilindrice de dimensiune infinita, local finite si algebrele po- liadice local finite, de grad infinit sunt structurile ce reflecta n mod direct calculul predicatelor (cu egalitate).Notiunile de algebra cilindrica si de algebra poliadica, mai largi decat aceste structuri asociaten mod nemijlocit lui CP s-au impus din ratiuni algebrice. A fost un prim pas de trecere de la logica algebrica la algebra logicii a lui CP.Chiar daca au atacat probleme similare, o vreme cele doua teorii s-au dezvoltat pe baza unor tehnici diferite. Cercetarile actuale au unificat cele doua directii; totusi teoria algebrelor cilin- drice este preponderenta (vezi [41] , [42], [64], [79]). Mai departe, vom discuta modul n care se obtine definitia algebrelor cilindrice avand ca prototip algebra Lindenbaum-Tarski asociata unei teorii a calculului cu predicate.Sistemul formal al calculului cu predicate (CP) este construit avand ca punct de plecare struc- turile de ordinul I. O structura de ordinul I A este formata dintr-o multime nevida A (universul structurii) nzestrata cu operatii, relatii si constante.Alfabetul lui CP este compus dintr-o multime infinita V de variabile, din constantele logice ,, , , = si din simboluri de operatii, de relatii si de constante. Prin inductie se definesctermenii, formulele si enunturile lui CP. Vom numi proprietati de ordinul I acele proprietati alestructurilor ce pot fi formalizate n limbajul lui CL.Pentru simplitate vom presupune ca multimea V a variabilelor este numarabila:V = {v0, v1, ..., vn, ...}.O multime de axiome si de reguli de deductie completeaza sintaxa lui CP. Pornind de la axiomesi aplicand pas cu pas cate o regula de deductie se obtin teoremele formale. Daca este o teorema formala a lui CP atunci notam: f- .Analog se defineste notiunea de deductie formala n CP. O teorie este o multime de enunturi ale lui CP. Daca T este o teorie si o formula atunci notam:T f- : din ipotezele T se deduce formal .Pentru a obtine algebrele calculului cu predicate va trebui sa examinam algebrele Lindenbaum-

9

Tarski asociate teoriilor lui CP. Fie F (resp. E) multimea formulelor (resp. enunturilor) lui CP. Fixam o teorie T a lui CP. Pe multimea F consideram relatia binara T : T daca si numai daca T f- si T f- .T este o relatie de echivalenta pe F . Notam cu /T clasa de echivalenta a unei formule . Pe multimea cat AT = F/T introducem operatiile : /T /T = ( )/T ; /T /T = ( )/T ;(/T ) = ()/T si constantele 1 = ( )/T , 0 = ( )/T (definitia lui 1 si 0 nu depinde de enuntul ).Atunci (AT , , , , 0, 1) este o algebra Boole. Operatiile acestei algebre Boole corespund disjunctiei, conjunctiei si negatiei lui CP. Pasul urmator este algebrizarea cuantificatorilor lui CP. Pentru fiecare variabila v a lui CP definim operatiile unare :v : AT AT si v : AT AT prin v (/T ) = v/T si v (/T ) = v/T .Operatiile unare (v )vV vor traduce algebric actiunea cuantificatorului existential , iar operatiile unare (v )vV actiunea cuantificatorului universal . Se poate arata usor cav (/T ) = v (/T ) si v (/T ) = v (/T ).Avand ca model operatia v (resp. v ) vom introduce notiunea de cuantificator existential(resp. cuantificator universal ) pe o algebra Boole oarecare.Fie (B, , , , 0, 1) o algebra Boole. O operatie unara : B B (resp. : B B) se numestecuantificator existential (resp. cuantificator universal) pe B daca verifica axiomele Q1 Q3(resp. Qt Qt ):13Q1 : 0 = 0;Q2 : a a;Q3 : (a b) = a b;

Qt1 : 1 = 1;

Qt2 : a a;

Qt3 : (a b) = a b;Se verifica usor ca operatia v (resp. v ) este un cuantificator existential (resp. universal) pe AT . Pentru orice i < vom nota ci = vi.1Predicatul de egalitate = introduce formule atomice de forma vi = vj (cu vi , vj variabile ale lui CP). Aceste formule atomice definesc urmatoarele constante ale lui AT : dij = (vi = vj )/T . Atunci putem considera urmatoarea algebra : AT =< AT , , , , 0, 1, ci, dij >i,ji,j 2 reprezentabile nu este finit axiomatizabila.Conform Teoremei 7.5, clasa algebrelor cilindrice (de orice dimensiune) este axiomatizabila prin ecuatii. In cazul dimensiunii 2 putem gasi un numar finit de ecuatii ca axiome, ceea ce pentru alte dimensiuni este imposibil. In lucrarea [2], Andreka a propus un grad de complexitate al unei axiomatizari a algebrelor cilindrice reprezentabile. Sa notam, pentru un ordinal infinit: CA = clasa algebrelor cilindrice de dimensiune ;LF CA = clasa algebrelor cilindrice de dimensiune , local finite; RCA = clasa algebrelor cilindrice de dimensiune , reprezentabile; P A = clasa algebrelor poliadice de grad ;LF P A = clasa algebrelor poliadice de grad , local finite;RP P A = clasa algebrelor poliadice de grad , reprezentabile.Relatia ntre aceste clase de structuri este mai sugestiv ilustrata vizual:

CP

LF CA

CA

RCA

LF P A

P A

RP A

Prin teorema lui Galler [26], categoriile LF CA si LF P A sunt echivalente. Dupa cum am vazut, clasa LF CA a fost definita de Tarski prin raportare directa la calculul cu predicate. Trecerea de la LF CA la CA a fost primul pas spre algebra logicii lui PC. Al doilea pas spre algebra logicii lui PC a fost definirea clasei RCA. Eforturile cercetatorilor s-au ndreptat n primul rand asupra obiectelor din RCA. S-au obtinut teoreme de caracterizare ale algebrelor cilindrice reprezentabile (de exemplu, teorema lui Henkin [41]) si s-au pus n evidenta subclase remarcabile ale lui RCA ([41]). Schimbarea notiunii de reprezentare (prin fascicole [16], cuasi- grupuri [62], etc.) conduce la o redesenare a hartii din figura de mai sus.Pentru teorema de completitudine s-au dat numeroase demonstratii. Dintre ele, patru ni se par a avea o semnificatie deosebita pentru subiectul nostru. Este vorba de metoda lui Henkin [39], metoda Rasiowa- Sikorski ([71], [72]), metoda prin forcing [48] si metoda prin proprietati de consistenta [56]. Fiecare dintre aceste demonstratii pune n evidenta o metoda de a construi modele. Am vazut ca algebrizarea metodei lui Henkin a condus la demonstratii algebrice ale teoremei de reprezentare a algebrelor poliadice (local finite, de grad infinit) [35] si a algebrelor cilindrice (local finite, de dimensiune infinita)[41].Metodei Rasiowa-Sikorski i corespunde o teorema de reprezentare a algebrelor poliadice prin algebre poliadice functionale ([35], [20]).Metoda forcing a fost introdusa de P. J. Cohen pentru demonstrarea independentei axiomei alegerii si a axiomei continuului ([15]). Inspirat de conceptul lui Cohen, A. Robinson a definit n teoria modelelor forcingul sintactic ([74]) si forcingul semantic ([75]). Forcingul sintactic a fost pus ntr-o forma generala de H. J. Keisler n [48]. Teorema modelului generic , demonstrata deKeisler n [48], este o metoda puternica pentru a obtine modele ale unor teorii. In particular,prin aplicarea ei se poate obtine o demonstratie a teoremei de completitudine. In lucrarea [27] s-a definit o notiune de forcing n algebrele poliadice si a fost demonstrata o forma poliadica a teoremei modelului generic din lucrarea [48].

A patra metoda de demonstratie a teoremei de completitudine are la baza

proprietatile de

consistenta. Acestea sunt abstractizari ale familiei multimilor consistente. Rezultatul funda- mental asupra multimilor de consistenta este teorema de existenta a modelului: orice teorie ce apartine unei proprietati de consistenta admite un model (vezi, de exemplu, [56]). Aplicand teorema de existenta a modelului n cazul familiei multimilor consistente se obtine teorema de

completitudine : orice teorie consistenta

admite un model. Demonstrarea unei variante poliadice

sau cilindrice a teoremei de existenta a modelului este o problema deschisa.Am vazut cum teorema de completitudine si diversele sale demonstratii au fost subiectele de inspiratie cele mai importante pentru logica algebrica a calculului cu predicate.In principiu, cu fiecare rezultat semnificativ al logicii se poate imagina un traseu de algebrizareanalog celui din cazul teoremei de completitudine: se gaseste o formulare algebrica a rezultatu- lui, se cauta o clasa de algebre poliadice (sau cilindrice) ce permite obtinerea unei demonstratii a variantei poliadice (resp. cilindrice) si apoi subiectul trece n algebra logicii.Un asemenea rezultat semnificativ este teorema lui Craig (vezi [56]).Daca este un enunt al lui CP atunci vom nota cu CP () limbajul obtinut din CP retinand numai simbolurile de operatii, de relatii si de constante ce apar n .

Teorema 7.8. (Craig) Fie si doua enunturi ale lui CP. Daca f- atunci exista un enunt astfel ncat f- , f- si CP () CP () CP ().

Proprietatea de amalgamare (AP) este o conditie frecvent ntalnita n algebra. Prin definitie, o categorie C are proprietatea de amalgamare daca orice diagrama din C :

16

f

gA

B

B

cu f, g monomorfisme se poate completa la o diagrama comutativa n C:

f

A g

B B

uv

B

n care u, v sunt de asemenea monomorfisme.In [19], A. Daigneault a aratat ca algebrele poliadice local finite, de grad infinit verifica propri- etatea de amalgamare si ca Teorema 7.8 poate fi dedusa din acest rezultat.In lucrarea [67], D. Pigozzi a stabilit un rezultat similar pentru algebrele cilindrice local- finite. Mai mult, el a aratat ca pentru aceste structuri AP poate fi demonstrata plecand de la teorema lui Craig. Prin urmare, AP este contrapartea algebrica a teoremei de interpolare. Studiul AP pentru diverse clase de algebre cilindrice sau poliadice a devenit o problema n sine (vezi [67], [80], etc.). AP a fost pusa n relatie atat cu subiecte de algebra logicii, cat si cu subiecte de logica algebrica.Rezumand discutia de pana acum, reprezentarea este algebrizarea completitudinii iar amalga- marea este algebrizarea interpolarii de tip Craig. Si alte rezultate din teoria modelelor au fost trecute n spatiul algebrei. Dintre ele, mentionam teorema de omitere a tipurilor, teorema Keisler- Shelah de caracterizare a echivalentei elementare, partial forcingul lui Keisler, etc. In acelasi timp, algebrizarea altor teme ale teoriei modelelor (teoreme ale celor doi cardinali, mo- dele saturate, modele existential-nchise, teoria stabilitatii, etc.) ramane o problema deschisa. Tratarea teoremei de categoricitate a lui Morley n contextul algebrelor poliadice sau al alge- brelor cilindrice ar constitui un rezultat senzational pentru cercetarile din logica algebrica.S-a pus si problema definirii unor sisteme logice (mai complicate decat CP) a caror logica al- gebrica sa fie realizata de clase de algebre cilindrice (sau poliadice). Structurile algebrice ale logicii lui Keisler ([47]) sunt exact algebrele poliadice fara egalitate si de grad infinit.

8 ALGEBRIZAREA TEOREMEI DE INCOMPLETITUDINE A LUI GO DEL.Teorema de incompletitudine a lui Godel ([32]) este, fara ndoiala, cel mai celebru rezultat al logicii matematice1. Printre altele, ea afirma ca n algebra lui Peano (ca sistem axiomatic), exista un enunt astfel ncat nici , nici nu este teorema formala.Algebrizarea teoremei de incompletitudine este o problema deschisa. Solutionarea ei ar constitui un atestat maximal pentru logica algebrica. Rezolvarea acestei probleme presupune urmatorii pasi:(i) Definirea structurilor algebrice ce corespund sistemului formal al aritmeticii lui Peano;(ii) Formularea variantei algebrice a teoremei de incompletitudine ;(iii) Demonstrarea algebrica a acestei variante.Pasii (i) si (ii) ai unei asemenea demonstratii au fost realizati chiar de Halmos n [35]. In algebrele poliadice cu egalitate el a introdus notiunile de operatie, termen, predicat, constanta,1Comentarii interesante asupra acestui rezultat pot fi gasite n lucrarea [77], precum si n Revista de Filosofie, LV, 1-2, 2008

etc. Aceasta i-a permis sa defineasca algebrele Peano n contextul algebrelor poliadice cu ega- litate. Algebra Lindenbaum - Tarski a sistemului formal al aritmeticii lui Peano este o algebra Peano. Halmos a gasit si o formulare algebrica a teoremei de incompletitudine n termenii algebrelor Peano simple : Not every Peano algebra is simple (cf. [35], p. 33). Pasul III estensa incomparabil mai greu de abordat. Exista totusi unele reusite n ncercarea de a algebriza demonstratia teoremei de incompletitudine. O etapa importanta n demonstratia teoremei lui Godel este urmatoarea propozitie: orice functie recursiva este reprezentabila n aritmetica lui Peano. Versiunea algebrica a acestei propozitii a fost obtinuta de L. Leblanc n monografia[52]. In sens invers, aplicarea teoremei de incompletitudine a condus la obtinerea unor rezultateimportante n algebre cilindrice ([63], [65]). Ca exemplificare, mentionam urmatoarea teorema a lui Nemeti : algebrele cilindrice libere de dimensiune mai mare ca 3 nu sunt atomice ([63]).

9 OBSERVAT II FINALEIn acest articol este analizata relatia dintre algebra logicii si logica algebrica n contextul unei reprezentari tridimensionale a unui sistem logic: sintaxa, semantica, algebra.Partea I a lucrarii are n vedere logica clasica (calculul propozitional si calculul cu predicate). Pentru calculul propozitional, granita dintre algebra logicii si logica algebrica a capatat un statut precis. Cu totul altfel stau lucrurile n cazul calculului cu predicate. Rezultatele importante din teoria algebrelor cilindrice si poliadice se ncadreaza n logica algebrica. Zona pur algebrica a acestei teorii nu este nca constituita ca un domeniu n sine.Partea a doua a lucrarii va studia raportul dintre algebra logicii si logica algebrica pentru unele logici neclasice (intuitionista, modala, temporala, multivalenta). Pentru calculele propozitionale ale acestor logici vom ntalni o mare varietate de algebre si de teoreme de reprezentare ale acestora; pentru calculele cu predicate corespunzatoare, atat algebra logicii cat si logica algebricasunt putin dezvoltate. In toate aceste cazuri ntalnim numeroase probleme deschise, a carorrezolvare ar constitui pasi importanti n afirmarea domeniului.Sugestiile primite de la domnii profesori Sergiu Rudeanu si Dragos Vaida ne-au fost de folosn obtinerea formei finale a acestui articol. Autorul le multumeste n mod calduros.

References[1] H. Andreka, I. Nemeti, A simple, purely algebraic proof of the completeness of some first order logic, Algebra Universalis, 5, 1975, 8-15

[2] H. Andreka, Complexity of equations valid in algebras of relations, Annals of Pure and Appl.Logic, 28, 1994, 31-43

[3] H. Andreka, S. Givant, S. Mikulis, I. Nemeti, A. Simon, Notions of density that imply representability in algebraic logic, Annals of Pure and Appl. Logic, 91, 1988, 93-190

[4] H. Andreka, J. D. Monk, I. Nemeti, (eds), Algebraic Logic, North Holland, 1991

[5] C. J. Bergman, R. D. Maddux, D. L. Pigozzi, (Eds), Algebraic Logic and Universal Algebra in Computer Science, Springer, LNCS, 425, 1990

[6] G. Birkhoff, Lattice Theory (third edition), Amer. Math. Soc., Providence, 1967 [7] W. J. Blok, D. Pigozzi, Algebraizable Logics, Memoirs AMS, vol. 77, 1989, no. 398

[8] V. Boicescu, A. Filipoiu, G. Georgescu, S. Rudeanu, L- ukasiewicz- Moisil Algebras, North-Holland, 1991

[9] G. Boole, On a general method in analysis, Philosophical Transactions of the Royal Society of London, 134, 1844, 225-282

[10] G. Boole, The Mathematical Analysis of Logic, 1847

[11] G. Boole, The Calculus of Logic, Cambridge and Dublin Mathematical Journal, 3, 1848, 183-198

[12] G. Boole, An Investigation of the Laws of Thought, 1854

[13] C. C. Chang, H. J. Keisler, Model Theory, North-Holland, 1994

[14] B. Chellas, Modal Logic. An Introduction, Cambridge Univ. Press, 1980

[15] P. J. Cohen, Set Theory and the Continuous Hypothesis, W. A. Benjamin, Inc., 1966

[16] S. D. Comer, A sheaf theoretic duality theory for cylindric algebras, Trans. AMS, 169, 1985, 75-87

[17] W. Craig, Logic in Algebraic Form, North Holland, 1974

[18] A. Daigneault, J. D. Monk, Representation theory for polyadic algebras, Fund. Math., 52, 1963, 151-176

[19] A. Daigneault, On automorphisms of polyadic algebras, Trans. Amer. Math. Soc., 112, 1964, 84- 130

[20] A. Daigneault, Theorie des mod`eles en logique mathematique, Montreal, 1967

[21] A. De Morgan, On the syllogism and on the logic of relations, Transactions of the Cambridge Philosophical Society, 10, 1864, 331- 358

[22] M. Dumitru, Modalitate si Incompletitudine, Ed. Paideea, 2001

[23] M. Fitting, Intuitionistic Logic, Model Theory and Forcing, North Holland, 1969

[24] M. Fitting, E. Orlowska, (Eds), Beyond Two : Theory and Applications of Multiple - Valued Logic, Physice-Verlag, Springer, 2003

[25] J. M. Font, R. Jansana, D. L. Pigozzi, A survey of abstract algebraic logic, Studia Logica, 71, 2003, 13-97

[26] B. A. Galler, Cylindric and polyadic algebras, Proc. AMS, 8, 1957, 176-183

[27] G. Georgescu, Sur le forcing faible dans les alg`ebres polyadiques, C. R. Acad. Sci. Paris, 280, 1975, 1257- 1258

[28] G. Georgescu, Extensii ale teoriei modelelor, In: Matematica n Lumea de Azi si de Maine,Ed. Academiei, 1985, 116-123

[29] G. Georgescu, Matematica teoremelor de completitudine (I), Revista de Filosofie, LV, 1-2, 2008, 71- 84

[30] G. Georgescu, A. Iorgulescu, S. Rudeanu, Some Romanian Researches in the Algebra of Logic, In: Grigore C. Moisil si continuatorii sai, Ed. Academiei Romane, 2007, 86-132[31] K. Godel, Die Vollstandigkeit der Axiome des logish Functionenkalkuls, Monatshefte fur Mathematik und Physik, 37, 1930, 349-360[32] K. Godel, U ber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme, Monatshefte fur Mathematik und Physik, 38, 1931, 173- 198[33] K. Godel, The consistency of the axiom of choice and of the generalized continuum hypoth- esis, Princeton Univ. Press, 1940[34] J. Green, The algebra of logic: what Boole really started [35] P. R. Halmos, Algebraic Logic, Chelsea Publ. Comp., 1962[36] P. R. Halmos, An autobiography of polyadic algebras, Logic J. of IGPL, 8, no.4, 1988, 363-392[37] P. R. Halmos, Lectures on Boolean Algebras, Van Nostrand, Priceton, Toronto, London, 1963[38] A. Heyting, Intuitionism. An Introduction, North Holland, 1956[39] L. Henkin, The completeness theorem of the first-order functional calculus, J.Symb. Logic, 14, 149, 159- 166[40] L. Henkin, The discovery of my completeness proofs, Bull. Symb. Logic, 2, 1996, 127-158 [41] L. Henkin, J. D. Monk, A. Tarski, Cylindric Algebras, I, II, North-Holland, 1971, 1985 [42] L. Henkin, J. D. Monk, A. Tarski, H. Andreka, I. Nemeti, Cylindric Set Algebras, LectureNotes in Math., 883, Springer, 1981[43] D. Hilbert, W. Ackermann, Grundzugen der theoretischen Logik, Springer-Verlag, 1928 [44] R. Hirsch, I. Hodkinson, Relation Algebras by Games, Studies in Logic and Foundations ofMathematics, vol. 147, 2002[45] E. Huntington, Sets of independent postulates for the algebra of logic, Transactions AMS, 5, 1904, 288-309[46] Th. J. Jech, Lectures in Set Theory with Particular Emphasis on the Method of Forcing,Lecture Notes in Math., 217, Sprinder-Verlag, 1971[47] H. J. Keisler, A complete first- order logic with infinitary predicates, Fund. Math., 52, 1963, 177-203[48] H. J. Keisler, Forcing and the omitting types theorem, in : Studies in Model Theory, MAA Studies in Math., Buffalo, N.Y., 8, 1873, 96-133[49] F. Kroger, Temporal Logic of Programs, Springer, 1985[50] C. Ladd, On the algebra of logic, in: C.S.Peirce (ed.), Studies in Logic, Boston, Little,Brown, and Co.,1883, 17-71[51] G. Loullis, Sheaves and Boolean- valued model theory, J. Symb. Logic, 44, 1979, 153-183

[52] L. Leblanc, Representabilite et Definisabilite dans les Alg`ebres Transformationnelles et dans les Alg`ebres Polyadiques, Les Presses de LUniversite de Montreal, 1966[53] J. L- ukasiewicz, On three valued logic (n poloneza), Ruch Filozoficzny, 5, 1920 160-171 [54] J. L- ukasiewicz, A. Tarski, Untersuchungen uber den Aussagenkalkul, C. R. Seances Soc.Sci. Lettres Varsovie, Cl. III, 23, 1930, 30-50[55] Gr. C. Moisil, Recherches sur lalg`ebre de la logique, Ann. Sci. Univ. Jassy, 22, 1936, 1-118 [56] Gr. C. Moisil, Recherches sur les logiques non-chrysipiennes, Ann. Sci. Univ. Jassy, 27,1941, 431- 466[57] Gr. C. Moisil, Essais sur les logiques non- chrysipiennes, Ed. Academiei, Bucuresti, 1972 [58] Gr. C. Moisil, Sur la structure algebrique du calcul des propositions, Bull. Math. Soc.Roumaine Sci., 40, 1938, 3-8[59] J. D. Monk, Non-finitizability of classes of representable cylindric algebras, J.Symb. Logic, 34, 1969, 331-343[60] J. D. Monk, Mathematical Logic, Springer,1976[61] J. D. Monk, Omitting types algebraically, Ann. Sci. Univ. Clermont, Ser. Math., 16, 1978, 101-105[62] J. D. Monk, Connections between combinatorial theory and algebraic logic, In:Studies in Mathematics, vol. 9, Amer.Math.Soc., 1974, 58-91[63] I. Nemeti, Free algebras and decidability in algebraic logic, Ph. D. Thesis, Hungarian Academy of Sciences, 1986[64] I. Nemeti, Algebraization of quantifier logics, an introductory overview, Studia Logica, 50, 1991, 465-569[65] I. Nemeti, G. Sagi, On the equational theory of representable polyadic algebras, J.Symb.Logic, 65, 2000, 1143-1167[66] R. Padmanabhan, S. Rudeanu, Axioms for Lattices and Boolean Algebras, World Scientific, 2008[67] D. Pigozzi, Amalgamation, congruence extension, and interpolation properties in algebras,Algebra Universalis, 1, 1971, 269-349[68] E. Post, Introduction to a general theory of elementary propositions of logic, Amer. J.Math., 43, 121, 163-185[69] K. Potthoff, Representation of locally finite polyadic algebras and ultraproducts, Zeit. Math.Logik und Grund. Math., 17, 1971, 91-96.[70] H. Rasiowa, An Algebraic Approach to Non-classical Logics, North-Holland, 1974[71] H. Rasiowa, R. Sikorski, A proof of the completeness theory of Godel, Fund. Math., 37, 1950, 193-200[72] H. Rasiowa, R. Sikorski, The Mathematics of Metamathematics, Polish Scientific Publ., 1963

[73] A. Robinson, Introduction to Model Theory and to the Metamathematics of Algebra, North Holland, 1974[74] A. Robinson, Forcing in model theory, Symposia Math., vol. 5, 1970, 64-82

[75] A. Robinson, Infinite forcing in model theory, Proc. Second Scandinavian Logic Symp., (Oslo, 1970), North Holland, 1971[76] S. Rudeanu, Gr. C. Moisil, a contributor to the early development of lattice theory1, Mult.-Valued Logic, 2, 1997, 323- 328

[77] S. Rudeanu, Calculabilitate intuitiva si teorema lui Godel, Revista de Logica (Publicatie Online), No. 1, 2008[78] T. Sayed Ahmed, Reducts of L3 has Godels incompleteness, therefore the free quasi- polyadic algebras of dimension 3 are not atomic, manuscript, 2001[79] T. Sayed Ahmed, Algebraic logic, where does it stand today, Bulletin of Symb. Logic, 11, no. 4, 2005, 465- 516[80] T. Sayed Ahmed, On amalgamation of reducts of polyadic algebras, Algebra Universalis, 51, 2004, 301-359[81] E. Schroder, Vorlesungen uber die Algebra der Logik, Leipzig, Eugen Muller, 1890-1905 .Reprint: Bronx, N.Y., Chelsea Publ. Comp., 1966, 3 vols. [82] R. Sikorski, Boolean Algebras, Springer- Verlag, 1964[83] H. M. Sheffer, A set of five independent postulates for Boolean algebras, with applications to logical constants, Trans. Amer. Math. Soc., 14, 1913, 481- 488[84] A. M. Shorb, Contributions of Boolean- valued model theory, Ph. D. Thesis, Univ. of Minesota, 1969[85] M. H. Stone, The theory of representation for Boolean algebras, Trans. Amer. Math. Soc., 40, 1936, 37- 111[86] A. Tarski, Grundzuge der Systemenkalkuls. Erster Teil., Fund. Math., 25, 1935, 503- 526 [87] A. Tarski, Logic, Semantics, and Metamathematics, papers from 1923 to 1938, Trans. J. H.Woodger, 2nd edition, Ed. J. Corcoran, Hackett Pub. Comp., Indianapolis, 1883

[88] A. N. Whitehead, A Treatise on Universal Algebra, with Applications, Cambridge Univ.Press, 1898

1Semnalam si o versiune a acestui articol n limba romana: S. Rudeanu, Contributiile lui Gr. C. Moisil la dezvoltarea timpurie a teoriei laticilor n: Grigore C. Moisil si continuatorii sai(coord.: A. Iorgulescu, S. Marcus,S. Rudeanu, D. Vaida), Editura Academiei Romane, 2007