Dimostrazioni formali come percorsi
Un sistema di dimostrazioni formali definisce un insieme di assiomi e regole di inferenza. Ogni programma dimostrativo naviga questo sistema come un problema di ricerca: partendo dalle premesse date, applicare le regole di inferenza per generare nuove affermazioni, fino a raggiungere il risultato desiderato.
Rappresenta questo come un grafo diretto:
Nodi: enunciati ben formati nel sistema formale.
Archi: applicazioni singole di regole di inferenza (modus ponens, congruenza SAS, ecc.).
Dimostrazione: un percorso diretto dalle premesse date alla conclusione desiderata.
Lunghezza della dimostrazione: numero di passaggi di inferenza nel percorso.
La dimostrazione più corta di un teorema corrisponde al percorso più corto tra il nodo delle premesse e il nodo della conclusione in questo grafo.
Il programma di geometria dimostrativa ha esplorato questo grafo applicando direttamente le regole e, se bloccati, introducendo costruzioni ausiliarie (che aggiungono nuovi nodi alla ricerca). Il programma ha trovato la dimostrazione di auto-congruenza evitando completamente la costruzione ausiliare - un percorso più corto esisteva che l'approccio classico ha ignorato.
Lunghezza della dimostrazione e ricerca della dimostrazione
La ricerca della dimostrazione affronta lo stesso aumento esponenziale della ricerca degli alberi di gioco. Il fattore di ramificazione a ogni nodo è uguale al numero di regole di inferenza applicabili. La profondità delle dimostrazioni cresce con la complessità del teorema.
Il programma di dimostrazione ha utilizzato heuristics per potare lo spazio delle dimostrazioni, analogamente all'alpha-beta pruning nei giochi.
Punti, Linee & Dualità
La dimostrazione autocongruente del programma di geometria della proposizione del teorema dell'isoscele utilizza una prospettiva che non è presente nelle dimostrazioni euclidee classiche. L'insight: invece di confrontare il triangolo ABC con un secondo triangolo costruito, confronta ABC con se stesso con i vertici basi scambiati - la corrispondenza A↘A, B↘C, C↘B.
Si tratta di un argomento di simmetria geometrica: il triangolo isoscele è simmetrico rispetto alla riflessione sull'altitudine dall'apice. Il programma non ha costruito la riflessione esplicitamente; ha utilizzato la corrispondenza come un'astrazione.
Il principio generale dietro a questo è la dualità proiettiva: nel piano proiettivo, ogni teorema sui punti e le linee ha un teorema dualizzato ottenuto sostituendo le parole 'punto' e 'linea' ovunque.
Lessico di dualità:
- Punto ↘ Linea
- Punto giace su linea ↘ Linea passa per punto
- Due punti determinano una linea unica ↘ - Due linee determinano un punto unico
- Punti collineari ↘ Linee concorrenti
Una sola dimostrazione di un teorema sui punti fornisce automaticamente una dimostrazione del teorema dualizzato sulle linee - e viceversa. Le due dimostrazioni hanno la stessa struttura, la stessa lunghezza e gli stessi passaggi di inferenza. Trovare la prospettiva dualizzata spesso rivela una dimostrazione più semplice dell'originale.
Applicazione della Dualità
Teorema di Desargues: Se due triangoli sono in prospettiva da un punto (le tre linee attraverso i vertici corrispondenti si incontrano in un solo punto), allora sono in prospettiva da una linea (gli intersezioni delle tre corrispondenti si trovano su una sola linea).
Questo teorema è auto-duale: scambiando i punti e le linee si ottiene la stessa enunciazione del teorema.
Frequenza di campionamento & Spazio delle frequenze
Il sistema di musica informatica dei Bell Labs si basava su un teorema matematico: il teorema di Nyquist-Shannon.
Enunciato: una segnale limitata da banda con massima frequenza f_max può essere ricostruita perfettamente dai campioni prelevati ad una velocità di almeno 2 × f_max campioni al secondo.
L'interpretazione geometrica: una segnale limitata da banda vive in uno sottospazio a dimensione finita dello spazio di tutte le funzioni continue. Campionare a una velocità di 2f_max fornisce abbastanza coordinate per identificare univocamente un punto in quell'sottospazio.
Aliasing: La geometria del fallimento del campionamento
Sotto la frequenza di Nyquist, le frequenze superiori a f_max si sovrappongono - appaiono come frequenze più basse nel segnale campionato. Due segnali distinti diventano indistinguibili dopo il campionamento. Geometricamente: l'operatore di campionamento proietta lo spazio segnale su uno spazio a dimensioni inferiori, causando la collisione di segnali diversi.
Per l'audio digitale (qualità CD): f_max = 22.050 Hz (leggermente sopra il limite di percezione umana di 20.000 Hz), taratura di campionamento = 44.100 campioni/al secondo. Per telefono: f_max = 4.000 Hz, taratura di campionamento = 8.000 campioni/al secondo.
Calcoli della Frequenza di Nyquist
Il teorema di Nyquist determina il campionamento minimo necessario per evitare la perdita di informazioni.
Dimostrazione dello spazio e dello spazio segnale: geometria condivisa
Il proof-as-path e il teorema di campionamento di Nyquist condividono una struttura geometrica comune: entrambi coinvolgono la ricerca della rappresentazione minima di qualcosa di complesso.
Minimizzazione della prova: trovare il percorso più breve (minimo numero di passi di inferenza) attraverso il grafo della prova dai presupposti alla conclusione. Il percorso di prova minimizzato dalla autocomprensione sfrutta la simmetria.
Campionamento del segnale: trovare il numero minimo di campioni (tasso di campionamento più basso) che preserva tutta l'informazione in un segnale a banda limitata. Il teorema di Nyquist minimizza la rappresentazione sfruttando i limiti di banda.
Entrambi i problemi vivono in spazi con struttura che consente risultati di rappresentazione minima. Entrambi falliscono quando quella struttura si rompe: le prove diventano più lunghe quando lo spazio degli assiomi è male organizzato; l'aliasing si verifica quando il segnale non è a banda limitata.