Bukti Formal sebagai Jalur
Sistem bukti formal mendefinisikan satu set aksioma & aturan inferensi. Setiap program pembuktian teorema menavigasi sistem ini sebagai masalah pencarian: mulai dari premis yang diberikan, terapkan aturan inferensi untuk menghasilkan pernyataan baru, sampai Anda mencapai tujuan.
Wakili ini sebagai grafik berarah:
Node: pernyataan yang terbentuk dengan baik dalam sistem formal.
Tepi: penerapan tunggal dari aturan inferensi (modus ponens, kongruensi SAS, dll.).
Bukti: jalur berarah dari premis yang diberikan ke kesimpulan yang diinginkan.
Panjang bukti: jumlah langkah inferensi dalam jalur.
Bukti terpendek dari teorema sesuai dengan jalur terpendek antara node premis & node kesimpulan dalam grafik ini.
Program pembuktian teorema geometri menjelajahi grafik ini dengan: (1) penerapan langsung aturan; (2) jika terjebak, memperkenalkan konstruksi tambahan (yang menambahkan node baru ke pencarian). Program menemukan bukti kongruensi-diri dengan menghindari konstruksi tambahan sepenuhnya — jalur yang lebih pendek ada yang pendekatan klasik lewatkan.
Panjang Bukti & Pencarian Bukti
Pencarian bukti menghadapi pertumbuhan eksponensial yang sama dengan pencarian pohon permainan. Faktor percabangan pada setiap node sama dengan jumlah aturan inferensi yang dapat diterapkan. Kedalaman bukti tumbuh dengan kompleksitas teorema.
Program pembuktian teorema menggunakan heuristik untuk memangkas ruang bukti, analog dengan pemangkasan alfa-beta dalam permainan.
Titik, Garis & Dualitas
Bukti kongruensi-diri program geometri dari teorema segitiga sama kaki menggunakan perspektif yang tidak muncul dalam bukti Euclidean klasik. Wawasannya: alih-alih membandingkan segitiga ABC dengan segitiga konstruksi kedua, bandingkan ABC dengan dirinya sendiri dengan simpul dasar ditukar — korespondensi A↔A, B↔C, C↔B.
Ini adalah argumen simetri geometri: segitiga sama kaki simetris di bawah refleksi di seluruh ketinggian dari puncak. Program tidak membangun refleksi secara eksplisit; itu menggunakan korespondensi sebagai abstraksi.
Prinsip umum di balik ini adalah dualitas proyektif: dalam bidang proyektif, setiap teorema tentang titik & garis memiliki teorema dual yang diperoleh dengan menukar kata 'titik' dan 'garis' di seluruh.
Kamus dualitas:
- Titik ↔ Garis
- Titik terletak pada garis ↔ Garis melewati titik
- Dua titik menentukan garis unik ↔ Dua garis menentukan titik unik
- Titik kolinear ↔ Garis bersamaan
Bukti tunggal dari teorema tentang titik secara otomatis menghasilkan bukti dari teorema dual tentang garis — dan sebaliknya. Dua bukti memiliki struktur yang sama, panjang yang sama, & langkah inferensi yang sama. Menemukan perspektif dual sering mengungkapkan bukti yang lebih sederhana dari yang asli.
Menerapkan Dualitas
Teorema Desargues: Jika dua segitiga berada dalam perspektif dari titik (tiga garis melalui simpul yang sesuai semuanya bertemu di satu titik), maka mereka berada dalam perspektif dari garis (tiga persimpangan sisi yang sesuai semuanya terletak pada satu garis).
Teorema ini self-dual: menukar titik dan garis memberikan pernyataan teorema yang sama persis.
Laju Sampel & Ruang Frekuensi
Sistem musik komputer di Bell Labs didasarkan pada satu teorema matematika: teorema pengambilan sampel Nyquist-Shannon.
Pernyataan: sinyal terbatas band dengan frekuensi maksimal f_max dapat direkonstruksi dengan sempurna dari sampel yang diambil dengan laju setidaknya 2 × f_max sampel per detik.
Interpretasi geometri: sinyal terbatas band hidup dalam subruang berdimensi hingga dari ruang semua fungsi kontinu. Pengambilan sampel dengan laju 2f_max memberikan koordinat yang cukup untuk secara unik mengidentifikasi titik dalam subruang itu.
Aliasing: Geometri Kegagalan Pengambilan Sampel
Di bawah laju Nyquist, frekuensi di atas f_max alias — mereka muncul sebagai frekuensi yang lebih rendah dalam sinyal sampel. Dua sinyal berbeda menjadi tidak dapat dibedakan setelah pengambilan sampel. Secara geometris: operator pengambilan sampel memproyeksikan ruang sinyal ke ruang berdimensi lebih rendah, menyebabkan sinyal berbeda bertabrakan.
Untuk audio digital (kualitas CD): f_max = 22.050 Hz (sedikit di atas batas pendengaran manusia 20.000 Hz), laju sampel = 44.100 sampel/detik. Untuk telepon: f_max = 4.000 Hz, laju sampel = 8.000 sampel/detik.
Perhitungan Laju Nyquist
Teorema Nyquist menentukan laju pengambilan sampel minimum yang diperlukan untuk menghindari kehilangan informasi.
Ruang Bukti & Ruang Sinyal: Geometri Bersama
Bukti-sebagai-jalur dan teorema pengambilan sampel Nyquist berbagi struktur geometri umum: keduanya melibatkan pencarian representasi minimum dari sesuatu yang kompleks.
Minimalisasi bukti: temukan jalur terpendek (langkah inferensi paling sedikit) melalui grafik bukti dari premis ke kesimpulan. Bukti kongruensi-diri meminimalkan panjang jalur dengan memanfaatkan simetri.
Pengambilan sampel sinyal: temukan jumlah minimum sampel (laju pengambilan sampel terendah) yang menjaga semua informasi dalam sinyal terbatas band. Teorema Nyquist meminimalkan representasi dengan memanfaatkan batas bandwidth.
Kedua masalah hidup di ruang dengan struktur yang memungkinkan hasil minimum-representasi. Keduanya gagal ketika struktur itu rusak: bukti menjadi lebih panjang ketika ruang aksioma tidak terorganisir dengan baik; aliasing terjadi ketika sinyal tidak terbatas band.