Dowody Formalne jako Ścieżki
System dowodu formalnego definiuje zbiór aksjomatów & reguł wnioskowania. Każdy program udowadniający twierdzenia porusza się po tym systemie jako po problemie wyszukiwania: zaczynając od danych przesłanek, stosuje reguły wnioskowania aby generować nowe stwierdzenia, aż do osiągnięcia celu.
Reprezentuj to jako graf skierowany:
Węzły: poprawnie sformułowane stwierdzenia w systemie formalnym.
Krawędzie: pojedyncze zastosowania reguł wnioskowania (modus ponens, przystającość SAS, itp.).
Dowód: ścieżka skierowana od danych przesłanek do żądanego wniosku.
Długość dowodu: liczba kroków wnioskowania w ścieżce.
Najkrótszy dowód twierdzenia odpowiada najkrótszej ścieżce między węzłem przesłanki & węzłem wniosku w tym grafie.
Program dowodzenia twierdzeń geometrycznych badał ten graf przez: (1) bezpośrednie zastosowanie reguł; (2) jeśli się zatrzyma, wprowadzenie konstrukcji pomocniczych (które dodają nowe węzły do wyszukiwania). Program znalazł dowód samo-przystającości poprzez całkowite uniknięcie konstrukcji pomocniczej — istniała krótsza ścieżka, którą podejście klasyczne przegapiło.
Długość Dowodu & Wyszukiwanie Dowodu
Wyszukiwanie dowodu napotyka ten sam eksponencjalny wzrost co wyszukiwanie drzewa gry. Współczynnik rozgałęzienia w każdym węźle równy jest liczbie zastosowanych reguł wnioskowania. Głębokość dowodu rośnie wraz ze złożonością twierdzenia.
Program dowodzący twierdzeń używał heurystyk do przycinania przestrzeni dowodu, analogicznie do przycinania alfa-beta w grach.
Punkty, Linie & Dualność
Dowód samo-przystającości programu geometrycznego twierdzenia trójkąta równoramiennego używa perspektywy, która nie pojawia się w klasycznych dowodach euklidesowych. Wgląd: zamiast porównywać trójkąt ABC do drugiego skonstruowanego trójkąta, porównaj ABC do siebie z zamienionymi wierzchołkami podstawy — korespondencja A↔A, B↔C, C↔B.
To jest geometryczny argument symetrii: trójkąt równoramienny jest symetryczny pod refleksją wzdłuż wysokości z wierzchołka. Program nie skonstruował refleksji jawnie; użył korespondencji jako abstrakcji.
Ogólna zasada stojąca za tym jest dualność projektywna: w płaszczyźnie projektywnej, każde twierdzenie o punktach & liniach ma twierdzenie dualne uzyskane przez zamianę słów 'punkt' i 'linia' na całej długości.
Słownik dualności:
- Punkt ↔ Linia
- Punkt leży na linii ↔ Linia przechodzi przez punkt
- Dwa punkty wyznaczają unikalną linię ↔ Dwie linie wyznaczają unikalny punkt
- Punkty współliniowe ↔ Linie współbieżne
Jeden dowód twierdzenia o punktach automatycznie daje dowód dualnego twierdzenia o liniach — i odwrotnie. Dwa dowody mają tę samą strukturę, tę samą długość, & te same kroki wnioskowania. Znalezienie dualnej perspektywy często ujawnia prostszy dowód oryginału.
Stosowanie Dualności
Twierdzenie Desargues'a: Jeśli dwa trójkąty są w perspektywie z punktu (trzy linie przechodzące przez odpowiadające wierzchołki wszystkie spotykają się w jednym punkcie), to są w perspektywie z linii (trzy przecięcia odpowiadających boków wszystkie leżą na jednej linii).
To twierdzenie jest samo-dualne: zamiana punktów i linii daje dokładnie to samo stwierdzenie twierdzenia.
Częstotliwość Próbkowania & Przestrzeń Częstotliwości
System muzyki komputerowej w Bell Labs opierał się na jednym twierdzeniu matematycznym: twierdzeniu o próbkowaniu Nyquista-Shannona.
Stwierdzenie: sygnał z ograniczonym pasmem z maksymalną częstotliwością f_max można doskonale zrekonstruować z próbek pobranych z częstotliwością co najmniej 2 × f_max próbek na sekundę.
Interpretacja geometryczna: sygnał z ograniczonym pasmem żyje w skończonego wymiaru podprzestrzeni przestrzeni wszystkich funkcji ciągłych. Próbkowanie z częstotliwością 2f_max dostarcza wystarczająco wiele współrzędnych aby jednoznacznie zidentyfikować punkt w tej podprzestrzeni.
Aliasing: Geometria Niepowodzenia Próbkowania
Poniżej częstotliwości Nyquista, częstotliwości powyżej f_max aliasują — pojawiają się jako niższe częstotliwości w próbkowanym sygnale. Dwa odrębne sygnały stają się nierozróżnialne po próbkowaniu. Geometrycznie: operator próbkowania projektuje przestrzeń sygnału na przestrzeń niższego wymiaru, powodując kolizję różnych sygnałów.
Do cyfrowego audio (jakość CD): f_max = 22 050 Hz (nieco powyżej limitu słuchu człowieka 20 000 Hz), częstotliwość próbkowania = 44 100 próbek/sekundę. Do telefonii: f_max = 4 000 Hz, częstotliwość próbkowania = 8 000 próbek/sekundę.
Obliczenia Częstotliwości Nyquista
Twierdzenie Nyquista określa minimalną częstotliwość próbkowania potrzebną aby uniknąć utraty informacji.
Przestrzeń Dowodu & Przestrzeń Sygnału: Wspólna Geometria
Dowód-jako-ścieżka i twierdzenie o próbkowaniu Nyquista mają wspólną strukturę geometryczną: obie obejmują znalezienie minimalnej reprezentacji czegoś złożonego.
Minimalizacja dowodu: znajdź najkrótszą ścieżkę (najmniej kroków wnioskowania) na grafie dowodu od przesłanek do wniosku. Dowód samo-przystającości zminimalizował długość ścieżki poprzez wykorzystanie symetrii.
Próbkowanie sygnału: znajdź minimalną liczbę próbek (najniższą częstotliwość próbkowania) która zachowuje wszystkie informacje w sygnale z ograniczonym pasmem. Twierdzenie Nyquista minimalizuje reprezentację poprzez wykorzystanie limitów pasma.
Oba problemy żyją w przestrzeniach ze strukturą, która umożliwia wyniki minimalnej reprezentacji. Oba zawodzą, gdy ta struktura się rozpada: dowody stają się dłuższe, gdy przestrzeń aksjomatów jest źle zorganizowana; aliasing występuje, gdy sygnał nie ma ograniczonego pasma.