我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 蕴含谓词 >

命题逻辑的soundness可靠性和completeness完备性

归档日期:06-24       文本归类:蕴含谓词      文章编辑:爱尚语录

  初学数理逻辑的时候,一个非常重要的点就是对可靠性与完备性概念的理解,这两个概念极为重要,却又经常让人觉得 难以理解。 说它重要是因为它涉及逻辑系统的基本框架,初学数理逻辑,最重要的倒不在于你有多高超的技巧去推导那些 公式,而在于对一些基本概念的理解和把握,这是思想层面的,如同学习概率论和数理统计不在于记住那几个公式和定理, 而在于获得一些基本的概率和统计的思想。TED演讲时,有一次一位在线教育的创始人谈到教育时说到,我们教授学生知识, 不是让他们仅仅记住那些公式,而是改变他们认识世界的方式。请大家一定记住这一点。同时也请注意,这句话不是在说 记住公式没有用。学习数理逻辑,要时刻提醒自己,我们需要去推导定理,但目的不在于此。 可靠性与完备性之所以让人难以理解,原因是多方面的。一方面是初学数理逻辑,根本不知道书上那些定理是要做什么,也 就是前面说的,对知识的整体没有一个宏观的把握,注意:这是教师的责任。另一方面在于对语法和语义不理解,经常将 二者混在一起看。而这一方面的“不理解”,又在于我们将现实世界的逻辑与形式系统中逻辑又混在一起看。 下面就谈一下我对可靠性与完备性的理解。特别需要说明的是,这是针对命题逻辑的,并且我也是初学,很可能有一些错误, 请不怀疑的怀疑,怀疑的指出。 要谈可靠性与完备性,需要先理解语法和语义,把这两个概念弄清楚了,理解可靠性与完备性就会水到渠成。 命题逻辑系统由语法和语义两部分组成。一旦定义了语法和语义,整个逻辑系统也就构建好了。下面我们开始构造命题逻辑系统。

  这就是一个基本的语法规则,而且是人为定义的。在没有这个定义之前,它就存在于语言当中,人们将这种在自然语言中 广泛出现的形式总结成简单的规则,这样方便了我们对语言的学习与利用。我们把一些经常出现的规则集合在一些,就构成了语法。请一定记住,一旦这些规则被从现实世界中剥离出来,它们就有了一定程度的独立性,不信赖于具体的含义。 例如,”我吃饭”,和 “饭吃我”都符合主谓宾结构,我们认为后者不正确不是因为主谓宾结构不对,而是它所表达的意思不正确,这是语义层面,而不是语法层面。

  从“我喜欢计算机科学,而且我也喜欢数学”中 推理出 “我喜欢计算机科学”。

  从“我经常编写程序,而且我也经常读书” 中 推理出 “我经常编写程序”。

  我们并没有意识到自己是在做推理,但是我们确确实实完成了一次推理,确且地说,是两次。并且我们发现这两次推理具有高度统一的形式:

  例如,“我喜欢计算机科学”是一个命题,但是“我喜欢文学吗?”就不是一个命题。

  对比一下自然语言中语法规则的产生,这一次,我们再次将这些在现实世界中广泛出现的推理形式抽象出来,把他们组成一个集 合,于是,我们就有了下面这组命题逻辑的自然推导规则集合。

  其中的 ∧ e1 ,我们叫做规则。e的意思是消除(elimination). 这条规则从 φ∧ψ 中消除了 ∧,只留下了前面的φ, e1 中的 1 就是指 φ,因为它排在第1个,对比一下 ∧ e2 就会明白了。

  规则中的i表示引入(introduction). 规则的具体含义可参考1.至于其中的 ¬ , →, … ,我认为目前没有必要知道含义,你仅仅需要知道他们是一些推导规则就好了。虽然你们多半都知道含义,但是,现在把它们忘了吧。

  请再一次又一次地记住,这些推导规则从现实世界中剥离出来后,就有了他们的独立性,和具体的含义无关,例如:

  我们只知道 φ 和 ψ 是命题,有真假,但是,不管他们是真是假,都不影响这条规则的成立。这一点请千万注意。 例如:

  由上面的那条推导规则,可以推出φ,即”我不喜欢计算机科学”,尽管这个结论是假的,但这和这条推导规则的成立无关。不能说, 这规则得出假的结论,所以这条规则就是不正确的。

  前面在引入自然推导规则时,我们举了一些例子,如自然语言中的对应形式,包括命题的真假,等等。这一切都是为了 理解这些规则是怎么来的。那么,从现在开始,请忘掉那些例子,让你的知识保留在只知道图1所示的自然推导规则表.我们现在仅仅知道这张规则表,那么,这些规则用来做什么呢? 这些规则可以用来推理。

  推理有效性的概念与可靠性,完备性直接相关,所以一定保证你理解它的含义。 推理的有效性是指:使用图1中定义的自然推导规则以及前提(φi),可以得出结论(ψ)。 例如我们如果问: p, ¬¬(q ∧ r) - ¬¬ p ∧ r 是不是有效的,那只需要看我们能不能仅根据自然推导规则,将前提转化为结论。转化的过程,我们叫做:证明(proof).

  上面的证明过程,例如第6行,最右面的 ∧i 3,5 表示使用第3,5行的公式和规则∧i, 得到第6行的公式。

  关于语法部分,现在只需要知道两件事:一:公式及自然推导规则表;二:推理和推理的有效性。

  你很容易知道这句话是什么意思。但是你想过为什么你能知道这句话是什么意思吗?

  原因在于,首先你知道“我”是什么意思,“饭”是什么意思,其次你知道“吃”是什么意思。最后,你明白“我吃饭”三个字连在一起是什么意思。你可能觉得这是一句废话,但是后面提到命题逻辑时,你可能就会明白为什么在这儿说了一句废话。

  一是,这句话是一个主谓宾的结构,但是即使你不知道这个句子的语法,你仍然可以知道它的含义。

  同时,在 “我吃饭”这个句子与“我吃饭的含义”之间存在着一种映射关系。语义中如果没有这种映射关系,那么你说“我吃饭”的时候, 别人可能觉得你在看书。

  所以, 我们得到了一个句子:“我吃饭”。 在命题逻辑中,我们也有自己的“句子结构”,例如: φ ∧ ψ 之所以没有自己的“句子”,是因为我们的公式 φ, ψ 没有自己的取值的集合,所以, 我们首先定义公式取值的集合:{T,F},T代表真,F代表假。 看到了吧,这和前面讲的“命题是可以判断真假的”是相关的。 有了取值集合,我们就可以定义自己的“句子”了: T ∧ F T ∨ T T → F … 我们知道,语义是指句子的含义,现在有了句子了,那么句子的含义是什么呢? 从自然语言的例子中,我们知道句子的含义是一个集合,在命题逻辑里,“句子含义”的集合仍然由我们来定义, 命题逻辑中我们只关心真与假,所以,这个集合,我们仍然定义为:{T,F} 好了,现在我们有了“句子”,有了“句子含义”取值的集合,那么定义一个语义系统,还需要 什么呢?同样对比自然语言的例子中,我们最后说的那一点,还需要一种映射,将句子与句子的含义映射起来,即将 T ∧ F 等句子与 T, F映射起来。而这,就是耳熟能详,家喻户晓的, 线 真值表

  有了真值表,我们才知道 T ∧ F 意味着什么, F → T 意味着什么。

  看下面这种形式: φ1, φ2, …, φn = ψ 其中的 = 即表示蕴含关系,从上面语法和语义的讨论中,你可能已经明白了,这只是一种语法层面的定义, 那么蕴含的语义是什么呢?翻译为人话就是:当我说蕴含的时候,我是在说什么。 蕴含就是在说,如果 φ1, φ2, … , φn 的取值都为T, 那么 ψ 的取值一定为 T. 例如: p ∧ q , q, r = p . 当 p ∧ q 为T, q为T,r为T时, P一定为T. 所以 p ∧ q , q, r 蕴含 p. 那么,什么是蕴含的有效性呢? 例如我问: p ∨ q , q, r= p 是有效的么? 我其实是在问, p ∨ q 为 T, q为T, r为T时, p一定为T么? 如果p一定为T, 那么 p ∨ q , q, r= p 是有效的。否则,p ∨ q , q, r= p 是无效的。 所以,如果我说 φ1, φ2, … , φn 蕴含 ψ, 意思等同于: φ1, φ2, …, φn = ψ 是有效的。

  经过了前面冗长的关于语法和语义的介绍,终于可以开始介绍可靠性与完备性了。在此之前,请保证你可以正确区分 - 和 = ,知道推理的有效性和语义蕴含的有效性意味着什么。 在完成命题逻辑系统的定义后,我们想知道这个系统的一切性质,其中最重要的性质就是可靠性与完备性。这一节的两个定理告诉我们,命题逻辑系统满足可靠性和完备性。

  可靠性定理:令 φ1, φ2, …, φn 和 ψ 为命题逻辑中的公式,如果 φ1, φ2, …, φn - ψ 是有效的, 那么 φ1, φ2, …, φn = ψ 是有效的。 这个定理是在说,我们为逻辑系统定义好语法和语义后,如果在语法上,我们可以利用推导规则,将φ1, φ2, …, φn 转化为 ψ,

  首先,我们需要理解,可靠性是逻辑系统满足的一个性质。如果有一天,我们构造了另一个逻辑系统,自己定义了 语法,定义了语义,那么,我们可能需要问一下自己:我定义的这个逻辑系统满足可靠性么? 上面的靠性定理是指在命题逻辑中,我们定义了语法:自然推导规则,推导及其有效性;我们定义了语义:真值表,语义蕴含及其有效性。在由这些定义构成的一个命题逻辑系统中,像可靠性定理描述的那样的性质是满足的。一旦我们 证明了一个逻辑系统满足了可靠性,我们就可以利用这个好的性质来做一些事。

  现在我们明白了,之前定义的命题逻辑系统满足可靠性。现在,我们就可以利用这一点来做一点事了。 我们可以利用逻辑系统的可靠性来确定:有一些证明是不存在的。 例如:在命题逻辑系统中给定前提 φ1, φ2, …, φn, 能否证明 ψ ?这其实是在问: φ1, φ2, … , φn - ψ 是否是有效的。 如果这个前提和结论非常复杂,那么你很可能证明不出来,因为证明通常是需要一点灵感的,而灵感通常是难得的。 但是,你证明不出来不能说明这个证明不存在。那我们应该怎么做呢?

  因为根据可靠性定理,如果 φ1, φ2, …, φn - ψ 是有效的, 那么 φ1, φ2, …, φn = ψ 是有效的, 与我们根据真值表得出的结论相矛盾。

  完备性定理:令 φ1, φ2, …, φn 和 ψ 为命题逻辑中的公式,如果 φ1, φ2, …, φn = ψ 是有效的, 那么 φ1, φ2, …, φn - ψ 是有效的。 可以看出,这和可靠性定理的定义正好相反。这其实是在说,在一个逻辑系统中,如果从语义上看, φ1, φ2, …, φn = ψ 是有效的, 那么我们一定可以为φ1, φ2, …, φn - ψ 找到一个证明。 在命题逻辑中,完备性定理也是成立的。具体的证明过程参考1

  与可靠性一样,完备性也是逻辑系统的性质。那么完备性有什么用呢?在一个逻辑系统中,如果我们知道一些前提是 线, …,φn 都为真,那么,我们想知道在这样的条件下,结论 ψ 也一定是线, …, φn = ψ 是否是有效的。那么我们可能想找一个由φ1, φ2, …, φn 到 ψ 的证明,即利用推导规则将 φ1, φ2, …, φn 转化为 φ. 这时候,完备性就会告诉我们, 如果 φ1, φ2, …, φn = ψ 是有效的,那么,这样 的证明一定存在。假如你的逻辑系统不满足完备性,那么即使φ1, φ2, …, φn = ψ 是有效的,但是它的证明也可能 不存在,那你的努力可能就是徒劳的。

  关于可靠性与完备性的讨论到这里就结束了,这只是我学习参考资料1 第1章的一些体会,这本书相当不错,特别推荐给诸位。如果有什么问题,欢迎随时讨论。

  前言 绪论 第一章 预备知识 第二章 经典命题逻辑 第三章 经典一阶逻辑 第四章 可靠性和完备性 第五章 公理推演系统 第六章 构造性逻辑 第七章 模态命题逻辑 第八章 模态一阶逻辑 附录 自然推演中形式证明的简明形式 参考文献 符号表 ...

  经验法则如下:1测试人员参与需求评审,需求人员参与测试用例的评审不懂需求,不了解需求的测试人员是不可能设计出完备的测试用例的。测试人员参与需求评审一是可以评审需求的可测试性,二是了解需求。 需求人员评...

  【代码管理】GitHub超详细图文攻略 - Git客户端下载安装 GitHub提交修改源码工作流程 Git分支 标签 过滤 Git版本工作流

  关于Python中的lambda,这篇阅读量10万+的文章可能是你见过的最完整的讲解

  真理的语义理论断言:对某个命题是真的的任何断言,可以只作为形式上的需要而做出来,不管表达命题自身用了什么语言。 1933年,塔尔斯基首创“真理”的语义概念(原创)。塔尔斯基在《OntheConcept...博文来自:

  本文试图归纳若干关于《数理逻辑》学习的基础问题,并给出相关参考书目,指导本科生在该领域的学习。多年没学数理逻辑了,错漏难免。另外,感觉应该早点进入模态逻辑的学习,可更接近应用。LICS问题1、数理逻辑...博文来自:

  安卓开发--textView的字体样式设置(设置宋体,微软雅黑等)12-10

  最近项目中出现把字体设置成宋体,微软雅黑,黑体,楷体等的需求;度娘发现Android系统默认支持三种字体,分别为:“sans”, “serif”, “monospace,除此之外还可以使...博文来自:

  Spring3MVC提交弹出窗口表单后,自动返回父窗口的列表页面02-16

  阅读数 1944(一)【中文网上深入介绍哥德尔不完备定理的文章很少,我这篇文章写得很长,花了不少时间打磨它,希望能帮助到爱好数学与逻辑的人。文章把理解哥德尔不完备定理分为了五重,建议只是......

  如果有一个人说:“我在说谎”那么,他说的话是谎言吗?如果是假的,那么他说的反而是真的,如果是真的,那么他说的反而是假的了。如果这话是匹诺曹说的,恐怕他的鼻子就得变成永动机了。匹诺曹:“怪我咯?”很多人...博文来自:的博客

  什么是图灵完备性语言?一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。一个能计算出每个图灵可计算函数(Turing-computablefunction)的计算系统被称为图灵完备的。...博文来自:Jeffreys 专栏

  泛函分析内积空间希尔伯特空间正交基正交列的完备性博文来自:一朵花开的时间

  作者:离散梦欢迎大家给出宝贵的建议!  命题逻辑的基本概念  1.1命题与联结词:非真即假的陈述句称作命题。【祈使句、疑问句、感叹句、悖论都不是命题】作为命题的陈述句所表达的判断结果称作命题的真值,真...博文来自:离散梦

  路径规划算法的目的是要规划出一条从起始点到目标点的无碰撞可行路径。常见的路径规划算法大致可以分为以A*算法为代表的基于搜索的规划算法、以RRT为代表的基于采样的规划算法和以遗传算法为代表的基于启发式的...博文来自:不知道起什么名字

  第三章命题逻辑的推理理论1.推理的形式结构(1)定义3.1:设A1,A2,A3...Ak和B都是命题公式,若对于A1,A2,A3...Ak和B中出现的命题变项的任意一组赋值,或者A1,A2,A3......博文来自:nicecat的专栏

  数学的进步是集合完备化与映射简洁化的共同作用。映射的简化会催化新的定义的产生,新的定义往往又会衍生出新的完备化过程,两者此消彼长,可看成是一个过程的两个对偶的方面。这篇文章会试着来讲述这个完备化过程,...

  在数理逻辑中,哥德尔不完备定理是库尔特 ·哥德尔于 1930年证明并发表的两条定理。哥德尔定理是 一阶逻辑 的定理,故最终只能在这个框架内理解。简单地说,第一条定理指出:任何一个相容的数学形式...博文

  每种数字标准形都能提供很多信息,如代数式的因式分解可判断代数式的根情况。逻辑公式在等值演算下也有标准形--范式,范式有两种:析取范式和合取范式。简单合取式和简单析取式定义2.2命题变项及其否定统称作文...博文

  一个在时间限制区间[a,b]上的正交函数集合是完备的正交函数集合满足以下2个条件:1该区间上不存在任何能量有限的信号s(t)s(t),即∫bas(t)2dt...博文

  用CentOS 7安装cadence搭建适合IC Design的科研环境(二)——操作系统的相关配置

  extjs glyph 图标web性接口测试教程大数据相关的机器学习方法

本文链接:http://jamescaronna.com/yunhanweici/136.html