Risoluzione esercizi di Matematica Discreta

Risoluzione esercizi di Matematica

DiscretaA cura della dott.ssa Maria Santa Santo

Indice

1 Esercizi sulle funzioni 1

2 Esercizi sulle relazioni d'ordine e di equivalenza 8

3 Esercizi sul principio di induzione 15

4 Esercizi sulle strutture algebriche: gruppi, anelli e campi 19

i

Capitolo 1

Esercizi sulle funzioni

Di seguito proponiamo lo svolgimento di alcuni esercizi sulle funzioni. Percomprenderli meglio è necessario che si abbiano i seguenti prerequisiti:

1. conoscenza del concetto di funzione,

2. di funzione iniettiva, suriettiva, biiettiva,

3. di funzione inversa,

4. di composizione di funzioni.

Esercizio 1.1 Siano date le seguenti leggi

g : N→ R, g(n) =√n− 4

eh : R→ R, h(x) = x3 + 5.

Stabilire se sono funzioni. In caso a�ermativo, provare se sono iniettive, su-riettive o biiettive. Calcolare, ove possibile, le funzioni inverse g−1 e h−1, ele composizioni h ◦ g e g ◦ h.

Svolgimento. La legge de�nita da h è sicuramente una funzione, infattiad ogni valore x di R viene associata la sua potenza x3, che è ancora unnumero reale, sommata al numero reale 5. Complessivamente si ottiene unnumero reale. Anche la legge de�nita da g è una funzione, infatti ad ogninumero naturale n viene associata la sua radice quadrata

√n, che è ancora un

numero reale (oltre ad essere ben de�nita dato che è la radice quadrata di unnumero positivo) a cui viene sottratto il numero 4. L'immagine di n non saràsempre un numero naturale, ma sicuramente un numero reale (ricordiamo chel'insieme dei numeri reali è formato dai numeri naturali, interi, razionali e

1

2

irrazionali).Detto ciò, stabiliamo se g è iniettiva cioè:

∀n1, n2 ∈ N g(n1) = g(n2)⇒ n1 = n2.

Siano n1, n2 ∈ N tali che g(n1) = g(n2) e proviamo che n1 = n2. Si ha:

g(n1) = g(n2)⇔√n1 − 4 =

√n2 − 4⇔

√n1 =

√n2 ⇔ n1 = ±n2.

Ma l'insieme di partenza di g è N, pertanto n1 = ±n2 se e solo se n1 = n2

(escludiamo il caso n1 = −n2, infatti, in tal caso, si otterrebbe un numeronaturale, n1, uguale ad un numero negativo −n2, che è sicuramente nega-tivo poiché n2 è un numero positivo). Quindi g è iniettiva. Ora, vogliamocontrollare se g è suriettiva, cioè:

∀x ∈ R ∃n ∈ N tale che g(n) = x.

Sia x ∈ R e si supponga che esista n ∈ N tale che g(n) = x, quindi si ha

g(n) = x⇔√n− 4 = x⇔

√n = x+ 4.

Sicuramente se x = −10 si ottiene√n = −6, ma ciò è impossibile poiché

la radice quadrata di un numero (positivo) è sempre una quantità positiva.Allora g non è suriettiva. Da ciò risulta che g non è biiettiva e quindi nonammette inversa g−1.Per quanto riguarda h, stabiliamo se è iniettiva cioè:

∀x1, x2 ∈ R h(x1) = h(x2)⇒ x1 = x2.

Siano x1, x2 ∈ R tali che h(x1) = h(x2) e proviamo che x1 = x2. Si ha:

h(x1) = h(x2)⇔ x31 + 5 = x3

2 + 5⇔ x31 = x3

2 ⇔ x1 = x2.

Quindi h è iniettiva. Ora, controlliamo se h è suriettiva cioè:

∀y ∈ R ∃x ∈ R tale che h(x) = y.

Sia y ∈ R e si supponga che esista x ∈ R tale che h(x) = y, quindi si ha

h(x) = y ⇔ x3 + 5 = y ⇔ x3 = y − 5⇔ x = 3»y − 5. (1.1)

Osserviamo che la radice cubica del numero reale y − 5 è sicuramente unnumero reale per ogni scelta di y in R (dato che abbiamo una radice di indicedispari non è necessario che sia veri�cata la condizione che il radicando (y−5)

3

sia maggiore o uguale a 0). Pertanto h è suriettiva. Poiché h è iniettiva esuriettiva allora è biiettiva. Possiamo determinare l'inversa di h data dallafunzione

h−1 : R→ R, h−1(y) = 3»y − 5,

la cui espressione è ottenuta sfruttando il calcolo (1.1) fatto per provare laproprietà suriettiva. In�ne, ci chiediamo se sono possibili le composizionig ◦h e h◦g. Ricordiamo che la composizione tra due funzioni f ◦g è possibilese il dominio (insieme di partenza) della funzione f coincide con il codominio(insieme di arrivo) della funzione g. Nel nostro caso, notiamo che il dominiodi g è N e non coincide con il codominio di h che è R. Pertanto non èpossibile determinare g ◦ h. D'altra parte, per quanto riguarda h ◦ g, si hache il dominio di h, cioè R, coincide con il codominio di g, cioè R. Quindipossiamo calcolare la composizione di h con g:

h ◦ g : N→ R→ R, h(g(n)) = h(√n− 4) = (

√n− 4)3 + 5.

Esercizio 1.2 Siano date le seguenti funzioni

h : Z→ R− {1}, h(x) = 2 | x | −1

2e

g : R− {1} → R− {0}, g(n) = n3 − 1.

Stabilire se sono iniettive, suriettive o biiettive. Calcolare, ove possibile, lefunzioni inverse h−1 e g−1, e le composizioni h ◦ g e g ◦ h.

Svolgimento. Osserviamo che l'esercizio non ci chiede di veri�care che leleggi assegnate siano funzioni, pertanto procediamo direttamente nella veri�-ca delle loro proprietà. Consideriamo inizialmente la funzione h e stabiliamose è iniettiva. Siano x1, x2 ∈ Z tali che h(x1) = h(x2), si ha

h(x1) = h(x2)⇔ 2 | x1 | −1

2= 2 | x2 | −

1

2⇔ 2 | x1 |= 2 | x2 | ⇔ | x1 |=| x2 |.

Ma| x1 |=| x2 |⇔ x1 = ±x2,

quindi, dato che x1 e x2 sono due numeri interi, non è possibile escluderenessun caso (diversamente da quanto fatto nell'esercizio precedente): x1 puòessere uguale a x2, ma può anche essere uguale a −x2. Quest'ultima possibi-lità (cioè x1 = −x2) ci dice che h non è iniettiva.Inoltre h non è suriettiva. Infatti, sia y ∈ R − {1} e si supponga che esistax ∈ Z tale che h(x) = y, quindi

h(x) = y ⇔ y = 2 | x | −1

2⇔ 2 | x |= y +

1

2⇔ | x |= y

2+

1

4.

4

Se y = 4 allora

| x |= 4

2+

1

4⇔ | x |= 2 +

1

4⇔ | x |= 9

4⇔ x = ±9

4/∈ Z.

Ciò contraddice la de�nizione di suriettività (in corrispondenza dell'y �ssato,abbiamo determinato x che non è un numero intero). Possiamo dedurre cheh non è suriettiva e quindi neanche biiettiva. In realtà, potevamo già dedurlodopo aver veri�cato che h non è iniettiva. Pertanto non è possibile calcolareh−1.Ora, stabiliamo se g è iniettiva. Siano n1, n2 ∈ R−{1} tali che g(n1) = g(n2),quindi si ha

g(n1) = g(n2)⇔ n31 − 1 = n3

2 − 1⇔ n31 = n3

2 ⇔ n1 = n2.

Ciò prova che g è iniettiva. Vediamo se g è anche suriettiva. Sia x ∈ R−{0}e si supponga che esista n ∈ R− {1} tale che g(n) = x, quindi

g(n) = x⇔ n3 − 1 = x⇔ n3 = x+ 1⇔ n = 3√x+ 1.

Poiché x è un numero reale diverso da 0, allora il radicando x + 1 è semprediverso da 1, e quindi n = 3

√x+ 1 è sicuramente un elemento di R − {1}.

Pertanto g è suriettiva, e quindi biiettiva. La sua inversa è data dalla funzione

g−1 : R− {0} → R− {1}, g−1(x) = 3√x+ 1.

Osserviamo che l'unica composizione possibile è g ◦ h, infatti solo in questocaso risulta che il dominio della prima funzione (g) coincide con il codominiodella seconda funzione (h). Quindi, si ha

g ◦ h : Z→ R− {1} → R− {0},

g(h(x)) = g

Ç2 | x | −1

2

å=

Ç2 | x | −1

2

å3

− 1.


h : R→ R, h(a) = a5 − 2

eg : Q→ R, g(n) = 2− n2.

Stabilire se sono funzioni, ed in tal caso se sono iniettive, suriettive o biiet-tive.Calcolare, ove possibile, le funzioni inverse h−1 e g−1, e le composizionih ◦ g e g ◦ h.

5

Svolgimento. Innanzitutto osserviamo che entrambe le leggi sono duefunzioni; infatti h ad ogni valore a di R associa la sua quinta potenza a5, cheè ancora un numero reale, e ad essa sottrae 2. Sicuramente la quantità che siottiene è un numero reale. Con un ragionamento analogo, considerata la leggede�nita da g, osserviamo che ad ogni n, numero razionale, viene associato n2

che è un numero razionale, e quindi reale, che viene sottratto da 2, ottenendoancora un numero reale. Pertanto possiamo procedere veri�cando se g ed hsono funzioni iniettive, suriettive e biiettive. Consideriamo la funzione h estabiliamo se è iniettiva. Siano a1, a2 ∈ R tali che h(a1) = h(a2), quindi

h(a1) = h(a2)⇔ a51 − 2 = a52 − 2⇔ a51 = a52 ⇔ a1 = a2,

da cui risulta che h è iniettiva.Proviamo la suriettività: sia y ∈ R e si supponga che esista a ∈ R tale cheh(a) = y, quindi

h(a) = y ⇔ a5 − 2 = y ⇔ a5 = y + 2⇔ a = 5»y + 2 ∈ R.

Allora h è suriettiva, quindi biiettiva, e pertanto possiamo determinare lasua inversa

h−1 : R→ R, h−1(y) = 5»y + 2.

Procediamo analogamente per g. Dapprima, stabiliamo se è iniettiva. Sianon1, n2 ∈ Q tali che g(n1) = g(n2), quindi si ha

g(n1) = g(n2)⇔ 2− n21 = 2− n2

2 ⇔ n21 = n2

2 ⇔ n1 = ±n2,

cioè la funzione g non è iniettiva (non è possibile escludere il caso n1 =−n2 poiché n1 e n2 sono due numeri razionali e pertanto potrebbero esserenegativi). Ciò esclude il caso che g possa essere biiettiva. Inoltre g nonè suriettiva, infatti �ssato y ∈ R, si supponga che esista n ∈ Q tale cheg(n) = y, si ha

g(n) = y ⇔ 2− n2 = y ⇔ n2 = y + 2⇔ n = ±»y + 2.

Ma√y + 2 /∈ Q, infatti se y = 3 si avrebbe

√y + 2 =

√5 che non è un numero

razionale. Quindi g non è suriettiva e pertanto non è possibile determinarela sua inversa. Per quanto riguarda le composizioni g ◦ h e h ◦ g, osserviamoche l'unica ammissibile è la seconda dato che solo in questo caso il dominiodi h coincide con il codominio di g. Pertanto si ha

h ◦ g : Q→ R→ R, h(g(n)) = h(2− n2) = (2− n2)5 − 2.

6


h : N→ R, h(x) =1 + x

x+ 5e

f : R→ R, f(z) =1

4z3 + 7.

Stabilire se sono funzioni, ed in tal caso se sono iniettive, suriettive o biietti-ve. Calcolare, ove possibile, le funzioni inverse h−1 e f−1, e le composizionih ◦ f e f ◦ h.

Svolgimento. Inizialmente stabiliamo se h e g sono due funzioni. Osser-viamo che h, ad ogni numero naturale x, associa sempre un numero razionalee quindi un numero reale (x assume valori maggiori o uguali a 0 quindi il de-nominatore x+5 è sempre strettamente maggiore di 0). La legge de�nita dag ad ogni numero reale z associa la sua terza potenza z3 moltiplicata per 1

4

ottenendo ancora un numero reale, che, sommato a 7, appartiene all'insiemedi arrivo.Ora, possiamo stabilire se h è una funzione iniettiva. Siano x1, x2 ∈ N taliche h(x1) = h(x2), allora si ha

h(x1) = h(x2)⇔1 + x1

x1 + 5=

1 + x2

x2 + 5

⇔ (1 + x1)(x2 + 5) = (1 + x2)(x1 + 5)

⇔ x2 + 5 + x1x2 + 5x1 = x1 + 5 + x1x2 + 5x2

⇔ x2 + 5x1 = x1 + 5x2

⇔ 4x1 = 4x2

⇔ x1 = x2.

Allora h è iniettiva. Controlliamo se è anche suriettiva. Sia y ∈ R e sisupponga che esiste x ∈ N tale che h(x) = y, allora

h(x) = y ⇔ 1 + x

x+ 5= y

⇔ 1 + x = y(x+ 5)

⇔ 1 + x = yx+ 5y

⇔ x− yx = 5y − 1

⇔ x(1− y) = 5y − 1

⇔ x =5y − 1

1− y.

7

Se y = 2 si ottiene x = −9 /∈ N. Quindi h non è suriettiva. Perciò non èbiiettiva e non possiamo determinare la sua inversa. Ora, vediamo che f èiniettiva. Infatti, siano z1, z2 ∈ R tali che f(z1) = f(z2), allora

f(z1) = f(z2)⇔1

4z31 + 7 =

1

4z32 + 7⇔ 1

4z31 =

1

4z32 ⇔ z31 = z32 ⇔ z1 = z2.

Ora, veri�chiamo la suriettività: sia y ∈ R e si supponga che esista z ∈ Rtale che f(z) = y, allora

f(z) = y ⇔ 1

4z3 + 7 = y ⇔ 1

4z3 = y − 7⇔ z3 = 4y − 28⇔ z = 3

»4y − 28.

Sicuramente z è un numero reale, perciò f è anche suriettiva e quindi biiet-tiva. Determiniamo la funzione inversa di f , cioè

f−1 : R→ R, f−1(y) = 3»4y − 28.

Determiniamo le composizioni h◦f e f ◦h. L'unica possibile è f ◦h, poiché èl'unico caso in cui il dominio della prima funzione coincide con il codominiodella seconda. Quindi si ha

f ◦ h : N→ R→ R, f(h(x)) = f

Ç1 + x

x+ 5

å=

1

4

Ç1 + x

x+ 5

å3

+ 7.

Capitolo 2

Esercizi sulle relazioni d'ordine e

di equivalenza

Ora proponiamo lo svolgimento di alcuni esercizi sulle relazioni. Percomprenderli meglio è necessario che si abbiano i seguenti prerequisiti:

1. conoscenza del concetto di relazione,

2. di relazione d'ordine,

3. di relazione di equivalenza.

Esercizio 2.1 Sia A = {a, b, c, d, e} e sia R ⊆ A× A la relazione su Ade�nita da

R = {(a, a), (b, b), (c, c), (d, d), (e, e), (b, d), (a, c), (d, b)}.

1. Dire se R è ri�essiva, simmetrica, antisimmetrica, transitiva su A.

2. Veri�care che R non è una relazione di equivalenza su A.

3. Veri�care che si può ottenere una relazione di equivalenza su A aggiun-gendo un unico elemento (cioè una coppia) ad R.

Svolgimento.

1. Innanzitutto stabiliamo se R è una relazione ri�essiva, cioè:

∀x ∈ A xRx.

Ricordiamo che la notazione xRx indica che la coppia (x, x) è un ele-mento di R. Quindi, osservato che A è costituito da a ,b ,c ,d ,e, cichiediamo se le coppie (a, a), (b, b), (c, c), (d, d), (e, e) appartengono

8

9

ad R. La risposta al nostro quesito è a�ermativa e pertanto possiamoa�ermare che R gode della proprietà ri�essiva. Ora, veri�care che R èuna relazione simmetrica vuol dire che

∀x, y ∈ A xRy ⇒ yRx,

cioè, considerati due qualunque elementi x, y di A, se la coppia (x, y)è un elemento di R allora lo è anche la coppia (y, x). Ovviamentele coppie formate da due elementi uguali (ovvero (a, a), (b, b), (c, c),(d, d), (e, e)) veri�cano banalmente questa proprietà, dato che equivalead uno scambio di due componenti uguali, pertanto la proveremo perle restanti coppie di R (cioè (b, d), (a, c), (d, b)). Stabiliamo, quindi, sesono veri�cate le seguenti implicazioni:

(b, d) ∈ R ⇒ (d, b) ∈ R

(d, b) ∈ R ⇒ (b, d) ∈ R

(a, c) ∈ R ⇒ (c, a) ∈ R.

Osservando l'insieme R, notiamo che le prime due a�ermazioni sonovere, invece l'ultima è falsa. Quindi R non è simmetrica. Stabiliamose R è antisimmetrica, cioè

∀x, y ∈ A xRy ∧ yRx⇒ x = y.

Questa proprietà è veri�cata sicuramente per le coppie formate da dueelementi uguali (ovvero (a, a), (b, b), (c, c), (d, d), (e, e)). D'altra parte,considerate le coppie (b, d) e (d, b), si ha che le seguenti implicazioni

bRd ∧ dRb⇒ b = d

edRb ∧ bRd⇒ d = b

non sono veri�cate. Infatti se fossero vere si avrebbe che b = d, ma ciònon è possibile poiché un insieme è costituito da elementi tutti distinti.Inoltre non abbiamo considerato la coppia (a, c) dato che la coppia(c, a) non è un elemento di R (per poter veri�care l'antisimmetria ènecessario che due coppie del tipo (x, y) e (y, x) appartengano ad R).In�ne decidiamo se R è transitiva, cioè

∀x, y, z ∈ A xRy ∧ yRz ⇒ xRz.

10

Così come per le altre proprietà, la transitività è veri�cata per le coppie(a, a), (b, b), (c, c), (d, d), (e, e). Pertanto restano solo da veri�care

aRa ∧ aRc⇒ aRc

aRc ∧ cRc⇒ aRc

bRb ∧ bRd⇒ bRd

dRd ∧ dRb⇒ dRb

bRd ∧ dRd⇒ bRd.

bRd ∧ dRb⇒ bRb.

dRb ∧ bRb⇒ dRb.

dRb ∧ bRd⇒ dRd.

E' su�ciente osservare gli elementi di R per poter dire che sono tuttevere.

2. Da quanto provato nel punto 1. si ha che R non è una relazioned'equivalenza dato che non è simmetrica.

3. Abbiamo osservato che R non è una relazione di equivalenza poichénon è simmetrica. Infatti quest'ultima proprietà non è veri�cata datoche la coppia (c, a) non appartiene ad R. Pertanto si può ottenereuna relazione di equivalenza su A aggiungendo solo la coppia (c, a)all'insieme R.

Esercizio 2.2 E' assegnata su Q la relazione

R = { (p, q) ∈ Q×Q | ∃h ∈ Z tale che p− q = h } .

1. Provare che R è di equivalenza.

2. Veri�care che (12,−5

3) /∈ R.

3. Individuare due elementi di Q in relazione tra loro.

4. Determinare la classe di equivalenza di 0.

Svolgimento.

11

1. Stabiliamo se R è ri�essiva. Sia p ∈ Q, allora

pRp⇔ ∃h ∈ Z tale che p− p = h⇔ ∃h ∈ Z tale che 0 = p− p = h.

Da cuipRp⇔ ∃h = 0 ∈ Z tale che p− p = 0.

Quindi è possibile trovare h = 0 che ci permette di a�ermare che p èin relazione R con sè stesso, cioè R è ri�essiva. Ora, stabiliamo se R èsimmetrica. Consideriamo p, q ∈ Q tali che pRq, cioè

∃h ∈ Z tale che p− q = h.

Veri�chiamo se qRp, cioè

∃k ∈ Z tale che q − p = k.

Per ipotesi, si ha∃h ∈ Z tale che p− q = h

che equivale a dire che

∃h ∈ Z tale che q − p = −h⇔ ∃k = −h ∈ Z tale che q − p = k.

Quindi R è anche simmetrica. Resta ancora da stabilire se R è transi-tiva. Siano p, q, r ∈ Q tali che

pRq ∧ qRr.

MapRq ⇔ ∃h ∈ Z tale che p− q = h

eqRr ⇔ ∃k ∈ Z tale che q − r = k

quindi

∃h, k ∈ Z tale che p− q = h ∧ q − r = k

⇒ ∃h, k ∈ Z tale che p− q + q − r = h+ k

⇒ ∃l = h+ k ∈ Z tale che p− r = l.

Pertanto pRr, cioè R è transitiva. Allora R è una relazione di equiva-lenza.

12

2. Osserviamo cheÅ12,−5

3

ã/∈ R. Infatti, se per assurdo fosse un elemento

di R, si avrebbeÅ12,−5

3

ã∈ R ⇔ ∃h ∈ Z tale che

1

2−Å−5

3

ã= h

⇔ ∃h ∈ Z tale che13

6= h.

Ma questa equivalenza non è vera poiché 136non è un numero intero.

3. Per determinare due elementi di Q in relazione tra loro (ovvero p, q ∈ Qtali che (p, q) ∈ R) è su�ciente considerare due razionali tali che, sot-traendo uno dall'altro, diano un numero intero. Ad esempio, possiamopensare di prendere la coppia (1, 2) ∈ Z× Z, cioè due numeri interi (equindi razionali), la cui di�erenza è -1 cioè un numero intero. Inoltre,se consideriamo la coppia (1

2, 32) ∈ Q×Q si ha che la loro di�erenza è

-1 che è un numero intero.

4. Ricordiamo che la classe di equivalenza di un elemento p, appartenentea Q, rispetto alla relazione R è de�nita come segue

[ p ]R = { q ∈ Q | pRq } = { q ∈ Q | ∃h ∈ Z tale che p− q = h } .

Allora

[ 0 ]R = { q ∈ Q | 0Rq }= { q ∈ Q | ∃h ∈ Z tale che − q = h }= { q ∈ Q | ∃h ∈ Z tale che q = −h }= { q ∈ Q | ∃k ∈ Z tale che q = k }= { q ∈ Z } = Z.

Quindi la classe di equivalenza di 0 coincide con l'insieme dei numeriinteri.

Esercizio 2.3 Assegnata su Z la relazione

R = { (a, b) ∈ Z× Z | 12 | 7b+ 5a } ,

(ovvero aRb⇔ 12 | 7b+ 5a).

1. Veri�care che R de�nisce una relazione di equivalenza su Z.

2. Scrivere la classe di equivalenza di 0.

13

Svolgimento.

1. Innanzitutto stabiliamo se R è ri�essiva. Sia a ∈ Z, si ha

aRa⇔ 12 | 7a+ 5a⇔ 12 | 12a.

Questa equivalenza è vera dato che 12a è un multiplo di 12 e quindisicuramente 12 | 12a. Vediamo, ora, seR è simmetrica ossia, consideratia, b ∈ Z deve risultare che

aRb⇒ bRa.

MaaRb⇔ 12 | 7b+ 5a.

D'altra parte, 12 | 12a+12b (12a+12b è un multiplo di 12 pertanto 12sarà un suo divisore). Ricordando che, in generale

∀x, y, z ∈ Z (z |x) ∧ (z | y)⇒ z | (x± y) (2.1)

si ha che

(12 | 12a+ 12b) ∧ (12 | 7b+ 5a)⇒ 12 | 12a+ 12b− 7b− 5a,

da cui12 | 7a+ 5b

cioè bRa. Quindi R è simmetrica. In�ne stabiliamo se R è transitiva.Siano a, b, c ∈ Z tali che

aRb ∧ bRc.Da ciò, si ha

(12 | 7b+ 5a) ∧ (12 | 7c+ 5b).

Quindi, per la proprietà (2.1), otteniamo che

(12 | 7b+ 5a+ 7c+ 5b)⇒ 12 | 12b+ 5a+ 7c.

A�nchè aRc (e quindi dire che R è transitiva) è necessario che, dal-la relazione precedente, si cancelli la quantità 12b. Ma sicuramente12 | 12b, pertanto applicando nuovamente la proprietà vista prima, siha

(12 | 12b+5a+7c)∧(12 | 12b)⇒ 12 | 12b+ 5a+ 7c− 12b⇒ 12 | 5a+ 7c.

Pertanto aRc, cioè R è transitiva e quindi R è una relazione di equi-valenza.

14

2. Determiniamo la classe di equivalenza di 0. Si ha

[ 0 ]R = { a ∈ Z | 0Ra } = { a ∈ Z | 12 | 7a }= { a ∈ Z | ∃h ∈ Z tale che 7a = 12h }= { a ∈ Z | a e′ un multiplo di 12 } .

Esercizio 2.4 Provare che la relazione | su N∗ tale che per ogni a, b ∈ N∗,

a|b⇔ ∃n ∈ N∗ tale che b = na

è una relazione d'ordine su N∗.

Svolgimento. Innanzitutto stabiliamo se la relazione | è ri�essiva. Siaa ∈ N∗, allora

a|a⇔ ∃n ∈ N∗ tale che a = na

⇔ ∃n = 1 ∈ N∗ tale che a = 1 · a.Quindi a|a dato che esiste n = 1 ∈ N∗ tale che a = 1 · a. Ciò signi�ca che larelazione | è ri�essiva. Ora, veri�chiamo la proprietà antisimmetrica. Sianoa, b ∈ N∗ tali che

(a|b) ∧ (b|a),e vediamo se a = b. Poiché


b|a⇔ ∃m ∈ N∗ tale che a = mb,

allorab = na = n(mb) = (nm)b,

ove abbiamo sostituito l'espressione di a in b. Ma l'ultima relazione è vera see solo se nm = 1 cioè n = m = 1 (questa è l'unica possibilità dato che n, me b sono numeri naturali). Pertanto, sostituendo il valore n = 1 in b = na (orispettivamente il valore m = 1 in a = mb) si ottiene b = a. In�ne stabiliamose tale relazione è anche transitiva. Siano a, b, c ∈ N∗ tali che

(a|b) ∧ (b|c),e vediamo se a|c. Poiché


b|c⇔ ∃m ∈ N∗ tale che c = mb,

allorac = mb = m(na) = (mn)a.

Quindi, ponendo r = mn ∈ N∗, si ha che c = ra cioè a|c. Pertanto larelazione | è transitiva e quindi è una relazione d'ordine.

Capitolo 3

Esercizi sul principio di induzione

Ora proponiamo lo svolgimento di alcuni esercizi sul principio di induzio-ne. Per comprenderli meglio è necessario che si conoscano gli enunciati deiteoremi ad esso relativi.

Esercizio 3.1 Mediante il principio di induzione si provi la seguenteproprietà:

P (n) :n+1∑i=0

(2i+ 1) = n2 + 4n+ 4, n ∈ N.

Svolgimento. Usiamo il principio di induzione per provare che P (n) èvera per ogni n ∈ N.

1. PASSO BASE: Veri�chiamo innanzitutto che

P (0) :0+1∑i=0

(2i+ 1) = 02 + 4 · 0 + 4

è vera. Si ha:

0+1∑i=0

(2i+ 1) =1∑

i=0

(2i+ 1) = (1) + (2 + 1) = 4,

d'altra parte02 + 4 · 0 + 4 = 4.

Quindi, data l'uguaglianza tra i due membri, P (0) è vera.

2. PASSO INDUTTIVO: Ora proviamo che per ogni n ∈ N, supponendovera P (n), è vera P (n+ 1), ovvero

∀n ∈ N P (n) vera⇒ P (n+ 1) vera.

15

16

Esplicitando la tesi si ha:

P (n+ 1) :(n+1)+1∑

i=0

(2i+ 1) = (n+ 1)2 + 4(n+ 1) + 4,

cioè

P (n+ 1) :n+2∑i=0

(2i+ 1) = (n+ 1)2 + 4(n+ 1) + 4. (3.1)

Tenendo presente l'ipotesi di induzione, si ha:

n+2∑i=0

(2i+ 1) =n+1∑i=0

(2i+ 1) + (2(n+ 2) + 1) = n2 + 4n+ 4 + 2n+ 4 + 1 =

= n2 + 6n+ 9.

D'altra parte:

(n+ 1)2 + 4(n+ 1) + 4 = n2 + 1 + 2n+ 4n+ 4 + 4 = n2 + 6n+ 9.

Data l'uguaglianza tra i due membri di (3.1), P (n+1) è vera. Pertantola proprietà è completamente veri�cata.

Esercizio 3.2 Veri�care per induzione completa che ∀n ∈ N, n ≥ 2 è vera

3n > 1 + 2n.



P (2) : 32 > 1 + 2 · 2,

è vera. Ma sicuramente 9 > 5, quindi P (2) è vera.



Esplicitando la tesi si ha:

P (n+ 1) : 3n+1 > 1 + 2(n+ 1) = 2n+ 3.

Tenendo presente l'ipotesi di induzione ed il fatto ovvio che 3n > 1(dato che n ≥ 2), si ha:

3n+1 = 3n · 3 = 3n + 3n + 3n > 1 + 2n+ 1 + 1 = 2n+ 3.

In conclusione, 3n+1 > 2n+ 3, cioè P (n+ 1) è vera.

17

Esercizio 3.3 Mediante il principio di induzione si provi la formula

3| 2n− 5n3, n ∈ N.



P (0) : 3| 2 · 0− 5 · 03

è vera. Deve risultare che 3| 0, ma ciò è sempre vero.



Si haP (n+ 1) : 3| 2(n+ 1)− 5(n+ 1)3,

ove, a conti fatti, 2(n+ 1)− 5(n+ 1)3 = (2n− 5n3)− 3− 15n3 − 15n.Allora, usando l'ipotesi di induzione e sapendo che −3− 15n3 − 15n èun multiplo di 3, cioè

3| − 3− 15n3 − 15n,

si ha

((3| 2n−5n3)∧ (3| −3−15n3−15n))⇒ 3| (2n−5n3)−3−15n3−15n.

Quindi P (n+ 1) è veri�cata.

Esercizio 3.4Veri�care che la seguente successione de�nita per ricorrenza

{bn}n =

b0 = 0, n = 0

bn = bn−1 + 6n, n ≥ 1

ammette come formula chiusa la successione {an}n con an = 3n(n + 1), perogni n ≥ 0.

Svolgimento. Usiamo il principio di induzione per provare che P (n) :an = bn è vera per ogni n ∈ N.

18


P (0) : a0 = b0,

è vera. Ma a0 = 3 · 0 · (0 + 1) = 0 e b0 = 0. Quindi, essendo entrambinulli, il passo base è veri�cato.


∀n ∈ N P (n) : an = bn ⇒ P (n+ 1) : an+1 = bn+1.

Quindi si ha:

bn+1 = bn+1−1 + 6(n+ 1) = bn + 6(n+ 1) = an + 6(n+ 1) =

= 3n(n+ 1) + 6(n+ 1)

= (3n+ 6)(n+ 1) = 3(n+ 2)(n+ 1).

Ma an+1 = 3(n+1)(n+1+1) = 3(n+1)(n+2). Pertanto, poiché an+1

coincide con bn+1, si ha che P (n+ 1) è veri�cata.

Capitolo 4

Esercizi sulle strutture algebriche:

gruppi, anelli e campi

Ora proponiamo lo svolgimento di alcuni esercizi riguardanti i gruppi, glianelli e i campi. Per comprenderli meglio è necessario che si conoscano leloro de�nizioni e le relative proprietà.

Esercizio 4.1 Si consideri la seguente struttura algebrica (Z, ∗), dove lalegge di composizione interna ∗ è de�nita come segue:

∀x, y ∈ Z, x ∗ y = x+ y + 1.

1. Stabilire se ∗ è una legge associativa e/o commutativa.

2. Determinare l'eventuale elemento neutro della struttura algebrica (Z, ∗).

3. Se la struttura algebrica (Z, ∗) ammette elemento neutro, determinaregli (eventuali) elementi di Z che hanno inverso rispetto ad ∗.

4. Concludere se la struttura algebrica (Z, ∗) è un monoide o un gruppo(abeliano).

Svolgimento.

1. Veri�chiamo innanzitutto se ∗ è associativa, cioè

∀x, y, z ∈ Z (x ∗ y) ∗ z = x ∗ (y ∗ z). (4.1)

Siano x, y, z ∈ Z, e calcoliamo separatamente i due membri della (4.1).Si ha:

(x ∗ y) ∗ z = (x+ y + 1) ∗ z = (x+ y + 1) + z + 1 = x+ y + z + 2,

19

20

x ∗ (y ∗ z) = x ∗ (y + z + 1) = x+ (y + z + 1) + 1 = x+ y + z + 2.

Quindi si ottiene l'uguaglianza richiesta. Ora, veri�chiamo se ∗ ècommutativa, cioè

∀x, y ∈ Z x ∗ y = y ∗ x.

Siano x, y ∈ Z, e calcoliamo

x ∗ y = x+ y + 1,

y ∗ x = y + x+ 1.

Ma, per la proprietà commutativa della somma tra numeri interi, si ha

x+ y + 1 = y + x+ 1,

cioè l'uguaglianza voluta.

2. Determiniamo l'elemento neutro dell'operazione ∗, veri�cando che

∃u ∈ Z t.c ∀x ∈ Z x ∗ u = x = u ∗ x.

Poiché abbiamo osservato che ∗ è commutativa, basta dimostrare cheè veri�cata solo la prima parte dell'uguaglianza della de�nizione, cioè

∃u ∈ Z t.c ∀x ∈ Z x ∗ u = x.

Sia x ∈ Z e determiniamo u dalla relazione seguente:

x ∗ u = x+ u+ 1 = x⇒ x+ u+ 1 = x⇒ u+ 1 = 0⇒ u = −1.

Quindi u = −1 è l'elemento neutro dell'operazione ∗.

3. Dato che abbiamo determinato l'elemento neutro, a�nchè ogni numerointero ammetta inverso rispetto a ∗ veri�chiamo se

∀x ∈ Z ∃x′ ∈ Z t.c. x ∗ x′ = x′ ∗ x = u.

Anche qui, come prima, è su�ciente provare solo la prima parte dell'u-guaglianza, poiché la seconda parte è garantita dalla commutatività di∗. Sia x ∈ Z. Si ha

x ∗ x′ = x+ x′ + 1 = u⇒ x+ x′ + 1 = u = −1⇒ x+ x′ + 1 = −1⇒ x′ = −2− x.

Quindi x ammette x′ = −2− x come inverso rispetto all'operazione ∗.

21

4. Concludiamo che la struttura algebrica (Z, ∗) è un gruppo abeliano datoche ∗ è associativa, ammette elemento neutro, ogni elemento ammetteinverso ed è commutativa.

Esercizio 4.2 Si consideri il gruppo (Z12,+).

1. Determinare tutti i generatori di (Z12,+);

2. Determinare l'ordine di [10]12, di [8]12 e [6]12 in (Z12,+);

3. Determinare il sottogruppo ciclico di (Z12,+) generato da [8]12;

4. Stabilire se H = {[0]12, [4]12, [8]12}, K = {[0]12, [3]12, [6]12, [9]12, [11]12}sono sottogruppi di (Z12,+) ed in caso a�ermativo determinare ungeneratore.

Svolgimento.

1. Determiniamo i generatori di (Z12,+), cioè le classi di congruenza [a]12tali che MCD(a, 12) = 1. A tal �ne, per determinarli più facilmente,esplicitiamo tutti gli elementi di Z12:

Z12 = {[0]12, [1]12, [2]12, [3]12, [4]12, [5]12, [6]12, [7]12, [8]12, [9]12, [10]12, [11]12}.

Quindi, dato che

MCD(1, 12) = 1, MCD(5, 12) = 1, MCD(7, 12) = 1, MCD(11, 12) = 1,

si ha che [1]12, [5]12, [7]12, [11]12 sono tutti e soli i generatori di (Z12,+).

2. Poiché abbiamo osservato che [1]12 è un generatore per il gruppo (Z12,+),possiamo determinare gli ordini degli elementi mediante la seguenteformula

o([a]12) = o([1]12 · [a]12) =|Z12|

MCD(a, 12),

ove |Z12| è la cardinalità di Z12, e [a]12 è un suo generico elemento, cona ∈ Z. Quindi

o([10]12) =|Z12|

MCD(10, 12)=

12

2= 6,

o([8]12) =|Z12|

MCD(8, 12)=

12

4= 3,

o([6]12) =|Z12|

MCD(6, 12)=

12

6= 2.

22

3. Osserviamo che, poiché o([8]12) = 3, il sottogruppo ciclico generato da[8]12 avrà 3 elementi. Pertanto

< [8]12 >= {h[8]12|h ∈ Z} = {[0]12, [8]12, [16]12 = [4]12}.

4. Per poter stabilire se H e K sono sottogruppi di (Z12,+), applichia-mo il Teorema di Lagrange. Quindi, poiché la cardinalità di K è 5, equella di H è 3, l'unico possibile sottogruppo di (Z12,+) è H ( 3 divide12 = |Z12| ). Resta solo da veri�care che H è e�ettivamente un sotto-gruppo di (Z12,+). Verichiamo se sono soddisfatte le tre proprietà checaratterizzano la de�nizione di sottogruppo di un gruppo. Innanzituttopossiamo a�ermare prontamente che H contiene l'elemento neutro di(Z12,+), cioè [0]12. Inoltre ogni elemento ha opposto che è ancora unelemento di H. In�ne H è chiuso rispetto alla somma, poichè comun-que considero due elementi di H, la loro somma è ancora un elementodi H. Pertanto H è un sottogruppo di (Z12,+). In realtà, dal punto3., si osserva che il sottogruppo generato da [8]12 è proprio H, pertantosi può subito concludere che H è un sottogruppo di (Z12,+).

Esercizio 4.3 Sia f : Z → Z3 l'applicazione tale che per ogni h ∈ Zf(h) = [h]3. Veri�care che f è un omomor�smo di gruppi e calcolare Ker(f).

Svolgimento. Proviamo che f è un omomor�smo del gruppo (Z,+) in(Z3,+), cioè

∀n,m ∈ Z f(n+m) = f(n) + f(m).

Siano n,m ∈ Z e calcoliamo

f(n+m) = [n+m]3 = [n]3 + [m]3 = f(n) + f(m),

ove nel secondo passaggio abbiamo utilizzato la de�nizione di somma traelementi di Z3. Pertanto f è un omomor�smo. Ora, determiniamo Ker(f),cioè

Ker(f) = {n ∈ Z| f(n) = [0]3} = {n ∈ Z| [n]3 = [0]3} = {n = 3k| k ∈ Z}.

Quindi il Ker(f) è formato dai multipli di 3.

Esercizio 4.4 Determinare gli elementi invertibili e i divisori dello zerodell'anello (Z18,+, ·). Per ogni elemento invertibile determinarne l'inverso.

23

Svolgimento. Prima di procedere nel calcolo degli elementi invertibili edei divisori dello zero di (Z18,+, ·), ricordiamo che se (A,+, ·) è un anellocommutativo unitario e se a ∈ A è un elemento invertibile, allora a non èdivisore dello zero. E il viceversa è vero solo negli anelli �niti. Pertanto, datoche (Z18,+, ·) è un anello commutativo unitario �nito, determineremo primagli elementi invertibili e i restanti saranno divisori dello zero. Un elemento[a]18 di (Z18,+, ·) è invertibile se il MCD(a, 18) = 1. Pertanto, si ha

MCD(a, 18) = 1⇔ a = 1, 5, 7, 11, 13, 17.

Quindi gli elementi invertibili di (Z18,+, ·) sono:

[1]18, [5]18, [7]18, [11]18, [13]18, [17]18.

Ora, ad esempio, determiniamo l'inverso di [5]18, cioè un elemento [a]18 diZ18 tale che

[5]18[a]18 = [1]18,

cioè5a ≡ 1 (mod 18).

La soluzione di questa congruenza è a = 11. Quindi [11]18 è l'inverso di [5]18.Analogamente si procede per tutti gli altri elementi invertibili. In�ne, comegià accennato, i divisori dello zero di (Z18,+, ·) sono tutti gli elementi chenon sono invertibili, cioè

[2]18, [3]18, [4]18, [6]18, [8]18, [9]18, [10]18, [12]18, [14]18, [15]18, [16]18.

Esercizio 4.5 Si consideri in S9 la seguente permutazione

f =

Ç1 2 3 4 5 6 7 8 99 2 4 3 8 6 1 5 7

å.

1. Scrivere f come prodotto di cicli disgiunti.

2. Stabilire se f è pari o dispari.

3. Calcolare f−1 e l'ordine di f in S9.

4. Calcolare l'ordine del sottogruppo H generato da f e scriverne esplici-tamente tutti gli elementi.

5. Calcolare l'ordine degli elementi del sottogruppo H.

Svolgimento.

24

1. Decomponiamo f in cicli disgiunti, cioè in modo che gli elementi checompaiono nei cicli sono distinti. A tal �ne, osserviamo che l'immaginetramite f di 1 è 9, quella di 9 è 7 e di 7 è 1. Quindi il primo ciclo, dilunghezza 3, è dato da (197). Procedendo analogamente per tutti glialtri elementi, si ottiene

f = (197)(2)(34)(58)(6) = (197)(34)(58).

2. Per stabilire se f è pari o dispari è necessario scrivere f nel prodottodi trasposizioni, cioè cicli di lunghezza 2. Pertanto, osservando che ilciclo (197) = (17)(19), si ha

f = (17)(19)(34)(58).

Quindi f è il prodotto di 4 cicli di lunghezza 2, cioè f è pari (poiché 4è un numero pari).

3. Calcoliamo f−1 invertendo la seconda riga di f con la prima, e rior-dinando le colonne in modo da sistemare in modo crescente i numeridella prima riga:

f−1 =

Ç9 2 4 3 8 6 1 5 71 2 3 4 5 6 7 8 9

å=

Ç1 2 3 4 5 6 7 8 97 2 4 3 8 6 9 5 1

å.

Ora, ricordiamo che in generale un ciclo di lunghezza k ha ordine k.Quindi l'ordine di f è il minimo comune multiplo delle lunghezze deicicli disgiunti:

|f | = m.c.m(3, 2, 2) = m.c.m(3, 2) = 6.

4. Osserviamo che, poiché f ha ordine 6, il sottogruppo H generato daf ha 6 elementi. Essi sono le potenze di f , compresa la permutazioneidentica. Quindi

H =< f >= {f 0, f 1, f 2, f 3, f 4, f 5}

Ovviamente f 0 è la permutazione identica, f 1 è f stessa. Calcoliamof 2. Componiamo f con se stessa due volte, cioè:

f 2 =

Ç1 2 3 4 5 6 7 8 99 2 4 3 8 6 1 5 7

åÇ1 2 3 4 5 6 7 8 99 2 4 3 8 6 1 5 7

å=

=

Ç1 2 3 4 5 6 7 8 97 2 3 4 5 6 9 8 1

å= (179),

25

Considerando la permutazione più a destra, si osserva che l'immagi-ne tramite f di 1 è 9. Quest'ultimo, mediante la prima permutazione(quella a sinistra, che è sempre f) ha immagine 7. Pertanto la permu-tazione f 2 trasformerà 1 in 7 (la prima �colonna� della permutazionef 2). Procedendo così anche per le altre potenze, si ha

H = {Id, f = (17)(19)(34)(58), f 2 = (179), f 3 = (34)(58),

f 4 = (197), f 5 = (179)(34)(58)}

5. Determiniamo gli ordini degli elementi di H osservando la loro decom-posizione in cicli disgiunti. Quindi si ha

o(Id) = 1

o(f) = 6

o(f 2) = 3

o(f 3) = m.c.m(2, 2) = 2

o(f 4) = 3

o(f 5) = m.c.m(3, 2) = 6.

Risoluzione esercizi di Matematica Discreta

Documents

Transcript of Risoluzione esercizi di Matematica Discreta