希尔伯特演绎系统

在逻辑特别是数理逻辑中，希尔伯特风格演绎系统是归功于弗雷格和希尔伯特的一类形式演绎系统。这种演绎系统最经常为一阶逻辑而研究，但对其他逻辑也是有价值的。

所有演绎系统都在逻辑公理和推理规则之间作出取舍平衡。 希尔伯特风格的演绎系统可以刻画为选择了大量的逻辑公理模式和少量的推理规则。最常研究的希尔伯特风格演绎系统只有一个推理规则即肯定前件和几个无限公理模式。

自然演绎系统做了相反的取舍，包括了很多演绎规则但有非常少甚至没有公理模式。

形式定义

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

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

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

$\forall y ( \forall x Pxy \to Pty)$

是 $\forall x Pxt \to Pty$ 的普遍化。

逻辑公理

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

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

1. $\phi \to \left( \psi \to \phi \right)$

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

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

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

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

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

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

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

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

保守扩展

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

元定理

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

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

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

进一步联系

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

引用

• Curry, Haskell B.; Robert Feys. Combinatory Logic Vol. I 1. Amsterdam: North Holland. 1958. 
• Monk, J. Donald. Mathematical Logic. Springer-Verlag. 1976. 
• Ruzsa, Imre; Máté, András. Bevezetés a modern logikába. Budapest: Osiris Kiadó. 1997 （Hungarian）. 
• Tarski, Alfred. Bizonyítás és igazság. Budapest: Gondolat. 1990 （Hungarian）.  It is a Hungarian translation of Alfred Tarski's selected papers on semantic theory of truth.

外部链接

Farmer, W. M. Propositional logic (pdf).  It describes (among others) a part of the Hilbert-style deduction system (restricted to propositional calculus).