Libro Delizia Esercizi Soluzioni

Costantino DeliziaPatrizia LongobardiMercede MajChiara Nicotera

Matematica discreta

Soluzione degli esercizi proposti

1Teoria degli insiemi

Esercizio 1.1.1. Vedi svolgimento nel testo.

Esercizio 1.1.2. Si ha: P(Ø) = Ø, P(P(Ø)) = P(Ø) = Ø, Ø,P(P(P(Ø))) = P(Ø, Ø) = Ø, Ø, Ø, Ø, Ø.


Esercizio 1.1.4. Si ha C = 1,−1, D = Ø, E = i,−i, F = n, o.

Esercizio 1.1.5. Risulta:

c ∈ A, 1 /∈ A, 4 /∈ A, 12 ∈ A,12 ∈ A, Ø ∈ A, Ø /∈ A, 12 ⊆ A,

12 ⊆ A, c, 12 ⊆ A, Ø ⊆ A, Ø ⊆ A,Ø 6⊆ A, c /∈ B, 1 ∈ B, d, 5 ∈ B,d /∈ B, f ∈ B, Ø /∈ B, Ø ∈ B,1 ⊆ B, d 6⊆ B, c, 12 6⊆ B, Ø ⊆ B,Ø 6⊆ B, Ø ⊆ B, 1, d, 5 ⊆ B, f 6⊆ B,

1, 0 6⊆ B, f, Ø ⊆ B, f,Ø 6⊆ B, f, d ⊆ B.

Esercizio 1.1.6. Sono vere la seconda, la settima e l’ultima affermazione, le altresono false.


P(L) = Ø, 11, 7, LP(M) = Ø, s, 8, π, s, 8, s, π, 8, π,M.

Esercizio 1.1.8. Si ha:

N ∈ P(N0), Ø ∈ P(N0), Ø /∈ P(N0),

2 Capitolo 1

0 ∈ P(N0), N0 ∈ P(N0), 3 /∈ P(N0),3, 4 /∈ P(N0), 0 /∈ P(N0), 10, 100 ∈ P(N0),2,−3, 5 /∈ P(N0), Z /∈ P(N0), −3 /∈ P(N0).

Esercizio 1.1.9. E vera la seconda affermazione, le altre sono false.

Esercizio 1.1.10. Se S = T = V , allora per la (1.1.4) si ha S ⊆ T , T ⊆ V eV ⊆ S.

Viceversa, si ha S ⊆ T e da T ⊆ V ⊆ S segue T ⊆ S, per la proprietatransitiva dell’inclusione, sicche S = T , ancora per la (1.1.4). Si ha poi T ⊆ V eV ⊆ T per la proprieta transitiva dell’inclusione, sicche T = V .

Esercizio 1.1.11. Per ogni x ∈ S si ha x ∈ P(S) ⊆ P(T ), quindi x ∈ P(T ),cioe x ⊆ T e x ∈ T , come volevasi.

Esercizio 1.1.12. Sia S ⊂ T . Allora P(S) ⊆ P(T ) per la (1.1.9). Inoltre esisteT : T ∈ P(T ), T /∈ P(S), pertanto P(S) ⊂ P(T ).

Sia ora P(S) ⊂ P(T ). Allora S ⊆ T per la (1.1.9). Esiste inoltre Y : Y ∈P(T ), Y /∈ P(S), ne segue Y 6⊆ S, dunque esiste y : y ∈ Y, y /∈ S, inoltre y ∈ Tpoiche Y ⊆ T , pertanto y e tale che y ∈ T, y /∈ S, e S ⊂ T .

Esercizio 1.1.13. Risulta |P(T )| = 24 = 16 e gli elementi di P(T ) sono: Ø,Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø,Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø,Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, T .

Esercizio 1.2.1. Da a ≤ b, b < c segue b ≤ c e a ≤ c per la proprieta transitivadella relazione ≤ (vedi (1.2.25)). Per assurdo sia a = c, allora si ha c ≤ b e dab ≤ c segue b = c per la proprieta asimmetrica (vedi (1.2.24)), contro l’essereb < c.

Analogamente si prova la seconda relazione.Da a < b e b < c segue poi a ≤ c e b < c e dunque a < c per quanto provato

in precedenza.Si supponga ora a < b e c ≤ d,. esistono allora e sono univocamente determi-

nati t ∈ N, s ∈ N0 tali che b = a+ t, d = c+s, pertanto b+d = (a+ c)+(t+s),con s + t ∈ N0, sicche a + c ≤ b + d. Non puo essere s + t = 0, altrimentisi avrebbe s = 0, t = 0 per la (1.2.4) e t = 0 contro l’essere t ∈ N, pertantoa+ c < b+ d.

Sia ora a < b, c < d. Allora esistono e sono univocamente determinati t ∈N, s ∈ N tali che b = a+t, d = c+s. Risulta bd = (a+t)(c+s) = ac+as+ct+st,

Teoria degli insiemi 3

per le (1.2.15) e (1.2.16). Non puo essere as+ ct+ st = 0, altrimenti si avrebbest = 0 per la (1.2.4) e s = 0 o t = 0 per la legge di annullamento del prodotto(vedi (1.2.11)), entrambi assurdi.

Le altre relazioni si provano analogamente.

Esercizio 1.2.2. Esistono k, k1 ∈ N0 tali che b = ak, d = ck1, ne seguebd = akck1 = ackk1 per la proprieta commutativa (vedi (1.2.7)), con kk1 ∈ N0,pertanto ac|bd.

Da n ∈ N0 segue n|n per la proprieta riflessiva (vedi (1.2.39)). Se a|b en ∈ N0 si ha allora an|bn per la proprieta precedente, e, essendo a|an risulta a|bnper la proprieta transitiva (vedi (1.2.41).

Esercizio 1.2.3. Per definizione si ha b = (b − a) + a = (b − c) + c. Dab − a = b − c segue allora a = c, per la cancellabilita rispetto alla somma (vedi(1.2.6)). La seconda relazione si prova analogamente.

Esercizio 1.2.4. Con a, b, c ∈ Z sia a+ b = a+ c, allora si ha (−a) + (a+ b) =(−a) + (a+ c), sicche, per la proprieta associativa della somma (vedi (1.2.2)), siha (−a+ a) + b = (−a+ a) + c, da cui 0 + a = 0 + b e b = c.

Esercizio 1.2.5. Si ragioni come nell’Esercizio 1.2.3.


Esercizio 1.2.7. Sia a ≤ b, esiste allora t ∈ N0 tale che b = a+ t. Se c > 0, si habc = (a+ t)c = ac+ tc, con tc ∈ N0, sicche ac ≤ bc. Se c < 0, si ha 0 = c+ k,con k ∈ N, da cui −c = k ∈ N; da a = b− t segue allora ac = (b− t)c = bc− tcper la 1.2.7, dunque ac = bc+ t(−c), con t(−c) ∈ N0, come volevasi.

Se poi a < b si ha b = a + t, con t ∈ N univocamente individuato e bc =ac + tc. Se c > 0, si ha tc ∈ N0 e non puo essere tc = 0, altrimenti si avrebbe,per la legge di annullamento del prodotto (vedi (1.2.11)), t = 0 o c = 0, entrambiassurdi, pertanto ac < bc. Se invece c < 0, si ha ac = bc− tc = bc+ t(−c), cont(−c) ∈ N0 e ancora non puo essere t(−c) = 0, altrimenti si avrebbe, per la leggedi annullamento del prodotto (vedi (1.2.11)), t = 0 o −c = 0, entrambi assurdi.pertanto bc < ac.

Se 0 ≤ a, si ha (−1)a ≤ (−1)0 = 0 e, per la 1.2.6 −a ≤ 0; viceversa da−a ≤ 0 segue 0 = (−1)0 ≤ (−1)(−a) e, sempre per la 1.2.6, 0 ≤ a.

Le altre relazioni si provano analogamente.

Esercizio 1.2.8. Si ha 0 = a0, pertanto a|0. Risulta b = 0k, con k ∈ Z se e solose b = 0. Si ha poi a = a, pertanto 1|a e a|a. Le analoghe di (1.2.41), (1.2.42),(1.2.43) si provano in modo del tutto simile.

Per la 1.2.6, si ha (−1)(−a) = a, pertanto −1|a e (−a)|a. Se a|b, si hab = ak, con k ∈ Z, da cui b = (−a)(−k), con−k ∈ Z, dunque (−a)|b; viceversa

4 Capitolo 1

se (−a)|b, si ha che−(−a)|b e dunque a|b. Infine se a|b, si ha b = ak, con k ∈ Z,da cui −b = −ak = a(−k), per la 1.2.6, sicche a|(−b), viceversa se a|(−b) si haanche a| − (−b) e dunque a|b, come richiesto.

Si noti infine che, per ogni a ∈ Z \ 0, a|(−a), (−a)|a, con a 6= −a,pertanto non vale l’analoga di (1.2.40).

Esercizio 1.2.9. Se a ≥ 0, b ≥ 0, risulta ab ≥ 0 e a + b ≥ 0, sicche |ab| =ab = |a||b| e |a + b| = a + b = |a| + |b|. Se invece a < 0, b < 0, si haab ≥ 0, per la 1.2.9 e a + b < 0, pertanto |ab| = ab = (−a)(−b) = |a||b|e |a + b| = −(a + b) = −a + (−b) = |a| + |b|. Siano infine, per esempio,a ≥ 0, b < 0, allora si ha ab < 0, per la 1.2.9, e |ab| = −ab = a(−b) = |a||b|; siha poi a+b < a ≤ a+(−b) = |a|+|b| e (−a)+(−b) ≤ −b ≤ a+(−b) = |a|+|b|,pertanto, se a + b ≥ 0, risulta |a + b| = a + b < |a| + |b|, se invece a + b < 0,risulta |a+ b| = −(a+ b) = (−a) + (−b) ≤ |a|+ |b|.

Esercizio 1.2.10. Da x, y ∈ Np segue x = 2k, y = 2k1, con k, k1 ∈ N0, da cuix+y = 2(k+k1) ∈ Np e xy = (2k)(2k1) = 2(2kk1) ∈ Np. Se invece x, y ∈ Nd,si ha x = 2k + 1, y = 2k1 + 1, con k, k1 ∈ N0, dunque x + y = 2 + 2k1 + 2 =2(k+ k1 + 1) ∈ Np e xy = 2k2k1 + 2k+ 2k1 + 1 = 2(2kk1 + k+ k1) + 1 ∈ Nd.Infine se, per esempio, x ∈ Np, y ∈ Nd, si ha x = 2k, y = 2k1 + 1, k, k1 ∈ N0,da cui x+ y = 2k + 2k1 + 1 = 2(k + k1) + 1 ∈ Nd e xy = 2k(2k1 + 1) ∈ Np.

Esercizio 1.2.11. Si ha b = ak, d = ck1, con k, k1 ∈ Z, da cui bd = akck1 =ac(kk1), con kk1 ∈ Z, sicche ac|bd. E z|z per la proprieta riflessiva (vedi 1.2.10),pertanto da a|b segue az|bz per ogni z ∈ Z; da a|az, az|bz segue infine a|bz perla proprieta transitiva (vedi 1.2.10).

Esercizio 1.2.12. Da sN0 ⊆ tN0 segue s = s1 ∈ tN0, cioe s = tk per unopportuno k ∈ N0, sicche t|s. Viceversa, sia t|s. Per ogni y ∈ sN0 si ha y = sv,con v ∈ N0, dunque s|y, ne segue t|y per la transitivita (vedi 1.2.41) sicchey ∈ tN0. La seconda relazione si prova analogamente.

Con s, t ∈ N0, si ha sN0 = tN0 se e solo se sN0 ⊆ tN0 e tN0 ⊆ sN0, cioe see solo se s|t e t|s, e dunque, per la (1.2.40), se e solo se s = t.

Con h, k ∈ Z si ha invece hZ = kZ se e solo se h|k e k|h, cioe se e solo seh = k o h = −k, per la 1.2.11.

Esercizio 1.2.13. Da mn = a

b ,st = c

d segue mb = an, sd = ct. Si ha allora

(mt+ ns)bd = mtbd+ nsbd = mbtd+ sdnb = antd+ ctnb = adnt+ bcnt =(ad + bc)nt, dunque mt+ns

nt = ad+bcbd . Si ha poi msbd = mbsd = anct = acnt,

dunque msnt = ac

bd .

Esercizio 1.2.14. Per ogni mn ,st ∈ Q, si ha, per la commutativita della somma e

del prodotto in Z, mn + st = mt+ns

nt = sn+mttn = s

t+mn . Per ogni mn ,

st ,uv ∈ Q, si ha,


per l’associativita della somma e del prodotto in Z, (mn + st ) + u

v = mt+nsnt + u

v =(mt+ns)v+unt

ntv = mtv+nsv+untn(tv) = m

n + sv+tutv = m

n + ( st + uv ).

Analogamente si provano la proprieta commutativa e la proprieta associativadel prodotto in Q.

Si ha poi, per ogni mn ,

st ,uv ∈ Q, (mn + s

t )uv = (mt+nsnt )uv = mtu+nsu

ntv =(mtu+nsu)v

ntv2= mu

nv + sutv = m

nuv + s

tuv .

Analogamente si prova la proprieta distributiva a sinistra del prodotto rispettoalla somma.

Esercizio 1.2.15. Si ha, per ogni n, t ∈ Z, 0t = 0 = n0, sicche 0n = 0

t , per

definizione. Si ha poi, per ogni m, s ∈ Z,m, s 6= 0, ms = sm e mm = s

s . Risultapoi, per ogni mn ∈ Q, mn + 0 = m

n + 0n = mn+n0

n2 = mnn2 = m

n . Infine si ha, per

ogni mn ∈ Q, mn 1 = mnnn = mn

n2 = mn .

Esercizio 1.2.16. Per ogni mn ∈ Q, si ha mn + −m

n = mn−nmn2 = 0

n2 = 0. Per ognimn ∈ Q, mn 6= 0, risulta poi m,n 6= 0 e m

nnm = mn

nm = mnmn = 1.




Esercizio 1.3.4. L’asserto e ovvio se k = 1, discende subito da 1.2.4 se k = 2.Sia k > 2. Se p|a1 . . . ak = (a1 . . . ak−1)ak, allora, per 1.2.4, p|a1 . . . ak−1 op|ak. Se p|a1 . . . ak−1, per ipotesi induttiva, esiste i ∈ 1, · · · , k − 1 tale chep|ai. Pertanto esiste i ∈ 1, . . . , k tale che p divide ai.

Sia ora n ≥ 2 e sia n = p1p2 · · · ph = q1q2 · · · qk, con pi, qj primi. Sisupponga per esempio h ≤ k. Da n = p1(p2 · · · ph) segue che p1|n = q1q2 · · · qk,dunque esiste i ∈ 1, . . . , k tale che p1 divide qi. Si ha dunque p1 = qi, poiche qie primo e p1 6= 1. Si puo assumere i = 1, sicche p1 = q1 e da n = p1p2 · · · ph =p1q2 · · · qk, segue p2 · · · ph = q2 · · · qk, per la cancellabilita rispetto al prodotto(vedi (1.2.14)). Ragionando analogamente su p2 si ha che esiste i ∈ 2, . . . , ktale che p2 = qi e si puo assumere i = 2, cioe p2 = q2; da p2 · · · ph = p2 · · · qk,segue allora p3 · · · ph = q3 · · · qk. Cosı continuando, dopo h passi si ottiene allorapi = qi per ogni i ∈ 1, . . . , h. Non puo essere h < k, altrimenti si avrebbe1 = qh+1 · · · qk e qk = 1 per (1.2.12), contro l’essere qk un numero primo.

6 Capitolo 1

Esercizio 1.3.5. Per n = 1, si ha 12 = 1 = 1(1+1)(2+1)6 . Con h ≥ 1, supposto

per ipotesi induttiva 12 + 22 + · · · + h2 = h(h+1)(2h+1)6 , si ottiene facilmente

12 + 22 + · · ·+ h2 + (h+ 1)2 = h(h+1)(2h+1)6 + (h+ 1)2 = (h+ 1)[h(2h+1)

6 +

(h+ 1)] = (h+ 1)[2h2+h+6h+66 ] = (h+ 1)[2h2+7h+6

6 ] = (h+ 1)[ (h+2)(2h+3)6 ] =

(h+1)(h+2)(2(h+1)+1)6 .

Esercizio 1.3.6. Per n = 1, si ha 11·2 = 1

2 = 1 − 12 = 1 − 1

1+1 . Con h ≥1, supposto per ipotesi induttiva 1

1·2 + 12·3 + · · · + 1

h·(h+1) = 1 − 1h+1 , si ha

11·2 + 1

2·3 +· · ·+ 1h·(h+1) + 1

(h+1)·(h+2) = 1− 1h+1 + 1

(h+1)·(h+2) = 1− h+2−1(h+1)(h+2) =

1− h+1(h+1)(h+2) = 1− 1

h+2 .

Esercizio 1.3.7. Per n = 1, si ha 1 = 12. Con h ≥ 1, supposto per ipotesiinduttiva 1 + 3 + 5 + · · · + (2h − 1) = h2, si ha 1 + 3 + 5 + · · · + (2h − 1) +(2(h+ 1)− 1) = h2 + (2(h+ 1)− 1) = h2 + 2h+ 1 = (h+ 1)2.

Esercizio 1.3.8. Per n = 1, si ha 2·1 = 2 = 1·2 = 1(1+1). Con h ≥ 1, suppostoper ipotesi induttiva 2+4+6+· · ·+2h = h(h+1), si ha 2+4+6+· · ·+2(h+1) =h(h+ 1) + 2(h+ 1) = (h+ 1)(h+ 2) = (h+ 1)((h+ 1) + 1).

Esercizio 1.3.9. Per n = 1, si ha 1 · 21 = 2 = 0 + 2 = (1 − 1) · 22 + 2 =(1−1) ·21+1 + 2. Con h ≥ 1, supposto per ipotesi induttiva 1 ·21 + 2 ·22 + · · ·+h · 2h = (h− 1) · 2h+1 + 2, si ha 1 · 21 + 2 · 22 + · · ·+ h · 2h + (h+ 1) · 2h+1 =(h− 1) · 2h+1 + 2 + (h+ 1)2h+1 = 2h+1(h− 1 + h+ 1) + 2 = 2h+1(2h) + 2 =2h+2h+ 2 = ((h+ 1)− 1) · 2(h+1)+1 + 2.

Esercizio 1.3.10. Per n = 1, si ha 2 = 2 · 1 = 2(21 − 1). Con h > 1, suppostoper ipotesi induttiva 2 + 22 + · · ·+ 2h−1 = 2(2h−1−1), si ha 2 + 22 + · · ·+ 2h =2+22+· · ·+2h−1+2h = 2(2h−1−1)+2h = 2h−2+2h = 2(2h)−2 = 2(2h−1).

Esercizio 1.3.11. Per n = 1, si ha 3 = 3(31−1)2 . Con h > 1, supposto per ipotesi

induttiva 3+32 + · · ·+3h−1 = 3(3h−1−1)2 , si ha 3+32 + · · ·+3h = 3+32 + · · ·+

3h−1 + 3h = 3(3h−1−1)2 + 3h = 3h−3

2 + 3h = 3h−3+2·3h

2 = 3·3h−32 = 3(3h−1)

2 .

Esercizio 1.3.12. Per n = 1, si ha −12 = −1 = (−1)1 1(1+1)2 . Con h ≥ 1,

supposto per ipotesi induttiva −12 + 22 − 32 + · · · + (−1)hh2 = (−1)h h(h+1)2 ,

si ha −12 + 22 − 32 + · · · + (−1)hh2 + (−1)h+1(h + 1)2 = (−1)h h(h+1)2 +

(−1)h+1(h+ 1)2 = (−1)h(h+ 1)[h2 + (−1)(h+ 1)] = (−1)h(h+ 1)[h−2h−22 ] =


(−1)h(h+ 1)(−h−22 ) = (−1)h(−1)(h+ 1)h+2

2 = (−1)h+1 (h+1)(h+2)2 .

Esercizio 1.3.13. Per n = 0, si ha 120 − 1 = 1 − 1 = 0 e 11|0. Con h ≥ 0,supposto per ipotesi induttiva 11|12h − 1, si ha 12h − 1 = 11t per un opportunot ∈ Z, da cui 12h+1−1 = 12h ·12−1 = 12h ·(11+1)−1 = 12h ·11+12h−1 =12h · 11 + 11t = 11(12h + t) e 11|12h+1.

Esercizio 1.3.14. Per n = 1, si ha 23·1 − 1 = 23 − 1 = 8− 1 = 7 e, ovviamente,7|7. Con h ≥ 1, supposto per ipotesi induttiva 7|23h − 1, si ha 23h − 1 = 7tper un opportuno t ∈ Z, da cui 23(h+1) − 1 = 23h · 23 − 1 = 23h · 8 − 1 =23h · (7 + 1)− 1 = 23h · 7 + 23h − 1 = 23h · 7 + 7t = 7(23h + t) e 7|23(h+1).

Esercizio 1.3.15. Per n = 1, si ha 53·1 − 1 = 53 − 1 = 125 − 1 = 124 e,ovviamente, 124|124. Con h ≥ 1, supposto per ipotesi induttiva 124|53h − 1, siha 53h−1 = 124t per un opportuno t ∈ Z, da cui 53(h+1)−1 = 53h ·53−1 = 53h ·125−1 = 53h·(124+1)−1 = 53h·124+53h−1 = 53h·124+124t = 124(53h+t)e 124|53(h+1).

Esercizio 1.3.16. Per n = 1, si ha 12 − 3 = −2 6= 1. Per ogni n ≥ 1 si ha1+3+5+ · · ·+(2n−1) = n2 (vedi Esercizio 1.3.7) e, ovviamente n2 6= n2−3.

Esercizio 1.4.1. Per ogni x ∈ S ∪ V risulta x ∈ S o x ∈ V , da cui x ∈ T ox ∈W per le ipotesi, dunque x ∈ T ∪W ; pertanto S ∪ V ⊆ T ∪W .

Risulta sempre V ⊆ V (vedi (1.1.2)), pertanto da S ⊆ T segue S ∪ V ⊆T ∪ V .

Da S ⊆ T, V ⊆ T segue S ∪ V ⊆ T ∪ T = T per la proprieta iterativadell’unione (vedi 1.4.5).

Esercizio 1.4.2. L’implicazione non vale, infatti per esempio , con A = a, B =b, c, C = a, b si ha A ∪ C = a, b ⊆ a, b, c = B ∪ C, ma A 6⊆ B.

Esercizio 1.4.3. Per ogni x ∈ S ∩ V risulta x ∈ S e x ∈ V , da cui x ∈ T ex ∈W per le ipotesi, dunque x ∈ T ∩W ; pertanto S ∩ V ⊆ T ∩W .

Risulta sempre V ⊆ V (vedi (1.1.2)), pertanto da S ⊆ T segue S ∩ V ⊆T ∪ V .

Da S ⊆ T, V ⊆ T segue S ∩ V ⊆ T ∩ T = T per la proprieta iterativadell’intersezione (vedi 1.4.9).

8 Capitolo 1

Esercizio 1.4.4. L’implicazione non vale, infatti per esempio , con A = a, b,B = a, c, C = a, d si ha A ∩ C = a = B ∩ C, ma A 6⊆ B.

Esercizio 1.4.5. La prima implicazione non vale: infatti, per esempio, con A =a, b, B = a, c, C = a, b, 3, D = a, c, d, E = a, b, 8 si ha A ⊂ C,B ⊂ D, ma A ∩B = a = C ∩D.

Si ha poi A∩B = a = C ∩B, pertanto non vale la seconda implicazione.Si ha infine A ⊂ C,A ⊂ E, ma A = a, b = C ∩ E.

Esercizio 1.4.6. Da S ∩ T ⊆ S (vedi (1.4.6)), segue S = (S ∩ T ) ∪ S per1.4.1, sicche per la proprieta commutativa dell’unione (vedi 1.4.2) S ∪ (S ∩T ) =(S ∩ T ) ∪ S = S.

Da S ⊆ S ∪ T (vedi (1.4.1) segue S ∩ (S ∪ T ) = S per 1.4.4.

Esercizio 1.4.7. Per ogni x ∈⋃X∈F X , esiste Y ∈ F tale che x ∈ Y , allora

x ∈ T per le ipotesi; pertanto⋃X∈F X ⊆ T .

Per ogni x ∈ T risulta x ∈ Y per ogni Y ∈ F per ipotesi, pertanto x ∈⋂X∈F X .


x ∈ S ∪ (⋂X∈F

X) ⇐⇒ x ∈ S o (x ∈⋂X∈F

X)

⇐⇒ x ∈ S o (x ∈ X,∀X ∈ F)⇐⇒ (x ∈ S o x ∈ X), ∀X ∈ F⇐⇒ (x ∈ S ∪X), ∀X ∈ F⇐⇒ x ∈

⋂X∈F

(S ∪X).

Si ha poi:

x ∈ S ∩ (⋃X∈F

X) ⇐⇒ x ∈ S e (x ∈⋃X∈F

X)

⇐⇒ x ∈ S e (∃ Y ∈ F : x ∈ Y )⇐⇒ ∃ Y ∈ F : x ∈ Y e x ∈ S⇐⇒ ∃ Y ∈ F : x ∈ Y ∩ S⇐⇒ x ∈

⋃X∈F

(S ∩X).



G ∪H = a, b, c, 2,m, n, d, 3, 0, G ∪K = a, b, c, 2,m, n, d, 3, 0,H ∪K = b, d, 3,m, 0, G ∩H = b,m,G ∩K = Ø, H ∩K = d, 3, 0 = K,

G \H = a, c, 2, n, H \G = d, 3, 0,G \K = a, b, c, 2,m, n, K \G = d, 3, 0,H \K = b,m, K \H = Ø.

Si ha dunque:

|G ∪H| = 9, |G ∪K| = 9, |H ∪K| = 5,|G ∩H| = 2, |G ∩K| = 0, |H ∩K| = 3,|G \H| = 4, |H \G| = 3, |G \K| = 6,|K \G| = 3, |H \K| = 2, |K \H| = 0.

Esercizio 1.4.10. Per ogni x ∈ S \W risulta x ∈ S e x /∈ W , da cui x ∈ V ex /∈ T per le ipotesi, dunque x ∈ V \ T ; pertanto S \W ⊆ V \ T . Ovviamente

S ⊆ V, T ⊆W ⇐⇒ T ⊆W, S ⊆ V =⇒ T \ V ⊆W \ S.

Da T ⊆ T (vedi (1.1.2)) seguono poi le altre implicazioni.

Esercizio 1.4.11. Con A = a, b, B = a, c, C = a, b, c, D = a, c, d, siha A ⊂ C,B ⊂ D e A \D = b = C \B.

Si ha poi A ⊂ C, A \ B = b = C \ B, sicche A \ B 6⊂ C \ B; B ⊂ D,A \B = b = A \D sicche A \B 6⊃ A \D.

Esercizio 1.4.12. Posto A = a, b, c, B = a, b, C = a, c, si ha:

B ∪ C = a, b, c,B ∩ C = a,A \B = c,A \ C = b,

A \ (B ∪ C) = Ø 6= b, c = (A \B) ∪ (A \ C),A \ (B ∩ C) = b, c 6= Ø = (A \B) ∩ (A \ C).


x ∈ S \ (S \ T ) ⇐⇒ x ∈ S e x /∈ S \ T⇐⇒ x ∈ S e (x /∈ S o x ∈ T )

10 Capitolo 1

⇐⇒ (x ∈ S e x ∈ T )⇐⇒ x ∈ S ∩ T.

Se S, T sono insiemi non disgiunti si ha allora S \ (S \ T ) = S ∩ T 6= Ø e(S \ S) \ T = Ø \ T = Ø, pertanto S \ (S \ T ) 6= (S \ S) \ T.



x ∈ S ∩ (T \ V ) ⇐⇒ x ∈ S e x ∈ T \ V⇐⇒ x ∈ S e (x ∈ T e x /∈ V )⇐⇒ x ∈ S e x ∈ T e x /∈ V⇐⇒ x ∈ S ∩ T e x /∈ S ∩ V⇐⇒ x ∈ (S ∩ T ) \ (S ∩ V ).

Inoltre:

x ∈ (S \ T ) ∩ V ⇐⇒ x ∈ S \ T e x ∈ V⇐⇒ (x ∈ S e x /∈ T ) e x ∈ V⇐⇒ x ∈ S e x /∈ T e x ∈ V⇐⇒ x ∈ S ∩ V e x /∈ T ∩ V⇐⇒ x ∈ (S ∩ V ) \ (T ∩ V ).


N ∪ 3,−4, a = N ∪ −4, a,N ∩ 3,−4, a = 3,N \ 3,−4, a = N \ 3,Z ∪ 3,−4, a = Z ∪ a,Z ∩ 3,−4, a = 3,−4,Z \ 3,−4, a = Z \ 3,−4,3,−4, a \ N = −4, a,3,−4, a \ N0 = −4, a,3,−4, a \ Z = a,N ∪ 3,−4, a = (N \ 3) ∪ −4, a,

N0 ∪ 3,−4, a = (N0 \ 3) ∪ −4, a,Z ∪ 3,−4, a = (Z \ 3,−4) ∪ a.



6N ∪ 9Z = 6x, 9y : x ∈ N, y ∈ Z,6N ∩ 9Z = 18N,6N \ 9Z = 3x : x ∈ 2N \ 3N,9Z \ 6N = 9x : x ∈ Z \ 2N,9Z ∪ 6N = 9x : x ∈ Z \ 2N ∪ 3x : x ∈ 2N \ 3N,

9Z ∪ 6N0 = 9x : x ∈ Z \ 2N0 ∪ 3x : x ∈ 2N \ 3N.

Esercizio 1.4.18. Le rappresentazioni richieste sono le seguenti:

L M

L \ (L \M)

L M

L ∪ M

L M

L \ (M \ L)

L M

N

(M ∪ N) \ (L ∩N)

L M

N

(L ∩N) \ (N \M)

L M

N

(L \M) ∪ (M \N)

L M

N

(M ∪ N) \ L

L M

N

(L ∩N) ∪ (M \ L)

L M

N

(L \M) ∩N

L M

N

L \ (M ∪ N)

L M

N

(L ∪N) ∩ (M \ L)

L M

N

(L \M) ∪N

Esercizio 1.4.19. Sono vere le affermazioni seguenti:

x /∈ S ∩ T ⇐⇒ x /∈ S o x /∈ T ;

12 Capitolo 1

x /∈ S ∪ T ⇐⇒ x /∈ S e x /∈ T ;x /∈ S \ T ⇐⇒ x /∈ S o x ∈ T.

Le altre sono false.

Esercizio 1.4.20. Siano A = 1, 2, 6, B = 3, 4, 6, C = 3, 5, 6. Si haB \ C = 4 e A ∪B = 1, 2, 3, 4, 6, A ∪ (B \ C) = 1, 2, 6, 4.

Esercizio 1.4.21. Siano A = 1, 2, 6, B = 3, 4, 6, C = 3, 5, 6. Si haB \ C = 4 e A ∩B = 6, A ∩ (B \ C) = Ø.

Esercizio 1.4.22. Siano A = 1, 2, 3, B = 1, 2, C = 1, 3. Si ha A \ B =3 e A \ (B ∩ C) = 2, 3.

Esercizio 1.4.23. Sia S \ (T \ V ) = S. Allora:

x ∈ S ∩ T =⇒ (x ∈ S) e (x ∈ T )=⇒ (x ∈ S \ (T \ V )) e (x ∈ T )=⇒ ((x ∈ S) e (x /∈ T o x ∈ V )) e (x ∈ T )=⇒ x ∈ V.

Viceversa sia S ∩ T ⊆ V . Allora ovviamente S \ (T \ V ) ⊆ S; inoltre si ha :

x ∈ S =⇒ (x ∈ S e x ∈ T ) o (x ∈ S e x /∈ T )=⇒ (x ∈ S ∩ T ) o (x ∈ S e x /∈ T )=⇒ (x ∈ S e x ∈ V ) o (x ∈ S e x /∈ T )=⇒ (x ∈ S) e (x ∈ V o x /∈ T )=⇒ (x ∈ S) e (x /∈ T \ V )=⇒ x ∈ S \ (T \ V ),

sicche S ⊆ S \ (T \ V ); pertanto S = S \ (T \ V ).Per provare la seconda equivalenza si puo, per esempio, utilizzare l’Esercizio

1.4.13. Si ha: S\T = S\V ⇐⇒ S\(S\T ) = S\(S\V ) ⇐⇒ S∩T = S∩V .


−3 ∈ Z \ N, 3 /∈ Z \ N, −3 /∈ 2Z \ N, 3 /∈ 2Z \ N, 0 ∈ Z \ N,5 /∈ 2Z ∪ N, −5 /∈ 2Z ∪ N, 0 ∈ 2Z ∪ N, −4 ∈ 2Z ∪ N, 4 ∈ 2Z ∪ N,0 /∈ 2Z ∩ N, −4 /∈ 2Z ∩ N, 4 ∈ 2Z ∩ N, −5 /∈ 2Z ∩ N, 5 /∈ 2Z ∩ N.


V ∪ (Ø \ V ) = V, V ∩ (Ø \ V ) = Ø, V ∪ (V \ V ) = V,


V ∩ (V \ V ) = Ø, V \ (Ø ∪ V ) = Ø, V \ (Ø ∩ V ) = V,

V ∩ (V \ Ø) = V, V \ (V \ Ø) = Ø, V \ (Ø \ V ) = V,

V ∪ (V ∩ Ø) = V, V \ (V \ V ) = V, V ∪ (V \ Ø) = V.


A ∪ (B \ C) = A ∪ i = a, 4, c, 13,√

5, i,

(A ∪B) \ (A ∪ C) = a, 4, c, 13,√

5, b, 7, i \ a, 4, c, 13,√

5, b, 7,√

15 = i.

Pertanto non sussiste l’uguaglianza S ∪ (T \V ) = (S ∪T ) \ (S ∪V ). Si ha pero:

x ∈ (S ∪ T ) \ (S ∪ V ) =⇒ x ∈ S ∪ T e x /∈ S ∪ V=⇒ (x ∈ S o x ∈ T ) e (x /∈ S e x /∈ V )=⇒ x ∈ T e x /∈ V=⇒ x ∈ T \ V=⇒ x ∈ S ∪ (T \ V ),

pertanto (S ∪ T ) \ (S ∪ V ) ⊆ S ∪ (T \ V ).


x ∈ (S \ T ) ∩ V ⇐⇒ x ∈ S \ T e x ∈ V⇐⇒ (x ∈ S e x /∈ T ) e x ∈ V⇐⇒ x ∈ S e x /∈ T e x ∈ V⇐⇒ x ∈ S ∩ V e x /∈ T⇐⇒ x ∈ (S ∩ V ) \ T.


x ∈ (S ∪ T ) \ (T ∩ V ) ⇐⇒ x ∈ (S ∪ T ) e x /∈ (T ∩ V )⇐⇒ (x ∈ S o x ∈ T ) e (x /∈ T o x /∈ V )⇐⇒ (x ∈ S e x /∈ T ) o (x ∈ S e x /∈ V )

o (x ∈ T e x /∈ V )⇐⇒ (x ∈ S e x /∈ T ) o (x ∈ S e x ∈ T e x /∈ V )

o (x ∈ S e x /∈ T e x /∈ V ) o (x ∈ T e x /∈ V )⇐⇒ (x ∈ S e x /∈ T ) o (x ∈ T e x /∈ V )⇐⇒ x ∈ (S \ T ) ∪ (T \ V ).

14 Capitolo 1

Esercizio 1.4.29. Si ha (L ∪M) \ N = (L \ N) ∪ (L \ N), per la proprietadistributiva a destra del complemento rispetto all’unione (vedi (1.4.17)), sicche(L∪M)\N ⊆ L∪(M \N)). L’inclusione puo essere stretta, infatti se L∩N 6= Øun elemento di L∩N appartiene a L∪ (M \N)) e non appartiene a (L∪M)\N .Si ha poi:

x ∈ L ∪ (M \N) ⇐⇒ x ∈ L o x ∈M \N⇐⇒ (x ∈ L) o (x ∈M e x /∈ N)⇐⇒ (x ∈ L o x ∈M) e (x ∈ L o x /∈ N)⇐⇒ (x ∈ L o x ∈M) e (x /∈ N o x ∈ L)⇐⇒ (x ∈ L ∪M) e (x /∈ N \ L)⇐⇒ x ∈ (L ∪M) \ (N \ L).

Esercizio 1.4.30. Con A = a, b, B = a, c, C = b, c si ha A ∩ B = a,B ∩ C = c, A ∩ C = b e A ∩B ∩ C = Ø.

Esercizio 1.4.31. Per le formule di De Morgan (vedi 1.4.13) si ha:

L \ (L ∩M ∩N) = (L \ L) ∪ (L \ (M ∩N))= Ø ∪ (L \ (M ∩N))= L \ (M ∩N).

Esercizio 1.4.32. Si assuma L \ (N \ (L ∩M)) = L. Si ha:

x ∈ L ∩N =⇒ x ∈ L e x ∈ N=⇒ x ∈ L \ (N \ (L ∩M)) e x ∈ N=⇒ x ∈ L e (x /∈ N o x ∈ L ∩M) e x ∈ N=⇒ x ∈M.

Pertanto L ∩N ⊆M .Viceversa si assuma L ∩N ⊆ M . Ovviamente L \ (N \ (L ∩M)) ⊆ L. Si

ha poi:

x ∈ L =⇒ (x ∈ L e x /∈ N) o (x ∈ L e x ∈ N)=⇒ (x ∈ L e x /∈ N) o (x ∈ L ∩N)=⇒ (x ∈ L e x /∈ N) o (x ∈ L e x ∈M)=⇒ (x ∈ L e x /∈ N) o (x ∈ L ∩M)=⇒ (x ∈ L) e ((x /∈ N) o (x ∈ L ∩M))=⇒ (x ∈ L) e (x /∈ N \ (L ∩M))=⇒ x ∈ L \ (N \ (L ∩M)).


Pertanto L \ (N \ (L ∩M)) = L.

Esercizio 1.4.33. Si assuma (L \ M) ∪ (L ∩ N) = L. Esista per assurdo unelemento x ∈ (L ∩M) \ N . Allora x ∈ L ∩M e x /∈ N , da x ∈ L segue perl’ipotesi x ∈ L \M o x ∈ L ∩ N , ma x ∈ M , pertanto x /∈ L \M e x /∈ N ,pertanto x /∈ L ∩N , un assurdo. Viceversa sia (L ∩M) \N = Ø. Ovviamente(L \M) ∪ (L ∩ N) ⊆ L; sia x ∈ L, allora si ha (x ∈ L e x /∈ M) o (x ∈ Le x ∈ M), nel secondo caso non puo’ essere x ∈ (L ∩M) \ N perche questoinsieme e vuoto, dunque x ∈ L∩N , dunque vale anche L ⊆ (L \M)∪ (L∩N),sicche L = (L \M) ∪ (L ∩N).

Esercizio 1.4.34. Ovviamente (S \ T ) ∪ (S ∩ T ) ⊆ S; se x ∈ S si ha poi(x ∈ S e x /∈ T ) oppure (x ∈ S e x ∈ T ), sicche x ∈ (S \ T ) ∪ (S ∩ T ), eS ⊆ (S \ T ) ∪ (S ∩ T ). Pertanto S = (S \ T ) ∪ (S ∩ T ). Esista per assurdox ∈ (S \ T ) ∩ (S ∩ T ), allora x /∈ T e x ∈ T , assurdo.

Esercizio 1.4.35. Si ha S = (S \ T ) ∪ (S ∩ T ) e S = (T \ S) ∪ (T ∩ S), perl’esercizio precedente, pertanto S ∪T = (S \T )∪ (S ∩T )∪ (T \S)∪ (T ∩S) =(S \ T ) ∪ (S ∩ T ) ∪ (S ∩ T ) ∪ (T \ S) = (S \ T ) ∪ (T \ S) ∪ (S ∩ T ),per la proprieta commutativa dell’intersezione e per le proprieta commutativa eassociativa dell’unione. Gli insiemi S \ T , T \ S sono ovviamente disgiunti, gliinsiemi S \ T e S ∩ T sono disgiunti per il precedente esercizio e cosı gli insiemiT \ S e S ∩ T .


S ∪T = (S ∪ T ) \ (S ∩ T )= ((S ∪ T ) \ S) ∪ ((S ∪ T ) \ T )= (S \ S) ∪ (S \ T ) ∪ (T \ S) ∪ (T \ T )= Ø ∪ (S \ T ) ∪ (T \ S) ∪ Ø= (S \ T ) ∪ (T \ S).

Esercizio 1.4.37. Se S e un qualunque insieme non vuoto risulta sempre S ⊆S ∪ (T ∪V ), ma ovviamente S 6⊆ (S ∪ T ∪ V ) \ (S ∪ T ∩ V ) = ((S ∪ T ∪ V ) \((S ∪ T ) ∩ (S ∪ V ))) = (S ∪ T ) ∪(S ∪ V ). Si ha:

x ∈ (S ∪ T ) ∪(S ∪ V ) =⇒ (x ∈ (S ∪ T ) ∪ (S ∪ V )) e(x /∈(S ∪ T ) ∩ (S ∪ V ))

=⇒ (x ∈ S o x ∈ T o x ∈ V ) e (x /∈ S ∪ (T ∩ V ))=⇒ (x ∈ S o x ∈ To x ∈ V ) e

((x /∈ S) e (x /∈ T ∩ V ))=⇒ (x ∈ T o x ∈ V ) e (x /∈ T ∩ V )

16 Capitolo 1

=⇒ x ∈ T ∪V.


x ∈ (⋃X∈F

X) \ S ⇐⇒ x ∈⋃X∈F

X e x /∈ S

⇐⇒ ∃ Y ∈ F : x ∈ Y e x /∈ S⇐⇒ ∃ Y ∈ F : x ∈ Y \ S⇐⇒ x ∈

⋃X∈F

(X ∪ S).

Si ha poi:

x ∈ (⋂X∈F

X) \ S ⇐⇒ x ∈⋂X∈F

X e x /∈ S

⇐⇒ x ∈ X,∀X ∈ F e x /∈ S⇐⇒ x ∈ X \ S,∀X ∈ F⇐⇒ x ∈

⋂X∈F

(X ∪ S).


x ∈ S \ (⋃X∈F

X) ⇐⇒ x ∈ S e x /∈⋃X∈F

X

⇐⇒ x ∈ S e x /∈ X,∀X ∈ F⇐⇒ x ∈ S \X,∀X ∈ F⇐⇒ x ∈

⋂X∈F

(S \X).

Si ha poi:

x ∈ S \ (⋂X∈F

X) ⇐⇒ x ∈ S e x /∈⋂X∈F

X

⇐⇒ x ∈ S e ∃ Y ∈ F : x /∈ Y⇐⇒ ∃ Y ∈ F : x ∈ S \ Y⇐⇒ x ∈

⋃X∈F

(S ∪X).


Esercizio 1.5.1. Se S = Ø, si ha S×T = Ø×T = Ø ⊆ V ×W qualunque sianoT, V,W e dunque anche se T 6⊆W.

Se T = Ø, si ha S × T = S × Ø = Ø ⊆ V ×W qualunque siano S, V,W edunque anche se S 6⊆ V.

Esercizio 1.5.2. Se S = T , ovviamente S × T = T × S, se S = Ø o T =Ø, S × T = Ø = T × S.

Sia ora S × T = T × S e si supponga S 6= Ø, T 6= Ø, da S × T ⊆ T × Ssegue allora, per la (1.5.4), S ⊆ T e T ⊆ S, sicche S = T .

Esercizio 1.5.3. Si ha :

V ×W = (9,m), (9,♦), (9, 9), (9, α), (∞,m), (∞,♦), (∞, 9), (∞, α),V × V = (9, 9), (9,∞), (∞, 9), (∞,∞),W × V = (m, 9), (m,∞), (♦, 9), (♦,∞), (9, 9), (9,∞), (α, 9), (α,∞),W ×W = (m,m), (m,♦), (m, 9), (m,α), (♦,m), (♦,♦), (♦, 9), (♦, α),

(9,m), (9,♦), (9, 9), (9, α), (α,m), (α,♦), (α, 9), (α, α),4V = (9, 9), (∞,∞),4W = (m,m), (♦,♦), (9, 9), (α, α).


(−1, 3) ∈ Z× N; (−1, 3) /∈ N× Z; (−1, 3) ∈ Z× Z; (−1, 3) /∈ N× N;(1, 0) ∈ Z× N0; (1, 0) ∈ N× Z; (1, 0) ∈ N× N0; (1, 0) /∈ N× N;(0, 0) ∈ Z× Z; (0, 0) ∈ N0 × N0; (0, 0) ∈ N0 × Z; (0, 0) /∈ N× Z;(4,−5) ∈ 2Z× Z; (4,−5) /∈ 2Z× N; (4,−5) /∈ N× 2Z; (4,−5) ∈ 2N× Z.


(N0,Ø) ∈ P(N0)× P(Z); (Ø,N0) ∈ P(N0)× P(Z);(Ø,Z) ∈ P(N0)× P(Z); (N,N0) ∈ P(N0)× P(Z);(N,N) ∈ P(N0)× P(Z); (2, 7) /∈ P(N0)× P(Z);

(Ø, Ø) /∈ P(N0)× P(Z); (1,−5) /∈ P(N0)× P(Z).


Esercizio 1.6.1. Per n = 2 si ha 4 = 2(2+1)−2. Con h ≥ 2, supposto per ipotesiinduttiva 4 + 6 + 8 + · · ·+ 2h = h(h+ 1)− 2, si ha 4 + 6 + 8 + · · ·+ 2(h+ 1) =

18 Capitolo 1

4+6+8+ · · ·+2h+2(h+1) = h(h+1)−2+2(h+1) = h2 +h−2+2h+2 =h2 + 3h+ 2− 2 = (h+ 1)(h+ 2)− 2.

Esercizio 1.6.2. Per n = 6 si ha 12 = 6(6 + 1) − 30. Con h > 6, supposto peripotesi induttiva 12+14+· · ·+2(h−1) = (h−1)h−30, si ha 12+14+· · ·+2h =12 + 14 + · · ·+ 2(h− 1) + 2h = (h− 1)h− 30 + 2h = h(h− 1 + 2)− 30 =h(h+ 1)− 30.

Esercizio 1.6.3. Per n = 3 si ha 3 ·23 = 3 ·8 = 24 = 8 ·3 = 8(2(3−1)−1). Conh ≥ 3, supposto per ipotesi induttiva 3·23+4·24+· · ·+h·2h = 8(2h−2(h−1)−1)si ha 3·23+4·24+· · ·+(h+1)·2h+1 = 3·23+4·24+· · ·+h·2h+(h+1)·2h+1 =8(2h−2(h−1)−1)+(h+1)·2h+1 = 2h−2(8(h−1)+(h+1)23)−8 = 2h−2(8(h−1)+8(h+1))−8 = 2h−2(2·8h)−8 = 8(2h−1h−1) = 8(2h+1−2(h+1−1)−1).

Esercizio 1.6.4. Per n = 5 si ha 25 = 32 = 64 − 32 = 26 − 32 = 25+1 − 32.Con h > 5, supposto per ipotesi induttiva 25 + 26 + · · ·+ 2h−1 = 2h − 32 , si ha25 + 26 + · · ·+ 2h = 25 + 26 + · · ·+ 2h−1 + 2h = 2h− 32 + 2h = 2 · 2h− 32 =2h+1 − 32.

Esercizio 1.6.5. Per n = 0 si ha 60 = 1 = 55 = 6(0+1)−1

5 . Con h > 0, supposto peripotesi induttiva 60 +61 +62 + · · ·+6h−1 = 6h−1

5 , si ha 60 +61 +62 + · · ·+6h =

60 +61 +62 + · · ·+6h−1 +6h = 6h−15 +6h = 6h−1+5·6h

5 = 6h(1+5)−15 = 6h+1−1

5 .

Esercizio 1.6.6. Per n = 4 si ha 43 = 64 = 100−36 = 16·254 −36 = 42(4+1)2

4 −36.Con h > 4, supposto per ipotesi induttiva 43 + 53 + 63 + · · · + (h − 1)3 =(h−1)2h2

4 − 36, si ha 43 + 53 + 63 + · · · + h3 = 43 + 53 + 63 + · · · + (h −1)3 + h3 = (h−1)2h2

4 − 36 + h3 = (h−1)2h2+4h3

4 − 36 = h4−2h3+h2+4h3

4 − 36 =h4+2h3+h2

4 − 36 = h2(h+1)2

4 − 36.

Esercizio 1.6.7. Per n = 1 si ha 1 = 3 ·12−2 ·1. Con h ≥ 1, supposto per ipotesiinduttiva 1+7+13+· · ·+(6h−5) = 3h2−2h, si ha 1+7+13+· · ·+(6(h+1)−5) = 1+7+13+· · ·+(6h−5)+(6(h+1)−5) = 3h2−2h+(6(h+1)−5) = 3h2−2h+6h+6−5 = 3h2+4h+1 = 3h2+6h+3−2h−2 = 3(h2+2h+1)−2(h+1).

Esercizio 1.6.8. Per n = 1 si ha 15 = 4

4·5 = 51−14·51 . Con h ≥ 1 supposto per

ipotesi induttiva 15 + 1

52 + · · · + 15h = 5h−1

4·5h , si ha 15 + 1

52 + · · · + 15h+1 =

15 + 1

52 + · · ·+ 15h + 1

5h+1 = 5h−14·5h + 1

5h+1 = 5·(5h−1)+44·5h+1 = 5h+1−5+4

4·5h+1 = 5h+1−14·5h+1 .

Esercizio 1.6.9. Per n = 0 si ha 440 − 1 = 1 − 1 = 0 e 43|0. Con h ≥ 0,


supposto per ipotesi induttiva 43|44h − 1, si ha 44h − 1 = 43t per un opportunot ∈ Z, e 44h+1 − 1 = 44h · 44− 1 = 44h · (43 + 1)− 1 = 44h · 43 + 44h − 1 =44h · 43 + 43t = 43(44h + t) da cui 43|44h+1.

Esercizio 1.6.10. Per n = 1 si ha 82 − 1 = 63 e ovviamente 63|63. Con h ≥ 1,supposto per ipotesi induttiva 63|82h − 1, si ha 82h − 1 = 63t per un opportunot ∈ Z, e 82(h+1) − 1 = 82h · 82 − 1 = 82h · (63 + 1)− 1 = 82h · 63 + 82h − 1 =82h · 63 + 63t = 63(82h + t) da cui 63|82(h+1).

Esercizio 1.6.11. Per n = 2 si ha 10 = 5·42 = 5(22+2−2)

2 . Con h > 2, supposto

per ipotesi induttiva 10 + 15 + · · · + 5(h − 1) = 5((h−1)2+(h−1)−2)2 , si ha 10 +

15 + · · · + 5h = 10 + 15 + · · · + 5(h − 1) + 5h = 5((h−1)2+(h−1)−2)2 + 5h =

5(h2−2h+1+h−3)+2·5h2 = 5h2−10h+5+5h−15+10h

2 = 5h2+5h−102 = 5(h2+h−2)

2 .

Esercizio 1.6.12. Per n = 1 si ha 10 = 9+112 = 9·12+11·1

2 . Con h > 1, supposto

per ipotesi induttiva 10 + 19 + 28 + · · · + (9(h − 1) + 1) = 9(h−1)2+11(h−1)2 ,

si ha 10 + 19 + 28 + · · · + (9h + 1) = 10 + 19 + 28 + · · · + (9(h − 1) +1) + (9h + 1) = 9(h−1)2+11(h−1)

2 + (9h + 1) = 9(h2−2h+1)+11(h−1)+18h+22 =

9h2−18h+9+11h−11+18h+22 = 9h2+11h

2 .



Esercizio 1.6.15. Per n = 4 si ha 42 = 16 = 1806 − 14 = 4(4+1)(2·4+1)

6 − 14. Conh > 4, supposto per ipotesi induttiva 42+52+· · ·+(h−1)2 = (h−1)h(2(h−1)+1)

6 −14, si ha 42 +52 + · · ·+h2 = 42 +52 + · · ·+(h−1)2 +h2 = (h−1)h(2(h−1)+1)

6 −14+h2 = (h2−h)(2h−1)+6h2

6 −14 = 2h3−2h2−h2+h+6h2

6 −14 = 2h3+3h2+h6 −14 =

(h2+h)(2h+1)6 − 14 = h(h+1)(2h+1)

6 − 14.

Esercizio 1.6.16. Per n = 4 si ha 4 · 24 = 4 · 16 = 16 · 4 = 16(6 − 2) =

20 Capitolo 1

16(24−3(4− 1)− 2). Con h ≥ 4, supposto per ipotesi induttiva 4 · 24 + 5 · 25 +· · ·+ h · 2h = 16(2h−3(h− 1)− 2), si ha 4 · 24 + 5 · 25 + · · ·+ (h+ 1) · 2h+1 =4 ·24 +5 ·25 + · · ·+h ·2h+(h+1)2h+1 = 16(2h−3(h−1)−2)+(h+1)2h+1 =16(2h−3(h − 1) − 2 + (h + 1)2h−3) = 16(2h−32h − 2) = 16(2h−2h − 2) =16(2(h+1)−3((h+ 1)− 1)− 2).

Esercizio 1.6.17. Per n = 1 si ha 1 = 99 = 101−1

9·101−1 . Con h ≥ 1, supposto peripotesi induttiva 1 + 1

10 + 1100 + · · · + 1

10h−1 = 10h−19·10h−1 , si ha 1 + 1

10 + 1100 +

· · · + 110(h+1)−1 = 1 + 1

10 + 1100 + · · · + 1

10h−1 + 110(h+1)−1 = 10h−1

9·10h−1 + 110h =

10(10h−1)+99·10h = 10h+1−10+9

9·10h = 10h+1−19·10h = 10h+1−1

9·10(h+1)−1 .


V ∪ V = V, V ∪ Ø = V, Ø ∪ V = V, Ø ∪ Ø = Ø,V ∩ V = V, V ∩ Ø = Ø, Ø ∩ V = Ø, Ø ∩ Ø = Ø,V \ V = Ø, V \ Ø = V, Ø \ V = Ø, Ø \ Ø = Ø,V ∪V = Ø, V ∪Ø = V, Ø ∪V = V, Ø ∪Ø = Ø.


−4 ∈ N ∪ 4Z, 8 ∈ N ∪ 4Z, −15 /∈ N ∪ 4Z, 15 ∈ N ∪ 4Z,−4 /∈ N ∩ 4Z, 8 ∈ N ∩ 4Z, −15 /∈ N ∩ 4Z, 15 /∈ N ∩ 4Z,−4 /∈ N \ 4Z, 8 /∈ N \ 4Z, −15 /∈ N \ 4Z, 15 ∈ N \ 4Z,−4 ∈ N ∪ 4Z, 8 /∈ N ∪ 4Z, −15 /∈ N ∪ 4Z, 15 ∈ N ∪ 4Z.


(2Z ∪ 3Z) ∩A = −6,−4,−2, 0, 2, 4, 6,−3, 3,(2Z ∩ 3Z) ∩A = −6, 0, 6,(2Z \ 3Z) ∩A = −4,−2, 2, 4,(2Z ∪ 3Z) ∩A = −4,−3,−2, 2, 3, 4.


X ∈ P(S ∩ T ) ⇐⇒ X ⊆ S ∩ T⇐⇒ (X ⊆ S) e (X ⊆ T )⇐⇒ X ∈ P(S) e X ∈ P(T )⇐⇒ X ∈ P(S) ∩ P(T ).


Si ha poi:

X ∈ P(S) ∪ P(T ) =⇒ (X ∈ P(S)) o (X ∈ P(T ))=⇒ (X ⊆ S) o (X ⊆ T )=⇒ X ⊆ S ∪ T=⇒ (X ∈ P(S ∪ T )).

Se A = a, b, B = a, c si ha b, c ∈ P(A ∪ B), ma b, c /∈ P(A) eb, c /∈ P(B), pertanto P(A) ∪ P(B) ⊂ P(A ∪B).


x ∈ (L \N) ∪ (M \ (L ∪N)) ⇐⇒ x ∈ L \N o x ∈ (M \ (L ∪N))⇐⇒ (x ∈ L e x /∈ N) o (x ∈M e x /∈ L ∪N)⇐⇒ (x ∈ L e x /∈ N)

o (x ∈M e x /∈ L e x /∈ N)⇐⇒ (x ∈ L o x ∈M) e (x /∈ N)⇐⇒ x ∈ (L ∪M) \N.

Esercizio 1.6.23. Risulta L \ (M ∪ N) = (L \M) ∩ (L \ N) per le formule diDe Morgan, da cui per la 1.4.4, l’Esercizio 1.4.10 e l’Esercizio 1.4.13 si ha:

L \ (M ∪N) = L \M ⇐⇒ L \M ⊆ L \N⇐⇒ L \ (L \N) ⊆ L \ (L \M)⇐⇒ L ∩N ⊆ L ∩M⇐⇒ L ∩N ⊆M.

Esercizio 1.6.24. Per l’Esercizio 1.4.34 si ha T = (T \S)∪(T ∩S), pertanto, perle proprieta commutativa e associativa dell’unione, per la proprieta commutativadell’intersezione, per la (1.4.6) e per la 1.4.4: S∪T = S∪ ((T \S)∪ (T ∩S)) =(S ∪ (T ∩ S))∪ (T \ S) = (S ∪ (S ∩ T ))∪ T \ S = S ∪ (T \ S). Ovviamente siha poi S ∩ (T \ S) = Ø.

Esercizio 1.6.25. Per l’esercizio precedente e per la 1.4.1 si ha: S ⊆ T ⇐⇒S ∪ T = T ⇐⇒ T = S ∪ (T \ S).

Esercizio 1.6.26. Per la proprieta distributiva a destra del complemento rispettoall’unione si ha: (S ∪ T ) \ (S ∪ V ) = (S \ (S ∪ V )) ∪ (T \ (S ∪ V )) =Ø ∪ (T \ (S ∪ V )) = T \ (S ∪ V ).

Esercizio 1.6.27. Per la (1.4.19) si ha S ∪T = (S \ T ) ∪ (T \ S), pertanto

(S ∪T ) \ V = ((S \ T ) ∪ (T \ S)) \ V

22 Capitolo 1

= ((S \ T ) \ V ) ∪ ((T \ S) \ V )= (S \ (T ∪ V )) ∪ (T \ (S ∪ V )),

per l’Esercizio 1.4.14. Si ha poi

V \ (S ∪T ) = V \ ((S ∪ T ) \ (S ∩ T )) = (V \ (S ∪ T )) ∪ (S ∩ T ∩ V ),

ancora per l’Esercizio 1.4.14. Risulta allora

(S ∪T ) ∪V = (S ∪T ) \ V ) ∪ (V \ (S ∪T ))= (S \ (T ∪ V )) ∪ (T \ (S ∪ V )) ∪ (V \ (S ∪ T )) ∪ (S ∩ T ∩ V ).

Si ha poi, per la proprieta commutativa dell’unione, dell’intersezione e dell’unionedisgiunta:

S ∪(T ∪V ) = (T ∪V ) ∪S= (T \ (V ∪ S)) ∪ (V \ (T ∪ S)) ∪ (S \ (T ∪ V )) ∪ (T ∩ V ∩ S)= (S \ (T ∪ V )) ∪ (T \ (S ∪ V ) ∪ (V \ (S ∪ T ) ∪ (S ∩ T ∩ V )= (S ∪T ) ∪V.


(Ø, 3) ∈ P(Z)× N0; (−4, 3) ∈ P(Z)× N0;(Ø, 3) /∈ P(Z)× N0; (N0, 6) ∈ P(Z)× N0;(Ø, 4) /∈ P(Z)× P(N0); (−4, 3) /∈ P(Z)× P(N0);(Z,Ø) /∈ P(N0)× P(Z); (N,Z) ∈ P(N0)× P(Z);(1,−1, 3N) /∈ P(N0)× P(Z); (3N, 1,−1) ∈ P(N0)× P(Z);(3Z,−3) ∈ P(Z)× N0; (N, 3) ∈ P(Z)× N0.


(5Z, N) /∈ P(Z)× P(N0); (−9, 2) /∈ P(Z)× P(N0);(Ø, 8) /∈ P(Z)× P(N0); (Ø, 2) /∈ P(Z)× P(N0);(N0, 6) /∈ P(Z)× P(N0); (N, 2) /∈ P(Z)× P(N0);(−4, 2) /∈ P(Z)× P(N0); (2Z,−2) /∈ P(Z)× P(N0).

Esercizio 1.6.30. Le rappresentazioni richieste sono le seguenti:

S T

V

T \ (S ∪ V )

S T

V

S ∪ (T \ V )

S T

V

V \ (S ∩ T )


S T

V

T \ (S ∩ V )

S T

V

S ∩ (T \ V )

S T

V

V \ (S ∪ T )

S T

V

T \ (S ∪ V )

S T

V

(S ∪ T ) \ (S ∪ V )

S T

V

(S ∪ T ) \ (S ∪ V )

S T

V

(S \ V ) ∪ (T ∩ V )

S T

V

V \ (S ∪ T )

S T

V

(S \ T ) ∪ (V \ S)

Esercizio 1.6.31. Sono vere le affermazioni:

S ∪ T = T ⇐⇒ S ⊆ T,S \ T = S ⇐⇒ S ∩ T = Ø.

Le altre sono false.

2Relazioni tra insiemi

Esercizio 2.1.1. Esistono elementi di N0 che non hanno corrispondenti nella R1,per esempio 3 /R1 y, per ogni y ∈ Z. Esistono elementi di N0 con piu di uncorrispondente nellaR1, per esempio 4R1 2 e 4R1−2.

Ogni elemento di Z ha uno e un solo corrispondente nellaR2, per ogni x ∈ Zsi ha infatti x2 ∈ N0 e xR2 x

2, con x2 univocamente determinato.



Esercizio 2.1.4. Siano S = a, b, c e R = (a, b), (b, a), (a, c). R non esimmetrica poiche aR c e c /R a, e non e asimmetrica poiche aR b e bR a cona 6= b.

Esercizio 2.1.5. Siano S = a, b, R1 = (a, b), R2 = (a, b), (b, b). R1 eantiriflessiva poiche a /R1 a e b /R1 b ; R2 non e riflessiva poiche a /R2 a e non eantiriflessiva poiche bR2 b.

Esercizio 2.1.6. Si ha xRt y per ogni x, y ∈ S, pertanto ovviamenteRt e riflessi-va, simmetrica e transitiva. Se Rt e asimmetrica, con x, y ∈ S, da xRt y, yRt xsegue x = y, pertanto S e un singleton. Il viceversa e ovvio.

Esercizio 2.1.7. Se S non e vuoto, la relazione vuota e antiriflessiva, simmetricae transitiva. Se S = Ø la relazione vuota e riflessiva, antiriflessiva, simmetrica etransitiva.

Esercizio 2.1.8. La relazione idS e riflessiva, simmetrica e transitiva, ed e asim-metrica se e solo se S e vuoto o e un singleton. Inoltre e antiriflessiva se e solo seS e vuoto.

Esercizio 2.1.9. Segue subito dalla definizione.

26 Capitolo 2


2 /R 10, 0 /R 0, 3 /R 3, 10R 13, 1R 1, 10 /R 17,4R 5, 6 /R 9, 7R 9, 13R 17, 5 /R 4, 2 /R 2.

R non e dunque riflessiva poiche per esempio 2 /R 2 (ne antiriflessiva poicheper esempio 1R 1). Non e simmetrica, infatti per esempio 4R 5 e 5 /R 4; none transitiva, poiche per esempio 10R 13, 13R 17 e 10 /R 17. Da xR y e yRxsegue 3 + 4x = 4 + 3y e 3 + 4y = 4 + 3x, da cui, sottraendo membro a membrosi ricava 4(x−y) = 3(y−x), cioe 7(x−y) = 0, da cui x−y = 0, dunque x = ye poi x = y = 1. PertantoR e asimmetrica.


1 /R 4, −1R 3, 4 /R 3, −4R−1, 1R 1, −6R 5,−1 /R −1, 4R 1, 9R−1, −2 /R 4, 11R 5, 0 /R −2.

PertantoR non e riflessiva (ne antiriflessiva), non e simmetrica infatti per esempio4R 1 e 1 /R 4, non e transitiva poiche per esempio 9R−1,−1R 3 ma 9 /R 3,e non e un’applicazione perche per esempio 2 non ha corrispondenti. Infine larelazione e asimmetrica, poiche da xR y, yRx segue x = y = 1. Infatti siaxR y, allora (2x−5 = 5y−8 da cui 2x = 5y−3 e x = 5y−3

2 ) oppure (2x−5 =8−5y, da cui 2x = 13−5y e x = 13−5y

2 ). Nel primo caso risulta 5x−8 = 25y−312

e da yRx segue (25y−312 = 2y−5 e 21y = 21, sicche y = 1 e ancora x = 1 = y),

oppure (25y−312 = 5 − 2y che conduce all’assurdo 29y = 41). Nel secondo caso

si ha 5x − 8 = 49−25y2 e da yRx segue (2y − 5 = 49−25y

2 e y = 5929 assurdo),

oppure (5− 2y = 49−25y2 e y = 13

7 ancora assurdo).

Esercizio 2.1.12. Si ha xR y ⇐⇒ (x = y) o (x+ y = 16). Si ha allora:

−3R−3, −3R 19, 0 /R −8, 0 /R 8,2R 14, −2 /R 14, 5R 5, 5 /R −11.

Ovviamente R e riflessiva e simmetrica, non e asimmetrica poiche per esempio0R 16, 16R 0. Infine e transitiva, infatti da xR y, yR z segue ovviamente xR zse x = y o y = z, se invece x = 16− y e y = 16− z si ha x = 16− 16 + z, dacui x = z e xR z.


3R−3, 3 /R 4, 2 /R 5, 2 /R −2, 7R 1, 4 /R 2,2 /R 1, −4 /R 2, 0R−1, 0 /R 0, −3 /R 3, −3R 2,1 /R 1, 8R 2, 5R−1, 4 /R 3, −1R 0, 3 /R 2.

Relazioni tra insiemi 27

Pertanto R non e riflessiva e non e simmetrica essendo per esempio 3R−3 e−3 /R 3. Si ha 0R−1,−1R 0 ma 0 /R 0, pertanto la relazione non e transitiva,infineR non e asimmetrica essendo ancora 0R−1,−1R 0 con −1 6= 0.

Esercizio 2.1.14. R1 non e un’applicazione perche per esempio 2 non ha cor-rispondenti. R2 e un’applicazione perche ogni x ∈ Z ha come corrispondente,unico, 8x ∈ 8Z. R3 non e un’applicazione perche ogni x ∈ Z ha corrispon-denti 8x e −8x ∈ 8Z. R4 non e un’applicazione perche per esempio 2 non hacorrispondenti.

Esercizio 2.1.15. R1 non e un’applicazione perche tutti i numeri dispari non han-no corrispondenti e per lo stesso motivo non lo eR2. R3 e un’applicazione percheogni x ∈ N0 ha come corrispondente solo 2x ∈ 2N0. R4 non e un’applicazioneperche per esempio 2 ha come corrispondenti 6 e 10.

Esercizio 2.1.16. R1 e un’applicazione perche ogni x ∈ Z ha come unico cor-rispondente il numero razionale 5

6x. R2 non e un’applicazione perche vi sononumeri con piu di un corrispondente: infatti ogni x ∈ Z ha come corrispondente14x e −1

4x. R3 non e un’applicazione perche per esempio 2 non ha corispondenti.R4 e un’applicazione perche ogni x ∈ Z ha come unico corrispondente x

2 .

Esercizio 2.1.17. R1 eR2 sono la stessa applicazione in cui ogni x ∈ N0 ha comeunico corrispondente il numero razionale x

2 . R3 non e un’applicazione perche peresempio 2 non ha corrispondenti.

Esercizio 2.1.18. R1 e un’applicazione perche ogni x ∈ N ha come unico corri-spondente il numero razionale 2

3x. R2 e un’applicazione perche ogni x ∈ N hacome unico corrispondente il numero razionale 2

3x2. R3 non e un’applicazione

perche vi sono elementi di N che non hanno corrispondenti, per esempio 1 /R3 yper ogni razionale y. R4 non e un’applicazione perche vi sono elementi di N conpiu di un corrispondente, per esempio 1R4

23 , 1R4−2

3 .

Esercizio 2.1.19. R1 e R2 sono applicazioni perche ogni elemento di S ha unoe un solo corrispondente in T . R3 non e un’applicazione perche n non ha cor-rispondenti. R4 non e un’applicazione perche m non ha corrispondenti. R5 eun’applicazione perche ogni elemento di S ha uno e un solo corrispondente inS. R6 non e un’applicazione perche l’elemento l ha due corrispondenti o ancheperche n non ha corrispondenti.

Esercizio 2.1.20. R1 non e un’applicazione perche ogni elemento maggiore di 3non ha corrispondenti. R2 e un’applicazione perche ogni x ∈ N ha come corri-spondente, unico, x + 4 ∈ N. R3 non e un’applicazione perche ogni x ∈ N hainfiniti corrispondenti, tutti i numeri naturali maggiori o uguali a 3.

28 Capitolo 2

Esercizio 2.1.21. R non e una relazione d’equivalenza perche non e simmetrica,essendo per esempio 12R 6 e 6 /R 12. R non e una relazione d’ordine perche none asimmetrica, infatti per esempio 6R 10 e 10R 6 con 6 6= 10.

Esercizio 2.1.22. R non e una relazione d’equivalenza ne d’ordine perche non etransitiva, infatti per esempio 6R 12, 12R 24, 6 /R 24.

Esercizio 2.1.23. Segue subito dalle definizioni.

3Elementi di calcolo combinatorio

Esercizio 3.1.1. L’asserto vale per k = 2 (vedi 3.1.1). Con k ≥ 2, supposto peripotesi d’induzione

∣∣⋃ki=1Ai

∣∣ =∑k

i=1 |Ai|, si ha∣∣∣∣∣k+1⋃i=1

Ai

∣∣∣∣∣ =

∣∣∣∣∣(

k⋃i=1

Ai

)∪Ak+1

∣∣∣∣∣ =k∑i=1

|Ai|+ |Ak+1|

essendo, per la proprieta distributiva dell’intersezione rispetto all’unione,(k⋃i=1

Ai

)∩Ak+1 =

k⋃i=1

(Ai ∩Ak+1) = Ø.

Pertanto si ha ∣∣∣∣∣k+1⋃i=1

Ai

∣∣∣∣∣ =k+1∑i=1

|Ai| ,

e l’asserto vale per ogni k ≥ 2 per il principio d’induzione.


|A ∪B ∪ C| = |(A ∪B) ∪ C| = |A ∪B|+ |C| − |(A ∪B) ∩ C|= |A|+ |B| − |A ∩B|+ |C| − |(A ∩ C) ∪ (B ∩ C)|

= |A|+ |B|+ |C| − |A ∩B| − (|A ∩ C|+ |B ∩ C| − |A ∩B ∩ C|)= |A|+ |B|+ |C| − |A ∩B| − |A ∩ C| − |B ∩ C|+ |A ∩B ∩ C|.

Esercizio 3.1.3. I numeri tra 1 e 1250 divisibili per 17 sono 73, quelli divisibiliper 31 sono 40, quelli divisibili per 17 · 31 = 527 sono 2. Il numero richiesto edunque 73 + 40− 2 = 111.

30 Capitolo 3

Esercizio 3.1.4. Si proceda per induzione su k. Per k = 2 l’asserto segue da3.1.3. Si assuma vera l’uguaglianza per k. Si ha allora∣∣∣∣∣

k+1⋃i=1

Ai

∣∣∣∣∣ =

∣∣∣∣∣(k⋃i=1

Ai) ∪Ak+1

∣∣∣∣∣ =

∣∣∣∣∣k⋃i=1

Ai

∣∣∣∣∣+ |Ak+1| −

∣∣∣∣∣(k⋃i=1

Ai) ∩Ak+1

∣∣∣∣∣=

k∑i=1

|Ai| −∑

1≤i<j≤k|Ai ∩Aj |+ . . .

· · ·+ (−1)k−1

∣∣∣∣∣k⋂i=1

Ai

∣∣∣∣∣+ |Ak+1| −

∣∣∣∣∣k⋃i=1

(Ai ∩Ak+1)

∣∣∣∣∣osservato che, per 1.4.9, si ha (

⋃ki=1Ai) ∩ Ak+1 =

⋃ki=1(Ai ∩ Ak+1). Per le

ipotesi d’induzione e per le proprieta (1.4.8), (1.4.7) e (1.4.9) si ottiene∣∣∣∣∣k⋃i=1

(Ai ∩Ak+1)

∣∣∣∣∣ =k∑i=1

|Ai ∩Ak+1| −∑

1≤i<j≤k|Ai ∩Aj ∩Ak+1|+

+∑

1≤i<j<h≤k|Ai ∩Aj ∩Ah ∩Ak+1| − ...+ (−1)k−1

∣∣∣∣∣(

k⋂i=1

Ai

)∩Ak+1

∣∣∣∣∣ .Sostituendo nella prima espressione si ottiene l’asserto.

Esercizio 3.1.5. Sia N il numero richiesto, cioe il numero degli scontrini in cuicompaiono sia un’aranciata che un chinotto. Il numero degli scontrini in cui com-pare un’aranciata vale 12, il numero degli scontrini in cui compare un chinottovale 15, il numero degli scontrini in cui compare o un’aranciata o un chinotto vale21, perche vi sono 21 giovani presenti e la consumazione e obbligatoria. Si haallora 21 = 12 + 15−N , da cui N = 12 + 15− 21 = 6.

Esercizio 3.1.6. I numeri tra 1 e 101 divisibili per 2 sono 50, quelli divisibili per5 sono 20, quelli divisibili per 2 · 5 = 10 sono 10. I numeri tra 1 e 101 divisibiliper almeno uno tra 2 e 5 sono dunque 50 + 20− 10 = 60.

I numeri divisibili per 7 sono 14, quelli divisibili per 2 · 7 = 14 sono 7, quellidivisibili per 5 · 7 = 35 sono 2 e c’e solo 1 numero divisibile per 2 · 5 · 7 =70. I numeri tra 1 e 101 divisibili per almeno uno tra 2, 5 e 7 sono dunque:50 + 20 + 14− 7− 10− 2 + 1 = 66.

Esercizio 3.1.7. Si osservi innanzitutto che un numero n e divisibile per 6 e per 8se e solo se e divisibile per 3 e per 8.

I numeri tra 1 e 1000 divisibili per 5 sono 200, quelli divisibili per 3 sono333, quelli divisibili per 8 sono 125, i numeri divisibili per 5 · 3 = 15 sono 6,quelli divisibili per 5 · 8 = 40 sono 25, quelli divisibili per 3 · 8 = 24 sono 41,

Elementi di calcolo combinatorio 31

infine quelli divisibili per 5 · 3 · 8 = 120 sono 8. I numeri tra 1 e 1000 divisibiliper 5 o per 6 o per 8 sono dunque 200 + 333 + 125− 66− 25− 41 + 8 = 534.Il numero richiesto e 1000− 534 = 466.

Esercizio 3.1.8. Siano A1, A2, A3, A4, A5, A6 le 6 facce del parallellepipedo esi supponga che A1, A2 siano le due facce che hanno dimensioni cm 7 e cm 7 eA3, A4, A5, A6 le quattro facce che hanno dimensioni cm 7 e cm 5. Per ogni i siaBi l’insieme dei cubetti disposti sulla faccia Ai. Il numero richiesto e

∣∣⋃6i=1Bi

∣∣,che, per il principio di inclusione-esclusione, vale

6∑i=1

|Bi| −∑

1≤i<j≤6

|Bi ∩Bj |+∑

1≤i<j<h≤6

|Bi ∩Bj ∩Bh|,

essendo Bi ∩ Bj ∩ Bh ∩ Bk = Ø se 1 ≤ i < j < h < k ≤ 6. Si ha |B1| =|B2| = 7 · 7 = 49, |B3| = |B4| = |B5| = |B6| = 5 · 7 = 35. Se 1 ≤ i < j ≤ 6,Bi ∩ Bj e non vuoto se e solo se e uno spigolo del parallelepipedo. Poiche visono dodici spigoli di cui quattro da 5 centimetri e otto da 7 centimetri, si ha poi∑

1≤i<j≤6 |Bi ∩ Bj | = (4 · 5) + (8 · 7) = 76. Infine, se 1 ≤ i < j < h ≤ 6,Bi ∩ Bj ∩ Bh e vuoto o e un vertice del solido; poiche i vertici sono otto si ha∑

1≤i<j<h≤6 |Bi ∩Bj ∩Bh| = 8.Il numero richiesto e dunque 2 · 49 + 4 · 35− 76 + 8 = 170.

Esercizio 3.2.1. Basta ragionare per induzione su k, utilizzare 3.2.1 e osservareche, per ogni h ≥ 2, e biettiva l’applicazione

φ : (S1 × · · · × Sh)× Sh+1 −→ S1 × · · · × Sh × Sh+1

definita ponendo φ(((x1, . . . , xh), xh+1)) = (x1, . . . , xh, xh+1).

Esercizio 3.2.2. 213 = 9261.

Esercizio 3.2.3. 63 = 216.

Esercizio 3.2.4. 72 = 49.

Esercizio 3.2.5. 6 · 4 = 24.

Esercizio 3.2.6. I possibili pranzi diversi sono 4 · 2 · 5 = 40, ciascun giapponeseha ordinato un pranzo diverso, pertanto il gruppo e formato da al piu 40 turisti.

32 Capitolo 3

Esercizio 3.4.1. ψ e iniettiva per la cancellabilita a destra e a sinistra di unaqualunque applicazione biettiva. E poi suriettiva in quanto, per ogni g ∈ Sy,esiste φ−1 g φ ∈ Sx tale che ψ(φ−1 g φ) = φ φ−1 g φ φ−1 = g

Esercizio 3.4.2. 4! = 24.

Esercizio 3.4.3. 5! = 120.

Esercizio 3.4.4. 5! = 120.

Esercizio 3.4.5. 8!3!2!2!1! = 1680.

Esercizio 3.4.6. 9!4!3!2! = 1260.

Esercizio 3.4.7. 7!2!3! = 420, 10!

6!3! = 840.

Esercizio 3.4.8. 10!4!3!2!1! = 12600.

Esercizio 3.4.9. Una su 5!, cioe una su 120.

Esercizio 3.4.10. 4! = 24.

4Strutture algebriche


Esercizio 4.1.2. L’operazione e commutativa: infatti, per ogni n,m ∈ Z, si han⊥m = n+m−1 = m+n−1 = m⊥n. L’operazione e associativa: infatti, perogni n,m, s ∈ Z, si ha : (n⊥m)⊥s = (n+m− 1)⊥s = n+m− 1 + s− 1 =n+m+s−2, e n⊥(m⊥s) = n⊥(m+s−1) = n+m+s−1−1 = n+m+s−2,pertanto (n⊥m)⊥s = n⊥(m⊥s). 1 e elemento neutro: infatti, per ogni n ∈ Z, siha n⊥1 = n + 1 − 1 = n = 1⊥n. Infine, per ogni n ∈ Z, si ha n⊥(2 − n) =n + 2 − n − 1 = 1 = (2 − n)⊥n, pertanto n e simmetrizzabile e ha simmetrico2− n. La struttura (Z,⊥) e dunque un gruppo abeliano.

Esercizio 4.1.3. L’operazione e commutativa, infatti, per ogni n,m ∈ Z, si han⊥m = nm− 5n− 5m+ 30 = mn− 5m− 5n+ 30 = m⊥n. L’operazione eassociativa, infatti, per ogni n,m, s ∈ Z, sia ha : (n⊥m)⊥s = (nm−5n−5m+30)⊥s = (nm)s− (5n)s− (5m)s+ 30s− 5(nm− 5n− 5m+ 30)− 5s+ 30 =nms− 5ns− 5ms− 5nm+ 30s+ 25n+ 25m− 150− 5s+ 30 = nms− 5ns−5ms−5nm+25m+25n+25s−120 e n⊥(m⊥s) = n⊥(ms−5m−5s+30) =n(ms)−5ns−5nm+30n−5(ms−5m−5s+30)−5n+30 = nms−5ns−5nm+30n−5ms+25m+25s−150−5n+30 = nms−5ns−5nm−5ms+25m+25s+25n − 120, pertanto (n⊥m)⊥s = n⊥(m⊥s). Si ha n⊥e = n, per ogni n ∈ Z,se e solo se ne− 5n− 5e+ 30 = n, per ogni n ∈ Z, cioe e(n− 5) = 6(n− 5),il che equivale a e = 6, pertanto 6 e elemento neutro. Da n⊥n′ = 6 seguenn′ − 5n− 5n′ + 30 = 6, da cui nn′ − 5n− 5n′ + 24 = 0, n′(n− 5) = 5n− 24e n′ = 5n−24

n−5 = 5n−25+1n−5 = 5 + 1

n−5 , si ha! n′ ∈ Z se e solo se n− 5 divide 1 dacui n− 5 = 1 e n = n′ = 6 o n− 5 = −1 da cui n = n′ = 4; pertanto gli unicielementi simmetrizzabili sono 6 e 4. La struttura (Z,⊥) e dunque un monoidecommutativo.

Esercizio 4.1.4. L’operazione e commutativa: infatti, per ogni x, y ∈ Q, si hax⊥y = 3

2xy = 32yx = y⊥x. Si ha poi, con x, y, z ∈ Q, (x⊥y)⊥z = (3

2xy)⊥z =94xyz e x⊥(y⊥z) = x⊥(3

2yz) = 94xyz, da cui (x⊥y)⊥z = x⊥(y⊥z) e l’opera-

zione e associativa. Per ogni x ∈ Q si ha x⊥23 = 3

2x23 = x, pertanto 2

3 e elemento

34 Capitolo 4

neutro. Da 0⊥y = 23 segue l’assurdo 3

20 = 0 = 23 , dunque 0 non e simmetrizza-

bile. Per ogni elemento x ∈ Q \ 0, posto x = mn , con m ∈ Z \ 0, n ∈ N, si

ha invece x⊥ 4n9m = 2

3 , sicche x e simmetrizzabile. La struttura (Q,⊥) e dunqueun monoide commutativo e non e un gruppo.

Esercizio 4.1.5. L’operazione e commutativa: infatti, per ogni n,m ∈ 5N, si han⊥m = nm

5 = mn5 = m⊥n. Si ha poi, per ogni n,m, s ∈ 5N, (n⊥m)⊥s =

nm5 ⊥s = nms

25 e n⊥(m⊥s) = n⊥ms5 = nms

25 sicche (n⊥m)⊥s = n⊥(m⊥s) el’operazione e associativa. Si ha n⊥e = n per ogni n ∈ 5N se e solo se ne

5 = nper ogni n ∈ 5N, cioe se e solo se e = 5. Pertanto 5 e elemento neutro. Infine,con n, n′ ∈ 5N, da n⊥n′ = 5 segue nn′

5 = 5, da cui nn′ = 25 e n = n′ = 5,pertanto 5 e l’unico elemento simmetrizzabile. La struttura (5N,⊥) e un monoidecommutativo.

Esercizio 4.1.6. L’operazione e commutativa: infatti, per ogni x, y ∈ Q si hax⊥y = x+ y− 1

3 = y+ x− 13 = y⊥x. Si ha poi (x⊥y)⊥z = (x+ y− 1

3)⊥z =x+y− 1

3 +z− 13 = x+y+z− 2

3 e x⊥(y⊥z) = x⊥(y+z− 13) = x+y+z− 1

3−13 =

x+ y+ z− 23 , pertanto (x⊥y)⊥z = x⊥(y⊥z) e l’operazione e associativa. Si ha

x⊥e = x per ogni x ∈ Q se e solo se x+e− 13 = x, per ogni x ∈ Q e cio succede

se e solo se e = 13 , pertanto 1

3 e elemento neutro per ⊥. Per ogni x ∈ Q si ha poix⊥x′ = 1

3 se e solo se x + x′ − 13 = 1

3 , cioe x′ = −x + 23 , dunque ogni x ∈ Q

e simmetrizzabile e ha per simmetrico −x − 23 . La struttura (Q,⊥) e dunque un

gruppo abeliano.

Esercizio 4.1.7. L’operazione e commutativa e associativa: infatti, conm,n ∈ 2Nsi ha n⊥m = 8 + n + m = 8 + m + n = m⊥n, e, con n,m, s ∈ 2N risulta:(n⊥m)⊥s = (8 + n + m)⊥s = 8 + 8 + n + m + s = 16 + n + m + s en⊥(m⊥s) = n⊥(8 +m+ s) = 8 + n+ 8 +m+ s = 16 + n+m+ s, sicche(n⊥m)⊥s = n⊥(m⊥s). Non esiste elemento neutro, infatti da n⊥e = n perogni n ∈ 2N segue 8 + n+ e = n e 8 + e = 0, impossibile per ogni e ∈ 2N. Lastruttura (2N,⊥) e un semigruppo commutativo.

Esercizio 4.1.8. L’operazione e commutativa e associativa: infatti, conm,n ∈ 2Zsi ha n⊥m = 6 + n + m = 6 + m + n = m⊥n, e, con n,m, s ∈ 2Z risulta:(n⊥m)⊥s = (6 + n + m)⊥s = 6 + 6 + n + m + s = 12 + n + m + s en⊥(m⊥s) = n⊥(6 +m+ s) = 6 + n+ 6 +m+ s = 12 + n+m+ s, sicche(n⊥m)⊥s = n⊥(m⊥s). Da n⊥e = n per ogni n ∈ 2Z segue 6 + n + e = ne e = −6. Pertanto −6 e elemento neutro per ⊥. Per ogni n ∈ 2Z si ha poin⊥(−n − 12) = 6 + n − n − 12 = −6, sicche n e simmetrizzabile ed hasimmetrico −6− n. La struttura (2Z,⊥) e un gruppo abeliano.

Esercizio 4.1.9. L’operazione e commutativa: infatti, per ogni m,n ∈ 2Z si ham⊥n = 4m+ 4n− nm

2 − 40 = 4n+ 4m− mn2 − 40 = n⊥m. L’operazione non

Strutture algebriche 35

e associativa, per esempio risulta (2⊥−2)⊥0 = −38⊥0 = −152−40 = −192 e2⊥(−2⊥0) = 2⊥− 48 = −176. Non esiste elemento neutro, infatti da n⊥e = nper ogni n ∈ 2Z segue 4n + 4e − ne

2 − 40 = n, da cui, se n = 2, 3e = 34 cone ∈ 2Z, impossibile.

Esercizio 4.1.10. L’operazione e commutativa e associativa: infatti, per ognim,n ∈ 3Z, si ha n⊥m = n+m−18 = m+n−18 = m⊥n, e, con n,m, s ∈ 2Zrisulta: (n⊥m)⊥s = (n+m− 18)⊥s = n+m− 18 + s− 18 = n+m+ s− 36e n⊥(m⊥s) = n⊥(m+s−18) = n+m+s−18−18 = n+m+s−36, sicche(n⊥m)⊥s = n⊥(m⊥s). Da n⊥e = n per ogni n ∈ 3Z segue n + e − 18 = ne e = 18. Pertanto 18 e elemento neutro per ⊥. Per ogni n ∈ 3Z si ha poin⊥(−n + 36) = n − n + 36 − 18 = 18, sicche n e simmetrizzabile ed hasimmetrico −n+ 36. La struttura (3Z,⊥) e un gruppo abeliano.

Esercizio 4.1.11. Sia x ≥ 1, si ha 0 = x⊥x′ = x + x′ + |xx′|, non esiste alloraun simmetrico negativo x′ di x altrimenti si avrebbe 0 = x+ x′ − xx′ e 0 = 1 sex = 1, x′ = x

x−1 > 0 se x > 1, ne un simmetrico positivo x′ altrimenti si avrebbe0 = x+ x′ + xx′ e x′ = − x

1+x < 0.Sia poi 0 ≤ x < 1, l’elemento− x

1−x e allora non positivo ed e un simmetrico

di x essendo x− x1−x + x2

1−x = x−x2−x+x2

1−x = 0, non esiste invece un simmetricopositivo x′ di x altrimenti si avrebbe x+ x′ + xx′ = 0 e x′ = − x

1+x < 0.Sia ora−1 < x < 0, l’elemento− x

1−x e in tal caso positivo ed e un simmetri-

co di x essendo x− x1−x+ x2

1−x = x−x2−x+x2

1−x = 0, non esiste invece un simmetriconegativo x′ di x altrimenti si avrebbe x+ x′ + xx′ = 0 e x′ = − x

1+x > 0.Sia infine x < −1, allora x ha un simmetrico negativo, cioe − x

1+x essendo

x− x1+x−

x2

1+x = x+x2−x−x2

1+x = 0, ed un simmetrico positivo, cioe− x1−x essendo

x− x1−x + x2

1−x = x−x2−x+x2

1−x = 0.

Esercizio 4.1.12. Si ha, per ogni x ∈ Z, 0⊥x = 0 + x − 0 = x, x⊥0 =x + 0 − 0 = x, pertanto x e elemento neutro. 0 e dunque simmetrizzabile, si hapoi 2⊥2 = 2 + 2− 4 = 0 e anche 2 e simmetrizzabile ed ha come simmetrico sestesso. Da x⊥x′ = 0 segue x+ x′ − xx′ = 0 da cui x′(1− x) = −x e x′ = x

x−1 ,ma x

x−1 ∈ Z se e solo se x− 1 divide x cioe se e solo se x− 1 = 1 o x− 1 = −1cioe se e solo se x = 2 o x = 0.

Si ha 0⊥1 = 0 + 1− 0 = 1 e −1⊥1 = −1 + 1 + 1 = 1 con 0 6= −1, sicche1 non e regolare. Se a 6= 1 da a⊥x = a⊥y segue a + x − ax = a + y − ay, dacui (1 − a)x = (1 − a)y e x = y essendo 1 − a 6= 0, pertanto l’elemento a ecancellabile a sinistra e lo e anche a destra essendo l’operazione ⊥ commutativa.

Esercizio 4.1.13. (i) Sia a cancellabile a sinistra. Da T sa (x) = T sa (y) seguea⊥x = a⊥y da cui x = y per la cancellabilita; pertanto T as e iniettiva. Vi-ceversa, sia T as iniettiva. Da a⊥x = a⊥y segue T as (x) = T as (y) da cui x =

36 Capitolo 4

y per l’iniettivita di T as ; pertanto a e cancellabile a sinistra. La (ii) si provaanalogamente.

5Elementi di aritmetica

Esercizio 5.1.1. Si ha 112 = 121, 132 = 169. Si verifica immediatamente che151 non e divisibile per 2, 3, 5, 7, 11, pertanto e un numero primo per il crivello diEratostene.

Esercizio 5.1.2. Si ha 112 = 121, 132 = 169. Si verifica immediatamente che149 non e divisibile per 2, 3, 5, 7, 11, pertanto e un numero primo per il crivello diEratostene.

Esercizio 5.1.3. Si ha 132 = 169, 172 = 289. Si verifica immediatamente che 191non e divisibile per 2, 3, 5, 7, 11, 13, pertanto e un numero primo per il crivello diEratostene.

Esercizio 5.1.4. Si elenchino tutti i numeri naturali n, con 2 ≤ n ≤ 250. Si ha132 = 169, 172 = 289. Si cancellino allora tutti i multipli di 2, 3, 5, 7, 11, 13, irestanti numeri sono tutti primi. Si ottiene: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,223, 227, 229, 233, 239, 241.

Esercizio 5.2.1. (11011011)2 = 1 · 20 + 1 · 21 + 0 · 22 + 1 · 23 + 1 · 24 + 0 · 25 +1 · 26 + 1 · 27 = 1 + 2 + 8 + 16 + 64 + 128 = 219,(12210)3 = 0 · 30 + 1 · 31 + 2 · 32 + 2 · 33 + 1 · 34 = 3 + 18 + 54 + 81 = 156,(12310)4 = 0 · 40 + 1 · 41 + 3 · 42 + 2 · 43 + 1 · 44 = 4 + 48 + 128 + 256 = 436,(34024)5 = 4 ·50 + 2 ·51 + 0 ·52 + 4 ·53 + 3 ·54 = 4 + 10 + 500 + 1875 = 2389,(25401)6 = 1 ·60 +0 ·61 +4 ·62 +5 ·63 +2 ·64 = 6+144+1080+2592 = 3822,(3456)7 = 6 · 70 + 5 · 71 + 4 · 72 + 3 · 73 = 6 + 35 + 196 + 1029 = 1266,(277)8 = 7 · 80 + 7 · 81 + 2 · 82 = 7 + 56 + 128 = 191,(881)9 = 1 · 90 + 8 · 91 + 8 · 92 = 1 + 72 + 648 = 721.

38 Capitolo 5

Esercizio 5.2.2. Risulta: (324)10 = (110000)3, (14)10 = (112)3, (662)10 =(220112)3, (201)10 = (21110)3, (55)10 = (2001)3, (1200)10 = (1122110)3.Inoltre si ha: (324)10 = (1300)6, (14)10 = (22)6, (662)10 = (3022)6, (201)10 =(533)6, (55)10 = (131)6, (1200)10 = (5320)6. Si verifica anche che: (324)10 =(504)8, (14)10 = (16)8, (662)10 = (1226)8, (201)10 = (311)8, (55)10 = (67)8,(1200)10 = (2260)8. Infine: (324)10 = (400)9, (14)10 = (15)9, (662)10 =(815)9, (201)10 = (243)9, (55)10 = (61)9, (1200)10 = (1573)9.

Esercizio 5.2.3. Innanzitutto si ha: (245)8 = (165)10, (54)9 = (49)10, (2001)4 =(129)10, (22222)3 = (242)10, (2020)5 = (260)10. Si verifica poi facilmenteche: (165)10 = (10100101)2, (49)10 = (110001)2, (129)10 = (10000001)2,(242)10 = (11110010)2, (260)10 = (100000100)2. Infine: (165)10 = (324)7,(49)10 = (100)7, (129)10 = (243)7, (242)10 = (464)7, (260)10 = (521)7.

Esercizio 5.2.4. (5432)6 = (1244)10.

Esercizio 5.2.5. (10234)7 = (2524)10.

6Alcune strutture algebriche notevoli

Esercizio 6.1.1. SianoA,B,C ∈ P(S), si ha allora (A×B)×C = A×(B×C).Sia infatti x ∈ (A × B) × C, esistono allora a ∈ A, b ∈ B, c ∈ C tali chex = (ab)c; per la proprieta associativa di× si ha allora x = a(bc) ∈ A×(B×C),pertanto (A×B)×C ⊆ A× (B×C). Viceversa sia x ∈ A× (B×C), esistonoallora a ∈ A, b ∈ B, c ∈ C tali che x = a(bc) = (ab)c ∈ (A × B) × C, siccheA× (B × C) ⊆ (A×B)× C. Ne segue l’asserto.

Esercizio 6.1.2. Sia x ∈ X . Da X ⊆ S = Y segue che esistono t ≥ 1 ey1, . . . , yt ∈ Y tali che x = y1 . . . yt. Si vuole provare che e t = 1. Da X basee quindi sistema di generatori di S segue che, per ogni i ∈ 1, . . . , t, esistonosi ≥ 1 e elementi xi1, . . . , xisi ∈ X tali che yi = xi1 . . . xisi . Pertanto x =x11 . . . x1s1 . . . xt1 . . . xtst . La proprieta (6.1.1) assicura allora che t = 1 e s1 = 1sicche x = x11 = y1 ∈ Y , come volevasi.

Supposto poi X ′ base di S, si ha X ′ ⊇ X , essendo X ′ = S, e X ⊇ X ′,essendo X = S e X ′ base di S. Pertanto X = X ′.

Esercizio 6.1.3. Sia A = a. Si ha allora A+ = an : n ∈ N ed e immediatoverificare che l’applicazione

ϕ : n ∈ N 7−→ an ∈ A+

e un isomomorfismo di (N,+) in (A+, ·): infatti ϕ(n + m) = an+m = anam =ϕ(n)ϕ(m), per ogni n,m ∈ N, Imϕ = ϕ(n) : n ∈ N = an : n ∈ N = A+,e da an = am segue n = m essendo a base di A+.

Esercizio 6.1.4. Siano w,w′ ∈ A+; esistano quindi, univocamente determinati,interi s, t ≥ 1 e elementi a1, . . . , at, a

′1, . . . , a

′s ∈ A tali che w = a1 . . . at, w

′ =a′1 . . . a

′s. Si ha allora l(w) = t, l(w′) = s e ww′ = a1 . . . ata

′1 . . . a

′s, sicche

l(ww′) = t+ s = l(w) + l(w′). Cio assicura che l e un omomorfismo di (A+, ·)in (N,+).

Ovviamente se A = Ø si ha l(A+) = l(Ø) = Ø ⊂ N e l non e suriettiva.Se poi A 6= Ø, allora ha senso considerare a ∈ A, sicche per ogni n ∈ N esistean ∈ A+ tale che n = l(an).

40 Capitolo 6

Se |A| ≤ 1, ovviamente l e iniettiva giacche A+ = Ø o A+ = an : n ∈ N.Supposto poi |A| > 1 e considerati a, b ∈ A, con a 6= b, si ha l(a) = 1 = l(b)sicche l non e iniettiva.

Esercizio 6.1.5. Si consideri tZm = t[x]m|[x]m ∈ Zm = [tx]m|x ∈ Z, cont ≥ 0, e siano t[a]m, t[b]m ∈ tZm. Si ha t[a]m + t[b]m = t([a]m + [b]m) =t[a + b]m ∈ tZm (vedi (4.1.5)) e t[a]m · t[b]m = t2[a]m[b]m = t(t[ab]m) =t[tab]m ∈ tZm (vedi (4.1.2)).

Esercizio 6.1.6. A partire dal semigruppo libero S e dall’immersione i, si con-siderino ancora S come semigruppo ed i come applicazione di X in S. La pro-prieta universale assicura che esiste un unico omomorfismo σ : S −→ S tale cheσ i = i. Ovviamente idS soddisfa tale proprieta ma anche ψ ϕ la soddisfa:infatti si ha (ψ ϕ) i = ψ (ϕ i) = ψ j = i. Pertanto idS = σ = ψ ϕ.Ragionando analogamente con X+ e j si ottiene idX+ = ϕ ψ.

Esercizio 6.1.7. Con s, s′ ∈ S si ha ϕ(s)ϕ(s′) = ϕsϕs′ = ϕss′ = ϕ(ss′). Infatti,per ogni x ∈ V , risulta ϕsϕs′(x) = ϕs′(ϕs(x)) = ϕs′(xs) = (xs)s′ = x(ss′) =ϕss′(x). Supposto poi ϕ(s) = ϕ(s′), cioe ϕs = ϕs′ , con s, s′ ∈ S, si ha inparticolare s = ϕs(1) = ϕs′(1) = s′.

7L’algebra delle matrici


AT =

( 1 0 −5 4−4 −7 1 4

3 8 2 7

),

BT =(−1 32 −7 0 15

0 1 21 0 0

),

CT =

( 0 −2 1−2 3 −50

1 −50 42

).


MR1 =

1 1 1 1 11 1 0 1 11 0 0 0 11 0 0 0 0

, MR2 =

0 0 0 0 00 0 1 0 00 0 1 0 00 1 1 1 0

,

MR3 =

0 1 0 1 10 0 0 1 11 0 0 0 10 0 0 0 0

, MR4 =

0 0 1 0 01 1 1 1 01 1 1 1 11 1 1 1 1

.

Esercizio 7.1.3. R1 e una relazione d’equivalenza e non e una relazione d’ordineperche non e asimmetrica;R2 e sia una relazione d’ordine che di equivalenza;R3

non e una relazione di equivalenza e non e una relazione d’ordine perche non etransitiva;R4 non e ne simmetrica ne antisimmetrica pertanto non e d’equivalenzane d’ordine.

42 Capitolo 7


MR1 =

1 0 0 1 0 00 0 0 0 0 00 0 0 0 0 10 0 0 0 0 0

, MR2 =

1 0 0 0 0 00 1 0 0 0 00 0 1 0 0 00 0 0 1 0 0

,

MR3 =

0 0 0 0 0 01 0 0 0 0 01 0 0 0 0 00 0 0 0 0 1

, MR4 =

0 0 0 0 1 00 0 0 0 0 10 0 0 0 1 00 1 0 0 0 0

.

Pertanto R1 non e un’applicazione in quanto sia nella seconda che nella quartariga non ci sono termini uguali ad 1, R2 e un’applicazione iniettiva, R3 non eun’applicazione perche nella prima riga non compare 1,R4 e un’applicazione.

Esercizio 7.1.5. R e un’applicazione iniettiva ma non suriettiva mentreRT non eun’applicazione.

Esercizio 7.1.6. Si ha B = AT .

Esercizio 7.2.1. Posto A = (aij), AT = (cij) e B = A + AT = (bij), sinoti che cij = aji per ogni i, j ∈ 1, . . . , n. Pertanto considerati comunquei, j ∈ 1, . . . , n si ha che bij = aij + cij = aij + aji = aji + aij = bji il chevuol proprio dire che la matrice B e simmetrica.

Esercizio 7.2.2. Si ha

2AT + 3BT =

( 4 0 3 2227 2 9 223 3 7 21

).


3A+ 4B − 2C =(

10 −25 −57 −2 10

)e

AT + 2BT − CT =

( 4 2−10 −1−3 7

).

L’algebra delle matrici 43


AB =(

11 −6 141 2 −14

).

Esercizio 7.2.5. Si haAB = ( 6 1 −3 ) .

Esercizio 7.2.6. Il prodotto e sempre definito.


A2 = AA =(

10 23 7

)e

A3 = A2A =(

26 1827 −1

).

Esercizio 7.2.8. Si ha(x yz w

)(1 10 1

)=(x x+ yz z + w

)e (

1 10 1

)(x yz w

)=(x+ z y + wz w

).

Tali matrici sono uguali se e solo se z = 0 e x = w. Pertanto le matrici richiestesono tutte e sole le matrici (

x y0 x

)con x, y ∈ R.

Esercizio 7.2.9. L’uguaglianzaBU = 6U e verificata da tutte e sole le matrici deltipo (

35 yy

).


AB =

1 2 2 2−1 −3 18 30−8 −23 26 54

1 1 1 1

44 Capitolo 7

e

BA =

( −1 0 −234 29 −424 10 −3

).


3A =

( 0 −36 12−6 3

), A+B =

( −2 −15 5−9 6

),

A− C =

( −1 00 1−2 1

), 2C − 5A =

( 2 3−6 −1410 −5

),

−7A+ 3B =

( −6 7−5 −25−7 8

), A+ C +B =

( −1 −27 8−9 6

),

D =

( −2 −27 9

−11 9

), E =

( 7 −2−2 316 −11

).

Esercizio 7.2.12. Per n = 1 l’asserto e verificato, essendo

A1 = A =

( 1 2 50 1 00 0 1

)=

( 1 2 · 1 5 · 10 1 00 0 1

).

Con n > 1, si assuma per ipotesi di induzione che

A(n−1) =

( 1 2(n− 1) 5(n− 1)0 1 00 0 1

);

allora risulta:

An = AA(n−1) =

( 1 2 50 1 00 0 1

)( 1 2(n− 1) 5(n− 1)0 1 00 0 1

)

=

( 1 2n 5n0 1 00 0 1

).

Esercizio 7.2.13. Si ragioni come nell’esercizio precedente.



Esercizio 7.3.1. La relazione e banalmente riflessiva; infatti ogni matrice A siottiene da A effettuando 0 operazioni elementari sulle righe e quindi A ∼ A.

Se A ∼ B, allora B si ottiene da A effettuando n operazioni elementari sullerighe, siano γ1, γ2, . . . , γn. Per ogni i ∈ 1, . . . , n, si denoti con γ∗i l’operazioneγi se γi e l’operazione Rh ↔ Rk, l’operazione Rh → λ−1Rh se γi e Rh → λRh

con λ 6= 0, l’operazione Rh → Rh − λRk se γi e Rh → Rh + λRk. Allora A siottiene da B effettuando le n operazioni elementari sulle righe γ∗n, γ

∗n−1, . . . , γ

∗1 .

Pertanto B ∼ A.Infine, per provare che∼ e transitiva basta notare che date le matriciA,B,C,

se A ∼ B e B ∼ C allora B si ottiene da A effettuando un numero finito n dioperazioni elementari sulle righe, C si ottiene da B effettuando un numero finitom di operazioni elementari sulle righe e questo comporta che C si ottiene da Aeffettuando n + m operazioni elementari sulle righe. Quindi A ∼ C come sivoleva.

Esercizio 7.3.2. Effettuando sulle righe della matrice A nell’ordine le operazionielementari R3 → R3 − 2R1, R4 → R4 − 3R1, R4 → R4 − 13

9 R3, si ottiene la

matrice a scala 1 0 50 1 10 0 −90 0 0

.

Invece effettuando sulle righe di B l’operazione elementare R2 → R2 − 32R

1 siottiene la matrice a scala (

2 0 0 10 1 0 −1

2

).

Esercizio 7.3.3. Eseguendo sulle righe della matrice A le operazioni elementariR2 → R2 − 2R1, R3 → R3 − 3R1 e R3 → R3 − 5

4R2, sulle righe di B le

operazioni elementariR2 → R2−2R1,R3 → R3−3R1 eR3 → R3− 73R

2, sullerighe di C le operazioni R2 → R2 + 4

6R1, R3 → R3 − 1

6R1 e R3 → R3 − 1

2R2

si ottengono le matrici a scala 1 2 −3 00 0 4 20 0 0 1

2

,

1 −2 3 −10 3 −4 40 0 3 −10

3

,

6 3 −40 3 −26

30 0 −13

6

,

che sono equivalenti ad A, B, C rispettivamente.

Esercizio 7.3.4. Eseguendo sulle righe della matrice A le operazioni elementariR2 → R2−R1, R3 → R3−R1 eR3 → R3−2R2, sulle righe diB le operazioniR2 → R2 − 2R1 e R3 − 3R2, sulle righe di C le operazioni R2 → R2 − 3R1,

46 Capitolo 7

R3 → R3 −R1 e R3 → R3 −R2, si ottengono le matrici a scala( 1 0 2 1 50 1 3 1 20 0 0 1 3

),

( 1 2 50 3 −20 0 10

),

( 1 2 1 10 −6 −3 10 0 0 −4

),

che sono equivalenti ad A, B, C rispettivamente.


E13 =

( 0 0 10 1 00 0 1

), E−5

32 =

( 1 0 00 1 00 −5 1

), E

122 =

1 0 00 1

2 00 0 1

,

E321 =

( 1 0 03 1 00 0 1

), E−7

3 =

( 1 0 00 1 00 0 −7

).


T =

−2 3 10 4 −50 0 −10 0 0

e E = E−2

43 E23E12.


A ∼

3 1 40 5 20 0 4

, B ∼

3 0 2 10 1 1 60 0 4 3

.

Per ottenere tali matrici a scala basta eseguire sulle righe di A le operazioni ele-mentari R1 ↔ R2, R3 → R3 + 2R1, R3 → R3 + 2R2 e sulle righe di B leoperazioni elementari R2 → R2 + 3R1 e R3 → R3 + 2R1.

Esercizio 7.3.8. Eseguendo sulle righe di A, nell’ordine, le operazioni elementariR3 → R3 + R1, R3 → R3 + 3R2, R1 → 2R1, R3 → 3R3, R1 → R1 + 3R2,R1 → R1 + 3R3, R2 → R2 + 4R3 si ottiene la matrice I3 identica di ordine 3.Invece la matrice a scala ridotta equivalente a B e la matrice(

1 0 1 10 1 0 1

)che si ottiene eseguendo sulle righe di B le operazioni elementari R1 → 2R1,R1 → R1 + 2R2.


Esercizio 7.3.9. La matrice a scala ridotta equivalente adA e la matrice I4 identicadi ordine 4, mentre la matrice a scala ridotta equivalente a B e la matrice 1 0 0

0 1 00 0 10 0 0

.

Esercizio 7.4.1. Se n = 2, banalmente V (α1, α2) = α2 − α1. Si osservi chesviluppando il determinante di Vandermonde secondo l’ultima colonna si ottieneun polinomio di grado n−1 in αn il cui coefficiente del termine di grado massimoe V (α1, . . . , αn−1). E poi immediato osservare che α1, . . . , αn−1 sono radici ditale polinomio, pertanto, applicando il teorema di Ruffini (vedi Teorema 6.6.5) siha che V (α1, . . . , αn) = V (α1, . . . , αn−1)(αn−α1) · · · (αn−αn−1). Da questaconsiderazione segue subito l’asserto.

Esercizio 7.4.2. Si ha: detA = −12, detB = −50.


A13 =

( 2 4 0 33 1 2 11 0 4 4

), A24 =

( 1 7 3 03 1 0 11 0 7 4

),

A35 =

( 1 7 3 52 4 1 01 0 7 4

), A41 =

( 7 3 5 04 1 0 31 0 2 1

).


detA = 35 + 18− 15 = 38, detB = 6 + 28− 28− 12 = −6.

Esercizio 7.4.5. Risulta detA = 3.

Esercizio 7.4.6. Si ha detB = 5.

Esercizio 7.4.7. Si ha: detA = 6π, detB = −3, detC = −1.

Esercizio 7.4.8. Si ha: detA = 4 + 6 + 2 + 6 = 0.

48 Capitolo 7

Esercizio 7.4.9. Il complemento algebrico dell’elemento di posto (2, 2) e 3/25,quello dell’elemento di posto (1, 4) e 23/10, quello dell’elemento di posto (3, 2)e 27/5 e quello dell’elemento di posto (2, 4) e 61/20.

Esercizio 7.4.10. Si denotino con I la matrice identica, con K la matrice che siottiene sostituendo alla h-esima riga di I la sua k-esima riga moltiplicata per λ econ H la matrice che si ottiene da I sostituendo alla riga h-esima la riga k-esima.Allora si ha:

detEhk = −det I = −1;

detEλh = λdet I = λ;

detEλhk = det I + detK = 1 + λ detH = 1 + λ · 0 = 1

(si noti che detH = 0 perche la matrice H ha due righe uguali).

Esercizio 7.4.11. L’esercizio precedente assicura che ogni matrice elementaree non singolare. Se A ∼ B, allora esiste una matrice T , prodotto di matricielementari, tale che B = TA. Per il teorema di Binet si ha che detT 6= 0 e chedetB = detT detA. Dunque detA 6= 0 comporta che detB 6= 0.

Esercizio 7.4.12. Risulta: detA = −1 ·7 ·−5 ·3 = 105; detB = −3 ·2 ·10 ·11 =−660; detC = −140; detD = −48; detE = 0 perche la terza riga della matriceE e l’opposto della prima; detF = 0 perche la quarta colonna di F e il doppiodella seconda; detG = 0 perche la prima riga di G e la differenza tra la terza ela seconda; detH = 0 perche la terza colonna della matrice H e la somma delleprime due.

Esercizio 7.5.1. Posto

B :=(

d (detA)−1 −b (detA)−1

−c (detA)−1 a (detA)−1

),

basta osservare che

AB =(

(ad− bc) (detA)−1 (−ab+ ba) (detA)−1

(cd− dc) (detA)−1 (−cb+ da) (detA)−1

)= I2 = BA.

Esercizio 7.5.2. Si ha detA = 6 6= 0, pertanto A e invertibile e la matrice inversae

A−1 =

( −8/3 7/3 −113/3 11/3 2−11/6 5/3 −1

).


Le matrici B e C invece non sono invertibili perche sono entrambe singolari.

Esercizio 7.5.3 Risulta detA = 2 e poiche tale elemento e invertibile modulo 9la matrice A e invertibile e la sua inversa e

1 0 0 00 4 0 00 0 7 00 0 0 5

.

Esercizio 7.5.4. Risulta detB = 0 pertanto la matrice considerata non e inverti-bile.

Esercizio 7.5.5. Risulta detA = 7, elemento invertibile modulo 9; pertanto lamatrice A e invertibile e la sua inversa e la matrice(

7 02 7

).

Invece poiche detB = 6 e tale elemento non e invertibile modulo 9, la matrice Bnon e invertibile.

Esercizio 7.6.1. Riducendo a scala le matrici A, B e C si ottengono le matrici

A ∼

( 1 0 2 1 50 1 3 1 20 0 0 1 3

),

B ∼

( 1 2 50 3 −20 0 10

),

C ∼

( 1 2 1 10 −6 −3 10 0 0 −4

).

Pertanto tutte e tre la matrici hanno rango 3.


A ∼

1 0 50 1 10 0 −90 0 0

, B ∼(

2 0 0 10 1 0 −1

2

);

50 Capitolo 7

pertanto A ha rango 3 e B ha rango 2.

Esercizio 7.6.3. La matrice C e una matrice 4× 3 pertanto ha rango ≤ 3; d’altrocanto e possibile individuare un minore di ordine massimo non nullo e quindi essaha rango 3. Per quanto riguarda la matrice D, questa e una matrice 3× 4 e cometale ha rango al piu 3. I minori di ordine massimo sono pero tutti nulli quindi ilsuo rango e < 3 e, osservando che possiede un minore di ordine 2 non nullo sipuo concludere che essa ha rango 2.

Esercizio 7.6.4. Il rango diM e 2 per ogni t ∈ R\1; se t = 1 allora ρ(M) = 1.

Esercizio 7.6.5. La matrice A ha rango 2.

Esercizio 7.6.6. Si osservi che poiche A e una matrice 2 × 3 non nulla si ha che1 ≤ ρ(A) ≤ 2. Se a = b = c allora i minori di ordine 2 di A sono tutti nulli equesto comporta che ρ(A) = 1. Se invece l’insieme a, b, c ha ordine almeno 2allora A possiede un minore di ordine 2 non nullo e quindi ha rango 2.

Esercizio 7.7.1. Si ha: x = 32 , y = −5

2 , z = −3.

Esercizio 7.7.2. Si ha: x = 11, y = 6, z = 8.

Esercizio 7.7.3. Il primo sistema ha come unica soluzione x = 10, y = 2; ilsecondo sistema ha come unica soluzione x = 2, y = 6.

Esercizio 7.7.4. L’unica soluzione del primo sistema e x = 1, y = 0, z = 4;quella del secondo e x = 2, y = 3.

Esercizio 7.7.5. Il primo sistema ammette come unica soluzione la terna (2, 3, 4),il secondo (−2, 0, 1).

Esercizio 7.7.6. La soluzione del primo sistema e (3, 4, 3); il secondo sistema hacome soluzione (0, 0, 3).

Esercizio 7.7.7. Il sistema considerato ammette come unica soluzione la quaterna(−1, 2,−3, 2).

Esercizio 7.7.8. Il primo dei due sistemi ammette soluzioni non banali perche ildeterminante della matrice incompleta e 0; il secondo sistema ha solo la soluzionebanale perche la sua matrice incompleta ha determinante non nullo.


Esercizio 7.7.9. Il determinante della matrice incompleta del sistema consideratoe 0, pertanto per risolvere il sistema occorre utilizzare il metodo di Gauss-Jordan.Con tale metodo si scopre che il sistema considerato e equivalente al sistema

x+53t = −2

3y = 1

z +23t = −2

3.

Le soluzioni di quest’ultimo costituiscono l’insieme infinito(−2− 5t

3, 1,−2− 2t

3, t

): t ∈ Q

.

Esercizio 7.7.10. Il sistema considerato e equivalente al sistemax+ 10w = 1y + 6w = 8z + 4w = 9,

e l’insieme delle sue soluzioni e quindi (1 +w, 8 + 5w, 9 + 7w,w) : w ∈ Z11.

Esercizio 7.7.11. L’insieme delle soluzioni del primo sistema e(11t− 1

18,7t+ 1

18,4t− 2

9, t

): t ∈ Q

;

il secondo sistema ammette invece un’unica soluzione e precisamente la terna(4

5 ,−12 ,

34).

Esercizio 7.7.12. Il sistema considerato non e compatibile.

Esercizio 7.7.13. Il sistema ha un’unica soluzione: x = −3, y = 194 , z = 1

4 .

Esercizio 7.7.14. Il sistema e compatibile ed ha infinite soluzioni.

Esercizio 7.7.15. L’unica soluzione del sistema e (1, 13 , 0).

Esercizio 7.7.16. Si ha : x = 9, y = 3, z = 1, t = 8.

Esercizio 7.7.17. Si ha: x = 722 , y = 13

44 , z = −1544 .

52 Capitolo 7

Esercizio 7.7.18. L’insieme delle soluzioni del sistema considerato e

S = (3 + z, 3 + 3z, z) : z ∈ Z5,

ossia (3, 3, 0), (4, 1, 1), (0, 4, 2), (1, 2, 3), (2, 0, 4).

Esercizio 7.7.19. Il sistema ammette l’unica soluzione (5, 0, 3).

Esercizio 7.8.1. Per n = 1 il polinomio caretteristico della matrice A e −λ+ a11

che ha grado 1 e coefficiente direttivo −1. Sia n > 1 e si supponga, per ipotesi diinduzione, che il polinomio caratterisico di una matrice quadrata di ordine n − 1abbia grado n− 1 e coefficiente direttivo (−1)n−1; allora tenendo presente che ilpolinomio caratteristico di A e det(A− λI), si ha l’asserto.

Esercizio 7.8.2. Gli autovalori reali di entrambe le matrici sono 1 e 2.

Esercizio 7.8.3. Il polinomio caratteristico di A e −λ3 + 11λ2 − 35λ + 25, gliautovalori 1 e 5; il polinomio caratteristico di B e −λ3 + 8λ2 − 17λ + 4 e gliautovalori reali 4, 2 +

√3, 2−

√3.

Esercizio 7.8.4. −λ3 + 12λ + 16 e il polinomio caratteristico di entrambe lematrici, gli autovalori sono 4 e −2.

Esercizio 7.8.5. Il polinomio caratteristico e λ3 + 2λ2 + 5λ− 6, gli autovalori 1,3, −2.

Esercizio 7.8.6. Il polinomio caratteristico di A e −λ3, l’unico autovalore e 0, gliautovettori costituiscono l’insieme

V0 = (2y, y, 0) : y ∈ Q \ 0.

La matrice B ha polinomio caratteristico −λ3 + 2λ2 + 5λ − 6 e autovalori 1, 3,−2; i corrispondenti autovettori sono

V1 = (2y, y, 2y) : y ∈ Q \ 0,

V3 =(

0, y,25y

): y ∈ Q \ 0

,

V−3 = (0, 0, y) : y ∈ Q \ 0.


La matrice C ha polinomio catteristico (2− λ)(λ2 − 5λ+ 4), autovalori 2, 4, 1 eautovettori

V1 = (−y, y, y) : y ∈ Q \ 0,V2 = (y, 0, 0) : y ∈ Q \ 0,

V4 =(

72y,−2y, 0

): y ∈ Q \ 0

.

Esercizio 7.8.7. I polinomi caratteristici delle matrici A, B e C sono rispettiva-mente−λ3 +7λ2−2λ−2,−λ3 +4λ2 +9λ−2 e−λ3−3λ2 +16λ+94, nessunodei quali possiede radici in Q.

Esercizio 7.8.8. La matrice A ha polinomio caratteristico λ2 + 4, autovalori 1 e4, autovettori

V1 = (3, 1), (1, 2), (4, 3), (2, 4),V4 = (1, 1), (2, 2), (3, 3), (4, 4).

La matrice B ha polinomio caratteristico (λ+ 3)2, autovalore 2 e autovettori

V2 = (3, 1), (1, 2), (4, 3), (2, 4).

Il polinomio caratteristico della matrice C e λ2, l’unico autovalore e 0, gli auto-vettori sono

V0 = (3, 1), (1, 2), (4, 3), (2, 4).Il polinomio caratteristico della matrice D e λ2 + λ+ 2 che non ha radici in Z5.

Esercizio 7.8.9. Il polinomio caratteristico di A e λ2 + 5, gli autovalori sono 3 e4, gli autovettori sono

V3 = (2, 1), (4, 2), (6, 3), (1, 4), (3, 5), (5, 6),V4 = (5, 1), (3, 2), (1, 3), (6, 4), (4, 5), (2, 6).

Il polinomio caratteristico di B e λ2 + λ, gli autovalori sono 0 e 6, gli autovettori

V0 = (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6),V6 = (1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1).

La matrice C ha polinomio caratteristico λ2 +3λ+3, autovalori 1 e 3, autovettori

V1 = (1, 3), (2, 6), (3, 2), (4, 5), (5, 1), (6, 4),V3 = (1, 4), (2, 1), (3, 5), (4, 2), (5, 6), (6, 3).

Il polinomio caratteristico diD e λ2 +5λ, gli autovalori sono 0 e 2, gli autovettori

V0 = (1, 5), (2, 3), (3, 1), (4, 6), (5, 4), (6, 2),V2 = (6, 1), (5, 2), (4, 3), (3, 4), (2, 5), (1, 6).

54 Capitolo 7

Esercizio 7.8.10. La matrice A ha polinomio caratteristico λ2 + 8, autovalori 6 e5, autovettori

V6 = (4y, y) : y ∈ Z11 \ 0,V5 = (y, 8y) : y ∈ Z11 \ 0.

La matrice B ha polinomio caratteristico λ2 + 6λ, autovalori 0 e 5, autovettori

V0 = (9y, y) : y ∈ Z11 \ 0,V5 = (y, 2y) : y ∈ Z11 \ 0.

La matrice C ha polinomio caratteristico λ2 + 7λ+ 4, autovalore 2, autovettori

V2 = (2y, y) : y ∈ Z11 \ 0.

La matrice D ha polinomio caratteristico λ2 + 5λ+ 9, autovalore 3, autovettori

V3 = (y, 2y) : y ∈ Z11 \ 0.

Esercizio 7.9.1. I risultati dei calcoli proposti sono rispettivamente le matrici:(0 0 00 0 0

),

6 7 43 0 51 6 2

,

0 2 1 74 6 7 54 4 2 2

, (0, 0).

Esercizio 7.9.2. Si ha detH = 0, quindiH non e invertibile; detK = −11245 6= 0,

pertanto K e invertibile e

K−1 =

( 165/56 −15/56 −75/5615/28 −1/4 −45/2845/56 −9/28 −51/56

).


CT =(

3 44 2

)Essendo detC = 0, la matrice C non e invertibile. Inoltre risulta

DT =

1 0 4 02 3 1 33 1 2 14 2 4 3

.


Poiche poi detD = 2 6= 0, la matrice D e invertibile e di ha

D−1 =

0 2 4 02 1 2 44 0 4 10 0 0 4

.


AT =

( 2 5 1−4 −3 −97 6 15

), BT =

( 1 5 80 −3 20 7 5

).

Poiche poi detA = 0 = detB, le due matrici sono non invertibili.

Esercizio 7.9.5. Se n = 0, si ha

A0 = I2 =(

1 00 1

)e l’asserto e verificato. Sia dunque n > 0 e si supponga

An−1 =(

1 n− 10 1

).

Allora

An = An−1A =(

1 n− 10 1

)(1 10 1

)=(

1 n0 1

).

Esercizio 7.9.6. Entrambi i sistemi ammettono un’unica soluzione che puo esseredeterminata per esempio con la regola di Cramer. La soluzione del primo sistemae (−113/19,−83/19,−106/19), quella del secondo (10, 4).

Esercizio 7.9.7. Se n = 2 si ha

A2 = AA =(

82 00 82

)=(

82 4 + (−1)2−140 (−8)2

).

Supposto n > 2 e, per ipotesi di induzione,

An−1 =(

8n−1 8n−3(4 + (−1)n−24)0 (−8)n−1

),

l’asserto si ottiene subito eseguendo il prodotto righe per colonne An = An−1A.Si ha poi che:

AB =(−2 47 −330 8 −56

)

56 Capitolo 7

BC =(−33 34 3010 −16 7

),

A−1 =(

1/8 1/640 −1/8

).

Infine detC = 91.

Esercizio 7.9.8. Si consideri il generico elemento di G, cioe una matrice

A =

(1 a b0 1 c0 0 1

);

allora risulta

A−1 =

(1 −a ac− b0 1 −c0 0 1

).

I tre sottoinsiemi S, T , V di G sono non vuoti perche contengono la matriceidentica. Inoltre si ha:

AB−1 =

(1 a− x 00 1 00 0 1

)∈ S

per ogni

A =

(1 a 00 1 00 0 1

), B =

(1 x 00 1 00 0 1

)in S;

HC−1 =

(1 0 b− y0 1 00 0 1

)∈ T

per ogni

H =

(1 0 b0 1 00 0 1

), B =

(1 0 y0 1 00 0 1

)in T ;

MN−1 =

(1 0 00 1 c− z0 0 1

)∈ V

per ogni

M =

(1 0 00 1 c0 0 1

), N =

(1 0 00 1 z0 0 1

)∈ V.


Quindi i sottoinsiemi S, T e V sono sottogruppi di G. Si puo poi osservare chel’unico normale e S.

L’applicazione g e ben posta, e un omomorfismo, e suriettiva ma non e iniet-tiva. Infine se K = Z2, allora G ha ordine 8 e non e abeliano.

Esercizio 7.9.9. Se n = 1, allora detA1 = detA = −6 − 6 = −12 =(−1)12 e l’asserto e verificato. Sia n > 1 e si assuma, per ipotesi di induzione,detAn−1 = (−1)n−112n−1; allora applicando il teorema di Binet si ha detAn =det(An−1A) = detAn−1 detA = (−1)n−112n−1(−1)12 = (−1)n12n.

Esercizio 7.9.10. Il ragionamento e analogo a quello dell’esercizio precedente.

Esercizio 7.9.11. Se n = 1, allora(1 11 −1

)A1 =

(8 88 −8

)e l’asserto e verificato. Si assuma n > 1 e, per ipotesi di induzione,(

1 11 −1

)An−1 =

(8n−1 8n−1

8n−1 −8n−1

).

Allora da An = An−1A segue l’asserto.




Esercizio 7.9.15. Si veda l’Esercizio 7.9.4.


Esercizio 7.9.17. Per quanto riguarda la matrice A si veda l’Esercizio 7.9.2. Si hapoi

BT =

( 2/5 7/2 0−1/3 5 −1

0 −10 2/3

);

risulta detB = −17/9, ed infine

B−1 =

( 60/17 −2/17 −30/1721/17 −12/85 −36/1763/85 −18/85 −285/170

).

58 Capitolo 7


H =

( 1 −1 65 −12 10−1 5 2

);

risulta detH = 24, pertanto H ha rango 3, e invertibile, e

H−1 =

( −37/12 16/12 31/12−10/12 1/3 10/1213/24 −1/6 −7/24

).

Il sistema ammette come unica soluzione la terna (47/12, 7/6,−11/24). Il poli-nomio caratteristico di T e −λ3 + 3λ2 + 7λ e gli autovalori sono 0, (3 +

√37)/2

e (3−√

37)/2.

Esercizio 7.9.19. Si osservi che detAn = n + 1 e detBn = n + 10. Le matriciAn e Bn sono non invertibili se e solo se i loro determinanti sono non invertibilimodulo 11 e 13 rispettivamente, quindi se e solo se n − 10 ≡ 0 (mod 11) en − 3 ≡ 0 (mod 13). Il sistema di equazioni congruenziali che si ottiene puoessere risolto utilizzando il teorema cinese del resto, ed ammette come soluzionetutti e soli i numeri interi della classe di 120 modulo 143. Tra questi i numeripositivi minori di 500 sono 120, 263 e 406.


H =

( 0 0 −6−2 −4 −10−2 4 4

);

risulta detH = 96, pertanto H ha rango 3, e invertibile e

H−1 =

( 1/4 7/24 −1/61/4 −1/8 0−1/4 −1/8 0

).

Esercizio 7.9.21. Si veda l’esercizio precedente.

Esercizio 7.9.22. Risulta detH = 5, pertanto H e invertibile e si ha

H−1 =

(0 0 30 5 24 6 5

);


H =

( 1 −2 −13 0 311 −3 4

);


inoltre detH = −24, per cui H ha rango 3, e invertibile, e

H−1 =

(−3/8 −11/24 −1/4−7/8 −5/8 −1/43/8 19/24 1/4

).

Il sistema ammette come unica soluzione la terna (−5/8,−5/8, 5/8).

Esercizio 7.9.24. Risulta detH = 6, quindi H ha rango 3 ed e invertibile. Si ha

H−1 =

( −8/3 7/3 −113/3 −11/3 2−11/6 5/3 −1

).

L’unica soluzione del sistema e x = 4, y = −2, z = 3.

Esercizio 7.9.25. La matrice Bt e invertibile se e solo se t ∈ R \

3+√

52 , 3−

√5

2

;

B2 ha rango 4. Poiche detH = 10, H e invertibile e

H−1 =

6/5 −9/5 1/5 4/5−2 3 −4/5 3/26/5 −2/5 1/5 −3/5−1/5 0 0 1/10

.

L’unica soluzione del sistema lineare e (1,−9/2, 1, 3/2).

Esercizio 7.9.26. La matrice Bt e invertibile per ogni t ∈ R \ −3, 3, 2. Il rangodi B2 e 3. Poiche detH = −312, H e invertibile e si ha

H−1 =

(−3/52 −1/52 11/523/52 1/52 19/1561/52 −9/52 −11/156

).

L’unica soluzione del sistema e (−7/3, 0,−1/3, 0).

8Spazi vettoriali

Esercizio 8.1.1. Poiche l’addizione in F e associativa e immediato osservare che,per ogni (λ1, . . . , λn), (µ1, . . . , µn), (ν1, . . . , νn) ∈ Fn, si ha

((λ1, . . . , λn) + (µ1, . . . , µn)) + (ν1, . . . , νn) =(λ1, . . . , λn) + ((µ1, . . . , µn) + (ν1, . . . , νn)).

La commutativita dell’addizione in F comporta poi che

(λ1, . . . , λn) + (µ1, . . . , µn) = (µ1, . . . , µn) + (λ1, . . . , λn)

per ogni (λ1, . . . , λn), (µ1, . . . , µn) ∈ Fn. E poi facile verificare che la n-upla le cui coordinate sono tutte uguali all’elemento di F neutro rispetto all’ad-dizione e elemento neutro rispetto all’addizione in Fn. Per concludere che lastruttura (Fn,+) e un gruppo abeliano basta infine osservare che ogni elemen-to (λ1, . . . , λn) ∈ Fn e dotato di opposto: la n-upla (−λ1, . . . ,−λn) le cuicoordinate sono gli opposti in F delle coordinate di ugual posto della n-uplaconsiderata.

Siano λ ∈ F e (λ1, . . . , λn), (µ1, . . . , µn) ∈ Fn, allora la proprieta distribu-tiva della moltiplicazione rispetto all’addizione in F comporta che:

λ((λ1, . . . , λn) + (µ1, . . . , µn)) = λ(λ1, . . . , λn) + λ(µ1, . . . , µn).

Sempre in virtu della proprieta distributiva della moltiplicazione rispetto all’addi-zione in F si ha che, per ogni λ, µ ∈ F e per ogni (λ1, . . . , λn) ∈ Fn,

(λ+ µ)(λ1, . . . , λn) = λ(λ1, . . . , λn) + µ(λ1, . . . , λn).

La proprieta associativa della moltiplicazione in F assicura poi che

(λµ)(λ1, . . . , λn) = λ(µ(λ1, . . . , λn))

per ogni λ, µ ∈ F e per ogni (λ1, . . . , λn) ∈ Fn.Infine, se 1 e l’elemento di F neutro rispetto alla moltiplicazione, si ha

1(λ1, . . . , λn) = (1λ1, . . . , 1λn) = (λ1, . . . , λn)

62 Capitolo 8

per ogni (λ1, . . . , λn) ∈ Fn.

Esercizio 8.1.2. Siano A un anello unitario, F un sottoanello di A unitario econ la stessa unita di A e si supponga che F sia un campo. Allora consideratoAn = (x1, . . . , xn) : x1, . . . , xn ∈ A e posto

(x1, . . . , xn) + (y1, . . . , yn) := (x1 + y1, . . . , xn + yn)

per ogni (x1, . . . , xn), (y1, . . . , yn) ∈ An e

α(x1, . . . , xn) := (αx1, . . . , αxn)

per ogni α ∈ F e per ogni (x1, . . . , xn) ∈ An si ottiene la struttura (An,+, ·) che,come e facile verificare in analogia a quanto fatto nel precedente esercizio, e unF -spazio vettoriale.

Si noti che nel testo, erroneamente, non e esplicitamente richiesto che A e Fsiano unitari e che abbiano la stessa unita.

Esercizio 8.1.3. Siano α, β ∈ F e f(x) = a0 + a1x + · · · + anxn ∈ F [x];

applicando la proprieta distributiva della moltiplicazione rispetto all’addizione inF e le proprieta commutativa ed associativa dell’addizione, si ha che:

(α+ β)f(x) = (α+ β)(a0 + a1x+ · · ·+ anxn)

= α(a0 + a1x+ · · ·+ anxn) + β(a0 + a1x+ · · ·+ anx

n)= αf(x) + βf(x).

Inoltre la proprieta associativa di cui gode l’addizione in F assicura che

(αβ)f(x) = (αβ)(a0 + a1x+ · · ·+ anxn)

= α(β(a0 + a1x+ · · ·+ anxn))

= α(βf(x)).

Se poi si considera 1 ∈ F e immediato osservare che 1f(x) = f(x). Sianoinfine α ∈ F e f(x), g(x) ∈ F [x]; e facile verificare che α(f(x) + g(x)) =αf(x) + αg(x). Tutto questo assicura che (F [x],+, ·) e uno spazio vettoriale suF .

Esercizio 8.1.7. Si puo per esempio osservare che non vale la proprieta (vii) delladefinizione di spazio vettoriale. Infatti se si considerano 2, 3 ∈ R e (1, 1) ∈ R2,risulta (2 + 3) ?(1, 1) = 5 ?(1, 1) = (25, 25) mentre 2 ?(1, 1) + 3 ?(1, 1) =(4, 4) + (9, 9) = (13, 13).

Esercizio 8.2.1. Se W e un sottospazio di V , allora e non vuoto ed e stabilerispetto alle operazioni; pertanto per ogni α, β ∈ F e per ogni x, y ∈W si ha cheαx, βy ∈ V e poi αx+ βy ∈ V .

Spazi vettoriali 63

Viceversa se W e non vuoto e gode della proprieta di cui all’ enunciato alloraper ogni α ∈ F e x ∈ W si ha che αx = αx + 0 = αx + 0x ∈ W e quindiW e stabile per la legge esterna; inoltre per ogni x, y ∈ W si ha che x − y =1x+ (−1)y ∈W . La 8.2.1 assicure che W e un sottospazio di V .

Esercizio 8.2.2. Se W e un sottospazio di V allora (W,+) e un sottogruppo di(V,+) per cui 0 ∈W . Per provare che αx+βy ∈W per ogni α, β ∈ F e per ognix, y ∈ W si procede come nell’esercizio precedente. Il viceversa e immediato;basta osservare che W 6= Ø, perche 0 ∈W e poi l’asserto segue dalla 8.2.2.

Esercizio 8.2.3. Per esempio si consideri il campo reale e lo si riguardi comeR-spazio vettoriale. Dall’esempio 8.2.3 segue che gli unici sottospazi sono 0 eR e quindi per esempio il sottogruppo (Q,+) del gruppo additivo (R,+) non e unsottospazio.

Esercizio 8.2.4. La matrice nulla e una matrice singolare per cui l’insiemeW del-le matrici non singolari, non essendo un sottogruppo di (M2(R),+), certamentenon e un sottospazio.

Per quanto riguarda l’insieme delle matrici singolari, questo non e stabile

rispetto alla somma di matrici infatti per esempio le matrici(

1 00 0

)e(

0 00 1

)sono singolari ma hanno come somma la matrice identica che non e singolare.

Esercizio 8.2.5. W3 non e un sottospazio infatti il vettore nullo (0, 0) non e unsuo elemento essendo 0 + 0 6= 1.

W1 e un sottospazio perche (0, 0) ∈ W1 e per ogni α, β ∈ Q, per ogni(x, x), (a, a) ∈W1 si ha che α(x, x) +β(a, a) = (αx+βa, αx+βa) e quest’ul-timo e un elemento di W1 perche ha le coordinate uguali.

Analogamente si osserva che W2 e W4 sono sottospazi.

Esercizio 8.2.6. Gli insiemi W3 e W4 non sono sottospazi di R3 perche, come efacile osservare, non contengono il vettore nullo. Invece W1 = (0, 0, 0), W2 eW5 sono sottospazi di R3: per verificarlo si puo procedere come nel precedenteesercizio.

Esercizio 8.2.7. Il sottoinsieme W1 non e un sottospazio di Q3 infatti per esem-pio (0, 1,−1), (0, 1, 1) ∈ W1 mentre la loro somma (0, 1,−1) + (0, 1, 1) =(0, 1, 0) 6∈ W1. Ragionando come negli esercizi precedenti si puo poi osservareche W2,W3,W4 sono sottospazi di Q3.

Esercizio 8.2.8. Procedendo come negli esercizi precedenti e facile verificare checiascuno dei sottoinsiemi considerati e un sottospazio di Z4

7.

64 Capitolo 8

Esercizio 8.2.9. La matrice nulla e elemento di W pertanto W 6= Ø. Per provareche tale insieme e un sottospazio basta osservare che, per ogni h, k ∈ Q e per ogni(

0 αβ γ

),

(0 α1

β1 γ1

)∈W , si ha che

h

(0 αβ γ

)+ k

(0 α1

β1 γ1

)=(

0 hα+ kα1

hβ + kβ1 hγ + kγ1

)∈W.

Esercizio 8.2.10. Poiche per ogni i ∈ I il sottoinsiemeWi e un sottospazio di V siha che il vettore nullo 0 ∈Wi per ogni i ∈ I e questo comporta che 0 ∈

⋂i∈IWi

pertanto l’intersezione e non vuota.Per provare che

⋂i∈IWi e un sottospazio di V basta quindi notare che per

ogni α, β ∈ F e per ogni u, v ∈∈⋂i∈IWi si ha che αu+ βv ∈

⋂i∈IWi perche

u, v ∈ Wi per ogni i ∈ I e quindi, per ogni α, β ∈ F , e αu + βv ∈ Wi per ognii ∈ I .

Esercizio 8.2.11. Si noti che con x ∈ F \ 0 risulta 〈x〉 = αx : α ∈ Fe poiche per ogni y ∈ F e y = (yx−1)x ∈ 〈x〉 si ha che 〈x〉 = F . Questocomporta che x e un sistema di generatori dell’F -spazio vettoriale F . L’unicosottoinsieme proprio di x e Ø, ed essendo 〈Ø〉 = 0 ⊂ F , si ha che x e uninsieme di generatori minimale.

Per quanto riguarda Fn con n > 1, si noti che

〈e1, . . . , en〉 = x1e1 + · · ·+ xnen : x1, . . . , xn ∈ F= (x1, . . . , xn) : x1, . . . , xn ∈ F= Fn.

Questo comporta che e1, . . . , en e un sistema di generatori di Fn.SiaX ⊂ e1, . . . , en, allora esistem ∈ e1, . . . , en tale che em 6∈ X e non

e difficile osservare che per ogni (y1, . . . , yn) ∈ 〈X〉 si ha che ym = 0. Questocomporta che em 6∈ 〈X〉 e quindi 〈X〉 ⊂ Fn. Dunque e1, . . . , en e minimaletra i sistemi di generatori di Fn.

Esercizio 8.2.12. E immediato osservare che 〈1, x, . . . , xn〉 = F [x;n]; infatti

〈1, x, . . . , xn〉 = a0 + a1x+ · · ·+ anxn : a0, a1, . . . , an ∈ F

= f(x) ∈ F [x] : v(f(x)) ≤ n.

Sia X ⊂ 1, x, . . . , xn, allora esiste m ∈ 0, 1, . . . , n tale che xm 6∈ X .Pertanto 〈X〉 non contiene polinomi di gradom e questo comporta che xm 6∈ 〈X〉.

Esercizio 8.2.13. Si noti che〈V 〉 = 〈(2, 0, 0), (0,−3, 0)〉

= α(2, 0, 0) + β(0,−3, 0) : α, β ∈ R= (2α,−3β, 0) : α, β ∈ R.

Spazi vettoriali 65

Ovvero〈V 〉 = (x, y, 0) : x, y ∈ R

perche per ogni x, y ∈ R si ha che (x, y, 0) = (2α,−3β, 0) con α = x/2 eβ = −y/3.

In particolare, il vettore (5,−2, 0) ∈ 〈V 〉, infatti (5,−2, 0) = (2α,−3β, 0)con α = 5/2 e β = 2/3.

Esercizio 8.3.1. Per assurdo si supponga x+ y, x− y, x− 2y + z linearmentedipendente. Allora esistono α, β, γ ∈ F non tutti nulli tali che

α(x+y) +β(x−y) +γ(x−2y+z) = (α+β+γ)x+ (α−β−2γ)y+γz = 0.

Poiche pero x, y, z sono linearmente indipendenti, si ha che α + β + γ = 0, α −β − 2γ = 0, γ = 0. Queste ultime tre relazioni danno luogo ad un sistemaomogeneo nelle incognite α, β, γ che ammette una soluzione non banale il che ein contraddizione con il fatto che la sua matrice e non singolare.

Esercizio 8.3.8. Si osservi che con α, β ∈ R si ha che α(1, 0, 0) + β(2, 1, 0) =(0, 0, 0) se e solo se (α + 2β, β, 0) = (0, 0, 0) ovvero se e solo se α + 2β = 0 eβ = 0 e quindi se e solo se α = 0 = β. Questo comporta che A e linearmenteindipendente.

Si noti che gli scalari non nulli 2, 1 ∈ R sono tali che la combinazione lineare2(0, 2, 3) + 1(0,−4−, 6) = (0, 0, 0). Pertanto B e linearmente dipendente.

Analogamente si puo provare che C e linearmente dipendente e che D elinearmente indipendente.

Esercizio 8.3.9. A e una base di R2 infatti e linearmente indipendente massimale;B e linearmente dipendente, non e un sistema di generatori ne una base di R2; Ce linearmente indipendente massimale e quindi e una base di R2; D e un siste-ma di generatori di R2 ma non e una base (infatti avendo ordine maggiore delladimensione dello spazio e linearmente dipendente).

Esercizio 8.3.10. L’insieme (1, 0, 1, 0), (0, 1, 0, 0), (0, 0, 1, 1) e una base di Vche quindi ha dimensione 3. L’insieme (1, 0, 1, 0), (0, 2, 0, 1) e una base di Wche quindi ha dimensione 2.

Esercizio 8.3.11. Una base del sottospazio considerato e per esempio l’insieme(1, 1, 2, 3), (0,−1,−5,−9), (0, 0,−2,−4); quindi la dimensione e 3.

Esercizio 8.3.12. Una base e per esempio l’insieme costituito dai due polinomi−3 + x+ x2 e −5 + 6x+ x3 e quindi la dimensione e 2.

66 Capitolo 8

Esercizio 8.3.13. Sono basi di W1 gli insiemi:

(1, 0, 1), (0, 1, 9), (1, 0, 1), (1, 1, 10), (1, 10, 3), (0, 1, 9);

sono basi di W2 gli insiemi:

(1, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (0, 1, 0), (0, 0, 1),(1, 1, 1), (1, 0, 1), (0, 1, 1);

sono basi di W3 gli insiemi:

(1, 1, 0), (0, 1, 0), (0, 0, 1), (1, 0, 0), (0, 1, 0), (0, 0, 1),(1, 1, 1), (1, 1, 0), (1, 0, 0).

Esercizio 8.3.14. Le tre matrici considerate sono linearmente indipendenti ma noncostituiscono una base dello spazio vettoriale considerato perche quest’ultimo hadimensione 6.

Esercizio 8.3.15. E facile osservare che

〈B〉 = (−x+ y − z,−x− y,−x) : x, y, z ∈ R.

Per ogni a, b, c ∈ R il sistema−x+ y − z = a

−x− y = b

−x = c

nelle incognite x, y, z e di Cramer. Questo vuol dire che per ogni (a, b, c) ∈ R3

esistono e sono univocamente determinati i numeri reali x, y, z tali che (a, b, c) =(−x+ y − z,−x− y,−x) e quindi che B e una base di R3.

Le componenti di v in B sono (2,−3,−2), quelle di w sono (0,−1,−1).

Esercizio 8.4.3. L’applicazione gof : V1 → V3 e lineare: infatti consideraticomunque v, u ∈ V1 e α, β ∈ F si ha che (gof)(αv + βu) = g(f(αv + βu)) =g(αf(v) + βf(u)) = αg(f(v)) + βg(f(u)) = α(gof)(v) + β(gof)(u)

Esercizio 8.4.4. Siano x ∈ V1 e n ∈ Z; se n = 0 allora f(nx) = f(0x) = f(0) =0 per la 6.3.16; sia dunque n > 0 e si supponga f((n−1)x) = (n−1)f(x). Alloraf(nx) = f(x+(n−1)x) = f(x)+f((n−1)x) = f(x)+(n−1)f(x) = nf(x).Il principio di induzione assicura dunque l’asserto per ogni n ≥ 0.

Spazi vettoriali 67

Sia n < 0, allora nx = (−n)(−x) con −n > 0 e per quanto prima provatoe per la 6.3.16 si ha f(nx) = f((−n)(−x)) = (−n)f(−x) = (−n)(−f(x)) =nf(x).

Esercizio 8.4.5. Siano x, y ∈ V2 e α, β ∈ F ; allora f(f−1(αx + βy)) =idV2(αx + βy) = αx + βy = αf(f−1(x)) + βf(f−1(y)) = f(αf−1(x) +βf−1(y)) da cui, essendo f iniettiva, segue f−1(αx+βy) = αf−1(x)+βf−1(y).Quest’ultima uguaglianza assicura che f−1 e lineare.

Esercizio 8.4.6. L’applicazione f non e linerare, infatti f((0, 0)) = (1, 1) 6=(0, 0).

Esercizio 8.4.7. La prima applicazione considerata non e lineare, infatti per esem-pio f((0, 0, 0)) = (3, 0, 0) 6= (0, 0, 0). Anche la seconda non e lineare, infattif((0, 0, 1)) + f((1, 1, 1)) = (0,−1, 1) + (1, 0, 1) = (1,−1, 2) 6= (1,−1, 4) =f((1, 1, 2)) = f((0, 0, 1) + (1, 1, 1)). La terza ed ultima applicazione consideratae invece lineare: infatti f(α(a, b, c)+β(x, y, z)) = (2(αb+βy)−(αc+βz), αa+βx+ 4(αc+ βz), 0) = αf(a, b, c) + βf(x, y, z).

9Elementi di geometria analitica

Esercizio 9.2.1. Le componenti di un vettore direttore delle rette OA, OB e ABsono rispettivamente (−5, 7), (3, 2) e (8,−5).

Esercizio 9.2.2. Una coppia di giacitura di π1 e costituita dai vettori di compo-nenti (1, 2,−5) e (−2,−3, 2); una coppia di giacitura di π2 e costituita dai vettoridi componenti (0, 3,−2) e (1, 5,−7); una coppia di giacitura di π3 e costituita daivettori di componenti (0, 3,−2) e (−2, 0, 0).

Esercizio 9.2.3. Un vettore direttore di HK ha componenti (14,−2, 5).

Esercizio 9.3.3. Il piano per i punti A, B, C ha equazioni:x = 1 + α

y = 1 + α− 3βz = 5− 4α− 3β

e il punto D non appartiene ad esso perche il sistemaα = −3

α− 3β = 0−4α− 3β = −3

nelle incognite α, β non ammette soluzioni.Le rette AB e CD sono sghembe.

Esercizio 9.3.4. (i) Il piano π1 ha equazionix = 1− αy = 1 + 6βz = −α+ 9β.

70 Capitolo 9

Il piano π2 ha equazioni x = 3αy = 1 + α− 3βz = −1 + 2α.

(ii) Le rette considerate non sono complanari.

Esercizio 9.3.5. (i) Le rette considerate sono incidenti e quindi complanari. Lecoordinale del punto P0 comune alle due rette sono (−1,−2,−1) e il piano checontiene le due rette, ovvero il piano per P0 una cui coppia di giacitura e quelladei vettori direttori delle due rette, ha equazioni:

x = −1 + 2α+ β

y = −2 + α+ 4βz = −1 + 3α+ 3β.

(ii) Per provare che i punti considerati non sono allineati basta scrivere per esem-pio le equazioni parametriche della retta AB e osservare che non esistono valoridel parametro per i quali si ottengono le coordinate di C. Il piano π1 ha equazioni

x = 1 + 3α+ 8βy = α

z = 3− 2α+ 6β.

(iii) I piani π e π1 non sono paralleli.

Esercizio 9.3.6. Le rette considerate sono complanari incidenti. Le coordinate delpunto comune alle due rette sono (3, 4, 0), mentre le equazioni parametriche delpiano che contiene le due rette sono:

x = 3 + α+ β

y = 4 + 3α+ β

z = −α+ β.

Esercizio 9.3.7. (i) Le equazioni parametriche del piano π1 sono:x = 1 + α

y = 1 + 2βz = α+ 3β.

Le equazioni parametriche del piano π2 sono:x = 3αy = 1 + α

z = −1 + 2α+ 5β.

Elementi di geometria analitica 71

Le equazioni parametriche del piano π3 sono:x = 2α+ β

y = 1− 2α+ β

z = 2β.

(ii) Le rette considerate sono complanari incidenti e le coordinate del punto co-mune alle due rette sono (2, 4, 3).

Esercizio 9.3.8. (i) La retta r ha parametri direttori (−1, 0, 1) e la retta sh haparametri direttori (−1, h+ 2, 1). Dunque le due rette sono parallele se e solo seh+ 2 = 0 cioe se e solo se h = −2.(ii) Non esistono siffatti valori di h.

Esercizio 9.3.9. (i) Le equazioni parametriche di s sono:x = −1 + t

y = 1z = −2 + 3t.

(ii) Le equazioni parametriche di π sono:x = −1 + α+ β

y = 1 + β

z = −2 + 3α+ 2β.

(iii) Il punto Q1 appartiene sia alla retta s che al piano π.

Esercizio 9.3.10. Le equazioni parametriche di r sonox = 1− 2ty = 1 + 2tz = 2 + 3t.

Il punto Q non appartiene ad r.

Esercizio 9.3.11. Le due rette si intersecano nel punto P di coordinate (2/5, 9/5).

Esercizio 9.3.12. L’origine del riferimento, ossia il punto di coordinate (0, 0), eun punto di ra se e solo se esiste t ∈ R tale che t+ 2 = 0 = −1 +at, e cio accadese e solo se a = −1/2.

Esercizio 9.3.13. La retta r1 ha parametri direttori (1, 0) e la retta r2 ha parame-tri direttori (−1,−2). Poiche −2 + 1 = −1 6= 0 tali rette sono incidenti. Lecoordinate del punto di intersezione sono (3/2, 1).

72 Capitolo 9

Esercizio 9.3.14. Le due rette si intersecano se e solo se a = −1 e le coordinatedel punto di intersezione sono (−8,−1).

Esercizio 9.3.15. La retta r ha equazioni parametrichex = 3− 4ty = 2tz = 4− 6t,

e la retta r1 ha equazioni parametrichex = 2− 2t′

y = 2− 2t′

z = 5− 8t′.

Poiche il sistema 3− 4t = 2− 2t′

2t = 2− 2t′

4− 6t = 5− 8t′

e compatibile, tali rette sono incidenti e le coordinate del punto di incidenza sono(1, 1, 1).

Esercizio 9.3.16. Le due rette si intersecano per ogni a 6= 0 e le coordinate delpunto di intersezione sono (−1/2, 1, 3/2).

Esercizio 9.4.1. La retta AB ha equazione 13x + 8y − 107 = 0, la retta CD haequazione 45x + 7y + 41 = 0. Le due rette sono incidenti e le coordinate delpunto di intersezione sono (23435/3497, 5348/269).

Esercizio 9.4.2. La rettaAhC ha equazione cartesiana 13x+(h+6)y−45−14h =0, ed e parallela all’asse y se e solo se h = −6.

Esercizio 9.4.3. (i) Non esistono valori di h per i quali i tre punti sono allineati.(ii) L’equazione cartesiana del piano per A, B e C0 e x+ y − 2z − 2 = 0.

Esercizio 9.4.4. (i) I punti sono complanari se e solo se h = 4.(ii) Le equazioni cartesiane della retta AB sono

3x+ y − 3 = 0y + 3z − 6 = 0.


Le equazioni cartesiane della retta CDh sonox− y = 0

z + (h− 1)y − h+ 2 = 0.

Non esistono valori di h per i quali le due rette sono parallele.

Esercizio 9.4.5. L’equazione cartesiana del piano π e 14x+ 25y+ 8z = 0, quelledella retta r sono

3x+ 2y − 5 = 02y − 3z − 8 = 0.

Il piano e la retta sono incidenti e le coordinate del punto di incidenza sono(109/63,−2/21,−172/63).

Esercizio 9.4.6. La retta r ha equazioni cartesiane7x+ 8y = 05y + 7z = 0,

ed il piano π ha equazione cartesiana 29x + 26y − 10z − 75 = 0. Il piano e laretta sono paralleli.


Esercizio 9.4.8. (i) Le equazioni cartesiane di r sonox+ 2y − 5 = 0

7y − 3z − 23 = 0.

(ii) Le equazioni cartesiane di s sonox− 3z + 23 = 0

y + 1 = 0.

(iii) La retta r ha parametri direttori (6,−3, 9), la retta s ha parametri direttori(9, 0, 3) e, poiche la matrice che ha per righe tali vettori numerici ha rango 2, ledue rette non sono parallele. Il punto di intersezione ha coordinate (−1, 7, 0).

Esercizio 9.5.1. L’origine del riferimento non appartiene alla circonferenza con-siderata: infatti sostituendo le coordinate (0, 0) del punto O al posto di x e ynell’equazione si ottiene 17 6= 0.

74 Capitolo 9

Esercizio 9.5.2. L’equazione richiesta e x2 + y2 + 14x− 2y + 9 = 0.

Esercizio 9.5.3. Poiche il numero reale 49/4+144/4+9 = 229/4 e positivo, l’e-quazione considerata rappresenta una circonferenza, e precisamente quella il cuicentro ha coordinate (7/2,−6) e raggio

√229/2. La circonferenza considerata

interseca l’asse x nei punti di coordinale ((7−√

85)/2, 0) e ((7 +√

85)/2, 0) edinterseca l’asse delle y nei punti di coordinate (0,−6− 3

√5) e (0,−6 + 3

√5).

Esercizio 9.5.4. I punti di intersezione della circonferenza considerata con la rettaconsiderata sono due, e hanno coordinate ((−51−3

√209)/20, (−17−

√209)/20)

e ((−51 + 3√

209)/20, (−17 +√

209)/20).

Esercizio 9.5.5. Le circonferenze Γ e Γ0 hanno in comune i due punti di coordi-nate (3(5−

√93)/34, (−9− 5

√93)/34) e (3(5 +

√93)/34, (−9 + 5

√93)/34).

Esercizio 9.6.1. Le rette considerate sono ortogonali; infatti hanno parametridirettori (2, 3) e (−6, 4) rispettivamente, e si ha 2 · (−6) + 3 · 4 = −12 + 12 = 0.

Esercizio 9.6.2. La retta richiesta ha equazione bx− ay = 0.

Esercizio 9.6.3. Le rette r e rk hanno parametri direttori (3, 2,−5) e (k, 2− k, 0)rispettivamente. Dunque r e rk sono perpendicolari se e solo se 3k+2(2−k) = 0,cioe se e solo se k = −4. Poiche poi i vettori numerici (3, 2,−5) e (k, 2 − k, 0)sono linearmente indipendenti per ogni k ∈ R si ha che non esistono valori di kper cui le due rette sono parallele.

Esercizio 9.7.1. (i) Il punto P ha coordinate (−59/10, 7/5, 43/10).(ii) La retta OP non e ortogonale ad r ed ha equazioni parametriche

x = −59/10ty = 7/5tz = 43/10t.

(iii) L’equazione cartesiana di Γ e 50x2 + 50y2 + 100x− 2713 = 0.(iv) L’intersezione della circonferenza Γ con la retta s e costituita da due punti.


Esercizio 9.7.2. (i) La circonferenza Γa ha centro nel punto di coordinate (−a, 2)e raggio

√a2 − 3a+ 4.

(ii) L’origine del riferimento e un punto di Γa se e solo se a = 0.(iii) La circonferenza e tangente all’asse y se a = 4/3, non ha punti di interse-zione con tale retta se a > 4/3, mentre se a < 4/3 l’intersezione e costituita dadue punti.(iv) La retta in questione ha equazioni parametriche

x = −a− ty = 2 + 2t.

Esercizio 9.7.3. La circonferenza ha equazione 4x2 + 4y2 − 8kx+ 8(k − 2)y +4(k2+(k−2)2)−1 = 0, la retta ha equazione x+y−2 = 0. Retta e circonferenzahanno in comune due punti, un punto o nessun punto rispettivamente quando k >−1/8, k = −1/8, k < −1/8.

Esercizio 9.7.4. (i) I punti sono allineati se e solo se h = 11.(ii) Il piano ha equazioni parametriche:

x = 1− α− 3βy = −1 + 4α+ β

z = 2− 3α− 9β.

(iii) I piani considerati sono paralleli.

Esercizio 9.7.5. (i) Le rette sono parallele se e solo se k = 1.(ii) Le rette sono sghembe per ogni k ∈ R \ 1.(iii) Non esistono valori di k per i quali le rette sono incidenti.(iv) La retta e parallela al piano se k = 47.

Esercizio 9.7.6. (i) Le rette sono parallele se e solo se k = −2.(ii) Le rette sono sghembe per ogni k ∈ R \ −2.(iii) Non esistono valori di k per i quali le rette sono incidenti.(iv) La retta e parallela al piano se k = −11/2.

10Reticoli, grafi, alberi

Esercizio 10.1.1. Sia S un insieme, e si consideri l’insieme ordinato (P(S),⊆),dove P(S) e l’insieme delle parti di S e⊆ e la usuale relazione d’inclusione insie-mistica. Per ogni X,Y ∈ P(S) risulta X ∪ Y ∈ P(S); inoltre X,Y ⊆ X ∪ Y , edaX,Y ⊆ Z segueX∪Y ⊆ Z. PertantoX∪Y = supP(S)X,Y per la (2.4.4).Analogamente si prova che X ∩Y = infP(S)X,Y per la (2.4.3). In particolare(P(S),⊆) e un reticolo avente S come massimo e Ø come minimo. Siccome poil’unione e l’intersezione di due sottoinsiemi finiti di S sono ancora sottoinsiemifiniti di S, ne segue che i sottoinsiemi finiti di S costituiscono un sottoreticolo di(P(S),⊆). Se S e infinito tale sottoreticolo risulta evidentemente privo di massi-mo, perche dato un qualunque sottoinsieme finito X di S, e scelto un qualunqueelemento a ∈ S \X , il sottoinsieme finito X ∪ a contiene propriamente X .

L’insieme parzialmente ordinato (N0, |), dove | denota la relazione del “divi-de”, e un reticolo, in quanto per ogni x, y ∈ N0 dalle definizioni date segue subitoche supN0

x, y = mcm(x, y) e infN0x, y = MCD(x, y) (vedi 5.4). Siccome

per ogni a ∈ N0 si ha a|0 e 1|a, e chiaro che 0 = max N0, 1 = min N0. Fissaton ∈ N0, sia D∗(n) l’insieme dei divisori positivi di n. Con a, b ∈ D∗(n) ancoraper definizione risulta MCD(a, b) ∈ D∗(n) e mcm(a, b) ∈ D∗(n), quindi D∗(n)costituisce un sottoreticolo di (N0, |), avente n come massimo e 1 come minimo.

Sia G un gruppo, e si denoti con L(G) l’insieme dei sottogruppi di G. Deno-tata con ⊆ l’usuale inclusione, l’insieme ordinato (L(G),⊆) e un reticolo. Infattiper ogni H,K ∈ L(G) per definizione supL(G)H,K e il piu piccolo (rispettoall’inclusione) sottogruppo di G contenente H e K, dunque coincide con 〈H,K〉(vedi 6.3); analogamente infL(G)H,K e il piu grande (rispetto all’inclusione)sottogruppo di G contenuto in H e in K, dunque coincide con H ∩K (vedi 6.3).Tale reticolo ha G come massimo e 1 come minimo. Se il gruppo G e infinito,l’insieme dei sottogruppi finiti diG non e, in generale, un sottoreticolo diL(G), inquanto il sottogruppo generato da una parte finita di G puo ben risultare infinito.Invece l’insieme dei sottogruppi normali di G e sempre un sottoreticolo di L(G).Infatti utilizzando l’Esercizio 6.3.8 si verifica subito che l’intersezione di due sot-togruppi normali di G e a sua volta un sottogruppo normale di G, e che il sotto-gruppo generato da due sottogruppi normali di G e a sua volta normale in G. Perquest’ultima verifica si tenga presente che seH,K E G e x ∈ 〈H,K〉 allora risul-

78 Capitolo 10

ta x = x1x2 . . . xn con xi ∈ H ∪K per ogni i = 1, . . . , n. Allora per ogni g ∈ Grisulta g−1xg = (g−1x1g)(g−1x2g) . . . (g−1xng), e ciascun g−1xig ∈ H ∪ Kper la normalita in G di H e di K. Ne segue che g−1xg ∈ 〈H,K〉 per ognix ∈ 〈H,K〉 e per ogni g ∈ G, e cio equivale al fatto che 〈H,K〉 E G perl’Esercizio 6.3.8.

Sia S uno spazio vettoriale su un campo F , e si denoti con L l’insieme deisottospazi di S. Allora (L,⊆) e un reticolo. Infatti, per ogni H , K ∈ L, perdefinizione supLH,K e il piu piccolo (rispetto all’inclusione) sottospazio diS contenente H e K, dunque coincide con H + K (vedi 8.2.12); analogamenteinfLH,K e il piu grande (rispetto all’inclusione) sottospazio di S contenuto inH e in K, dunque coincide con H ∩ K. Tale reticolo ha S come massimo e ilsottospazio nullo 0 come minimo.

Esercizio 10.1.2. Risulta A = 1, 2, 5, 10, 25, 50. Il diagramma di Hasse delreticolo (A, |) e il seguente:

ss s

s ss

@@

@@

@@

1

2

10

5

50

25

Risulta infine (5 ∨ 2) ∧ 25 = 10 ∧ 25 = 5, (1 ∧ 2) ∨ 25 = 1 ∨ 25 = 25.

Esercizio 10.1.3. Risulta B = 1, 3, 9, 27, 81. Il diagramma di Hasse delreticolo (B, |) e il seguente:

ss

s

s

s

81

27

1

3

9

Risulta infine (9 ∨ 27) ∧ 3 = 27 ∧ 3 = 3, (1 ∧ 9) ∨ 81 = 1 ∨ 81 = 81.

Esercizio 10.1.4. Risulta C = 1, 3, 5, 11, 15, 33, 55, 165. Il diagramma diHasse del reticolo (C, |) e il seguente:

Reticoli, grafi, alberi 79

ss s ss s s

s

@@

@@

@@@

@

@@@

@

@@

@@

1

15

3 5

33

11

55

165

Risulta infine (55 ∨ 5) ∧ 11 = 55 ∧ 11 = 11, (5 ∧ 11) ∨ 33 = 1 ∨ 33 = 33.

Esercizio 10.1.5. Si ha 1573 = 11 · 11 · 13, e D = 1, 11, 13, 121, 143, 1573. Ildiagramma di Hasse del reticolo (D, |) e il seguente:

ss s

s ss

@@

@@

@@

1

13

143

11

1573

121

Risulta infine (143∨121)∧13 = 1573∧13 = 13, (143∧11)∨13 = 11∨13 = 143.


Esercizio 10.1.7. Sia a un elemento minimale del reticolo (L,≤). Per ogni x ∈ Lrisulta a ∧ x ≤ a, quindi a = a ∧ x per la minimalita di a, e da 10.1.3 seguex ≤ a. Pertanto a e il minimo di L. L’unicita del minimo prova allora l’unicita dia come elemento minimale in L.

Esercizio 10.1.8. La relazione v e banalmente riflessiva, essendo a = a e quindia v a per ogni a ∈ N0. Con a, b ∈ N0 si abbia a v b e b v a. Se fosse a 6= bdovrebbe aversi 2a < b e 2b < a, quindi 2a < b ≤ 2b < a, assurdo. Pertantoa = b e la relazione e asimmetrica. Infine, con a, b, c ∈ N0 si abbia a v b e b v c.Se b = c oppure b = a si ottiene subito a v c. Ovviamente cio vale anche sea = c. Si puo dunque assumere che a, b e c siano a due a due distinti. Allora si ha2a < b e 2b < c, da cui 2a < c e di nuovo a v c. Cio prova che la relazione v etransitiva, pertanto essa e una relazione d’ordine.

In (N0,v) i minoranti dell’insieme 5, 6 sono 0, 1 e 2; siccome pero l’in-sieme 0, 1, 2 e privo di massimo in (N0,v) (in quanto 1 e 2 non sono confron-tabili), non esiste infN0

5, 6. Quindi (N0,v) non e un reticolo.

80 Capitolo 10

Esercizio 10.1.9. (i) La relazione v e banalmente riflessiva, in quanto a = a equindi a v a per ogni a ∈ V . Con a = 5h + 1, b = 5k + 1 ∈ V , si abbia a v be b v a. Se fosse a 6= b si avrebbe |a| < |b| e |b| < |a|, una contraddizione.Pertanto a = b e la relazione e asimmetrica. Infine con a = 5h + 1, b = 5k + 1,c = 5l + 1 ∈ V , si abbia a v b e b v c. Se b = c oppure b = a si ottiene subitoa v c. Ovviamente cio vale anche se a = c. Si puo dunque assumere che a, be c siano a due a due distinti. Allora si ha |h| < |k| e |k| < |l|, da cui |h| < |l|e di nuovo a v c. Cio prova che la relazione v e transitiva, pertanto essa e unarelazione d’ordine.(ii) In (V,v) i minoranti dell’insieme 11,−9 sono 1, 6 e −4; siccome perol’insieme 1, 6,−4 e privo di massimo in (V,v) (in quanto 6 e −4 non sonoconfrontabili), non esiste infV 11,−9. Quindi (V,v) non e un reticolo.(iii) Si ha: −19 = 5(−4) + 1, −14 = 5(−3) + 1, −9 = 5(−2) + 1, −4 =5(−1)+1, 1 = 5 ·0+1, 6 = 5 ·1+1, 11 = 5 ·2+1, 16 = 5 ·3+1, 21 = 5 ·4+1.Pertanto il diagramma di Hasse di (W,v) e il seguente:

ss ss ss ss s

@@

HHH

HHH

HH HHHH

1

−4 6

−9 11

−14 16

−19 21

Esercizio 10.1.10. Sia X un sottoinsieme finito di un reticolo L (non necessaria-mente finito). Si ragioni per induzione su |X|. Se |X| ≤ 2, esistono certamentesupLX e infLX , in quanto L e un reticolo. Si assuma ora |X| = n > 2, ed esistasupLX = s ∈ L per ipotesi induttiva. Si consideri poi un elemento a ∈ L \X ,e si ponga Y = X ∪ a. L’elemento s ∨ a ∈ L, che certamente esiste in quantoL e un reticolo, risulta un maggiorante di X essendo s = supLX . Inoltre ov-viamente a ≤ s ∨ a, pertanto s ∨ a e un maggiorante di Y . Sia ora m ∈ L unmaggiorante di Y . Allora x ≤ m per ogni x ∈ X , quindi s ≤ m per la (2.4.4).Inoltre a ∈ Y , quindi a ≤ m. Pertanto s ∨ a ≤ m ancora per la (2.4.4). Cosırisulta s ∨ a = supL Y . Il principio di induzione (vedi 1.3.1) assicura allora chesupLX esiste per ogni sottoinsieme finito X di L. Con un analogo ragionamentoinduttivo si dimostra che infLX esiste per ogni sottoinsieme finito X di L.

Ovviamente, se L e finito, ogni sottoinsieme di L lo e; cosı quanto appenaprovato dimostra l’asserto.

Esercizio 10.1.11. Sia S un insieme, e si consideri il reticolo (P(S),⊆), doveP(S) e l’insieme delle parti di S e ⊆ e la usuale relazione d’inclusione insiemi-stica. Siccome per ogni X,Y ∈ P(S) risulta X ∨Y = X ∪Y e X ∧Y = X ∩Y ,si vede facilmente che per ogni sottoinsieme Ω ∈ P(S) risulta

supP(S)Ω =⋃Xi∈Ω

Xi ∈ P(S), infP(S)Ω =⋂Xi∈Ω

Xi ∈ P(S),


quindi (P(S),⊆) e completo.Si denoti ora con F il sottoreticolo costituito dai sottoinsiemi finiti di S. Se S

e finito allora F = P(S) risulta completo per quanto appena dimostrato (oppureanche per l’Esercizio 10.1.10, essendo in tal caso F un reticolo finito). Se inveceS e infinito alloraF non e completo, in quanto l’unione di tutti i sottoinsiemi finitidi S coincide con S e dunque non e un elemento di F .

Esercizio 10.1.12. Per quanto provato nella prima parte dell’Esercizio 10.1.10,bastera provare che esistono supN0

X e infN0X per ogni sottoinsieme infinito X

di N0. Sia X un tale sottoinsieme.Essendo il massimo di (N0, |), l’elemento 0 e certamente un maggiorante di

X . Inoltre esso e l’unico maggiorante di X , in quanto un maggiorante di X deveessere multiplo delle infinite potenze di primi positivi che dividono gli elementidi X . Pertanto 0 = supN0

X .Un minorante di X e un elemento di N0 che divide ogni elemento di X .

L’insieme Y dei minoranti di X e certamente non vuoto, in quanto contiene l’e-lemento 1. Inoltre Y e finito, in quanto ogni numero naturale ha solo un numerofinito di divisori. Per quanto provato nella prima parte dell’Esercizio 10.1.10, esi-ste supN0

Y . Si denoti con s tale elemento di N0. Siccome ogni elemento di Ydivide ciascun elemento x ∈ X , ogni x ∈ X e maggiorante di Y in N0, pertantos|x per la (2.4.4). Cio prova che s ∈ Y , quindi s = maxY , da cui s = infN0

X .

Esercizio 10.1.13. Sia G un gruppo, e sia L(G) il reticolo dei sottogruppi diG. Sia Ω un insieme non vuoto di sottogruppi di G. Come osservato nel testo apag. 222 (subito dopo 6.3.10), l’intersezione degli elementi di Ω e un sottogruppodi G. Quindi risulta supL(G) Ω = 〈H : H ∈ Ω〉 e infL(G) Ω = ∪H∈ΩH , e L(G)e completo.

Sia ora N(G) il reticolo dei sottogruppi normali di G. Ragionando comenell’Esercizio 10.1.1 si puo provare che l’intersezione di un insieme non vuotodi sottogruppi normali di G e ancora un sottogruppo normale di G, e che il sot-togruppo generato da sottogruppi normali di G e normale in G. Pertanto ancheN(G) e completo.

Esercizio 10.1.14. Sia S uno spazio vettoriale su un campo F , e si denoti con Lil reticolo dei sottospazi di S. La 8.2.8 assicura che l’intersezione di un insiemenon vuoto di sottospazi di S e un sottospazio di S, il reticolo L risulta completo.Inoltre banalmente il sottospazio generato da sottospazi di S e un sottospazio diS. Pertanto L e completo.

Esercizio 10.1.15. Sia L il reticolo dei sottospazi di uno spazio vettoriale S suun campo F , E sia L∗ l’insieme dei sottospazi di S di dimensione finita su F . SeW1,W2 ∈ L∗, la formula di Grassmann (vedi 8.5.1) assicura che W1 +W2 ∈ L∗e W1 ∩W2 ∈ L∗, pertanto L∗ e un sottoreticolo di L. Se S ha dimensione finitasu F allora 8.2.23 garantisce che L = L∗, quindi L∗ e completo per l’esercizioprecedente. Se invece S ha dimensione infinita su F , scelta una qualunque base

82 Capitolo 10

B = bi : i ∈ I di S, si considerino i sottospazi Bi = 〈bi〉, con i ∈ I . Ovvia-mente per ogni i ∈ I risulta dimF Bi = 1, quindi Bi ∈ L∗. Pero il sottospazio〈Bi : i ∈ I〉 = S /∈ L∗, quindi L∗ non e completo.

Esercizio 10.1.16. Sia L un reticolo completo. Allora esistono m1 = supL L edm2 = infL L, ed ovviamente risulta m1 = maxL e m2 = minL.


Esercizio 10.1.18. Sia X un sottoinsieme non vuoto di L. Allora 0 = minLe un minorante di X , quindi l’insieme Y dei minoranti di X e non vuoto. Peripotesi, esiste y1 = supL Y . Per ogni x ∈ X e y ∈ Y risulta y ≤ x, quindi ognielemento di X e un maggiorante di Y . Pertanto per la (2.4.4) risulta y1 ≤ x perogni x ∈ X . Cio significa che y1 ∈ Y , quindi y1 = minY . Per definizione alloray1 = infLX . Ne segue che L e un reticolo completo.

Esercizio 10.1.19. Siccome b ∨ d e un maggiorante di b, d, da a ≤ b e c ≤ dsegue che a ≤ b ≤ b∨d e c ≤ d ≤ b∨d. Quindi b∨d e un maggiorante di a, c,pertanto a ∨ c ≤ b ∨ d per la (2.4.4). Siccome l’enunciato

P : a ≤ b , c ≤ d =⇒ a ∨ c ≤ b ∨ d (∀a, b, c, d ∈ L)

e valido per ogni reticoloL, il principio di dualita dei reticoli (vedi 10.1.2) assicurache e valido per ogni reticolo L anche l’enunciato duale

P∗ : a ≥ b , c ≥ d =⇒ a ∧ c ≥ b ∧ d (∀a, b, c, d ∈ L).

Esercizio 10.2.1. Sia f : L −→M un’applicazione tra i reticoli (L ≤) e (M,v).Se f e un isomorfismo di reticoli allora per la 10.2.1 f ed f−1 sono applicazionicrescenti, quindi f e un isomorfismo di insiemi ordinati.

Viceversa, sia ora f un isomorfismo di insiemi ordinati. Per ogni a, b ∈ L,da a ≤ a ∨ b e b ≤ a ∨ b segue f(a) v f(a ∨ b) e f(b) v f(a ∨ b), quindif(a ∨ b) e un maggiorante in M di f(a), f(b). Se f(c) ∈M e un maggiorantedi f(a), f(b), allora a ≤ c e b ≤ c, da cui a ∨ b ≤ c e f(a ∨ b) v f(c).Per la (2.4.4) risulta allora f(a ∨ b) = f(a) ∨ f(b). Analogamente si prova chef(a ∧ b) = f(a) ∧ f(b). Pertanto f e un isomorfismo di reticoli.

Esercizio 10.2.2. Sia f : L −→M un isomorfismo tra i reticoli (L ≤) e (M,v).Per l’esercizio precedente f e un isomorfismo di insiemi ordinati, quindi a ≤ b inL se e solo se f(a) v f(b) in M . Cio comporta che i diagrammi di Hasse di L eM = f(a) : a ∈ L sono identici.


Esercizio 10.2.3. ConA,B ∈ P(S), daA ⊆ B segue ovviamente f(A) ≤ f(B),quindi f e un omomorfismo di insiemi ordinati. Risulta pero 1, 2 ∨ 2, 3 =1, 2, 3, ma f(1, 2) ∨ f(2, 3) = 3 ∨ 5 = 5 6= 6 = f(1, 2, 3), pertanto fnon e un omomorfismo di reticoli.

Esercizio 10.3.1. Basta applicare la proprieta distributiva dell’unione rispettoall’intersezione oppure dell’intersezione rispetto all’unione (vedi 1.4.6).

Esercizio 10.3.2. Si osservi innanzitutto che con α, β, γ ∈ N0 risulta sempre

maxα,minβ, γ = minmaxα, β, maxα, γ.Se infatti α ≤ β e α ≤ γ allora entrambi i termini della precedente espressionevalgono minβ, γ; altrimenti valgono entrambi α.

Si osservi poi che con a, b ∈ N0, posto a = pα11 . . . pαs

s e b = pβ11 . . . pβs

s , dovep1, . . . , ps sono primi positivi e αi, βi ∈ N0 per ogni i = 1, . . . , s, nel reticolo deinaturali risulta ovviamente

a ∧ b = MCD(a, b) = pminα1,β11 . . . pminαs,βs

s ,

a ∨ b = mcm(a, b) = pmaxα1,β11 . . . pmaxαs,βs

s .

Siano ora a, b, c ∈ N0, e si ponga

a = pα11 . . . pαs

s , b = pβ11 . . . pβs

s , c = pγ11 . . . pγss ,

dove p1, . . . , ps sono primi positivi e αi, βi, γi ∈ N0 per ogni i = 1, . . . , s. Allora

a ∨ (b ∧ c) = a ∨ (pminβ1,γ11 . . . pminβs,γs

s )

= pmaxα1,minβ1,γ11 . . . pmaxαs,minβs,γs

s

= pminmaxα1,β1,maxα1,γ11 . . . pminmaxαs,βs,maxαs,γs

s

= pmaxα1,β11 . . . pmaxαs,βs

s ∧ pmaxα1,γ11 . . . pmaxαs,γs

s

= (a ∨ b) ∧ (a ∨ c).

Cio prova che il reticolo dei naturali e distributivo.

Esercizio 10.3.3. Il reticolo dei sottospazi di uno spazio vettoriale di dimensione0 oppure 1 ha ordine rispettivamente 1 oppure 2, quindi e banalmente distributivo.

Sia ora S uno spazio vettoriale di dimensione ≥ 2 su un campo F . Conside-rati due vettori linearmente indipendenti a, b ∈ S, i sottospazi A = 〈a〉, B = 〈b〉,C = 〈a + b〉 sono a due a due distinti ed hanno dimensione 1. Si verifica poiimmediatamente che A⊕B = A⊕C = B ⊕C. Quindi il reticolo dei sottospazidi S contiene il sottoreticolo trirettangolo

84 Capitolo 10

ssss s

@@

@@

0

B

A⊕B

A C

e pertanto non e distributivo per 10.3.4.


Esercizio 10.3.5. Siano x, y, z ∈ L con x ≤ z. Essendo y ∧ z ≤ y ≤ x ∨ y ey ∧ z ≤ z risulta y ∧ z ≤ (x ∨ y) ∧ z per (2.4.3). Del resto da x ≤ x ∨ y e x ≤ zsegue x ≤ (x ∨ y) ∧ z ancora per (2.4.3). Dunque x ∨ (y ∧ z) ≤ (x ∨ y) ∧ z per(2.4.4).








Esercizio 10.6.1. Il grafo considerato puo essere disegnato come segue:


sss ss s

@@

@@

a

d

fe

b c

Essendo costituito da 2 componenti connesse, Γ non e connesso. Il vertice b hagrado 3, il vertice a ha grado 2 mentre c, e ed f hanno grado 1. Il vertice d hagrado 0 e quindi e un punto isolato.

Esercizio 10.6.2. Il grafo considerato puo essere disegnato come segue:

s ss s s sss

@@

@@

1 5

2 3 4 6 7 8

Le sue componenti connesse sono [1] = 1, 2, 3, 4 e [5] = 5, 6, 7, 8. Il grafoΓ e una foresta ma non un albero.

Esercizio 10.6.3. Il multigrafo Υ puo essere disegnato come segue:

•b•a •d

•e

•c

l2

l1

l4l3

l6

l5

l8 l7

Esso e connesso e tutti i suoi vertici sono pari; pertanto, in virtu del Teorema10.6.4, Υ possiede un circuito euleriano.

Esercizio 10.6.4. Per assurdo si suppongano Γ1 e Γ2 isomorfi e sia f : V1 → V2

un isomorfismo. Il vertice a di Γ1 ha grado 3 essendo a, b, a, c e a, d latiincidenti in a, dunque anche f(a) ha grado 3 perche f(a), f(b), f(a), f(c)e f(a), f(d) sono lati incidenti in f(a); ma questo e in contraddizione con ilfatto che tutti i vertici di Γ2 hanno grado 2.

Esercizio 10.6.5. E facile osservare che le applicazioni f : V1 → V2 che scambiaa e b e fissa ogni altro elemento di V1 e g : V2 → V3 che scambia a con c e b cond sono isomorfismi di grafi.

86 Capitolo 10

Esercizio 10.6.6. Non esiste un tale grafo. Infatti se un tale grafo esistesse lasomma dei gradi dei suoi vertici sarebbe 35 e quindi dispari, in contraddizionecon quanto osservato subito dopo 10.6.3.

Esercizio 10.6.7. Il sottografo richiesto e Γ1 = (V1, E1) con E1 = 3, 5.

Esercizio 10.7.1. A meno di isomorfismi esistono esattamente un albero di ordine3 e due alberi di ordine 4. Tali alberi possono essere schematizzati come segue:

s ss ss ss s sss

@@

Esercizio 10.7.2. A meno di isomorfismi esistono esattamente tre alberi di ordi-ne 5:

s ssss

@@DDDDDD

s ssss

@@DDDDDD

s ssss

@@

Esercizio 10.7.3. Γ e connesso ma non e un albero perche possiede per esem-pio il circuito a, b, b, c, a, c. Per avere un albero di supporto si puo peresempio considerare (V,E′) con E′ = a, e, a, b, b, c, c, d, d, f.

Esercizio 10.7.4. Γ e un grafo di ordine 10 connesso con 9 lati, pertanto, per la10.7.3, e un albero. Le fogli sono 3, 8 e 10.

Esercizio 10.7.5. Un tale grafo ha esattamente 7 lati.

Esercizio 10.8.1. (i) Ovviamente 2a3b v 2a3b essendo a ≤ a e b ≤ b, quindi ve riflessiva. Da 2a3b v 2c3d e 2c3d v 2a3b segue a ≤ c, b ≤ d, c ≤ a e d ≤ b,quindi a = c e b = d, cioe 2a3b = 2c3d, ev e asimmetrica. Infine da 2a3b v 2c3de 2c3d v 2e3f segue a ≤ c, b ≤ d, c ≤ e e d ≤ f , quindi a ≤ e e b ≤ f , cioe2a3b v 2e3f , e v e transitiva. Pertanto v e una relazione d’ordine.(ii) L’insieme ordinato (L,v) non e totalmente ordinato, in quanto per esempio2 = 2130 e 3 = 2031 non sono confrontabili. Di conseguenza, per 2.4.12, (L,v)


non e ben ordinato. L’unico elemento minimale in (L,v) e 1 = 2030; risultaanche 1 = minL. E poi evidente che in (L,v) non ci sono elementi massimali,quindi non esiste maxL.(iii) Per ogni 2a3b, 2c3d ∈ L risulta supL2a3b, 2c3d = 2maxa,c3maxb,d,infL2a3b, 2c3d = 2mina,c3minb,d. Pertanto (L,v) e un reticolo.(iv) Per ogni 2a3b, 2c3d, 2e3f ∈ L, tenendo presente quanto provato all’iniziodello svolgimento dell’Esercizio 10.3.2, risulta

2a3b ∨ (2c3d ∧ 2e3f ) = 2a3b ∨ 2minc,e3mind,f

= 2maxa,minc,e3maxb,mind,f

= 2minmaxa,c,maxa,e3minmaxb,d,maxb,f

= 2maxa,c3maxb,d ∧ 2maxa,e3maxb,f

= (2a3b ∨ 2c3d) ∧ (2a3b ∨ 2e3f ),

e cio prova che L e distributivo.(v) Tenendo presente quanto provato nel punto (iii) risulta:

4 ∧ 6 = 2230 ∧ 2131 = 2130 = 2,

12 ∧ 18 = 2231 ∧ 2132 = 2131 = 6,

4 ∨ 6 = 2230 ∨ 2131 = 2231 = 12,

6 ∨ 9 = 2131 ∨ 2032 = 2132 = 18.

(vi) Per ogni 2a3b, 2c3d ∈ L da 2a3b v 2c3d segue h(2a3b) = a + b ≤ c + d =h(2c3d), quindi h e un omomorfismo tra gli insiemi ordinati (L,v) e (N0,≤).(vii) Risulta h(2130) = 1 = h(2031), 2130 ∨ 2031 = 2131, h(2130 ∨ 2031) =h(2131) = 2 6= 1 = 1∨1 = h(2130)∨h(2031). Quindi h non e un omomorfismotra i reticoli (L,v) e (N0,≤).(viii) Il diagramma di Hasse di (F,v) e il seguente:

s ss s ss s s sAAAA

AAAA

AAAA

AA

2 3

6

12 18 27

4 9

16

E poi evidente che (F,v) non e un sottoreticolo di (L,v): per esempio 2 ∧ 3 =1 /∈ F .

Esercizio 10.8.2. (i) Ovviamente 2a3b v 2a3b essendo a ≤ a e b|b, quindi v eriflessiva. Da 2a3b v 2c3d e 2c3d v 2a3b segue a ≤ c, b|d, c ≤ a e d|b, quindia = c e b = d, cioe 2a3b = 2c3d, e v e asimmetrica. Infine da 2a3b v 2c3d e

88 Capitolo 10

2c3d v 2e3f segue a ≤ c, b|d, c ≤ e e d|f , quindi a ≤ e e b|f , cioe 2a3b v 2e3f ,e v e transitiva. Pertanto v e una relazione d’ordine.(ii) L’insieme ordinato (L,v) non e totalmente ordinato, in quanto per esempio9 = 2032 e 27 = 2033 non sono confrontabili. Di conseguenza, per 2.4.12, (L,v)non e ben ordinato. L’unico elemento minimale in (L,v) e 3 = 2031; risultaanche 3 = minL. E poi evidente che in (L,v) non ci sono elementi massimali,quindi non esiste maxL.(iii) Per ogni 2a3b, 2c3d ∈ L risulta supL2a3b, 2c3d = 2maxa,c3mcm(b,d),infL2a3b, 2c3d = 2mina,c3MCD(b,d). Pertanto (L,v) e un reticolo.(iv) Si osservi innanzitutto che, come provato nell’Esercizio 10.3.2, per ogni b, d,f ∈ N0 risulta

mcm(b,MCD(d, f)) = MCD(mcm(b, d),mcm(b, f)).

Per ogni 2a3b, 2c3d, 2e3f ∈ L, tenendo presente anche quanto provato all’iniziodello svolgimento dell’Esercizio 10.3.2, risulta

2a3b ∨ (2c3d ∧ 2e3f ) = 2a3b ∨ 2minc,e3MCD(d,f)

= 2maxa,minc,e3mcm(b,MCD(d,f))

= 2minmaxa,c,maxa,e3MCD(mcm(b,d),mcm(b,f))

= 2maxa,c3mcm(b,d) ∧ 2maxa,e3mcm(b,f)

= (2a3b ∨ 2c3d) ∧ (2a3b ∨ 2e3f ),

e cio prova che L e distributivo.(v) Tenendo presente quanto provato nel punto (iii) risulta:

4 ∧ 6 = 2230 ∧ 2131 = 2131 = 6,

12 ∧ 18 = 2231 ∧ 2132 = 2131 = 6,

4 ∨ 6 = 2230 ∨ 2131 = 2230 = 4,

6 ∨ 9 = 2131 ∨ 2032 = 2132 = 18.

(vi) Per ogni 2a3b, 2c3d ∈ L, da σ(2a3b) = σ(2c3d) segue immediatamente a =c, b = d, dunque 2a3b = 2c3d, e σ e iniettiva. e poi evidente che σ non e suriettiva:per esempio, non esiste alcun elemento 2a3b ∈ L tale che σ(2a3b) = 1, 3.(vii) Con 2a3b, 2c3d ∈ L sia 2a3b v 2c3d. Se b = 0 allora necessariamente d = 0e a ≤ c, quindi σ(2a3b) ⊆ σ(2c3d); se invece b 6= 0 allora a ≤ c e b|d, quindib ≤ d, da cui ancora σ(2a3b) ⊆ σ(2c3d). Pertanto h e un omomorfismo tra gliinsiemi ordinati (L,v) e (P(N),⊆).(viii) Risulta per esempio σ(6) = σ(2131) = 2, σ(12) = σ(2231) = 3,e σ(6 ∨ 12) = σ(12) = 3 6= 2, 3 = σ(6) ∨ σ(12). Quindi σ non e unomomorfismo tra i reticoli (L,v) e (P(N),⊆).(ix) Il diagramma di Hasse di (F,v) e il seguente:


ss s ss s sss

@@

3

9

182

4

16

6 27

12

E poi evidente che (F,v) non e un sottoreticolo di (L,v): per esempio 9 ∨ 27 =2036 = 729 /∈ F .

Esercizio 10.8.3. (i) Ovviamente 3n + 1 v 3n + 1 poiche n|n, quindi v eriflessiva. Da 3n + 1 v 3m + 1 e 3m + 1 v 3n + 1 segue n|m e m|n, quindin = m e 3n+ 1 = 3m+ 1, per cui v e asimmetrica. Infine da 3n+ 1 v 3m+ 1e 3m + 1 v 3r + 1 segue n|m e m|r, quindi n|r e 3n + 1 v 3r + 1, cioe v etransitiva. Pertanto v e una relazione d’ordine.(ii) L’insieme ordinato (L,v) non e totalmente ordinato, in quanto per esempio7 = 3 · 2 + 1 e 10 = 3 · 3 + 1 non sono confrontabili. Di conseguenza, per 2.4.12,(L,v) non e ben ordinato.(iii) Per ogni 3n+ 1, 3m+ 1 ∈ L risulta:

supL3n+ 1, 3m+ 1 = 3(mcm(n,m)) + 1,infL3n+ 1, 3m+ 1 = 3(MCD(n,m)) + 1.

Pertanto (L,v) e un reticolo.(iv) L’applicazione f e banalmente biettiva. Inoltre per ogni 3n+ 1, 3m+ 1 ∈ Lrisulta:

f(3n+ 1 ∨ 3m+ 1) = f(3(mcm(n,m)) + 1)= mcm(n,m)= f(3n+ 1) ∨ f(3m+ 1),

f(3n+ 1 ∧ 3m+ 1) = f(3(MCD(n,m)) + 1)= MCD(n,m)= f(3n+ 1) ∧ f(3m+ 1),

quindi f e un isomorfismo tra i reticoli (L,v) e (N0, |).(v) Risulta minL = 1 · 3 + 1 = 4, maxL = 0 · 3 + 1 = 1.(vi) Essendo 7 = 2·3+1, 10 = 3·3+1, 13 = 4·3+1, 19 = 6·3+1, 37 = 12·3+1il diagramma di Hasse di F e il seguente:

s ss ss

@@

@@

107

13

37

19

90 Capitolo 10

(vii) F non e un sottoreticolo di L: per esempio, 7 ∧ 10 = 4 /∈ F .

Esercizio 10.8.4. (i) Ovviamente 5a v 5a poiche a|a, quindi v e riflessiva.Da 5a v 5b e 5b v 5a segue a|b e b|a, quindi a = b e 5a = 5b, per cui v easimmetrica. Infine da 5a v 5b e 5b v 5c segue a|b e b|c, quindi a|c e 5a v 5c,cioe v e transitiva. Pertanto v e una relazione d’ordine.(ii) L’insieme ordinato (5N0,v) non e totalmente ordinato, in quanto per esempio10 = 5·2 e 15 = 5·3 non sono confrontabili. Di conseguenza, per 2.4.12, (5N0,v)non e ben ordinato. Risulta min 5N0 = 5, max 5N0 = 0.(iii) Per ogni 5a, 5b ∈ 5N0 risulta:

sup5N05a, 5b = 5(mcm(a, b)),

inf5N05a, 5b = 5(MCD(a, b)).

Pertanto (5N0,v) e un reticolo.(iv) Si ha 15 ∨ 25 = (5 · 3) ∨ (5 · 5) = 5 ·mcm(3, 5) = 75.(v) Con 5a, 5b ∈ 5N0, risulta ω(5a ∨ 5b) = ω(5 · mcm(a, b)) = mcm(a, b) eω(5a ∧ 5b) = ω(5 ·MCD(a, b)) = MCD(a, b), quindi ω e un omomorfismo tra ireticoli (5N0,v) e (N0, |).(vi) Risulta 5 · 1 v 5 · 0, ma σ(5 · 1) = 1 > 0 = σ(5 · 0) quindi σ non e unomomorfismo tra gli insiemi ordinati (5N0,v) e (N0,≤).(vii) Risulta σ((5 · 0) ∨ (5 · 1)) = σ(0) = 0, ma σ(5 · 0) ∨ σ(5 · 1) = 0 ∨ 1 = 1,quindi σ non e un omomorfismo tra i reticoli (5N0,v) e (N0,≤). Si osservi cheil risultato segue anche direttamente dalla (iv) di 10.2.1 e da quanto provato alpunto precedente.(viii) Il diagramma di Hasse di H e il seguente:

s ss ss s

152510

150

5020

(ix) H non e un sottoreticolo di 5N0: per esempio, 10 ∧ 15 = 5 /∈ H .(x) In (H,v) l’unico maggiorante dell’insieme 15, 25 e 150, quindi risultasupH15, 25 = 150.(xi) Gli elementi minimali in (H,v) sono 10, 15 e 25; pertanto non esiste minH .(xii) Gli elementi massimali in (H,v) sono 20 e 150; pertanto non esiste maxH .

Esercizio 10.8.5. Per ogni X,Y ∈ V con X 6= Y si ha che X ∪ Y ∈ V eL = l1, l2 con l1 = X,X ∪ Y e l2 = X ∪ Y, Y e un cammino da Xa Y . Dunque Γ e connesso. Un circuito e per esempio ∅, a, a, a, c,c, a, c,∅, c. Un albero di supporto e Γ1 = (V,E1) dove l’insieme E1

e costituito dai lati ∅, a, ∅, c, ∅, b, a, a, b, b, b, c,c, a, c, S, b, c. Per il Corollario 10.6.5 il multigrafo considerato non


possiede cammini euleriani: infatti ciascuno dei suoi vertici ha grado 3 ed e quindidispari.

Esercizio 10.8.6. Si puo per esempio considerare il multigrafo (V,E, ψ) con V =1, 2, 3, 4, 5, 6, 7, 8, 9, 10, E = li : i ∈ N, 1 ≤ i ≤ 21 e ψ : E → [V ]2 taleche ψ(l1) = 1, 2 = ψ(l9), ψ(l2) = 2, 3 = ψ(l10), ψ(l3) = 3, 4 = ψ(l11),ψ(l4) = 4, 5 = ψ(l12), ψ(l5) = 5, 6 = ψ(l13), ψ(l6) = 6, 7 = ψ(l14),ψ(l7) = 7, 8 = ψ(l15), ψ(l8) = 8, 9 = ψ(l16), ψ(l17) = 1, 10, ψ(l18) =2, 10, ψ(l19) = 3, 10, ψ(l20) = 4, 10, ψ(l21) = 9, 10:

•1

•2

•3

•4 •5 •6 •7

•8

•9

•10

l9l1

l10l2

l11l3

l12

l4

l13

l5

l14

l6

l15 l7

l16 l8

l17

l18

TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTl19

JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ

l20

????

????

????

????

????

????

????

????

????

????

????

?

l21

Tale grafo e del tipo richiesto: infatti e connesso e privo di punti isolati, ed avendo6 vertici dispari (precisamente: 1, 2, 3, 4, 9, 10) non possiede cammini eulerianiper il Corollario 10.6.5.

ACenni di logica proposizionale e predicativa

Esercizio A.1. Posto P = A ∨ (B ∧C), Q = (A ∨B) ∧ (A ∨C), la prima formaenunciativa considerata ha la seguente tavola di verita:

A B C B ∧ C P A ∨ B A ∨ C Q P⇐⇒ QV V V V V V V V V

V V F F V V V V V

V F V F V V V V V

V F F F V V V V V

F V V V V V V V V

F V F F F V F F V

F F V F F F V F V

F F F F F F F F V

quindi essa e una tautologia.Posto poi P = A ∧ (B ∨ C), Q = (A ∧ B) ∨ (A ∧ C), la seconda forma

enunciativa considerata ha la seguente tavola di verita:

A B C B ∨ C P A ∧ B A ∧ C Q P⇐⇒ QV V V V V V V V V

V V F V V V F V V

V F V V V F V V V

V F F F F F F F V

F V V V F F F F V

F V F V F F F F V

F F V V F F F F V

F F F F F F F F V

quindi anch’essa e una tautologia.

94 Appendice A

Esercizio A.2. Le tavole di verita richieste sono le seguenti:

A B A =⇒ B (A =⇒ B) ∧AV V V V

V F F F

F V V F

F F V F

A B C ¬C A ∧ ¬C (A ∧ ¬C)⇐⇒ BV V V F F F

V V F V V V

V F V F F V

V F F V V F

F V V F F F

F V F V F F

F F V F F V

F F F V F V

Esercizio A.3. Per verificare che le forme enunciative considerate sono tautolo-gie e sufficiente scrivere le rispettive tavole di verita. Le prime quattro sono leseguenti:

A A ∧A A ∧A⇐⇒ AV V V

F F V

A A ∨A A ∨A⇐⇒ AV V V

F F V

A B A ∨ B B ∨A A ∨ B⇐⇒ B ∨AV V V V V

V F V V V

F V V V V

F F F F V

A B A ∧ B B ∧A A ∧ B⇐⇒ B ∧AV V V V V

V F F F V

F V F F V

F F F F V

Cenni di logica proposizionale e predicativa 95

Posto poi P = (A ∨ B) ∨ C e Q = A ∨ (B ∨ C) si ha:

A B C A ∨ B P B ∨ C Q P⇐⇒ QV V V V V V V V

V V F V V V V V

V F V V V V V V

V F F V V F V V

F V V V V V V V

F V F V V V V V

F F V F V V V V

F F F F F F F V

Infine, posto P = (A ∧ B) ∧ C e Q = A ∧ (B ∧ C) si ha:

A B C A ∧ B P B ∧ C Q P⇐⇒ QV V V V V V V V

V V F V F F F V

V F V F F F F V

V F F F F F F V

F V V F F V F V

F V F F F F F V

F F V F F F F V

F F F F F F F V

Esercizio A.4. Per verificare che le forme enunciative considerate sono contrad-dizioni e sufficiente scrivere le rispettive tavole di verita, che sono le seguenti:

A B A ∧ B ¬A ¬B ¬A ∨ ¬B A ∧ B⇐⇒ ¬A ∨ ¬BV V V F F F F

V F V F V V F

F V V V F V F

F F F V V V F

A B A ∨ B ¬A ¬B ¬A ∧ ¬B A ∨ B⇐⇒ ¬A ∧ ¬BV V V F F F F

V F V F V F F

F V V V F F F

F F F V V V F

96 Appendice A

Esercizio A.5. Posto:P1 : Carla e francese

P2 : Luigi e americano

la proposizione P si scrive al modo seguente:

¬P1 ∨ (P2 ∧ P1).

Posto poi:Q1 : Il bambino e felice

Q2 : E domenica

Q3 : C’e il sole

Q4 : Il bambino mangia il gelato

la proposizione Q si scrive al modo seguente:

Q1 ⇐⇒ (Q2 ∧Q3 ∧Q4).

Esercizio A.6.

Esercizio A.7. Gli enunciati considerati possono essere scritti come segue:A : (∃x, y ∈ Z)(x+ y = 12);B : (∀x ∈ 2N0)(2x+ 16 ∈ 2N);C : (∀x ∈ N, x > 7)(∃y ∈ N)(x = y + 7);D : (∀x ∈ P)(x e dispari oppure x = 2).

Esercizio A.8. Le negazioni richieste sono le seguenti:¬H : (∃x)(∀y)(x− 3y 6= 15);¬K : (∃x)((∀y)(x ≤ y + 7) ∧ (∀y)(x− 7 > y));¬L : (∀x)(∃y)(x− 15 > y).

Esercizio A.9.

Esercizio A.10. Per assurdo, esista a = max N0. Allora a ∈ N0, e ovviamentea+ 1 ∈ N0. Ma a < a+ 1, in contraddizione con la massimalita di a in N0. Cioprova che N0 non ha massimo.

Libro Delizia Esercizi Soluzioni

Documents

Transcript of Libro Delizia Esercizi Soluzioni