Complementare, De Morgan, induzione e partizioni

Nella lezione D01 un insieme era un sacchetto di oggetti. Qui gli oggetti sono dieci tessere numerate da 1 a 10. Il sacchetto con tutte le tessere si chiama $X$:

Ora riempi due sacchetti più piccoli. Nel primo metti le tessere con un numero pari, nel secondo quelle con un multiplo di 3:

Quale tessera dovrebbe stare in tutti e due i sacchetti? Solo la 6: è pari ed è un multiplo di 3. Le tessere che stanno in tutti e due gli insiemi formano un insieme nuovo, l'intersezione di $A$ e $B$.

L'intersezione si scrive $A\cap B$ e si legge «$A$ intersecato $B$». Il simbolo $\cap$ somiglia a una U capovolta. Nel nostro esempio:

Il risultato è un insieme, con le graffe, anche se dentro c'è un solo numero: è un sacchetto con una tessera.

Guarda la figura: l'intersezione è la zona dove i due cerchi si sovrappongono. Le tessere 1, 5 e 7 stanno fuori da tutti e due i cerchi: non sono pari e non sono multipli di 3.

Un altro esempio, con le lettere. Prendi $A=\{a,b,f,h,m\}$ e $C=\{c,p,q,s,z\}$. Nessuna lettera compare in tutti e due, quindi l'intersezione è il sacchetto vuoto:

Il simbolo $\varnothing$ si legge «insieme vuoto». Due insiemi senza elementi in comune si chiamano disgiunti.

Il libro scrive così la definizione.

Come si legge. La riga con le graffe dice: «l'intersezione è fatta degli oggetti $x$ che stanno in $A$ e stanno anche in $B$». Il simbolo $\in$ si legge «appartiene a», cioè «sta nel sacchetto». La seconda frase dice: due insiemi sono disgiunti quando non hanno niente in comune.

Una tessera o un sacchetto?

Le domande del quiz giocano quasi sempre su una differenza della lezione D01: un elemento è una tessera, un sottoinsieme è un sacchetto di tessere.

• $6\in A\cap B$ vuol dire «la tessera 6 sta nell'intersezione». Vero.
• $\{6\}\subset A\cap B$ vuol dire «il sacchetto con la tessera 6 è contenuto nell'intersezione». Vero anche questo. Il simbolo $\subset$ si legge «è contenuto in».

Torna alle tessere. Ora versa in un sacchetto nuovo tutte le tessere pari e tutte quelle multiple di 3. Che cosa c'è dentro? Le tessere 2, 4, 6, 8, 10 e poi 3 e 9. La 6 c'era già: è una tessera sola, non la metti due volte.

Questo insieme si chiama unione di $A$ e $B$.

L'unione si scrive $A\cup B$ e si legge «$A$ unione $B$». Il simbolo $\cup$ è una U, come «unione». Nel nostro esempio:

Conta gli elementi. $A$ ne ha 5 e $B$ ne ha 3, ma l'unione ne ha 7, non 8: la 6 sta in tutti e due e nell'unione si conta una volta sola.

Come si legge. «L'unione è fatta degli oggetti $x$ che stanno in $A$ oppure in $B$.» In matematica «oppure» non esclude il caso «tutti e due». È l'«o» di «vuoi zucchero o latte?», a cui si può rispondere «tutti e due».

Tre insiemi o più (p. 9)

Unione e intersezione funzionano anche con tre insiemi o più. Prendi $A=\{1,2,3\}$, $B=\{2,3,4\}$ e $C=\{3,4,5\}$.

• L'intersezione $A\cap B\cap C$ contiene quello che sta in tutti e tre: solo il 3. Quindi $A\cap B\cap C=\{3\}$.
• L'unione $A\cup B\cup C$ contiene quello che sta in almeno uno: $\{1,2,3,4,5\}$.

Con tre insiemi conviene fare un pezzo alla volta: prima $A\cap B=\{2,3\}$, poi di questi tieni quelli che stanno in $C$.

Le proprietà distributive (pp. 9–10)

Unione e intersezione si mescolano con una regola che ricorda la moltiplicazione. A scuola $2\cdot (3+4)=2\cdot 3+2\cdot 4$: il 2 si «distribuisce» sui due numeri della parentesi. Con gli insiemi succede una cosa simile.

Prova con le tessere. Prendi ancora $A$ (i pari) e $B$ (i multipli di 3), e in più $D=\{1,2,3,4\}$, le tessere piccole. Fai il conto in due modi.

1. Prima metti insieme pari e multipli di 3: $A\cup B=\{2,3,4,6,8,9,10\}$. Poi tieni quelli che stanno in $D$: 2, 3 e 4.
2. Prima prendi i pari piccoli, $A\cap D=\{2,4\}$, e i multipli di 3 piccoli, $B\cap D=\{3\}$. Poi mettili insieme: 2, 3 e 4.

Viene lo stesso insieme, $\{2,3,4\}$. Non è un caso: vale sempre.

Come si legge. La prima è il conto delle tessere: «metti insieme e poi tieni quelli in $C$» dà lo stesso di «tieni quelli in $C$ da ognuno e poi metti insieme». La seconda scambia i ruoli di unione e intersezione, e vale anche lei.

Torna alle tessere: dal sacchetto dei pari togli quelle che sono anche multiple di 3, cioè la 6. Resta $\{2,4,8,10\}$: è la differenza tra $A$ e $B$.

La differenza si scrive $A\setminus B$ e si legge «$A$ meno $B$». Contiene gli elementi di $A$ che non stanno in $B$:

L'ordine conta: $A\setminus B$ toglie da $A$, $B\setminus A$ toglie da $B$, e i risultati sono diversi.

Come si legge. «$X$ meno $A$ è fatto degli elementi di $X$ che non stanno in $A$.» Il simbolo $\notin$ si legge «non appartiene a». Non serve che $A$ stia dentro $X$: gli elementi di $A$ che in $X$ non ci sono semplicemente non contano.

Il complementare: tutto il resto

Il caso più comune è quello in cui togli una parte dal sacchetto grande. Dal sacchetto $X$ di tutte le tessere togli i pari: restano i dispari, $\{1,3,5,7,9\}$. Quello che resta si chiama complementare dei pari in $X$.

Il libro scrive il complementare $C_X(A)$ e si legge «complementare di $A$ in $X$». Altri testi scrivono $A^c$ oppure $\overline{A}$, ma in quel modo non si vede l'informazione più importante: da quale sacchetto $X$ hai tolto $A$.

Come si legge. È la stessa regola della differenza, con una condizione in più: $A$ deve essere una parte di $X$. Il complementare è «quello che manca ad $A$ per arrivare a $X$».

Due cose che il libro fa notare (p. 10):

• il complementare del complementare è l'insieme di partenza: il complementare dei pari sono i dispari, e il complementare dei dispari sono di nuovo i pari;
• i numeri irrazionali, come $\sqrt{2}$ e $\pi$, sono i reali che non sono frazioni: sono il complementare delle frazioni dentro i reali.

Comincia dalle frasi di tutti i giorni. Il contrario di «prendo il treno o il pullman» è «non prendo né il treno né il pullman»: devo rinunciare a tutti e due. Il contrario di «oggi piove e fa freddo» è «oggi non piove oppure non fa freddo»: basta che manchi una delle due cose. Con gli insiemi succede lo stesso.

Torna alle tessere e alla figura dell'intersezione. Quali tessere stanno fuori dall'unione, cioè fuori da tutti e due i cerchi? Quelle che non sono pari e non sono multiple di 3: 1, 5 e 7.

Ora fai il conto in un altro modo. Le tessere non pari sono $\{1,3,5,7,9\}$. Le tessere non multiple di 3 sono $\{1,2,4,5,7,8,10\}$. Quelle che stanno in tutti e due gli elenchi sono 1, 5 e 7. Lo stesso risultato.

C'è anche la regola gemella. Quali tessere stanno fuori dall'intersezione? L'intersezione è $\{6\}$, quindi tutte tranne la 6. E quali tessere sono non pari oppure non multiple di 3? Sono quelle a cui manca almeno una delle due cose: di nuovo tutte tranne la 6, l'unica che le ha tutte e due.

Il libro le enuncia così.

Come si legge.

• Prima uguaglianza: il complementare dell'intersezione è l'unione dei complementari. Le cose che non stanno in tutti e due sono quelle che mancano ad almeno uno.
• Seconda uguaglianza: il complementare dell'unione è l'intersezione dei complementari. Le cose che non stanno in nessuno dei due sono quelle che mancano a tutti e due.
• Un modo per ricordarle: il complementare «entra» nella parentesi e, entrando, scambia $\cap$ con $\cup$.

Ecco i conti con le tessere, messi in fila.

Le leggi valgono anche con tre o più insiemi (esercizio 1.10 del libro). Esiste anche una versione con la differenza al posto del complementare, che non chiede che $A$ e $B$ stiano dentro $X$: è l'esercizio 1.11, svolto nell'esercizio 7.

In una classe di venti studenti si formano dei gruppi di studio. Due condizioni sono ragionevoli: ogni gruppo è fatto di studenti della classe, e nessuno studente resta senza gruppo. Se qualcuno sta in due gruppi, va bene lo stesso.

Quando le parti, messe insieme, danno tutto l'insieme, formano un ricoprimento.

Prendi $X=\{1,2,3,4,5\}$ e le parti $\{1,2,3\}$ e $\{3,4,5\}$. La loro unione è $\{1,2,3,4,5\}$, cioè tutto $X$: è un ricoprimento. Il 3 sta in tutte e due le parti, e va bene.

Le parti $\{1,2\}$ e $\{4,5\}$, invece, lasciano fuori il 3: non sono un ricoprimento.

Il libro chiama famiglia un gruppo di sottoinsiemi e la scrive $\mathcal{A}=\{A_i{\}}_{i\in I}$. Si legge «la famiglia degli $A_i$» e vuol dire: le parti si chiamano $A_1$, $A_2$ e così via, con un numero ciascuna. Nell'esempio di prima, $A_1=\{1,2,3\}$ e $A_2=\{3,4,5\}$.

Come si legge. «Le parti $A_i$ sono sottoinsiemi di $X$. La loro unione è tutto $X$.» Il simbolo grande $\bigcup$ vuol dire «l'unione di tutte le parti».

Gli esempi del libro sono questi.

• Gli interi, divisi in pari e dispari: ogni intero è pari o dispari, quindi è un ricoprimento.
• I numeri reali, divisi in tre parti: i negativi, i positivi e i numeri tra $-1$ e $1$. Ogni numero reale è negativo, positivo oppure zero, e lo zero sta nella terza parte.
• I numeri reali, divisi in pezzi di retta lunghi 1: da 0 a 1, da 1 a 2, da 2 a 3, e così via, anche verso i negativi. Ogni numero sta in almeno un pezzo.

Una scrittura comoda: 2Z e 2Z + 1 (p. 12)

Il libro usa due scritture per gli insiemi di numeri (Nota 1.20). Prendi un insieme di numeri $S$ e un numero $a$:

• $aS$ è l'insieme che ottieni moltiplicando per $a$ ogni elemento di $S$;
• $S+a$ è l'insieme che ottieni sommando $a$ a ogni elemento di $S$.

Per esempio $2\mathbb{Z}$ sono gli interi moltiplicati per 2, cioè i pari: $\dots ,-4,-2,0,2,4,\dots$ E $2\mathbb{Z}+1$ sono i pari più 1, cioè i dispari. Il ricoprimento con pari e dispari si scrive allora

In generale $n\mathbb{Z}$ sono i multipli di $n$: $3\mathbb{Z}$ sono i multipli di 3. Questa scrittura compare nella domanda 1 dell'appello del 06/06/2026.

Hai un mucchio di calzini da mettere in tre cassetti: bianchi, neri e colorati. Ogni calzino finisce in un cassetto, e in uno solo. E non tieni un cassetto vuoto. Questa divisione è una partizione.

Una partizione è un ricoprimento con due condizioni in più. Per riconoscerla si controllano tre cose, una per volta.

1. Nessuno resta fuori: messe insieme, le parti danno tutto l'insieme.
2. Nessuna parte è vuota.
3. Nessuna sovrapposizione: due parti diverse non hanno elementi in comune, cioè sono disgiunte.

Prendi $X=\{1,2,3,4,5\}$.

Come si legge. Sono i tre controlli. Il primo: le parti coprono $X$. Il secondo: ogni parte $A_i$ non è vuota ($\forall$ si legge «per ogni», $\ne$ si legge «diverso da»). Il terzo: due parti con numeri diversi non hanno niente in comune.

Gli esempi del libro (p. 12), con i ricoprimenti di prima:

• pari e dispari sono una partizione degli interi: nessun intero è pari e dispari insieme;
• negativi, positivi e numeri tra $-1$ e $1$ non lo sono: $-\frac{1}{2}$, per esempio, è negativo e sta anche tra $-1$ e $1$;
• i pezzi di retta lunghi 1 non lo sono: il numero 1 sta sia nel pezzo da 0 a 1 sia in quello da 1 a 2;
• una parte $A$ di $X$ e il suo complementare sono una partizione di $X$, purché $A$ non sia vuota e non sia tutto $X$: altrimenti una delle due parti sarebbe vuota.

L'insieme quoziente (p. 13)

Quando dividi i calzini nei cassetti, a volte ti interessano i cassetti e non i singoli calzini: «quanti tipi di calzini ho?». Il libro chiama insieme quoziente l'insieme che ha come elementi le parti di una partizione: l'insieme dei cassetti.

Per la partizione degli interi in pari e dispari l'insieme quoziente ha due elementi: il cassetto dei pari e il cassetto dei dispari. Ogni elemento di un cassetto si chiama rappresentante di quel cassetto, e il cassetto si indica con un suo rappresentante tra parentesi quadre: $[0]$ è il cassetto dei pari, $[7]$ quello dei dispari. Anche $[2]$ e $[-4]$ indicano i pari: lo stesso cassetto, nominato con rappresentanti diversi.

Come si legge. L'insieme quoziente è «l'insieme dei cassetti». Un rappresentante di un cassetto è uno qualunque dei suoi elementi. Le scritture $[x]$ e $\overline{x}$ (si legge «x segnato») vogliono dire «il cassetto in cui sta $x$».

Il quoziente tornerà con le relazioni di equivalenza e con l'aritmetica dell'orologio, dove $[3]$ indicherà tutti i numeri che danno lo stesso resto di 3 in una divisione.

Ora un argomento diverso. Nella lezione D01 hai visto i numeri per contare, 0, 1, 2, 3 e così via, che formano l'insieme $\mathbb{N}$ dei naturali. Hai visto anche l'idea che partendo da 0 e andando avanti di uno alla volta si arriva a tutti. Il libro descrive i naturali con cinque regole, gli assiomi di Peano. Un assioma è una regola che non si dimostra: si accetta come punto di partenza.

Il libro chiama $s(n)$ il successivo di $n$, cioè il numero che viene subito dopo: $s(n)$ si legge «esse di $n$», e $s(4)=5$.

Le cinque regole, a parole:

1. lo zero è un numero naturale;
2. ogni naturale ha un successivo, che è ancora un naturale;
3. due naturali diversi hanno successivi diversi;
4. lo zero non è il successivo di nessun naturale;
5. se un insieme di naturali contiene lo zero e, ogni volta che contiene un numero, contiene anche il suo successivo, allora contiene tutti i naturali.

Che cosa va storto senza una regola

Il modo migliore per capire a che cosa serve ogni regola è guardare che cosa succede quando manca.

Senza la regola 4: l'orologio. Prendi le ore di un orologio, da 0 a 11, e come successivo l'ora dopo. Il successivo di 11 è 0: dopo le 11 vengono di nuovo le 0. Le regole 1, 2 e 3 valgono, ma la 4 no, perché lo zero è il successivo di 11. Con questi «numeri» non si conta oltre 11: si gira in tondo. La regola 4 impedisce di tornare all'inizio.

Senza la regola 3: il cappio. Prendi i numeri da 0 a 5 e dai a ognuno il successivo solito, tranne il 5, che ha come successivo il 3. Si va 0, 1, 2, 3, 4, 5 e poi di nuovo 3, 4, 5, 3… Lo zero non è il successivo di nessuno, quindi la regola 4 vale. Ma 2 e 5 hanno lo stesso successivo, 3: la regola 3 no. La regola 3 impedisce di rientrare a metà strada.

Senza la regola 5: i numeri fantasma. Prendi i naturali veri e aggiungi una seconda fila di numeri «fantasma» $0^{\prime }$, $1^{\prime }$, $2^{\prime }$ e così via, ognuno con il successivo nella sua fila: dopo $0^{\prime }$ viene $1^{\prime }$. Le regole da 1 a 4 valgono tutte. Ma la fila fantasma non si raggiunge mai partendo da 0. La regola 5 dice proprio che non ci sono altri numeri oltre a quelli che si raggiungono da 0 andando avanti.

Metti in fila tante tessere del domino, in piedi. Se fai cadere la prima, e ogni tessera, cadendo, fa cadere quella dopo, allora cadono tutte. Non serve guardarle una per una.

L'induzione usa la stessa idea per dimostrare che una frase sui numeri vale per tutti i naturali. È la regola 5 di Peano. Prendi l'insieme dei numeri per cui la frase è vera. Se contiene lo zero, cade la prima tessera. Se passa sempre al successivo, ogni tessera fa cadere quella dopo. Allora contiene tutti i naturali.

Il libro enuncia il principio come teorema 1.10, già visto nella lezione D01. Qui lo usiamo su due esempi nuovi.

Primo esempio: la somma dei numeri dispari

Somma i primi numeri dispari e guarda che cosa viene.

I risultati sono 1, 4, 9, 16, 25: i quadrati. Sembra che la somma dei primi $n$ dispari sia $n^2$, cioè $n$ per $n$.

C'è un'immagine che spiega perché. Un quadrato di 3 per 3 puntini ne ha 9. Per farlo diventare un quadrato di 4 per 4 aggiungi una riga in basso e una colonna a destra, a forma di L: sono $3+3+1=7$ puntini, il dispari successivo. Ogni volta che il quadrato cresce di uno, aggiungi un numero dispari.

Per scrivere la frase con le lettere serve il dispari numero $n$. Il primo è 1, il secondo 3, il terzo 5: è sempre il doppio della posizione meno 1, cioè $2n-1$. Per esempio il quinto è $2\cdot 5-1=9$. La frase da dimostrare, per ogni $n$ da 1 in poi, è:

Secondo esempio: le potenze di 2 crescono in fretta

La frase è: per ogni naturale $n$, $2^n$ è almeno $n+1$. Si scrive $2^n\ge n+1$, e il simbolo $\ge$ si legge «maggiore o uguale a».

Prima i numeri: per $n=0$ viene $1\ge 1$; per $n=1$, $2\ge 2$; per $n=2$, $4\ge 3$; per $n=3$, $8\ge 4$. La potenza di 2 corre sempre più avanti.

Nella lezione D01 hai visto l'insieme delle parti: il sacchetto che contiene tutti i sottoinsiemi di un insieme. L'insieme delle parti di $A$ si scrive $P(A)$ e si legge «parti di $A$». Qui conti quanti elementi ha.

Per $A=\{1,2,3\}$ conviene elencare i sottoinsiemi in ordine di grandezza.

In tutto $1+3+3+1=8$. Il vuoto e l'insieme intero ci sono sempre.

Perché sono 2 alla n

Per costruire un sottoinsieme di $\{1,2,3\}$ decidi, elemento per elemento, «dentro» o «fuori». L'1 dentro o fuori, il 2 dentro o fuori, il 3 dentro o fuori: tre scelte da due possibilità ciascuna, $2\cdot 2\cdot 2=8$. Con $n$ elementi le scelte sono $n$, e i sottoinsiemi $2^n$, cioè 2 moltiplicato per sé stesso $n$ volte.

Il libro lo dimostra per induzione (p. 7), con un'idea che conviene ricordare. Aggiungi un elemento nuovo, per esempio 4, all'insieme $\{1,2,3\}$. I sottoinsiemi del nuovo insieme sono di due tipi:

• quelli senza il 4: sono gli 8 sottoinsiemi di prima;
• quelli con il 4: a ognuno degli 8 di prima aggiungi il 4.

Sono due gruppi con lo stesso numero di sottoinsiemi, quindi il totale raddoppia: $2\cdot 8=16$. Un elemento in più, il doppio dei sottoinsiemi. È il passo induttivo: ogni tessera del domino fa cadere la successiva.

Come si legge. «Se $A$ ha $n$ elementi, l'insieme delle parti di $A$ ne ha $2^n$.» Le barre vogliono dire «quanti elementi ha». Il passo base è l'insieme vuoto: il suo unico sottoinsieme è il vuoto stesso, quindi $P(\varnothing )=\{\varnothing \}$ ha un elemento, e $2^0=1$. Il passo induttivo è il raddoppio con i due gruppi.

Elementi di elementi

Gli elementi di $P(A)$ sono sacchetti. Questo crea due livelli, e le domande del quiz giocano proprio sui livelli. Con $A=\{1,2,3\}$:

• $\{1,2\}\in P(A)$ è vero: il sacchetto $\{1,2\}$ è un sottoinsieme di $A$, quindi sta nel sacchetto dei sottoinsiemi;
• $1\in P(A)$ è falso: 1 è una tessera di $A$, non un sottoinsieme;
• $\{\{1\},\{2\}\}\subset P(A)$ è vero: i suoi due elementi, $\{1\}$ e $\{2\}$, sono sottoinsiemi di $A$.

La prova di Matematica Discreta, la parte 1 di MDAG, è scritta ed è la stessa per i canali A, B e C. Al 02/10/2026 le regole del 2026/27 non sono ancora uscite; quelle del 2025/26 dicono così.

Com'è fatta la prova

• 10 domande a risposta multipla, ognuna con 5 risposte e una sola giusta. Una risposta giusta vale 1 punto; una sbagliata o vuota vale 0.
• 2 problemi a risposta aperta, divisi in più domande con il punteggio scritto accanto.
• Sbarramento. Con meno di 6 punti nel quiz la prova non è superata, e i problemi non vengono corretti.
• Sufficienza: almeno 18 punti in tutto. Durata: 2 ore.
• Materiale ammesso: libro di testo e appunti del corso, e una calcolatrice non programmabile.

Dettagli e fonti nella scheda del corso.

Che cosa serve di questa lezione

1. Domanda 1 del quiz: unione e intersezione. È la domanda sugli insiemi che apre quasi ogni appello. Con due insiemi: 14/01/2025, 04/02/2025 e 03/02/2026. Con tre insiemi: 06/06/2025. Con un insieme in più da intersecare, «quale è un sottoinsieme di $(A\cup B)\cap X$?»: 01/07/2026. Con i multipli, $n\mathbb{Z}$: 06/06/2026. Le risposte sbagliate confondono quasi sempre $\in$ e $\subset$.
2. Domanda 2 del quiz: partizioni e ricoprimenti. «Quale di queste è una partizione?» nella prova del 10/07/2023 e nell'appello del 04/02/2025. «Quale è un ricoprimento ma non una partizione?» nell'appello del 07/07/2025. Si risolvono con il metodo dei tre controlli.
3. Il complementare per contare. Nei problemi di combinatoria, «almeno uno» si conta spesso come «tutti meno nessuno»: è il complementare. Lo usa la soluzione ufficiale dell'appello dell'08/09/2025, problema 2, punto (b). La combinatoria arriva più avanti nel corso.
4. Induzione e assiomi di Peano. Negli appelli di Matematica Discreta dal 2021 al 2026 non ho trovato domande che chiedano una dimostrazione per induzione. Il principio di induzione è invece tra gli argomenti dei quiz di Fondamenti dell'Informatica.

Una domanda vera, letta insieme

Errori da evitare

• Contare due volte nell'unione un elemento comune.
• Scrivere il complementare senza dire in quale insieme $X$.
• Nelle leggi di De Morgan, portare il complementare dentro la parentesi senza scambiare $\cap$ e $\cup$.
• Considerare una partizione una famiglia con una parte vuota, o controllare le sovrapposizioni solo su tutte le parti insieme invece che a due a due.
• Accettare una parte che contiene un elemento estraneo all'insieme.