02-离散谓词逻辑-1.4-1.5

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章 谓词逻辑,第四节 公式解释与类型,第四节 公式解释与类型,一、公式解释,一般情况下，谓词公式中包含：,个体常元、个体变元、函数变元、谓词变元,等。,对各种变元用指定的特殊常元去代替就构成了一个,公式的解释,。,在给定的解释下，可以对多个公式进行解释,公式解释,定义：一个解释,I,由下面4部分组成,非空个体域,D,I,D,I,中,特定元素,：,a,b,D,I,上的,特定的函数,：,f,g,D,I,上的,特定的谓词,：,P,Q,公式解释,在一个具体的解释中，个体常元、函数、谓词的数量一般是有限的，并且其解释一旦确定下来就不再改变，只是个体变元的值在个体域,D,I,内变化，量词符,和,仅作用于,D,I,中的元素,公式解释,例2.5 有给定的解释,I：,D,I,3,6,D,I,中特定的元素：,a=3,D,I,中特定函数：,f(x):f(3)=6,f(6)=3,D,I,中特定谓词：,P(x):P(3)=F,P(6)=TQ(x,y):Q(i,j)=T(i,j=3,6)R(x,y):R(3,3)=R(6,6)=T R(3,6)=R(6,3)=F,公式解释,求下列公式的真值：,(,x),(P(x),Q(x,a),解：在解释,I,下：公式,(P(3),Q(3,3),(P(6),Q(6,3),(F,T),(T,T),F,D,I,=3,6,a,=3,f(x),:f(3)=6,f(6)=3,P(x),:P(3)=F,P(6)=T,Q(x,y),:Q(i,j)=T(i,j=3,6),R(x,y),:R(3,3)=R(6,6)=T R(3,6)=R(6,3)=F,公式解释,(,x),(P(f(x),Q(x,f(x),解：在解释,I,下：公式,(P(f(3),Q(3,f(3),(P(f(6),Q(6,f(6),(P(6),Q(3,6),(P(3),Q(6,3),(T,T),(F,T),T,D,I,=3,6,a,=3,f(x),:f(3)=6,f(6)=3,P(x),:P(3)=F,P(6)=T,Q(x,y),:Q(i,j)=T(i,j=3,6),R(x,y),:R(3,3)=R(6,6)=T R(3,6)=R(6,3)=F,公式解释,(,x)(,y)R(x,y),解：在解释,I,下：公式,(,x)(R(x,3),R(x,6),(R(3,3),R(3,6),(R(6,3),R(6,6),(T,F),(F,T),T,D,I,=3,6,a,=3,f(x),:f(3)=6,f(6)=3,P(x),:P(3)=F,P(6)=T,Q(x,y),:Q(i,j)=T(i,j=3,6),R(x,y),:R(3,3)=R(6,6)=T R(3,6)=R(6,3)=F,公式解释,例2.6 有给定的解释,I：,D,I,整数集合,D,I,中特定的元素：,a=0,D,I,中特定函数：,f(x,y):x+y,g(x,y)=xy,D,I,中特定谓词：,E(x,y):x=y,B(x,y):x y,求下列公式哪个为真，哪个为假？,公式解释,(,x)E(g(x,a),x),解：在解释,I,下：公式,(,x)E(g(x,0),x),(,x)(x0=x),(,x)(0=x),F,a=0,f(x,y):x+y,g(x,y)=xy,E(x,y):x=y,B(x,y):x y,公式解释,(,x)(,y)(E(f(x,a),y),E(f(y,a),x),解：在解释,I,下：公式,(,x)(,y)(x+0=y),(y+0=x),(,x)(,y)(x=y),(y=x),T,a=0,f(x,y):x+y,g(x,y)=xy,E(x,y):x=y,B(x,y):x y,公式解释,(,x)(,y)(,z)E(f(x,y),z),解：在解释,I,下：公式,(,x)(,y)(,z)(x+y=z),T,E(f(x,y),g(x,y),解：公式,(x+y=xy),真值不确定，不是命题,a=0,f(x,y):x+y,g(x,y)=xy,E(x,y):x=y,B(x,y):x y,公式解释,(,x)(,y)B(x,y),解：在解释,I,下：公式,(,x)(,y)(x y),T,(,x)(,y)B(x,y),解：在解释,I,下：公式,(,x)(,y)(x y),F,a=0,f(x,y):x+y,g(x,y)=xy,E(x,y):x=y,B(x,y):x y,公式类型,二、公式类型,定义：,若一个公式在任何解释下都是真的称该公式为逻辑有效式，也叫作,永真式,或,重言式,若一个公式在任何解释下都是假的称该公式为,矛盾式,，也叫作,永假式,若一个公式至少存在一个解释使其为真称该公式为,可满足式,公式类型,前面介绍的,代入规则,，不仅局限于自由变元，对公式中的,命题变元,和,谓词变元,均可实施代入。原则是,不能改变原公式的约束关系,公式类型,谓词变元和命题变元的代入规则,：,在一个公式,A,中，一个,n,元谓词,P,(,x,1,x,2,x,n,),可以用至少含有,n,个自由变元的公式,B,(,y,1,y,2,y,n,y,n+1,y,n+r,),(,r,0),代入，其中,y,1,y,2,y,n,是分别对应于,x,1,x,2,x,n,的任意选定的,n,个自由变元，且对,P,的所有出现处处代入,B,中的其他,r,个自由变元不允许在原公式,A,中约束出现,P,中的个体变元也不允许在,B,中约束出现,公式类型,例2.7 对于公式,A:(,y)(P(x),Q(y),中的谓词变元,P(x),用,B:(,x)(R(x),S(y,z),代入,P(x),中的个体变元,x,在,B,中约束出现，因此需要将,B,中的约束变元,x,改名为,u：,(,u)(R(u),S(y,z),B,中的自由变元,y,在公式,A,中为约束出现，因此要将,A,中的约束变元,y,改名为,v：,(,v)(P(x),Q(v),将,P(x),用,(,u)(R(u),S(y,z),代入，得到：,(,v)(,(,u)(R(u),S(y,z),Q(v),公式类型,若原公式为重言式，则实施代入后仍为重言式,若原公式为非永真式，则实施代入后可能发生改变,例：,公式,(,x)(P(x),P(x),为永真式，将,P(x),用,Q(y),代入后得到,(,x)(Q(y),Q(y),仍为永真式,公式,(,x)(P(x),Q(y),为非永真式，将,P(x),用,Q(y),代入后得到,(,x)(Q(y),Q(y),为永真式,公式类型,例2.8 判断下列公式是否为重言式,(,x)P(x),(,x)P(x),解：设,I,为任意解释，个体域为,D,I,，,若存在,a,D,I,，,使,P(a),为假，则公式的前件,(,x)P(x),为假，则公式为真,否则，对于,x,D,I,，,都有,P(a),为真，即公式的前件,(,x)P(x),为真，且后件,(,x)P(x),为真，则公式为真。,因此该公式是重言式,公式类型,(,x)P(x),(,x)P(x),(,y)Q(y),解：因为,P,P,Q,是重言式，,因此将,(,x)P(x),代入,P，,将,(,y)Q(y),代入,Q，,得到公式,(,x)P(x),(,x)P(x),(,y)Q(y),因此该公式是重言式,公式类型,(,x)(,y)P(x,y),(,x)(,y)P(x,y),解：设解释,I,为：,个体域,D,I,是自然数集合,P(x,y):x=y，,则公式的前件为真，后件为假，因此该公式不是重言式,(,x),(,y),意译成：“无论选定,什么样的,x,的值，都可以确定一,个,y,的值，能使,”,例：个体域是鞋,(,x),(,y),（,x,和,y,能配成双）：,对于客体域中的每一只鞋,x,，存,在一只鞋,y,，,x,和,y,能够配成双。,(,y),(,x),？,第五节 等价式与蕴涵式,第五节 等价式与蕴涵式,一、等价式,定义：设,A,和,B,是任意两个公式，若,A,B,是永真式，则称,A,与,B,是等价的，记做,A,B，,称,A,B,为等价式,Ls,中列出的基本等价式都是,Lp,中的等价式,设,(,A),是含有,A,出现的公式，,(,B),是用公式,B,替换了若干,A,的结果，若,A,B，,则,(,A),(,B),等价式,Lp,的基本等价式,(,x)A,A(,x)A,A,其中,A,是不含自由变元,x,的谓词公式,量词否定等价式,(,x)A(x),(,x),A(x),(,x)A(x),(,x),A(x),等价式,例2.9：,(,x)(,y)(,z)P(x,y,z),(,x),(,y)(,z)P(x,y,z),(,x)(,y),(,z)P(x,y,z),(,x)(,y)(,z),P(x,y,z),等价式,量词辖域的扩大与缩小（,B,是不含自由变元,x,的谓词）,(,x)(A(x),B),(,x)A(x),B,证明：当,B,为假时，两边都为假；,当,B,为真时，两边都等价于(,x)A(x)。,同理可证：,(,x)(A(x),B),(,x)A(x),B,(,x)(A(x),B),(,x)A(x),B,(,x)(A(x),B),(,x)A(x),B,等价式,量词辖域的扩大与缩小（,B,是不含自由变元,x,的谓词）,(,x)(A(x),B),(,x)A(x),B,证明：(,x)(A(x),B),(,x)(,A(x),B),(,x),A(x),B,(,x)A(x),B,(,x)A(x),B,等价式,量词辖域的扩大与缩小（,B,是不含自由变元,x,的谓词）同理可证：,(,x)(A(x),B),(,x)A(x),B,(,x)(B,A(x),B,(,x)A(x),(,x)(B,A(x),B,(,x)A(x),等价式,量词辖域的扩大与缩小（小结,）,(,x)(A(x),B),(,x)A(x),B,(,x)(A(x),B),(,x)A(x),B,(,x)(A(x),B),(,x)A(x),B,(,x)(A(x),B),(,x)A(x),B,(,x)(A(x),B),(,x)A(x),B,(,x)(A(x),B),(,x)A(x),B,(,x)(B,A(x),B,(,x)A(x),(,x)(B,A(x),B,(,x)A(x),等价式,例2.11 求证,(,x,),(,y,)(A(x),B(y),(,x)A(x),(,y,)B(y),证明：左式,(,x),(A(x),(,y)B(y),(,x)A(x),(,y)B(y),(,x)(B,A(x),B,(,x)A,(x),(,x)(A,(x),B),(,x)A,(x),B,等价式,量词的,分配,等价式,(,x)(A(x),B(x),(,x)A(x),(,x)B(x),(,x)(A(x),B(x),(,x)A(x),(,x)B(x),证明：由(,x)(A(x),B(x),(,x)A(x),(,x)B(x),可知：,(,x)(,A(x),B(x),(,x),A(x),(,x),B(x),左边,(,x),(,A(x),B(x),(,x)(A(x),B(x),右边,(,x),A(x),(,x),B(x),(,x)A(x),(,x)B(x),全称量词,(,x),对于析取不服从分配率,设：,A(x),：,x,是偶整数,B(x),：,x,是奇整数,考察两公式是否等价,(,x)(A,(x),B(x),(,x)A,(x),(,x)B,(x),对于每一个,x,，有,A(x,),为真并且,B,（,x,）同时为真；,对于每一个,x,，有,A(x,),为真，并且对于每一个,x,，,B,（,x,）为真,等价式,例2.10 求证：,(,x)(A(x),B(x),(,x)A(x),(,x)B(x),证明：左式,(,x)(,A(x),B(x),(,x),A(x),(,x)B(x),(,x)A(x),(,x)B(x),(,x)A(x),(,x)B(x),思考：是否,(,x)(A(x),B(x),(,x)A(x),(,x)B(x)？,O,等价式,多重量词等价式,(,x),(,y)A(x,y),