Logica e dimostrazioni: le regole con cui si ragiona nell’IA

Proposizioni, connettivi e tavole di verità, la trappola dell’implicazione, quantificatori e tipi di dimostrazione — e perché XOR fermò le prime reti neurali.

14 minuti Matěj Žalmánek 2026-10-15

Serie Basi di IA Parte 7 di 52

1. Mappa dell’intelligenza artificiale: che cos’è ciascuna cosa e come si incastra tutto
2. Breve storia dell’intelligenza artificiale: da Turing ai modelli linguistici
3. Dati, modello, addestramento, inferenza: i concetti di base su un unico esempio
4. Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
5. Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
6. Funzioni e applicazioni: perché ogni modello di IA è una funzione
7. Logica e dimostrazioni: le regole con cui si ragiona nell’IA
8. Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali
9. Algebra lineare per l’apprendimento automatico: vettori, matrici e perché l’IA soprattutto moltiplica
10. Derivate, gradiente e regola della catena: come un modello capisce in quale direzione imparare
11. Discesa del gradiente: come impara un modello
12. Che cos’è la probabilità: dal lancio di un dado agli assiomi di Kolmogorov
13. Probabilità condizionata e teorema di Bayes: come cambiare una stima quando scopri qualcosa di nuovo
14. Variabile aleatoria e funzione di ripartizione: una sola funzione che dice tutto sulla distribuzione
15. Funzione di densità e funzione di massa: perché una variabile continua ha probabilità zero in un punto
16. Valore atteso, varianza e covarianza: dove si trova una distribuzione, quanto è larga e che cosa è legato a che cosa
17. Panoramica delle distribuzioni di probabilità: Bernoulli, binomiale, Poisson, uniforme, normale ed esponenziale
18. Legge dei grandi numeri e teorema del limite centrale: perché le medie si comportano in modo così prevedibile
19. Statistica e stima dei parametri: massima verosimiglianza, MAP e intervalli di confidenza
20. Teoria dell’informazione: entropia, entropia incrociata e divergenza KL — da dove vengono le funzioni di perdita
21. Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni
22. Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search
23. Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche
24. Logica e sistemi basati sulla conoscenza: concatenazione in avanti e all’indietro, risoluzione e sistemi esperti
25. Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA
26. Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi
27. Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione
28. Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero
29. Ottimizzazione con colonie di formiche: come una traccia di feromone trova un percorso breve
30. Ottimizzazione a sciame di particelle: inerzia, esperienza propria ed esperienza dello sciame
31. Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT
32. Insiemi fuzzy e funzioni di appartenenza: come scrivere «un po’ caldo»
33. Logica fuzzy e probabilità: perché «un po’ caldo» non significa «probabilmente caldo»
34. Logica fuzzy: t-norme, implicazioni e regole SE–ALLORA
35. Controllo fuzzy: Mamdani e Sugeno, dal ventilatore al pendolo inverso su un carrello
36. Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster
37. Sistemi neuro-fuzzy (ANFIS): regole fuzzy che imparano dai dati
38. Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank
39. Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto
40. Reti bayesiane: perché l’erba è bagnata e che cosa significa per l’irrigatore
41. Filtro di Kalman: come stimare da misure imprecise dove si trova un’auto e a che velocità va
42. Tipi di apprendimento automatico: supervisionato, non supervisionato, semi-supervisionato e altri
43. Prompt, contesto e RAG: come dare a un modello le informazioni giuste
44. Autoencoder variazionali (VAE): immagini nuove da uno spazio latente continuo
45. Reti generative avversarie (GAN): il falsario contro il detective
46. Modelli di diffusione: come il rumore puro diventa un’immagine
47. Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman
48. Q-learning e DQN: imparare il valore delle azioni, dalla tabella alla rete neurale
49. Policy gradient e PPO: imparare direttamente la politica
50. Come funziona un agente IA: un modello linguistico in un ciclo con strumenti
51. Programmare con agenti IA: incarico, test e controllo
52. Valutazione e sicurezza dei sistemi di IA: come misurare e come sorvegliare

Programma completo della serie 52 di 83 argomenti pubblicati

Ogni definizione di questa serie è una proposizione logica e ogni «quindi» che la segue è un pezzo di dimostrazione. La logica sono le regole del gioco: dice quando un’affermazione è vera e come dedurne correttamente altre da affermazioni vere. E nell’intelligenza artificiale compare due volte: come linguaggio in cui si parla degli algoritmi e come disciplina a sé, da cui sono nati i primi programmi «pensanti».

I simboli ¬, ∧, ∨, ⇒, ∀ ed ∃ li abbiamo incontrati per la prima volta nella parte sulla notazione matematica. Qui scopriremo come funzionano esattamente, dove si sbaglia più spesso e come con essi si costruisce una dimostrazione.

1. Proposizioni e valori di verità

Definizione — proposizione

Una proposizione è un’affermazione di cui ha senso dire se è vera o falsa. Il suo valore di verità è 1 (vero) o 0 (falso).

Dalle proposizioni semplici P, Q, … si formano, tramite i connettivi logici, le proposizioni composte. La verità di una proposizione composta dipende solo dalla verità delle sue parti.

2. Connettivi e tavole di verità

Come funziona un connettivo lo mostra meglio di tutto una tavola di verità: una riga per ogni combinazione di valori di P e Q. Due variabili hanno 2 · 2 = 4 combinazioni, n variabili 2ⁿ.

• La negazione ¬P inverte il valore.
• La congiunzione P ∧ Q («e») è vera solo quando sono vere entrambe le parti.
• La disgiunzione P ∨ Q («o») è vera quando ne è vera almeno una, anche entrambe.
• L’implicazione P ⇒ Q («se…, allora») è falsa in un solo caso: P è vera e Q no.
• L’equivalenza P ⇔ Q è vera quando le due parti hanno lo stesso valore.
• La disgiunzione esclusiva P ⊕ Q (XOR) è vera quando ne è vera esattamente una.

3. L’implicazione: la trappola più frequente

Definizione — inversa e contronominale

Per l’implicazione P ⇒ Q, l’inversa (o conversa) è Q ⇒ P e la contronominale (contrapposizione) è ¬Q ⇒ ¬P.

Teorema. Un’implicazione è equivalente alla sua contronominale, ma non alla sua inversa.

La tavola lo mostra senza discussioni: le colonne dell’implicazione e della contronominale sono uguali, l’inversa differisce in due righe.

La seconda trappola sono le righe con P = 0: quando la premessa è falsa, l’implicazione è vera, qualunque cosa sia Q. «Se 7 è pari, io sono il papa» è una proposizione vera. Suona strano, ma ha senso: l’implicazione promette qualcosa solo sulla situazione in cui P è vera, e quella promessa non si può infrangere quando P è falsa.

4. Tautologie e proposizioni equivalenti

Definizione — tautologia, contraddizione, equivalenza

Una tautologia è una proposizione composta vera per ogni assegnazione di valori alle variabili (per es. P ∨ ¬P). Una contraddizione è sempre falsa (P ∧ ¬P).

Le proposizioni A e B sono logicamente equivalenti, A ≡ B, quando A ⇔ B è una tautologia: hanno la stessa colonna nella tavola di verità.

Così si possono verificare le leggi di De Morgan della parte sugli insiemi: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q. Le colonne sono uguali:

Verificare una tautologia con una tavola è affidabile, ma per n variabili significa 2ⁿ righe. Per 300 variabili sono più righe di quanti atomi ci siano nell’universo. La domanda se una proposizione si possa soddisfare (il problema SAT) è uno dei problemi difficili più famosi dell’informatica.

5. Perché XOR fermò le prime reti neurali

Disegniamo le quattro combinazioni di P e Q come punti nel piano e coloriamoli in base al risultato. Sia per «e» sia per «o» i punti verdi si possono separare da quelli arancioni con una sola retta. Per XOR non si può: i punti verdi stanno su una diagonale e quelli arancioni sull’altra:

P ∧ Q

P ∨ Q

P ⊕ Q

Il percettrone, la rete neurale più semplice, sa separare i punti solo con una retta. Nel 1969 Minsky e Papert dimostrarono che per questo non riesce a gestire nemmeno una funzione semplice come XOR, e l’interesse per le reti neurali calò per anni. La soluzione è aggiungere uno strato: XOR si può comporre da funzioni più semplici, (P ∨ Q) ∧ ¬(P ∧ Q), e una rete a due strati ci riesce. Qui comincia la storia del deep learning.

6. Predicati e quantificatori

Definizione — predicato e quantificatori

Un predicato P(x) è una proposizione con una variabile: per ogni x di un insieme dato diventa una proposizione («x è pari»).

∀x ∈ M : P(x) è vera quando P(x) vale per tutti gli x ∈ M. ∃x ∈ M : P(x) è vera quando vale almeno per uno.

L’ordine di quantificatori diversi conta: ∀x ∃y : P(x, y) in generale non significa lo stesso di ∃y ∀x : P(x, y).

Le definizioni nell’IA sono piene di quantificatori. L’euristica ammissibile della parte sulla ricerca è «∀n : h(n) ≤ h*(n)», e per confutarla basta un solo stato in cui la stima sbaglia per eccesso.

7. Che cos’è una dimostrazione

Definizione — dimostrazione e modus ponens

Una dimostrazione di un’affermazione T è una successione finita di proposizioni che termina con T e in cui ogni proposizione è o una premessa (assioma, teorema già dimostrato) o segue dalle precedenti secondo una regola di inferenza.

La regola di inferenza fondamentale è il modus ponens: da P e P ⇒ Q segue Q. La regola è corretta perché (P ∧ (P ⇒ Q)) ⇒ Q è una tautologia.

8. Tipi di dimostrazione

Dimostrazione diretta

Dalle premesse arriviamo passo dopo passo all’affermazione. Affermazione: la somma di due numeri pari è pari. Dimostrazione: i numeri pari sono 2a e 2b per interi a, b. La loro somma è 2a + 2b = 2(a + b), cioè il doppio di un intero: un numero pari. ∎

Dimostrazione per contronominale e per assurdo

Invece di P ⇒ Q dimostriamo l’equivalente ¬Q ⇒ ¬P, oppure supponiamo che l’affermazione sia falsa e arriviamo a un’assurdità. Affermazione: i numeri primi sono infiniti. Dimostrazione per assurdo (Euclide): se fossero in numero finito, p₁, …, p_k, prendiamo N = p₁ · … · p_k + 1. Nessun p_i divide N: avanza sempre 1. Quindi N ha un divisore primo che manca nell’elenco. Contraddizione. ∎

Controesempio

Un’affermazione «per ogni» si confuta con un solo esempio. «Ogni numero dispari maggiore di 1 è primo» vale per 3, 5 e 7, e cade su 9 = 3 · 3. Tre esempi non dimostrano nulla, un controesempio confuta.

Induzione matematica

Definizione — principio di induzione matematica

Se vale P(1) (passo base) e per ogni n ≥ 1 vale P(n) ⇒ P(n + 1) (passo induttivo), allora P(n) vale per ogni n ∈ ℕ.

Affermazione: 1 + 2 + … + n = n(n + 1)/2. Passo base: per n = 1 a sinistra c’è 1 e a destra 1 · 2/2 = 1. Passo: se la formula vale per n, allora 1 + … + n + (n + 1) = n(n + 1)/2 + (n + 1) = (n + 1)(n + 2)/2, che è la formula per n + 1. ∎ Lo stesso risultato lo mostra anche l’immagine: due scalinate di punti formano insieme un rettangolo n × (n + 1).

In informatica per induzione si dimostra la correttezza degli algoritmi: «dopo k passi del ciclo vale…». Così si dimostra per esempio che UCS espande gli stati in ordine di costo non decrescente, e quindi trova il cammino più economico.

9. La logica nell’intelligenza artificiale

• IA simbolica: i primi sistemi di intelligenza artificiale erano logici, con la conoscenza scritta come regole «se–allora» e la deduzione tramite modus ponens. Su questo si reggevano i sistemi esperti degli anni Ottanta.
• I SAT solver risolvono il problema «questa proposizione si può soddisfare?» per milioni di variabili: pianificano, verificano l’hardware e cercano errori nei programmi.
• Verifica dell’IA: con la logica si dimostrano proprietà dei sistemi, per esempio che un pilota automatico non dia mai due comandi contraddittori o che una rete neurale non cambi decisione a causa di un rumore invisibile.
• Modelli linguistici e dimostrazioni: i modelli di oggi sanno scrivere dimostrazioni, che poi vengono controllate da strumenti formali che verificano ogni passo in modo meccanico.

10. Riepilogo

• Una proposizione è vera o falsa; i connettivi ¬ ∧ ∨ ⇒ ⇔ ⊕ sono definiti con precisione dalla tavola di verità.
• Un’implicazione è equivalente alla sua contronominale, non alla sua inversa, e con una premessa falsa è sempre vera.
• XOR non si può separare con una sola retta, ed è per questo che una rete neurale ha bisogno di più strati.
• L’ordine dei quantificatori conta; un’affermazione «per ogni» la confuta un solo controesempio.
• Una dimostrazione è una catena di passi verificabili: diretta, per contronominale, per assurdo o per induzione.

La vedi diversamente? Scrivi a support@coden-app.com.