希尔伯特演绎系统

✍ dations ◷ 2025-07-30 13:53:20 #证明论,逻辑演算

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

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

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

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

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

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

x P x y P t y {\displaystyle \forall xPxy\to Pty} 的普遍化。

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

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

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

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

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

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

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

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

相关

  • 千年人图根原人(Orrorin tugenensis),又名千年人、千禧猿或土根猿,是已知最古老与人类有关的人族祖先,是原人属(或称千年人属)中的唯一种。种小名是以其化石发现地肯雅的图根山区命名。利
  • 吉野彰吉野彰(日语:吉野 彰/よしの あきら Yoshino Akira ?,1948年1月30日-),日本化学家,福井谦一的再传弟子,现任旭化成研究员、名城大学教授。紫绶褒章表彰。吉野是现代锂离子电池(LIB)的
  • 冷暗物质冷暗物质(英语:Cold Dark Matter,简称CDM)是大爆炸理论在改善的过程中加入的新材料,这种物质在宇宙中不能用电磁辐射来观测,因此是暗的;同时这种微粒的移动是缓慢的,因此是冷的。在2
  • 心物问题心物问题(英语:Mind–body problem),又译为心身问题、身心问题,一个传统的哲学问题,讨论心灵(mind)与物质之间的关系,探讨心灵如何透过身体,与外在世界进行互动,相互影响。比较狭义的讨
  • 罗杰米尔斯罗杰米尔斯县(Roger Mills County, Oklahoma)是美国奥克拉荷马州西部的一个县,西邻德克萨斯州。面积2,969平方公里。根据美国2000年人口普查,共有人口3,436人。县治夏延 (Cheyen
  • 马里 (叙利亚)马里(英语:Mari,即现在叙利亚境内的特尔·哈利利(Tell Hariri))是古代苏美尔亚摩利人建立的城邦,位于幼发拉底河中流的西岸。位于现在叙利亚的阿布·卡马尔西北部11km处,代尔祖尔东
  • 多利多利(英语:Dolly,1996年7月5日-2003年2月14日)是应用细胞核移植技术,利用哺乳动物的成年体细胞培育出的雌性绵羊。是第一个成功克隆的哺乳动物。它是由苏格兰罗斯林研究所和PPL Th
  • 男童镇足球会男童镇足球会(Boys' Town Football Club)是一支位于牙买加金斯敦的职业足球会,目前于牙买加超级联赛角逐。最后更新:2013年9月1日注释:国旗表示球员在国际足联资格规则定义的
  • 佩德罗·恩里克 (巴西)佩德罗·恩里克·阿方索·菲利普·玛利亚·米格尔·加布里埃尔·拉斐尔·贡扎加·德·奥尔良-布拉干萨( Afonso Felipe Maria Miguel Gabriel Rafael Gonzaga de Orléans e
  • 多元微积分在微积分学中,多元微积分(也称为多变量微积分,英语:Multivariable calculus,multivariate calculus)是涉及多元函数的微积分学的统称。相较于只有单个变量的一元微积分,多元微积分