希尔伯特演绎系统

✍ dations ◷ 2025-06-08 09:54:23 #证明论,逻辑演算

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

所有演绎系统都在逻辑公理和推理规则之间作出取舍平衡。希尔伯特风格的演绎系统可以刻画为选择了大量的逻辑公理模式和少(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同构。

相关

  • 库努牡库努牡((英语:Khnum)(亦可拼写为"Chnum", "Knum"或"Khnemu")是最早的埃及神祇之一,原为尼罗河源头之神。由于尼罗河每年的固定泛滥会带来淤泥与黏土,而河水则带来生命,所以库努牡也被
  • 未来学家未来学家是指推测未来的人。未来学是一项难度很高的研究,因为我们很难集中研究一项尚未发生的事件。不过,这些对未来的推测,并不是好像占星一样的虚无缥缈,而是以历史及文化的发
  • 没关系,是爱情啊《没关系,是爱情啊》(韩语:괜찮아, 사랑이야)为韩国SBS自2014年7月23日起播出的水木迷你连续剧,由赵寅成、孔晓振、都敬秀、成东镒及李光洙主演,《他们的世界》、《Padam Padam》
  • 球冠球冠是指一个球面被平面所截后剩下的曲面。截得的圆面是底,垂直于圆面的直径被截得的部分是高。也可看作圆弧绕过它的一个端点的圆的直径旋转一周得到的面。球冠的面积:
  • 战役风云《众神与将军》(英语:Gods and Generals)是一部关于南北战争的电影,这部影片是以同名的书(Gods and Generals)作根据。《众神与将军》试图将内战早期的将士们的爱国热忱,以及他们
  • 皮斯河皮斯河(Peace River,法语:rivière de la Paix)位于加拿大不列颠哥伦比亚省和阿尔伯塔省,起于芬利河河口,最终注入奴河,全长1923公里。皮斯河被认为是马更些河水系的正源。以皮斯河
  • 占碑市占碑市是印尼占碑省的首府,为苏门答腊的第六大城市,占碑省的省会。是一个印度尼西亚的石油和橡胶重要产地,有沿河港口。距现在占碑市26千米曾是古代三佛齐王国的占碑遗迹(英语:Mu
  • 安崎安崎(1996年5月13日-),中国大陆歌手。出生于重庆,所属经纪公司为匠星娱乐。是Hickey喜祺的成员之一。在2020年5月30日,在《青春有你2》排名第六并以THE9成员出道。1996年5月13日,出
  • 托尔拉库方言托尔拉库方言(塞尔维亚-克罗地亚语:,保加利亚语:Торлашки/Torlashki)是南斯拉夫语支的方言集合之一,使用者分布在塞尔维亚东南部,科索沃北部,马其顿共和国东北部和保加利亚
  • 赫尔曼·施莱格尔赫尔曼·施莱格尔(Hermann Schlegel,1804年6月10日-1884年1月17日),德国鸟类学家暨爬虫两栖类学家。由于其多数著名的研究都是在荷兰完成,因此常也被认为是荷兰的科学家。施莱格尔