証明支援プログラム
HOL Lightは、古典的な 高階論理 のための 証明支援システム です。HOL 定理証明器ファミリー の一員です 。他のHOLシステムと比較して、HOL Lightは比較的シンプルな基礎を持つことが意図されています。HOL Lightは、数学者でありコンピュータ科学者でもあるジョン・ハリソンによって開発・保守されています。HOL Lightは、 簡易BSDライセンス の下でリリースされています。 [1]
論理的根拠 HOL Lightは、等式を唯一の 基本概念とする 型理論 の定式化に基づいています 。基本的な推論規則は次のとおりです。
⊢ t ＝ t {\displaystyle {\cfrac {\qquad }{\vdash t=t}}} 反射 平等の反射性 Γ ⊢ s ＝ t Δ ⊢ t ＝ あなた Γ ∪ Δ ⊢ s ＝ あなた {\displaystyle {\cfrac {\Gamma \vdash s=t\qquad \Delta \vdash t=u}{\Gamma \cup \Delta \vdash s=u}} トランス 等式の推移性 Γ ⊢ f ＝ グラム Δ ⊢ × ＝ y Γ ∪ Δ ⊢ f （ × ） ＝ グラム （ y ） {\displaystyle {\cfrac {\Gamma \vdash f=g\qquad \Delta \vdash x=y}{\Gamma \cup \Delta \vdash f(x)=g(y)}}} MK_COMB 平等の合同 Γ ⊢ s ＝ t Γ ⊢ （ λ × 。 s ） ＝ （ λ × 。 t ） {\displaystyle {\cfrac {\Gamma \vdash s=t}{\Gamma \vdash (\lambda xs)=(\lambda xt)}}} ABS 平等の抽象化（ 自由であってはならない ） × {\displaystyle x} Γ {\displaystyle \Gamma} ⊢ （ λ × 。 t ） × ＝ t {\displaystyle {\cfrac {\qquad }{\vdash (\lambda xt)x=t}}} ベータ 抽象化と関数適用の接続 { p } ⊢ p {\displaystyle {\cfrac {\qquad }{\{p\}\vdash p}}} 仮定する 仮定して 証明する p {\displaystyle p} p {\displaystyle p} Γ ⊢ p ＝ q Δ ⊢ p Γ ∪ Δ ⊢ q {\displaystyle {\cfrac {\Gamma \vdash p=q\qquad \Delta \vdash p}{\Gamma \cup \Delta \vdash q}}} EQ_MP 平等と演繹の関係 Γ ⊢ p Δ ⊢ q （ Γ − { q } ） ∪ （ Δ − { p } ） ⊢ p ＝ q {\displaystyle {\cfrac {\Gamma \vdash p\qquad \Delta \vdash q}{(\Gamma -\{q\})\cup (\Delta -\{p\})\vdash p=q}}} 反象徴ルールを控除する 双方向の演繹可能性から等式を演繹する Γ [ × 1 、 … 、 × n ] ⊢ p [ × 1 、 … 、 × n ] Γ [ t 1 、 … 、 t n ] ⊢ p [ t 1 、 … 、 t n ] {\displaystyle {\cfrac {\Gamma [x_{1},\ldots ,x_{n}]\vdash p[x_{1},\ldots ,x_{n}]}{\Gamma [t_{1},\ldots ,t_{n}]\vdash p[t_{1},\ldots ,t_{n}]}}} INST 定理の仮定と結論における変数を具体化する Γ [ α 1 、 … 、 α n ] ⊢ p [ α 1 、 … 、 α n ] Γ [ τ 1 、 … 、 τ n ] ⊢ p [ τ 1 、 … 、 τ n ] {\displaystyle {\cfrac {\Gamma [\alpha _{1},\ldots ,\alpha _{n}]\vdash p[\alpha _{1},\ldots ,\alpha _{n}]}{\Gamma [\tau _{1},\ldots ,\tau _{n}]\vdash p[\tau _{1},\ldots ,\tau _{n}]}}} INST_TYPE 定理の仮定と結論において型変数をインスタンス化する
この型理論の定式化は、Lambek & Scott (1986) のセクション II.2 で説明されているものと非常に近いです。
参考文献 ^ “Jrh13/Hol-light”. GitHub . 2021年10月13日.
さらに読む Freek Wiedijk (2008年12月)、「形式証明 — 入門」 (PDF) 、 アメリカ数学会誌 、 55 (11): 1408–1414 、 2008年12月14日 閲覧
外部リンク
![{\displaystyle {\cfrac {\Gamma [x_{1},\ldots ,x_{n}]\vdash p[x_{1},\ldots ,x_{n}]}{\Gamma [t_{1},\ldots ,t_{n}]\vdash p[t_{1},\ldots ,t_{n}]}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a6a015bd670b5703c8656815de6b95ad2eaa634)
![{\displaystyle {\cfrac {\Gamma [\alpha _{1},\ldots ,\alpha _{n}]\vdash p[\alpha _{1},\ldots ,\alpha _{n}]}{\Gamma [\tau _{1},\ldots ,\tau _{n}]\vdash p[\tau _{1},\ldots ,\tau _{n}]}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca98e3cf888649f74a8c490f9e770e2585302052)
