16 - Insiemi e logica: il linguaggio della matematica

Prima o poi apri la pagina di un manuale di machine learning e trovi ∀ε>0 ∃δ>0 ...: ti sembra di leggere una lingua straniera, e per molte persone è il punto in cui il corso finisce. Quasi sempre il problema non sono i calcoli, che sono semplici, ma il linguaggio: un simbolo è soltanto una frase abbreviata, e se sai leggere la frase la formula non ha più segreti. Questa lezione apre il modulo di matematica e statistica ed è il dizionario che userai in tutte le successive. Per ogni concetto seguo lo stesso ordine: un'analogia concreta, la definizione completa, il codice Python che la verifica, il trade-off (quando serve e quando no) e le trappole. Le dimostrazioni sono scritte per intero, in passaggi che puoi seguire con la matita. Alla fine ogni simbolo ha una traduzione in italiano e in codice, e sai dimostrare le due leggi che si usano di continuo, De Morgan e l'inclusione-esclusione.

Basta Python 3 con la sola libreria standard, più NumPy in un paio di listati. I listati formano un solo programma da eseguire nell'ordine in cui compaiono (ciascuno riusa le definizioni del precedente), eccetto l'ultimo, la soluzione del mini-progetto, che è autonomo. Sono stati eseguiti con Python 3.14.4 e NumPy 2.3.5. Se non hai familiarità con il tipo set di Python, ripassa prima la lezione su liste, tuple, dizionari e insiemi.

Il dizionario dei simboli

La tabella accoppia ogni simbolo della lezione con la frase italiana che significa e con l'espressione Python che lo calcola. Per l'unione, oltre al metodo A.union(B), Python accetta l'operatore A | B, che useremo nel codice; la documentazione dei tipi built-in precisa che i metodi come union() accettano qualsiasi iterabile, mentre gli operatori richiedono due insiemi.

Tieni la tabella a portata di mano: nel resto del modulo ogni simbolo nuovo sarà tradotto così. Il simbolo da guardare con più cura è il complemento, perché la traduzione U - A contiene un oggetto, U, che nella notazione matematica spesso resta sottinteso; torneremo sul perché.

Gli insiemi

Un insieme è un sacchetto di biglietti. Quello che conta è cosa c'è dentro: non l'ordine in cui li hai infilati e non quante volte ripeti lo stesso biglietto. Il sacchetto {rosso, verde, rosso} e il sacchetto {verde, rosso} sono lo stesso sacchetto. Questa differenza con la lista è sostanziale: una lista è una fila ordinata che ammette ripetizioni, un insieme è un'appartenenza. Per questo x in insieme non scorre i biglietti uno per uno ma chiede al sacchetto se quello c'è, grazie alla tabella hash di cui parla la lezione sulle strutture dati, e per lo stesso motivo la documentazione avverte che gli insiemi non registrano la posizione né l'ordine di inserimento e non supportano indici né slicing.

Un insieme si descrive in due modi. Per elenco: A = {2, 4, 6, 8}. Per proprietà (set-builder): A = {n ∈ ℕ : n è pari, 0 < n ≤ 8}, che si legge «l'insieme degli n naturali tali che...» e in Python diventa una set comprehension. Il primo listato mostra la comprehension e tre fatti da non confondere: ripetizioni e ordine non contano per gli insiemi, contano per le liste, e le parentesi graffe vuote {} producono un dizionario, non un insieme vuoto.

A = {n for n in range(1, 9) if n % 2 == 0}
print(sorted(A))
print("ripetizioni e ordine non contano:", {3, 1, 3, 2} == {1, 2, 3})
print("lista e insieme sono oggetti diversi:", [3, 1, 3, 2] == [1, 2, 3])
print("`{}` è un dizionario vuoto, l'insieme vuoto è set():", type({}).__name__, type(set()).__name__)

Uscita ottenuta (Python 3.14.4, NumPy 2.3.5; eseguito due volte con uscita identica):

[2, 4, 6, 8]
ripetizioni e ordine non contano: True
lista e insieme sono oggetti diversi: False
`{}` è un dizionario vuoto, l'insieme vuoto è set(): dict set

Gli insiemi numerici standard sono ℕ i naturali (0, 1, 2, ...; alcuni testi partono da 1, quindi dichiara sempre la convenzione), ℤ gli interi, ℚ i razionali (frazioni) e ℝ i reali, con ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ. Un intervallo come [0, 1] è l'insieme dei reali tra 0 e 1 estremi inclusi (parentesi quadre); (0, 1) li esclude.

Sottoinsiemi e insieme delle parti

A ⊆ B significa che ogni elemento di A è anche elemento di B. L'insieme di tutti i sottoinsiemi di A si chiama insieme delle parti, 𝒫(A). Quanti sono? Costruiamo un sottoinsieme decidendo, per ciascun elemento, se entra o non entra: due scelte per elemento. Con |A| = n elementi e scelte indipendenti il totale è 2 · 2 · … · 2 = 2ⁿ, ed è il principio moltiplicativo che formalizzeremo nella lezione di calcolo combinatorio. La funzione parti del listato genera i sottoinsiemi per costruzione, una dimensione alla volta con itertools.combinations (la documentazione di itertools la definisce come le sottosequenze di lunghezza r dell'iterabile), e il ciclo confronta il conteggio con 2ⁿ.

from itertools import combinations

def parti(insieme):
    """Tutti i sottoinsiemi: per ogni dimensione k, tutte le combinazioni di k elementi."""
    elementi = list(insieme)
    return [set(c) for k in range(len(elementi) + 1) for c in combinations(elementi, k)]

for n in range(0, 6):
    print(f"|A| = {n}: sottoinsiemi = {len(parti(range(n)))}  (2^{n} = {2 ** n})")

Uscita ottenuta (Python 3.14.4, NumPy 2.3.5; eseguito due volte con uscita identica):

|A| = 0: sottoinsiemi = 1  (2^0 = 1)
|A| = 1: sottoinsiemi = 2  (2^1 = 2)
|A| = 2: sottoinsiemi = 4  (2^2 = 4)
|A| = 3: sottoinsiemi = 8  (2^3 = 8)
|A| = 4: sottoinsiemi = 16  (2^4 = 16)
|A| = 5: sottoinsiemi = 32  (2^5 = 32)

La corrispondenza è esatta per ogni n da 0 a 5, compreso il caso n = 0, in cui l'unico sottoinsieme è l'insieme vuoto. Nel machine learning questo conto spiega una scelta di progetto: con n = 30 caratteristiche il numero di sottoinsiemi di caratteristiche tra cui scegliere è 2³⁰ ≈ 10⁹, e con 40 caratteristiche è 2⁴⁰ ≈ 10¹². Provarli tutti è impensabile, ed è per questo che la selezione delle caratteristiche si fa con euristiche e non per forza bruta.

Le operazioni

Immagina una scuola con tre club: scacchi, teatro, robotica, a cui ogni studente può iscriversi in più di uno. L'unione A ∪ B è chi sta in almeno uno dei due club, contato una volta sola anche se è in entrambi. L'intersezione A ∩ B è chi sta in entrambi. La differenza A ∖ B è chi sta in A ma non in B. Il complemento Aᶜ è chi non sta in A rispetto a un universo, per esempio tutti gli studenti della scuola: senza universo il complemento non ha senso, perché «chi non è nel club di scacchi» è una frase che ha bisogno di sapere tra chi cercare. Il listato applica le cinque operazioni a un universo di 10 studenti e a due club, e aggiunge la differenza simmetrica (^), cioè chi sta in uno solo dei due.

U = set(range(1, 11))                 # universo: studenti numerati da 1 a 10
scacchi = {1, 2, 3, 4, 5}
teatro = {4, 5, 6, 7}

print("unione        :", sorted(scacchi | teatro))
print("intersezione  :", sorted(scacchi & teatro))
print("scacchi meno teatro:", sorted(scacchi - teatro))
print("complemento di scacchi:", sorted(U - scacchi))
print("differenza simmetrica (in uno solo dei due):", sorted(scacchi ^ teatro))

Uscita ottenuta (Python 3.14.4, NumPy 2.3.5; eseguito due volte con uscita identica):

unione        : [1, 2, 3, 4, 5, 6, 7]
intersezione  : [4, 5]
scacchi meno teatro: [1, 2, 3]
complemento di scacchi: [6, 7, 8, 9, 10]
differenza simmetrica (in uno solo dei due): [1, 2, 3, 6, 7]

Il risultato si controlla a occhio: gli studenti 4 e 5 sono in entrambi i club, quindi stanno nell'intersezione e non nella differenza simmetrica. Le proprietà base si ricordano pensando ai club: A ∪ B = B ∪ A (commutativa), (A ∪ B) ∪ C = A ∪ (B ∪ C) (associativa), e la distributiva A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C): «chi è negli scacchi e (in teatro o robotica)» coincide con «chi è negli scacchi e in teatro, oppure negli scacchi e in robotica».

Le leggi di De Morgan, dimostrate

Le leggi di De Morgan, che l'autore a cui sono intitolate espose nella sua opera di logica del 1847, dicono come il complemento «attraversa» un'unione o un'intersezione: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ e (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ. In italiano: «non (A o B)» è «non A e non B»; «non (A e B)» è «non A o non B». Se non sei iscritto né a scacchi né a teatro, allora non sei iscritto a scacchi e non sei iscritto a teatro. Per dimostrare che due insiemi sono uguali si mostra che un elemento qualunque sta nell'uno se e solo se sta nell'altro. Sia x un elemento dell'universo; la prima legge si dimostra così, passo per passo.

1. x ∈ (A ∪ B)ᶜ significa (definizione di complemento) x ∉ A ∪ B.
2. x ∉ A ∪ B significa che non è vero che «x ∈ A oppure x ∈ B», cioè (negando un «oppure») x ∉ A e x ∉ B.
3. x ∉ A e x ∉ B significa (definizione di complemento, due volte) x ∈ Aᶜ e x ∈ Bᶜ.
4. Cioè x ∈ Aᶜ ∩ Bᶜ.

Ogni passaggio è una equivalenza («se e solo se»), quindi (A ∪ B)ᶜ e Aᶜ ∩ Bᶜ hanno gli stessi elementi: sono uguali. ∎ L'ordine dei passi non è intercambiabile: il secondo usa il significato di «oppure» che il primo ha appena scritto, e il quarto riunisce i due pezzi del terzo. La seconda legge si dimostra allo stesso modo, scambiando i ruoli di «e» e «o».

Un controllo con il computer non è una dimostrazione generale, ma qui è possibile qualcosa di forte: su un universo piccolo si provano tutte le coppie di sottoinsiemi. Con un universo di 4 elementi ci sono 16 sottoinsiemi e quindi 256 coppie; il listato le percorre tutte e usa assert per le due leggi, così basta una sola eccezione per interrompere il programma.

U = {0, 1, 2, 3}
tutti = parti(U)                    # i 16 sottoinsiemi di U
coppie = 0
for A in tutti:
    for B in tutti:
        assert U - (A | B) == (U - A) & (U - B)       # prima legge
        assert U - (A & B) == (U - A) | (U - B)       # seconda legge
        coppie += 1
print("coppie (A, B) verificate:", coppie, "| nessuna eccezione")

Uscita ottenuta (Python 3.14.4, NumPy 2.3.5; eseguito due volte con uscita identica):

coppie (A, B) verificate: 256 | nessuna eccezione

Nessuna asserzione è fallita, quindi su questo universo le due leggi valgono per tutte le 256 coppie. Il vantaggio del controllo esaustivo è che trova da solo gli errori di trascrizione: se scrivessi U - (A | B) == (U - A) | (U - B) con il «o» al posto dell'«e», il programma si fermerebbe subito. Il limite è che non dice nulla su universi più grandi: per quello serve la dimostrazione di sopra.

Dove le incontri davvero

Ogni volta che scrivi un filtro con più condizioni su una tabella stai usando De Morgan. Il listato lo mostra con maschere booleane di NumPy (la stessa sintassi vale per le colonne di Pandas): ~(a | b) e ~a & ~b selezionano le stesse righe, dove ~ è la negazione.

import numpy as np

eta = np.array([15, 22, 35, 41, 67, 70])
a = eta < 18                                   # minorenne
b = eta >= 65                                  # anziano
print("fuori da entrambe (~(a|b))  :", eta[~(a | b)])
print("~a & ~b                     :", eta[~a & ~b])
print("stessa selezione:", np.array_equal(~(a | b), ~a & ~b))

Uscita ottenuta (Python 3.14.4, NumPy 2.3.5; eseguito due volte con uscita identica):

fuori da entrambe (~(a|b))  : [22 35 41]
~a & ~b                     : [22 35 41]
stessa selezione: True

Il giorno in cui devi negare un filtro lungo senza sbagliare, De Morgan ti salva: nega ogni condizione e scambia gli «e» con gli «o». Lo stesso vale per i filtri sui dati di una pipeline di addestramento, dove un errore nella negazione toglie righe che avresti voluto tenere senza che nulla segnali il problema.

Il prodotto cartesiano: lo spazio dei dati e la griglia

Un ristorante propone 3 primi e 2 secondi, e un menù è una coppia (primo, secondo). I menù possibili sono tutte le coppie: 3 · 2 = 6. Il prodotto cartesiano A × B è l'insieme di tutte le coppie ordinate (a, b) con a ∈ A e b ∈ B, quindi |A × B| = |A| · |B|: per ogni elemento di A hai |B| modi di completare la coppia. Nel machine learning compare due volte. Lo spazio dei dati è un prodotto cartesiano: un esempio con d caratteristiche reali è un punto di ℝ × ℝ × … × ℝ = ℝᵈ, e dire «i dati stanno in uno spazio a 30 dimensioni» significa che ogni esempio è una 30-upla. La griglia degli iperparametri è un altro: provare C ∈ {0.1, 1, 10} e kernel ∈ {lineare, rbf} significa percorrere il prodotto {0.1, 1, 10} × {lineare, rbf}, cioè 6 combinazioni, ed è ciò che fa GridSearchCV nella lezione su scikit-learn. Il listato costruisce la griglia con itertools.product, che la documentazione descrive come il prodotto cartesiano degli iterabili in ingresso.

from itertools import product

C = [0.1, 1, 10]
kernel = ["lineare", "rbf"]
griglia = list(product(C, kernel))
print(griglia)
print("combinazioni:", len(griglia), "= |C| · |kernel| =", len(C) * len(kernel))

print("con 5 iperparametri da 10 valori:", 10 ** 5, "combinazioni")

Uscita ottenuta (Python 3.14.4, NumPy 2.3.5; eseguito due volte con uscita identica):

[(0.1, 'lineare'), (0.1, 'rbf'), (1, 'lineare'), (1, 'rbf'), (10, 'lineare'), (10, 'rbf')]
combinazioni: 6 = |C| · |kernel| = 6
con 5 iperparametri da 10 valori: 100000 combinazioni

La lunghezza della lista coincide con il prodotto delle lunghezze. Il trade-off è che il prodotto cartesiano cresce moltiplicativamente: aggiungere un iperparametro da 10 valori moltiplica per 10 il costo della ricerca, e con 5 iperparametri da 10 valori ciascuno si arriva a 100 000 combinazioni, ciascuna da addestrare più volte nella validazione incrociata. È la «maledizione» che spinge verso ricerche casuali o adattive invece della griglia completa.

Contare: l'inclusione-esclusione

Quanti studenti ci sono in almeno un club? Se sommi gli iscritti ai due club, quelli iscritti a entrambi vengono contati due volte. La correzione è sottrarre una volta l'intersezione: |A ∪ B| = |A| + |B| − |A ∩ B|. La dimostrazione spezza A ∪ B in tre parti disgiunte: i soli in A (A ∖ B), i soli in B (B ∖ A) e i comuni (A ∩ B). Allora |A ∪ B| = |A∖B| + |B∖A| + |A∩B|. Ma |A| = |A∖B| + |A∩B| (A è fatto dai soli-A e dai comuni), da cui |A∖B| = |A| − |A∩B|, e analogamente |B∖A| = |B| − |A∩B|. Sostituendo: |A∪B| = (|A| − |A∩B|) + (|B| − |A∩B|) + |A∩B| = |A| + |B| − |A∩B|. ∎

Con tre insiemi serve una correzione in più: sottraendo le tre intersezioni a coppie, la triplice intersezione è stata tolta troppe volte e va riaggiunta, |A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. Il listato generalizza a un numero qualunque di insiemi con una somma alternata: per ogni dimensione k del gruppo, segno più se k è dispari e meno se è pari, sulle intersezioni di tutti i gruppi di quella dimensione (costruiti con combinations). Lo confronta con l'unione calcolata direttamente, su tre canali di vendita.

from itertools import combinations

def incl_escl(insiemi):
    """Cardinalità dell'unione con la formula: somma alternata sulle intersezioni."""
    totale = 0
    for k in range(1, len(insiemi) + 1):
        segno = 1 if k % 2 == 1 else -1
        for gruppo in combinations(insiemi, k):
            totale += segno * len(set.intersection(*gruppo))
    return totale

web = {1, 2, 3, 4, 5, 6}
app = {4, 5, 6, 7, 8}
negozio = {6, 8, 9, 10}

print("formula          :", incl_escl([web, app, negozio]))
print("unione diretta   :", len(web | app | negozio))
print("somma ingenua    :", len(web) + len(app) + len(negozio), "(conta più volte chi usa più canali)")

Uscita ottenuta (Python 3.14.4, NumPy 2.3.5; eseguito due volte con uscita identica):

formula          : 10
unione diretta   : 10
somma ingenua    : 15 (conta più volte chi usa più canali)

La formula e l'unione diretta danno entrambe 10, mentre la somma ingenua dà 15 perché conta più volte chi usa più canali. Se hai gli insiemi, basta len(A | B | C); la formula serve quando conosci solo i conteggi, per esempio da report diversi («12 000 hanno comprato online, 8 000 in negozio, 3 000 in entrambi»), e devi stimare quanti clienti distinti hai. Nella lezione sulla probabilità la stessa formula riapparirà con «numero di elementi» sostituito da «probabilità».

Le funzioni

Una funzione f : A → B è una macchinetta distributrice: a ogni elemento di A (il dominio, ciò che inserisci) assegna esattamente un elemento di B (il codominio, il tipo di cosa che esce). L'insieme dei valori che escono davvero si chiama immagine, f(A) ⊆ B. Tre proprietà, ciascuna con la sua domanda, sono riassunte nella tabella.

Una funzione biiettiva è invertibile: dall'uscita puoi risalire all'ingresso. Quando un'operazione sui dati deve essere reversibile (codificare le etichette, comprimere senza perdita) serve una biiezione. Il listato verifica le due proprietà per funzioni definite su un dominio finito: l'iniettività controlla che le immagini non collidano (nessun duplicato nella lista delle uscite), la suriettività che l'insieme delle uscite coincida con il codominio dichiarato.

def iniettiva(f, dominio):
    immagini = [f(x) for x in dominio]
    return len(set(immagini)) == len(immagini)          # nessuna collisione

def suriettiva(f, dominio, codominio):
    return {f(x) for x in dominio} == set(codominio)

D = range(-3, 4)                                    # dominio: da -3 a 3
print("x -> x^2 su D        iniettiva:", iniettiva(lambda x: x * x, D))
print("x -> x+10 su D       iniettiva:", iniettiva(lambda x: x + 10, D))
print("x -> max(0, x) (ReLU) iniettiva:", iniettiva(lambda x: max(0, x), D))
print("x -> x % 3 sul codominio {0,1,2} suriettiva:", suriettiva(lambda x: x % 3, D, [0, 1, 2]))

Uscita ottenuta (Python 3.14.4, NumPy 2.3.5; eseguito due volte con uscita identica):

x -> x^2 su D        iniettiva: False
x -> x+10 su D       iniettiva: True
x -> max(0, x) (ReLU) iniettiva: False
x -> x % 3 sul codominio {0,1,2} suriettiva: True

La funzione x → x² su {−3, …, 3} non è iniettiva ((−2)² = 2²): dall'uscita 4 non puoi risalire se l'ingresso era 2 o −2. Una ReLU (max(0, x)) schiaccia tutti i negativi sullo stesso zero, quindi perde informazione e non è invertibile; per questo uno strato con ReLU non è, in generale, reversibile. Aggiungere 10 invece è una biiezione sul proprio codominio. Il controllo in codice vale solo per domini finiti e piccoli: per un dominio infinito servono le dimostrazioni.

Funzioni e machine learning

Un modello è una funzione, f : ℝᵈ → ℝ, dallo spazio delle caratteristiche ai valori da prevedere. La preimmagine f⁻¹(S) = {x : f(x) ∈ S} è l'insieme di ingressi che producono un certo risultato: per un classificatore, f⁻¹({1}) è la regione di decisione della classe 1, un sottoinsieme dello spazio dei dati, e classificare significa partizionare lo spazio in insiemi. La composizione (g ∘ f)(x) = g(f(x)) è alla base delle reti neurali, che applicano strati in sequenza, e della regola della catena dell'analisi. La funzione indicatrice 1_A(x), che vale 1 se x ∈ A e 0 altrimenti, è il ponte tra insiemi e numeri: l'accuratezza di un classificatore è la media di indicatrici, (1/n) Σ 1[predetto_i = vero_i]. Il listato calcola l'accuratezza in questo modo su sei esempi e costruisce la regione di decisione di un classificatore minuscolo, f(x) = [2x − 1 > 0], su nove punti.

vero = np.array([1, 0, 1, 1, 0, 1])
pred = np.array([1, 0, 0, 1, 0, 1])
indicatrici = (pred == vero).astype(int)       # 1 dove abbiamo indovinato
print("indicatrici:", indicatrici, "| accuratezza = media delle indicatrici =", indicatrici.mean())

regione_classe_1 = {x for x in np.linspace(-2, 2, 9) if 2 * x - 1 > 0}      # preimmagine di {1} per f(x) = [2x - 1 > 0]
print("regione di decisione della classe 1:", sorted(float(x) for x in regione_classe_1))

Uscita ottenuta (Python 3.14.4, NumPy 2.3.5; eseguito due volte con uscita identica):

indicatrici: [1 1 0 1 1 1] | accuratezza = media delle indicatrici = 0.8333333333333334
regione di decisione della classe 1: [1.0, 1.5, 2.0]

Cinque previsioni su sei sono corrette, quindi la media delle indicatrici è 5/6 ≈ 0.8333. La regione di decisione contiene i punti con 2x − 1 > 0, cioè x > 0.5, e tra i nove punti scelti sono 1.0, 1.5 e 2.0. Il modello vero di una lezione futura sarà più complicato, ma l'idea è già tutta qui: un modello è una funzione, e la sua classificazione è un sottoinsieme.

Logica: implicazione, quantificatori, controesempi

P ⇒ Q («se P allora Q») è falsa solo nel caso in cui P è vera e Q è falsa. La tabella di verità (V vero, F falso) sorprende chi non l'ha mai guardata.

Se P è falsa l'implicazione è vera «a vuoto»: la promessa «se piove, porto l'ombrello» non è violata nei giorni di sole. Da qui tre fatti da tenere distinti. La contronominale ¬Q ⇒ ¬P equivale all'originale: «se piove, la strada è bagnata» equivale a «se la strada è asciutta, non piove», ed è utile per dimostrare. L'inversa Q ⇒ P non equivale all'originale: «se la strada è bagnata, piove» è falsa (c'è l'autolavaggio), e confondere le due è la fallacia dell'affermazione del conseguente. Un esempio dal machine learning: «se il modello va in overfitting, l'errore sul test è maggiore dell'errore sul training»; l'inversa («se l'errore sul test è maggiore, c'è overfitting») è falsa, perché potrebbe esserci anche solo un normale divario. Il listato stampa la tabella di verità dell'implicazione, della contronominale e dell'inversa per tutte le quattro combinazioni.

def implica(p, q):
    return (not p) or q

print("P     Q     | P=>Q  | non-Q => non-P | inversa Q=>P")
for P in (True, False):
    for Q in (True, False):
        print(f"{P!s:5} {Q!s:5} | {implica(P, Q)!s:5} | {implica(not Q, not P)!s:14} | {implica(Q, P)!s}")

Uscita ottenuta (Python 3.14.4, NumPy 2.3.5; eseguito due volte con uscita identica):

P     Q     | P=>Q  | non-Q => non-P | inversa Q=>P
True  True  | True  | True           | True
True  False | False | False          | True
False True  | True  | True           | False
False False | True  | True           | True

Nelle righe la colonna dell'implicazione e quella della contronominale sono identiche, mentre l'inversa differisce nelle righe True False e False True. È la verifica meccanica dell'equivalenza: due espressioni logiche sono equivalenti se hanno la stessa colonna in tutte le righe.

I quantificatori e la loro negazione

∀x ∈ A : P(x) dice che tutti gli elementi soddisfano P; ∃x ∈ A : P(x) dice che almeno uno la soddisfa. La negazione scambia i due: ¬(∀x : P(x)) ⇔ ∃x : ¬P(x) e ¬(∃x : P(x)) ⇔ ∀x : ¬P(x). Sono le leggi di De Morgan generalizzate a un numero qualunque di termini. La negazione di «il modello sbaglia mai» (per ogni esempio, corretto) è «esiste un esempio in cui sbaglia». Una conseguenza pratica per chi testa software e modelli: un solo controesempio basta per confutare un ∀, ma nessun numero finito di esempi basta per dimostrarlo. Mille test verdi non dimostrano che il codice è corretto; un test rosso dimostra che non lo è. In Python i due quantificatori sono all e any, e il listato verifica che la negazione di uno sia l'altro sulla lista degli errori di un modello.

errori = [False, False, True, False]            # True = il modello ha sbagliato su quell'esempio

mai_sbaglia = all(not e for e in errori)         # ∀ esempio: non ha sbagliato
sbaglia_almeno_una_volta = any(errori)           # ∃ esempio: ha sbagliato
print("∀ corretto:", mai_sbaglia, "| ∃ errore:", sbaglia_almeno_una_volta,
      "| negazione coerente:", (not mai_sbaglia) == sbaglia_almeno_una_volta)

print("all([]) =", all([]), "| any([]) =", any([]))

Uscita ottenuta (Python 3.14.4, NumPy 2.3.5; eseguito due volte con uscita identica):

∀ corretto: False | ∃ errore: True | negazione coerente: True
all([]) = True | any([]) = False

L'ultima riga contiene una trappola classica: all([]) vale True. La documentazione di all lo dichiara espressamente («o se l'iterabile è vuoto»). Un ∀ sull'insieme vuoto è vacuamente vero: «tutti i cigni verdi sono lunghi 2 metri» è vera perché non ce ne sono, quindi nessuno viola la frase. Se calcoli «il modello ha indovinato tutte le previsioni» su un gruppo senza esempi ottieni True, e un test di qualità su un filtro che per errore ha svuotato i dati passa in silenzio. Verifica sempre che l'insieme non sia vuoto.

Dove ritroverai queste idee

La lezione può sembrare astratta finché non si vede l'uso, quindi dico subito dove ritorna ciascuna idea. Gli insiemi e le loro operazioni diventano, nella lezione sulla probabilità, gli eventi: «esce un numero pari e maggiore di 2» è un'intersezione, «esce un numero pari o maggiore di 2» è un'unione, «non esce un pari» è un complemento. Le funzioni sono i modelli: ogni modello è una funzione dallo spazio delle caratteristiche all'insieme delle risposte, e addestrarlo significa scegliere una funzione in una famiglia. La logica dei quantificatori ritorna con forza nella definizione di limite (∀ε ∃δ) della lezione di analisi, e il controesempio è lo strumento mentale per leggere ogni affermazione generale su un modello: «funziona su tutti i casi» si confuta con un solo caso. Il prodotto cartesiano, infine, è lo spazio dei dati e la griglia degli iperparametri. Chi capisce bene questi pochi concetti ha già in mano la metà del linguaggio del resto del modulo.

Errori tipici

Tre di queste righe (l'universo, l'«o» inclusivo e l'inversa) nascono dalla stessa abitudine: leggere una formula come si legge una frase di tutti i giorni, dove il contesto riempie i vuoti. In matematica nulla è sottinteso, e per questo conviene sempre tradurre la formula in codice ed eseguirla su un esempio piccolo.

Mini-progetto

Hai tre elenchi di identificativi cliente: newsletter, acquisti, reclami (inventali con 20-30 numeri ciascuno, con sovrapposizioni). Procedi in quattro passi.

1. Calcola, con operazioni su insiemi, i clienti che hanno comprato ma non si sono mai lamentati e quelli che sono iscritti alla newsletter ma non hanno comprato.
2. Verifica con la formula di inclusione-esclusione che |N ∪ A ∪ R| coincide con la cardinalità diretta.
3. Verifica De Morgan su questi tre insiemi, con un universo che includa tutti gli identificativi.
4. Scrivi una frase, con un quantificatore, che descriva il caso «ogni cliente che ha fatto un reclamo ha anche fatto un acquisto», e testala con all. Che cosa succede se reclami è vuoto?

Il quarto passo ti riporta alla trappola della verità a vuoto, ed è il motivo per cui l'ho messo alla fine: se il tuo risultato con reclami vuoto è True, hai capito la differenza fra «tutti rispettano la regola» e «c'è qualcuno che la rispetta». Prova a farlo da solo prima di leggere la soluzione.

La soluzione mette al lavoro tutto il vocabolario su tre elenchi di identificativi generati con un seme (default_rng(4)), in modo che il risultato sia riproducibile. scegli(k) estrae k identificativi diversi tra 1 e 40 (con replace=False la documentazione di Generator.choice garantisce che non ci siano duplicati) e li converte in interi Python con int(x), perché un insieme di interi NumPy si stampa in modo meno leggibile. Poi ciascuno dei quattro blocchi del listato risolve il passo corrispondente.

import numpy as np
from itertools import combinations

rng = np.random.default_rng(4)
universo = set(range(1, 41))                                  # 40 clienti in tutto
scegli = lambda k: {int(x) + 1 for x in rng.choice(40, size=k, replace=False)}
newsletter, acquisti, reclami = scegli(22), scegli(18), scegli(9)
print("|N| =", len(newsletter), "| |A| =", len(acquisti), "| |R| =", len(reclami))

# 1) operazioni su insiemi
print("hanno comprato e non si sono mai lamentati :", len(acquisti - reclami))
print("iscritti alla newsletter che non hanno comprato:", len(newsletter - acquisti))

# 2) inclusione-esclusione contro la cardinalità diretta
def incl_escl(insiemi):
    totale = 0
    for k in range(1, len(insiemi) + 1):
        for gruppo in combinations(insiemi, k):
            totale += (-1) ** (k + 1) * len(set.intersection(*gruppo))
    return totale

print("|N ∪ A ∪ R| formula:", incl_escl([newsletter, acquisti, reclami]), "| diretto:", len(newsletter | acquisti | reclami))

# 3) De Morgan con un universo esplicito
fuori_da_tutti = universo - (newsletter | acquisti | reclami)
print("De Morgan 1:", fuori_da_tutti == (universo - newsletter) & (universo - acquisti) & (universo - reclami))
print("De Morgan 2:", universo - (newsletter & acquisti) == (universo - newsletter) | (universo - acquisti))

# 4) quantificatore: «ogni cliente che ha fatto un reclamo ha anche comprato»
print("∀ r ∈ R : r ∈ A  ->", all(r in acquisti for r in reclami), "| controesempi:", sorted(reclami - acquisti))
print("con R vuoto:", all(r in acquisti for r in set()), "(vero a vuoto)")

Uscita ottenuta (Python 3.14.4, NumPy 2.3.5; eseguito due volte con uscita identica):

|N| = 22 | |A| = 18 | |R| = 9
hanno comprato e non si sono mai lamentati : 14
iscritti alla newsletter che non hanno comprato: 14
|N ∪ A ∪ R| formula: 33 | diretto: 33
De Morgan 1: True
De Morgan 2: True
∀ r ∈ R : r ∈ A  -> False | controesempi: [12, 21, 25, 27, 39]
con R vuoto: True (vero a vuoto)

Il primo blocco usa solo differenze di insiemi: «comprato ma non lamentato» è acquisti - reclami. Il secondo confronta la formula di inclusione-esclusione con la cardinalità dell'unione calcolata direttamente: le due coincidono (33), ed è un buon test della formula. Il terzo verifica le due leggi di De Morgan, che richiedono un universo per calcolare il complemento (universo - X). Il quarto traduce la frase con il quantificatore in all(...) e mostra l'insieme dei controesempi (reclami - acquisti): non solo «falso», ma quali reclamanti non hanno comprato, che è l'informazione utile a chi deve intervenire. L'ultima riga ricorda che su un insieme vuoto all è sempre vero.

Sfide

• Easy. Dimostra che A ∖ B = A ∩ Bᶜ e verificalo in codice per tutte le coppie di sottoinsiemi di un universo di 4 elementi.
• Medium. Dimostra la seconda legge di De Morgan, (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ, con una catena di equivalenze, e scrivi il test esaustivo.
• Hard. Dimostra che per insiemi finiti |A × B| = |A| · |B| e che |𝒫(A)| = 2^{|A|} per induzione su |A| (suggerimento: un sottoinsieme di A ∪ {a} contiene a oppure no).
• Expert. Una funzione f : A → B tra insiemi finiti con |A| = |B|: dimostra che è iniettiva se e solo se è suriettiva. Perché la stessa affermazione è falsa per insiemi infiniti? Pensa a n → n + 1 su ℕ.
• Enterprise. Prendi due esportazioni di anagrafica clienti della tua organizzazione. Usando solo operazioni su insiemi di chiavi, elenca i clienti presenti in una sola, quelli presenti in entrambe e i duplicati interni. Quali di questi controlli diventano critici prima di un merge di Pandas?

Le prime due sfide si risolvono ricalcando le dimostrazioni di questa lezione; la terza e la quarta chiedono un'idea in più, l'induzione e il conteggio con una funzione. Nella sfida Expert la sorpresa è proprio il caso infinito: vale la pena provare a costruire l'esempio prima di guardare la soluzione.

Nella prossima lezione, calcolo combinatorio, impari a contare gli elementi di questi insiemi senza elencarli. La lezione su scikit-learn, che precede questa, usa già questi conti per la ricerca a griglia degli iperparametri.

Nella stessa serie trovi anche: 23 - Algebra lineare 1: vettori, matrici, sistemi (che richiama questa lezione).

Fonti

Riferimenti bibliografici citati ma non aperti per questa revisione: A. De Morgan, Formal Logic, 1847 (la data e il titolo sono quelli indicati nella versione precedente di questo articolo, non riverificati); P. R. Halmos, Naive Set Theory, 1960; D. J. Velleman, How to Prove It, Cambridge University Press.