Formale Beweise als Wege
Ein formales Beweissystem definiert eine Menge von Axiomen & Schlussregeln. Jedes Theorembeweisprogramm navigiert dieses System als Suchproblem: Starten Sie bei den gegebenen Prämissen, Anwendung von Schlussregeln, um neue Aussagen zu generieren, bis Sie das Ziel erreichen.
Darstellen Sie dies als gerichteter Graph:
Knoten: korrekt formulierten Aussagen im formalen System.
Kanten: einzelne Anwendungen von Schlussregeln (modus ponens, SAS Kongruenz usw.).
Beweis: eine gerichtete Strecke von den Prämissen-Knoten zum gewünschten Schlussknoten.
Beweislänge: Anzahl der Schritt inferenz in der Strecke.
Der kürzeste Beweis eines Theorems entspricht dem kürzesten Weg zwischen dem Prämissen-Knoten und dem Schlussknoten in diesem Graph.
Das Geometrie-Theorembeweisprogramm erkundete diesen Graph durch: (1) direkte Anwendung von Regeln; (2) wenn feststeckt, Einführung von Hilfskonstruktionen (was neue Knoten zum Suchen hinzufügt). Das Programm fand den Selbstkongruenzbeweis, indem es die Hilfskonstruktion überhaupt vermied - eine kürzere Strecke existierte, die der klassische Ansatz verpasst hat.
Beweislänge & Beweis-Suche
Beweis-Suche steht vor demselben exponentiellen Wachstum wie Spielbaumsuche. Der Astfaktor an jedem Knoten entspricht der Anzahl anwendbarer Schlussregeln. Beweis-Tiefe wächst mit Komplexität des Theorems.
Das Theorembeweis-Programm verwendete Heuristiken, um den Beweisraum zu prunen, ähnlich wie Alpha-Beta-Pruning in Spielen.
Punkte, Linien & Dualität
Das Selbstkongruenzbeweis des isoszäligen Dreiecksatzes der Geometrie-Programm verwendet einen Blickwinkel, der in klassischen euklidischen Beweisen nicht erscheint. Der Einfall: Statt das Dreieck ABC mit einem zweiten konstruierten Dreieck zu vergleichen, vergleiche ABC mit sich selbst, wobei die Basispunkte vertauscht werden - die Korrespondenz A↔A, B↔C, C↔B.
Dies ist ein geometrisches Symmetrieargument: Das isoszälige Dreieck ist symmetrisch zum Spiegelungsachse vom Apex. Das Programm hat die Spiegelung nicht explizit konstruiert; es hat die Korrespondenz als Abstraktion verwendet.
Das allgemeine Prinzip hinter dieser ist projektive Dualität: Im projektiven Raum hat jeder Satz über Punkte und Linien einen dualen Satz, der erhalten wird, indem man die Worte 'Punkt' und 'Linie' im gesamten austauscht.
Dualitäts-Wörterbuch:
- Punkt ↔ Linie
- Punkt liegt auf Linie ↔ Linie geht durch Punkt
- Zwei Punkte bestimmen eine eindeutige Linie ↔ Zwei Linien bestimmen eine eindeutige Punkt
- Kolinear Punkte ↔ Konvergente Linien
Ein einzelner Beweis eines Satzes über Punkte liefert automatisch einen Beweis des dualen Satzes über Linien - und umgekehrt. Die beiden Beweise haben die gleiche Struktur, die gleiche Länge und die gleichen Schritt-Weisen. Die Suche nach dem dualen Blickwinkel enthüllt oft eine einfachere Beweis des Originals.
Anwendung der Dualität
Desargues' Theorem: Wenn zwei Dreiecke von einem Punkt aus in Perspektive stehen (die drei durch entsprechende Ecken verlaufenden Geraden treffen sich an einem Punkt), dann stehen sie auch in Perspektive zu einer Geraden (die drei Durchschnitte von entsprechenden Seiten liegen auf einer Geraden).
Dieses Theorem ist selbst-dual: Austausch von Punkten und Geraden ergibt genau die gleiche Aussage.
Probenrate & Frequenzraum
Das Computermusiksystem bei Bell Labs basierte auf einem mathematischen Theorem: dem Nyquist-Shannon-Probentheorem.
Aussage: Eine bandbegrenzte Signal mit einer maximalen Frequenz von f_max kann perfekt aus Proben, die alle 2 × f_max Sekunden genommen werden, rekonstruiert werden.
Die geometrische Interpretation: Eine bandbegrenzte Signal lebt in einem endlich-dimensionalen Unterraum des Raums von allen stetigen Funktionen. Probenahmen mit einer Rate von 2f_max bieten genügend Koordinaten, um einen Punkt in diesem Unterraum eindeutig zu identifizieren.
Aliasierung: Die Geometrie des Probenversagens
Unterhalb der Nyquist-Frequenz aliassen Frequenzen oberhalb von f_max - sie erscheinen als niedrigere Frequenzen im abgetasteten Signal. Zwei verschiedene Signale werden nach der Abtastung nicht mehr voneinander unterscheidbar. Geometrisch: Der Abtastoperator projiziert den Signalraum auf einen niedrigdimensionaleren Raum, wodurch sich verschiedene Signale kreuzen.
Für digitales Audio (CD-Qualität): f_max = 22.050 Hz (etwas über dem 20.000 Hz Schwellenwert des menschlichen Hörens), Abtastfrequenz = 44.100 Abtastungen pro Sekunde. Für das Telefon: f_max = 4.000 Hz, Abtastfrequenz = 8.000 Abtastungen pro Sekunde.
Nyquist-Frequenz-Rechnungen
Das Nyquist-Theorem bestimmt die minimale Abtastfrequenz, die den Informationsverlust verhindern soll.
Beweisraum & Signalsraum: Geteilter Geometrie
Der Beweis als Weg und das Nyquist-Abtastungssatz teilen eine gemeinsame geometrische Struktur: Beide betreffen die minimale Darstellung von etwas Komplexem.
Beweisminimierung: Finden Sie den kürzesten Weg (wenigste Schritte der Schlussfolgerung) durch das Beweisgraph von Prämissen zur Schlussfolgerung. Der selbstkonkordante Beweis hat den Pfad der Beweisminimierung durch Ausnutzung von Symmetrien verkürzt.
Signalprobenahme: Finden Sie die minimale Anzahl von Proben (niedrigste Probenrate), die alle Informationen in einem bandbegrenzten Signal bewahrt. Der Nyquist-Satz minimiert die Darstellung durch Ausnutzung von Bandbreitenbegrenzungen.
Beide Probleme befinden sich in Räumen mit Struktur, die Ergebnisse zur Minimierung der Darstellung ermöglichen. Beide scheitern, wenn diese Struktur zusammenbricht: Beweise werden länger, wenn der Axiomenspace unordentlich ist; Aliasbildung tritt auf, wenn das Signal nicht bandbegrenzt ist.