第七章谓词逻辑.ppt

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,第七章 谓词逻辑,广东工业大学计算机学院,为何引入谓词逻辑,只用命题无法描述所有的推理过程。,苏格拉底三段论,：,所有的人都是要死的，,苏格拉底是人，,所以苏格拉底是要死的。,众所周知，这是,真,命题。,命题逻辑中的求解：,令,P:,所有的人都是要死的，,Q:,苏格拉底是人，,R:,所以苏格拉底是要死的。,在命题逻辑中，将只能用,(P,Q),R,表示上述命题，,无法证明,(P,Q),R,。,所以，这个简单而著名的论断就,无法,用,命题逻辑,予以推证。,2,为何引入谓词逻辑,命题逻辑无法精确描述苏格拉底三段论的根本原因是：,P,Q,R,这样的命题表示太,粗略,，没有把命题之间的内在联系反映出来。,要反映这种内在联系，就要对原子命题作进一步的细化，分析出其中的客体、谓词、量词等，研究它们之间的形式结构及逻辑关系，这就是,谓词逻辑,所研究的内容。,谓词逻辑也叫,一阶逻辑,。,3,谓词逻辑,7.1.1,谓词与命题函数,谓词,7.1.2,量词,1.,全称量词,2.,存在量词,7.1.3,谓词合式,7.1.4,约束元与自由元,改名规则,4,1.,谓词,定义,个体词（客体）,命题所陈述的对象,可以是一个具体的事物,也可以是一个抽象的概念,例如：,刘德华,是香港人。,自然数集,是,整数集,的子集。,定义,谓词,刻画个体词的性质或个体词之间的关系的词,例如：,“,是香港人”是谓词，表示,个体词的性质,：,“,是,的子集”是谓词，描述,个体词之间的关系,5,谓词的函数表示,谓词可用大写英文字母表示,例如：,A,：,是香港人。,B,：,年轻,20,岁。,谓词的函数表示,用不同的个体变元取代谓词表示中要填入的个体词,例如：,A(x),：,x,是香港人。,B(x,y),：,x,比,y,年轻,20,岁。,这样的函数称为,(,简单,),命题函数（原子公式）,。,8,复合命题函数,复合命题函数,由简单命题函数与联结词运算后构成,举例：,A(x):,x,有一条足够长的杠杆,B(x):,x,能够翘起整个地球,则,A(x),B(x),表示,：如果,x,有一条足够长的杠杆，则,x,能够翘起整个地球。,9,n,元谓词元数,定义,n,元谓词,含有,n,个个体变元的谓词。,一元谓词表示个体词的,性质,多元谓词反映个体词之间的,关系,0,元谓词是命题,。,例如：,A(x),：,x,是香港人。,(,一元谓词,),B(x,y),：,x,比,y,年轻,20,岁。,(,二元谓词,),10,命题函数与命题,当,n,1,，,命题函数,(n,元谓词,)P(x,1,x,n,),不是命题，因为真值,无法,确定。,只有当用,n,个个体词代替,x,1,x,2,x,n,之后，才是命题。,举例：,L(x,y),：,表示“,x,小于,y”,的二元谓词，它的真值,不能,确定。,L(2,3),是命题“,2,小于,3”,11,命题函数的定义域和值域,命题函数的定义域（个体域）：,命题函数包含的所有个体变元的取值范围。,例如：,R(x):x,是大学生。,x,的定义域可为：所有人,/,某大学的所有学生,/,某中学的所有学生,注意：,(1),定义域不同，对命题的真值有影响。,(2),若无特殊说明，个体变元的定义域为全总个体域。,命题函数的值域：,对命题函数每种可能的赋值所生成的命题的集合。,例如：,x,的定义域为：张三、李四,则,R(x),的值域为：,张三是大学生，李四是大学生,12,谓词逻辑,7.1.1,谓词与命题函数,谓词,7.1.2,量词,1.,全称量词,2.,存在量词,7.1.3,谓词合式,7.1.4,约束元与自由元,改名规则,13,量词的引入,为了用谓词表示若干个体词或全体个体词具有某种性质或具有某种关系，需要引入量词。,例如：,(1),某些,人会跳舞；,(2),所有,人都会跳舞；,14,量词,定义,量词,表示数量的词,1.,全称量词,:,表示,任意的,所有的,每一个，凡是,x,表示对个体域中所有的,x,2.,存在量词,:,表示,存在,有的,至少有一个，有些,x,表示在个体域中存在,x,在,x A(,x,),和,x A(,x,),中：,紧跟量词的,x,称为量词的,指导变元,或,作用变元,A,称为量词的,辖域,或,作用域,15,量词举例,(1),所有的鱼都生活在水中。,F(x),：,x,是鱼,W(x),：,x,生活在水中,所有的鱼都生活在水中,：,(,x)(F(x),W(x),。,(2),有些人会讲粤语,M(x),：,x,是人,Y(x):,x,会讲粤语,有些人会讲粤语,：,(,x)(M(x),Y(x),。,16,全称量词和存在量词与联结词的搭配,描述某类个体中包含的,所有,个体具有某种性质,与,搭配,例如：设：,S(x),：,x,是学生。,P(x),：,x,通过了考试。,所有学生都通过了考试,(,x)(S(x),P(x),(,x)(S(x),P(x),？,因为个体域必须是学生时，,(,x)(S(x),P(x),才为真,某类个体中,部分,个体具有某种性质,与,搭配,例：,有些学生通过了考试。,(,x)(S(x),P(x),(,x)(S(x),P(x),？,因为只要个体域中有非学生的个体,(,x)(S(x),P(x),为真,17,个体域与命题的符号化,(1),人都爱美,(2),有人用左手写字,分别取不同的个体域集合：,(a),个体域为,人类集合,(b),个体域为,全总个体域,（宇宙中的一切事物）,.,解：,设,M(x),：,x,是人,;F(x),：,x,爱美；,G(x),：,x,用左手写字,(a),个体域为,人类集合,的情况下：,(1),x F(x),或,x,(,M(x),F(x),),(2),x G(x),或,x,(,M(x),G(x),),(b),个体域为,全总个体域,的情况下：,(1),x,(,M(x),F(x),),(2),x,(,M(x),G(x),),说明：（,1,）个体域不同，同一个命题符号化的结果不同。,18,量化的命题函数与命题,命题函数不是命题，但,仅包含被量化的变量的命题函数是命题。,如：,M(x),：,x,是人。,A(x),：,x,是聪明的。,B(x),：,x,要呼吸。,(1)M(x),B(x),(2)(x)(M(x)B(x),(3)M(x)A(x),(4)(x)(M(x)A(x),不是命题,是命题,不是命题,是命题,19,量词的顺序,量词顺序一般不要随便颠倒，颠倒后表示的含义可能会改变。,例：,命题：,对于任一给定的实数,x,，都存在着一个实数,y,，使得,x+y=0,取个体域为实数集合，,H(x,y):x+y=0,，,则命题可符号化为：,x,y,H(x,y),y,x,H(x,y),则表示：,存在着一个实数,y,，对于任一实数,x,，使得,x+y=0,x,y,H(x,y),是真命题，而,y,x,H(x,y),假命题,20,带量词的命题符号化举例（,1,）,请将下列命题符号化：,(1),某些实数是有理数。,(2),没有不犯错误的人。,(3),尽管有人聪明，但未必一切人都聪明。,解：,(1)R(x),：,x,是实数。,Q(x),：,x,是有理数。,(,x)(R(x),Q(x),),(2)M(x),：,x,是人。,F(x),：,x,犯错误。,(,x)(M(x),F(x),),(3)M(x),：,x,是人。,S(x),：,x,聪明。,(,x)(M(x),S(x),),(,x)(M(x),S(x),),21,带量词的命题符号化举例（,2,）,(4),正数都大于负数。,(5),直线,a,与,b,平行当且仅当,a,与,b,不相交。,解：,(4),令,F(x):x,为正数。,G(y):y,为负数。,L(x,y):x,大于,y,。,x,y,(,(,F(x),G(y),),L(x,y),),(5),令,L(x):x,是直线。,P(x,y):x,与,y,平行。,G(x,y):x,与,y,不相交,(,x)(,y)(L(x),L(y),(,P(x,y),G(x,y),22,命题符号化举例（,3,）,只使用全称量词，将下列命题符号化。,某些实数是有理数，但并非所有实数都是有理数。,解：,原语句等价于：并非所有实数都不是有理数，并且并非所有实数都是有理数。,R(x),：,x,是实数。,Q(x),：,x,是有理数。,(,x)(R(x),Q(x),(,x)(R(x),Q(x),23,消去量词,当个体域为,有限集,时，如,D=a,1,a,2,a,n,，对于任意的谓词,A(x),，都有：,x,(A(x)A(a,1,)A(a,2,)A(a,n,),x,(A(x)A(a,1,)A(a,2,)A(a,n,),这两个等价式称为,消去量词,等价式。,24,消除量词举例,设个体域,D=a,b,请消除下列谓词中的量词。,(1)(,x)(A(x)B(x),(2),(,x)(A(x),B(x),(3)(,x),(,y)R(x,y),(4)(,y),(,x)R(x,y),解：,(1),(A(a)B(a),(A(b)B(b),(2),(A(a),B(a),(A(b),B(b),(3),(,x)(,R(x,a,),R(x,b,),(,R(,a,a,),R(,a,b,),(,R(,b,a,),R(,b,b,),(4),(,y)(,R(,a,y),R(,b,y),(,R(,a,a,),R(,b,a,),(,R(,a,b,),R(,b,b,),25,量化的谓词函数的翻译例,设个体域为整数集，令,P(x,y):,x+y=1,Q(x,y):,xy 0,说明下列命题的意义，并指出哪些为真命题。,(1),x,y,P(x,y),(2),x,y,Q(x,y),(3),x,y,(,Q(x,y),P(x,y),),对于,任意整数,x,，,存在,整数,y,，使得,x+y=1,存在整数,x,，对于任意整数,y,，使得,xy 0,对于任意整数,x,，存在,整数,y,，使得,x+y=1,时当且仅当,xy0,26,谓词逻辑,7.1.1,谓词与命题函数,1.,谓词,7.1.2,量词,1.,全称量词,2.,存在量词,7.1.3,谓词合式,7.1.4,约束元与自由元,改名规则,27,谓词演算的原子公式,定义,原子公式,不含任何联结词和量词的简单命题函数称为,原子公式,。,举例：,M(x),：,x,是人,Y(x):,x,会讲粤语,28,谓词合式,定义,谓词合式,/,公式,由简单命题函数、逻辑联结词和量词组合成的,谓词表达式,。,合式公式的,形式化定义,：,(1),原子公式是,合式公式,；,(2),若,A,是,合式公式,，则,(,A),是,合式公式,；,(3),若,A,、,B,是,合式公式,，则,(A,B),、,(A,B),、,(A,B),、,(A,B),是,合式公式,；,(4),若,A,是,合式公式,，则,x A(x),、,x A(x),是,合式公式,;,(5),只有经过有限次地应用规则,(1),(4),构成的符号串才是,合式公式,。,29,谓词合式举例,判断下列符号串是否谓词合式,(1),x,(,A(x),B(x),),(2),x,(,A(x)B(x),),x C(x),(3)(,x),A(x),(,x),B(x),(4)(,x),(,y)P(,x,y,),回答：,(1)(2),是谓词合式。,30,谓词逻辑,7.1.1,谓词与命题函数,1.,谓词,2.,命题函数,7.1.2,量词,1.,全称量词,2.,存在量词,7.1.3,谓词合式,7.1.4,约束元与自由元,改名规则,31,约束元和自由元,在谓词公式,x A(,x,),和,x A(,x,),中：,紧跟量词的,x,称为量词的,指导变元,或,作用变元,A,称为量词的,辖域,或,作用域,辖域中,x,的所有出现称为约束出现，,x,称为,约束变元,除去约束变元以外所其它变元的出现称“自由出现”，这种变元称为,自由变元,举例：,x(P(x)Q(y),R(y),的辖域是,P(x)Q(y),，指导变元是,x,。,整个公式中，,x,是约束出现，受,x,的约束，,y,是自由出现,32,约束元与自由元举例（,1,）,讨论下列合式公式中的约束元及自由元,2),(,x P(x,y)R(y,z),y Q(y),解：,的指导变元是,，辖域是,(,x P(x,y)R(y,z),中，,是,约束出现且受,x,的约束，,是自由出现。,y Q(y),中，,的指导变元是,，辖域是,，,是约束出现。,整个公式中，,约束出现，,既有约束出现又有自由出现，,是自由出现。,x,P(x,y),x,y,、,z,y,Q(y),y,x,y,z,33,变元的约束讨论,从约束变元的概念可以看出，,P,(x,1,x,2,x,n,),是,n,元谓词，它有,n,个相互独立的自由变元。,若对其中,k,个变元进行约束，则,P,成为,n-,k,元谓词。,当,k=n,，即谓词公式中,没有,自由变元出现时，则该公式就成为一个命题。,例如：,x,P(x,y,z),是二元谓词。,y,x,P(x,y,z),是一元谓词。,z,y,x,P(x,y,z),是零元谓词，即命题。,34,谓词逻辑,7.1.1,谓词与命题函数,1.,谓词,2.,命题函数,7.1.2,量词,1.,全称量词,2.,存在量词,7.1.3,谓词合式,7.1.4,约束元与自由元,改名规则,35,约束变元的改名规则,一个变元在公式中可以同时为约束变元与自由变元，因此有可能引起语义上的,混乱,。所以产生改名的必要性。,例如：,(,x P(x,y)R(y,z),y Q(y),y,既是自由变元又是约束变元。,原理：,一个公式的约束变元所使用的名称符号对公式所表示的意义没有影响。,(,x),P(x),与,(,y),P(y),具有相同的意义。,(,x),P(x),与,(,y),P(y),具有相同的意义。,例如：,设,A(x),：,x,不小于,0,，则在实数域中,(,x),P(x),，,(,y),P(y),(,z),P(z),都表示,“,一切实数均不小于,0,”,36,约束变元的改名规则,约束变元的改名规则,:,将量词辖域中出现的某个,约束变元,及相应的,指导变元,，换成一个在辖域中,未曾出现过的,个体变元名。公式的其余部分不变。,举例：,(x P(x,y)R(y,z),y,Q(,y,),用,代替,y Q(y),中出现的,y,变成,(x P(x,y)R(y,z),Q(,),37,自由变元的代入规则,更改自由变元的符号称为自由变元的代入。,自由变元的代入规则,:,对于谓词公式中出现该自由变元的每一处，都使用同一个未在公式中出现过的变元,替代,。,举例：,(x P(x,y,)R(,y,z)y Q(y),用,代替,(x P(x,y,)R(,y,z),中的,y,：,(x P(x,)R(,z)y Q(y),38,课堂练习：,P285:1,、,4,39,作业：,P285-286:3,、,5,、,8,40,