English· Español· Deutsch· Nederlands· Français· 日本語· ქართული· 繁體中文· 简体中文· Português· Русский· العربية· हिन्दी· Italiano· 한국어· Polski· Svenska· Türkçe· Українська· Tiếng Việt· Bahasa Indonesia

un

ゲスト
1 / ?

形式的証明の道として

形式的証明システムは公理と推論規則の集合を定義します。定理証明プログラムはこのシステムを検索問題として進みます。与えられた前提から始まり、推論規則を適用して新しいステートメントを生成し、目標に到達するまで進みます。

これを有向グラフとして表現してください:

ノード:形式的システムの整形された文。

エッジ:推論規則の単一の適用(三段論法、SAS合同など)。

証明:与えられた前提から目的の結論への有向パス。

証明長:パス内の推論ステップ数。

定理の最短証明は、このグラフにおける前提ノードと結論ノード間の最短パスに対応します。

公理空間における道としての証明

幾何定理証明プログラムはこのグラフを以下の方法で探索しました:(1) 規則の直接適用。(2) 行き詰まった場合は補助構成を導入(検索に新しいノードを追加)。プログラムは補助構成を完全に回避することで自己合同証明を発見しました。古典的なアプローチが見逃した、より短いパスが存在していたのです。

証明長と証明探索

証明探索はゲーム木探索と同じ指数的成長に直面します。各ノードの分岐係数は適用可能な推論規則の数に等しいです。証明の深さは定理の複雑さとともに増加します。

定理証明プログラムは、ゲームのアルファベータプルーニングに類似した、証明空間を削減するためのヒューリスティックを使用しました。

形式的幾何システムが各ステップで12個の適用可能な推論規則を持つとします。証明を探索しているとき、二等辺三角形定理の古典的な証明は3ステップ(与えられた→構成→SAS→結論)を必要とします。プログラムの証明は2ステップ(与えられた→自己合同→結論)を必要とします。証明を見つける前の最悪の場合に、各長さのパスで探索する必要がある数を計算してください。2ステップの探索空間は3ステップの探索空間と比べてどの程度小さいですか?

点、直線と双対性

幾何プログラムの二等辺三角形定理の自己合同証明は、古典的なユークリッド証明には表れない視点を使用しています。洞察:三角形ABCを別の構成された三角形と比較するのではなく、ABCを底の頂点が入れ替わった自身と比較します。つまり、対応はA↔A、B↔C、C↔Bです。

これは幾何学的対称性論証です:二等辺三角形は頂点からの高さに関して反射対称です。プログラムは反射を明示的に構成しませんでした。対応を抽象化として使用しました。

この背後にある一般的な原則は射影双対性です:射影平面では、点と直線についてのすべての定理は、文全体で「点」と「直線」という単語を入れ替えることで得られた双対定理を持っています。

双対辞書:

- 点 ↔ 直線

- 点が直線上にある ↔ 直線が点を通過する

- 2つの点が一意の直線を決定する ↔ 2つの直線が一意の点を決定する

- 共線点 ↔ 同時点線

定理についての単一の証明は、自動的にその双対定理についての証明を生成します。つまり、直線についての定理です。2つの証明は同じ構造、同じ長さ、同じ推論ステップを持っています。双対の視点を見つけることは、しばしば元の定理のより単純な証明を明らかにします。

双対性の適用

デザルグの定理:2つの三角形が1つの点から透視されている場合(対応する頂点を通る3つの直線がすべて1つの点で合う)、それらは1つの直線から透視されています(対応する辺の3つの交点がすべて1つの直線上にある)。

この定理は自己双対です:点と直線を入れ替えると、まったく同じ定理のステートメントが得られます。

次の定理の双対を述べてください:「3つの点は共線です。かつ、それらのうちのどの2つも別個の直線ではありません。」待ってください。そのステートメントは形式が悪いです。代わりに、次を考えてください:「任意の2つの異なる点は正確に1つの直線を決定します。」点と直線を入れ替えることで、双対定理を述べてください。次に、双対定理が射影平面で真であるかどうかを述べてください。そして簡潔な理由を与えてください。

標本化レートと周波数空間

ベル研究所のコンピュータ音楽システムは、1つの数学定理に基づいていました。ナイキスト・シャノン標本化定理です。

ステートメント:最大周波数f_maxでバンド制限された信号は、少なくとも2×f_max標本/秒の速度で取られた標本から完全に再構成できます。

幾何学的解釈:バンド制限された信号は、すべての連続関数の空間の有限次元部分空間に存在します。レート2f_maxで標本化すると、その部分空間内の点を一意に識別するのに十分な座標が提供されます。

エイリアシング:標本化失敗の幾何学

ナイキストレート未満では、f_max上の周波数はエイリアシングします。標本化された信号ではより低い周波数として表れます。2つの異なる信号は標本化後に区別できなくなります。幾何学的に:標本化演算子は信号空間をより低次元の空間に投影し、異なる信号を衝突させます。

デジタルオーディオ(CD品質):f_max = 22,050 Hz(人間の聴覚限度の20,000 Hzわずかに上)、標本化レート = 44,100標本/秒。電話:f_max = 4,000 Hz、標本化レート = 8,000標本/秒。

ナイキストレート計算

ナイキスト定理は、情報損失を避けるために必要な最小標本化レートを決定します。

インターネット音声システムが8,000 Hzまでの音声を再現する必要があります。必要な最小標本化レートはいくつですか?次に、このレートで5分のオーディオを16ビット標本(65,536量子化レベル)で保存するのに、記録にはいくつのバイトが必要ですか?すべての計算を表示してください。

証明空間と信号空間:共有幾何学

道としての証明とナイキスト標本化定理は共通の幾何学的構造を共有しています。両方とも複雑なものの最小表現を見つけることが含まれます。

証明最小化:前提から結論への証明グラフを通して最短パス(最も少ない推論ステップ)を見つけます。自己合同証明は対称性を利用することにより、パスの長さを最小化しました。

信号標本化:バンド制限された信号のすべての情報を保存する最小数の標本(最も低い標本化レート)を見つけます。ナイキスト定理は帯域幅制限を利用することにより、表現を最小化します。

両方の問題は、最小表現結果を有効にする構造を持つ空間に存在します。両方ともその構造が崩れるときに失敗します。証明グラフの接続性が悪く組織化されている場合、証明はより長くなります。信号がバンド制限されていない場合、エイリアシングが発生します。

証明最小化と信号標本化は、最小表現を達成するための基礎的な構造的特性を利用しています。証明の場合、構造は証明グラフの接続性です。信号の場合、構造はバンド制限性です。基礎的な構造的特性のために最小表現結果が存在する別の領域を特定してください。構造、表現、および最小結果の内容を名前を付けてください。