Drago-Ptru Covei Gheorghe Caralicea-Mrculescu Vasile Lupulescu

MATEMATIC Pentru institutori (nvtori) Refereni tiinifici: Prof. univ. dr. GeorgeVraciuConf. univ. dr. Ion Chiriac Tehnoredactare computerizat: Costin Covei Editura: SITECH ISBN: P73-944-1 2005 -2--3-Prezentare Aceastlucrareseadreseaznmodspecialstudenilordela specializarea: Pedagogia nvmntului primar i precolari are scopul deaconstituiunsprijinconsiderabilnsusinereadectreacetiaa examenelordelicenidedefinitivat.Dinacestmotivs-aavutnvedere caprinconinutulsulucrareasacopere,,Programadeperfecionare prin definitivat-partea de teoria mulimilor-, n vigoare, i extins pe cea de licen. Pentru ndeplinirea obiectivului, linia de conduit s-a ndreptat cu atenie spre prezentarea materialului tiinific de pe poziii de nelegere i independen fa de alte lucrri. Cunoaterea manualelor de liceu asigur parcurgerea lesnicioas a lucrrii. naceeaiidee,acoloundesuportulteoreticmergespreo accentuatabstractizare,aufostintroduseexempledeexerciiirezolvate. Pentrufixareacunotinelorfiecarecapitolconineiunsetdeexerciii propuse spre rezolvare. Lucrarea poate fi utilizat cu folos i de ctre cei care ntr-un mod sau altul vin n contact, la un anumit moment, cu teorii ale matematicii. -4--5- Capitolul I.Elemente de logic matematic Fiecaredisciplintiinificnecesitunraionamentclarilogic, precumioexprimareriguroasiprecis.Dinacestpunctdevedere,enunurile trebuie s fie lipsite de ambiguiti i contradicii. Prin enun vom nelege orice text lingvistic n care se afirm ceva cuprivirelaunulsaumaimulteobiecte.Oastfeldeafirmaiepoateavea saunuoanumesemnificaie.Obiectulsauobiecteleunuienuntrebuies aparinunuidomeniubinespecificat,numitdomeniul(mulimea)de referinalenunului.Dinpunctdevederesintactic,laoriceenunvom distinge:parteapredicativisubiectulsausubiectele.Subiectulsau subiecteleunuienunreprezintobiectulsauobiectelelacareserefer enunul. Unenunpoateaveatoatesubiecteledeterminatesaupoateavea unul sau mai multe subiecte nedeterminate. nfunciededomeniuldereferin,acelaienunpoatefi adevratsaufals sau nu i se poate stabili o valoare de adevr, adic este indecidabil. Enunul: p:"Mingea este rotund" esteadevratdacdomeniuldereferinestefotbalul,estefals dacdomeniuldereferinesteRugby-uliindecidabildacdomeniulde referin este Sportul. Unenuncutoatesubiecteledeterminatesenumetepropoziie dac este sau adevrat sau fals, nu i una i alta simultan. Un enun cu unul sau mai multe subiecte nedeterminate se numete predicat dac pentru orice valoaredatsubiectelornedeterminatedevinepropoziie.Subiectele nedeterminate ale unui predicat se numesc variabilele predicatului. nfunciedenumrulsubiectelornedeterminatedistingem predicate cu o variabil (unare), cu dou (binare), etc. Enunul p: "Oaia este carnivor"are domeniul de referin zoologia iar partea predicativ const din textul ". . .este carnivor" -6-Enunul are un singur subiect determinat: "Oaia", deci reprezint propoziie. Notaia p: semnific faptul c enunul " Oaia este carnivor "va fi reprezentat prin simbolul p. Enunul p(x): "x este divizibil prin 2" are domeniul de referin teoria numerelor iar partea predicativ const din textul ". . . este divizibil prin. . ." Enunul are dou subiecte:"x" i "2", dintre care unul nedeterminat. Observmcdndluixvalorienunuldevineadevratsaufals ns nu i una i alta simultan, prin urmare este un predicat cu o variabil. Enunul p(x,y): "x este divizibil prin y"esteunpredicatcudouvariabileavnddomeniuldereferinteoria numerelor. 1.Elemente de calculul propoziiilor Dup cum am vzut o propoziie este un enun cu toate subiectele determinate care este adevrat sau fals nu i una i alta simultan. Astfel de propoziii le numim propozitii simple.Opropoziiepoatefiadevratsaufalsdaccorespundesaunu unei stri de fapt din domeniul su de referin. Calitatea uneipropoziiideafi adevratsaufalsse numete valoarea de adevr a propoziiei respective. Propoziiile simple le notmprin:p, q, r, . . . ncontinuare,propoziiiloradevrateleatribuimvaloareade adevr 1 iar propoziiilor false valoarea de adevr 0. Plecnddelaunasaumaimultepropoziiisimpleprinaplicarea unuinumrfinitdeoperatori(conectori)logiciobinemaltepropoziii numite propoziii compuse. Exist patru operatori logici de baz: (citit non), (citit i), (citit sau) i (citit implic). Definiie.Fieppropoziie.Propoziiacareseobinepunnd particula "nu" n faa prii predicative a propoziieipse numete negaia propoziieipi se noteaz prin simbolul p. Negaia propoziieipeste adevrat numai cndpeste fals. -7-Exemplu."2estenumrpar"cudomeniuldereferin mulimea numerelor naturale. Negaia luipestep: " 2nuestenumrpar " p fiind o propoziie adevrat, pe cnd p esteo propoziie fals.Esteuorsfolosimuntabeldeadevrpentruaverificarelaiile dintrevalorile de adevr ale propoziiilor.Tabelul de adevr pentru p n funcie de valoarea de adevr a lui p este: pp 10 01 Definiie.Fiep,qpropoziii.Propoziiacareseobinepunnd particula "i" ntre prile predicative se numete conjuncia propoziiilor p, q i se noteaz prin simbolul p q. Propoziiap qesteadevratnumaicndambelepropoziiisunt adevrate. Exemplu.Propoziia "2 este numr par i 3 este numr par" cu domeniuldereferinmulimeanumerelornaturaleesteconjuncia propoziiilor: p: "2 este numr par" q: "3 este numr par", p fiind adevrat iar q fals.Valoareadeadevrapropoziieip qnfunciedevalorilede adevr ale propoziiilor p, q este dat n tabelul: pqp q 111 100 010 000 Definiie.Fiep,qpropoziii.Propoziiacareseobinepunnd particula"sau"ntreprilepredicativesenumetedisjunciapropoziiilor p, q ise noteaz prin simbolul p q.Propoziiap qesteadevratnumaicndunadinpropoziiieste adevrat. Exemplu.Propoziia"8estemultiplude2sau5estenumr ntreg"cudomeniuldereferinmulimeanumerelornaturaleeste disjuncia propoziiilor: -8-p:" 8 este multiplu de 2 " ;q:" 5 este numr ntreg ",p, q fiind adevrate.Valoreadeadevrapropoziieip qnfunciedevalorilede adevr ale propoziiilor p, q este dat n tabelul: pqp q 111 101 011 000 Definiie. Fie p, q propoziii.Exprimarea " p implic q " este o noupropoziie,numitimplicaiapropoziiilorp,q.Implicaia propoziiilorp, q se noteazp q. Implicaiapropoziiilorp,qesteopropoziiefalscndpropoziiaqeste fals iar p este o propoziie adevrat i adevrat n celelalte cazuri. Exemplu.Propoziia,,x2 0implicx=0"cudomeniulde referin mulimea numerelor reale este implicaia propoziiilor: p: " x20 " ;q: " x = 0 "ea fiind o propoziie adevrat. Pentru exprimarea" p implic q " se mai folosete: " dac p atunci q " " p este suficient pentru q " " q este necesar pentru p " Valoreadeadevrapropoziieipqnfunciedevalorilede adevr ale propoziiilor p, q este dat n tabelul: pqp q 111 100 011 001 Propoziia q p se numete reciproca propoziieip q. Dac combinm propoziia p q cu propoziia q p, obinem o noupropoziiecreiaispuneechivalenapropoziiilorp,q.Echivalena propoziiilor se noteazp q. Definiie.Fiep,qpropoziii.Echivalenapqesteacea propoziie care este adevrat cnd p, q au aceeai valoare de adevr i este fals n rest.Propoziiap qse citete p dac i numai dac q . -9-Exemplu.Propoziia"x3 0dacinumaidacx0"cu domeniuldereferinmulimeanumerelorrealeesteechivalena propoziiilor: p:" x3 0 implic x 0 " ;q:" x 0 implic x3 0 " ea fiind o propoziie adevrat. Notmcechivalenapqesteadevratcndpqiqpsunt adevrate. Pentru exprimarea" p dac i numai dac q " se mai folosete: " p este necesar i suficient pentru q" " dac p atunci q, i invers " Valoarea de adevr a propoziiei p q n funcie de valorile de adevr ale propoziiilor p, q este dat n tabelul: pqp q 111 100 010 001 Vom nota prin A sau A (p, q, r,), B sau B (p, q, r,) propoziiile compuse(sauexpresiilogice)obinuteprinaplicareadiferiiloroperatori logici propoziilor simple p, q, r,. A (p, q, r) : (p q) r . Calcululpropoziiilorstudiazexpresiilelogicedinpunctulde vederealadevruluisaufalsuluilornraportcuvalorilelogiceale propoziiilor simple care le compun.OexpresielogicA(p,q,r,...)careesteadevratindiferentde valorile de adevr ale propoziiilor p, q, r, se numete tautologie. Dac A (p, q, r, ...) B (p, q, r,)este o tautologie atunci scriem A (p, q, r, ...) B (p, q, r, ) DacA (p, q, r, ...) B (p, q, r,)este o tautologie scriemA (p, q, r, ...) B (p, q, r, ) Observaii: 1.Semnulesteooperaiedincarededucemvaloareade adevr a propoziiei A B n timp ceindic legtura ntre propoziiile A (p, q, r,..),B(p, q, r,).-10-2.Semnulesteooperaiedincarededucemvaloareade adevr a propoziieiAB n timp ce indic legtura ntre propoziiile A (p, q, r,...),B (p, q, r,). Exemple de tautologii : 1. legea terului exclus: p (p) 2. legea silogismului: [(p q) (q r)] (p r) 3. legea de reflexivitate: p p4. legea idempotenei conjunciei: p p p 5.legea idempotenei disjunciei: p p p 6. legea dublei negaii: (p) p 7.legea de comutativitate a conjunciei: (p q) (q p) 8.legea de comutativitate a disjunciei: (p q) (q p) 9. legea de asociativitate a conjuncei: [(p q) r] [p (q r)] 10. legea de asociativitate a disjuncei:[(p q) r] [p (q r)] 11. Legile lui De Morgan:(p q) (p)(q) (p q) (p)(q) 12. Legea de distributivitate a conjunciei: -n raport cu disjuncia: [p (q r)] [(p q) (p r)] 13. Legea de distributivitate disjunciei : -n raport cu conjuncia: [p (q r)] [(p q) (p r)] 14. (pq) ( qp) Demonstrm 1 : ppp (p) 101 011 Demonstrm 2. pqrpqqr(pq)(qr)]pr[(pq)(qr)] (pr) 11111111 00011111 10101011 01111111 10001001 01010011 00111111 11001001 -11- 2. Elemente de calcululpredicatelor Amintimcprinpredicatsenelegeunenuncuunulsaumai multe subiecte nedeterminate care depinde de o variabil sau de maimulte variabile i are proprietatea c pentru orice valori date variabilelor se obine o proproziie adevrat sau o propoziie fals. Observaie.Oridecteoridefinimunpredicat,trebuies indicm i mulimile n care variabilele iau valori. Exemplu.Predicatul p(x): " x < 4, x R " aredomeniuldereferinmulimeanumerelorrealeiarparteapredicativ const din textul " este mai mic dect " Predicatularedousubiecte:"x"i"4",dintrecareunul nedeterminat, prin urmare, este un predicat cu o variabil. Exerciiu.Fie p(x) predicatul " x < 4, x R ". Care sunt valorile de adevr ale propoziiilor p(5) i p(4) ? Exemplu. Fiep(x,y) predicatul"2x+y=2".Caresuntvalorile deadevrale propoziiilor p(2,0) i p(1,0) ? Propoziia p(2,0) obinut atribuind lui x, y valorile x = 2, y = 0 este opropoziiefals,ntimpcepropoziiap(1,0)obinutatribuindluix,y valorile x = 1, y = 0 este o propoziie adevrat. n general, un predicat cunvariabilex1, x2, . . ., xn este notat prin p(x1, x2, . . ., xn). Fiep(x),q(x)predicateunare.Cuajutoruloperatorilorlogiciconstruim i alte predicate unare, anume: p(x),p(x)q(x),p(x)q(x),p(x)q(x),p(x)q(x) Astfel,deexemplu,pentrupredicatulp(x),p(x)estepredicatul cruia pentru fiecare valoare x = ai corespunde propoziia p(a). Strnslegatdenoiuneadepredicataparenoiuneade cuantificator. Distingem urmtoarele tipuri de cuantificatori: Definiie.Propoziia universal alui p(x)estepropoziia " p(x) este o propoziie adevrat pentru orice valoare a luixdin domeniul de referin ". Notaia ( ) ( ) x p x denot propoziia universal a lui p(x).Semnul se numete cuantificator universal. Pentru propoziia universal a lui p(x) se folosesc i exprimrile: -12-" pentru toi x, p(x) " " pentru fiecare x, p(x) ". Exemplu.OriceelevdinclasaaIX-acunoatemulimea numerelor naturale. Predicatul este p(x): " Orice elev cunoate mulimea numerelor naturale" Mulimea n care p(x) este adevrat este elevii clasei a IX-a.Dac propoziia)) ( ) ( )( ( x q x p x este adevrat, atunci vom folosi notaia p(x) q(x) i citim: " p(x) implic q(x) ". Se mai spune, n acest caz, c predicatul q(x) este o consecin logic a predicatului p(x). Exemplu. Considernd predicatelep(x): " x = 1 " i q(x): " x3-1=0, xR " cu domeniul de referin mulimea numerelor reale, avem p(x) q(x). Dacpropoziia)) ( ) ( )( ( x q x p x esteadevrat,atunci vom folosi notaia p(x)q(x) i citim: " p(x) dac i numai dac q(x) ". Se mai spune, n acest caz, c predicatele p(x), q(x) sunt echivalente logic. Exemplu.Considernd predicatelep(x): " x > 0, x R " i q(x): " x3 > 0, x R " cudomeniul dereferin mulimea numerelor reale, avemp(x) q(x). Observaie.Relaiiledeconsecinlogiciechivalenlogic pot fi definite i ntre predicaten-are, unde n 2, ntr-un mod asemntor. Definiie.Propoziia existenial alui p(x) este propoziia "exist cel puin un x din domeniul de referin astfel nctp(x)". Notaia( ) ( ) x p x denotpropoziiaexistenialaluip(x)iesteo propoziieadevratcndexistcelpuinunelementx0dindomeniulde referin astfel nct p(x0) este adevrat.Semnul se numete cuantificator existenial. Pentru propoziia existenial a luip(x) se folosetei exprimarea: " exist x, p(x) " Exemplu.Dac considerm predicatul p(x): " x Z , astfel nct x+5=0 " cudomeniuldereferinmulimeanumerelorntregi,atuncipropoziiaexistenial lui p(x)ste adevrat, deoarece pentru x = -5) 0 5 )( ( = + x xastfel propoziiap(-5): " -5+5=0 " -13-este adevrat. Considermncontinuarepredicatulp(x)definitnumaipentruun numr finit de valori ale variabileix, anumex1, x2, . . . , xn, atunci: p(x) p(x1) p(x2) p(xn) i p(x) p(x1) p(x2) p(xn) innd cont de legile lui De Morgan (vezi paragraful 1 proprietatea 11), rezult p(x) p(x1) p(x2)p(xn) i p(x) p(x1) p(x2) p(xn) Reguliledenegaiestabilitemaisus,suntvalabileincazul general. Deci pentru orice predicat unarp(x) avem: a)p(x) ( ) x ( p(x)) b)( ) x ( p(x)) ( ) x (p(x)) Exemplu. S considerm predicatul p(x): ") ( N x astfel nct x+1=2 " a crui valoare de adevr este adevrul. Negaia ei este propoziiap(x): ") ( N x ,avem x+12" evident o propoziie fals. Predicate binare. Fie p(x, y) un predicat binar. Folosind cuantificatorii i s'putem forma predicatele unare: y) x)p(x, (i s) , ( ) (' y x p xundeyestevariabilaacestordoupredicate.Dinacestepredicateunare putem forma predicatele: y)" x)p(x, y)( ( i s y) x)p(x, y)( ( y), x)p(x, y)( ( ), , ( ) )( ( "' y x p x yncontinuarevomartacumsededuclegiledenegaiepentru predicatele binare, din legile de negaie pentru predicate unare. Adic: )) , ( )( )( ( )) , ( ) ( ( )) , ( ) ( ) (( ) ')) , ( )( )( ( )) , ( ) ( ( )) , ( ) ( ) (( ) 'b) )b) )y x p x y y x p x y y x p x y by x p x y y x p x y y x p x y adin b dindin a din Analog se extind aceste rezultate la predicate n-are. ( ) x ( ) x ) ( x ) ( x ( ) x -14- 3. Teorem direct, teorem reciproc.Metoda demonstraiei prin reducere la absurd. Oteoremesteopropoziieadevratcarestabiletecunulsau mai multe obiecte posed o proprietate, forma lor general fiind:p(x1, x2, . . . , xn) q(x1, x2, . . . , xn), unde p(x1, x2, . . . , xn) se numete ipoteza teoremei iar q(x1, x2, . . . , xn) se numete concluzia teoremei.Teoremele care se accept fr demonstraie se numesc axiome. Demonstraiauneiteoremeconstntrecereasuccesivdela ipotezlaconcluziepebazaunordeduciilogice.Demonstraiasefacepe baza unor definiii i axiome cunoscute mai nainte. Adic:demonstraiateoremeipqesteunirfinitdeimplicaii logice de forma: p = p1, p1 p2, ,pn-1 pn = q fiecare element al acestui ir fiind o implicaie adevrat. Dacmaimulteteoremeauaceeaiipoteziconcluziidiferite, atuncielepotfinlocuitecuoteorem,careareipotezacomun,iardrept concluzie, conjuncia concluziilor teoremelor.Fie teorema p(x1, x2, . . . , xn) q(x1, x2, . . . , xn). care exprim faptul c predicatul q(x1, x2, . . . , xn) este consecin logic a predicatului p(x1, x2, . . . , xn). Dac i predicatul q(x1, x2, . . . , xn) este consecin logic a predicatului p(x1, x2, . . . , xn) atunci are loc teorema: p(x1, x2, . . . , xn) q(x1, x2, . . . , xn) numit contrara teoremei date. Exemplu.Considerm teorema: " Dac cel mai mare divizor comun a dou numere ntregi a, b este 1 atunci numerele nu pot fi amndou pare " Ea este format din predicatele: p(x): " Dac cel mai mare divizor comun a dou numere ntregi a, b este 1 " q(x): " atunci numerele nu pot fi amndou pare " Predicatul p(x) const din enunul: " Dac cel mai mare divizor comun a dou numere ntregi a, b estediferit de 1 " Predicatul q(x) const din enunul: " atunci numerele pot fi amndou pare " -15-Contrarateoremei date este: " Dac cel mai mare divizor comun a dou numere ntregi a, b este diferit de 1 atunci numerelepot fi amndou pare " Fie teorema p(x1, x2, . . . , xn) q(x1, x2, . . . , xn), putem forma: -teorema reciproc q(x1, x2, . . . , xn) p(x1, x2, . . . , xn). -teorema contrar: p(x1, x2, . . . , xn) q(x1, x2, . . . , xn). -teorema contrar reciprocei: q(x1, x2, . . . , xn) p(x1, x2, . . . , xn) Datorit tautologiei: (p q) ( q p) din calculul cu propoziii, teorema direct p(x1, x2, . . . , xn) q(x1, x2, . . . , xn) este adevrat dac i numai dac contrara reciprocei sale q(x1, x2, . . . , xn) p(x1, x2, . . . , xn) este adevrat. Acest lucru ne arat c pentru a demonstrap(x1, x2, . . . , xn) q(x1, x2, . . . , xn) este totuna cu a demonstra q(x1, x2, . . . , xn) p(x1, x2, . . . , xn) Acest raionamentpoart denumirea de metoda reducerii la absurd. nrezumat,metodareduceriilaabsurdseaplicdupurmtoarea schem: a) Etapa negrii concluziei. n aceast etap, se presupune c ceea ce avem de demonstrat nu este adevrat. b) Etapa contrazicerii. n aceast etap, pornind de la presupunerea fcut n etapa anterioar, printr-o serie de raionamente logice, se caut s se ajung la un rezultat care s fie contradictoriu cu un adevr (o axiom, o teorem etc.). c)Etapa deciziei.n aceasta, se pune ntrebarea: de unde s-a ajuns lacontradiciadinetapaadoua?Rspunsulestefirescinndseamade presupunereafcutnetapaa)cceeacetrebuiademonstratnueste adevrat. -16-4.Exerciii 1.Caredinenunurileurmtoaresuntpropoziiiicevaloride adevr au: a) (2-1)(2+1)=22-1; b) Un numr ntreg a pentru care (a,2)=2 este numr par; c) 3>6; d) m()=900 este unghi drept. 2.Din propoziiile: p: 4=6 i q: 9m, atunci scdem laN, fr a-i schimba valoarea, expresia: 0 ... y unde , ...1 1 n1111= = = = + + ++ ++ m nmmnnnny y a y a y a ya z a y xi i i< + = +iz ,( ) ( )iii iiii ia z a a z a a y x + = + = ++1-64-Atunci: ( ) ( ) ( )( ) ( ) ( )0 0 1 122 211 1 ... ...y x a y x a y xa y x a y x a y x M Nii inn nnn n + + ++ + + + + = Dac toate numerele (xI-yi) sunt definite, numrul A = N M se scrie: ( )( ) ( ) ( )( )( ). ... ...0 0 1 1 1 1 a i i n n n ny x y x y x y x y x A = Dacexistvreodiferen(xi -yi)carenusepoateefectuanseamnc exist un numr i, astfel ca yi > xi caz n care scriem: ( ) ( ) ( ) ( )ii iii iii iii ia y x a a y x a y x a y x + + = + ++ +++ +11 111 11Dar:0n+qp>q.Deducemcm>nnudepindede reprezentani, cinumaide numrulntreg [m,n]. Folosindu-ne demulmea numerelornaturale,avemsaum>niatunci[m,n]Z+,saum=niatunci [m,n]=0 sau m