主題
Search

時序演算


時序(Sequent)是一個表示式 Gamma|-Lambda, 其中 GammaLambda 是(可能為空的)公式序列。這裡,Gamma 被稱為前件(antecedent),Lambda 被稱為後件(consequent)。對時序的非正式理解是,時序 A_1,...,A_n|-B_1,...,B_m 對應於 A_1 ^ ... ^ A_n superset B_1 v ... v B_m。所有推導的初始時序是

 A|-A.
(1)

時序演算的推理規則分為兩類:結構規則和邏輯規則。對於每個命題連線詞和每個量詞,至少有兩個邏輯規則;其中一個應用於前件,而另一個應用於後件。結構規則包括:弱化,

 (Gamma|-Lambda )/(A,Gamma|-Lambda )(Gamma|- )/(Gamma|-A ),
(2)

收縮,

 (A,A,Gamma|-Lambda )/(A,Gamma|-Lambda ),
(3)

交換,

 (Pi,A,B,Gamma|-Lambda )/(Pi,B,A,Gamma|-Lambda ),
(4)

和 cut 規則,

 (Gamma|-C;C,Pi|-Lambda )/(Gamma,Pi|-Lambda ).
(5)

邏輯規則由以下規則給出:合取,

 (Gamma|-A;Gamma|-B )/(Gamma|-A ^ B )(A,Gamma|-Lambda )/(A ^ B,Gamma|-Lambda )(B,Gamma|-Lambda )/(A ^ B,Gamma|-Lambda ),
(6)

析取,

 (A,Gamma|-Lambda;B,Gamma|-Lambda )/(A v B,Gamma|-Lambda )(Gamma|-A )/(Gamma|-A v B )(Gamma|-B )/(Gamma|-A v B ),
(7)

否定,

 (A,Gamma|- )/(Gamma|-¬A )(Gamma|-A )/(¬A,Gamma|- ),
(8)

蘊涵,

 (A,Gamma|-B )/(Gamma|-A superset B )(Gamma|-A;B,Pi|-Lambda )/(A superset B,Gamma,Pi|-Lambda ),
(9)

全稱量詞,

 (Gamma|-F(a) )/(Gamma|- forall xF(x) )(F(a),Gamma|-Lambda )/( forall xF(x),Gamma|-Lambda ),
(10)

和存在量詞

 (Gamma|-F(a) )/(Gamma|- exists xF(x) )(F(a),Gamma|-Lambda )/( exists xF(x),Gamma|-Lambda ).
(11)

這裡,變數 aF 中是自由的,並且 F(x) 是透過將 F(a) 中所有自由出現的 a 替換為 x 而獲得的。在  forall -後繼式規則和  exists -前件式規則中出現的變數 (a) 被稱為本徵變數。它不得出現在相應規則的下層時序中。

時序演算指定了經典一階邏輯,並且相同的框架也可以用於指定直覺邏輯。為了將推導限制為直覺邏輯,添加了額外的約束,即每個後繼式最多隻能有一個公式。根岑提出的經典(多後繼式)變體稱為 LK,直覺(單後繼式)變體稱為 LJ。LK 也可以被定義為單後繼式演算,並使用排中律作為另一個基本時序進行擴充。基於時序推理規則的證明理論也稱為根岑型。隨後引入了許多其他基於時序的邏輯公式。

SequentCalculus1

雙重否定提供了一個示例推導,它在時序演算的經典變體中有效,但在直覺變體中無效。

SequentCalculus2

上面顯示了第二個推導(這是一個有效的直覺推導)。

時序演算是證明論的一個非常有用的工具,主要是因為 cut 規則的可容許性,它可以從推導中消除,而不會影響可推導公式的集合。


另請參閱

Cut 消去定理

此條目由 Alex Sakharov (作者連結) 貢獻

使用 探索

參考文獻

Gentzen, G. The Collected Papers of Gerhard Gentzen (Ed. M. E. Szabo). Amsterdam, Netherlands: North-Holland, 1969.Kleene, S. C. Introduction to Metamathematics. Princeton, NJ: Van Nostrand, 1964.

在 上被引用

時序演算

請引用為

Sakharov, Alex. “時序演算。” 來自 —— 資源,由 Eric W. Weisstein 建立。 https://mathworld.tw/SequentCalculus.html

學科分類