徽标
联盟百科
通讯
下载应用,请到 Google Play
新! 在您的Android™设备上下载联盟百科!
下载
比浏览器更快的访问!
 

切消定理

指数 切消定理

切消定理是确立相继式演算重要性的主要结果。它最初由格哈德·根岑在他的划时代论文《逻辑演绎研究》对分别形式化直觉逻辑和经典逻辑的系统LJ和LK做的证明。切削定理声称在相继式演算中,拥有利用了切规则的证明的任何判断,也拥有无切证明,就是说,不利用切规则的证明。 相继式是与多个句子有关的逻辑表达式,形式为"A, B, C, \ldots \vdash N, O, P",它可以被读做"A, B, C, \ldots证明N, O, P",并且(按Gentzen的注释)应当被理解为等价于真值函数"如果(A & B & C \ldots)那么(N or O or P)"。注意LHS(左手端)是合取(and)而RHS(右手端)是析取(or)。LHS可以有任意多个公式;在LHS为空的时候,RHS是重言式。在LK中,RHS也可以有任意数目的公式--如果没有,则LHS是个矛盾,而在LJ中,RHS只能没有或有一个公式:在右紧缩规则前面,允许RHS有多于一个公式,等价于容许排中律。注意,相继式演算是相当有表达力的框架,已经为直觉逻辑提议了允许RHS有多个公式的相继式演算,而来自Jean-Yves Girard的逻辑LC得到了RHS最多有一个公式的经典逻辑的更加自然的形式化;逻辑和结构规则的相互作用是它的关键。 "切"是在相继式演算的正规陈述中的一个规则,并等价于在其他证明论中的规则变体,给出 和 你可以推出 就是说,在推论关系中"切掉"公式"C"的出现。 切消定理声称(对于一个给定的系统)使用切规则的任何相继式证明也可以不使用这个规则来证明。如果我们认为(D, E, \ldots)是一个定理,则切消简单的声称用来证明这个定理的引理C可以被内嵌(inline)。在这个定理的证明提及引理C的时候,我们可以把它代换为C的证明。因此,切规则是可接纳的。 对于用相继式公式化的系统,分析性证明是不使用切规则的证明。这种证明典型的会很长,当然没有必要这么做。在散文《不要消除切呀!》中,George Boolos展示了可以使用切在一页中完成的推导,而它的分析性证明要耗尽宇宙的寿命来完成。 这个定理有很多丰富的推论。一旦一个系统被证明有切消定理,这个系统通常立即就是一致的。这个系统通常也有子公式性质,这是达成证明论语义的重要性质。切削是证明插值定理的最强力工具。基于归结原理的完成证明查找的可能性,导致Prolog编程语言的本质洞察,依赖于在适当的系统中接纳切规则。.

11 关系: 假言三段论归结原理经典逻辑直觉主义逻辑相继式演算证明论逻辑和谐Prolog推理规则排中律格哈德·根岑

假言三段论

假言三段论又称假言推理。假言推理总是以假言判断为前提来进行推理的。 在逻辑中,假言三段论是服从下列形式的有效的论证: 在逻辑运算符记号中 换句话说,这种论证陈述如果第一个蕴涵第二个,并且第二个蕴涵第三个,则第一个蕴涵第三个。假言三段论的一个例子: 假言三段论有一个好处,它们可以是反事实的(counterfactual): 它们可以是真的,即使前提假设的命题已知是假的。 反事实的前提的可以在有效的假言三段论中使用的例子.

新!!: 切消定理和假言三段论 · 查看更多 »

归结原理

在数理逻辑和自动定理证明中(GOFAI涉及的主题),归结(resolution)是对于命题逻辑和一阶逻辑中的句子的推理规则,它导致了一种反证法的定理证明技术。.

新!!: 切消定理和归结原理 · 查看更多 »

经典逻辑

经典逻辑(Classical logic),又稱古典邏輯,标识已经被最深入的研究和最广泛的使用的一类形式逻辑,也被稱為標準邏輯(standard logic)。經典邏輯被特征化为一些性质,非经典逻辑缺乏這其中的某一个或多个特性:.

新!!: 切消定理和经典逻辑 · 查看更多 »

直觉主义逻辑

觉主义逻辑或构造性逻辑是最初由阿蘭德·海廷开发的为鲁伊兹·布劳威尔的数学直觉主义计划提供形式基础的符号逻辑。这个系统保持跨越生成导出命题的变换的证实性而不是真理性。从实用的观点,也有使用直觉逻辑的强烈动机,因为它有存在性质,这使它还适合其他形式的数学构造主义。.

新!!: 切消定理和直觉主义逻辑 · 查看更多 »

相继式演算

在证明论和数理逻辑中,相继式演算(又译矢列演算、矢列式演算)是众所周知的一阶逻辑(和作为它的特殊情况的命题逻辑)的演绎系统。这个系统也叫做LK系统,用以区别于后来建立的有时也叫做相继式演算的类似风格的各种其他系统。另一个给这种系统的术语是Gentzen系统。 相继式演算LK由Gerhard Gentzen介入为研究自然演绎的工具。它已经变成构造逻辑推导的非常有用的演算。它的名字得来自德语的Logischer Kalkül,意思是"逻辑演算"。相继式演算是关于这个主题的很多研究所选择的方法。.

新!!: 切消定理和相继式演算 · 查看更多 »

证明论

证明论是数理逻辑的一个分支,它将数学证明表达为形式化的数学客体,从而通过数学技术来简化对他们的分析。证明通常用归纳式地定义的数据结构来表达,例如链表,盒链表,或者树,它们根据逻辑系统的公理和推理规则构造。因此,证明论本质上是语法逻辑,和本质上是语义学的模型论形相反。和模型论,公理化集合论,以及递归论一起,证明论被称为数学基础的四大支柱之一。 证明论也可视为哲学逻辑的分支,其主要兴趣在于证明论语义学的思想,该思想依赖于结构证明论的技术型想法才可行。.

新!!: 切消定理和证明论 · 查看更多 »

逻辑和谐

逻辑和谐,由 Michael Dummett 命名,是对可以用于给定的逻辑系统的推理规则的假定约束。 逻辑学家格哈德·根岑提议了逻辑连结词的意义可以用把它们介入到论述中的规则给出。例如,如果你相信“天是蓝的”并且还相信“草是绿的”,则你可以如下这样介入逻辑连接词“与”: “天是蓝的 AND 草是绿的”。Gentzen 的想法是拥有这样的规则就是对你的词语,至少对特定词语的给出意义的东西。这个想法也关联于维特根斯坦的格言,在很多情况下我们可以说意义是使用。多数当代逻辑学家偏好认为介入规则和除去规则对于表达是同等重要的。在这种情况下,“与”被如下规则所特征化: |- ! 介入: !! colspan.

新!!: 切消定理和逻辑和谐 · 查看更多 »

Prolog

Prolog(Programming in Logic的缩写)是一种逻辑编程语言。它建立在逻辑学的理论基础之上, 最初被运用于自然语言等研究领域。现在它已广泛的应用在人工智能的研究中,它可以用来建造专家系统、自然语言理解、智能知识库等。.

新!!: 切消定理和Prolog · 查看更多 »

推理规则

在逻辑中,特别是数理逻辑中,推理规则(推论规则)是构造有效推论的方案。这些方案建立在一组叫做前提的公式和叫做结论的断言之间的语法关系。这些语法关系用于推理过程中,新的真的断言从其他已知的断言得出。规则也适用于非形式逻辑和逻辑论证,但是形式化更加困难和有争议。 按照规定,推理规则的应用纯粹是语法过程。尽管如此它必须是有效的,或者更精确地说保持有效性。为了使保持有效性的要求有意义,某种形式的语义与推理规则有关和推理规则自身的断言是必需的。对于在推理规则和和语义之间相互关系的讨论请参见命题逻辑。 命题逻辑中推理规则的显著例子是肯定前件和否定后件规则。对于一阶谓词逻辑,推理规则需要处理逻辑量词。对这种论证的更详细的描述请参见有效性。在一阶谓词逻辑中把所有推理规则作为一个单一规则来统一处理请参见一阶归结。 注意有很多不同的形式逻辑系统,每个都带有合式公式、推理规则和语义的自己的集合。参见时间逻辑、模态逻辑或直觉逻辑的实例。量子逻辑也是一种不同寻常形式的逻辑。参见证明论。在谓词演算中,需要一个补充的推理规则。它叫做普遍化。 在形式逻辑的设置(和很多有关领域)中,推理规则通常用如下形式给出:  前提#1  前提#2  ...  前提#n   结论 这个表达式声称,在某个逻辑推导期间已经获得了给定前提,同样可以认可特定结论。用来描述前提和结论二者的的精确的形式语言依赖于推导的实际上下文。在一个简单的情况下,你可以使用逻辑公式,比如  A→B  A     B 它是命题逻辑的肯定前件规则。推理规则通常通过使用全称变量而公式化为规则模式。在上面的规则(模式)中,A和B可以被实例化为论域(有时约定为某种受限制的子集比如命题)的任何元素,来形成推理规则的无限集合。 证明系统形成自一组规则,它们可以被链接在一起形成证明或推导。任何推导都只有一个最终结论,它是要证明或推导的陈述。如果在推导中留下了未满足的前提,则推导就是假言陈述:"如果前提成立,那么结论成立"。.

新!!: 切消定理和推理规则 · 查看更多 »

排中律

在逻辑中,排中律(tertium non datur)声称对于任何命题 P,(P ∨ ¬P) 为真。 符号 '¬' 读作“非”,∨ 读作“或”,∧ 读作“与”。 例如,如果 P 是 则包含式析取 为真。 这不完全同于二值原理,它陈述的是 P 必须要么是真要么是假。它也不同于无矛盾律,它陈述的是 ¬(P ∧ ¬P) 是真。排中律只是说 (P ∨ ¬P) 整体是真。不提及 P 自身可以采用什么真值。在任何情况下,任何二值逻辑的语义都将为 P 和 ¬P 指派对立的真值(就是说,如果 P 是真,则 ¬P 是假),所以在二值逻辑中排中律会等价于二值原理。但是,对于非二值逻辑或多值逻辑就不能这么说。 特定的逻辑系统可能通过允许多于两个真值(比如:真、假、中;真、假、非真非假、亦真亦假)而拒绝二值原理,但接受排中律。在这种逻辑中,(P ∨ ¬P) 可以为真,而 P 和 ¬P 不被分别指派为对立的真值。 一些逻辑不接受排中律,最著名的是直觉逻辑。文章《二值和有关规律》中详细地讨论了这个问题。 排中律可能被误用,导致排中律的逻辑谬论,这也叫做假两难推理。.

新!!: 切消定理和排中律 · 查看更多 »

格哈德·根岑

格哈德·根岑(Gerhard Karl Erich Gentzen,)是德国的数学家和逻辑学家。 他生于德国的格赖夫斯瓦尔德,在1929年到1933年期间是赫尔曼·外尔在哥廷根大学的学生之一。在1934年到1943年間他是大卫·希尔伯特在哥廷根大学的助手。從1943年起他是布拉格大學的教授。他的主要工作是数学基础中的证明论,特别是自然演绎和相继式演算。他的切消定理是证明论语义的基石,《逻辑演绎研究》中的某些哲学评论和维特根斯坦的格言"意义是使用"一起建立了推论角色语义的基础。 他是納粹黨和沖鋒隊的成員,在1945年5月7日隨所有在布拉格的德國人一起被逮捕之后,饿死于布拉格附近的战俘营中。.

新!!: 切消定理和格哈德·根岑 · 查看更多 »

传出传入
嘿!我们在Facebook上吧! »