希尔伯特演绎系统

✍ dations ◷ 2025-09-10 19:17: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同构。

相关

  • 藏缅语族藏缅语族是分布于中国西南部、印度东北部、尼泊尔、巴基斯坦、不丹、缅甸、泰国、越南等地的一组语言。根据民族语网站2009年的资料,藏缅语族共包含有435种语言,其中主要的语
  • 云端运算云计算(英语:cloud computing),是一种基于互联网的计算方式,通过这种方式,共享的软硬件资源和信息可以按需求提供给计算机各种终端和其他设备,使用服务商提供的电脑基建作计算和资
  • 朝鲜国家宇宙开发局朝鲜国家宇宙开发局(韩语:국가우주개발국;官方英文译名:National Aerospace Development Administration,简称NADA)是朝鲜于2013年4月1日在第十二届最高人民会议中成立的国家中央
  • 玫瑰少年《玫瑰少年梦》(法语:Ma vie en rose,台湾译《玫瑰少年》)是1997年比利时导演亚兰·贝利执导的剧情片。
  • 宝贝鱼Yahoo! Babel Fish(Yahoo! 奇摩称作Yahoo! 奇摩翻译;又译宝贝鱼、巴别鱼)是一个互联网上一个自动化的免费机械翻译系统服务,由门户网站AltaVista(已被雅虎收购)提供。宝贝鱼可以为
  • 肯尼斯·尼科尔斯肯尼斯·大卫·尼科尔斯少将(英语:Major General (United States))(Kenneth David "Nick" Nichols,1907年11月13日-2000年2月21日)是一位美国陆军军官兼工程师,曾效命于在二战期间研
  • 铁托主义铁托主义(塞尔维亚语:Titoizam;英语:Titoism)是以南斯拉夫社会主义联邦共和国总统约瑟普·布罗兹·铁托命名的一种社会主义政治思想体系。铁托主义起源于第二次世界大战之后,由铁
  • 宁夏路夜市坐标:25°03′19″N 121°30′54″E / 25.0553758°N 121.5150976°E / 25.0553758; 121.5150976宁夏路夜市,简称宁夏夜市,是位于台北市大同区宁夏路的夜市景点。2015年,台北市
  • 模拟城市 (2013年游戏)《模拟城市》(英语:SimCity),是于2013年发行的城市建造电脑游戏,一般玩家为方便区分称之为模拟城市5。由艺电的子公司Maxis开发。这是艺电第6个,也是第5个由Maxis制作的《模拟城市
  • 1,3,5-三氮杂-7-磷杂金刚烷1,3,5-三氮杂-7-磷杂金刚烷(英语:1,3,5-Triaza-7-phosphaadamantane,缩写PTA)是一种有机化合物,为六次甲基四胺(乌洛托品)的一个氮原子被磷原子取代的产物,化学式C6H12N3P。它可溶于