ELEMENTE DE LOGIC MATEMATIC

Limbajul matematic riguros imetodele raionamentului logic, folosite n rezolvarea de exerciii i probleme, dar i n parcurgerea drumului de la ipotez la concluzie,ofer certitudinea c deduciile abordate sunt corecte.Cunoaterea operaiilor logice elementare (negaia, disjuncia, conjuncia, implicaia, echivalena) estecerin de maxim importan n construcia propoziiilor matematice.

DEFINITII:

Propozitie: Un enunt care afirma sau neaga ceva si care este fie adevarat, fiefals. Distingem 2 tipuri de propozitii:1) Propozitie simpla:propozitie care nu comporta decat un singur subiect, un singur verb si un singur atribut.Exemplu: "Numarul 24 este divizibil cu 8" (propozitie, evident, adevarata).2) Propozitie compusa:propozitie obtinuta prin combinarea de propozitii simple, cu ajutorul conectorilor logici:negatie, disjunctiesiconjunctie.Exemplu: "(Ecuatia x + 1 = 0 are radacini reale in multimea numerelor reale) sau (25 este patrat perfect)" (disjunctie intre unpredicatfals si opropozitie adevarata).

Valoare de adevar:Este proprietatea unei propozitii (p) de a fi adevarata sau falsa. Se noteaza cu v(p). v(p) = 1 (sau A) daca propozitia p este adevarata v(p) = 0 (sau F) daca propozitia p este falsa.

Predicat(propozitie cu variabile, sau propozitie deschisa):Propozitie a careivaloare de adevar depinde de valorile atribuite variabilelor; in definirea unui predicat trebuie specificata intotdeauna si multimea parcursa de variabila (variabile), numita si universul discursului.Exemplu: "Ecuatia 2x + 10 = 0, unde x apartine multimii numerelor reale"este un predicat cu o singura variabila (numit sipredicat unar), care devine o propozitie adevarata pentru x = -5 (avand, deci,valoarea de adevar 1), sau o propozitiefalsa pentru orice alta valoare atribuita lui x (avand valoarea de adevar 0).Observatie:Multimea valorilor care, atribuite variabilelor predicatului, confera acestuia statut depropozitie adevarata, se numestemultimea de adevara predicatului respectiv.

Cuantificatorul existential:Propozitia "exista cel putin un x, astfel incat p(x)" se numeste propozitie existentiala,asociata predicatului p(x).Notatie folosita:Simbolulse citeste "exista (cel putin)" si senumeste cuantificatorexistential.

Cuantificatorul universal:Propozitia "oricare ar fi x din X, are loc p(x)" (X fiind o multime nevida, careia ii apartine variabila x) se numestepropozitie universala,asociata predicatului p(x).Notatie folosita:Simbolulse citeste "oricare ar fi" si senumestecuantificator universal.

OPERATIILOGICE ELEMENTARE:

1) Negatia unei propozitii:Fiind data o propozitie notata cu p, numimnegatiasa(saucontrarasa) acea propozitie, notata cusau p (a se citi "non-p"), careeste falsa daca peste adevarata si care este adevarata daca peste falsa. Sugestiv,aceasta definitiepoate fi ilustrata prin urmatoareatabla de adevar:

10

01

2)Disjunctia propozitiilor:Fiind date propozitiile p si q, numimdisjunctiaacestora aceapropozitie, notata cu (a se citi "psauq") si a carei valoare de adevar rezulta din tabla de adevar:

11 1

10 1

01 1

00 0

Observatii:a) Disjunctia este falsa daca ambele propozitii sunt false si adevarata in celelalte cazuri. b) Disjunctia a n propozitii este falsa daca toate propozitiile sunt false si adevarata in rest.

3) Conjunctia propozitiilor:Fiind date 2 propozitii p si q, numimconjunctialor, notata cu ( a se citi "psiq")acea propozitie definita prin urmatoareatabla de adevar:

111

100

010

000

Observatii:a) Conjunctia este adevarata cand ambele propozitii sunt adevarate si falsa in rest.b) Conjunctia a n propozitii este adevarata cand toate propozitiile sunt adevarate si falsa in celelalte cazuri.

4)Implicatia propozitiilor:Propozitia (a se citi"p implicaq") se numesteimplicatie;p se numesteipoteza, iar q se numesteconcluzie.Rezulta urmatoareatabla de adevar:

1101

100 0

0111

0011

Observatii:a) Implicatia "p implica q", foarte des utilizata in demonstratii matematice, mai are si urmatoarele interpretari: Daca p, atunci q; peste conditiesuficientapentru q; q este conditienecesarapentru p.b) Implicatia "p implica q" este structura logica a tuturor teoremelor directe (ipoteza pare drept consecintaconcluzia q).c) Din tabla de adevar se constata ca: O implicatie, cu ipoteza adevarata,este adevarata numai daca si concluzia este adevarata; O implicatie este falsa intr-un singur caz: ipoteza adevarata si concluzie falsa! Falsul implica orice! (foarte important de stiut acest lucru: a nu se construirationamente pornind de la premize false!).

5)Echivalenta propozitiilor:Propozitiap q(ase citi "p este echivalent cu q") reprezinta conjunctia a douaimplicatii, anume:(p = > q) si (q = > p),avandtabla de adevar:

11111

10 010

01100

00111

Observatii:a) Doua propozitii sunt echivalente daca si numai daca ambele au aceeasi valoare de adevar (ambele adevarate sau ambele false).b)Se spune ca propozitiile "p si q sunt echivalente",sau "propozitia p este conditie necesara si suficienta pentru propozitia q", sau "p daca si numai daca q".c) Daca oteorema directaare structura logica "p implica q", atuncireciprocasa (adevarata sau falsa!)are structura "q implica p".Deci o teorema care admitereciprocareprezinta, din punct de vedere logic, o echivalenta intre ipoteza si concluzie.

Teorema directa este echivalenta cu contrara reciprocei(teorema directa este adevarata daca si numai daca este adevarata contrara reciprocei): Observatie:Aceasta echivalenta logica sta la baza metodei de demonstratie prinreducere la absurd,folosita mai ales in cazul cand demonstratia teoremei directa estedificila.

EXERCITIUL 1Suport teoretic: Negatiadisjunctiei,negatia conjunctiei,tabla adevar.Enunt: Sa se demonstreze ca:1)Negatia unei disjunctii a 2 propozitii este echivalenta cuconjunctia negatiiloracestora, anume:

2)Negatia unei conjunctii a 2 propozitii este echivalenta cu disjunctia negatiiloracestora, anume:

Rezolvare: Demonstratia se face cu ajutorul tablelor deadevar:1)

11 1 000 0

10 1 001 0

01 1 01 0 0

00 0 111 1

2)

11 1 000 0

10 0 101 1

01 011 01

00 0 111 1

Cele doua echivalente rezulta in urma compararii valorilor de adevar din coloanele 4 si7 ale tablelor de adevar de mai sus.Observatie:Echivalentele din aceasta aplicatie sunt cunoscute sub numele de Legilelui DeMorgan.EXERCITIUL 2Suport teoretic: Implicatii,echivalente logice,inductia matematica,divizibilitate.Enunt: Sa se demonstreze ca pentru orice numar natural n, expresia este divizibila cu 6.Demonstratie: Descompunerea in factori a expresiei esteE(n) = n(n+1)(n+2) si, cum primii doi factori sunt numere naturale consecutive, deducem ca E(n) este divizibila cu 2. (1)Fie propozitia P(n): n(n+2) = M3(multiplu de 3), pe care s-o demonstram prininductie matematica. Etapa verificarii: P(0) = 0 = M3, adevarat; Etapa demonstratiei implicatiei P(k) => P(k+1), pentru orice k natural:Avem P(k): k(k+ 2) = M3siP(k + 1): (k + 1)[(k + 1) +2] = M3.Deci P(k) =>(k + 1)[(k + 1) +2] =... = k(k + 2) + 3(k +k +1) = M3+ M3= M3; implicatia P(k) => P(k+1) este, deci, adevarata pentru oricek natural. (2)Din (1) si (2), deducem ca propozitia P(n) este adevarata pentru orice n natural, conformprincipiului inductieicomplete.

EXERCITIUL 3Suport teoretic: Numere irationale,divizibilitateain Z,numere prime,reducere la absurd.Enunt: Sa se demonstreze ca numarul esteirational.Demonstratie:Vom folosimetoda reducerii la absurd:presupunem ca numarul a este rational, adica exista doua numere intregi m si n, evident nenule, astfel incat a = m/n; fara a restrange generalitatea, putem considera m,n N* si (m,n) = 1. Evident:< = >2013n = m ; (1).Cum m si n sunt numere prime intreele,are loc implicatia 2013|m= >2013|m(2013 divide m) (*) < = > exista k N*,astfelincat m = 2013k; (2).Din (1) si (2) rezulta 2013n = 2013k < = > n = 2013k = > 2013|n (2013 divide n) (**).Din (*) si (**) rezulta ca numerele m si n nu sunt prime intre ele (cel mai mare divizorcomun al lor este mai mare decat 1). Contradictie, deci presupunerea ca numarul a este rational este falsa; prin urmare: a R \ Q(numarul a este irational).

EXERCITIUL 4Suport teoretic: Conditie necesara,suficienta,distributivitate,legide compozitie.Enunt: Sedaulegiledecompozitie

oricare ar fix,y R, a,b R.Sasedetermineconditianecesarasisuficienta pentrucalegeasa fie distributiva fata de legeaRaspuns:a = a + b.Rezolvare:Necesitateae probata prin implicatia(x y) z = (x z) (y z), x, y, z = a + bin timp cesuficientaprin implicatia = a + b (x y) z = (x z) (y z), x, y, z Prima implicatie se bazeaza pe definitia distributivitatii si legile date, a doua incepe prin a scrie legeasub forma

si, apoi, se incheie prin verificarea distributivitatii.1