Formel kanılar yollar olarak
Bir formel kanıt sistemi, bir dizi aksiyom ve çıkarım kuralı tanımlar. Her teorem kanıtı programı bu sistemi bir arama sorunu olarak navigasyon yapar: verilen prensiplerden başlayarak, çıkarım kurallarını uygulayarak yeni ifadeler oluşturun, hedefe ulaşılıncaya kadar.
Bu durumu bir yönlendirilmiş grafik olarak temsil ediniz:
Düğüm: formel sistemin iyi formatlı ifadeleri.
Kenar: çıkarım kurallarının tek bir uygulaması (modus ponens, SAS kıvrımlılık vb.).
Kanıt: bu grafiğin prensip düğümünden sonuç düğümüne kadar yönlendirilmiş bir yol.
Kanıt uzunluğu: kanıtı oluşturan çıkarım adedidir.
Bir teoremin en kısa kanıtı, bu grafiğin en kısa yoluna karşılık gelir.
Geometri kanıt programı grafiği şu şekilde keşfetmiştir: (1) kuralları doğrudan uygulamak; (2) bloğa takılırsa yardımcı yapılar eklemek (bu arama için yeni düğüm ekler). Program, klasik yaklaşmayı tamamen atlayarak öz-kıvrımlı kanıtı buldu - daha kısa bir yol vardı ve klasik yaklaşım kaçırdı.
Kanıt Uzunluğu ve Kanıt Arama
Kanıt arama, oyun ağaç araması gibi aynı eksponansiyel büyümeyi karşı karşıya bırakır. Her düğümde uygulanan çıkarım kurallarının sayısı dal genişliği olarak kabul edilir. Teorem karmaşıklığıyla kanıt derinliği artar.
Teorem kanıtı programı, oyunlarda alpha-beta kestirme gibi heuristikler kullanarak kanıt alanını budamıştır.
Noklar, Çizgiler ve Düälite
Eğri programının, eşkenar üçgen teoremi için kendi perspektifini kullanan öz-kendiliğinden kanıtı, klasik Eukleid'li kanıtlarda görünmeyen bir perspektif kullanır. Keşif: ABC üçgenini, taban noktalarının yer değiştirdiği ikinci bir oluşturulan üçgenle karşılaştırmanın yerine, ABC'yi kendi itself ile karşılaştırın - taban noktalarının yer değiştirildiği - A↔A, B↔C, C↔B correspondence.
Bu, geometrik simetri bir argümandır: eşkenar üçgen, apiksten düşen yükseklik üzerinde yansıma ile simetriktir. Program, yansımayı açıkça oluşturmamış, correspondence'u bir soyutlama olarak kullandı.
Bu genel prensip, projektif düzlemde, noktalar ve çizgiler hakkındaki her teoremin, 'nok' ve 'çizgi' kelimelerini tümünde değiştirerek elde edilen ikili teorem vardır.
Düälite sözlüğü:
- Nok ↔ Çizgi
- Nok çizgi üzerinde yer alır ↔ Çizgi noktasından geçer
- İki nokta, benzersiz bir çizgi belirler ↔ İki çizgi, benzersiz bir nokta belirler
- Kenarlı nokta ↔ Keşir çizgi
Bir noktalara ve çizgilere ilişkin teorem için tek bir kanıt, aynı şekilde, aynı uzunlukta ve aynı inferans adımları olan çizgilere ilişkin otomatik olarak ikili teorem kanıtı sağlar. İki kanıt aynı yapıya sahiptir. İlk orijinalin daha basit bir kanıtı ortaya çıkarmak için, genellikle ikili perspektif bulmak gerekir.
Düälite Uygulaması
Desargues' Theorem: Eğer iki üçgen bir nokta üzerinden perspektifse (korespondans vertexlere giden üç çizgi bir noktada kesişiyorsa), o zaman bir çizgi üzerinden de perspektifse (korespondans kenarlarda kesişen üç nokta aynı çizgi üzerinde bulunur).
Bu teorem öz-düaldir: noktaları ve çizgileri değiştirerek aynı teorem açıklamasını elde edersiniz.
Sampling Rate & Frequency Space
Bell Labs bilgisayar müzik sistemi bir matematik teoreme dayanıyordu: Nyquist-Shannon örnekleme teoremi.
Açıklama: sınırlı frekanslı bir sinyal, en fazla frekansı f_max olan ve saniye başına en az 2 × f_max örnek alınabilir ve bu örnekler ile sinyal tam olarak yeniden yapılandırılabilir.
Geometrik açıklama: sınırlı frekanslı bir sinyal, tüm sürekli fonksiyonların uzayındaki sınırlı boyutlu bir alt uzayda yaşar. 2f_max hızı ile örneklem, o alt uzaydaki bir noktayı benzersiz bir şekilde tanımlamak için yeterli koordinat sağlar.
Aliasing: The Geometry of Sampling Failure
Nyquist frekansı altında, f_max'tan büyük frekanslar alias olur - örneklenecekler ve örneklenen sinyalde daha düşük frekanslarda görünür. İki farklı sinyal örnekleme sonrası ayırt edilemez. Geometrik olarak: örneklem operatori sinyal alanını daha düşük boyutlu bir alana projeler, farklı sinyalleri çarpışmaya neden olur.
Dijital ses (CD kalitesi) için: f_max = 22.050 Hz (insan duyusu sınırlarının biraz üzerinde 20.000 Hz), örneklem hızı = 44.100 örnek/saniye. Telefon için: f_max = 4.000 Hz, örneklem hızı = 8.000 örnek/saniye.
Nyquist Frekansı Hesaplamaları
Nyquist teoremi, bilgi kaybını önlemek için en düşük gerekli örneklem hızı belirler.
Düşük Boyutlu Geometri: İfade Alanı ve Sinyal Alanı
Örneklem teoremi ve kanıtın yolculuğu, her ikisi de karmaşık şeyin minimum temsilini elde etmek için ortak bir yapıya sahiptir: her ikisi de karmaşık şeyin minimum temsilini elde etmek için ortak bir yapıya sahiptir.
Düşük kanıt minimizasyonu: kanıtlar grafından prensiplerden sonuçlara en kısa yol (en az kanıt adımları) bulmak. Özsimetri kanıt minimizasyonu yol uzunluğunu simetriyi kullanarak optimize etti.
Sinyal örnekleme: en düşük sayıdaki örneklem (en düşük örnekleme hızı) kullanarak bandlimited bir sinyalin tüm bilgilerini korur. Nyquist teoremi, bant genişliği sınırlarını kullanarak temsilin en aza indirilmesini sağlar.
Her iki sorun da yapıların yapısını kullanarak minimum temsil sonuçları elde edebilecek yapılar üzerinde çalışır. O yapıların bozulduğu zamanlar: kanıtlar axioma alanının iyi düzenlenmemiş olduğu zaman uzar; alaşım oluşur sinyal bandlimited olmadığı zaman.