希尔伯特演绎系统

✍ dations ◷ 2025-07-06 08:40:06 #证明论,逻辑演算

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

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

相关

  • 夸休可尔症夸休可尔症(英语:Kwashiorkor),即恶性营养不良,又称蛋白質缺乏症,台湾亦称作红孩儿症,是一种营养不良症,其致病原因尚有争议,目前普遍认为是由于蛋白质摄入不足而导致。此病症通常发
  • VIIIBbr /8固体、 液体、 气体8族元素(又称铁族元素)是指元素周期表上第8族的元素,位于7族元素和9族元素之间,在过去和9族元素及10族元素合称为ⅧB族元素。8族元素包含铁(Fe)、钌(Ru)、锇(Os)、
  • 永续设计可持续设计,是一种以符合经济、社会及生态学三者可持续经营为方针的设计方法。可持续设计领域旨在通过采用综合方法创造“三赢”设计来平衡这些领域的需求。可持续设计的范畴
  • Escherich特奥多尔·埃舍里希(Theodor Escherich 1857年11月29日-1911年2月15日)德国奥地利儿科医生、格拉茨大学和维也纳大学教授。他发现了大肠杆菌并确定了其特性。1885年埃舍里希尝
  • 贝特曼原理生物学上,贝特曼原理指的是雌性通常在生育时比雄性投入更多能量,因此在多数物种中雌性必须操作有限的资源而趋于被动,雄性将为争夺她们而竞争。该理论是以英国遗传学家安格斯·
  • 启(前2084年-前2006年),姒姓,名启,是中国夏朝第二任君主。治水英雄的禹的儿子,母亲是涂山氏族的女子。儿子至少有五人,其中有太康及中康。据《竹书纪年》,启在位39年,78岁驾崩。相传禹
  • 非晶物质无定形体,或称无定形体、无定形形固体,是其中的原子不按照一定空间顺序排列的固体,与晶体相对应。常见的无定形体包括玻璃和很多高分子化合物如聚苯乙烯等。只要冷却速度足够快
  • 布莱根妇女医院布莱根妇女医院(Brigham and Women's Hospital,BWH)是位于美国马萨诸塞州波士顿Mission山的一所著名医院,位于长木医学区内。布莱根妇女医院是校园与之毗邻的哈佛医学院的主要教
  • 蒙苏农多蒙苏农多(高棉语:ម៉ម សូណង់ដូ,或译曼·索南多;1942年2月13日-),柬埔寨电台记者,拥有柬埔寨、法国双重国籍。他是金边蜂巢电台东主兼台长;保护记者委员会曾于2012年形容蜂巢
  • 国际文字设计协会国际文字设计协会(法语:Association Typographique Internationale,简称:ATypI)是字体排印和字体设计行业的非营利性国际组织,于1957年由法国Deberny & Peignot(英语:Deberny & Peig