希尔伯特演绎系统

✍ dations ◷ 2025-04-04 04:47:03 #证明论,逻辑演算

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

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

相关

  • 保守治疗保守治疗,亦称为保守疗法(conservative therapy),指相对于有创操作(即有创伤的操作,如手术)的疗法,如药物治疗、物理治疗等。
  • 三名法在分类学上,三名法(英语:Trinomial nomenclature)指针对低于种的分类单位所采用的命名方式。动物学和植物学中的三名法有差异。对于动物来说,只有一个物种以下的分类层级──亚种
  • 鱿鱼鱿鱼、学名是“开眼亚目”,又称句公、枪乌贼、鱿鱼亚目,是软体动物门头足纲鞘亚纲十腕总目管鱿目开眼亚目动物的通称。鱿鱼身体细长,呈长锥形,有十只触腕,其中两只较长。触腕前端
  • 膨胀宇宙加速膨胀是宇宙的膨胀速度越来越快的现象。以天文学术语来说,就是宇宙标度因子  a ( t ) {\displays
  • 板桥水库板桥水库是一座位于河南省驻马店市驿城区板桥镇、淮河支流汝河上游,以防洪为主,兼顾灌溉、供水、发电、水产等综合利用的丘陵区水库,控制流域面积768平方公里。1951年开始了大
  • 肯特省肯特省(蒙古语:Хэнтий аймаг,转写:Khentii aimag)位于蒙古国中部偏东,面积80,325平方公里,人口65,811(2011年)。首府温都尔汗。得名于肯特山脉,据说是成吉思汗出生和成长的
  • 董酒董酒是产于贵州省遵义董公寺一带的国家名酒。董酒以“酒液晶莹透明,香气幽雅舒适,入口醇和浓郁,饮后甘爽味长”为特点。曾四次荣获全国名酒称号(在全国第二、第三届评酒会上,都被
  • 雪胎雪胎,也通常称为雪地胎、冬季胎,轮胎的一种,是为寒冷天气设计的,专门用于雪地及结冰的路面,使车辆行驶时减少打滑。在雪地状况下,防滑链是权宜之计,毕竟会影响行驶速度。相较于防滑
  • 加拿大体育加拿大流行多种不同的体育活动。加拿大的体育运动中最常见的是冰球、曲棍球、加拿大橄榄球、足球、篮球、冰壶和棒球。冰球是加拿大的国球,也是加拿大最受欢迎的体育运动,在国
  • 喀拉米豚鹿喀拉米豚鹿(),又名卡拉棉豚鹿或卡岛豚鹿,是菲律宾巴拉望卡拉绵群岛特有的一种鹿。雄性喀拉米豚鹿高60-65厘米,鹿角有三叉。不像其他亚洲的花鹿,它们出生时并没有斑点。除了猛禽及