希尔伯特演绎系统

✍ dations ◷ 2025-04-04 11:40: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同构。

相关

  • 密歇根湖密歇根湖(Lake Michigan)是北美洲五大湖之一,从南方顺时针排列,沿岸有美国如下各州︰印地安那、伊利诺伊、威斯康辛及密歇根。“密歇根”这个字原本是用来称呼这座湖泊的,被认为是
  • 霍利奥克坐标:42°12′15″N 72°37′00″W / 42.20417°N 72.61667°W / 42.20417; -72.61667霍利奥克(英语:Holyoke),绰号纸城,是美国马萨诸塞州汉登县的一个城市,位于康涅狄格河西岸。面
  • 若山富三郎若山富三郎(1929年9月1日-1992年4月2日)原名奥村胜,又名城健三朗,日本著名演员、歌手暨电视剧导演,代表作为于1970年代的《带子狼》的拜一刀角色。因为急性心衰竭而逝世;其弟为演员
  • 博蒙迪旺图1法国统计部门在计算土地面积时,不计算面积大于1平方公里的湖泊、池塘、冰川和河口。博蒙迪旺图(法语:Beaumont-du-Ventoux)是法国普罗旺斯-阿尔卑斯-蓝色海岸大区沃克吕兹省的
  • 西湖村西湖村(英文:Westlake Village),是美国加利福尼亚州洛杉矶县下属的一座城市。建市于1981年12月11日,面积 大约为5.19平方英里 (13.4平方公里)。根据2010年美国人口普查,该市有人口
  • 葬于德州苏禄王墓位于山东省德州市城北的北营村,是东南亚古国苏禄国东王巴都葛·叭哈喇(英语:Paduka Pahala)的墓葬。1988年1月13日,被国务院公布为全国重点文物保护单位。明永乐十五年(14
  • 洗礼洗礼(英语:Baptism),又称圣洗圣事、施洗、受洗,全身浸入水中的称为浸礼、受浸,是一宗教仪式,现普遍指基督教的传统仪式。据《圣经》记载,施洗约翰曾为耶稣施洗,而这亦是耶稣吩咐的使
  • 马伊达内克灭绝营纳粹集中营转移营比利时:布伦东克堡垒 · 梅赫伦转移营法国:居尔集中营 · 德朗西集中营意大利:波尔查诺转移营荷兰:阿默斯福特集中营 · 韦斯特博克转移营挪威:法斯塔德集中营部
  • 酯膜结构酯膜结构是由国立台湾大学物理学系教授赵治宇在2004年所发现的新相态。是借于固态与液态之间的样态,属于液晶状态里面的一个亚状态。酯膜结构和液晶一样具有柔性排列结构的特
  • cat (Unix)cat是unix系统下用来查看文件连续内容用的指令,字面上的含意是“concatenate”(连续)的缩写。除了用来作为显示文件内容外,cat指令也可用于标准流上的处理,如将显示的消息转入