Informatica - Matematica discreta

Raccolta applicazioni

Divided by topic

Denizione 1. Siaf:A!Buna funzione. La funzionefsi dice INIET- TIVA o INGETTIVA se 8a; a0 2A; a6 =a0 =)f(a)6 =f(a0 ); cioè se elementi distinti diAhanno necessariamente immagini distinte inB. Tenendo conto cheP=)Qè equivalente a:Q=) :P, si ottiene la seguente denizione equivalente alla precedente. Denizione 2.Siaf:A!Buna funzione. La funzionefsi dice INIET- TIVA o INGETTIVA se 8a; a0 2A f(a) =f(a0 ) =)a=a0 Esempio 1.Si consideri la funzione f:Z!Ztale chef(n) = 3n48n2Z f è iniettiva?? La risposta è aermativa perchè8n; n0 2Zsef(n) =f(n0 ) =)3n4 = 3n0 4 =)3n= 3n0 =)n=n0 , quindi è vericata la seconda denizione. Esempio 2.Si consideri la funzione f:Z!Ntale chef(n) =n2 8n2Z f è iniettiva?? La risposta è NO perchè se, per esempio, si considerano i due numeri interi n= 2en0 =2si ha chef(2) = 4 =f(2), quindi non è soddisfatta la prima denizione. Esempio 3.Si consideri la funzione f:Z!Ntale chef(n) =jnj 8n2Z f è iniettiva?? La risposta è NO perchè se, per esempio, si considerano i due numeri interi n= 3en0 =3si ha chef(3) = 3 =f(3), quindi non è soddisfatta la prima denizione. Osservazione1.Sef:A!Bè una funzione iniettiva, allora per ognib2B l'insieme controimmaginef 1 (b)ha al più un elemento. 1 Osservazione 2.La nozione di iniettività dipende dall'insieme di partenza della funzione. Infatti se consideriamo la funzione f:N!Ntale chef(n) =n2 8n2N questa è iniettiva in quanto, comunque si scelgono due numeri naturali distinti i loro quadrati sono ancora distinti. Se invece consideriamo f:Z!Ntale chef(n) =n2 8n2Z allora in tal caso f non è iniettiva. (Esempio 2) Denizione 3.Siaf:A!Buna funzione. La funzionefsi dice SURIET- TIVA o SURGETTIVA se 8b2B;9a2Atale chef(a) =b; cioè seI m(f) =B. Esempio 4.Si consideri la funzione f:Z!Ztale chef(n) = 3n48n2Z f è suriettiva?? La risposta è NO perchè,8n0 2Zsef(n) =n0 =)3n4 =n0 =)3n= n0 + 4 =)n=n 0 +43 , ma ora questo ntovato non appartiene sempre aZ, al variare din0 inZ. Esempio 5.Si consideri la funzione f:Q!Qtale chef(q) = 3q48q2Q f è suriettiva?? La risposta è SI perchè8q0 2Qsef(q) =q0 =)3q4 =q0 =)q=q 0 +43 e questoqtovato appartiene sempre aQ, al variare diq0 inQ. Osservazione3.Questi due ultimi esempi mettono in mostra come la suriettività di una funzione dipenda sia dall'insieme di partenza che dall'in- sieme di arrivo della funzione stessa. Osservazione4.Una funzionef:A!Bè suriettiva se e solo sef 1 (b)6 =?, per ognib2B. Osservazione5.Siaf:A!Buna funzione. Alloraf:A!I m(f)è suriettiva. 2 Denizione 1. Siaf:A!Buna funzione. La funzionefsi dice BIETTI- VA o BIGETTIVA se è sia iniettiva che suriettiva, cioè 8b2B;9!a2At.cf(a) =b Esempio 1.Si consideri la funzione f:R!Rtale chef(x) =x5 48x2R f è biettiva?? La risposta è SI poichèfè sia iniettiva che suriettiva. Infatti: 8x; y2Rsef(x) =f(y) =)x5 4 =y5 4 =)x5 =y5 =)x=y, quindifè iniettiva; inoltre8y2Rsef(x) =y=)x5 4 =y=)x5 = y+ 4 =)x=5 py + 4e talexappartiene adR, comunque si scelgay2R. Quindifè anche suriettiva. Esempio 2.Si consideri la funzione f:Z!Ntale chef(n) =n2 8n2Z f è biettiva?? Osserviamo chefè non iniettiva, infatti se si considerano gli interin= 2e n0 =2, pur essendo diversi, le loro immagini, mediantef, coincidono. Quindi la funzionefNON è biettiva, poichè per esserlo dovrebbe essere sia iniettiva che suriettiva. Denizione 2.Sianof:A!Beg:B!Cdue funzioni. Si chiama FUN- ZIONE COMPOSIZIONE difeg, si indica congf(si leggegcerchietto f), la funzione gf:A!Ctale che8a2A;(gf)(a) =g(f(a)); cioèAaf !7!B f(a)g !7!C g(f(a)) Osservazione1.Come si evince dalla denizione precedente, anchè esita la funzione compostagfè fondamentale che l'insieme di arrivo dif(funzione che si trova scritta più a destra, cioè quella che viene applicata per prima) coincida con l'insieme di partenza dig(funzione più a sinistra). Questa è la regola generale per stabilire se, assegnate due funzionifegesiste la loro funzione composizionegf Osservazione2.Se esiste la funzionegf, come si evince dalla denizione, gfha come insieme di partenza l'insieme di partenza dife come insieme di arrivo quello della funzioneg. 1 Osservazione 3.Come segue dalla denizione, assegnate due funzionifeg è ben diverso determinare, se è possibile,gfefg. Nell'ipotesi che esistano entrambe le funzioni composizioni, in generale si hagf6 =fg. Spesso questo si esprime dicendo che l'operazione di composizione, in generale, non è commutativa. Esempio 3.Si considerino le seguenti funzioni: f:N!Ntale chef(n) =n2 8n2N g:N!Ntale chef(t) =t+ 28t2N Esistegf? La risposta è SI poichè l'insieme di arrivo difcoincide con l'insieme di partenza dig. Esistefg? La risposta è SI poichè l'insieme di arrivo digcoincide con l'insieme di partenza dif. Osservato ciò, tenendo conto dell' Osservazione 2 e della Denizione 2, si ha gf:N!Ntale che8n2N (gf)(n) =g(f(n)) =g(n2 ) =n2 + 2 efg:N!Ntale che8n2N (fg)(n) =f(g(n)) =f(n+ 2) = (n+ 2)2 Osserviamo chegf6 =fg Esempio 4.Si considerino le seguenti funzioni: h:N!Q tale cheh(n) =n3 + 1 8n2N f:Q !Qtale chef(q) =1q 8 q2Q Esistehf? La risposta è NO poichè l'insieme di arrivo difnon coincide con l'insieme di partenza dih. Esistefh? SI, perchè l'insieme di arrivo dihè uguale all'insieme di partenza dif. In tal caso si ha: fh:N!Qtale che8n2N (fh)(n) =f(h(n)) =f(n3 + 1) = 1n 3 + 1= 3n + 3 2 PROPRIETA' 1. 1) (Associativa) Sianof:A!B,g:B!Ceh:C! Dtre funzioni.Allora h(gf) = (hg)f : 2) Siaf:A!Buna funzione e sianoid Ae id Ble funzioni identità su Ae B, rispettivamente. Allora fid A= f=id B f : 3) Sianof:A!Beg:B!Cdue funzioni. Sefegsono iniettive, alloragfè iniettiva. Sefegsono suriettive, alloragfè suriettiva. Sefegsono biettive, alloragfè biettiva. Osservazione1.Per ciascuna di queste tre implicazioni non vale il viceversa. A supporto di tale aermazione, forniamo il seguente controesempio. Si considerino i seguenti tre insiemi: A=f1g;B=fa; b; cg;C=ftg: A partire da essi, deniamo le seguenti due funzioni:f:A!Btale chef(1) =a g:B!Ctale cheg(a) =g(b) =g(c) =t: Si osserva, facilmente, per come sono denite, chefè una funzione iniettiva ma non suriettiva egè una funzione suriettiva ma non iniettiva. Inoltre possiamo considerare la funzione composta gf:A!Ctale che(gf)(1) =t: Si verica facilmente chegfè una funzione iniettiva e suriettiva, quindi anche biettiva. Dunque,gfè una funzione iniettiva mafegnon sono entrambe iniettive. Questo mostra che non vale il viceversa della prima implicazione della Pro- prietà 3. Analogamente per le altre due implicazioni. Denizione 1.Siaf:A!Buna funzione. La funzionefsi dice INVERTIBILE se esiste una funzioneg:B!Atale chefg=id Be gf=id A. Tale funzionegsi dice FUNZIONE INVERSA dif Osservazione2.Sefè una funzione invertibile, la sua funzione inversa è UNICA. 1 Proposizione 1. Siaf:A!Buna funzione.fè invertibile se e solo sef è biettiva. Inoltre, nell'ipotesi chefsia invertibile, la funzione inversa difè la funzione f 1 :B!Atale cheb2B7!f 1 (b)2A Dimostrazione.Per provare l'equivalenza bisogna provare la doppia impli- cazione. Iniziamo col provare la seconda implicazione, cioè proviamo che sefè biet- tiva allorafè invertibile. Supponiamofbiettiva, dunque, per denizione, si ha che8b2B;9!a2A tale chef(a) =bma questo equivale a dire che8b2B;9!a2Atale che f 1 (b) =fag. Dunque ha senso denire la funzionef 1 :B!Atale cheb2B7!f 1 (b)2 A. Per provare chefè invertibile, resta da dimostrare chef 1 è la sua funzione inversa, cioèff 1 =id Be f 1 f=id A. Questo è di verica immediata. Proviamo, ora, la prima implicazione. Supponiamofinvertibile, dunque, per denizione, esiste (ed è unica)g:B! Atale chefg=id Be gf=id A. Sotto tale ipotesi dimostriamo chefè biettiva, cioè iniettiva e suriettiva. Per ognix; x0 2Asef(x) =f(x0 ) =)g(f(x)) =g(f(x0 )) =)(gf)(x) = (gf)(x0 ) =)id A( x) =id A( x0 ) =)x=x0 , dunquefè iniettiva. Ora, per ognib2Bpossiamo considerareg(b)2A. Poniamoa=g(b)2Ae dunquef(a) =f(g(b)) = (fg)(b) =id B( b) =b. Ciò dimostra chefè suriettiva. Inne, è facile osservare che questa funzionegè proprio la funzionef 1 .Osservazione 3.Sefè una funzione invertibile( equivalentemente, biettiva), allora lo è anche la sua funzione inversaf 1 . PROPRIETA' 2.1) Sianof:A!Beg:B!Cdue funzioni invertibili. Alloragfè una funzione invertibile, inoltre (gf) 1 =f 1 g 1 : 2) La funzione identitàid Aè invertibile, inoltre (id A) 1 =id A. 3) Siaf:A!Buna funzione invertibile. Allora(f 1 ) 1 =f. 2