跳至內容

構造演算

維基百科,自由的百科全書

構造演算(CoC)是高階有類型 lambda 演算,這裏的類型一級值。因此在 CoC 內有可能定義從整數到類型、從類型到類型的函數,同從整數到整數的函數一樣。CoC 是強規範化的。

CoC 最初由 Thierry Coquand 開發。

CoC 是 Coq 定理證明器早期版本的基礎;它後來的版本建造在歸納構造演算之上,這是帶有對歸納數據類型的天然支持的 CoC 擴展。在最初的 CoC 中,歸納數據類型必須模擬為它們的多態解構函數。

構造演算的基礎

[編輯]

構造演算可以被當作 Curry-Howard同構的擴展。Curry-Howard 同構把在簡單類型 lambda 演算中項關聯上在直覺命題邏輯中自然演繹證明。構造演算擴展了這個同構為在完全的直覺謂詞邏輯中的證明,這包括了量化陳述(它也叫做"命題")的證明。

[編輯]

在構造演算中使用如下規則構造:

  • T 是項(也叫做類型
  • P 是項(也叫做命題,所有命題的類型)
  • 變量 是項
  • 如果 是項,則如下也是項
    • ()
    • ()

構造演算有 5 種對象類型:

  1. 證明,它是其類型都是命題的那些項
  2. 命題,也叫做小類型
  3. 謂詞,它是返回命題的函數
  4. 大類型,它是謂詞的類型。(P 是大類型的例子)
  5. T 自身,它是大類型的類型。

判斷

[編輯]

在構造演算中,判斷是類型推理:

它可以被讀作蘊涵

如果變量 分別有類型 ,則項 有類型

構造演算的有效判斷是從推理規則集合可推導的。在下面,我們使用 來指示類型指派的序列 ,並使用 K 來指示要麼 P 要麼 T。我們將寫 來指示「 有類型 ,和 有類型 」。我們將寫 來指示用項 代換在項 中變量 的結果。

推理規則用如下形式寫成



它指示着

如果 是有效判斷,則 也是。

構造演算的推理規則

[編輯]






定義邏輯運算

[編輯]

構造演算在引入基本算子的時候是非常簡約的:唯一形成命題的邏輯算子是 。但是,這個唯一的算子足夠定義所有其他邏輯算子:

定義數據類型

[編輯]

在構造演算中可以定義計算機科學中使用的基本數據類型:

布爾
自然數
乘積
不交並

參見

[編輯]

引用

[編輯]