Bukti Formal sebagai Jalur
Suatu sistem bukti formal menentukan sebuah set aturan dan aturan inferensi. Setiap program pembuktian menavigasi sistem ini sebagai masalah pencarian: mulai dari dugaan yang diberikan, aplikasikan aturan inferensi untuk menghasilkan pernyataan baru, hingga mencapai tujuan.
Wakil ini sebagai graf arah:
Node: pernyataan yang baik-baik dan terbentuk dalam sistem formal.
Edges: aplikasi tunggal aturan inferensi (modus ponens, SAS congruence, dll.).
Bukti: jalur arah dari dugaan yang diberikan ke konklusi yang diinginkan.
Panjang bukti: jumlah langkah inferensi dalam jalur.
Bukti pendek dari sebuah teorema berkorespondensi dengan jalur terpendek antara node dugaan dan node konklusi dalam graf ini.
Program geometri bukti ini menjelajahi graf ini dengan: (1) aplikasi langsung aturan; (2) jika terjebak, memperkenalkan konstruksi auxiliar (yang menambahkan node baru dalam pencarian). Program ini menemukan bukti selfcongruence dengan menghindari konstruksi auxiliar sepenuhnya - jalur yang lebih pendek ada yang klasik melewatkan.
Panjang Bukti & Pencarian Bukti
Pencarian bukti menghadapi pertumbuhan eksponensial yang sama seperti pencarian pohon permainan. Faktor cabang pada setiap node sama dengan jumlah aturan inferensi yang dapat diterapkan. Kekayaan bukti tumbuh dengan kompleksitas teorema.
Program pembuktian menggunakan heuristik untuk memangkas ruang bukti, analog dengan alpha-beta pruning dalam permainan.
Titik, Garis & Dualitas
Bukti keselarasan program geometri tentang teorema segitiga sama kaki menggunakan perspektif yang tidak muncul dalam bukti Euklides klasik. Kesadaran: daripada membandingkan segitiga ABC dengan segitiga kedua yang dibangun, bandingkan ABC dengan dirinya sendiri dengan posisi ujung dasar ditukar - korespondensi A↔A, B↔C, C↔B.
Ini adalah argumen simetri geometri: segitiga sama kaki simetri terhadap bayangan dari puncak. Program tidak membangun bayangan secara eksplisit; itu menggunakan korespondensi sebagai abstraksi.
Prinsip umum di balik ini adalah dualitas proyektif: di bidang proyektif, setiap teorema tentang titik & garis memiliki teorema dual yang diperoleh dengan menukar kata 'titik' dan 'garis' di seluruhnya.
Kamus dualitas:
- Titik ↔ Garis
- Titik terletak pada garis ↔ Garis melewati titik
- Dua titik menentukan garis unik ↔ Dua garis menentukan titik unik
- Titik sejajar ↔ Garis bersilangan
Satu bukti dari sebuah teorema tentang titik secara otomatis menghasilkan bukti teorema dual tentang garis - dan sebaliknya. Dua bukti memiliki struktur yang sama, panjang yang sama, & langkah inferensi yang sama. Menemukan perspektif dual seringkali mengungkapkan bukti sederhana dari yang asli.
Mengaplikasikan Dualitas
Teorema Desargues: Jika dua segitiga berada dalam perspektif dari titik (tiga garis melalui vertex yang sesuai semuanya bertemu di satu titik), maka mereka berada dalam perspektif dari garis (tiga interseksi dari sisi yang sesuai semuanya terletak di satu garis).
Ini adalah teorema yang dual: menukar titik dan garis memberikan teorema pernyataan yang sama.
Kecepatan Sampel & Ruang Frekuensi
Sistem musik komputer di Bell Labs didasarkan pada satu teorema matematika: teorema sampling Nyquist-Shannon.
Pernyataan: sinyal terbatas frekuensi yang dapat direkonstruksi sempurna dari sampel yang diambil dengan kecepatan setidaknya 2 × f_max sampel per detik.
Interpretasi geometris: sinyal terbatas frekuensi hidup dalam subspasial terbatas dimensi dari ruang semua fungsi kontinu. Sampel dengan kecepatan 2f_max memberikan cukup koordinat untuk unik mengidentifikasi titik dalam subspasial tersebut.
Aliasing: Geometri Kegagalan Sampel
Di bawah tingkat Nyquist, frekuensi di atas f_max alias - mereka muncul sebagai frekuensi yang lebih rendah dalam sinyal yang dianalisis. Dua sinyal yang berbeda tidak dapat dibedakan setelah sampling. Geometrisnya: operator sampling memroyalkan ruang sinyal ke ruang yang lebih rendah-dimensi, menyebabkan sinyal yang berbeda bertabrakan.
Untuk audio digital (kualitas CD): f_max = 22.050 Hz (sedikit di atas batas dengar manusia 20.000 Hz), tingkat sampling = 44.100 sampel/detik. Untuk telepon: f_max = 4.000 Hz, tingkat sampling = 8.000 sampel/detik.
Perhitungan Tingkat Nyquist
Teorema Nyquist menentukan tingkat sampling minimum yang diperlukan untuk menghindari kehilangan informasi.
Bukti Ruang & Ruang Sinyal: Geometri Bersama
Teorema sampling Nyquist dan bukti sebagai jalan membagi struktur geometris yang sama: keduanya melibatkan menemukan representasi minimum dari sesuatu yang kompleks.
Pemangkatan bukti: cari jalan terpendek (langkah inferensi terendah) melalui grafik bukti dari premis ke kesimpulan. Jalan terpendek bukti selfcongruence diperoleh dengan menjelajahi simetri.
Sampling sinyal: cari jumlah sampel terendah (pengurangan pengambilan sampel terendah) yang mempertahankan semua informasi dalam sinyal terbatas bandwidth. Teorema Nyquist meminimalkan representasi dengan menjelajahi batasan bandwidth.
Kedua masalah berada di ruang dengan struktur yang memungkinkan hasil representasi minimum. Kedua masalah gagal saat struktur tersebut rusak: bukti menjadi lebih lama saat ruang axiom tidak terorganisir dengan baik; aliasing terjadi saat sinyal tidak terbatasi bandwidth.