Con le ultime versioni di Adobe Reader la ricerca è agevolata utilizzando l’indice tematico che si apre sul lato sinistro della pagina sotto ‘Bookmarks’ con i relativi
links. Da ‘Pages’ si visualizzano le miniature delle diapositive. Rosalba BaratteroRosalba Barattero
Lucidi delle Esercitazioni di Lucidi delle Esercitazioni di
Matematica Discreta Matematica Discreta
2006 2007
C.S. in Informatica C.S. in Informatica
Universit
Universitàà di Genovadi Genova
http://www.dima.unige.it/
http://www.dima.unige.it/~baratter~baratter
Dipartimento di Matematica Dipartimento di Matematica
Genova, 3 dicembre 2006 Genova, 3 dicembre 2006
♦
♦ Il principio di induzione
♦
♦ Immagine e controimmagine
♦
♦ Funzioni iniettive, surgettive, bigettive
Rosalba Barattero
ESERCITAZIONE N.1 24 ottobre 2006
ESERCIZIOC1.1
Il principio di induzione:la somma dei dispari
Provare per induzione che vale la seguente proprietà per ogni numero naturale n ≥1
(*) 1+3+5+…+ (2n-1)= n2.
(pari = multiplo di 2 = 2n, dispari= successivo o antecedente di un pari = 2n+1 opp. 2n-1 )
E' la somma dei primi n numeri naturali dispari consecutivi.
1 = 12 = 1 1+3 = 22 = 4
1+3+5 = 32 = 9 1+3+5+7 = 42 = 16 …..………..………
Per provare che (*) è vera per ogni n≥1 usiamo il principio di in- duzione.
BASE DELL'INDUZIONE:La proprietà è vera per n=1.
Sostituiamo n=1 in (*), otteniamo: 1 = 12 , vero (v.sopra).
PASSO DELL'INDUZIONE:Se la proprietà (*) è vera per un generico n≥1 allora è vera anche per il successivo n+1.
Un’immagine comoda per rappresentarsi la situazione è quella di una successione di pezzi di domino messi in piedi in equilibrio precario , distanti tra loro meno della loro al- tezza.
Così se un pezzo cade verso destra fa cadere verso destra quello adiacente. Se cade il primo, fa cadere il secondo, che fa cadere il terzo,e tutti cadono.
[ da G. Lolli – Logica Matematica – Corso di laurea in Informatica 2005-2006 ]
Supponiamo di sapere che la proprietà valga per n, n≥1 1+3+5+…+ (2n-1)= n2 IPOTESI INDUTTIVA. Mostriamo che la proprietà vale per n+1 TESI
Come si esprime la tesi ?
Sostituiamo in (*) n+1 al posto di n 1+3+5+…+ (2(n+1)-1)= (n+1)2 ,cioè 1+3+5+…+ (2n+1) = (n+1)2. TESI
Ora si tratta di dedurre dall'ipotesi 1+3+5+…+(2n-1)= n2 la tesi 1+3+5+… + (2n+1) = (n+1)2 , tramite calcolo.
2 2
ipotesi per n
1) (n 1) (2n n
1) (2n 1)
- ...(2n 5
3 1
2
+
= + +
= + +
+ + +
= 4 4443
4
4 2
1
Allora la tesi è vera.
CONCLUSIONE: per il principio di induzione la proprietà (*) è vera per tutti i numeri naturali n≥ 1.
In simboli (*) si scrive così :
l'addendo immediatamente precedente è 2n-1 ( il numero dispari che precede)
2 1
k ) 1 2
( − =
∑
= kn
n
ESERCIZIOC2.1
Il principio di induzione – esempio geometrico
Provare per induzione che la somma degli angoli interni di un poligono convesso con n lati è π (n - 2).
La proprietà ha senso a partire dal triangolo (n=3).
Quindi in questo caso il principio di induzione correttamente enun- ciato è :
• BASE : P(3)
• PASSO INDUTTIVO: ∀n ≥ 3 si ha P(n) ⇒ P(n+1)
∀n P(n)
In parole:
detta P(n) la proposizione “la somma degli angoli interni di un po- ligono convesso con n lati è π (n - 2)”, per provare che è vera
∀ n sono sufficienti due mosse:
• la prima consiste nel dimostrare che è vera per n=3
• la seconda nel dimostrare che se è vera per un generico n (n ≥3) allora è vera anche per il successivo n+1.
BASE
P(3): somma angoli interni è π=π(3-2)
PASSO INDUTTIVO
Il poligono dato, che nella figura immaginiamo avere n lati, si suddivide nel poligono R avente n-1 lati e nel triangolo T.
Per l’ ipotesi induttiva si sa che la somma degli angoli interni di R è π ((n-1) – 2 ).
A questo punto basta aggiungere la somma degli angoli interni di T, che vale π, per ottenere la somma degli angoli interni del poli- gono dato :
π((n-1) – 2 ) + π = π(n-2) ok!
R T
ESERCIZIOC3.1
Il principio di induzione:altro esempio aritmetico
Provare per induzione che vale la seguente proprietà per ogni numero naturale n ≥1
(*) 13 +23 + 33 + … + n3=
2 2
1) n(n ⎥⎦⎤
⎢⎣⎡ +
.
BASE DELL'INDUZIONE:La proprietà è vera per n=1. Sostituiamo n con 1 nella (*) :
13 =
2 2
1) 1(1 ⎥⎦⎤
⎢⎣⎡ +
Sì è vera !
PASSO DELL'INDUZIONE:Se la proprietà (*) è vera per un generico n≥1 allora è vera anche per il successivo n+1.
Ipotesi induttiva: la proprietà è vera per n ,cioè
13 +23 + 33 + … + n3=
2 2
1) n(n ⎥⎦⎤
⎢⎣⎡ +
.
Tesi : La proprietà è vera per n+1, cioè (n+1 al posto di n)
13 +23 + 33 + … + n3+ (n+1)3 =
2 2
1) 1) 1)((n
(n ⎥⎦⎤
⎢⎣⎡ + + + =
2 2
2) 1)(n
(n ⎥⎦⎤
⎢⎣⎡ + +
Scriviamo il membro di sinistra dell’uguaglianza della tesi:
13 +23 + 33 + … + n3+ (n+1)3 =
?
=
2 2
1) n(n ⎥⎦⎤
⎢⎣⎡ +
+ (n+1)3
= n (n 1) 4 4(n 1)
3 2
2 + + +
= (n 1) (n4 4(n 1))
2
2 + +
+
= (n 1)4(n 2)
2
2 +
+
abbiamo ottenuto esattamente il membro di destra della tesi. Ok!
Ipotesi induttiva
ESERCIZIO 4.1
Funzioni - Immagini – Controimmagini – Surgettività - Iniettività
Sia f : N x N → Z la relazione così definita f (m,n) = m+n.
a) Verificare che f è una funzione.
b) Determinare f(0,1), f(1,0), f(2,3) ( = immagini di elementi di N x N ).
c) Determinare f –1(0) (=controimmagine di 0∈Z tramite f ), f –1(1) , f –1(-2).
d) Stabilire se f è iniettiva, surgettiva, bigettiva.
• N x N : prodotto cartesiano di due insiemi
Il prodotto cartesiano A x B di due insiemi A e B è per def. l’insieme di tutte le coppie ordinate (a,b) con a∈A e b∈B.
• f è una funzione se ad ogni elemento dell’insieme di partenza ( dominio) fa corrispondere uno ed un solo elemento dell’insieme di arrivo ( codominio) .
A ogni (m,n)∈NxN la nostra f fa corrispondere m+n, m+n ∈ N ⊆ Z e il valore della somma m+n è unico.
b) f : N x N → Z definita da f (m,n) = m+n.
Determinare f(0,1), f(1,0), f(2,3)
f(0,1) = ? N x N → Z
(0,1) → 0+1 = 1 ⇒ f(0,1) =1 f(1,0) = 1+0 = 1 ⇒ f(1,0) =1
f(2,3) = 2+3 = 5 ⇒ f(2,3) =5
c) Determinare f –1(0) (=controimmagine di 0 tramite f ), f –1(1) , f –1(-2).
f: A → B, x ∈ B : f –1(x) = {a∈ A| f(a) = x }
f: N x N → Z così definita f (m,n) = m+n
c) f –1(0) = {(m,n) ∈ N x N | f(m,n) = 0 } = {(m,n) ∈ N x N | m+n = 0 } = {(0,0)}
f –1(1) = {(m,n) ∈ N x N | f(m,n) = 1 } = {(m,n) ∈ N x N | m+n = 1 } = {(0,1), (1,0)}
f –1(-2) = {(m,n) ∈ N x N | m+n = -2 } = ∅
d) f è iniettiva se trasforma elementi distinti del dominio in elementi distinti del codominio
Detto con una metafora:
″ f è iniettiva se i bersagli che vengono raggiunti, lo sono con una sola freccia ! ″
In simboli : f è iniettiva se e solo se : x≠y in A ⇒ f(x) ≠ f(y) in B o equivalentemente
f(x) = f(y) in B ⇒ x = y in A
f non è iniettiva perché da b) sappiamo che (0,1) e (1,0) sono due elementi distinti di N x N che hanno uguale immagine mediante f :
f(0,1) = f(1,0) = 1
O equivalentemente da c) sappiamo che f –1(1) = {(0,1), (1,0)}
In generale si ha:
f:A → B è iniettiva ⇔∀ b ∈ B risulta : f –1(b) = ∅ oppure f –1(b) ={a}, a∈ A
f:A → B è surgettiva se
Im(f) = {f(x)| x∈A } (Immagine di f) coincide con B.
Ciò vuol dire che ogni elemento di B proviene da al- meno un elemento di A : ∀ b∈B ∃ a ∈ A t.c. f(a)=b
Con una metafora: "f è surgettiva se tutti i bersagli vengono raggiunti."
f: N x N → Z così definita f (m,n) = m+n
f è surgettiva se per ogni x ∈ Z esiste (m,n) ∈ N x N t.c. m+n = x.
Ciò è falso: se x=-2 non esistono m ed n naturali t.c.
m+n = -2. Quindi la nostra f NON è surgettiva.
Oppure possiamo anche dire che f non è surgettiva perché abbiamo trovato un elemento –2 del codominio la cui controimmagine f –1(-2) è vuota.
In generale si ha :
f:A → B è surgettiva ⇔ ∀ b ∈ B risulta f –1(b) ≠ ∅ ossia equivalentemente:
f:A → B non è surgettiva ⇔ ∃ b ∈ B t.c. f –1(b) = ∅
• f è bigettiva ⇔ f è iniettiva e surgettiva.
Quindi la nostra f non è bigettiva
ESERCIZIOC5.1
Funzioni iniettive - surgettive
Sia f: ZxZ→ N la funzione definita da f(a,b) = |ab|.
a) Determinare f-1(0).
b) Stabilire se f è iniettiva e/o surgettiva.
c) Se p è un numero primo, quanti elementi ha f-1(p) ?
a) f-1(0) = { (a,b)∈ZxZ | |ab| =0}
(Il valore assoluto di un numero vale zero se e solo se il numero è zero)
Quindi: f-1(0) = { (a,b)∈ZxZ | ab =0 }
= { (a,b)∈ZxZ | a = 0 oppure b = 0}
= { (0,b) | b∈Z } ∪ { (a,0) | a∈Z }
b) f non è iniettiva:
(1,0) ≠ (0,1) in ZxZ , ma f(1,0) = f(0,1) = 0
f: ZxZ→ N tale che f(a,b) = |ab| è surgettiva se
∀ n ∈N ∃ (a,b) ∈ ZxZ t.c. f(a,b) = n.
Quindi il quesito è :
∀ n ∈N ∃ (a,b) ∈ ZxZ t.c. |ab| = n ?
sì, basta scegliere ad esempio a=n, b=1 e si è trovato un elemento (n,1) ∈ ZxZ (n ∈Z, perché n ∈N) che va bene !
b) Se p è un numero primo,quanti elementi ha f-1(p)?
f-1(p) = { (a,b)∈ZxZ | |ab| = p } = { (a,b)∈ZxZ | |a|⋅|b| =p }
Ma ogni numero primo p si decompone in fattori primi così: 1⋅ p oppure p ⋅ 1 . Da cui segue che:
|a| = 1 , |b| =p oppure |a|=p, |b| = 1, cioè a = ± 1, b = ± p oppure a = ± p, b = ± 1.
Quindi f-1(p) è l'insieme di 8 elementi :
{(1, p),(-1, p),(1, -p),(-1, -p),(p, 1),(-p, 1),(p, -1),(-p, -1)}
F
Fuunnzziioonnii
Funzioni iniettive, surgettive Funzioni bigettive tra insiemi infiniti
CeCennnnii ddii ccaallccoolloo ccoommbibinnaattoorriioo Permutazioni, disposizioni,combinazioni
I
Innvveerrttiibbiilliittàà ddeellllee ffuunnzziioonnii Inversa destra – inversa sinistra
Rosalba Barattero
ESERCITAZIONE N.2 31 ottobre 2006
ESERCIZIOC1.2
Ancora sulle funzioni iniettive , surgettive
1) Sia f: Z→ ZxZ la funzione definita da f(n)=(n2,n).
a)Determinare la controimmagine f−1((1,1)).
b)Stabilire se f è iniettiva, surgettiva.
2) Provare che la funzione f:ZxZ→N definita da f(a,b)=|ab|
è surgettiva.
3) Provare che la funzione definita da f: Z → N
⎩⎨⎧
≤
−
= >
0 n se
n 1
- ) 2n
( n
n se
f 2
0 è bigettiva.
1a) f−1((1,1)) = {n ∈ Z | f(n)= (1,1) } = {n ∈ Z | (n2,n) = (1,1) }
= {n ∈ Z | n2 = 1 e n= 1) } = {1}
Due coppie (a,b), (c,d) sono uguali se e solo se hanno gli elementi ordinatamente uguali, ossia a=c, c=d
ATT.ne È un insieme !
1b) f: Z→ ZxZ la funzione definita da f(n)=(n2,n)
Iniettività : f(x) = f(y) ⇒ x=y
Per def. f(x)=(x2,x), f(y)=(y2,y).
Da (x2,x)=(y2,y) ne segue che ⎩⎨⎧
=
= y x
y x2 2
quindi ⎩⎨⎧
=
= + y x
0 y) y)(x - (x
⇒ x=y Ok: f iniettiva
Surgettività: Im(f) = ZxZ
no, ad esempio (-1,1) ∉ Imf
perché non esiste n∈Z t.c. f(n) = (-1,1) ( f(n) =(n2,n)=(-1,1)
⇒ n2 =-1 :assurdo in Z).
2) f: ZxZ→ N tale che f(a,b) = |ab| è surgettiva se ∀ n ∈N ∃ (a,b) ∈ ZxZ t.c. f(a,b) = n.
Quindi il quesito è :
∀ n ∈N ∃ (a,b) ∈ ZxZ t.c. |ab| = n ?
sì, basta scegliere ad esempio a=n, b=1 e si è trovato un elemento (n,1) ∈ ZxZ (n ∈Z, perché n ∈N) che va bene !
In pratica si risolve l’equazione |ab| = n dove n è
supposto essere termine noto ed a, b sono le incognite.
Per la surgettività basta trovare una soluzione soltanto, se esiste ! ( Quindi una sola coppia (a, b) ).
3) f: Z N t.c. ⎩⎨⎧
≤
−
= >
0 n se 2
0 n 1 - ) 2n
( n
n se
f iniettiva
Dallafigura intuitivamente f risulta iniettiva e surgettiva.
0 1 2 3 4
-1 -2 -3
0 1 2 3 4
Z
N
Per provare correttamente l’ iniettività occorre distinguere 3 casi.
I CASO
Se m>0, n≤ 0 in Z (quindi m, n distinti)
⇒ f(m)=2m-1, f(n)=-2n
⇒ f(m) ≠ f(n), perché f(m) è dispari, mentre f(n) è pari.
ok!
II CASO
m ≤ 0, n ≤ 0 , m ≠ n ⇒ f(m) ≠ f(n)
In generale è meglio usare l’implicazione logica equi- valente che fa uso dell ″=″ anziché ″≠″ per poter applicare le note proprietà dell’uguaglianza rispetto alle operazioni.
Mostriamo quindi che:
f(m) = f(n), m ≤ 0, n ≤ 0 ⇒ m=n
Se f(m) = f(n) con m ≤ 0, n ≤ 0 ⇒ -2m = -2n
⇒ m = n ok!
III CASO
Mostriamo che : m>0, n>0, f(m)=f(n) ⇒ m=n Se f(m) = f(n) con m>0, n>0 ⇒ 2m-1 = 2n-1
⇒ m=n Conclusione: f è iniettiva.
Proviamo ora la surgettività di f: Z N t.c
⎩⎨
⎧
≤
−
= >
0 n se 2
0 n 1 - ) 2n
( n
n se f
Proviamo cioè che vale la proprietà:
∀ b ∈ N ∃ a ∈ Z t.c. f(a)=b
Dobbiamo distinguere i pari dai dispari:
♦ se b ∈ N e b è dispari, b è del tipo b = 2a-1 con a∈N*, ma 2a-1 è proprio f(a) quando a>0 (per def. di f),quindi abbiamo trovato a∈Z t.c. b=f(a) ok!
♦ se b ∈ N e b è pari, dobbiamo trovare a∈ Z t.c. f(a)=b, ossia t. c. –2a = b, con a≤0. Supposto quindi b dato, e a incognita, si ha che
∀ b∈ N, b pari ∃ a= −2b , a∈ Z, t.c. f(a)=b. ok!
OSSERVAZIONE : La funzione f che abbiamo studiato è bigettiva e stabilisce quindi una corrispondenza biunivoca tra i due insiemi infiniti N e Z. Si dice che Z è numerabile, o che ha la stessa cardinalità di N, nel senso che riusciamo a “contare fino all’infinito” gli elementi di Z (uno, due, tre, …. ), essendo Z in corrispondenza biunivoca con N.
ESERCIZIOC2.2
Contiamo le funzioni…
Siano A ={1,2,3}, B={1,2,3,4}. Si considerino gli insiemi seguenti
a) X = {funzioni f: A →B}
b) Y = {funzioni iniettive f: A →B}
c) Z = {funzioni iniettive f: A →B tali che f(1)=1}
d) W = {funzioni surgettive f: A →B}
Dire quanti elementi hanno gli insiemi X, Y, Z,W.
a) f: {1,2,3}→ {1,2,3,4} è una funzione quando ad ogni elemento del dominio fa corrispondere uno ed un solo elemento del codominio.
Ad esempio:
1 → 3 2 → 2 3 → 3
In generale le funzioni da A in B sono |B||A|
dove con |A| indichiamo la cardinalità dell’insieme A.
f è individuata da una terna ordinata (•,∗,♦) di elementi del codominio (che possono anche essere ripetuti). Quante sono queste terne? Per ogni elemento abbiamo 4 scelte.
In totale 4⋅4⋅4 = 43 = 64. Quindi |X|=64.
f
b) f: {1,2,3}→ {1,2,3,4} funzione iniettiva: funzione che manda elementi distinti in elementi distinti.
Ad esempio:
f: {1,2,3}→ {1,2,3,4} t.c. 1 →3, 2 →4, 3 →1
f è individuata da una terna ordinata (•,∗,♦) di elementi distinti del codominio.
Quante sono queste possibili terne (f(1),f(2),f(3)) ? Ci sono 4 scelte per il I° elemento f(1) che, una volta fissato, consente 3 scelte per il II°, e così … 2 scelte per il III° ( per l’iniettività! ).
In totale le terne sono : 4 ⋅ 3 ⋅ 2 = 24. Quindi |Y|=24.
QUESITO
E’ una domanda “equivalente” chiedere:
quante sono le possibili assegnazioni di medaglie (oro, argento, bronzo) in una gara a cui partecipano 4 concorrenti ?
Sì, perché…
Le funzioni iniettive f: A →B con A={1,2,3,…k}, |B|=n, (k ≤ n) si chiamano disposizioni (semplici) di n oggetti di classe k , con k ≤ n
( nel nostro esempio:k=3, n=4) e il loro numero è Dn,k = n ⋅ (n-1) ⋅ (n-2) ⋅ ⋅ ⋅ (n-(k-1))
D4,3 = 4 ⋅ 3 ⋅ 2 ( 3 fattori decrescenti consecutivi) . (Cfr. lo schema riassuntivo alle pagine successive).
c) funzioni iniettive f: {1,2,3}→ {1,2,3,4} tali che f(1)=1.
1 → 1
2 → ♣ abbiamo per ♣ 3 scelte ( va escluso 1 ) 3 → ♠ abbiamo per ♠ 2 scelte (va escluso 1 e ♣ )
Sono in pratica tante quante le funzioni iniettive di {2,3}→ {2,3,4}, cioè 3⋅2=6. Quindi |Z|=6.
Se f fosse surgettiva sarebbe Im(f) = B, ma B ha 4 elementi e Imf ha al massimo 3 elementi : assurdo!
⇒ non ci sono f surg.
RIEPILOGO
Denominazione Definizione Numero Disposizione con
ripetizione
Funzione : A →B
A={1,2,3,…k}, |B|=n nk
Disposizione (semplice) Funzione iniettiva: A →B
A={1,2,3,…k}, |B|=n, (k ≤ n) n(n-1)(n-2)…(n-(k-1))
Permutazione
Funzione bigettiva: A →A o funzione bigettiva f :{1,2,3,…,n}→A, n=|A|
n!
Combinazione di classe k di n elementi , k≤n
Sottoinsieme di {1,2,3,…n} di k
elementi ⎟⎟⎠
⎜⎜ ⎞
⎝
⎛ k n d)
ESERCIZIOC3.2
… ancora un po’ di calcolo combinatorio
a) Quanti sono i possibili anagrammi della parola “Esami”
( senza tener conto del significato ! ) ?
b) Quanti sono i possibili terni al gioco del lotto ? c) Quante sono le possibili colonne di 13 al totocalcio ?
a) Sono tutti i possibili modi di “disporre”,tenendo conto dell’ordine, i caratteri “e, s, a, m, i”, o meglio tutti gli elementi dell’insieme {e,s,a,m,i}.
Sono tanti quante le funzioni bigettive
f: A={e,s,a,m,i} → A={e,s,a,m,i}, o equivalentemente g: A={1,2,3,4,5} → A={e,s,a,m,i}, e si chiamano permutazioni di A.
Le permutazioni si possono riguardare come un caso particolare delle disposizioni (semplici), quando n=k.
Il numero delle permutazioni di un insieme di n elementi è:
n(n-1)(n-2) ⋅ ⋅ ⋅ 1 = n! ( n fattoriale ).
Nel nostro caso sono 5! = 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 120.
Notiamo che nel caso finito per f:A→ A si ha : f bigettiva ⇔ f iniettiva ⇔ f surgettiva
b) Contiamo le possibili terne scelte nell’insieme L={1,2,3,4,…..,90}.
Poiché non conta l’ordine,ma solo gli elementi stessi ( non ripetuti), sono tutti i possibili sottoinsiemi di 3 elementi di L.
Si chiamano “ combinazioni” di classe k degli n elementi ( qui k=3, n= 90 ).
Il numero delle combinazioni di n elementi di classe k ( k≤ n) è Cn,k = ⎟⎟⎠⎞
⎜⎜⎝
⎛ k n =
k!
1)) (k (n 2) 1)(n
n(n− − ⋅⋅⋅ − −
(al numeratore:k fattori decrescenti).
N.B. E’ la formula ⎟⎟⎠
⎜⎜ ⎞
⎝
⎛ k
n = (n k)!k!
n!
− semplificata.
Nel nostro caso C90,3 = ⎟⎟⎠
⎜⎜ ⎞
⎝
⎛ 3
90 = 3! 88 89 90⋅ ⋅
= 3 2 1 88 89 90
⋅
⋅
⋅
⋅ =117.480.
Curiosità : la probabilità di fare terno, giocando 1 sola volta è pari a 117480
1
. ∼ 0.000008512 ossia ∼ 0.0008512 %
c) Si tratta di contare tutte le funzioni f: {1,2,3,….,13}→ {1,x,2}.
Il loro numero è quindi 313 .
ESERCIZIOC4.2
Funzioni composte
Sono date la funzione f:ZxZ →Z definita da f((x,y)) =x-y e la funzione g:Z →Z xZ definita da g(n) = (n+1,3n).
Stabilire il dominio e il codominio delle funzioni f ○ g, g ○ f e darne la rispettiva definizione.
La funzione f ○ g è definita poiché il codominio di g coincide con il dominio di f.
Z⎯⎯→g ZxZ⎯⎯→f Z
n⎯⎯→g (n +1,3n)
(x,y)⎯⎯→f x− y
n g(n) = (n+1,3n) f((n+1,3n)= n+1-3n=1-2n
Z ⎯⎯ →f⎯og Z t.c. f ○ g (n) = 1-2n.
Analogamente si trova ZxZ⎯⎯ →g⎯of ZxZt.c. g○f (x,y)=(x-y+1,3x-3y).
Sta in “codominio di g” = “dominio di f”
dominio codominio
ESERCIZIOC5.2
Inversi destri – inversi sinistri
Sia f: ù→ù la funzione definita da f(n) =n+1.
a) Stabilire se ha inversa sinistra e in caso affermativo determinarne una.
b) Stabilire se ha inversa destra.
c) Stabilire se è invertibile.
a) Data f: ù →ù si dice inversa sinistra di f una funzione g: ù →ù t.c. g ○ f = Idù .
Vale la seguente proprietà : f ha inversa sinistra ⇔ f è iniettiva
La funzione f: ù →ù definita da f(n) =n+1 è iniettiva se: f(x) = f(y) ⇒ x= y.
Ma f(x) = x+1, f(y) =y+1, e da x+1=y+1 discende x=y,
quindi f è iniettiva ed ha inversa sinistra.
Troviamola ( o troviamone una ! ).
ù ù ù 0 → 1 → 0
1 → 2 → 1 2 → 3 → 2 . → . → .
Problema
g non è stata “automaticamente” definita in 0.
Come definiamo g(0) = ?
Come g(0) va bene un qualsiasi numero naturale, poiché g(0) non interviene nel fare la composizione.
Quindi scriviamo la definizione di una delle infinite g inverse sinistre di f.
Ad esempio: g: ù → ù t.c. g(n)= ⎩⎨⎧0n −1 sese nn=≥10
Oppure anche g(n)= |n-1| va bene, oppure … g
f
Imponiamo la condizione g ○ f = Idù
b) Data f: ù →ù si dice inversa destra di f una funzione g: ù →ù t.c. f ○ g = Idù .
Vale la seguente proprietà :
f ha inversa destra ⇔ f è surgettiva.
f è surgettiva se
∀ y∈ù (codominio) ∃ x∈ù (dominio) t.c. f(x) = y.
Ma dallo schema fatto vediamo che 0 ∉ Im(f) , in
altre parole, scelto y=0 (nel condominio di f ) non esiste x ∈ ù (dominio) t.c. f(x) = 0.
Quindi f non è surgettiva e di conseguenza non ha inversa destra.
c) f è invertibile se ∃ g: ù →ù tale che f○g=Idù e g○f=Idù Per b) f non è invertibile perchè non ha inversa destra.
O equivalentemente, usando la proprietà (cfr. teoria)
"f invertibile ⇔ f è bigettiva"
si ricava che f non è invertibile, perché non è bigettiva.
FuFunnzziioonnii iinnvveerrttiibbiillii
LaLa ddiivviissiioonnee iinn ZZ :: aapppplliiccaazziioonnii MM. . CC.. DD..
AlAlggoorriittmmoo eeuucclliiddeeo o IdIdeennttiittàà ddii BBeezzoouutt
Rosalba Barattero
ESERCITAZIONE N.3 7 novembre 2006
ESERCIZIOC1.3
E’ la funzione inversa ?
Sia f: Z2 → Z2 la funzione definita da f(x,y) = (x-y+1, x+1).
Provare che g: Z2 → Z2 definita da g(a,b) = (b-1,b-a) è l’inversa di f.
Ricordiamo che :
• f:A →A è invertibile se ∃ g:A →A t.c. f○g=IdA e g○f=IdA
• Se f è invertibile allora l’inversa è unica (coincide con g).
Quindi per provare che g è l’inversa di f basta verificare che valgono le due condizioni f ○ g = IdA e g ○ f = IdA .
¾ f ○ g : Z2 → Z2 f(g(a,b)) = f(b-1,b-a)
= ( b-1– (b-a) +1, (b-1)+1) = (a,b)
⇒ f ○ g = Id Z2
¾ g ○ f = IdA g(f(x,y)) = g((x-y+1, x+1))
= ((x+1)-1, (x+1)-(x-y+1)) = (x,y)
⇒ f ○ g = Id Z2 OK
ESERCIZIOC2.3
Determinazione dell’inversa destra ( quando esiste)
a) Provare che la funzione f:R→R+ definita da f(x) = x2 ammette inversa destra
b) Determinare tutte le inverse destre di f . a) f ammette inversa destra ⇔ f è surgettiva
Proviamo che ∀ y∈R+ (reali≥0)lacontroimmagine f-1(y) di y mediante f non è vuota.
f-1(y) = {x∈R| f(x)=y}
= {x∈R| x2=y}
= {x∈R| x=± y }
La controimmagine di y non è mai vuota, quindi f è surgettiva.
b) g :R+→R è inversa destra di f se f ○ g = IdR+. Ma com’è definita ? Basta porre g(y)= y’ con y’ ∈ f-1(y).
R R+ x x2
R R+ y y
f
g
Ci sono in questo caso 2 possibili inverse destre di f:
g: R+→R t.c. g(y) = y e h: R+→R t.c. h(y) = - y . Infatti per entrambe si ha:
f(g(y)) = f( y ) = y ∀ y∈ R+ f(h(y)) = f(- y) = y ∀ y∈ R+
ESERCIZIOC3.3
Determinazione dell’inversa
a) Determinare l’inversa della funzione f:IR → IRdefini- ta da f(x) = 2x-3.
b) Determinare l’inversa della funzione g:ZxZ→ZxZ de- finita da g(a,b)=(a-1,2a+b).
Se mostriamo che la controimmagine di ogni elemento y del co- dominio è un sottoinsieme del dominio costituito da un solo e- lemento (diverso dal vuoto), proviamo che f è bigettiva e trovia- mo simultaneamente anche la definizione della funzione inversa.
Se y ∈ R (codominio), la controimmagine di y è f –1 (y) ={x ∈ R (dominio) | f(x)=y}.
Quindi risolviamo l’equazione 2x-3 = y , dove possiamo supporre y noto e x incognita. Ricaviamo x= y2+3 unica soluzione.
Conclusione: f è bigettiva e la sua inversa è la funzione g: R → R definita da g(y) = y2+3. ( La funzione inversa si indica spesso f-1).
Attenzione: f-1(y) ha due diversi significati !.
b) g:ZxZ→ZxZ definita da g(a,b)=(a-1,2a+b) Poniamo (a-1,2a+b) = (x,y).
Deduciamo che ⎩⎨⎧
= +
=
−
y b 2a
x 1 a
.
Supponiamo x,y noti, a,b incognite che ricaviamo:
⎩⎨⎧
= +
=
2a - y b
1 x a
⇒ ⎩⎨⎧
+
= +
=
1) 2(x - y b
1 x a
⇒ ⎩⎨⎧
−
= +
=
2 2x - y b
1 x a
Per ogni (x,y)∈ZxZ codominio esiste una ed una sola soluzione: l’elemento (a,b)∈ZxZ dominio tale che g(a,b) =(x,y) , per cui g è bigettiva e la sua inversa è h(x,y) = (x+1,y-2x-2).
LA DIVISIONE EUCLIDEA IN Z
Siano a, b ∈ Z , b≠0. Allora esistono e sono unici due inte- ri, il quoziente q e il resto r tali che a = b q +r , con 0≤r<|b|.
Come si fa la divisione se entrambi o uno dei numeri a, b è negativo ?
Esempio 1 : -62 : 20 = ?
-62 = 20 (-3) – 2 Non va bene ! il resto è negativo !
-62 = 20(-4) + 18 OK !
Esempio 2: 62 : (-20) = ?
Si fa 62 = 20 ⋅ 3 +2, poi si cambia segno …
62 = (-20) ⋅ (- 3) +2
Esempio 3: (-62) : (-20) = ?
(-62) = (-20) ⋅ 4 +18.
Vediamo un’ applicazione dell’algoritmo della divisione.
ESERCIZIOC4.3
Numeri di patente in Florida
I numeri di patente in Florida sono codificati nel modo se- guente SSSS-FFF-YY-DDD, dove nei gruppi con ′S′ ed ′F′
ci sono informazioni relative a nome e cognome, mentre YY indicano le ultime due cifre dell’anno di nascita e DDD codificano il mese m e il giorno b di nascita secondo la se- guente espressione:
40(m-1)+b nel caso dei maschi,
40(m-1)+b+500 nel caso delle femmine.
Trascuriamo i casi di persone aventi lo stesso numero di patente, etc.
Determiniamo la data di nascita e il sesso dei titolari di pa- tente aventi un numero di patente le cui ultime 5 cifre del codice sono: 80251, 62789.
80251: 80 indica l’anno di nascita 1980
251 corrisponde a 40(m-1)+b , poiché risulta 40(m-1)+b+500 ≥ 501. Si tratta quindi di maschio.
251 : 40 = ? 251= 40 ⋅ 6+11
6 è il quoziente e 11 il resto (univocamente determinati).
⇒ 80251 : maschio nato il giorno 11 luglio 1980
62789: 62 indica l’anno di nascita 1962
789 corrisponde a 40(m-1)+b+500, poiché il mas simo di 40(m-1)+b è 40 ⋅ 11 +31 = 471. Si tratta quindi di femmina.
789= 40(m-1)+b+500 ⇒ 789-500= 40(m-1)+b ⇒ 289=40(m-1)+b 289 : 40 = ? 289= 40 ⋅ 7+9
7 è il quoziente e 9 il resto (univocamente determinati).
⇒ 62789 : femmina nata il giorno 9 agosto 1962.
Per approfondimenti su US Driver's License Numbers:
http://www.highprogrammer.com/alan/numbers/dl_us_shared.html http://www.highprogrammer.com/alan/numbers/dl_us_shared_mmm.html
Qui un applet Java per codificare i dati della Florida
http://www.highprogrammer.com/cgi-bin/uniqueid/dl_fl
ESERCIZIOC5.3
M.C.D.
Calcolare il massimo comun divisore delle seguenti coppie di numeri:
a) M.C.D. ( 12, 18)
b) M.C.D. ( 23⋅32⋅5 , 2 ⋅33 ⋅11) c) M.C.D. ( 84, 120)
def. di M.C.D. (a,b) , con a, b interi non nulli:
è quell’intero d tale che
• d|a e d|b
• per ogni intero c tale che c|a e c|b, risulta c|d
a) M.C.D. (12,18)= 6
Anche -6 va bene, ma prendiamo quello positivo, nel senso che in Z M.C.D. è unico a meno del segno.
L’insieme dei divisori comuni è: {1,2,3,6}
6 è il più grande dei divisori comuni, ed è anche multiplo di tutti i divisori.
b) M.C.D. ( 23⋅32⋅5 , 2 ⋅33 ⋅11) =
C’era una regoletta che suonava così:
″il M.C.D. si calcola moltiplicando i fattori primi che com- paiono in entrambe le scomposizioni ( in fattori primi), cia- scuno preso con il minimo esponente″.
M.C.D. ( 23⋅32 ⋅5 , 2 ⋅33 ⋅11) = 2⋅32 =18
c) M.C.D. ( 84, 120) = ?
Usiamo il “vecchio” metodo della scomposizione in fat- tori primi.
84 2 120 2
42 2 60 2
21 3 30 2
7 7 15 3
1 5 5
1
Sempre con la vecchia regoletta risulta M.C.D. ( 84,120) = 22⋅ 3 = 12
Quindi si ha:
84 = 22⋅ 3 ⋅ 7 120 = 23⋅ 3 ⋅ 5
ESERCIZIOC6.3
M.C.D. con l'algoritmo euclideo
Calcolare il M.C.D. tra 120 e 84 con l’algoritmo di Euclide.
L'algoritmo euclideo consiste in una sequenza di divisioni successive:
1. 120 = 84 ⋅ 1 + 36 2. 84 = 36 ⋅ 2 + 12
3. 36 = 12 ⋅ 3
L’algoritmo di Euclide afferma che l’ultimo resto non nullo è il M.C.D. Abbiamo ritrovato M.C.D. (120,84) = 12 .
Questo succede perché il M.C.D. tra dividendo e divisore di una divisione euclidea (purchè i due numeri non siano uno multiplo dell’altro) è uguale al M.C.D. tra divisore e resto.
Così si conclude: M.C.D. ( 120,84) = M.C.D. ( 84,36) = M.C.D. ( 36,12) = 12 .
poiché il resto è 36≠0, procediamo dividendo il divisore 84 per il resto 36, e così via, fino ad avere resto nullo.
ESERCIZIOC7.3
Identità di Bezout
Calcolare mediante l’algoritmo euclideo il M.C.D. delle se- guenti coppie di interi: (120,84), (501,468) e scrivere la corrispondente identità di Bezout.
Algoritmo euclideo
4. 120 = 84 ⋅ 1 + 36 5. 84 = 36 ⋅ 2 + 12
6. 36 = 12 ⋅ 3
Con l'algoritmo euclideo troviamo M.C.D.(120,84)=12.
Ora ricordiamo che vale il seguente Teorema di Bezout
Se d= M.C.D. (a,b),allora esistono due interi m, n tali che d= am +bn.
Scriviamo dunque 12 come combinazione lineare di 120 e 84,ossia cerchiamo due interi x e y tali che 120x +84y=12.
poiché il resto è 36≠0, procediamo dividendo il divisore 84 per il resto 36, e così via, fino ad avere resto nullo.
Alla tabella precedente affianchiamo a destra l’espressione dei resti:
1. 120 = 84 ⋅ 1 + 36 36 = 120 - 84 ⋅ 1 2. 84 = 36 ⋅ 2 + 12 12 = 84 - 36 ⋅ 2 3. 36 = 12 ⋅ 3
Partiamo dalla riga 2.(quella in cui compare l’ultimo resto non nullo ), e sostituiamo a ritroso i resti:
12 = 84 - 36 ⋅ 2
= 84 – (120 - 84 ⋅ 1) ⋅ 2 = 84 – 120 ⋅ 2 + 84 ⋅ 2
= 120 (-2) + 84 (3) OK !
N.B. I coefficienti dell’uguaglianza di Bezout NON sono unici !
Ad esempio vale anche:
12 = 120 (-9) + 84 (13) ( = -1080 + 1092) .
…vedremo presto perché !
Ora rifacciamo la procedura per trovare il
M.C.D. (501,468) e la relativa identità di Bezout.
1. 501 = 468 ⋅ 1 + 33 33 = 501 - 468 ⋅ 1 2. 468 = 33 ⋅ 14 + 6 6 = 468 - 33 ⋅ 14
3. 33 = 6 ⋅ 5 + 3 = 33 - 6 ⋅ 5 4. 6 = 3 ⋅ 2
Facciamo il procedimento di “goback” , a partire da 3. per trovare i coefficienti dell’identità di Bezout.
3 = 33 - 6 ⋅ 5
= 33 - ( 468 - 33 ⋅ 14) ⋅ 5 = 468 (-5) + 33 (71) = 468 (-5) + (501 - 468 ⋅ 1)(71)= 501 (71)+468 (-76)
CONCLUSIONE. M.C.D.(501,468)=3 &
3 = 501 (71) + 468 (-76) q r
ultimo resto non nullo ⇒ M.C.D.(501,468)=3 3
EqEquuaazizioonnii ddiiooffaantnteeee lliinneeaarrii a
apppplliiccaazziioonnii eelleemmeennttaarrii pprraattiicchhee:: i
ill pprroobblleemma a cciinneessee ddeeii 110000 ppoollllii
ReRellaazziioonnii ssuu iinnssiieemmii
DoDommaannddee iinntteerreessssaannttii popossttee iinn aauullaa ddaaglglii ssttuuddeennttii
Rosalba Barattero
ESERCITAZIONE N.4 14 novembre 2006
EQUAZIONI DIOFANTEE LINEARI (= equazioni di I° grado a coefficienti
in Z che vengono risolte in Z)
1INCOGNITA
Esempi a) 3x=4 non ha sol. in Z
b) 5x=10 ha unica sol. in Z, x= 10/5 =2
Quindi ax=b con a, b ∈ Z , a≠0 ha un’unica soluzione in Z (x= b/a) se e solo se a|b ( a divide b)
Altrimenti non ci sono soluzioni in Z
2INCOGNITE
Esempi a) 4x+6y=3 non ha sol. in Z:comunque si sostituiscano x e y con due interi il I° membro è pari, il secondo è dispari.
Si noti che in R l’equazione ha infinite soluzioni, basta assegnare ad x un generico valore reale t e ricavare il corrispondente
y= 6
4t 3−
, con t∈R .
b) 3x+6y=18 ha soluzioni intere,ad esempio (4,1), (-6,6),(10,-2).
