Formella Bevis som Vägar
En formell bevissystem definierar en uppsättning axiom & inferensregler. Varje theorem-proving program navigerar detta system som ett sökproblemat: börja på de givna premisserna, tillämpa inferensregler för att generera nya uttalanden, tills du når målkonklusionen.
Representera detta som en riktad graff:
Noder: välformulerade uttalanden i det formella systemet.
Kanter: enstaka tillämpningar av inferensregler (modus ponens, SAS kongruens, etc.).
Bevis: en riktad väg från de givna premisserna till önskad slutsats.
Bevislängd: antalet inferenssteg i vägen.
Det kortaste beviset för ett theorem motsvarar den kortaste vägen mellan premisset och slutsatsen i denna graff.
Programmet för geometribevisning utforskade denna graff genom: (1) direkt tillämpning av regler; (2) om man fastnar, introducera tilläggskonstruktioner (vilka lägger till nya noder i sökningen). Programmet hittade det självömsesidiga beviset genom att undvika tilläggskonstruktionen helt - en kortare väg fanns som den klassiska metoden missade.
Bevislängd & Bevis Sökning
Bevis sökning står inför samma exponentiella tillväxt som spelträesökning. Kanterna på varje nod motsvarar antalet tillämpliga inferensregler. Bevisdjupet ökar med theorem komplexitet.
Theorem-proving program använde heuristik för att pruna bevisrummet, liknande alphabeta-pruning i spel.
Punkter, Räta & Dualitet
Den geometriska programmet använder en perspektiv i sin självlikformighetsbevis för isosceles triangelsatsen som inte finns i klassiska euklidiska bevis. Insikten: istället för att jämföra triangeln ABC med en andra konstruerad triangel, jämför ABC med sig själv med basnoderna bytt - korrespondensen A↔A, B↔C, C↔B.
Detta är ett geometrisk symmetriargument: isosceles triangeln är symmetrisk under spegling längs höjden från toppen. Programmet byggde inte speglingen explicit; det använde korrespondensen som en abstraktion.
Den allmänna principen bakom detta är projektiv dualitet: i projektivplanet har varje sats om punkter & räta en dual sats som erhålls genom att byta ut orden 'punkt' och 'rät' genomgående.
Dualitetsordlista:
- Punkt ↔ Rät
- Punkt ligger på rät ↔ Rät går genom punkt
- Två punkter bestämmer en unik rät ↔ Två räta bestämmer en unik punkt
- Rät punkter ↔ Sammansatta räta
Ett enda bevis för en sats om punkter ger automatiskt ett bevis för den duala satsen om räta - och vice versa. De två bevisen har samma struktur, samma längd & samma inferenssteg. Att hitta den duala perspektivet avslöjar ofta en enklare bevis för den ursprungliga.
Användning av Dualitet
Desargues sats: Om två trianglar är perspektiviska från en punkt (de tre räta genom motsvarande hörn möts i en och samma punkt), så är de också perspektiviska från en linje (de tre snittpunkter för motsvarande sidor ligger på en och samma linje).
Detta sats är själv-dualt: byter man punkter och linjer ger det precis samma satsstatement.
Provfrekvens & Frekvensutrymme
Det datorbaserade musiksystemet på Bell Labs grundade sig på ett matematiskt teorem: Nyquist-Shannons provtagningsteorem.
Utlåtande: ett bandbegränsat signal med maximal frekvens f_max kan rekonstrueras perfekt från provtagningar taget på en hastighet av minst 2 × f_max prov per sekund.
Den geometriska tolkningen: ett bandbegränsat signal lever i ett ändligdimensionellt underrum av utrymmet för alla kontinuerliga funktioner. Provtagning på hastighet 2f_max ger noggrant koordinater för att unikt identifiera en punkt i det underrummet.
Aliasning: Geometrin för provtagningens misslyckande
Under Nyquistfrekvensen finns det frekvenser över f_max som aliaserar - de uppträder som lägre frekvenser i det proberade signalen. Två skilda signaler blir omöjliga att skilja efter probing. Geometriskt: proberingsoperatören projicerar signalutrymmet på ett lägre-dimensionellt utrymme, vilket gör att olika signaler kolliderar.
För digital ljud (CD-kvalitet): f_max = 22,050 Hz (lite över det 20,000 Hz som människans hörsel kan uthärma), proberingsfrekvens = 44,100 proberingar per sekund. För telefon: f_max = 4,000 Hz, proberingsfrekvens = 8,000 proberingar per sekund.
Beräkningar av Nyquistfrekvens
Nyquist satsen bestämmer den minsta proberingsfrekvens som behövs för att undvika informationstap.
Bevisutrymme & Signalutrymme: Delad Geometri
Beviset som stig och Nyquist-proberingssatsen delar en gemensam geometrisk struktur: både innebär att hitta den minsta representationen av något komplext.
Bevis minimization: hitta den kortaste vägen (fåsta inferenssteg) genom bevisgraphen från premisser till slutsats. Den självkongruens beviset minimerade vägens längd genom att utnyttja symmetri.
Signalprobing: hitta det minsta antalet prober (lägsta proberingshastighet) som bevarar alla uppgifter i en bandbegränsad signal. Nyquist satsen minimerar representationen genom att utnyttja bandbreddsgränser.
Båda problemen finns i rum med struktur som möjliggör minsta-representationresultat. Båda misslyckas när den här strukturen bryts: bevis blir längre när axiomrummet är dåligt organiserat; aliasing inträffar när signalen inte är bandbegränsad.