Logică şi teoria mulţimilor, partea 1

Facultatea de Matematica, Universitatea “Al. I. Cuza”Iasi

Logica si teoria multimilorde

Claudiu Volf & Ioan I. Vrabie

2015

NOTE DE CURS

CAPITOLUL 1

Elemente de logica

“Spune ıntotdeauna adevarul si

nu va trebui sa tii minte nimic.”

Mark Twain

1.1. Principiile logicii

Logica este stiinta demonstratiei, avand drept obiecte de studiu legile generalede rationament corect. Pe scurt, logica se ocupa de studiul sistematic al adevarului.Obiectele cu care ea opereaza sunt propozitiile si predicatele, iar mijloacele de lucruutilizate sunt limbajul si regulile de deductie. Mai precis, logica opereaza cu definitii,propozitii, predicate, operatori logici, cuantificatori si reguli de deductie.

Incepem prin a formula patru principii fundamentale ale logicii matematice:

• Principiul identitatii• Principiul non-contradictiei• Principiul tertului exclus• Principiul ratiunii suficiente

Conform principiului identitatii, ın cadrul oricarui proces de rationament,notiunile, propozitiile, predicatele, notatiile, etc., trebuie utilizate ıntr-o singuraacceptiune si numai una. Orice abatere de la aceasta regula este o sursa de neadevarsi confuzie. Este binecunoscuta replica “cred ca vorbim despre lucruri diferite”pe care unul dintre participantii la o discutie o da altuia atunci cand, cel putinaparent, pornind de la aceeasi premisa adevarata, ajung la concluzii contradictorii.Aceasta replica este de fapt o atentionare asupra unei posibile ıncalcari a principiu-lui identitatii, ıncalcare cunoscuta drept cea mai frecventa sursa de contradictii. Unrationament – eronat – de tipul “Cainele este mamifer. Mamifer este substantiv.Deci cainele este substantiv.” este bazat pe ıncalcarea principiului identitatii prinutilizarea termenului “mamifer” ın doua acceptiuni diferite: prima de nume denotiune si cea de-a doua de parte de vorbire. Subliniem ca acest principiu are dreptconsecinta ca un acelasi simbol, ın cadrul unui rationament, nu poate nota obiectediferite. De aici decurge regula substitutiei , care afirma ca substituirea unei variabileıntr-o expresie trebuie facuta peste tot unde apare cu unul si acelasi simbol.

Pe de alta parte, traditia gandirii corecte ne spune ca o propozitie nu poate fi siadevarata si falsa, cerinta cunoscuta sub numele de principiul non-contradictiei.

Propozitiile pot fi adevarate sau false, iar logica matematica se bazeaza pecerinta ca o a treia posibilitate nu exista. Acesta este principiul tertului exclus.

Logica pretinde justificari fundamentate si complete. Aceasta cerinta este for-mulata de principiul ratiunii suficiente: exceptand axiomele, toate afirmatiileacceptate drept adevarate se bazeaza doar pe demonstratii corecte, care folosesc

2 Capitolul 1 Elemente de logica

numai adevaruri deja cunoscute, suficient de ıntemeiate. In plus, concluziile tre-buie obtinute doar pe cale deductiva. Cu alte cuvinte, pentru a stabili faptul ca opropozitie este adevarata sau falsa trebuie sa ne sprijinim pe o argumentatie rig-uroasa, deductiva, bazata pe o “cantitate suficienta de adevar”. Aceasta revine la aspune ca logica nu accepta argumente care se bazeaza pe: propozitii false, argumentede autoritate de tipul “pentru ca asa vreau”, nici argumente care pot fi corecte, darsunt incomplete – precum cele inductive.

Aparitia ın cadrul limbajelor naturale (mai tarziu, chiar ın interiorul unor teoriimatematice) a unor propozitii ce nu respecta principiul necontradictiei, propozitiinumite fie antinomii1 – termen folosit cu precadere de filosofi – fie paradoxuri2, aimpulsionat atat logica cat si matematica spre rezolvarea cu prioritate a problemelorproprii de fundament.

Matematica este cu siguranta disciplina care, pana la un anumit punct, s-aformat, dezvoltat si formalizat pe baza logicii, ulterior observandu-se si o inversarede roluri: logica s-a formalizat utilizand metode matematice. Demn de subliniat estefaptul ca exista o corespondenta perfecta ıntre calculul propozitiilor si operatiile cusubmultimile unei multimi nevide date. De exemplu, disjunctiei a doua propozitii ıicorespunde reuniunea a doua multimi, si reciproc. Din acest motiv, nu de putine ori,elementele de logica matematica se prezinta ımpreuna cu cele de teoria multimilor,suportul intuitiv al celei din urma fiind de un real folos ın ıntelegerea si aprofundareaa numeroase constructii logice abstracte. Nu este lipsit de interes sa subliniem ca auexistat logicieni – precum Bertrand Russell – care au sustinut teza ca matematicaeste o ramura a logicii.

1.2. Rolul limbajului.

Un prim scop al acestui curs este de a trece de la limbajul natural, obisnuit,la limbajul matematic, modern. Instrumentul principal cu care opereaza orice tipde stiinta, ın particular si logica, este limbajul. In afara de limbajul natural – ıncazul nostru limba romana – exista multe alte limbaje specifice diferitelor stiinte.Aceaste limbaje au fost create din mai multe ratiuni dintre care amintim:

• Evitarea problemelor de natura logica: antinomiile semantice – vezi maijos antinomia mincinosului si cea a lui Grelling; formularile echivoce; uti-lizarea dublei negatii cu rol de negatie simpla – folosita ın multe limbinaturale precum romana si franceza, dar nu ın engleza – utilizare careeste de natura sa perverteasca gandirea corecta. La ıntrebarea: “Ce faci?”cei mai multi prefera sa aleaga varianta de raspuns, ilogic: Nu fac nimic!,ın locul celei perfect logice: Nimic3. Alaturarea lui nu cu nimic, vrem,nu vrem, are drept ınteles ceva. Ca urmare, Nu fac nimic! se traduceın termenii logicii aristotelice prin Fac ceva! Ceea ce trebuie sa retinemdin acest exemplu simplu este ca, daca ın limbajul comun, din motivetraditionale4, nu putem renunta la unele exprimari care utilizeaza dubla

1Constand dintr-o contradictie aparent insolubila dintre doua teze, legi sau principii care,

desi se exclud reciproc, pot fi demonstrate, fiecare ın parte, la fel de convingator.2Termenul de paradox este utilizat ın special de logica matematica si denumeste orice

propozitie corect construita care este adevarata daca si numai daca este falsa.3Si care, din pacate, pentru unii, exprima un adevar incontestabil.4La care s-ar putea renunta cu o mare dificultate si cu pretul unor costuri educationale

enorme.

Introducere 3

negatie pe post de negatie simpla – cu scop de a sublinia caracterul negatival unei asertiuni–, ın cadrul limbajului matematic aceasta practica este in-terzisa cu desavarsire. Oricum, este de dorit ca si ın limbajul de toate zilelesa evitam, prin intermediul unor formulari echivalente pe deplin corecte,utilizarea dublei negatii pe post de negatie simpla.

• Simplificarea si standardizarea exprimarii, e.g.5 chimia foloseste o sim-bolistica proprie pentru a scurta expunerea si a descrie cat mai precisobiectele cu care opereaza. In loc de termenul sare de bucatarie chimistulfoloseste termenul simbolic NaCl care descrie foarte precis si, ın acelasitimp, concis compozitia chimica a substantei mai sus mentionate. Tot ınscopul simplificarii si al standardizarii exprimarii, atat matematica cat silogica fac apel la o multime de simboluri proprii precum: ∀, ∃, ¬, ∈, ∋,⇒, ⇔, ∩, ∪, ∨, ∧ si multe altele pe care le vom defini si despre care vomdiscuta mai tarziu.

• Fiecare stiinta are limbajul propriu si drept urmare, cand formulam e-nunturi ın care intervin notiuni si rezultate din mai multe stiinte, trebuiesa specificam cu claritate semnificatia simbolurilor utilizate. Altminterise poate ajunge la confuzii sau la asertiuni absurde. Reamintim ca, ınchimie, N este simbolul numelui elementului Azot, ın fizica N reprezintaacronimul unitatii de masura pentru putere, i.e. Newton, iar ın matem-atica este simbolul multimii numerelor naturale. Analog, ın chimie Creprezinta acronimul elementului Carbon, ın fizica C este simbolul sis-temului de masura pentru temperatura bazat pe scara Celsius, ın muzicaC desemneaza nota Do, iar ın matematica C noteaza multimea numerelorcomplexe (si nu numai).

Este locul sa subliniem importanta utilizarii corecte a limbii, o atentie specialatrebuind a fi acordata semnelor de punctuatie. Lipsa sau prezenta acestora (i.e.6

plasarea lor neinspirata) pot modifica dramatic ıntelesul unei propozitii. Sa luamdrept exemplu propozitia (culeasa dintr-o emisiune televizata): “Stam de vorba cuFlorin, de 19 ani student ın anul ıntai.” Lipsa virgulei ıntre ani si student – virgulacare tine locul conjunctiei “si” – modifica radical ıntelesul dorit, anume ca: Florinare 19 ani si este ın anul ıntai precizand fara nici un dubiu ca: perioada ın careFlorin a fost si ınca mai este student ın anul ıntai este de 19 ani, ceea ce . . .este cu totul altceva. Un alt exemplu de acelasi tip (cules chiar dintr-o carte dematematica) evidentiaza nu numai importanta plasarii corecte a virgulei, dar sidependenta ıntelesului unei propozitii de ordinea termenilor: Teorema de uniformaconvergenta a lui Weierstrass doreste sa exprime de fapt Teorema lui Weierstrassde uniforma convergenta. Putem exprima corect acelasi lucru plasand virgula lalocul cuvenit, adica Teorema de uniforma convergenta, a lui Weierstrass.

De asemenea, unele permutari de cuvinte sau de grupuri de cuvinte pot schimbaradical ıntelesul pe care intentionam sa-l atribuim unui enunt. De exemplu, sensulpropozitiei: “Ursul a mai atacat o femeie care se afla la pascut, cu vacile.” (Reali-tatea TV, 15.09.2012, ora 18:25) este cu totul altul decat cel avut ın vedere: “Ursula mai atacat o femeie care se afla cu vacile la pascut.”

5Prescurtarea e.g. provine de la expresia latina exempli gratia si ınseamna: de exemplu, ca

exemplu, spre exemplu.6Prescurtarea i.e. provine de la expresia latina id est si ınseamna: altfel spus, cu alte cuvinte,

adica.


1.3. Definitii, propozitii

Logica opereaza cu definitii , propozitii (pe care le vom mai numi si enunturi),predicate (numite si functii propozitionale), operatori logici , cuantificatori si regulide deductie. O definitie este o delimitare precisa a unei familii particulare de obiectedintr-una mai ampla, deja cunoscuta (numita gen proxim), prin intermediul uneiproprietati comune tuturor obiectelor nou definite si numai acestora (proprietatenumita diferenta specifica). Desigur, aceasta este o descriere a ceea ce se ıntelegeprintr-o definitie si nicidecum o definitie a definitiei. Numele generic dat unui obiectdin familia nou definita este numele conceptului (notiunii) definit(e).

In definitia: “Se numeste triunghi dreptunghic un triunghi care are un unghidrept.”, numele conceptului definit este “triunghi dreptunghic”, genul proxim este“triunghi” iar diferenta specifica este “proprietatea de a avea un unghi drept”. Ocerinta esentiala pe care trebuie sa o respecte o definitie este de a fi consistenta.Aceasta ınseamna ca genul proxim trebuie sa contina macar un obiect care sa aibatoate proprietatile cerute de diferenta specifica. Un astfel de obiect se numesteexemplu pentru definitia respectiva. In cazul definitiei notiunii de grup un astfel deexemplu este grupul (Z,+).

Este usor de ınteles ca, din moment ce pentru a defini un nou concept, e.g. celde triunghi dreptunghic, trebuie sa ne bazam pe un altul deja definit, e.g. cel detriunghi, mergand ınapoi, din definitie ın definitie, vom ajunge la concepte (notiuni)pentru care nu putem gasi nici un gen proxim pre-existent la care sa ne raportam,i.e. de la care sa construim definitia. Asadar, trebuie sa consideram ın cele dinurma notiuni care nu se definesc (notiuni primare); cu ajutorul lor vom puteadefini alte obiecte. Aceasta este un principiu de baza ın orice teorie axiomatica.Cele mai importante notiuni primare pe care le vom utiliza ın cadrul acestui curssunt notiunea de multime si de relatie de apartenenta. Pentru descrierea acestorasuntem nevoiti sa apelam la intuitie.

O propozitie sau un enunt este o constatare spusa, scrisa, gandita, sau expri-mata ın orice alt mod, care este fie adevarata fie falsa. Adevarul, notat pe scurt cu asau 1 si falsul, notat pe scurt cu f sau 0, poarta numele de valori de adevar ale uneipropozitii. De exemplu: “Mihai are parul blond.” este o propozitie ın acceptiunealogicii, a carei valoare de adevar, a sau f , poate fi stabilita fie prin verificare di-recta – observarea subiectului, Mihai, – fie indirect prin observarea unei fotografiicolor a subiectului. Dimpotriva, formularile: “Cand ploua?”, “Du-te acasa!” nu suntpropozitii ın sensul logicii, desi, ın acceptiunea gramaticala, prima este o propozitieinterogativa iar cea de-a doua o propozitie imperativa. Trebuie sa mentionam de labun ınceput ca, pentru ca o anumita formulare sa fie o propozitie, nu este necesarsa fim ın stare a-i stabili valoarea de adevar. De asemenea, este foarte importantsa subliniem ca exista o distinctie ıntre modul de exprimare, i.e. expresia uneipropozitii si propozitia ınsasi. Mai precis, una si aceeasi propozitie poate fi expri-mata ın mai multe moduri. De exemplu propozitia “Mihai are parul blond.” admiteformularea echivalenta “Parul lui Mihai este blond.” Este usor de constatat ca, desiaceste doua formulari sunt distincte, ele exprima aceeasi constatare.

Mai mult, ıntr-o propozitie nu pot exista variabile libere, i.e. nelegate printr-unul dintre cuantificatorii oricare, notat cu ∀, sau exista, notat cu ∃. De exemplu:

• Constatarea ”Numarul x2 este par.” nu este o propozitie ın sensul logiciideoarece ea contine variabila libera x.

Introducere 5

• Constatarea ”Oricere ar fi numarul natural x, x2 este par.” este o propozitieın sensul logicii deoarece variabila x este legata prin cuantificatorul ∀, iarvaloarea ei de adevar este 0.

• Constatarea ”Exista numarul natural x, x2 este par.” este o propozitieın sensul logicii deoarece variabila x este legata prin cuantificatorul ∃, iarvaloarea ei de adevar este 1.

Vom reveni pe larg la acest subiect ın cadrul sectiunii Predicate.

1.3.1. Exercitii.

Exercitiul 1.3.1. Pentru definitiile de mai jos sa se puna ın evidenta:

(i) numele conceptului definit;(ii) genul proxim;(iii) diferenta specifica;

si apoi sa precizeze cateva forme echivalente. Exemplu. In cazul definitiei “Poligonulcu trei laturi se numeste triunghi.” avem

(i) numele conceptului definit:triunghi(ii) genul proxim: poligon(iii) diferenta specifica: proprietatea de a avea trei laturi.

Formulari utilizate frecvent: “Triunghiul este un poligon cu trei laturi.”, “Nu-mim triunghi un poligon cu trei laturi.” Aceasta din urma formulare este preferabiladeoarece evidentiaza de la bun ınceput ca avem de-a face cu o definitie si nu cu oteorema.

(1) Se numeste dreptunghi un patrulater cu trei unghiuri drepte.(2) Se numeste functie injectiva o functie cu proprietatea ca transforma orice

doua puncte distincte din domeniu ın doua puncte disticte din codomeniu.(3) Se numeste grup comutativ un grup (G, ◦) cu proprietatea ca pentru orice

doua elemente x, y din G avem x ◦ y = y ◦ x.(4) Se numeste numar prim un numar natural, mai mare decat 1, ai carui

singuri divizori sunt 1 si numarul ınsusi.(5) Se numeste multime ınchisa o multime de numere reale care este comple-

mentara unei multimi deschise.(6) Doua drepte se numesc paralele daca sunt coplanare si nu au ın comun

niciun punct.(7) Trei drepte se numesc concurente daca au ın comun un punct si numai

unul singur.

Exercitiul 1.3.2. Care dintre urmatoarele constatari sunt propozitii?

(1) Pomii sunt verzi.(2) Fie △ABC un triunghi isoscel.(3) Patratul are toate laturile congruente.(4) Patratul are exact doua laturi congruente.(5) Cine este autorul teoremei: “o paralela dusa la una din laturile unui tri-

unghi determina pe celelalte doua laturi segmente proportionale”?(6) De ce △ABC este echilateral?(7) Orice functie, f : R → R, continua este derivabila.(8) Toate functiile, f : R → R, continue sunt derivabile.(9) Exista o functie, f : R → R, continua care nu este derivabila.

(10) Nici o functie, f : R → R, continua nu este derivabila


(11) Nu exista o functie, f : R → R, continua care sa fie derivabila.(12) Nu exista o functie, f : R → R, continua care sa nu fie derivabila.(13) Daca x ≤ 3 atunci x10 > 10.(14) x ≤ 3.(15) (a+ b) (a− b) = a2 − b2.(16) Pentru orice a ∈ C, (a+ b) (a− b) = a2 − b2.(17) Pentru orice a, b ∈ C, (a+ b) (a− b) = a2 − b2.(18) Daca x ≤ 3 atunci y2 > 0.(19) x · x−1 = 1.

1.4. Operatii cu propozitii.

Fiind date doua propozitii p, q, putem forma altele noi prin intermediul oper-atorilor logici de: disjunctie, conjunctie, negatie si implicatie.

1.4.1. Disjunctia. Propozitia p ∨ q, care se citeste “p sau q”, poarta numelede disjunctia propozitiilor p si q, propozitie care este adevarata exact atunci candcel putin una dintre propozitiile p sau q este adevarata. Asadar, p ∨ q este falsaexact atunci cand atat p cat si q sunt false. Aceasta definitie a valorii de adevar alui p ∨ q se poate da cu ajutorul tabelului de adevar :

p q p ∨ q1 1 11 0 10 1 10 0 0

S-au scris pe linii toate combinatiile posibile de valori de adevar pentru p siq. Tabelul se citeste pe linii: de exemplu, linia 3 a tabelului spune, ca, daca p arevaloarea de adevar 0, iar q are valoarea de adevar 1, atunci p ∨ q are valoarea deadevar 1.

Exemplul 1.4.1.

• “Florin nu este acasa sau telefonul lui este defect” este un enunt de formap ∨ q, unde p este “Florin nu este acasa”, iar q este “Telefonul lui Florineste defect”.

• “Patrulaterul ABCD este patrat sau patrulaterul ABCD este romb.”Aceasta propozitie este adesea enuntata mai pe scurt “PatrulaterulABCDeste patrat sau romb.” Este important de identificat structura logica aunei propozitii “compuse” de acest tip.

1.4.2. Conjunctia. Propozitia p ∧ q, care se citeste “p si q”, poarta numelede conjunctia propozitiilor p si q, propozitie care este adevarata exact atunci candambele propozitii p si q sunt adevarate. Deci, p ∧ q este falsa exact atunci candmacar una dintre ele este falsa. Corespunzator, avem tabelul de adevar:

p q p ∧ q1 1 11 0 00 1 00 0 0

Exemplul 1.4.2.

Introducere 7

• “Trenul opreste si calatorii coboara”.• “Patrulaterul ABCD este romb si are un unghi drept.”

1.4.3. Negatia. Data o propozitie p, putem forma propozitia ¬p, numitanegatia propozitiei p, care este adevarata exact atunci cand p este falsa. Deci, ¬peste falsa daca p este adevarata. Propozitia ¬p se citeste “non p” sau “nu esteadevarat ca p”.

p ¬p1 00 1

Exemplul 1.4.3.

• Negatia propozitiei “Orice om este muritor” este “Nu orice om este muri-tor”. Forme echivalente: “Exista un om care nu este muritor” – preferata– si “Nici un om nu este muritor” – pe care o vom evita. Vezi comentariulde mai jos.

• Negatia propozitiei “Exista triunghiuri cu doua unghiuri drepte” este“Nu exista un triunghi care sa aiba doua unghiuri drepte”– preferata– sau formele echivalente “Orice triunghi nu are doua unghiuri drepte” –preferata – si “Nici un triunghi nu are doua unghiuri drepte” – pe care ovom evita.

Comentariul 1.4.1. In ambele exemple, ultima forma, desi folosita si accep-tata ın limbajul curent, va fi evitata ın limbajul matematic tocmai pentru a nupermite utilizarea dublei negatii cu rol de negatie simpla, utilizare avand dreptscop de a accentua caracterul negativ al constatarii, dar generatoare de posibileambiguitati.

Sa analizam cateva exemple.

Exemplul 1.4.4. Negatia propozitiei: “dreptele d1 si d2 sunt paralele saunecoplanare” este “dreptele d1 si d2 nu sunt paralele si nu sunt necoplanare”,ceea ce, ın virtutea pricipiului dublei negatii, se reformuleaza: “dreptele d1 si d2nu sunt paralele si sunt coplanare” – de unde deducem ca “dreptele d1 si d2 suntconcurente”. Aceeasi negatie mai poate fi exprimata si sub forma: “dreptele d1 sid2 nu sunt paralele si nici necoplanare”.

Exemplul 1.4.5. Negatia propozitiei: “patrulaterul ABCD este romb si areun unghi drept” este “patrulaterul ABCD nu este romb sau nu are un unghi drept”sau, echivalent: “patrulaterul ABCD nu este romb sau orice unghi al sau nu estedrept” sau ınca: “patrulaterul ABCD nu este romb sau nu exista un unghi al saucare sa fie drept”.

1.4.4. Implicatia. Definim propozitia p → q, care se citeste “p implica q” cafiind o notatie prescurtata pentru propozitia (¬p) ∨ q. Scriind tabelul de adevarpentru (¬p)∨ q, se vede imediat ca p → q este adevarata daca q este adevarata sau

atat p cat si q sunt false, si falsa numai daca p este adevarata si q falsa. In expresiap → q, p poarta numele de ipoteza sau de premisa iar q de concluzie . Operatorullogic → se numeste implicatie.


Tabelul sau de adevar este:

p q p → q1 1 11 0 00 1 10 0 1

Se justifica intuitiv ca p → q este acelasi lucru cu (¬p) ∨ q, astfel: p → q ınseamna“daca p este adevarata, atunci q este adevarata”. Altfel spus, sau p este falsa (adicaare loc ¬p), sau p este adevarata si atunci automat q este adevarata (adica are locq); pe scurt, (¬p) ∨ q. Faptul ca p → q este acelasi lucru din punct de vedere logiccu (¬p)∨q este foarte important si util cand trebuie negata o implicatie (lucru careintervine frecvent, de exemplu ın cazul demonstratiilor prin reducere la absurd).

Exemple:

• “Daca plecam ıntr-un minut atunci vom ajunge la timp”.• “Daca △ABC este triunghi cu toate laturile congruente doua cate doua

atunci unghiurile triunghiului ABC sunt congruente doua cate doua”.

Propozitia p → q se mai poate exprima prin frazele urmatoare, des ıntalnite ıntextele matematice sau ın limbajul natural:

• “daca p atunci q”• “ın ipoteza p are loc q”• “p este o conditie suficienta pentru q”• “q este o conditie necesara pentru p”• “q daca p”• “p numai daca q”• “q ın ipoteza ca p”• “este suficient ca p pentru ca q”• “q este o consecinta a lui p”etc.

Invitam cititorul sa reformuleze ın limbaj natural exemplele de mai sus, folosindtoate variantele posibile. De pilda, “Daca plecam ıntr-un minut atunci vom ajungela timp” se mai poate exprima prin “Plecam ıntr-un minut implica ca vom ajungela timp”7, “Este suficient sa plecam ıntr-un minut pentru ca sa ajungem la timp”,“Vom ajunge la timp daca plecam ıntr-un minut” etc.

In sfarsit, definim operatorul logic ↔ a carui semnificatie este precizata mai jos.Daca p si q sunt propozitii, p ↔ q este notatia prescurtata pentru (p → p)∧(q → p) .

Propozitia p ↔ q se mai poate exprima prin frazele urmatoare, des ıntalnite ıntextele matematice sau ın limbajul natural:

• “p daca si numai daca q”• “O conditie necesara si suficienta pentru p este q”• “p este o conditie necesara si suficienta pentru q”.

1.5. Expresii

Sa definim riguros cum putem construi noi propozitii din propozitiile deja ex-istente. Pornim de la trei multimi de simboluri: V = {p, q, . . . }, numita multimeavariabilelor propozitionale, O = {∨,∧,→,¬} numita multimea operatorilor logici

7Din multiplele moduri de exprimare, este indicat totusi sa le alegem pe cele care evita

cacofoniile...

Introducere 9

si A = {(, )}, numita multimea simbolurilor auxiliare. O expresie propozitionala,sau, pe scurt, expresie8, este un sir de simboluri alese din multimile V,O sau A,construit dupa regulile de mai jos:

(E1) orice variabila propozitionala este o expresie;(E2) daca E si F sunt expresii atunci (E)∨ (F ), (E)∧ (F ), (E) → (F ) si ¬(E)

sunt expresii;(E3) singurele expresii corecte sunt cele construite respectand regulile (E1) si

(E2).

Pentru un plus de claritate, se admite folosirea, ın afara de parantezele rotunde,si a parantezelor patrate [, ] si a acoladelor {, }. In cele ce urmeaza vom numi cuvanto succesiune de elemente din cele trei multimi precizate mai sus.

Pentru simplitatea scrierii, ori de cate ori nu apare pericol de confuzie, ın locde (E) ∨ (F ) vom scrie, mai simplu, E ∨ F . Aceeasi observatie se aplica pentru(E)∧ (F ), (E) → (F ) si ¬(E). De asemenea, operatorul ¬ actioneaza numai asupraexpresiei imediat urmatoare. De exemplu, ¬¬p reprezinta scrierea simplificata a¬(¬p). Analog, ¬p ∨ q este scrierea simplificata a (¬p) ∨ q.

Exemplu. In conformitate cu cele precizate mai sus, daca E si F sunt expresii,atunci cuvintele (E ∧ F ) → ¬(E) si ¬(E ∨ F ) sunt expresii, ın timp ce (E ∧ F )¬Esi EF ∧ F nu sunt expresii.

Remarca 1.5.1. Dupa cum este de asteptat, ın ¬(E ∨ F ) negatia se refera ladisjunctia E∨F , ın timp ce ın expresia ¬E∨F , ea se refera doar la E. Uneori, candvom utiliza mai multe randuri de paranteze, pentru a scoate ın evidenta ordineaoperatiilor efectuate, vom utiliza si alte semne ınafara de parantezele rotunde, (, ),anume: [, ] si chiar {, }. De exemplu, ın expresia {[(E ∨ F ) → G] ∧ H} ∨ L seefectueaza ın ordine: E ∨ F , (E ∨ F ) → G, [(E ∨ F ) → G] ∧ H si, ın sfarsit,{[(E ∨ F ) → G] ∧H} ∨ L.

Definitia 1.5.1. Doua expresii propozitionale E si F se numesc echivalentedaca, pentru orice valori de adevar ale variabilelor propozitionale care apar ın E siF, expresiile au aceeasi valoare de adevar. Notam acest lucru prin E ≡ F.

Remarca 1.5.2. Au loc urmatoarele reguli de negatie exprimate prin inter-mediul echivalentelor logice:

¬(p ∨ q) ≡ (¬p) ∧ (¬q)¬(p ∧ q) ≡ (¬p) ∨ (¬q),

numite legile lui DeMorgan.

Exemplul 1.5.1. Au loc urmatoarele echivalente (demonstrati-le cu ajutorultabelelor de adevar):

(i) p → q ≡ (¬p) ∨ q. Aceasta echivalenta nu este decat o transcriere adefinitiei implicatiei.

(ii) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) (distributivitatea lui ∧ fata de ∨).(iii) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (distributivitatea lui ∨ fata de ∧).(iv) ¬(¬p) ≡ p (legea negarii negatiei).

Pentru ilustrare, demonstram distributivitatea lui ∧ fata de ∨. Intrucat sunt3 variabile propozitionale, trebuie sa avem 8 linii ın tabel, corespunzatoare celor8 = 23 combinatii al valorilor de adevar ale p, q, r :

8Sau formula.


p q r p ∧ q p ∧ r (p ∧ q) ∨ (p ∧ r) q ∨ r p ∧ (q ∨ r)1 1 1 1 1 1 1 11 1 0 1 0 1 1 11 0 1 0 1 1 1 11 0 0 0 0 0 0 00 1 1 0 0 0 1 00 1 0 0 0 0 1 00 0 1 0 0 0 1 00 0 0 0 0 0 0 0

Egalitatea coloanelor (p ∧ q) ∨ (p ∧ r) si p ∧ (q ∨ r) demonstreaza echivalentaceruta.

Revenim asupra negarii implicatiei. Intuitiv, cand spunem ca p → q este falsa?Desigur, atunci cand ipoteza p este adevarata si totusi concluzia q este falsa (adicaare loc p ∧ ¬q). Aceasta este ın acord cu urmatorul calcul propozitional:

¬ (p → q) ≡ ¬ ((¬p) ∨ q) ≡ ¬(¬p) ∧ (¬q) ≡ p ∧ (¬q).Am aplicat legile de negare ale lui DeMorgan. Vezi Remarca 1.5.2. Pentru importantasa, trebuie retinuta aceasta regula de negare a implicatiei :

¬(p → q) ≡ p ∧ (¬q) .

In general, concluziile bazate pe un calcul logic formal trebuie totdeauna in-terpretate intuitiv (conform bunului simt). Acest fapt evita aparitia unor greselidatorate aplicarii defectuoase a regulilor logicii si, totodata, este un proces absolutnecesar ın ıntelegerea unor demonstratii (sau ın gasirea unor solutii la o problemadata).

Echivalenta. Pentru doua expresii propozitionale E si F, definim E ↔ F , unde↔ este un operatorul logic a carui semnificatie a fost precizata la finalul sectiuniiprecedente. Tabelul sau de adevar este (demonstrati):

p q p ↔ q1 1 11 0 00 1 00 0 1

In concluzie, p ↔ q este adevarata atunci cand p si q au aceeasi valoare de adevar,si falsa ın caz contrar. Observam ca p ≡ q este acelasi lucru cu faptul ca p ↔ q esteadevarata. Propozitia p ↔ q se citeste:

• “p este echivalenta cu q”• “p daca si numai daca q”• “p este o conditie necesara si suficienta pentru q”.

Definitia 1.5.2. Se numeste tautologie o expresie care este adevarata, indifer-ent de valorile de adevar ale variabilelor propozitionale. Se numeste contradictie oexpresie care este falsa, indiferent de valorile de adevar ale variabilelor propozitionale.

Astfel, daca E, F sunt expresii, atunci: “E ↔ F este o tautologie” este exactacelasi lucru cu “E ≡ F”. Orice echivalenta E ≡ F genereaza tautologia E ↔ F :folosind Exemplul 1.5.1, obtinem tautologiile [p ∧ (q ∨ r)] ↔ [(p ∧ q) ∨ (p ∧ r)] etc.

Introducere 11

Definitia 1.5.3. Fie E siF expresii. Daca expresia E → F este o tautologie,scriem E ⇒ F. Daca expresia E ↔ F este o tautologie, scriem E ⇔ F.

Insistam asupra distinctiei dintre E → F si E ⇒ F. Astfel, E → F este oexpresie, din care putem obtine propozitii adevarate sau false, ın functie de valorilede adevar ale variabilelor propozitionale, care sunt implicate ın definirea ambelorexpresii E si F , pe cand E ⇒ F ınseamna ca E → F este o tautologie.

Analog, E ↔ F poate fi o tautologie sau nu, pe cand E ⇔ F este o tautologie.Evident, E ⇔ F ınseamna ca atat E ⇒ F si F ⇒ E. sunt tautologii

De aceste lucruri trebuie sa se tina cont ın redactarea demonstratiilor sau ındiverse enunturi matematice: vom scrie E ⇒ F doar ın cazul ın care E → F este otautologie. La fel, scriem E ⇔ F doar cand E ⇒ F si F ⇒ E au loc simultan. Ogreseala frecventa este folosirea abuziva a notatiei ⇔, cand ar trebui sa se foloseasca⇒ (de exemplu ın cursul rezolvarii unor ecuatii).

Exemplul 1.5.2. Pentru orice propozitii p, q avem: ((p → q) ∧ p) ⇒ q.

Demonstratie. Trebuie sa aratam ca propozitia ((p → q) ∧ p) → q este adevarata,indiferent de valorile de adevar ale p, q. Examinand definitia operatorului →, avemde aratat ca, daca ((p → q) ∧ p) este adevarata, atunci q este adevarata.

Presupunand deci ((p → q) ∧ p) adevarata, rezulta din tabela de adevar pentru∧ ca p este adevarata si p → q adevarata. Dar p → q ≡ ¬p∨q, deci p ∧ (¬p ∨ q) esteadevarata. Folosind distributivitatea, deducem ca p ∧ (¬p ∨ q) ≡ (p ∧ ¬p) ∨ (p ∧ q)este adevarata. Cum p ∧ ¬p este ıntotdeauna falsa (este o contradictie), (p ∧ q)trebuie sa fie adevarata, deci q este adevarata. �

Mai exista doua variante de demonstratie: folosind tabele de adevar sau folosindcalculul propozitional. Lasam ın seama cititorului demonstratia bazata pe tabelelede adevar, margninindu-ne sa exemplificam metoda calculului propozitional (carenecesita cunoasterea unor formule din calculul cu propozitii).

Demonstratie. Folosind definitia implicatiei (p → q ≡ ¬p ∨ q), avem:

((p → q) ∧ p) → q ≡ ¬ ((p → q) ∧ p) ∨ q ≡ ¬ ((¬p ∨ q) ∧ p) ∨ q ≡(¬ (¬p ∨ q) ∨ ¬p) ∨ q ≡ ((¬¬p ∧ ¬q) ∨ ¬p) ∨ q ≡ ((p ∧ ¬q) ∨ ¬p) ∨ q ≡

((p ∨ ¬p) ∧ (¬q ∨ ¬p)) ∨ q

Dar p ∨ ¬p este totdeauna adevarata, deci (p ∨ ¬p) ∧ (¬q ∨ ¬p) ≡ ¬q ∨ ¬p.Continuam:

((p ∨ ¬p) ∧ (¬q ∨ ¬p)) ∨ q ≡ (¬q ∨ ¬p) ∨ q ≡ (¬p ∨ ¬q) ∨ q ≡ ¬p ∨ (¬q ∨ q)

Am folosit ca disjunctia este asociativa si comutativa. Aceasta propozitie esteo tautologie (caci ¬q ∨ q este tautologie). �

Urmatoarea propozitie colecteaza o serie de tautologii, dintre care unele suntfolosite ın rationamente si au primit nume distinctive. Cateva au mai fost ıntalniteın text, sub forma unor echivalente logice. Invitam cititorul sa demonstreze catevadintre ele (macar (6), (7), (13), (19), (23), (24), (25)), folosind una din metodeledescrise mai sus.

Propozitia 1.5.1. Fie p, q, r variabile propozitionale. Au loc urmatoarele tau-tologii :

(1) (p ∨ q) ↔ (q ∨ p) (Comutativitatea disjunctiei).


(2) (p ∧ q) ↔ (q ∧ p) (Comutativitatea conjunctiei).(3) [(p ∨ q) ∨ r] ↔ [p ∨ (q ∨ r)] (Asociativitatea disjunctiei).9

(4) [(p ∧ q) ∧ r] ↔ [p ∧ (q ∧ r)] (Asociativitatea conjunctiei).10

(5) p ∧ (q ∨ r) ↔ [(p ∧ q) ∨ (p ∧ r)] (Distributivitatea lui ∧ fata de ∨).(6) p ∨ (q ∧ r) ↔ [(p ∨ q) ∧ (p ∨ r)] (Distributivitatea lui ∨ fata de ∧).(7) [¬(p ∨ q)] ↔ (¬p ∧ ¬q) ; [¬(p ∧ q)] ↔ (¬p ∨ ¬q) (Legile lui DeMorgan sau

legile de dualitate).(8) (p ↔ q) ↔ [(p → q) ∧ (q → p)](9) (p ↔ q) ↔ (q ↔ p)

(10) (p ↔ q) → (p → q)(11) p ↔ p(12) ¬ (p ∧ ¬p)(13) (p ∧ ¬p) → q (Pornind de la o contradictie, deducem ca orice este adevarat)11.(14) ¬(¬p) ↔ p (Legea dublei negatii).(15) p ∨ ¬p (Legea tertului exclus).(16) (p ∧ p) ↔ p(17) (p ∨ p) ↔ p(18) p → (q → p) (Daca p este adevarata, atunci p este adevarata ın orice

ipoteza).(19) [p → (q → r)] ↔ [(p ∧ q) → r](20) (¬p) → (p → q)(21) (p → q) ∨ (q → p)(22) (p → q) ↔ (¬p ∨ q)(23) (p → q) ↔ (¬q → ¬p) (Principiul de demonstratie prin reducere la ab-

surd: pentru a demonstra q ın ipoteza p, presupunem ca q este falsa sidemonstram ¬p.)

(24) (p → q) ↔ [(p ∧ ¬q) → (r ∧ ¬r)] (O varianta a principiului de demonstra-tie prin reducere la absurd: pentru a demonstra ca p ⇒ q, se presupune caare loc p si totusi q este falsa. De aici se deduce o contradictie: (r ∧ ¬r) .)

(25) [p → (q ∨ r)] ↔ [(p ∧ ¬q) → r] (Pentru a demonstra ca p implica o con-cluzie de forma q ∨ r, se presupun adevarate p si ¬q si se demonstreazar.)

(26) [(p → q) ∧ (q → r)] → (p → r) (Tranzitivitatea implicatiei, cunoscuta subnumele de regula silogismului)

(27) ¬ (p → q) ↔ (p ∧ ¬q) (Regula de negare a implicatiei) .

1.5.1. Exercitii.

Exercitiul 1.5.1. Fie propozitiile p:“ın triunghiul ∆ABC m(A) = π2 ”, q: “ın

triunghiul ∆ABC m(B) = π4 ” si r: “ın triunghiul ∆ABC m(C) = π

4 ”.Scrieti expresiile logice corespunzatoare enunturilor:

(1) Daca ın triunghiul ∆ABC m(A) = π2 si m(B) = π

4 atunci m(C) = π4 .

(2) Daca ın triunghiul ∆ABC m(B) = m(C) = π4 atunci m(A) = π

2 .

9Asociativitatea disjunctiei ne permite sa scriem p∨q∨r ın loc de (p∨q)∨r sau de p∨(q∨r),

fara pericol de confuzie deoarece valoarea de adevar nu este influentata de pozitia parantezelor.10Asociativitatea conjunctiei ne permite sa scriem p∧q∧r ın loc de (p∧q)∧r sau de p∧(q∧r),

fara pericol de confuzie deoarece valoarea de adevar nu este influentata de pozitia parantezelor.11Este deci esential ca o teorie matematica sa nu contina contradictii: daca orice afirmatie

este adevarata, atunci cercetarea adevarului este inutila...

Introducere 13

Traduceti ın limbaj natural urmatoarele propozitii:

(3) (r ∧ q) → p(4) (r ∧ ¬q) → ¬p.

Exercitiul 1.5.2. Fie propozitiile p: “Ana are mere”, q: “Ana este blonda” sir: “Ana canta frumos.” Traduceti ın limbaj natural urmatoarele propozitii:

(1) q → r(2) p ∧ q(3) ¬q(4) ¬ (p ∨ q)(5) (¬p) ∨ (¬q)(6) (r ∧ q) → p(7) (r ∧ q) ∨ p(8) r ∧ (q ∨ p)(9) r ↔ (p ∧ q)

(10) (r → q) ∧ (r → p)(11) r → (q ∧ p)(12) (p ∧ (¬q)) ↔ (r ∨ (¬p))

Exercitiul 1.5.3. Scrieti expresiile logice corespunzatoare enunturilor:

(1) Ana nu este blonda, dar canta frumos.(2) Ana nu are mere, si nu este blonda sau canta frumos.(3) Ana nu are mere si nu este blonda, sau canta frumos.(4) Nu este adevarat ca Ana este blonda sau are mere.(5) Nu este adevarat ca Ana este blonda, sau are mere.(6) Ana are mere si este blonda, sau are mere si canta urat.(7) Daca Ana are mere si este blonda, atunci ea canta frumos.(8) O conditie necesara ca Ana sa cante frumos este sa fie blonda.(9) O conditie suficienta ca Ana sa cante frumos este sa fie blonda.

(10) Chiar daca Ana canta frumos, nu are mere.(11) Ana are mere daca este blonda, si nu canta urat daca are mere.

Exercitiul 1.5.4. Fie p, q, r propozitii. Sa se demonstreze ca:

(1) p ⇒ p ∨ q(2) (p ∧ q) ⇒ p(3) ¬ (p → q) ⇒ p(4) (p → q) ∧ (p → ¬q) ⇒ ¬p(5) (p → (q → r)) ≡ (p ∧ q) → r(6) (p → q) ⇔ (¬q → ¬p)(7) (p ∨ q) → r ⇔ (p → r) ∧ (q → r).

Exercitiul 1.5.5. Formulati negatia fiecareia dintre propozitiile:

(1) Patrulaterul ABCD este romb si are aria de 2m2.(2) Numarul 8 este par si x8 = 2.(3) Raza sferei este din [ 1, 3 ] si baza conului este pe sfera(4) Ecuatia x2 + 2x = 0 cu x ∈ N are solutia x = 0 si solutia x = −2.(5) Functia f este pozitiva pe (0, 1) si se anuleaza ın x = 0 si x = 1.(6) Patrulaterul ABCD este patrat sau romb.(7) Functia exponentiala este strict crescatoare sau strict descrescatoare.(8) Sirul (an)n∈N este monoton crescator sau monoton descrescator.


(9) Functia f este continua si monotona.(10) ^ABC este drept sau ^BCA este drept.

1.6. Predicate

Sa consideram urmatoarele propozitii

• 2 · 2 + 1 ≥ 0• 2 · 3 + 1 ≥ 0• 2 · (−2) + 1 ≥ 0.

Observam ca toate cele trei propozitii de mai sus sunt de forma 2 · x + 1 ≥ 0,unde x este un numar – care, ın cazurile considerate, este din Z. Suntem condusila a defini notiunea de propozitie depinzand de un parametru care, ın terminologiaconsacrata, poarta numele de predicat de o variabila. De fapt, un predicat este ofunctie definita pe multimea (clasa12) unde se gaseste variabila (parametrul), fieaceasta Γ, cu valori ın multimea P a propozitiilor. Adica, un predicat de o variabilaeste o functie p : Γ → P.

Pentru a evita confuziile, accentuam ca, daca p : Γ → P este un predicat sib ∈ Γ, atunci p(b) este o propozitie si nu un predicat.

Analog, se poate vorbi despre predicate de mai multe variabile. De exemplu,“x2 − y2 = (x− y)(x+ y), x, y ∈ R” este un predicat de doua variabile.

Subliniem ca, pentru a evita confuziile, oricarui predicat trebuie sa i se precizezeclar multimea Γ ın care se pot “misca” variabilele, i.e. domeniul de definitie alfunctiei p. Se admite omiterea scrierii multimii Γ doar daca aceasta este clara dincontext. Astfel, ”x2 + 1 = 0” poate fi considerat un predicat numai daca precizamx ∈ Γ, unde Γ este de exemplu una din multimile N, Z, Q, R sau C. Intr-adevar,este usor de observat ca

p(x) : x2 + 1 = 0 cu x ∈ R

este un predicat ale carui valori sunt toate false, ın timp ce

q(x) : x2 + 1 = 0 cu x ∈ C

este un predicat pentru care q(i) si q(−i) sunt adevarate, iar restul valorilor suntfalse. Prin traditie, un predicat de tipul celui prezentat, care are toate valorile (adicapropozitiile) egalitati, se numeste ecuatie. O solutie a ecuatiei este o valoare pentrucare egalitatea este satisfacuta, i.e. propozitia obtinuta prin ınlocuirea variabileicu solutia este adevarata. A rezolva o ecuatie ınseamna a gasi multimea tuturorsolutiilor ei. Asadar, multimea solutiilor ecuatiei q(x) : x2 + 1 = 0 cu x ∈ Ceste {i,−i}. Pentru simplitatea scrierii, pentru ecuatii se renunta la notarea detip predicatul q(x) : . . . , precizandu-se doar egalitatea si domeniul variabilei. Deexemplu, ecuatia de mai sus se ıntalneste sub forma ”x2 + 1 = 0 cu x ∈ C”. Alteexemple de ecuatii sunt:

x′ = 2x, x ∈ {y; y : R → R, cu y functie derivabila},

numita ecuatie diferentiala cu functia necunoscuta x. Se poate arata ca multimeasolutiilor acestei ecuatii este

{xc; xc : R → R, xc(t) = c · e2t, ∀t ∈ R, c ∈ R}.

12O clasa este o “colectie de obiecte” care nu este neaparat multime. Orice multime este o

clasa dar nu si reciproc. De exemplu clasa tuturor multimilor. Vezi Capitolul Teoria multimilor.

Introducere 15

Sa consideram acum

2 · x+ 3 · y = 24, (x, y) ∈ Z× Z,ın care variabila este o pereche (x, y) ∈ Z×Z, numita ecuatie diofantica13. Multimeasolutiilor ecuatiei diofantice de mai sus este o multime de perechi de numere ıntregi.O solutie este (0, 8). Puteti gasi toate solutiile?

1.7. Variabile libere. Variabile legate

Sa consideram un predicat de o singura variabila p(x), x ∈ Γ. Pornind de la el,putem forma urmatoarele doua propozitii :

(1) Pentru orice x ∈ Γ, p(x) este adevarata.(2) Exista x ∈ Γ astfel ıncat p(x) este adevarata.

Subliniem ca acestea sunt propozitii si nu predicate.Pentru simplificarea scrierii, introducem doua simboluri corespunzatoare celor

doua tipuri de propozitii de mai sus. Incepem cu simbolul ∀, care se va citi pentruorice, sau oricare ar fi, sau ınca pentru toti (toate) si pe care ıl vom numi cuantifica-tor universal . Cu ajutorul lui, propozitia: pentru orice x din Γ p(x) este adevaratase rescrie, fara a se mai specifica “este adevarata”, adica

(∀x ∈ Γ) p(x).Scrierea (∀x ∈ Γ) p(x) poate fi interpretata ca o conjunctie extinsa a tuturor

propozitiilor p(x) dupa x ∈ Γ, mai precis

(∀x ∈ Γ) p(x) = ∧x∈Γp(x). (1.7.1) eq131

Intr-adevar, daca Γ = {1, 2, 3, . . . , n}, atunci• ∀x ∈ Γ p(x) are aceeasi valoare de adevar cu p(1) ∧ p(2) ∧ · · · ∧ p(n).

In sfarsit, sa introducem cuantificatorului existential, notat ∃, si care se citesteexista un/o, macar pentru un/o, cel putin pentru un/o. Cu ajutorul lui, propozitia:exista x ∈ Γ pentru care p(x) este adevarata se rescrie

(∃x ∈ Γ)p(x).Similar, scrierea (∃x ∈ Γ) p(x) poate fi interpretata ca o disjunctie extinsa a

tuturor propozitiilor p(x) dupa x ∈ Γ, mai precis

(∃x ∈ Γ) p(x) = ∨x∈Γp(x). (1.7.2) eq132

Intr-adevar, daca Γ = {1, 2, 3, . . . , n}, atunci• ∃ x ∈ Γ p(x) are aceeasi valoare de adevar cu p(1) ∨ p(2) ∨ · · · ∨ p(n).

In concluzie, pornind de la un predicat de o variabila, p(x) cu x din Γ, obtinem douapropozitii: una, utilizand cuantificatorul ∀, i.e. (∀x ∈ Γ) p(x) si cealalta, utilizandcuantificatorul ∃, i.e. (∃x ∈ Γ) p(x). Astfel, luand predicatul 2 · x + 1 ≥ 0, unde xeste din Z se obtin propozitiile

• (∀x ∈ Z)(2 · x+ 1 ≥ 0)• (∃x ∈ Z)(2 · x+ 1 ≥ 0)

din care prima este falsa iar cea de-a doua adevarata.Dupa cum am constatat, variabila x are roluri diferite ın predicatul “p(x), x ∈

Γ” si respectiv ın propozitia (∀x ∈ Γ)p(x). In primul caz, x este o variabila libera ınsensul ca x poate lua valori arbitrare ın Γ, obtinandu-se diverse propozitii, adevarate

13Numele ecuatiei provine de la Diofant din Alexandria (cca. 325-410), care a studiat acest

tip de ecuatie.


sau false. In cel de-al doilea caz, propozitia (∀x ∈ Γ)p(x) are o valoare de adevarbine determinata, independenta de variabila x. Din acest motiv, ın (∀x ∈ Γ)p(x),se spune ca variabila x este variabila legata. Consideratii similare au loc si pentrucuplul: predicatul “p(x), x ∈ Γ” si propozitia (∃x ∈ Γ)p(x), variabila x fiind legataın propozitia (∃x ∈ Γ)p(x).

In sfarsit, subliniem ca numele variabilei, libera sau legata, nu are nici o impor-tanta. Mai precis, propozitia (∀x ∈ Γ)p(x) ınseamna exact acelasi lucru cu propozitia(∀y ∈ Γ)p(y), dar nu cu (∀y ∈ Γ)p(x). Cu alte cuvinte, schimbarea numelui uneivariabile trebuie sa fie facuta peste tot unde apare aceasta (cu un nume diferit de

numele celorlalte variabile care apar ın predicat sau propozitie). In cazul ın care Γeste subınteleasa din context si nu exista pericol de confuzie, ın loc de (∀x ∈ Γ)p(x)se poate scrie ∀x p(x). Analog, ın loc de (∃x ∈ Γ)p(x) se poate scrie ∃x p(x).

1.8. Reguli de negatie

Au loc urmatoarele reguli de negatie pentru cuantificatori (a se compara culegile lui DeMorgan, tinand cont de (1.7.2) si (1.7.1)):

¬ [(∃x ∈ V ) (p(x))] ≡ (∀x ∈ V ) (¬p(x))¬ [(∀x ∈ V ) (p(x))] ≡ (∃x ∈ V ) (¬p(x))

Exemplul 1.8.1. Negatia propozitiei: “exista un numar natural n astfel ıncat“f(n) > 1” este: “pentru orice numar natural n avem f(n) ≤ 1”.

Exemplul 1.8.2. Negatia propozitiei: “pentru orice numar real a, a4 estestrict pozitiv” este: “exista un numar real a astfel ıncat a4 nu este strict pozitiv”sau, echivalent: “exista un numar real a astfel ıncat a4 este negativ”.

Pornind de la un predicat de doua variabile P (x, y) , se pot lega variabilele ınmai multe moduri cu ajutorul cuantificatorilor ∀ si ∃. Sa luam exemplul predicatuluiP (x, y) : “x ∈ y”, unde x si y sunt multimi. Se pot forma predicatele de o variabilasi apoi propozitiile urmatoare:

(1) Legand mai ıntai pe x cu ajutorul lui ∀, obtinem Q (y) = ∀x (x ∈ y).Faptul ca Q (y) este adevarat pentru o anumita multime y ınseamna cay contine toate multimile, ceea ce este imposibil (nu exista o “multime atuturor multimilor”).

Legand apoi pe y cu ∀, obtinem ∀y (∀x (x ∈ y)) , o propozitie falsa.Daca legam pe y cu ∃, obtinem ∃y∀x (x ∈ y) , de asemenea o propozitie

falsa.(2) R (x) = ∀y (x ∈ y). Pentru o anumita multime x, R (x) adevarat ınseamna

ca x apartine tuturor multimilor. Nu exista astfel de x (de exemplu, x ∈ ∅este falsa).

∀x (∀y (x ∈ y)) este echivalenta cu ∀y (∀x (x ∈ y)) . Ordinea ın careaplicam cuantificatori de acelasi fel nu are importanta.

∃x (∀y (x ∈ y)) este o propozitie falsa.(3) Legand x cu ajutorul lui ∃, obtinem S (y) = ∃x (x ∈ y). Faptul ca S (y)

este adevarat pentru o anumita multime y ınseamna ca y este nevida.∀y (∃x (x ∈ y)) ınseamna ca toate multimile sunt nevide (fals).∃y (∃x (x ∈ y)) este adevarata (exista o multime nevida).

(4) Legand y cu ajutorul lui ∃, obtinem T (x) = ∃y (x ∈ y). Pentru oricemultime x, T (x) este adevarata: ∃P (x) (x ∈ P (x)) .

Introducere 17

∀x (∃y (x ∈ y)) este adevarata.∃x (∃y (x ∈ y)) este adevarata.

Observam ca:

- ∀x (∀y (P (x, y))) este echivalenta cu ∀y (∀x (P (x, y))) . Se poate scrie maipe scurt ∀y∀x (P (x, y)) .

- ∃x (∃y (P (x, y))) este echivalenta cu ∃y (∃x (P (x, y))) . Se poate scrie maipe scurt ∃y∃x (P (x, y)) . Ordinea de aplicare a cuantificatorilor de acelasitip nu are importanta.

- ∀x (∃y (P (x, y))) nu este echivalenta cu ∃y (∀x (P (x, y))).

Subliniem ca ıntre propozitiile care provin dintr-un predicat de doua sau maimulte variabile exista o relatie de implicare precizata de schema de mai jos.

(∀x)(∀y)P (x, y) ⇔ (∀y)(∀x)P (x, y)⇓ ⇓

(∃x)(∀y)P (x, y) (∃y)(∀x)P (x, y)⇓ ⇓

(∀y)(∃x)P (x, y) (∀x)(∃y)P (x, y)⇓ ⇓

(∃x)(∃y)P (x, y) ⇔ (∃y)(∃x)P (x, y)

Remarca 1.8.1. Propozitiile obtinute una din alta prin schimbarea ordiniicuantificatorilor de tipuri diferite nu sunt, ın general, echivalente logic. De exemplu,pornind de la predicatul Q(x, y): “x are nota y”, cu x din multimea studentiloranului I si y din {1, 2, . . . 10}, se obtine propozitia ∀x∃yQ(x, y) care, tradusa ınlimbajul natural, ınseamna “orice student din anul I are o nota cuprinsa ıntre 1 si10”. Prin inversarea ordinii cuantificatorilor se obtine ∃x∀yQ(x, y) care ınseamna“exista o nota comuna tuturor studentilor din anul I”, sau “toti studentii din anulI au aceeasi nota”. Este clar ca cele doua propozitii nu sunt echivalente logic.

Analog ∀x∃y (x+ y = 1) si ∃y∀x (x+ y = 1) nu sunt logic echivalente.

Au loc regulile de calcul:

q ∧ (∃xP (x)) ≡ ∃x (q ∧ P (x)) ,

q ∨ (∀xP (x)) ≡ ∀x (q ∨ P (x)) ,

unde q este o propozitie (sau un predicat care nu depinde de x). Ce legatura putetistabili ıntre aceste reguli si distributivitatea lui ∧ fata de ∨?

1.9. Exercitii si probleme

Exercitiul 1.9.1. [5] Se considera urmatoarele predicate (se presupune cavariabilele iau valori ın multimea oamenilor):

B (x) =“x este un barbat”F (x) =“x este o femeie”xTy =“x este mai tanar decat y”xCy =“x este copilul lui y”xMy =“x este casatorit cu y”I (x) =“x locuieste la Iasi”D (x) =“x locuieste la Dej”Folosind notatiile de mai sus, sa se scrie expresiile ın limbaj formal pentru

urmatoarele propozitii sau predicate:


(1) Fiecare are un tata si o mama.(2) x este casatorit.(3) Fiecare este mai tanar decat parintii sai.(4) Fiecare este mai tanar decat bunicii sai.(5) Oricine care are un tata, are si o mama.(6) Exista un om cu o nora mai ın varsta decat el.(7) x si y sunt frati (ın sensul si de mama si de tata).(8) Daca exista o femeie la Iasi cu un frate la Dej, atunci exista un barbat la

Dej cu o sora la Iasi.(9) Un barbat casatorit poate sa nu locuiasca la Iasi.

(10) Nu fiecare femeie din Iasi nu are un fiu la Dej.(11) Toti copiii lui x sunt casatoriti.(12) Exista cineva ai carui copii sunt toti casatoriti.(13) Fiecare copil al lui x este casatorit cu un copil al lui y.(14) Exista un copil al lui x care nu este casatorit cu un copil al lui y.(15) Exista doua persoane astfel ıncat fiecare copil al uneia dintre ele este

casatorit cu un copil al celeilalte.(16) x si y sunt veri.

Sa se traduca ın limbaj natural:(17) ∀x∀y [(xMy ∧B (x)) → F (y)] .(18) ∃x∃y [B (x) ∧ F (y) ∧ xMy ∧ ∀z (zCy → ¬ (zCx))] .(19) ∃y (F (y) ∧ xMy) ∧ ∃z (F (z) ∧ yCz) ∧ zTx.

Exercitiul 1.9.2. Sa se reformuleze propozitiile de mai jos ın limbaj matem-atic (LM) utilizand cuantificatorii ∀ si ∃, sa se precizeze negatiile lor ın limbajmatematic (NLM) si apoi sa se formuleze negatiile gasite ın limbajul natural(NLN).

(1) Exista a ∈ A astfel ıncat f(a) = b. (Ecuatia f(x) = b are solutia a ∈ A.)(2) Pentru orice y ∈ B exista x ∈ A astfel ıncat f(x) = y. (O functie f : A →

B cu proprietatea enuntata se numeste surjectiva.)(3) Pentru orice x, y ∈ A, cu x = y, avem f(x) = f(y). (O functie f : A → B

cu proprietatea enuntata se numeste injectiva.)(4) Exista M ∈ R astfel ıncat, pentru orice x ∈ A, f(x) ≤ M . (O functie

f : A → R cu proprietatea enuntata se numeste marginita superior pe A,iar numarul M ∈ R ca mai sus se numeste margine superioara pentru fpe multimea A.)

(5) Exista m ∈ R astfel ıncat, pentru orice x ∈ A, m ≤ f(x). (O functief : A → R cu proprietatea enuntata se numeste marginita inferior pe A,iar numarul m ∈ R ca mai sus se numeste margine inferioara pentru f pemultimea A.)

(6) Exista M > 0 astfel ıncat, pentru orice x ∈ A, |f(x)| ≤ M . (O functief : A → R cu proprietatea enuntata se numeste marginita pe A, iarnumarul M ∈ R ca mai sus se numeste margine pentru f pe multimea A.)

(7) Pentru orice x ∈ R exista r > 0 si M > 0 astfel ıncat, pentru oricey ∈ (x − r, x + r), |f(y)| ≤ M . (O functia f : R → R cu proprietateaenuntata se numeste local marginita pe A.)

(8) Pentru orice ε > 0 exista k(ε) ∈ N astfel ıncat, pentru orice n ∈ N,n ≥ k(ε), avem |an − a| ≤ ε. (Conditia de convergenta cu ε.)

Introducere 19

(9) Pentru orice n ∈ N avem an ≤ an+1. (Un sir (an)n∈N cu proprietatea demai sus se numeste monoton crescator.)

(10) Pentru orice ε > 0 exista k(ε) ∈ N astfel ıncat, pentru orice n,m ∈ Ncu n ≥ k(ε) si m ≥ k(ε), sa avem |an − am| ≤ ε. (Un sir (an)n∈N cuproprietatea de mai sus se numeste sir Cauchy sau sir fundamental.)

(11) Pentru orice ε > 0 exista δ(ε) > 0 astfel ıncat, pentru orice x, y ∈ [ a, b ]cu |x− y| ≤ δ(ε), sa avem |f(x)− f(y)| ≤ ε. (O functia f : [ a, b ] → R cuproprietatea de mai sus se numeste uniform continua pe [ a, b ].)

(12) Prin orice punct din planul π trece o dreapta si numai una paralela cu odreapta d care nu contine punctul.

(13) Prin orice doua puncte distincte A,B de pe o sfera, care nu sunt diametralopuse, se poate duce un cerc si numai unul singur de lungime maxima.

(14) In orice triunghi exista macar doua unghiuri ascutite.(15) Pentru orice plan π si orice punct din spatiu se poate duce o singura

perpendiculara pe plan.(16) Pentru orice cerc C(O, r) exista cel putin un patrulater ınscris ın el.

Exercitiul 1.9.3. Sa se reformuleze, utilizand cuantificatorii ∃ si ∀ si conec-torii logici ∨, ∧, →, ¬ urmatoarele afirmatii ın limbaj logic si, apoi, sa se formulezenegatiile acestor afirmatii.

(1) a = max{a1, a2, . . . , an}. Aceasta ınseamna caexista i ∈ {1, 2, . . . , n} cu a = ai si aj ≤ a pentru orice j ∈ {1, 2, . . . , n}.

(2) a = min{a1, a2, . . . , an}. Aceasta ınseamna caexista i ∈ {1, 2, . . . , n} cu a = ai si aj ≥ a pentru orice j ∈ {1, 2, . . . , n}.

(3) Sirul (an)n este marginit superior. Aceasta ınseamna caexista M ∈ R astfel ıncat an ≤ M pentru orice n ∈ N.

(4) Sirul (an)n este marginit inferior. Aceasta ınseamna caexista m ∈ R astfel ıncat an ≥ m pentru orice n ∈ N.

(5) Sirul (an)n este crescator. Aceasta ınseamna caan ≤ an+1 pentru orice n ∈ N.

(6) Sirul (an)n este descrescator. Aceasta ınseamna caan ≥ an+1 pentru orice n ∈ N.

(7) Sirul (an)n este strict crescator. Aceasta ınseamna caan < an+1 pentru orice n ∈ N.

(8) Sirul (an)n este strict descrescator. Aceasta ınseamna caan > an+1 pentru orice n ∈ N.

(9) Numarul real a este limita sirului (an)n. Aceasta ınseamna ca pentru oriceV ∈ V (a), exista k ∈ N astfel ıncat pentru orice n ∈ N, n ≥ k rezultaan ∈ V .

(10) Sirul (an)n este convergent. Aceasta ınseamna caexista a ∈ R astfel ıncat limn an = a.

(11) Sirul (an)n are limita +∞. Aceasta ınseamna capentru orice a > 0, exista k ∈ N astfel ıncat pentru orice n ∈ N, n ≥ k

rezulta an ≥ a.(12) Sirul (an)n are limita −∞. Aceasta ınseamna ca

pentru orice b < 0, exista k ∈ N astfel ıncat pentru orice n ∈ N, n ≥ krezulta an ≤ a.

(13) Functia f : [ a, b ] → R este marginita pe [ a, b ]. Aceasta ınseamna caexista M ∈ R astfel ıncat |f(x)| ≤ M pentru orice x ∈ [ a, b ].


(14) Functia f : R → R este local marginita pe R. Aceasta ınseamna capentru orice x0 ∈ R exista δ > 0 si M ∈ R astfel ıncat |f(x)| ≤ M

pentru orice x ∈ [x0 − δ, x0 + δ ].(15) Functia f : R → R este crescatoare. Aceasta ınseamna ca

pentru orice x ∈ R si orice y ∈ R cu x ≤ y rezulta f(x) ≤ f(y).(16) Functia f : R → R este descrescatoare. Aceasta ınseamna ca

pentru orice x ∈ R si orice y ∈ R cu x ≤ y rezulta f(x) ≥ f(y).(17) Functia f : R → R este monotona. Aceasta ınseamna ca

f : R → R este crescatoare sau descrescatoare.(18) Functia f : E → R este continua ın x0 ∈ E. Aceasta ınseamna ca

fie x0 este izolat, fie x0 este punct de acumulare al multimii E silimx→x0

f(x) = f(x0).(19) Numarul T ∈ R este perioada a functiei f : R → R. Aceasta ınseamna ca

f(x+ T ) = f(x) pentru orice x ∈ R.(20) Functia f : R → R este periodica. Aceasta ınseamna ca

f : R → R are o cea mai mica perioada strict pozitiva.(21) Functia f : R → R este para. Aceasta ınseamna ca

f(x) = f(−x) pentru orice x ∈ R.(22) Functia f : R → R este impara. Aceasta ınseamna ca

f(x) = −f(−x) pentru orice x ∈ R.(23) Fie f : E → R si fie x0 un punct de acumulare al lui E. Daca exista

M ∈ R astfel ıncat f(x) ≤ M pentru orice x ∈ E si limx→x0 f(x) = ℓatunci ℓ ≤ M .

(24) Orice polinom cu coeficienti ın corpul C al numerelor complexe are celputin o radacina ın C.

(25) Fie V un spatiu liniar peste R. Vectorii x1, x2, . . . , xn din V sunt liniarindependenti. Aceasta ınseamna ca

pentru orice λ1, λ2, . . . , λn, din R din∑n

i=1 λixi = 0 rezulta λ1 =λ2 = · · · = λn = 0.

(26) Fie V un spatiu liniar peste R. Vectorii x1, x2, . . . , xn din V sunt liniarindependenti daca orice vector x ∈ V se exprima ın mod unic sub formax =

∑ni=1 λixi, cu λ1, λ2, . . . , λn din R.

(27) Fie V un spatiu liniar peste R. Familia {x1, x2, . . . , xn} ⊆ V este degeneratori. Aceasta ınseamna ca

pentru orice vector x ∈ V exista λ1, λ2, . . . , λn din R astfel ıncatx =

∑ni=1 λixi.

1.10. Solutii

Exercitiul 1.3.2

(1) (i) numele conceptului definit:dreptunghi(ii) genul proxim: patrulater(iii) diferenta specifica: proprietatea de a avea trei unghiuri drepte.

(2) (i) numele conceptului definit:functie injectiva(ii) genul proxim: functie(iii) diferenta specifica: proprietatea de a avea transforma orice doua puncte

distincte din domeniu ın doua puncte distincte din codeomeniu.(3) (i) numele conceptului definit:grup comutativ

(ii) genul proxim: grup

Introducere 21

(iii) diferenta specifica: proprietatea ca pentru orice doua elemente x, ydin G sa avem x ◦ y = y ◦ x.

(4) (i) numele conceptului definit:numar prim(ii) genul proxim: numar natural(iii) diferenta specifica: proprietatea de a fi mai mare decat 1, ai carui

singuri divizori sunt 1 si numarul ınsusi.(5) multime ınchisa

genul proxim: multimi de numere reale(ii)(iii) diferenta specifica: proprietatea de a fi complementara unei multimi

deschise.(6) (i) numele conceptului definit: doua drepte paralele

(ii) genul proxim: multimea prechilor de drepte(iii) diferenta specifica: proprietatea de a fi coplanare si nu au niciun

punct ın comun.(7) (i) numele conceptului definit: trei drepte concurente

(ii) genul proxim: multimea tripletelor de drepte(iii) diferenta specifica: proprietatea de a avea ın comun un punct si numai

unul singur.

Exercitiul 1.3.2

(1) Este o propozitie care exprima aceeasi constatare ca si ”Toti pomii suntverzi” sau cu ”Orice pom este verde”. Aceasta propozitie are valoarea deadevar 0 ıntrucat exista macar un pom care nu are culoarea verde.

(2) Nu este o propozitie ın sensul logicii deoarece nu i se poate atribui o valoarede adevar. Din punctul de vedere gramatical, aceasta este o propozitieimperativa.

(3) Este o propozitie care exprima aceeasi constatare ca si ”Orice patrat aretoate laturile congruente”, a carei valoare de adevar este 1.

(4) Este o propozitie care exprima aceeasi constatare ca si ”Orice patrat areexact doua laturi congruente”, acarei valoare de adevar este 0.

(5) Nu este o propozitie ın sensul logicii deoarece nu i se poate atribui o valoarede adevar. Cu toate acestea, din punct de vedere gramatical, enuntul esteo propozitie interogativa.

(6) Nu este o propozitie ın sensul logicii deoarece nu i se poate atribui o valoarede adevar. Cu toate acestea, din punct de vedere gramatical, enuntul esteo propozitie interogativa.

(7) Este o propozitie carei valoare de adevar este 0 deoarece exista macar ofunctie continua care nu este derivabila. Un exemplu de astfel de functieeste functia modul care este continua pe R, dar nu este derivabila ın 0.

(8) Este o propozitie care exprima aceeasi constatare ca si precedenta.(9) Este o propozitie a carei valoare de adevar este 1. Vezi exemplul de la

punctul (7).(10) Este o propozitie care exprima aceeasi constatare ca si cea de la punctul

(7), a carei valoare de adevar este 0 deoarece exista macar o functie con-tinua care este derivabila. Un exemplu de estfel de functie este f : R → R,f(x) = x pentru orice x ∈ R.

(11) Este o propozitie care exprima aceeasi constatare ca si cea de la punc-tul (7), a carei valoare de adevar este 0 deoarece exista macar o functiecontinua care este derivabila.


(12) Este o propozitie a carei valoare de adevar este 0. Vezi exemplul de lapunctul (7).

(13) Nu este o propozitie deoarece contine variabila libera x, i.e. nelegata prin

cuantificatorul oricare sau exista. In plus, multimea ei de apartenenta (deexemplu: x ∈ N, sau x ∈ Z sau x ∈ Q, s.a.m.d.) nu este precizata.

(14) Nu este o propozitie deoarece contine variabila libera x, i.e. nelegata princunatificatorul oricare sau exista.

(15) Nu este o propozitie deoarece contine doua variabile libere: a si b, nelegateprin niciunul din cunatificatorul oricare sau exista.

(16) Nu este o propozitie deoarece contine doua variabile: una legata prin cu-natificatorul oricare, si anume a si celalta libera, si anume b

(17) Este o propozitie a carei valoare de adevar este 1. Aici, ambele variabilea si b sunt legate.

(18) Nu este o propozitie deoarece contine doua variabile libere: x si y, nelegateprin niciunul din cunatificatorul oricare sau exista.

(19) Nu este o propozitie deoarece contine variabila libera x, i.e. nelegata princunatificatorul oricare sau exista.

Exercitiul 1.5.1

(1) (p ∧ q) → r.(2) (q ∧ r) → p.

(3) Daca ın triunghiul ∆ABC m(C) = π4 si m(B) = π

4 atunci m(A) = π2 .

(4) Daca ın triunghiul ∆ABC m(C) = π4 si m(B) = π

4 atunci m(A) = π2 .

Exercitiul 1.5.2 Fie p = “Ana are mere”, q = “Ana este blonda” si r = “Anacanta frumos.” Traduceti ın limbaj natural urmatoarele propozitii:

(1) Daca Ana este blonda atunci ea canta frumos.(2) Ana are mere si este blonda.(3) Ana nu este blonda.(4) Nu este adevarat ca Ana are mere sau ca ea canta frumos. Aceasta propozitie

este echivalenta logic cu: Ana nu are mere si nu canta frumos.(5) (¬p) ∨ (¬q)(6) (r ∧ q) → p(7) (r ∧ q) ∨ p(8) r ∧ (q ∨ p)(9) r ↔ (p ∧ q)

(10) (r → q) ∧ (r → p)(11) r → (q ∧ p)(12) (p ∧ (¬q)) ↔ (r ∨ (¬p))Exercitiul 1.5.3 Scrieti expresiile logice corespunzatoare enunturilor:

(1) Ana nu este blonda, dar canta frumos.(2) Ana nu are mere, si nu este blonda sau canta frumos.(3) Ana nu are mere si nu este blonda, sau canta frumos.(4) Nu este adevarat ca Ana este blonda sau are mere.(5) Nu este adevarat ca Ana este blonda, sau are mere.(6) Ana are mere si este blonda, sau are mere si canta urat.(7) Daca Ana are mere si este blonda, atunci ea canta frumos.(8) O conditie necesara ca Ana sa cante frumos este sa fie blonda.(9) O conditie suficienta ca Ana sa cante frumos este sa fie blonda.

Introducere 23

(10) Chiar daca Ana canta frumos, nu are mere.(11) Ana are mere daca este blonda, si nu canta urat daca are mere.

Exercitiul 1.5.4 Fie p, q, r propozitii. Sa se demonstreze ca:

(1) p ⇒ p ∨ q(2) (p ∧ q) ⇒ p(3) ¬ (p → q) ⇒ p(4) (p → q) ∧ (p → ¬q) ⇒ ¬p(5) (p → (q → r)) ≡ (p ∧ q) → r(6) (p → q) ⇔ (¬q → ¬p)(7) (p ∨ q) → r ⇔ (p → r) ∧ (q → r).

Exercitiul 1.5.5 Formulati negatia fiecareia dintre propozitiile:

(1) Patrulaterul ABCD este romb si are aria de 2m2.(2) Numarul 8 este par si x8 = 2.(3) Raza sferei este din [ 1, 3 ] si baza conului este pe sfera(4) Ecuatia x2 + 2x = 0 cu x ∈ N are solutia x = 0 si solutia x = −2.(5) Functia f este pozitiva pe (0, 1) si se anuleaza ın x = 0 si x = 1.(6) Patrulaterul ABCD este patrat sau romb.(7) Functia exponentiala este strict crescatoare sau strict descrescatoare.(8) Sirul (an)n∈N este monoton crescator sau monoton descrescator.(9) Functia f este continua si monotona.

(10) ^ABC este drept sau ^BCA este drept.

Exercitiul 1.9.1 [5] Se considera urmatoarele predicate (se presupune ca vari-abilele iau valori ın multimea oamenilor):

B (x) =“x este un barbat”F (x) =“x este o femeie”xTy =“x este mai tanar decat y”xCy =“x este copilul lui y”xMy =“x este casatorit cu y”I (x) =“x locuieste la Iasi”D (x) =“x locuieste la Dej”Folosind notatiile de mai sus, sa se scrie expresiile ın limbaj formal pentru

urmatoarele propozitii sau predicate:

(1) x este casatorit.(2) Fiecare este mai tanar decat parintii sai.(3) Fiecare este mai tanar decat bunicii sai.(4) Oricine care are un tata, are si o mama.(5) Exista un om cu o nora mai ın varsta decat el.(6) x si y sunt frati (ın sensul si de mama si de tata).(7) Daca exista o femeie la Iasi cu un frate la Dej, atunci exista un barbat la

Dej cu o sora la Iasi.(8) Un barbat casatorit poate sa nu locuiasca la Iasi.(9) Nu fiecare femeie din Iasi nu are un fiu la Dej.

(10) Toti copiii lui x sunt casatoriti.(11) Exista cineva ai carui copii sunt toti casatoriti.(12) Fiecare copil al lui x este casatorit cu un copil al lui y.(13) Exista un copil al lui x care nu este casatorit cu un copil al lui y.


(14) Exista doua persoane astfel ıncat fiecare copil al uneia dintre ele estecasatorit cu un copil al celeilalte.

(15) x si y sunt veri.Sa se traduca ın limbaj natural:

(16) ∀x∀y [(xMy ∧B (x)) → F (y)] .(17) ∃x∃y [B (x) ∧ F (y) ∧ xMy ∧ ∀z (zCy → ¬ (zCx))] .(18) ∃y (F (y) ∧ xMy) ∧ ∃z (F (z) ∧ yCz) ∧ zTx.

Exercitiul 1.9.2 Sa se reformuleze propozitiile de mai jos ın limbaj matematic(LM) utilizand cuantificatorii ∀ si ∃, sa se precizeze negatiile lor ın limbaj matem-atic (NLM) si apoi sa se formuleze negatiile gasite ın limbajul natural (NLN).

Exemplu. Propozitia: “pentru orice x ∈ A exista y ∈ B astfel ıncat f(x) = y” sereformuleaza ın limbajul matematic (LM) prin: “(∀x ∈ A) (∃y ∈ B) (f(x) = y)”,propozitie a carei negatie ın limbajul matematic (NLM) este “(∃x ∈ A) (∀y ∈ B)(f(x) = y)” care, ın limbajul natural (NLN), are formularea: “exista x ∈ A astfelıncat, pentru orice y ∈ B, f(x) = y.”

(1) Exista a ∈ A astfel ıncat f(a) = b. (Ecuatia f(x) = b are solutia a ∈ A.)(2) Pentru orice y ∈ B exista x ∈ A astfel ıncat f(x) = y. (O functie f : A →

B cu proprietatea enuntata se numeste surjectiva.)(3) Pentru orice x, y ∈ A, cu x = y, avem f(x) = f(y). (O functie f : A → B

cu proprietatea enuntata se numeste injectiva.)(4) Exista M ∈ R astfel ıncat, pentru orice x ∈ A, f(x) ≤ M . (O functie

f : A → R cu proprietatea enuntata se numeste marginita superior pe A,iar numarul M ∈ R ca mai sus se numeste margine superioara pentru fpe multimea A.)

(5) Exista m ∈ R astfel ıncat, pentru orice x ∈ A, m ≤ f(x). (O functief : A → R cu proprietatea enuntata se numeste marginita inferior pe A,iar numarul m ∈ R ca mai sus se numeste margine inferioara pentru f pemultimea A.)

(6) Exista M > 0 astfel ıncat, pentru orice x ∈ A, |f(x)| ≤ M . (O functief : A → R cu proprietatea enuntata se numeste marginita pe A, iarnumarul M ∈ R ca mai sus se numeste margine pentru f pe multimea A.)

(7) Pentru orice x ∈ R exista r > 0 si M > 0 astfel ıncat, pentru oricey ∈ (x − r, x + r), |f(y)| ≤ M . (O functia f : R → R cu proprietateaenuntata se numeste local marginita pe A.)

(8) Pentru orice ε > 0 exista k(ε) ∈ N astfel ıncat, pentru orice n ∈ N,n ≥ k(ε), avem |an − a| ≤ ε. (Conditia de convergenta cu ε.)

(9) Pentru orice n ∈ N avem an ≤ an+1. (Un sir (an)n∈N cu proprietatea demai sus se numeste monoton crescator.)

(10) Pentru orice ε > 0 exista k(ε) ∈ N astfel ıncat, pentru orice n,m ∈ Ncu n ≥ k(ε) si m ≥ k(ε), sa avem |an − am| ≤ ε. (Un sir (an)n∈N cuproprietatea de mai sus se numeste sir Cauchy sau sir fundamental.)

(11) Pentru orice ε > 0 exista δ(ε) > 0 astfel ıncat, pentru orice x, y ∈ [ a, b ]cu |x− y| ≤ δ(ε), sa avem |f(x)− f(y)| ≤ ε. (O functia f : [ a, b ] → R cuproprietatea de mai sus se numeste uniform continua pe [ a, b ].)

(12) Prin orice punct din planul π trece o dreapta si numai una paralela cu odreapta d care nu contine punctul.

(13) Prin orice doua puncte distincte A,B de pe o sfera, care nu sunt diametralopuse, se poate duce un cerc si numai unul singur de lungime maxima.

Introducere 25

(14) In orice triunghi exista macar doua unghiuri ascutite.(15) Pentru orice plan π si orice punct din spatiu se poate duce o singura

perpendiculara pe plan.(16) Pentru orice cerc C(O, r) exista cel putin un patrulater ınscris ın el.

Exercitiul 1.9.3 Sa se reformuleze, utilizand cuantificatorii ∃ si ∀ si conectoriilogici ∨, ∧, →, ¬ urmatoarele afirmatii ın limbaj logic si, apoi, sa se formulezenegatiile acestor afirmatii.

(1) Formularea afirmatiei ın limbaj logic este

(a = max{a1, a2, . . . , an} daca (∃i ∈ {1, 2, . . . , n})(∀j ∈ {1, 2, . . . , n})(a = ai)∧(aj ≤ a).

Negatia este

(a = max{a1, a2, . . . , an} daca (∀i ∈ {1, 2, . . . , n})(∃j ∈ {1, 2, . . . , n})(a = ai)∨(aj > a).

(2) Formularea afirmatiei ın limbaj logic este

(a = min{a1, a2, . . . , an} daca (∃i ∈ {1, 2, . . . , n})(∀j ∈ {1, 2, . . . , n})(a = ai)∧(aj ≥ a).

Negatia este

(a = min{a1, a2, . . . , an} daca (∀i ∈ {1, 2, . . . , n})(∃j ∈ {1, 2, . . . , n})(a = ai)∨(aj < a).

(3) Sirul (an)n este marginit superior. Aceasta ınseamna caexista M ∈ R astfel ıncat an ≤ M pentru orice n ∈ N.

(4) Sirul (an)n este marginit inferior. Aceasta ınseamna caexista m ∈ R astfel ıncat an ≥ m pentru orice n ∈ N.

(5) Sirul (an)n este crescator. Aceasta ınseamna caan ≤ an+1 pentru orice n ∈ N.

(6) Sirul (an)n este descrescator. Aceasta ınseamna caan ≥ an+1 pentru orice n ∈ N.

(7) Sirul (an)n este strict crescator. Aceasta ınseamna caan < an+1 pentru orice n ∈ N.

(8) Sirul (an)n este strict descrescator. Aceasta ınseamna caan > an+1 pentru orice n ∈ N.

(9) Numarul real a este limita sirului (an)n. Aceasta ınseamna ca pentru oriceV ∈ V (a), exista k ∈ N astfel ıncat pentru orice n ∈ N, n ≥ k rezultaan ∈ V .

(10) Sirul (an)n este convergent. Aceasta ınseamna caexista a ∈ R astfel ıncat limn an = a.

(11) Sirul (an)n are limita +∞. Aceasta ınseamna capentru orice a > 0, exista k ∈ N astfel ıncat pentru orice n ∈ N, n ≥ k

rezulta an ≥ a.(12) Sirul (an)n are limita −∞. Aceasta ınseamna ca

pentru orice b < 0, exista k ∈ N astfel ıncat pentru orice n ∈ N, n ≥ krezulta an ≤ a.

(13) Functia f : [ a, b ] → R este marginita pe [ a, b ]. Aceasta ınseamna caexista M ∈ R astfel ıncat |f(x)| ≤ M pentru orice x ∈ [ a, b ].

(14) Functia f : R → R este local marginita pe R. Aceasta ınseamna capentru orice x0 ∈ R exista δ > 0 si M ∈ R astfel ıncat |f(x)| ≤ M

pentru orice x ∈ [x0 − δ, x0 + δ ].(15) Functia f : R → R este crescatoare. Aceasta ınseamna ca

pentru orice x ∈ R si orice y ∈ R cu x ≤ y rezulta f(x) ≤ f(y).


(16) Functia f : R → R este descrescatoare. Aceasta ınseamna capentru orice x ∈ R si orice y ∈ R cu x ≤ y rezulta f(x) ≥ f(y).

(17) Functia f : R → R este monotona. Aceasta ınseamna caf : R → R este crescatoare sau descrescatoare.

(18) Functia f : E → R este continua ın x0 ∈ E. Aceasta ınseamna cafie x0 este izolat, fie x0 este punct de acumulare al multimii E si

limx→x0f(x) = f(x0).

(19) Numarul T ∈ R este perioada a functiei f : R → R. Aceasta ınseamna caf(x+ T ) = f(x) pentru orice x ∈ R.

(20) Functia f : R → R este periodica. Aceasta ınseamna caf : R → R are o cea mai mica perioada strict pozitiva.

(21) Functia f : R → R este para. Aceasta ınseamna caf(x) = f(−x) pentru orice x ∈ R.

(22) Functia f : R → R este impara. Aceasta ınseamna caf(x) = −f(−x) pentru orice x ∈ R.

(23) Fie f : E → R si fie x0 un punct de acumulare al lui E. Daca existaM ∈ R astfel ıncat f(x) ≤ M pentru orice x ∈ E si limx→x0

f(x) = ℓatunci ℓ ≤ M .

(24) Orice polinom cu coeficienti ın corpul C al numerelor complexe are celputin o radacina ın C.

(25) Fie V un spatiu liniar peste R. Vectorii x1, x2, . . . , xn din V sunt liniarindependenti. Aceasta ınseamna ca

pentru orice λ1, λ2, . . . , λn, din R din∑n

i=1 λixi = 0 rezulta λ1 =λ2 = · · · = λn = 0.

(26) Fie V un spatiu liniar peste R. Vectorii x1, x2, . . . , xn din V sunt liniarindependenti daca orice vector x ∈ V se exprima ın mod unic sub formax =

∑ni=1 λixi, cu λ1, λ2, . . . , λn din R.

(27) Fie V un spatiu liniar peste R. Familia {x1, x2, . . . , xn} ⊆ V este degeneratori. Aceasta ınseamna ca

pentru orice vector x ∈ V exista λ1, λ2, . . . , λn din R astfel ıncatx =

∑ni=1 λixi.

Bibliografie

[1] M. Becheanu et al., Algebra pentru perfectionarea profesorilor, Ed. didactica si pedagogica,

Bucuresti, 1983.[2] O. Becker, Fundamentele matematicii, Editura Stiintifica, Bucuresti, 1968.

[3] E.D. Bloch, Proofs and fundamentals; a first course in mathematics, Birkhauser Boston,

2000.[4] A. Dumitriu, Istoria Logicii, Editia a II-a, Editura Didactica si Pedagogica, 1975, 1212pp.

[5] H. Freudenthal, Limbajul logicii matematice, Seria Matematici Moderne Aplicate, Editura

Tehnica, Bucuresti 1973.[6] P.R. Halmos, Naive set theory, Undergraduate texts in Mathematics, Springer Verlag New

York-Heidelberg-Berlin, 1974.[7] I.D. Ion, Radu, N. Algebra, Ed. Didactica si pedagogica, Bucuresti, 1981.

[8] G. Klaus, Logica moderna, Editura Stiintifica si Enciclopedica, Bucuresti, 1977.

[9] I.A. Lavrov, L.L. Maksimova, Probleme de teoria multimilor si logica matematica, SeriaCulegeri de probleme de matematica si fizica, Editura tehnica, Bucuresti 1974.

[10] Yu.I. Manin, A Course in Mathematical Logic, Springer Verlag, New York, 1977.

[11] Miron[12] Gr.C. Moisil, Elemente de logica matematica si teoria multimilor, M Matematica Enciclo-

pedia de buzunar, Editura Stiintifica, Bucuresti, 1969.

[13] C. Nastasescu, Introducere ın teoria multimilor, Ed. Didactica si pedagogica, Bucuresti, 1974.[14] C. Nastasescu, Teoria dimensiunii ın algebra necomutativa, Ed. Academiei R.S.R., Bucuresti,

1983.

[15] C. Nita, T. Spircu, Probleme de structuri algebrice, Ed. Tehnica, Bucuresti, 1974.[16] P. S. Novikov, Elemente de logica matematica, Editura Stiintifica, Bucuresti, 1966.

[17] M. Reghis, Elemente de teoria multimilor si logica matematica, Ed. Facla, Timisoara, 1981.[18] A. Scorpan, Introducere ın teoria axiomatica a multimilor, Editura Universitatii Bucuresti,

1996.

[19] Izu Vaisman, Fundamentele matematicii, Editura Didactica si Pedagogica, Bucuresti, 1968.

83

Logică şi teoria mulţimilor, partea 1

Documents

Transcript of Logică şi teoria mulţimilor, partea 1