第4章 谓词逻辑

,主标题,主文本标题,二级标题,三级标题,四级标题,五级标题,电子科技大学离散数学课程组,国家精品课程,132,*,离 散 数 学,电子科技大学,计算机科学与工程学院,示 范 性 软 件 学 院,02 十月 2024,2024/10/2,第,4,章 谓词逻辑,例如,(,著名的苏格拉底三段论,),（,1,）所有的人都是要死的；,（,2,）苏格拉底是人。,（,3,）苏格拉底是要死的。,命题逻辑能够解决的问题是有,局限性,的。只能进行,命题间关系,的推理，无法解决与,命题的结构和成分,有关的推理问题。,2024/10/2,苏格拉底三段论,P,：所有的人都是要死的；,Q,：苏格拉底是人。,R,：所以，苏格拉底是要死的。,可见，,P,，,Q,，,R,为不同的命题，无法体现三者相互之间的联系。,问题在于这类推理中，各命题之间的逻辑关系不是体现在原子命题之间，而是体现在,构成原子命题的内部成分之间,。对此，命题逻辑将无能为力。,2024/10/2,本章内容,谓词逻辑中的基本概念,1,谓词的翻译原理,2,谓词的合式公式,3,谓词的标准型,-,范式,4,2024/10/2,4.1,本章学习要求,重点掌握,了解,1,1,谓词逻辑符号化及真值,2,谓词公式的有效性和基本等价公式,3,前束范式与,SKOLEM,范式,2,1,谓词公式的解释和真值,2,自由变元和约束变元,一般掌握,2024/10/2,4.2,谓词逻辑中的基本概念与表示,命题是具有真假意义的陈述句，从语法上分析，一个陈述句由,主语和谓语,两部分组成。,例如，,“,计算机,是现代科学技术必不可少的工具,”,例如,“,陈华,是电子科技大学的学生,”,；,“,张强,是电子科技大学的学生,”,。,若：是电子科技大学的学生,-P(,陈华,),-P(,张强,),2024/10/2,谓词,更一般地，,P(x),：,x,是电子科技大学的学生。,x,：个体词,P,：谓词,P(x):,命题函数,P(x),2024/10/2,个体词与谓词,定义,4.2.1,在原子命题中，可以独立存在的客体（句子中的主语、宾语等），称为,个体词,(Individual),。而用以刻划客体的性质或客体之间的关系即是,谓词,(Predicate),。,单纯的谓词或单纯的个体词都无法构成一个完整的逻辑含义，只有将它们结合起来时才能构成一个独立的逻辑断言。,例,1,成都、北京、赵明、,20060806,班、计算机科学,等等仅仅是简单的个体常量；,“,是中国的首都,”,、,“,是计算机的基础课程,”,等仅仅是简单的谓词，它们都不能构成完整的句子。,2024/10/2,例子,例,2,考察下列句子：,（,1,）,北京,是中国的首都,；,（,2,）,离散数学,是计算机的基础课程,；,（,3,）,刘翔,是一个跨栏世界冠军,；,（,4,）,中国人,是很聪明的,。,（,5,）,小张,和,小李,同岁,。,（,6,）,x,与,y,具有倍数关系,。,（,7,）,点,A,位于,点,B,和,点,C,之间,。,2024/10/2,个体词的分类,（,1,）表示,具体的或特定,的个体词称为,个体常量,(Individual Constant),，一般个体词常量用带或不带下标的小写英文字母,a, b, c,，,，,a,1, b,1, c,1,等表示；,（,2,）表示,抽象的或泛指,的个体词称为,个体变量,(Individual Variable),，一般用带或不带下标的小写英文字母,x, y, z, x,1, y,1, z,1,等表示。,2024/10/2,个体域,定义,4.2.2,（,1,）,个体词的取值范围,称为,个体域,(,或,论域,)(Individual Field),，常用,D,表示；,（,2,）而,宇宙间的所有个体域聚集,在一起所构成的个体域称为,全总个体域,(Universal Individual Field),。,2024/10/2,n,元谓词,定义,4.2.3,设,D,为,非空的,个体域，定义在,D,n,(,表示,n,个个体都在个体域,D,上取值,),上取值于,0,1,上的,n,元函数，称为,n,元命题函数,或,n,元谓词,(Propositional Function),，记为,P(x,1, x,2, x,n,),。此时，个体变量,x,1, x,2, x,n,的,定义域,都为,D,，,P(x,1, x,2, x,n,),的,值域,为,0, 1,。,2024/10/2,例,4.2.1,设有如下命题，并用,n,元谓词进行表示。,P,：,王童,是一个三好学生,；,Q,：,李新华,是,李兰,的父亲,；,R,：,张强,与,谢莉,是好朋友,；,S,：,武汉,位于,北京,和,广州,之间,。,2024/10/2,例,4.2.1,（续）,解,定义命题函数：,S(x),：,x,是一个三好学生；,F(x, y),：,x,是,y,的父亲；,T(x, y),：,x,与,y,是好朋友；,B(x,y,z),：,x,位于,y,和,z,之间；,用符号表示个体词：,a,：王童；,b,：李新华；,c,：李兰；,d,：张强；,e,：谢莉；,f,：武汉；,g,：北京；,h,：广州。,则命题可表示为：,P,：,S(a),；,Q,：,F(b, c),；,R,：,T(d, e),；,S,：,B(f, g, h),。,2024/10/2,结论,（,1,）谓词中,个体词的顺序是十分重要,的，不能随意变更。如命题,F(b, c),为,“,真,”,，但命题,F(c, b),为,“,假,”,；,（,2,）,一元谓词,用以描述,某一个个体的某种特性,，而,n,元谓词,则用以描述,n,个个体之间的关系,。,（,3,）,0,元谓词,(,不含个体词的,),实际上就是一般的命题；,2024/10/2,结论（续）,（,4,）,具体命题的谓词表示形式,和,n,元命题函数,(n,元谓词,),是不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。如上例中,S(a),是有真值的，但,S(x),却没有真值；,（,5,）,一个,n,元谓词不是一个命题,，但,将,n,元谓词中的个体变元都用个体域中具体的个体取代,后，就,成为一个命题,。而且，个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响。,2024/10/2,4.2.2,量词,例,4.2.2,符号化下述命题：,（,1,）,所有的,老虎都要吃人；,（,2,）,每一个,大学生都会说英语；,（,3,）,所有的,人都长着黑头发；,（,4,）,有一些,人登上过月球；,（,5,）,有一些,自然数是素数。,2024/10/2,例,4.2.2(,续,),解,设立如下谓词：,P(x),：,x,会吃人；,Q(x),：,x,会说英语；,R(x),：,x,长着黑头发；,S(x),：,x,登上过月球；,T(x),：,x,是素数。,则有：（,1,）,所有的,x,，,P(x) x,老虎；,（,2,）,每一个,x,，,Q(x) x,大学生,；,（,3,）,所有的,x,，,R(x) x,人,；,（,4,）,有一些,x,，,S(x) x,人,；,（,5,）,有一些,x,，,T(x) x,自然数,。,2024/10/2,量词含义,有些,x,；,至少有一个,x,；,某一些,x,；,存在,x,；等等,。,所有的,x,；,任意的,x,；,一切的,x,；,每一个,x,；等等。,2024/10/2,全称量词与存在量词,定义,4.2.4,称,(,x),为,全称量词,（,Universal Quantifier,），,(,x),为,存在量词,（,Existential Quantifier,），其中的,x,称为,作用变量,（,Function Variable,）。一般将其量词加在其谓词之前，记为,(,x)F(x),，,(,x)F(x),。此时，,F(x),称为全称量词和存在量词的,辖域,(Scope),。,2024/10/2,例,4.2.2(,续,),（,1,）,(,x)P(x),x,老虎,；,（,2,）,(,x)Q(x),x,大学生,；,（,3,）,(,x)R(x),x,人,；,（,4,）,(,x)S(x),x,人,；,（,5,）,(,x)T(x),x,自然数,。,2024/10/2,不便之处,（,1,）,从,书写上,十分不便，总要特别注明个体域；,（,2,）,在同一个比较复杂的句子中，对于不同命题函数中的个体可能属于不同的个体域，此时,无法清晰,表达；,如例,(1),和,(4),的合取,(,x)P(x)(,x)R(x),x,人,x,老虎,2024/10/2,不便之处,(,续,),（,3,）,若个体域的注明不清楚，将造成,无法确定其真值,。即,对于同一个,n,元谓词，不同的个体域有可能带来不同的真值,。,例如 对于语句,“,(,x)(x+6 = 5),”,可表示为：,“,有一些,x,，使得,x+6 = 5,”,。该语句在下面两种个体域下有不同的真值：,（,a,）,在实数范围内时，确有,x=-1,使得,x+6 = 5,，因此，,(,x)(x+6 = 5),为,“,真,”,；,（,b,）,在正整数范围内时，则找不到任何,x,，使得,x+6=5,为,“,真,”,，所以，,(,x)(x+6=5),为,“,假,”,。,2024/10/2,不便之处的根源,对了，都是因为需要特别标注每个谓词的个体域所致！,全总个体域,2024/10/2,特性谓词,新的问题出现了，,U(x),如何与,(,x)P(x),结合才符合逻辑呢？,U(x),：,x,是老虎,x,老虎,2024/10/2,谓词逻辑符号化的两条规则,统一个体域为,全总个体域,，而对每一个句子中个体变量的变化范围用一元,特性谓词,刻划之。这种特性谓词在加入到命题函数中时必定遵循如下原则：,（,1,）对于,全称量词,(,x),，刻划其对应个体域的特性谓词作为,蕴涵式之前件,加入。,（,2,）对于,存在量词,(,x),，刻划其对应个体域的特性谓词作为,合取式之合取项,加入。,2024/10/2,特性谓词的例子,想想，为什么要这样规定特性谓词加入的原则呢？若不遵循会出现什么样的问题？,例如，符号化,“,所有的,老虎都要吃人,”,这个命题,若,P(x),：,x,会吃人,U(x),：,x,是老虎,则符号化的正确形式应该是,(,x)(U(x)P(x),它的含义是：,“,对于任意的,x,如果,x,是老虎，则,x,会吃人,”,，符合原命题的逻辑含义。,若符号化为,(,x)(U(x),P(x),它的含义是：,“,对于任意的,x,x,是老虎，并且,x,会吃人,”,，,与原命题,“,所有的老虎都要吃人,”,的逻辑含义不符。,2024/10/2,例,4.2.3,用谓词逻辑符号化下述语句：,(1),天下,乌鸦,一般,黑；,(2),没,有人,登上过木星；,(3),在美国留学的学生,未必,都,是亚洲人；,(4),每个,实数都,存在,比它大的另外的实数；,(5),尽管,有人,很聪明，,但未必,一切,人都聪明；,(6),对于,任意,给定的,0,，,必,存在,着,0,，使得对,任意,的,x,，,只要,|x-a|,，,就,有,|f(x)-f(a)|0,，,必,存在,着,0,，使得对,任意,的,x,，,只要,|x-a|,，,就,有,|f(x)-f(a)|0)(,)(,0)(,x),(|x-a|,)(|f(x)-f(a)|,),。,2024/10/2,4.2.3,谓词的语言翻译,特殊的，当个体域,D,x,0, x,1,是,可数集合,时，上述,(,x)G(x),、,(,x)G(x),的真值可表示为：,(,x)G(x)=G(x,0,)G(x,1,).,(,x)G(x)=G(x,0,)G(x,1,).,2024/10/2,个体域可数或有限,更特别的，当个体域,D,x,0, x,1,x,n,是,有限集合,时，上述,(,x)G(x),、,(,x)G(x),的真值可以用与之等价的命题公式来进行表示。,(,x)G(x)=G(x,0,)G(x,1,).G(x,n,),(,x)G(x)=G(x,0,)G(x,1,).G(x,n,),2024/10/2,例,4.2.5,设,P(x),：,x,是素数；,I(x),：,x,是整数；,Q(x, y),：,x+y=0,。用语句描述下述句子，并判断其真假值。,（,1,）,(,x)(I(x)P(x),；,（,2,）,(,x) (I(x)P(x),；,（,3,）,(,x) (,y)(I(x)I(y)Q(x, y),；,（,4,）,(,x)(I(x)(,y)(I(y)Q(x, y),；,（,5,）,(,x)(,y)(I(x)(I(y)Q(x, y),。,2024/10/2,例,4.2.5,解,句子,(1),可描述为：,“,对任意的整数,x,，,x,一定是素数,”,，真值为,“,假,”,；,句子,(2),可描述为：,“,存在一些整数,x,，,x,是素数,”,，真值为,“,真,”,；,句子,(3),可描述为：,“,对任意的整数,x,，,y,，都有,x+y=0,”,，真值为,“,假,”,；,句子,(4),可描述为：,“,对任意的整数,x,，都存在着整数,y,，使得,x+y=0,”,，真值为,“,真,”,；,句子,(5),可描述为：,“,存在着整数,x,，使得对任意的整数,y,，都有,x+y=0,”,，真值为,“,假,”,。,2024/10/2,4.2.4,谓词翻译难点,1,、,一元谓词,用以描述,某一个个体的某种特性,，而,n,元谓词,则用以描述,n,个个体之间的关系,；,2,、如有多个量词，则读的顺序按,从左到右,的顺序；另外，量词对变元的约束，往往与量词的次序有关，不同的,量词次序,，可以产生不同的真值，此时对多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原有的含义。,2024/10/2,谓词翻译难点（续）,3,、根据命题的实际意义，选用全称量词或存在量词。,全称量词加入,时，其刻划个体域的特性谓词将以,蕴涵的前件,加入，,存在量词加入,时，其刻划个体域的特性谓词将以,合取项,加入；,4,、有些命题在进行符号化时，由于语言叙述不同，可能翻译不同，但它们表示的意思是相同的，即,句子符号化形式可不止一种,。,2024/10/2,4.2.5,谓词翻译的应用,例,4.2.4,将下列命题符号化,（,1,）兔子比乌龟跑得快；,（,2,）有的兔子比所有乌龟跑得快；,（,3,）并不是所有的兔子都比乌龟跑得快；,（,4,）不存在跑得同样快的两只兔子。,谓词设定：,P(x),：,x,是兔子；,Q(x),：,x,是乌龟；,R(x, y),：,x,比,y,跑得快；,T(x, y),：,x,与,y,跑得同样快。,2024/10/2,例,4.2.4,解,（,1,）,(,x) (,y)(P(x)Q(y)R(x, y),；,（,2,）,(,x)(P(x)(,y)(Q(y)R(x, y),；,（,3,）,(,x) (,y)(P(x)Q(y)R(x, y),或者,(,x)(,y)(P(x)Q(y),R(x, y),；,（,4,）,(,x)(,y)(P(x)Q(y)T(x, y),或者,(,x)(,y)(P(x)Q(y),T(x, y),。,2024/10/2,例,4.2.5,符号化下述一组语句：,只要是需要室外活动的课，郝亮都喜欢；所有的公共体育课都是需要室外活动的课；篮球是一门公共体育课；郝亮喜欢篮球这门课。,解,设,O(x),：表示,x,是需要室外活动的课；,L (x, y),：表示,x,喜欢,y,；,S (x),：表示,x,是一门公共体育课；,Hao,：表示郝亮；,Ball,：表示篮球。,2024/10/2,例,4.2.5,解（续）,上述句子可符号化为：,(,x)(O(x)L(Hao, x),；,(,x)(S(x)O(x),；,S(ball),；,L(Hao, Ball),。,2024/10/2,例,4.2.6,符号化下述一组语句：,海关人员检查每一个进入本国的不重要人物；某些走私者进入该国时仅仅被走私者所检查；没有一个走私者是重要人物；海关人员中的某些人是走私者。,解,设,E(x),：表示,x,进入国境；,V(x),：表示,x,是重要人物；,C(x),：表示,x,是海关人员；,P(x),：表示,x,是走私者；,B(x, y),：表示,y,检查,x,。,2024/10/2,例,4.2.6,解（续）,上述句子可符号化为：,(,x)(E(x),V(x)(,y)(C(y)B(x, y),；,(,x)(P(x)E(x)(,y)( B(x,y)P(y),；,(,x)(P(x),V(x),；,(,x)(P(x)C(x),。,2024/10/2,4.3,谓词合式公式与解释,谓词公式涉及如下四种符号：,（,1,）,常量符号,：用带或不带下标的,小写英文字母,a, b, c, a,1, b,1, c,1,来表示。当个体域名称集合,D,给出时，它可以是,D,中的某个元素,；,（,2,）,变量符号,：用带或不带下标的,小写英文字母,x, y, z, ., x,1, y,1, z,1,.,来表示。当个体域名称集合,D,给出时，它可以是,D,中的任意元素,；,2024/10/2,符号定义,（,3,）,函数符号,：用带或不带下标的,小写英文字母,f, g, h, ., f,1, g,1, h,1, .,来表示。当个体域名称集合,D,给出时，,n,元函数符号,f(x,1, x,2, x,n,),可以是,D,n,D,的任意一个函数；,（,4,）,谓词符号,：用带或不带下标的,大写英文字母,P, Q, R,., P,1, Q,1, R,1,.,来表示。当个体域名称集合,D,给出时，,n,元谓词符号,P(x,1, x,2, x,n,),可以是,D,n,0,，,1,的任意一个谓词。,2024/10/2,为何需要函数符号？,例如 符号化,“,周红的父亲是教授,”,：,设,f(x),：,x,的父亲；,P(x),：,x,是教授；,c,：周红,此时,P(f(c),表示,“,周红的父亲是教授,”,这一命题。,函数的使用给谓词逻辑中的个体词表示,带来了很大的方便,2024/10/2,项,定义,4.3.1,谓词逻辑中的,项,（,Term,），被递归地定义为：,（,1,）,任意的常量符号,或,任意的变量符号,是项；,（,2,）若,f(x,1,x,2,x,n,),是,n,元函数符号,，,t,1,t,2,t,n,是项，则,f(t,1, t,2, t,n,),是项；,（,3,）仅由,有限次使用,(1),，,(2),产生的符号串才是项。,2024/10/2,原子公式,定义,4.3.2,若,P(x,1, x,2, x,n,),是,n,元谓词,，,t,1,，,t,2,，,，,t,n,是项，则称,P(t,1, t,2, t,n,),为,原子谓词公式,(Atomic Propositional Formulae),，简称,原子公式,(Atomic Formulae),。,2024/10/2,定义,4.3.3,满足下列条件的表达式，称为,合式公式,(,Well-Formed Formulae/Wff,),，简称,公式,(,Formulae,),。,（,1,）,原子公式,是合式公式；,（,2,）若,G,，,H,是合式公式，则,(,G),、,(,H),、,(GH),，,(GH),、,(GH),、,(G,H),也是合式公式；,（,3,）若,G,是合式公式，,x,是个体变量，则,(,x),G,、,(,x)G,也是合式公式；,（,4,）仅仅由,(1)-(3),产生的表达式才是合式公式。,2024/10/2,例子,(,x)(,y)(P(x, y)(Q(x,y)R(x,a,f(z),，,(,x)(P(x)(,y)R(x,y),，,(,x)(P(x) R(x),。,等,都是公式。,而,(,x)(P(x)R(x),，,(,y)(,x)(P(x, y),。,等则不是公式,。,2024/10/2,4.3.2,自由变元和约束变元,定义,4.3.4,给定一个合适公式,G,，若变元,x,出现在使用变元的量词的辖域之内，则称变元,x,的出现为,约束出现,(,Bound Occurrence,),，此时的变元,x,称为,约束变元,(,Bound Variable,),。若,x,的出现不是约束出现，则称它为,自由出现,(,Free Occurrence,),，此时的变元,x,称为,自由变元,(,Free Variable,),。,量词辖域的确定方法：,（,1,）若量词后,有括号,，则,括号内的子公式,就是该量词的辖域；,（,2,）若量词后,无括号,，则,与量词邻接的子公式,为该量词的辖域。,2024/10/2,例,4.3.1,确定以下公式各量词的辖域以及各个体变量为自由变元还是约束变元。,（,1,）,(,x)(P(x)(,y)R(x, y),；,（,2,）,(,x)P(x)Q(x, y),；,（,3,）,(,x)(,y)(P(y,z)Q(x,y)(,x)R(x,y),；,（,4,）,(,x)(P(x)R(x)(,y)Q(x,y),。,2024/10/2,例,4.3.1,解,在,(1),中,，,P(x),中的,x,，,R(x,y),的,x,，,y,都为约束变元。,在,(2),中,，,P(x),中的,x,为约束变元，,Q(x,y),中的,x,，,y,是自由变元。,在,(3),中,，,P(y,z),、,Q(x,y),中的,x,y,都为约束变元，,z,为自由变元；,R(x,y),中的,x,为约束变元，,y,为自由变元。,在,(4),中,，,P(x),，,R(x),中的,x,为约束变元，,Q(x, y),中的,x,为自由变元、,y,为约束变元。,2024/10/2,变元混淆,（,4,）,(,x)(P(,x,)R(,x,)(,y)Q(,x, y),约束变元,自由变元,在一个公式中，某一个变元的出现既,可以是自由的，又可以是约束的,，如,(4),中的,x,。为了使得我们的研究更方便，而不致引起混淆，同时为了使其式子给大家以一目了然的结果，对于表示不同意思的个体变元，我们总是以,不同的变量符号,来表示之。,2024/10/2,两个规则,规则,1(,约束变元的改名规则,),：,（,1,）,将量词中出现的变元以及该量词辖域中此 变量之所有约束出现都用新的个体变元替换,；,（,2,）,新的变元一定要有别于改名辖域中的所有其它变量,。,2024/10/2,两个规则,规则,2(,自由变元的代入规则,),：,（,1,）,将公式中出现该自由变元的每一处都用新的个体变元替换,；,（,2,）,新变元不允许在原公式中以任何约束形式出现。,2024/10/2,例,4.3.2,（,1,）将公式,(,x)(P(x)Q(x, y)R(x, y),中的约束变元,x,进行改名；,（,2,）将公式,(,x)(P(x)Q(x, y)R(x, y),中的约束变元,y,进行代入。,解,利用规则,1,对,x,进行改名，则：,(,z)(P(z)Q(z, y)R(x, y),(,z)(P(z)R(x, y)R(x, y),(,y)(P(y)R(y, y)R(x, y),-,对,-,错,-,错,利用规则,2,对,y,进行代入，则：,(,x)(P(x)Q(x, z)R(x, z),(,x)(P(x)Q(x, z)R(x, y),(,x)(P(x)Q(x, x)R(x, x),-,对,-,错,-,错,2024/10/2,改名规则和代入规则的关系,改名规则和代入规则之间的,共同点,都是,不能改变原有的约束关系,，而,不同点,是：,（,1,）,施行的对象不同,：改名规则是对,约束变元,施行，代入规则是对,自由变元,施行；,（,2,）,施行的范围不同,：改名规则可以只对公式中的一个量词及其辖域内施行，即只,对公式的一个子公式施行,；而代入规则必须对整个公式同一个自由变元的所有自由出现同时施行，即必须,对整个公式施行,；,2024/10/2,改名规则和代入规则的关系（续）,（,3,）,施行后的结果不同,：改名后，公式含义不变，因为,约束变元只改名为另一个个体变元,，约束关系不改变，约束变元不能改名为个体常量；代入后，不仅可用另一个个体变元进行代入，并且也可用,个体常量,去代入，从而使公式由具有普遍意义变为仅对该个体常量有意义，即公式的含义改变了。,2024/10/2,闭式的定义,定义,4.3.5,设,G,是任意一个公式，若,G,中无自由出现的个体变元，则称,G,为封闭的合适公式，简称闭式。,例如 例,4.3.1,中的,(1),，则是一个闭式。,2024/10/2,4.3.3,谓词合式公式的解释,定义,4.3.6,谓词逻辑中公式,G,的每一个,解释,I(Expl-anation),由如下四部分组成：,（,1,）,非空的个体域,集合,D,；,（,2,）,G,中的每个,常量符号,，指定,D,中的某个特定的元素；,（,3,）,G,中的每个,n,元,函数符号,，指定,D,n,到,D,中的某个特定的函数；,（,4,）,G,中的每个,n,元,谓词符号,，指定,D,n,到,0,1,中的某个特定的谓词。,2024/10/2,公式的解释,例,4.3.3,设有公式：,(,x),(P(x)Q(x),(,(,x),P(x),(,x),Q(x),，,在个体域,D=a, b,上，构造两个使公式分别为真和假的解释。,思考一下，谓词逻辑中的一个公式,G,可以像命题逻辑中的公式那样列出真值表来研究它的真值情况么？,2024/10/2,例,4.3.3,解,（,1,）构造解释,I,1,为,P(a) = 0,，,P(b) = 0,，,Q(a) = 1,，,Q(b) = 1,，,则,(P(a)Q(a)(P(b)Q(b),在此解释,I,1,下真值为,1,，,(P(a)P(b)(Q(a)Q(b),在此解释,I,1,下真值为,1,，即,I,1,使得等价式前面的,(,x)(P(x)Q(x),为真，,且使得等价式后面的,(,x)P(x)(,x)Q(x),为真，因此，,这样的解释使得原公式的真值为真。,2024/10/2,例,4.3.3,解（续）,（,2,）,构造解释,I,2,为,P(a)= 0,，,P(b) = 1,，,Q(a)= 0,，,Q(b)= 1,，,则,(P(a)Q(a)(P(b)Q(b),在此解释,I,2,下真值为,1,，,(P(a)P(b)(Q(a)Q(b),在此解释,I,2,下真值为,0,，即,I,2,使得等价式前面的,(,x)(P(x)Q(x),为真，,而使得等价式后面的,(,x)P(x)(,x)Q(x),为假，因此，这样的解释使得,原公式的真值为假,。,2024/10/2,例,4.3.4,.个体域为,D，；,.a,指定为：,；,.f(),指定为,：,f(),指定为：,；,.P(),指定为：1,P(),指定为：0，,Q(,),指定为：0，,Q(,),指定为：1，,Q(,),指定为：1，,Q(,),指定为：1,设有公式,(,x),(,P(f(x)Q(x，f(a)。,在如下给定的解释下，判断该公式的真值。,2024/10/2,例,4.3.4,解,（续）,因当,x,时，有：,f()，P(f(x)P(f()P()1,f(a)f()，,Q(x，f(a)Q(，f()Q(，)1。,所以：,P(f()Q(,f(a)111，,即存在,x,使得,P(f()Q(，f(a)1,，,即：,(,x),(,P(f(x)Q(x，f(a)1。,2024/10/2,4.3.4,谓词合式公式的分类,例,4.3.5,给出公式：,P(a)(,x)P(x),和,(,x)P(x)P(a),，讨论公式的真值情况。,解,（,1,）对于公式,P(a)(,x)P(x),，对任何解释,I,：,（,a,）,当,P(a),取值为真时，,(,x),P(x),也必为真，,此时，,P(a)(,x)P(x),的真值为真；,（,b,）,当,P(a),取值为假时，,(,x)P(x),可为真，也,可为假，此时，,P(a)(,x)P(x),的真值为真；所以，,P(a)(,x)P(x),在任何情况下的真值恒为真,2024/10/2,例,4.3.5,解（续）,（,2,）对于公式,(,x)P(x)P(a),，对任何的解释,I,：,（,a,）,当,(,x),P(x),取值为真时，,P(a),也必为真，,此时，,(,x)P(x)P(a),的真值为真；,（,b,）,当,(,x)P(x),取值为假时，,P(a),可为真，也,可为假，此时，,(,x)P(x)P(a),的真值为真。 所以，,(,x)P(x)P(a),在任何情况下的真值恒为真,2024/10/2,例,4.3.6,判断下列公式的真假。,（,1,）,P(x, y)Q(x,y)P(x, y),；,（,2,）,P(x, y),P(x, y),；,（,3,）,P(x, y),P(x, y),。,解,无论在何种结构中，无论对变元作何种赋值，,公式,(1),，,(2),均取真值,T,，而公式,(3),均取真值,F,。,从而,(1),，,(2),就是关于一切结构与一切赋值下恒取,“,T,”,值的谓词公式，,(3),就是关于一切结构与一切赋值下恒取,“,F,”,值的谓词公式。,2024/10/2,谓词合式公式的分类,定义,4.3.7,（,1,）公式,G,称为,有效公式,，,如果,G,在它,所有的解释,I,下都取值为,“,真,”,。,（,2,）公式,G,称为,矛盾公式,，,如果,G,在它,所有的解释,I,下都取值为,“,假,”,。,（,3,）公式,G,称为,可满足公式,，,如果,至少有一种解释,I,使得,G,取值为,“,真,”,。,2024/10/2,公式之间的关系,从上述定义可知三种特殊公式之间的关系：,（,1,）,有效公式的否定为矛盾公式,；,矛盾公式的否定为有效公式,；,（,2,）,有效公式一定为可满足公式,。,2024/10/2,谓词逻辑的判定问题,若说谓词逻辑是,可判定,的，就要求给出一个,能行的方法,，使得对,任一公式都能判断是否是有效的,。所谓,能行的方法,，乃是,一个机械方法,，可一步一步做下去，并在,有穷步,内实现判断。,2024/10/2,谓词公式的可判定性,（,1,）,谓词逻辑是不可判定的,；,（,2,）只,含有一元谓词变项,的公式是可判定的；,（,3,）如下形式的公式：,(,x,1,)(,x,2,),(,x,n,)P(x,1, x,2, x,n,),，,(,x,1,)(,x,2,),(,x,n,)P(x,1, x,2,x,n,),。,若,P,中无量词和其它自由变元时，也是可判定的；,（,4,）,个体域有穷时,的谓词公式是可判定的。,2024/10/2,4.3.5,谓词合式公式的基本等价关系,定义,4.3.8,公式,G,，,H,称为,等价,的,(Equivalent),，记为,G = H,，如果公式,G,H,是有效公式,。,定义,4.3.9,设,(P,1, P,2, P,n,),是命题演算中的,命题公式,，,P,1, P,2, P,n,是,G,中的命题变元，当用,任意的谓词公式,G,i,(1in),分别代入,P,i,后，得到的新谓词公式,(G,1, G,2, G,n,),称为原公式的,代入实例,。,2024/10/2,4.3.5,谓词合式公式的基本等价关系,定理,4.3.1,永真公式的任意一个代入实例必为有效公式。,命题演算中的,24,个基本的等价公式在谓词演算,中仍成立。,2024/10/2,谓词演算中的有效公式,（,1,）,E,25,：,(,x)G(x) = (,y)G(y),；,E,26,：,(,x)G(x) = (,y)G(y),；,-(,改名规则,),（,2,）,E,27,：,(,x),G(x) =,(,x),G(x),；,E,28,：,(,x),G(x) =,(,x),G(x),；,- (,量词转换律,/,量词否定等值式,),Example,2024/10/2,谓词演算中的有效公式（续）,（,3,）,E,29,：,(,x)(G(x)S) = (,x)G(x)S,；,E,30,：,(,x)(G(x)S) = (,x)G(x)S,；,E,31,：,(,x)(G(x)S) = (,x)G(x)S,；,E,32,：,(,x)(G(x)S) = (,x)G(x)S,；,- (,量词辖域的扩张与收律,),2024/10/2,谓词演算中的有效公式（续,2,）,（,4,）,E,33,：,(,x)(G(x)H(x),=(,x)G(x)(,x)H(x),；,E,34,：,(,x)(G(x)H(x),=(,x)G(x)H(x),；,(,量词分配律,),（,5,）,E,35,：,(,x)G(x)(,x)H(x),=(,x)(,y)(G(x)H(y),；,E,36,：,(,x)G(x)(,x)H(x),=(,x)(,y)(G(x)H(y),；,Example,2024/10/2,例,1,设,P(x),：,x,今天来上课，个体域为计算机学院,2006,级全体同学的集合。则：,1.,(,x),P(x),表示所有同学今天都来上课了；,(,x),P(x),表示不是所有的同学今天来上课了；,(,x),P(x),表示今天有同学没来上课。,所以,(,x),P(x)=(,x),P(x),2.,类似地,(,x),P(x)=,(,x),P(x),return,2024/10/2,例,2,1.,设,G(x),：,x,勤奋学习；,H(x),：,x,喜欢体育活动。 其中：个体域是大学里的学生。,则,(,x),(G(x)H(x),表示：,大学里的所有学生即勤奋学习又喜欢体育活动,”,；,(,x),G(x),(,x),H(x),表示：,“,大学里的所有学生都勤奋学习且大学里所有的学生都喜欢体育活动,”,。,两者意义是相同的,。,即有,(,x),(G(x)H(x)=,(,x),G(x),(,x),H(x),。,2024/10/2,例,2,（续）,2.,设,G(x),：,x,勤奋学习；,H(x),：,x,喜欢体育活动。其中：个体域是大学里的学生。,则,(,x),(G(x)H(x),表示：,“,大学里有些学生勤奋学习或喜欢体育活动,”,；,(,x),G(x)(,x),H(x),表示：,“,大学里有些学生勤奋学习或大学里有些学生喜欢体育活动,”,。,两者意义是相同的。,所以,(,x),(,G(x)H(x),(,x),G(x),(,x),H(x),return,2024/10/2,4.3.6,谓词合式公式难点,3,命题逻辑与谓词逻辑中的公式及其解释的不同,1,掌握并能够灵活运用谓词，个体词和量词；,2,注意量词的作用域。通过紧跟量词后面的是否为括号进行判定；,2024/10/2,4.3.7,谓词合式公式的应用,例,4.3.7,利用谓词之间的等价关系证明下列公式之间的关系：,(,x)P(x)Q(x)=(,y)( P(y)Q(x),证明,(,x)P(x)Q(x),=,(,x)P(x)Q(x),= (,x),P(x)Q(x),= (,y),P(y)Q(x),= (,y)(,P(y)Q(x),= (,y)(P(y)Q(x),2024/10/2,例,4.3.8,判断,(,x)P(x)Q(x)(,x)P(x)(,x)Q(x),是否为一个有效公式。,解,设个体域,D=2, 4, 6, 8,，,P(x),：,x,能被,2,整除；,Q(x),：,x,能被,4,整除。,可知,(,x)P(x),真值为真，,(,x)Q(x),真值为假。,1,）自由变元,x=4,原式真值,=,（,1Q(4),（,10,）,=0,故,(,x)P(x)Q(4)(,x)P(x)(,x)Q(x),的真值为假。所以原式不是有效公式。,2024/10/2,例,4.3.8,（续）,2,）自由变元,x=6,原式真值,=,（,1 Q(6),）,（,10,）,= 1,故,(,x)P(x)Q(6)(,x)P(x)(,x)Q(x),的真值为真。,综上所述，个体域中有些个体使原式的真值为真，有些个体使原式的真值为假，因此，该公式只能是一个可满足公式。,2024/10/2,4.4,公式的标准型,范式,在命题逻辑里，每一公式都有与之等值的范式，范式是一种,统一的表达形式,，当研究一个公式的特点,(,如,永真,、,永假,),时，范式起着重要作用。,对谓词逻辑的公式来说，也有范式，其中,前束范式与原公式是等值的,，而,其它范式与原公式只有较弱的关系,。,2024/10/2,4.4.1,前束范式,定义,4.4.1,称公式,G,是一个,前束范式,，如果,G,中的一切量词都位于该公式的,最前端,(,不含否定词,),且这些量词的,辖域都延伸到公式的末端,。其标准形式如下：,(Q,1,x,1,)(Q,2,x,2,),(Q,n,x,n,)M(x,1, x,2, x,n,),其中,Q,1,为量词,或,(i=1,，,，,n),，,M,称作公式,G,的母式,(,基式,),，,M,中没有量词。,2024/10/2,前束范式的转换方法,定理,4.4.1,谓词逻辑中的任一公式都可化为与之等价的前束范式，但其前束范式并不唯一。,证明,设,G,是任一公式，通过下述步骤可将其转化为与之等价的前束范式：,（,1,）,消去公式中包含的联结词,“,”,、,“,”,；,（,2,）反复运用德,摩根定律，直接,将,“,”,内移到原子谓词公式的前端,；,（,3,）使用谓词的等价公式将,所有量词提到公式的最前端,。,2024/10/2,例,4.4.1,求,(,x)(,y)P(a,x,y),(,x)(,(,y)Q(y,b),R(x),的前束范式。,解,（,1,）,消去联结词,“,”,、,“,”,，得：,(,(,x)(,y)P(a, x, y),(,x)(,(,y)Q(y, b),R(x),（,2,）,内移,，得：,(,x)(,y)P(a, x, y),(,x)(,y)Q(y, b),R(x),= (,x)(,y)P(a, x, y),(,x)(,y),Q(y, b),R(x),2024/10/2,例,4.4.1,解,（续）,（,3,）,量词左移，得：,(,x)(,y)P(a, x, y),(,y),Q(y, b),R(x),= (,x)(,y)P(a, x, y),(,z),Q(z, b),R(x),= (,x)(,y)(,z)(P(a, x, y),Q(z, b),R(x),= (,x)(,y)(,z)S(a, b, x, y, z),即：,(,x)(,y)(,z)S(a, b, x, y, z),为,原式,的前束范式,，,这里,S(a, b, x, y, z),是原公式的母式。,2024/10/2,4.4.2 Skolem,标准型,定义,4.4.2,设公式,G,是一个前束范式，如,消去,G,中所有的存在量词和全称量词,，所得到的公式称为,Skolem,标准型,。,定理,4.4.2,任意一个公式,G,都有相应的,Skolem,标准形存在，但此,Skolem,标准形不一定与原公式等值,。,2024/10/2,例,4.4.2,求公式,(,x)(,y)(,z)(,u)(,v)(,w)P(x, y, z, u, v, w),的,Skolem,标准型。,消去,(,y),消去,(,x),(,y)(,z)(,u)(,v)(,w),P(a, y, z, u, v, w),(,z)(,u)(,v)(,w),P(a, y, z, u, v, w),消去,(,z),(,u)(,v)(,w)P(a, y, z, u, v, w,),(,x)(,y)(,z)(,u)(,v)(,w),P(x,y,z,u,v,w),消去,(,w),(,v)(,w),P(a, y, z, f(y,z), v, w),消去,(,u),(,w),P(a, y, z, f(y,z), v, w),P(a, y, z, f(y,z), v, g(y,z,v),消去,(,v),解,2024/10/2,4.5,谓词逻辑的推理理论,4.5.1,谓词演算的演绎与推理,定义,4.5.1,设,G,1, G,2,G,n,是公式，称,H,是,G,1, G,2,G,n,的逻辑结果,(G,1, G,2,G,n,共同蕴涵,H),，当且仅当,H,是,G,1,G,2,G,n,的,逻辑结果,(logic conclusion),。记为,G,1, G,2,G,n,，此时称,G,1, G,2,G,n,为,有效的,(efficacious),，否则称为无效的（,inefficacious,）。,G,1, G,2,G,n,称为一组,前提,(Premise),，有时用集合,来表示，记, = G,1, G,2,G,n,。,H,称为,结论,(conclusion),。又称,H,是前提集合的逻辑结果。记为,H,。,2024/10/2,定理,4.5.1,定理,4.5.1,公式,H,是前提集合,=G,1, G,2,G,n,的逻辑结果当且仅当,G,1,G,2,G,n,为,有效公式,。,2024/10/2,一 推理规律,（,1,）,I,16,：,(,x)G(x),(,x)G(x),；,（,2,）,I,17,：,(,x)G(x)(,x)H(x),(,x)(G(x)H(x),I,18,：,(,x)(G(x)H(x),(,x)G(x)(,x)H(x),（,3,）,I,19,：,(,x)(G(x)H(x),(,x)G(x)(,x)H(x),I,20,：,(,x)(G(x)H(x),(,x)G(x)(,x)H(x),2024/10/2,推理规律（续）,（,4,）,I,21,：,(,x)(,y)G(x,y),(,y)(,x)G(x,y),；,I,2