Formele Bewijzen als Paden
Een formeel bewijssysteem definieert een reeks axioma's & gevolgtrekkingsregels. Elk stelling-bewijsprogramma navigeert dit systeem als een zoekprobleem: beginnend met de gegeven premissen, past u gevolgtrekkingsregels toe om nieuwe uitspraken te genereren, totdat u het doel bereikt.
Stel dit voor als een gerichte grafiek:
Knooppunten: goed gevormde uitspraken in het formele systeem.
Randen: enkele toepassingen van gevolgtrekkingsregels (modus ponens, SAS-congruentie, enz.).
Bewijs: een gericht pad van de gegeven premissen tot de gewenste conclusie.
Bewijslengte: aantal gevolgtrekking stappen in het pad.
Het kortste bewijs van een stelling komt overeen met het kortste pad tussen het premisse-knooppunt & het conclusieknooppunt in deze grafiek.
Het meetkundestelling-bewijsprogramma verkende deze grafiek door: (1) directe toepassing van regels; (2) als vastgelopen, introductie van hulpconstructies (die nieuwe knooppunten aan de zoekopdracht toevoegen). Het programma vond het zelfcongruentie bewijs door de hulpconstructie geheel te vermijden — een korter pad bestond dat de klassieke aanpak had gemist.
Bewijslengte & Bewijszoeken
Bewijszoeken ondervindt dezelfde exponentiële groei als spelboomboomzoeken. De vertakkingsfactor op elk knooppunt is gelijk aan het aantal toepasselijke gevolgtrekkingsregels. Bewijsdiepte groeit met theoremcomplexiteit.
Het stelling-bewijsprogramma gebruikte heuristieken om de bewijsruimte in te korten, analoog aan alfa-bèta snoeien in spelletjes.
Punten, Lijnen & Dualiteit
Het bewijsprogramma van zelfcongruentie voor de gelijkbenige driehoeksstelling maakt gebruik van een perspectief dat niet in klassieke euclidische bewijzen voorkomt. Het inzicht: in plaats van driehoek ABC te vergelijken met een tweede geconstrueerde driehoek, vergelijkt u ABC met zichzelf met de basishoekpunten omgewisseld — de correspondentie A↔A, B↔C, C↔B.
Dit is een meetkundig symmetrie-argument: de gelijkbenige driehoek is symmetrisch onder reflectie over de hoogte van het toppunt. Het programma construeerde de reflectie niet expliciet; het gebruikte de correspondentie als een abstractie.
Het algemene principe achter dit is projectieve dualiteit: in het projectieve vlak heeft elke stelling over punten & lijnen een duaalstelling verkregen door de woorden 'punt' en 'lijn' overal in de stelling om te wisselen.
Dualiteitwoordenboek:
- Punt ↔ Lijn
- Punt ligt op lijn ↔ Lijn gaat door punt
- Twee punten bepalen een unieke lijn ↔ Twee lijnen bepalen een uniek punt
- Collineaire punten ↔ Concurrente lijnen
Een enkel bewijs van een stelling over punten geeft automatisch een bewijs van de duaalstelling over lijnen — en vice versa. De twee bewijzen hebben dezelfde structuur, dezelfde lengte, & dezelfde gevolgtrekking stappen. Het vinden van het duaalstandpunt onthult vaak een eenvoudiger bewijs van het origineel.
Dualiteit Toepassen
Desargues' Theorem: Als twee driehoeken in perspectief zijn van een punt (de drie lijnen door corresponderende hoekpunten ontmoeten elkaar in één punt), dan zijn ze in perspectief van een lijn (de drie snijpunten van corresponderende zijden liggen allemaal op één lijn).
Deze stelling is zelf-duaal: het omwisselen van punten en lijnen geeft precies dezelfde stellingverklaring.
Bemonsteringssnelheid & Frequentieruimte
Het computermuzieksysteem van Bell Labs rustte op één wiskundig theorema: de Nyquist-Shannon-bemonsteringsstelling.
Verklaring: een bandbegrensde signaal met maximale frequentie f_max kan perfect worden gereconstrueerd uit monsters genomen met een snelheid van minstens 2 × f_max monsters per seconde.
De meetkundige interpretatie: een bandbegrensde signaal leeft in een eindig-dimensionale deelruimte van de ruimte van alle continue functies. Bemonstering met snelheid 2f_max biedt genoeg coördinaten om een punt in die deelruimte uniek te identificeren.
Aliasing: De Meetkunde van Bemonsteringsfout
Beneden de Nyquist-snelheid worden frequenties boven f_max gealiast — zij verschijnen als lagere frequenties in het bemonsterde signaal. Twee verschillende signalen worden na bemonstering ononderscheidbaar. Meetkundig: de bemonsteringsoperator projecteert de signaalruimte op een lager-dimensionale ruimte, waardoor verschillende signalen botsen.
Voor digitale audio (CD-kwaliteit): f_max = 22.050 Hz (iets boven de 20.000 Hz grens van menselijk gehoor), bemonsteringssnelheid = 44.100 monsters/seconde. Voor telefoon: f_max = 4.000 Hz, bemonsteringssnelheid = 8.000 monsters/seconde.
Nyquist-Snelheidsberekeningen
De Nyquist-stelling bepaalt de minimale bemonsteringssnelheid die nodig is om informatieverlies te voorkomen.
Bewijsruimte & Signaalruimte: Gedeelde Meetkunde
Het bewijs-als-pad en de Nyquist-bemonsteringsstelling delen een gemeenschappelijke meetkundige structuur: beide gaan om het vinden van de minimale representatie van iets complexs.
Bewijsminimalisatie: zoek het kortste pad (minste gevolgtrekking stappen) door de bewijsgrafiek van premissen naar conclusie. Het zelfcongruentie bewijs minimaliseerde padlengte door symmetrie uit te buiten.
Signaalbemonstering: zoek het minimale aantal monsters (laagste bemonsteringssnelheid) dat alle informatie in een bandbegrensde signaal behoudt. De Nyquist-stelling minimaliseert de representatie door bandbegrenzingsgrenzen uit te buiten.
Beide problemen leven in ruimten met structuur die minimale-representatie-resultaten mogelijk maakt. Beide mislukken wanneer die structuur instort: bewijzen worden langer wanneer de axiomaruimte slecht georganiseerd is; aliasing treedt op wanneer het signaal niet bandbegrensde is.