希尔伯特演绎系统

✍ dations ◷ 2025-06-28 16:48:02 #证明论,逻辑演算

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

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

相关

  • 色雷斯色雷斯(希腊语:Θρᾴκη,保加利亚语:Тракия,土耳其语:Trakya)是东南欧的历史学和地理学上的概念。今天的色雷斯包括了保加利亚南部(北色雷斯)、希腊北部(西色雷斯)和土耳其的欧
  • 甲基蓝甲基蓝(C37H27N3Na2O9S3)是一种组织学上使用的染料。可以用于胶原质和植物细胞壁的染色,也可作原生生物的染色,缺点是经日光照射容易褪色且容易氧化。甲基蓝和水溶蓝混合后称作
  • 音讯工程师音频工程师(Audio engineer)是指工作涉及录音(recording)、调整(manipulation)、混音(mixing)以及声音再制(reproduction of sound)的人士。许多音频工程师创造性的运用科技来为电影、
  • 街口网络股份有限公司街口电子支付股份有限公司,简称街口电子支付,为街口金融科技股份有限公司的全资子公司,是中华民国电子支付系统业者之一,旗下有街口支付支付系统。于2015年由胡亦嘉所创立,2018年
  • 欧洲自由贸易联盟欧洲自由贸易协会(英语:European Free Trade Association,缩写为EFTA)是欧洲一个促进贸易的组织。该组织于1960年5月3日成立。成员国有冰岛、挪威、瑞士以及列支敦士登 ,前成员国
  • 大气环流大气环流 (英语:atmospheric circulation) 是指地球表面上大规模的空气流动,是(与较小规模的海洋环流一起)重新分配热量和水汽的途径。大规模的大气环流即使年年有所不同,其基本
  • 胚根在植物学里,胚根是幼苗(成长中的植物胚胎)是在发芽的过程中从种子里出来的第一个部分。胚根是植物初始的根,会向下生长至土壤之中。在胚根之上的是胚轴,是初始支撑子叶的茎。胚根
  • 贝克尔古斯塔沃·阿道夫·贝克尔(西班牙语:Gustavo Adolfo Bécquer,1836年2月17日-1870年12月22日)是西班牙浪漫主义诗人,短篇小说作家,剧作家,文学艺术评论家和专栏作家。他是西班牙文学
  • 伊斯兰教派伊斯兰教派,系伊斯兰教入面分出来的各个不同的派系,在穆罕默德建立伊斯兰教时,原意是以伊斯兰思想为中心统一阿拉伯半岛, 他曾经说过要统一,不要分裂,《古兰经》亦说:“你们当全体
  • 醇类似物醇类似物是泛指任何有类似于醇类或羟基结构的有机化合物,例如硫醇、酚等。大部分的醇类似物都有类似的性质,例如易挥发和刺激性等性质。酚是一种具有羟基的芳香烃,不属于醇类,但