希尔伯特演绎系统

在希尔伯特风格演绎系统中，形式演绎是公式的有限序列，其中每个公式要么是个原子要么是从前面的公式通过推理规则而获得。这些形式演绎系统意图反映自然语言证明，尽管它们要更加详细。

假设${\displaystyle \Gamma }$ 是被当作假设的公式集合。例如${\displaystyle \Gamma }$ 可以是群论或集合论的公理集合。符号${\displaystyle \Gamma \vdash \phi }$ 意味着有只使用逻辑公理和${\displaystyle \Gamma }$ 的元素的结束于${\displaystyle \phi }$ 的一个演绎。因此，非形式的说${\displaystyle \Gamma \vdash \phi }$ 意味着假定了${\displaystyle \Gamma }$ 中的所有公式则${\displaystyle \phi }$ 是可证明的。

希尔伯特风格演绎系统可刻画为使用了众多逻辑公理模式。公理模式是把所有某种形式的公式代换成特定模式。不只是从这种模式生成的公理，还有这些公理之一的任何普遍化，都包括在逻辑公理集合中。公式的普遍化是通过在公式上前缀上零个或多个全称量词而获得的；因此

${\displaystyle \forall y(\forall xPxy\to Pty)}$ 

是${\displaystyle \forall xPxy\to Pty}$ 的普遍化。

逻辑公理

常见的希尔伯特风格的系统有六个无限公理模式和一个补充公理。为了简约公理模式的数目，这个系统假定所有公式都已经被重写为只使用连结词${\displaystyle \lnot }$ 和${\displaystyle \to }$ 并且只有量词${\displaystyle \forall }$ 。如下面所讨论的那样，可以把系统扩展为包括额外的逻辑连结词比如${\displaystyle \land }$ 和${\displaystyle \lor }$ ，而不扩大可演绎的公式类。

前三个逻辑公理模式（与肯定前件一起）允许操纵逻辑连结词。

1. ${\displaystyle \phi \to \left(\psi \to \phi \right)}$ 

2. ${\displaystyle \left(\phi \to (\psi \rightarrow \xi \right))\to \left(\left(\phi \to \psi \right)\to \left(\phi \to \xi \right)\right)}$ 

3. ${\displaystyle \left(\lnot \phi \to \lnot \psi \right)\to \left(\psi \to \phi \right)}$ 

后三个逻辑公理模式提供了增加、操纵和去除全称量词的方式。

4. ${\displaystyle \forall x\left(\phi \right)\to \phi [x:=t]}$ 这里的t可以代换在${\displaystyle \phi }$ 中x

5 ${\displaystyle \forall x\left(\phi \to \psi \right)\to \left(\forall x\left(\phi \right)\to \forall x\left(\psi \right)\right)}$ 

6 ${\displaystyle \phi \to \forall x\left(\phi \right)}$ 这里的x不是${\displaystyle \phi }$ 中的自由变量

需要最后的公理模式来处理涉及等号的公式。

1. ${\displaystyle x=x}$ 对于所有变量x
2. ${\displaystyle \left(x=y\right)\to \left(\phi [z:=x]\to \phi [z:=y]\right)}$ 

在希尔伯特风格的演绎系统中经常只包含对蕴涵和否定的公理。给定这些公理，有可能形成允许使用补充连结词的演绎定理的保守扩展。这些扩展被称为是保守的，因为如果涉及新连结词的公式φ被重写为只涉及否定、蕴涵和全称量词的逻辑等价的公式θ，则φ在扩展系统中是可导出的，当且仅当θ在最初系统中可导出的。在完全扩展的时候，希尔伯特风格的系统将非常类似于自然演绎系统。

由于希尔伯特风格系统有非常少的演绎规则，经常证明元定理来展示额外的演绎规则不增加演绎能力，在使用新演绎规则的演绎可以转换成只使用最初演绎规则的演绎的意义上。

一些常见的这种形式的元定理有：

• 演绎定理：${\displaystyle \Gamma ;\phi \vdash \psi }$ 当且仅当${\displaystyle \Gamma \vdash \phi \to \psi }$ 。
• ${\displaystyle \Gamma \vdash \phi \leftrightarrow \psi }$ 当且仅当${\displaystyle \Gamma \vdash \phi \to \psi }$ 并且${\displaystyle \Gamma \vdash \psi \to \phi }$ 。
• 对置（Contraposition）:如果${\displaystyle \Gamma ;\phi \vdash \psi }$ 则${\displaystyle \Gamma ;\lnot \psi \vdash \lnot \phi }$ 。
• 普遍化：如果${\displaystyle \Gamma \vdash \phi }$ 并且x不自由的出现在${\displaystyle \Gamma }$ 的任何公式中，则${\displaystyle \Gamma \vdash \forall x\phi }$ 。

公理1、2与演绎规则肯定前件对应于组合子逻辑的基础组合子K, S与应用的概念。参见Curry-Howard同构。

引用

来源

• Farmer, W. M. Propositional logic (PDF). （原始内容 (pdf)存档于2007-09-26）.  It describes (among others) a part of the Hilbert-style deduction system (restricted to propositional calculus).