Dowody Formalne jako Ścieżki
System dowodzenia formalnego definiuje zestaw aksjomatów & reguł inferencyjnych. Każde programy dowodzenia navigują tym systemem jako problem wyszukiwania: zaczynając od podstawowych założeń, stosując reguły inferencyjne, aby wygenerować nowe deklaracje, aż dotrą do celu.
Oto to przedstawia jako skierowany graf:
Węzły: poprawne deklaracje w formalnym systemie.
Krawędzie: pojedyncze zastosowanie reguł inferencyjnych (modus ponens, SAS sprzężenie itp.).
Dowód: skierowana ścieżka od podstawowych założeń do pożądanego wniosku.
Długość dowodu: liczba kroków inferencyjnych w ścieżce.
Krótki dowód twierdzenia odpowiada krótkiej ścieżce między węzłem założenia a węzłem wniosku w tym grafie.
Program dowodzenia geometrii zbadawał ten graf poprzez: (1) bezpośrednie zastosowanie reguł; (2) jeśli zatrzymuje się, wprowadzenie dodatkowych konstrukcji (co dodaje nowe węzły do wyszukiwania). Program znalazł dowód samosprzężenia, unikając dodatkowej konstrukcji - krótsza ścieżka istniała, którą klasyczne podejście pomijało.
Długość Dowodu & Wyszukiwanie Dowodów
Wyszukiwanie dowodów staje przed tym samym wzrostem eksponencjalnym, co wyszukiwanie w drzewie gry. Przestawka stosunkowa na każdym węźle równa się liczbie zastosowalnych reguł inferencyjnych. Głębokość dowodu rośnie z złożonością twierdzenia.
Program dowodzenia geometrii używał heurystyk do obcięcia przestrzeni dowodzenia, podobnie jak alpha-beta w grach.
Punkty, Linie & Dualność
Dowód samodwużystwa programu geometrii dowodu teoremy trójkąta ozsajnych używa perspektywy, która nie pojawia się w klasycznych dowodach euklidesowych. Przemyśl: zamiast porównywać trójkąt ABC z drugim konstrukowanym trójkątem, porównaj ABC z samym sobą, zamieniając wierzchołki podstawy - korespondencja A↔A, B↔C, C↔B.
To jest argument symetrii geometrycznej: trójkąt ozsajnych jest symetryczny względem odbicia od wierzchołka szczytowego. Program nie konstruował odbicia wyraźnie; użył korespondencji jako abstrakcji.
Powszechna zasadnicza zasada za tą jest dualność projekttywna: w płaszczyźnie projekttywnej każde twierdzenie o punktach & liniach ma dualne twierdzenie, uzyskane przez zamianę słów 'punkt' i 'linia' w całym.
Słownik dualności:
- Punkt ↔ Linia
- Punkt należący do linii ↔ Linia przechodzi przez punkt
- Dwa punkty określają jednoznacznie linię ↔ Dwa linie określają jednoznacznie punkt
- Punkty prostej ↔ Przeciwnie linie
Jeden dowód twierdzenia o punktach automatycznie wydaje dowód dualnego twierdzenia o liniach - i na odwrót. Dwa dowody mają tę samą strukturę, tę samą długość & te same kroki inferencyjne. Znalezienie perspektywy dualnej często odkrywa prostszy dowód pierwotnego.
Zastosowanie Dualności
Teorema Desargues: Jeśli dwa trójkąty są względem punktu w perspektywie (trzy przecinające się linie przez odpowiednie węzły spotykają się w jednym punkcie), to są względem linii w perspektywie (trzy przecięcia odpowiednich boków leżą na jednej linii).
To teorema jest samo-dualne: zamiana punktów i linii daje dokładnie tę samą deklarację teoremu.
Sampling Rate & Frequency Space
System muzyczny komputerowy w Bell Labs opierał się na jednym twierdzeniu matematycznym: twierdzeniu próbowania Nyquist-Shannona.
Deklaracja: sygnał ograniczony pasmem z maksymalną częstością f_max można doskonale odbudować na podstawie prób pobranych z szybkością co najmniej 2 × f_max prób sekundę.
Interpretacja geometryczna: sygnał ograniczony pasmem istnieje w przestrzeni ograniczonej wymiarem w przestrzeni wszystkich funkcji ciągłych. Probowanie z szybkością 2f_max dostarcza wystarczających współrzędnych do jednoznacznego zidentyfikowania punktu w tej przestrzeni.
Aliasing: Geometry próbnej niepowodzenia
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ę nieodróżnialne po próbkowaniu. Geometrycznie: operator próbkowania projkuje przestrzeń sygnałów na niższy wymiar przestrzenny, powodując, że różne sygnały zderzają się.
Dla cyfrowego dźwięku (jakość CD): f_max = 22,050 Hz (nieco powyżej granicy słyszalności człowieka 20,000 Hz), szybkość próbkowania = 44,100 prób/sekund. Dla telefonu: f_max = 4,000 Hz, szybkość próbkowania = 8,000 prób/sekund.
Obliczenia Częstotliwości Nyquista
Teoria Nyquista określa minimalną szybkość próbkowania potrzebną, aby uniknąć utraty informacji.
Dowód Przestrzeni i Sygnału: Udzielona Geometria
Teoria próbkowania Nyquista i dowód jako ścieżka mają wspólną strukturę geometryczną: oba dotyczą minimalnej reprezentacji czegoś złożonego.
Minimalizacja dowodu: znajdź najkrótszą ścieżkę (mniej kroków dedukcyjnych) przez graf dowodowy od przesłanek do wniosku. Ścieżka minimalizująca dowód samosprawiedliwości wykorzystuje symetrię.
Probka sygnału: znajdź minimalną liczbę próbek (najniższą szybkość próbkowania), która zachowuje wszystkie informacje w sygnale o ograniczonym pasmościu. Teoria Nyquista minimalizuje reprezentację wykorzystując ograniczenia pasma.
Oba problemy występują w przestrzeniach z strukturą, która umożliwia wyniki minimalnej reprezentacji. Oba zawodzą, gdy ta struktura ulega zakłóceniom: dowody stają się dłuższe, gdy przestrzeń aksjomatów jest źle zorganizowana; aliasing występuje, gdy sygnał nie jest ograniczony pasmem.