希尔伯特演绎系统

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

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

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

相关

  • 恩氟醚恩氟醚(英文Enflurane,系统命名法名称(2-氯-1,1,2-三氟乙基)二氟甲基醚),是一种卤代醚麻醉药,适用于全身麻醉。本药由罗斯·特雷尔(Robert Terrell)于1963年发明并于三年后首次投入
  • 杜尔贝科罗纳托·杜尔贝科(意大利语:Renato Dulbecco,1914年2月22日-2012年2月19日),意大利出生的病毒学家,二次世界大战后与好友神经生物学家丽塔·列维-蒙塔尔奇尼一起移居美国。由于发现
  • 音乐之声《音乐之声》(The Sound of Music)是一部1965年的美国电影,改编自同名音乐剧。1960年6月,二十世纪福斯以1,250,000美元购得电影版版权。但条约中规定二十世纪福斯公司必须等同名
  • 假面《假面》(Persona)是瑞典导演英格玛·伯格曼的电影作品,发行于1966年,由Bibi Andersson 和丽芙·乌曼主演。伯格曼本人对其极为看重;在回忆录《影像:我的电影生涯》中,他写道:“今天
  • 打喷嚏 (电影)《打喷嚏》(英语:A choo),中国大陆片名为《不倒侠》,改编自台湾知名作家九把刀小说《打喷嚏》。此片原订2014年10月31日上映,但因后制尚未完成,另因吸毒事件影响,以致上映延期。历经
  • 塞奇威克县塞奇威克县(Sedgwick County, Colorado)是美国科罗拉多州东北角的一个县,东、北、西北为内布拉斯加州包围。面积1,423平方公里。根据美国2000年人口普查,共有人口2,747人。县治
  • 普拉特河普拉特河(英语:Platte River、/plæt/)是内布拉斯加州的一条主要河流,长约500公里,由北普拉特河和南普拉特河汇合而成。
  • 清卷舌边塞擦音清卷舌边塞擦音(Voiceless retroflex lateral affricate)是一种辅音,使用于一些口语中。用于表示此音的国际音标(IPA)是⟨ʈ͜ɭ̊˔⟩。清卷舌边塞擦音的特征包括:当符号成对出现
  • 安贾·涅得金豪斯安贾·涅得金豪斯(或译安雅·尼德林豪斯,Anja Niedringhaus,1965年10月12日-2014年4月5日)德国战地女摄影记者。2005年曾因一组伊拉克战争照获普利策突发新闻摄影奖 及国际妇女传
  • Ba.88攻击机布雷达 Ba.88 “猞猁”(意大利语:Breda Ba.88 "Lince") 是意大利于二战期间装备的一种攻击机。该机于1937年首次公布,并打破了当时多项速度记录。Ba.88具有流线型外形与可伸缩起