相继式演算
在证明论和数理逻辑中,相继式演算(又译矢列演算、矢列式演算、序贯演算)是一阶逻辑(和作为它的特殊情况的命题逻辑)、模态逻辑等逻辑的一类证明演算。第一个相继式演算由格哈德·根岑(Gerhard Gentzen)引入,作为研究自然演绎的工具;它的名字得来自德语的“Logischer Kalkül”,意思是“逻辑演算”。相继式演算系统有时被称为Gentzen系统,但使用时应避免与同为Gentzen发明的证明演算自然演绎混淆。自然演绎、公理系统和相继式演算是常见的证明演算。
相继式演算是逻辑研究的重要工具。许多逻辑学者会为其所研究的逻辑构造出一个或多个相继式演算,并研究其性质(如切消定理)。
介绍
分类不同风格的演绎系统的一种方式是查看在系统中“判断”的形式,就是说,什么事物可以作为(子)证明的结论出现。最简单的判断形式是用在希尔伯特演绎系统中的,这里的判断有形式
- ,
这个是一阶逻辑的任何公式(或演绎系统适用的任何逻辑,比如命题演算或高阶逻辑或模态逻辑)。定理出现为有效证明中结论判断。希尔伯特演绎系统不需要区分公式和判断;提及它只是为了和下面的情况做比较。
希尔伯特演绎系统的简单语法付出的代价是完整的形式证明变得非常长。在这种系统中的关于证明的具体论证总是求助于演绎定理。这导致了把演绎定理包括为系统中的形式规则的想法,这激发出了自然演绎。在自然演绎中,判断有形式
这里的和是公式并且。用语言表述,判断组成自十字转门符号“”左手端的公式(可能为空)列表与右手端的一个单一公式。定理是那些公式使得(带有空左手端)是一个有效证明的结论。(在某些自然演绎的介绍中,和十字转门是不明显写出来的,转而使用二维表示法)。
在自然演绎中判断的标准语义是断言只要[註 1] , 等都是真的,就也是真的。判断
- 与
是在任何一个的证明都可以扩展为另一个的证明的强烈意义上等价的。
最后,“相继式演算”推广了自然演绎的形式为
- ,
这个语法对象叫做相继式。再次和是公式,而和是非负整数,就是说左手端或右手端都可以为空或不空。如同自然演绎,定理是那些这里的是有效证明的结论。
相继式的标准语义是断言只要都是真的,“至少一个”也是真的。表达这个的一种方式是在十字转门左侧的逗号要被认为是“合取”,而在十字转门右侧的逗号要被认为是(包容性的)“析取”。相继式
- 与
是在任何一个的证明都可以扩展为另一个的证明的强烈意义上等价的。
在第一印象上,这种判断的扩展可能带来奇怪的复杂性—它不是由于自然演绎的有明显缺陷而激发来的,人们最初被逗号在十字转门的两侧完全意味着不同的事物搞糊涂了。但是观察到相继式的语义还可以(通过命题重言式)被表达为
在这种公式中,在十字转门两侧的公式间的唯一不同是在左侧的公式被否定了。因为对换相继式左右侧的公式对应于否定所有构成公式。这意味着对称性,如逻辑否定的德·摩根定律在语义层次上所显现的,直接转换到了相继式的左右对称—实际上,在相继式中处理合取()、的推理规则处理析取()的推理规则的镜像。
很多逻辑学家觉得这种对应的对称表述允许提供比其他证明系统在逻辑结构上的深刻洞察,这里的否定的对偶性不出现在规则中。
LK系统
在这个演算中的(形式)证明是一序列的相继式,这个的每个相继式使用下面的推理规则之一而推导自更早出现的相继式。
推理规则
将要使用下列符号:
- 和指示一阶谓词逻辑的公式(你也可以把它限制为命题逻辑),
- 、、和是有限的(可能为空)公式序列,也叫做上下文,
- 指示一个任意的项,
- 指示一个公式,在其中项的某个出现是我们感兴趣的
- 指示把在中的的指定出现代换为项,
- 和指示变量,
- 一个变量被称为在一个公式中自由出现,如果它只出现于不在量词或作用域内的公式中,
- 和表示弱化左/右,和表示紧缩左/右,而和表示排列左/右。
公理: | 切: |
|
|
左逻辑规则: | 右逻辑规则: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
限制:在规则和中,变量一定不能在或中自由出现。
左结构规则: | 右结构规则: |
|
|
|
|
|
|
直觉解释
上面的规则可以被分成两个主要群组:逻辑规则和结构规则。每个逻辑规则都在十字转门的左边或右边介入一个新的逻辑公式。相反的,结构规则操作在相继式的结构上,忽略公式的准确形状。这个一般模式的两个例外是同一性公理和规则切。
尽管是以形式方式陈述的,上述规则允许用经典逻辑的方式非常直觉的读出来。比如,考虑规则。它陈述了如果你能证明可以从包含的公式序列推导出来,则你也能证明自更强的假定,也就是成立。类似的,规则陈述了如果和足够推导出,则从单独的你可以要么仍然推导出要么必然为假,就是说成立。所有规则都可以用这种方式来解释。
对于量词规则的直觉解释,考虑规则。当然只从为真的事实推导出成立一般是不可能的。但是如果变量在其他地方没有被提及(就是说,它仍可以被自由的选择,而不影响其他公式),则你可以假定,对的任何值都成立。其他规则应当是非常直接的。
不再把规则看作是对在谓词逻辑中合法的推导的描述,你还可以把它们当作为给定陈述构造一个证明的指导。在这种情况下规则可以自底向上的读。例如,声称要证明推导自假定和,分别证明可以推导自和可以推导自就足够了。注意,给顶某个前件,如何分解成和是不明确的。但是,只有有限多的可能需要检查,因为前件被假定为是有限的。这也展示了证明论如何被看作是以组合方式在证明的操作:给定对和二者的证明,你可以构造一个对的证明。
在查找某个证明的时候,多数规则提供或多或少的如何做的处方。切规则是不同的:它声称,在公式可以被推导出来,并且这个公式也可以充当推导其他公式的前提的时候,则公式可以被"切掉"并把各自的推导连接起来。在自底向上构造一个证明的时候,这产生了猜测的问题(因为它在下面根本就没有出现)。这个问题在切消定理中处理。
第二个规则有某种特殊性,它就是同一性公理。明显的直觉读为:证明。
例子推导
作为一个例子,下面是叫做排中律(拉丁语tertium non datur)的的序列推导。
这个推导还强调了语法演算的严格形式结构。例如,上述定义的右逻辑规则总是作用于右相继式的第一个公式,这使得的应用在形式上是需要的。这种非常严格的推理开始时可能难于理解,但是它形成了在形式逻辑中语法和语义之间非常核心的区别。尽管我们知道和有相同的意义,对后者的推导将不等价于上面给出的那个。但是,你可以通过介入引理而使语法推理更加方便些,就是说,预定义完成特定标准推导的方案。作为一个例子,你可以证明下列是一个合法的变换:
一旦已知一个一般的规则序列要建立这种推导,你可以使用它作为证明内的缩写。但是,当证明使用了好的引理而变得更加易读的时候,也使得推导的过程更加复杂,因为有更多可能的选择要考虑。在使用证明论(经常需要)作为自动演绎的时候这特别重要。
变体
上述规则可以以各种方式修改:
次要结构变更
有些修改不改变系统的本质。所有这些修改都仍可以叫做系统。
首先,如上面提及的,相继式可以被看做由集合或多重集组成。在这种情况下,排列和(在使用集合的时候)紧缩公式的规则就可以废弃了。
弱化规则也变成是可接纳的了,在公理被变更的时候,使得形如的任何相继式都可以被得出。这意味着在任何上下文中证明。在推导中的任何弱化因此可以在开始处正确的进行。在自底向上构造证明的时候这是个方便的变更。
独立于这些修改,你还可以在规则内上下文被分割的方式:在、和的情况下,在向上走的时候,左上下文被以某种方式分割成和。因为紧缩允许它们的重复,你可以假定全部上下文在两个推导分支中都使用。通过这么做,你能确保没有重要的前提在错误的分支中被丢失。使用弱化,上下文中无关的部分以后可以被消去。
所有这些改变生成等价的系统,这是在LK中的所有推导可以有效的变换因使用了替代规则的推导反之亦然的意义上。
注释
- 这里的“只要”是如下的非正式略写“对值到判断中的自由变量的所有指派”。
参考文献
- Girard, Jean-Yves; Taylor, Paul; Lafont, Yves. . Cambridge University Press(Cambridge Tracts in Theoretical Computer Science, 7). 1990 [1989] [2006-07-19]. ISBN 978-0-521-37181-0. (原始内容存档于2016-07-04).