希尔伯特演绎系统

✍ dations ◷ 2025-04-26 13:20:00 #证明论,逻辑演算

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

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

相关

  • 心肺复苏心肺复苏术(英语:Cardiopulmonary Resuscitation,CPR)是一种救助心搏骤停病患的急救措施,通过人工保持脑功能直到自然呼吸和血液循环恢复。心肺复苏术并非单一的技术,它包含了一系
  • 电位在静电学里,电势,或作电位(英语:electric potential),是标量,定义为处于电场中某个位置的单位电荷所具有的电势能。其数值不具有绝对意义,只具有相对意义,因此为了便于分析问题,必须设
  • 马卢尔县马卢尔县(英语:Malheur County,发音: /mælˈhɪər/)是美国俄勒冈州东南部的一个县,东隔蛇河与爱达荷州相望,南邻内华达州。马卢尔县亦是组成东俄勒冈的八个县份之一。马卢尔县面
  • 俄罗斯共和国俄罗斯共和国(俄语:Российская республика,罗马化:Rossiyskaya respublika,IPA:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libe
  • 非对映体过量非对映体过量(diastereomeric excess, 缩写为de%),通常用来表征两个以上手性中心时的光学纯度。例如,某个拥有两个手性中心的分子,有四个非对映体:(R,R)、(R,S)、(S,S)、(S,R),两两
  • 布丽·拉尔森布丽·拉尔森(英语:Brie Larson,1989年10月1日-),本名布莉安·希唐妮·特桑尼尔斯(英语:Brianne Sidonie Desaulniers),是一位美国女演员和歌手。童年出道开始参演喜剧小品《The Tonig
  • 尚之信尚之信(1636年-1680年),字德符,号白岩,别称“俺答公”,汉军镶蓝旗人,祖籍山西洪洞,平南王尚可喜长子。尚之信年少时曾入宫为侍卫,顺治帝赐其同公爵秩。及后,尚之信归广东,辅佐尚可喜处理
  • 国际纯化学和应用化学联合会国际纯化学和应用化学联合会(英语:International Union of Pure and Applied Chemistry,简称IUPAC,/ˈaɪjuːpæk, ˈjuː-/),又译为国际纯粹与应用化学联合会、国际纯化学与应用
  • 江户幕府将军列表江户幕府将军列表中列出日本江户幕府时期,德川氏十五任征夷大将军的列表。德川家的将军除了秀忠以外,在就任同时都会一并得到源氏长者的称号,死后也会追赠正一位的地位。15位将
  • 波萝勉市波萝勉(高棉语:ខេត្តព្រៃវែង),是柬埔寨南部的一个城市,该城市是波萝勉省省会、波萝勉县县治。该城市的名字在高棉语中意思是“大森林”。西北距金边48公里。人口33,0