主题
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.net.cn/SequentCalculus.html

学科分类