离散数学课件第二章(第1讲).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章 谓词逻辑,1,基本概念,2,谓词逻辑的翻译,3,谓词公式的解释,4,谓词演算的等价式与蕴含式,5,前束范式,6,谓词逻辑演的推理理论,1,基本概念,在研究命题逻辑中，原子命题是命题演算中最基本的单位，不再对原子命题进行分解,.,这样会产生二大缺点：（,1,）不能研究命题的结构，成分和内部逻辑的特征；（,2,）也不可能表达二个原子命题所具有的共同特征，甚至在命题逻辑中无法处理一些简单又常见的推理过程。,例：苏格拉底论证是正确的，但不能用命题逻辑的推理规则推导出来。“所有的人总是要死的。,P,“,苏格拉底是人。,Q,“,所以苏格拉底是要死的。”,R,1.,谓词,定义,：用以刻划客体的性质或关系的即是,谓词,。,我们可把原子命题分解为二部分：,主语（名词，代词）和谓语（动词）。,例：张华是学生，李明是学生。则可把它表示成：,H:,表示,“,是学生,”,，,j:,表示,“,张华,”,，,m:,表示,“,李明,”,，则可用下列符号表示上述二个命题：,H(j),，,H(m),。,H,作为,“,谓词,”,用大写英文字母表示，,j,m,称为,“,客体,”,或称,“,个体,”,。客体一般用小写的英文字母表示。,分析：,（,1,）若谓词字母联系着一个客体，则称作,一元谓词,；若谓词字母联系着二个客体，则称作,二元谓词,；若谓词字母联系着,n,个客体，则称作,n,元谓词,。,（,2,）客体的次序必须是有规定的。,例：河南省,北接,河北省。,n L b,写成二元谓词为：,L(n,b),，但不能写成,L(b,n),。,2.,命题函数,客体在谓词表达式中可以是任意的名词。,例：,C,“,是有颜色的。,”,g,：水果；,y,：树叶；,f,：衣服。,则,C(g),C(y),C(f),都是命题。,在上例中，如果用,x,表达任意的客体，则,x,表示客体变元，,C(x),表示,“,x,是有颜色的,”,，则称,C(x),为命题函数。,定义,由一个谓词字母和一些非空的客体变元的集合所组成的表达式，称为简单,命题函数,。,讨论：（,a,）当简单命题函数仅有一个客体变元时，称为一元简单命题函数；,（,b,）若用某一特定客体去取代客体变元之后，则命题函数就变为命题；,（,c,）命题函数中客体变元的取值范围称为个体域（论述域）。,（,d,）个体域（论述域）,:,用特定的集合表示的客体变元的取值范围。,例：,P(x),表示,x,是素数。这是一个命题函数。,其值取决于个体域。,个体域的给定形式有二种：,具体给定。,如：,j,e,t,全总个体域,任意域：将各种个体域综合在一起作为论述范围的域称全总个体域。,命题函数可以,转变为命题，有两种方法：,a),将,x,取定一个值。如：,P(4),，,P(5),b),将谓词量化。如：xP(x),，,xP(x),3.,量词,（,1,）全称量词,“,”,为全称量词符号，读作,“,所有的,”,，,“,任意的,”，,“每个”,。,例：,“,这里所有的都是苹果,”,可写成：,xA(x),或,(,x)A(x),全称量词的几种形式的读法：,xP(x),：,“,对所有的,x,，,x,是,”,；,x,P(x),：,“,对所有,x,，,x,不是,”,；,xP(x),：,“,并不是对所有的,x,，,x,是,”,；,x,P(x),：,“,并不是所有的,x,，,x,不是,”,。,例：将,“,对于所有,x,和所有,y,，如果,x,高于,y,，那么,y,不高于,x,”,写成命题表达形式。解：,G(xy),：,x,高于,y,x,y(G(x,y),G(y,x),（,2,）存在量词,“,”,为存在量词符号，读作,“,存在一个,”,，,“有,些,”,，,“,某些,”,，,“,至少存在一个,”,等等。,存在量词的几种形式的读法：,x A(x),：存在,x,使,x,是,；,x,A(x),：存在,x,使,x,不是,；,x A(x),：不存在,x,使,x,是,；,x,A(x),：不存在,x,使,x,不是,。,为什么将谓词量化，命题函数可以,转变为命题？,设给定个体域：,a,1,a,n,以,a,1,a,n,中的每一个个体代入则：,xP(x),P(a,1,),P(a,n,),xQ(x),Q(a,1,),Qa,n,),例如：,Q(x),表示,:x5,-1,0,3,-3,6,2,15,30,xQ(x),T,F,F,xQ(x),T,T,F,注：个体域不同，则表示同一命题的值不同。,4.,谓词公式,原子谓词公式：不出现命题联结词和量词的谓词命名式称为原子谓词公式，并用,P(x,1,x,n,),来表示。（,P,称为,n,元谓词，,x,1,x,n,称为客体变元）。,定义,（谓词公式的归纳法定义）,原子谓词公式是谓词公式；,若,A,是谓词公式，则,A,也是谓词公式；,若,A,B,都是谓词公式，则,(A,B),(AB),(AB),(AB),都是谓词公式；,若,A,是谓词公式，,x,是任何变元，则,xA,xA也都是谓词公式；,当且仅当有限次地应用,-,所求得的那些公式才是谓词公式。,5.,自由变元与约束变元,(1),辖域：紧跟在量词后面括号内的谓词公式，叫做相应量词的作用域或辖域。,例：,x(P(x),x(P(x),Q(x),P(x),是全称量词的辖域，,P(x),Q(x),是存在量词的辖域。,若量词后括号内为原子谓词公式，则括号可以省去。,例：,x(P(x),xP(x),辖域举例,在,xP(x)Q(x),中,x,的辖域是,P(x),;,在,y,(,C(y),x,(,T(x)u,Q,(,x,u,),),),中,u,的辖域是：,Q,(,x,u,),;,x,的辖域是：,T(x)u,Q,(,x,u,)y,的辖域是：,C(y),x,(,T(x)u,Q,(,x,u,),).,(2),自由变元与约束变元,约束变元,：位于量词的辖域内，并且与量词下标相同的变元。,自由变元,：当且仅当不受量词约束的变元。,例：,xP(x,y),xP(x),Q(y),在谓词公式,xP(x,y),中，,x,是约束变元，,y,是自由变元。,在谓词公式,xP(x),Q(y),中，,x,是约束变元，,y,是自由变元。,注：自由变元可以位于量词的辖域内，也可以不在量词的辖域内。,(3),区别是命题还是命题函数的方法,（,a,）若谓词公式中有自由变元，则该公式为命题函数；,（,b,）若谓词公式中的变元都是约束变元，则该公式为命题。或者说若谓词公式中没有自由变元出现，则该公式是一个命题。,例：,xP(x,y,z),是二元命题函数,y,xP(x,y,z),是一元命题函数,y,xP(x,y),是命题,(4),约束变元的改名规则,我们认为,xP(x,y),和,zP(z,y),是等价的谓词公式，所以任何谓词公式对约束变元都可以改名。,但是，不能用同一个变元去表示谓词公式中的二个不同变元。,例如：,xP(x,y),和,yP(y,y),是不等价的。,约束变元的改名规则：,（,a,）改名时所用的变元符号在量词辖域内未出现的；,（,b,）在改名时要把公式中所有相同的约束变元全部同时改掉。,例：,xP(x)yR(x,y),可改写成xP(x)zR(x,z),但不能改成,:,xP(x)xR(x,x),因为在谓词公式,xR(,x,x),中，前面的,x,原为自由变元，现在变为约束变元了。,(5),自由变元的代入规则,对谓词公式中的自由变元的更改叫做代入。,(a),用以代入的变元与原公式中所有变元的名称不能相同。,(b),对公式中出现该自由变元的每一处都进行代入。,2,谓词公式的翻译,一般来说，将自然语言翻译成谓词公式主要有以下几个步骤：,（,1,）确定个体域，如无特别说明，一般使用全总个体域；,（,2,）根据个体域，分析命题中的个体、个体性质以及各个个体间的关系，确定谓词；,（,3,）根据表示数量的词确定量词；如果使用全总个体域，则要加入特性谓词。,（,4,）利用联结词将整个命题符号化。,例：某个人很聪明。,令,C(x),：,x,很聪明。,下面给出不同的个体域来讨论命题的翻译：,个体域为：,人类,则可翻译为,:,xC(x),；,个体域为任意域（全总个体域），则人必须首先从任意域中分离出来。,设,M(x),表示：,x,是人，,M(x),为特性谓词。则可翻译为,:,x(M(x),C(x),特性谓词：,用来限制个体变元取值范围的谓词。,(2),对于同一个体域，用不同的量词时，特性谓词加入的方法不同。,对于全称量词，其特性谓词以条件联结词的前件的方式加入；,对于存在量词，其特性谓词以合取的形式加入。,注,:,(1),个体域不同，表示同一命题的谓词公式的形式不同。,例：,（,1,）,每个学生都要参加考试。,令,S(x),：,x,是学生（特性谓词）,T(x):x,要参加考试,可翻译为,:,x,(,S(x),T(x),),（,2,）一些人是聪明的。,令,M(x):x,是人（特性谓词）,C(x),：,x,是聪明的。,可翻译为,:,x,(,M(x)C(x),),解：设,I(x):x,是整数；（特性谓词）,R,1,(x),：,x,是正数；,R,2,(x),：,x,是负数。,此句可翻译为：,x(I(x),(,R,1,(x),R,2,(x),),。,例：任何整数或是正的，或是负的。,例：试将苏格拉底论证符号化：,“,所有的人总是要死的。因为苏格拉底是人，所以苏格拉底是要死的。,”,解：设,M(x),：,x,是人；（特性谓词）,D(x),：,x,是要死的；,M(s),：苏格拉底是人；,D(s),：苏格拉底是要死的。,则翻译为：,x(M(x),D(x),，,M(s),D(s),例：,“,没有不犯错的人。,”,解：设,F(x),为,“,x,犯错误,”,，,M(x),为,“,x,是人,”,（特性谓词）。,则可翻译为：,(,x(M(x),F(x),也可以翻译为：,x(M(x),F(x),解：,T(x):x,坐头等舱,J(x):x,坐经济舱,F(x):x,家境富裕,前提：,x(,T(x),J(x),x(,T(x),F(x),x,F(x),x,F(x),例：每个乘客或坐头等舱或坐经济舱；每个乘客当且仅当其家境富裕时坐头等舱；有些乘客家境富裕；并非所有的乘客都家境富裕。因此，有些乘客坐经济舱。（,个体域为全体乘客构成的集合,）,结论：,x,J(x),则可翻译为：,(,x)(S(x)L(x)H(x)G(x)S(x),由于对个体描述性质的刻划深度不同，可翻译成不同形式的谓词公式。,例,：在南京高校学习的学生，未必都是南京籍的学生。,设,S(x),：,x,是南京高校学习的学生。,F(x),：,x,是南京籍的学生。,则翻译为：,x(S(x)F(x),本题也可加深刻划：,S(x),：,x,是学生。,L(x),：,x,在学习。,H(x),：,x,在南京高校。,G(x),：,x,是南京籍的人。,谓词公式中常常含有：个体常元、个体变元（约束变元或自由变元）、函数变元和谓词变元等，对各种变元用指定的特殊常元去代替，就构成了一个公式的解释。,3,谓词公式的解释,一个解释,I,由,4,部分组成：,(1),非空个体域,D,；,(2)D,中一部分特定元素；,(3)D,上一些特定的函数；,(4)D,上一些特定的谓词。,今后将谓词公式中的自由变元看作常元。于是，若对公式,A,给定了一个解释,I,，则,A,在解释,I,下可以计算其真值。,