(精品)一阶逻辑公式及解释

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2.2,谓词公式与翻译,一、项和原子公式,定义,1,、项的定义,(1),个体变元是项；,(2),个体常元是项；,(3),f,是,n,元运算符号，,t,1,，,t,2,，,t,n,是项，,则,f,(,t,1,，,t,2,，,t,n,),是项,(4),当且仅当有限次地使用以上三条得到的,是项。,定义,2,、原子公式定义,P,是,n,元谓词，,t,1,，,t,2,，,t,n,是项，,称,P,（,t,1,，,t,2,，,t,n,）为原子公式,定义,3,谓词公式，由如下递归定义构成：,(1),原子公式是谓词公式；,(2),若,A,是谓词公式，则,A,也是谓词公式；,(3),若,A,和,B,都是谓词公式，则,(,A,B,), (,A,B,), (,A,B,), (,A,B,),都是谓词公式；,(4),若,A,是谓词公式，,x,是任何个体变元，则,xA,和,xA,都是谓词公式；,(5),当且仅当有限次地应用规则,(1), (2), (3), (4),所得到的公式是谓词公式。,二、一阶公式（谓词公式）,定义,4,对于谓词公式,xP,(,x,),或,xP,(,x,),来说，,x,称为量词,x,或量词,x,的,指导变元,或,作用变元,。,P,(,x,),称为相应量词的,辖域,。,定义,5,在一个谓词公式中，若,x,出现于,x,或,x,的辖域中则称,x,的出现是,约束的,；若,x,的出现不是约束的，则称是,自由的,。,( x),A( x ),或,(, x),A( x ),指导变元,辖域,约束变元,例如,x,y,(,A,(,x,y,),B,(,y,z,),xA,(,x,y,),注：,1,）一个变元在同一个公式中,:,既可以为,约束,出现，又为,自由,出现。,2,）公式,xP,(,x,),、,yP(y),和,zP(z),在相同的个体域中具有相同的意义,可将谓词公式中的约束变元更改名称符号，这一过程称为,约束变元换名,。约束变元换名要遵循一定的规则：,(,1),换名时，更改的对象是量词中的指导变元，以及该量词辖域中所出现的所有该变元，其余不变；,(2),换名时换为 公式中未出现的变元名称。,例如,x,(,P,(,x,),R,(,x,y,),Q,(,x,y,),自由变元的代入规则,:,(1),对公式中出现该自由变元的每一处都,用新的个体变元替换,.,(,2),新变元与原公式中所有变元名称不同。,如：,x,(,A,(,y,),B,(,x,y,),),注：当个体域中元素的个数是有限时，对量词辖域中的约束变元的所有可能的取代是可枚举的，即：,若设个体域为,a,1,a,2, ,a,n,则：,(1) (,x,),A,(,x,),A,(,a,1,),A,(,a,2,),A,(,a,n,),(,2) (,x,),A,(,x,),A,(,a,1,),A,(,a,2,),A,(,a,n,),定义,6,闭式,:,不含自由变元的公式,.,否则称为非,闭式,谓词公式的真值与那些因素有关,?,谓词公式的真值能否像命题逻辑那样总可由真值表给出,?,例,x,y,(P(,x,),Q(,f,(,x,a), y ,z,),),的真值,给出个体域,指定谓词,指定运算具体含义和个体,指定自由变元,三、 谓词公式的解释,为公式中的每个自由变元指定个体域,D,I,中的一个个体,.,定义,7,谓词公式的一个解释,I,(,Interpretation,),解释,I,下的一个赋值,1).,指定一个个体域,D,I,.,2).,为个体常元符号指定,D,I,中的一个个体,.,3).,为,n,元运算符号指定具体含义,.,4).,为,n,元谓词符号指定,具体含义,闭式在一解释下有一确定真值,.,非闭式在一组解释,I,及,I,下一个赋值下,有一确定真值,.,注：要求给一个公式，会给出使之成真 （成假）的解释；反之，给定公式的解释，会求其真值。,(1),x,E(g(,x,a,),x,),(2),x,y,L(,x,y,),(3),y,(E(,x,y,),L(,x, y,),例,1,：对下列公式，,给出使之成真 （成假）的解释,例,2,：给定解释,I,和,I,中的赋值如下,:,D,I,:,自然数集,L,(,x,y,):,xy,E,(,x,y,):,x=y,h,(,x,y,):,xy,自由变元赋值,x=,0,（,x=,1,）,求公式在解释,I,下的真值,.,(1),y,(E(,x,y,),L(,x, y,),(2),y,z,E(,h,(,y,z,), x,),设解释,I,的个体域为,a,1,a,2,a,n,则在解释,I,下,xA(x,),A(,a,1,),A(,a,2,),.A(,a,n,),xA(x,),A(,a,1,),A(,a,2,),.A(,a,n,),当个体域,D,I,中的元素个数有限时,可将变元的所有,可能取值一一列举出来,此时量词可消除,.,求下列闭式在解释,I,下的真值,例,3,：给定解释,I,如下,:,D,=,a,b,P,(,a,b,)=,P,(b,a)=1,P,(a,a)=,P,(,b,b,)=0,1),xP,(,x,x,),2,) ,x,yP,(,y,x,),3),x,yP,(,x,y,),定义,8,A,为一个一阶公式,1,）如果公式,A,在任何解释下均为真,称,A,为,永真式,;,2,）如果,A,在某个解释,I,和,I,的一个赋值下为真,称,A,可满足,;,3,）如果公式在任何解释下均为假,称,A,为,永假式,.,例,4,：判别以下公式的类型,(1),x,P(,x,),x,P(,x,),(2),x,P(,x,),x,P(,x,),(3),x,P(,x,),y,P(,y,),定义,9,：设,A,是包含命题变元,p,1,p,2,.p,n,的命题公式, B,1,B,2,.,B,n,是谓词公式,用,B,1,B,2,.,B,n,分别代替,p,1,p,2,.p,n,在,A,中的所有出现,得到的谓词公式,B,称,A,的代换实例,.,例如,x,P(,x,),x,P(,x,),x,P(,x,),x,P(,x,),x,(P(,x,),Q,(,x,),结论：,命题逻辑永真（假）式的代换实例称为一阶逻辑永真（假）式,p,q,p,永真,x,P(,x,),yQ,(,y,),x,P(,x,),永真,例,5,：判别以下公式的类型,（,1,）,x,P(,x,),(,x,yG,(,x,y,),x,P(,x,),),（,2,）,x,P(,x,),x,P(,x,),（,3,）,x,y,(P(,x,y,),P(,y,x,),),（,4,）,(,x,P(,x,),(,x,Q(,x,),x,P(,x,) ),求下列闭式在解释,I,下的真值,【,练习,1】,给定解释,I,如下,:,D= 2, 3 ,f,(2)=3,f,(3)=2, P(2,)=1,P(3)=0,Q(2, 2,)=1,Q(3, 3,)=1,Q(2, 3,)=0,Q(3, 2,)=0,.,1),x,(,Q(,f,(,x,),x,),P(,x,),),2,),x,(,y,),Q(,x, y,),【,练习,2】,在数学分析中极限定义为：任给小正数,，则存在着一个正数,，使得当,0,|,x,a,|,时有,|,f,(,x,),b,|,。,P,(,x,y,),表示 “,x,大于,y,”,，,Q,(,x,y,),表示 “,x,小于,y,”,则可表示为：,(,)(,)(,x,)(,P,(,0),P,(,0),Q,(|,x,a,|,),P,(|,x,a,|, 0),Q,(|,f,(,x,),b,|,),