切消定理 切消定理cutelimination theorem or Gentzens Hauptsatz是确立相继式演算重要性的主要结果它最初由格哈德根岑在他的划时代论文逻辑演绎研究对分别形式化直觉逻辑和经典逻辑的系统LJ和LK做的证明切削定理声称在相继式演算中拥有利用了切规则的证明的任何判断也拥有无切证明就是说不利用切规则的证明 相继式是与多个句子有关的逻辑表达式形式为 A  B  C    N  O  P displaystyle ABCldots vdash NOP 它可以被读做A B C  displaystyle ldots  证明N O P并且按Gentzen的注释应当被理解为等价于真值函数如果A  B  C  displaystyle ldots  那么N or O or P注意LHS左手端是合取and而RHS右手端是析取orLHS可以有任意多个公式在LHS为空的时候RHS是重言式在LK中RHS也可以有任意数目的公式如果没有则LHS是个矛盾而在LJ中RHS只能没有或有一个公式在右紧缩规则前面允许RHS有多于一个公式等价于容许排中律注意相继式演算是相当有表达力的框架已经为直觉逻辑提议了允许RHS有多个公式的相继式演算而来自JeanYves Girard的逻辑LC得到了RHS最多有一个公式的经典逻辑的更加自然的形式化逻辑和结构规则的相互作用是它的关键 切是在相继式演算的正规陈述中的一个规则并等价于在其他证明论中的规则变体给出   A  B     C displaystyle ABldots vdash C 和  C   D  E    displaystyle Cvdash DEldots  你可以推出   A  B      D  E    displaystyle ABldots vdash DEldots  就是说在推论关系中切掉公式C的出现 切消定理声称对于一个给定的系统使用切规则的任何相继式证明也可以不使用这个规则来证明如果我们认为  D  E    displaystyle DEldots  是一个定理则切消简单的声称用来证明这个定理的引理 C displaystyle C 可以被内嵌inline在这个定理的证明提及引理 C displaystyle C 的时候我们可以把它代换为 C displaystyle C 的证明因此切规则是可接纳的 对于用相继式公式化的系统分析性证明是不使用切规则的证明这种证明典型的会很长当然没有必要这么做在散文不要消除切呀中George Boolos展示了可以使用切在一页中完成的推导而它的分析性证明要耗尽宇宙的寿命来完成 这个定理有很多丰富的推论一旦一个系统被证明有切消定理这个系统通常立即就是一致的这个系统通常也有子公式性质这是达成证明论语义的重要性质切削是证明插值定理的最强力工具基于归结原理的完成证明查找的可能性导致Prolog编程语言的本质洞察依赖于在适当的系统中接纳切规则