希尔伯特演绎系统

✍ dations ◷ 2025-09-18 17:19:26 #证明论,逻辑演算

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

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

相关

  • 高密度脂蛋白高密度脂蛋白(英语:High-density lipoprotein,又称为HDL)是脂蛋白的一种,是由蛋白质和脂质组成的大分子复合物。高密度脂蛋白有不同的种类,它们的形状,大小,密度,蛋白质和脂质成分以
  • 厌氧发酵发酵作用(英语:fermentation)有时也写作酦酵,其定义由使用场合的不同而不同。通常所说的发酵,多是指生物体对于有机物的某种分解过程。发酵是人类较早接触的一种生物化学反应,如今
  • 心理卫生心理健康(Mental health)也称为精神卫生,是指心理幸福安宁的状态,或指没有精神疾病的状态。是指“一个情绪及行为调整都运作相当良好的人,当时的心理状态”。若以正面心理学或是
  • 应用物理应用物理学(applied physics)指的是针对实际用途而进行的物理研究。物理学通常视做一种基础科学,而非应用科学。物理学也被认为是基础科学中的基础科学,因为其它自然科学的分支,
  • bspan style=color:white;阿尔沃兰海/span/b阿尔沃兰海(西班牙语:Mar de Alborán),是地中海的一个附属海,是一片夹在伊比利亚半岛和非洲大陆西端末尾之间的海域,通过直布罗陀海峡和大西洋相连。海区东西长370千米,南北宽170
  • 金邦杜语金邦杜语是安哥拉最常用的语言之一,主要使用人口在该国西北部,尤其是马兰热省。金邦杜语有11种方言:Ngola, Dembo, Jinga, Bondo, Bângala, Songo, Ibaco, Luanda, Quibala, L
  • 产量这是一个各国天然气产量列表,分数据基于世界概况。
  • 门诊患者,又称病人、病者和病患,是指医疗服务的接受者,大多用来指罹患疾病、或身体受到创伤,而需要医生和护理人员进行治疗的人;动物如遇到相同状况,也可以患者称之。但是对于不用接受
  • 酷6网酷6网是中国一个视频分享网站,成立于2006年,2009年酷6网被盛大集团收购。2010年7月30日,酷6网被优酷网盗播8部热播影视剧。2012年4月20日,温州网被优酷网、酷6网盗播12集大型人
  • 马拉巴灵猫马拉巴灵猫(学名:Viverra civettina)是一种麝猫。它们在南印度喀拉拉邦及卡纳塔克邦的低地沿岸很是普遍。但自20世纪后就开始变得稀少,但仍然是1960年代用来制造麝香的主要材料