`
somefuture
  • 浏览: 1089091 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

数理逻辑之 命题逻辑可靠性

 
阅读更多

好几天没写了,因为这几天回到了北京,比较乱。

上海找工作依然没着落,再从北京看看。待好运!

 

命题逻辑的主要规则已经说完了。

对于逻辑学来说,一个很重要的部分就是为什么这样

要证明一个逻辑系统是正确的,需要证明两部分:它的可靠性和它的完备性。

今天先来说可靠性

 

下面的内容可能要求你对前面的课程很熟悉才比较方便。

 前面说了数学归纳法。归纳法是出现使得我们通过假设一些正确的前提就能得到正确的结论。

所以我们现在可以这样来证明一个结论:

φ1, φ2, . . . , φn |- ψ

 当命题φ1, φ2, . . . , φn都是正确的时候,如果可以得出ψ,则ψ就是正确的结论。

 

那么你有没有疑问:会不会出现这种情况,如果在真值表中前提假设都是正确的却能得出结论是错误的?

你可能会想当然的认为:不可能吧。但是why

你的确说对了:不可能的。怎么证明呢?

要证明这个结论,我们需要在真值表中把前提都赋值为T,看能否出现结论为F的情况。

当然了,你一下子就想到了:需要把宇宙中的全部相继式都尝试过才能得出这个结论。

太扯淡了是吧!咋办呢?

还记得语意继承关系?在数理逻辑之合式公式中我们说过这个概念:如果某个(或某些)合式公式Θ1, Θ2, Θ3, …, Θn每次求值为T的时候都能使公式ΨT,则称它们之间是语意继承关系语意蕴含关系,记作

Θ1, Θ2, Θ3, …, Θn |= Ψ

 考虑如下例子:

p q |=  p成立吗?

p q |=  p成立吗?

¬q, p q |= p成立吗?

p |= q ¬q成立不?

第一个例子当合取为T时子式肯定为T,所以成立;

第二个就不一定了,因为析取为T,只要任意一个为T就可以,不能得出某个子式为T

第三个因为¬qT所以qF了,又析取为T所以pT,成立;

第四个pT是右边不影响,因为总是对的(这种公式称为重言式)。

所以我们的证明变成了另一种方式:如果相继关系成立,则语意继承关系成立。即

如果φ1, φ2,..., φn |- ψ 成立,则 φ1, φ2,..., φn |= ψ 成立。

可就是说我们不去考虑公式的真值表了,去看看它的相继关系成不成立就行了。 

 

上面这个称为命题逻辑的可靠性。

证明

由于相继关系成立,我们有ψ可由φ1, φ2,..., φn导出。

我们的证明需要对证明的长度使用数学归纳法

所谓证明的长度就是它的行数。

在使用归纳法前我们先提一个断言M(k)

如果φ1, φ2,..., φn |- ψ 成立(其中n>0,相继关系的证明行数为k),则 φ1, φ2,..., φn |= ψ 成立

 在看一个例子(别嫌啰嗦,否则直接证明就晕倒了):

 

相继关系p q → r |- p → (q → r)的证明如下:

 

 
一共有7行。如果去掉最后一行,最外层的盒子的结论就没有了,我们改写一下:

 

 
我去掉了最外面的框,这样第二行就变成了前提。

当然了上面的证明过程是针对p q → r, p |- p → r的,这时候p q → r, p |= p → r也成立。

而且p q → r |= p → (q → r)也是成立的。why

(如果你还记得一般相继式和定理的关系可能会有些释然)
我们的归纳假设是这样的:对于任意k'k'<kM(k')成立。我们希望能证明M(k)成立。

归纳基础:当k=1时,相继关系是这样的:ψ |- ψ,这时候语意继承关系ψ |= ψ成立,因为左边赋值T则右边也是T(当然了左边是F右边也是F,不过我们不关心);

归纳步骤:假设相继关系φ1, φ2,..., φn |- ψ的证明过程是k行,并且所有小于k行的证明过程都是成立的。

证明过程的结构是这样的:

 

 
这个描述中有两点令人疑惑:一是在n个前提写完之后到结论得出前发生了什么;二是结论的得出使用了什么规则。

 第一个疑惑数学归纳法帮我买解决了。第二个问题是大大的问题,证明过程基本花费在上面了。

由于不确定最后使用的什么规则,我们只能一个一个的来证明了。 

假设最后的规则是合取引入(i),则ψ的形式是ψ1 ψ2,并且合取引入规则使用在第k行。必然在k之上有两行是ψ1ψ2,假设它们的行号是k1k2。那么一定有相继关系φ1, φ2,..., φn |- ψ1φ1, φ2,..., φn |- ψ1成立,它们的证明行数分别是k1k2。根据归纳假设,有φ1, φ2,..., φn |= ψ1φ1, φ2,..., φn |= ψ1成立。所以φ1, φ2,..., φn |= ψ成立(为啥?);

假设最后的规则是析取消去(e),则ψ之前必有形式是ψ1ψ2,得出结论的行号是k'(k'<k)。这样存在一个短证明φ1, φ2,..., φn |- ψ1ψ2,根据析取消去规则必有两个盒子分别证明φ1, φ2,..., φn,ψ1 |- ψφ1, φ2,..., φn,ψ2|- ψ。根据归纳假设,φ1, φ2,..., φn |= ψ1ψ2φ1, φ2,..., φn,ψ1 |= ψφ1, φ2,..., φn,ψ2|= ψ都成立。这足以保证φ1, φ2,..., φn |= ψ成立(为啥?);

其他规则类似。

 
<!--[if !supportLineBreakNewLine]-->
<!--[endif]-->

 

 

 

 

 

  • 大小: 10.2 KB
  • 大小: 8.9 KB
  • 大小: 11.3 KB
分享到:
评论

相关推荐

    数理逻辑基础

    数理逻辑基础是研究推理规则的科学,它运用数学符号化方法来构建推理体系,探究这些体系的一致性、可靠性和完备性。数理逻辑主要由两个部分构成:演算和理论。其中演算包括命题演算和谓词演算,而理论涉及递归论、...

    数据库——数理逻辑ppt

    通过命题逻辑,可以形式化地表述和验证算法的正确性,确保系统的可靠性。 数理逻辑的进一步发展包括谓词逻辑,它允许对个体和属性进行更复杂的表述,引入量词(全称量词和存在量词)来描述普遍性和特殊性。谓词逻辑...

    数理逻辑与机器证明(陆钟万)

    书中深入探讨了命题逻辑和一阶逻辑的可靠性与完备性问题。可靠性问题关注的是逻辑系统是否能保证从真实的前提出发,能够得到真实的结论;而完备性问题则关注逻辑系统是否能够推导出所有真实的结论,即没有遗漏。通过...

    面向计算机科学的数理逻辑

    《面向计算机科学的数理逻辑》是一本专为研究生设计的教材,旨在深入探讨数理逻辑在计算机科学中的应用和重要性。数理逻辑作为连接数学与计算机科学的桥梁,对于理解和解决计算问题、设计算法以及验证程序正确性等...

    面向计算机的数理逻辑

    数理逻辑在计算机科学领域扮演着至关重要的角色,它不仅是理论计算机科学的基础之一,也是现代软件开发、人工智能、数据库管理等多个领域的基石。 ### 数理逻辑概述 数理逻辑是逻辑学的一个分支,它将逻辑推理的...

    数理逻辑(讲义)

    形式推理系统的可靠性意味着按照规则进行的推理一定是有效的,而完备性则指任何真命题都可以通过这些规则推导出来。 逻辑的多样性源于不同的形式语言、推理规则和解释系统。例如,当现有形式语言不足以表达复杂的...

    数理逻辑课件

    课件中的"02-dtmcs.pdf"可能涉及离散时间马尔可夫链(DTMCs),这是一种处理离散状态和概率转移的模型,广泛应用于系统可靠性分析和性能评估。 综上所述,这个数理逻辑课程全面覆盖了从基础逻辑到高级模型检查的...

    数理逻辑讲义 电子版 通俗易懂

    - **定义与基本概念**:命题逻辑是最基础的逻辑系统之一,它主要研究命题及其逻辑联结词(如否定、合取、析取、蕴含、等价)之间的关系。命题是指可以判断真假的陈述句。 - **命题联结词**: - **否定**(¬):...

    数理逻辑讲义附件.

    - 包括如有效性定理、可靠性定理等。 **2.6 自然演绎推理系统(ND)** - **组成**: - 描述了ND系统的语法结构和推理规则。 - **基本定理**: - 如ND系统的完备性和一致性。 通过以上章节的学习, 学生不仅能够掌握...

    数理逻辑讲义 20220411.zip

    综上所述,这些讲义涵盖了数理逻辑的核心概念,从简单的命题逻辑逐步深入到谓词逻辑,然后探讨了公理系统、数字逻辑的基础以及逻辑系统的可靠性与完备性问题,为理解形式推理和数学证明的逻辑基础提供了全面的框架。

    逻辑基础 王路

    - 有效性与可靠性 4. **形式逻辑的核心要素** - 命题逻辑 - 谓词逻辑 - 证明方法与技巧 5. **数理逻辑简介** - 数理逻辑的意义 - 模型论与证明论 - 形式系统的构建 6. **逻辑学的应用领域** - 在计算机...

    离散数学简单版的资料

    ### 离散数学简单版资料之数理逻辑知识点概览 #### 教学目标解析 **《数理逻辑》**作为计算机科学与技术及信息安全专业的重要基础课程之一,其核心目的是培养学生的逻辑思维能力和数学素养。具体而言,课程旨在让...

    人工智能逻辑.pptx

    逻辑系统的可靠性是指其证明能够保持语句的真值不变,即如果在某解释下,一个语句是真实的并且可被证明,那么在所有解释下它都保持真实。完备性则是指逻辑系统能够推导出所有真实的语句。一阶逻辑被证明是完备的,但...

    离散数学 教材 上海科学技术文献出版社

    离散数学是计算机科学及相关领域的重要基础学科之一,它涵盖了数理逻辑、集合论、代数系统、图论以及形式语言与自动机等核心知识。上海科学技术文献出版社出版的这本教材详细地介绍和讨论了离散数学的基本理论和应用...

    论文研究-逻辑系统L*和BL*的广义演绎定理的逆定理.pdf

    综上所述,文档内容涉及的不仅仅是对特定逻辑系统的理论分析,它还涵盖了数理逻辑中的基础概念、证明方法、逻辑系统的完备性和可靠性问题,以及这些理论在计算机科学中的应用前景。通过这些知识点的深入研究,我们能...

    《逻辑起源 》完全版

    - 探讨了数理逻辑的发展及其对数学理论的影响。 #### 4.2 逻辑与物理学 - 讨论了逻辑学在物理学概念模型构建中的应用。 - 探究了逻辑推理在实验设计与数据分析中的作用。 #### 4.3 逻辑与计算机科学 - 分析了逻辑...

    离散数学总结PPT课件.pptx

    2. 数理逻辑:包括命题逻辑和一阶逻辑,用于精确表述和推理。命题逻辑涉及命题、真值、联结词以及等值演算,例如通过真值表、等值式和消去规则进行公式转换。一阶逻辑引入量词,允许对个体进行量化,使得我们能够...

    2008北航计算机考研大纲

    复习内容包含命题逻辑(联结词、等值演算、逻辑推论)、谓词逻辑(谓词、量词、等值演算、逻辑推论)、公理系统(命题逻辑和谓词逻辑的公理系统、可靠性和完全性)以及归结法原理(前束范式、斯科伦范式、归结法在...

Global site tag (gtag.js) - Google Analytics