离散数学第三章 谓词演算基础-永真性和可满足性.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第三章 谓词演算基础,3.1,谓词与个体,3.2,函数与量词,3.3,自由变元和约束变元,3.4,永真性和可满足性,3.4.1,真假性,3.4.2,同真假性、永真性和可满足性,3.4.3,范式,3.5,唯一性量词与摹状词,真假性：四个因素,(1),个体域,设,A,(,e,),表示,e,为偶数，考察,xA,(,x,),当个体域,I,为,1,，,2,，,3,时，公式的值为假；,当个体域,I,为,2,，,4,，,6,时，公式的值为真,。,真假性：四个因素,(2),自由变元,设,A,(,e,),表示,e,为偶数，考察,A,(,x,),当,x,取,2,时，其值为,T,；,当,x,取为,3,时，其值为,F,。,真假性：四个因素,(3),谓词变元,个体域,I,=2,，,4,，,6,，,8.,考察,xA,(,x,),当,A,(,e,),表示,e,为偶数时，,xA,(,x,)=,T,；,当,A,(,e,),表示,e,为奇数时，,xA,(,x,)=,F,；,真假性：四个因素,(4),命题变元,个体域,I,=2,，,4,，,6,，,8,，,A,(,e,),表示,e,为偶数,.,考察,xA,(,x,),P,当,P,=,T,时，公式的值为真；,当,P,=,F,时，公式的值为假。,谓词演算公式,设,为任何一个谓词演算公式，,其中自由变元为,x,1,，,x,2,，,，,x,n,；,谓词变元为,X,1,，,X,2,，,，,X,m,；,命题变元为,P,1,，,P,2,，,，,P,k,。,此时,可表示为：,(,x,1,，,，,x,n,；,X,1,，,，,X,m,；,P,1,，,，,P,k,),谓词演算公式的解释,设个体域,I,解释为常个体域,I,0,；,自由变元,x,1,，,，,x,n,解释为：,I,0,中的个体,a,1,，,，,an,；,谓词变元,X,1,，,，,X,m,解释为：,I,0,上的谓词,A,1,，,，,A,m,；,命题变元,P,1,，,，,P,k,解释为：,P,1,0,，,，,P,k,0,，,其中,P,i,0,=,T,或,F,(,i,=1,，,2,，,，,k,),。,成真解释、成假解释,给定公式,一个解释：,(I,0,；,a,1,，,，,a,n,；,A,1,，,，,A,m,；,P,1,0,，,，,P,k,0,),公式,在该解释下的值记为：,(a,，,A,，,P,0,)=,(a,1,，,，,a,n,；,A,1,，,，,A,m,；,P,1,0,，,，,P,k,0,),若,(a,，,A,，,P,0,)=T,，则称,(I,0,；,a,；,A,；,P,0,),为,成真解释,；,若,(a,，,A,，,P,0,)=F,，则称,(I,0,；,a,；,A,；,P,0,),为,成假解释,。,含有量词的谓词演算公式,设个体域,I,中所有实体变元为,a,1,，,a,2,，,，,a,n,，则有：,x,(,x)=,(,a,1,),(,a,2,),(,a,n,),x,(,x)=,(,a,1,),(,a,2,),(,a,n,),含有量词的谓词演算公式的真假性,x,(x),为真,个体域,I,中的每一个个体均使得,取为真,x,(x),为真,个体域,I,中有一个个体使得,取为真,例,在给定解释下，,求,x(F(x),G(x,a),给定解释,I,2,3;,I,中特定元素,a=2,；,函数为,f(2)=3,f(3)=2;,谓词,F(x),为,F(2)=0,F(3)=1,G(x,y),为,G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1,L(x,y),为,L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0,解：原式,=(F(2),G(2,a),(F(3),G(3,a),=(0,0,),(1,0),=0,0,=0,例,在给定解释下，,求,x(F(f(x),G(x,f(x),给定解释,I,2,3;,I,中特定元素,a=2,；,函数为,f(2)=3,f(3)=2;,谓词,F(x),为,F(2)=0,F(3)=1,G(x,y),为,G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1,L(x,y),为,L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0,解：原式,=(,F(f(2),G(2,f(2),(,F(f(3),G(3,f(3),=(,F(3),G(2,3),(,F(2),G(3,2),=(1,0),(0,0),=0,0,=0,例,在给定解释下，求,x,yL(x,y),给定解释,I,2,3;,I,中特定元素,a=2,；,函数为,f(2)=3,f(3)=2;,谓词,F(x),为,F(2)=0,F(3)=1,G(x,y),为,G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1,L(x,y),为,L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0,解：原式,=(,yL(2,y),(,yL(3,y),=(L(2,2),L(2,3),),(L(3,2),L(3,3),),=,(1,0,),(0,1,),=1,1,=1,例,在给定解释下，求,y,x L(x,y),给定解释,I,2,3;,I,中特定元素,a=2,；,函数为,f(2)=3,f(3)=2;,谓词,F(x),为,F(2)=0,F(3)=1,G(x,y),为,G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1,L(x,y),为,L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0,解：原式,=(,x L(x,2),(,x L(x,3),=(L(2,2),L(3,2),(L(2,3),L(3,3),=(1,0,),(0,1),=0,0,=0,量词指导变元次序不能随意,例,(p31),已知,x,y(X(x,，,y),Y(z),Z(x,，,y),试求公式在解释,(I,；,z,；,X(e1,，,e2),，,Y(e),，,Z(e1,，,e2),=(1,，,2,，,3,，,4,；,2,；,e1,e2,；,e,为偶数；,e1,e2),之下的值。,解：将解释代入公式得：,原式,=,x,y,(,x,y,2,为偶数,),x,y,),=,x,y,(,x,y,x,y,),解,(,续,),原式,=,x,y,(,x,y,x,y,),(1),当,x,=1,时,原式的作用域,=,y,(1,y,1,y,),当,y,=1,时，,(1,1),(1,1)=,T,T,=,T,当,y,2,时，,(1,y,),(1,y,)=,F,T,=,T,(2),当,x,=2,时,原式的作用域,=,y,(2,y,2,y,),当,y,=1,时，,(2,1),(2,1)=,T,F,=,F,当,y,=2,时，,(2,2),(2,2)=,T,T,=,T,当,y,3,时，,(2,y),(2,y)=,F,T,=,T,所以，得到：,原式,=(T,T,T,T),(F,T,T,T),(),(),=T,F,*,*,=F,例,(,补充,),考察新公式,x,y,(,x,y,x,y,),在上例中考察了,x=1,2,的情况，现在还需要继续考虑,x=3,4,的情况。,(3),当,x,=3,时,新公式的作用域,=,y,(3,y,3,y,),当,y,=1,2,时，,(3,y,),(,3,y,)=,T,F,=,F,当,y,=3,时，,(3,3,),(,3,3,)=,T,T,=,T,当,y,=4,时，,(3,4,),(,3,4,)=,F,T,=,T,(4),当,x,=4,时,新公式,的作用域,=,y,(4,y,4,y,),当,y,4,时，,，,(4,y,),(4,y,),=,T,F,=,F,当,y,=4,时，,，,(1,4,),(1,4,),=,T,T,=,T,所以，新公式,=(T,T,T,T),(F,T,T,T),(F,F,T,T),(F,F,F,T),=,T,T,T,T=T,例,(,补充,),四个公式的比较,考察新公式,x,y,(,x,y,x,y,),=(T,T,T,T),(F,T,T,T),(F,F,T,T),(F,F,F,T),=,T,T,T,T,=,T,考察新公式,x,y,(,x,y,x,y,),=(T,T,T,T),(F,T,T,T),(F,F,T,T),(F,F,F,T),=,T,F,F,F=,T,原公式,=,x,y,(,x,y,x,y,),=(T,T,T,T),(F,T,T,T),(F,F,T,T),(F,F,F,T),=,T,F,F,F=F,考察新公式,x,y,(,x,y,x,y,),=(T,T,T,T),(F,T,T,T),(F,F,T,T),(F,F,F,T),=,T,T,T,T=,T,第三章 谓词演算基础,3.1,谓词与个体,3.2,函数与量词,3.3,自由变元和约束变元,3.4,永真性和可满足性,3.4.1,真假性,3.4.2,同真假性、永真性和可满足性,3.4.3,范式,3.5,唯一性量词与摹状词,同真假性,定义：设有两公式,和,如果对于个体域,I,上任何解释，公式,和,均取得相同的真假值，,则称,和,在,I,上同真假,。,如果,和,在每一个非空个体域上均同真假，则称,和,同真假,。,关于否定的等价公式,x,(,x)=,x,(,x),x,(,x)=,x,(,x),设个体域,I,中所有实体变元为,a,1,，,a,2,，,，,a,n,，则有：,x,(,x)=,(,(,a,1,),(,a,2,),(,a,n,),=,(,a,1,),(,a,2,),(,a,n,),=,x,(,x),x,(,x)=,(,(,a,1,),(,a,2,),(,a,n,),=,(,a,1,),(,a,2,),(,a,n,),=,x,(,x),量词作用域的收缩与扩张,设公式,中不含有自由的,x,，则,:,x(,(x),)=,x,(x),x(,(x),)=,x,(x),x(,(x),)=,x,(x),x(,(x),)=,x,(x),例 试用等价公式判断两公式是否等价,x(,(x),和,x,(x),解：,x(,(x),=,x,(,(,x),=,x,(,x),=,x,(x),所以两公式等价。,例,(p33),试用等价公式判断两公式是否等价,x,(x),和,x(,(x),),解：,x,(,x),=(,x,(,x),=(,x,(,x),=,x,(,(,x),),=,x,(,(,x),),x,(,(,x),),所以两公式不等价。,量词作用域的收缩与扩张,(,续,),设公式,中不含有自由的,x,，则下面的公式成立,:,x(,(x),)=(,x,(x),),x(,(x)=(,x,(x),x(,(x),)=(,x,(x),),x(,(x)=(,x,(x),考察,xF(,x),I=2,3,I=2,4,F(x):x,为偶数,F,T,F(x):x,为奇数,F,F,F(x):x5,T,T,F(x):x,是质数,T,F,考察,xF(,x),xF(,x),I=2,3,I=2,4,F(x):x,为偶数,F,T=T,T,T=T,F(x):x,为奇数,F,T=T,F,F,=T,F(x):x5,T,T=T,T,T=T,F(x):x,是质数,T,T=T,F,T=T,永真、永假,定义：给定一个谓词演算公式,，其个体域为,I,，对于,I,中的任意一个解释,(1),若,均取为真，,则称公式,在,I,上为,永真的,；,(2),若,均取为假，,则称公式,在,I,上为,永假的,，,也称为公式在,I,上不可满足的。,例,讨论公式类型,xF(,x),xF(,x),证明 设,E,为任意一个解释，其个体域为,I,，,若对于任意的,xI,F(x),均为真,则,xF(,x),与,xF(,x),都为真，,从而该公式也为真。,若存在,x,0,I,使得,F(x0),为假，,则,xF(,x),为假，从而该公式为真。,故在解释,E,下,该公式,为真。,由于,E,的任意性，所以,该公式,是永真式。,可满足、非永真,定义：给定一个谓词演算公式,，其个体域为,I,(1),如果在个体域,I,上存在一个成真解释,则称公式,在,I,上为,可满足,公式；,(2),如果在个体域,I,上存在一个成假解释，,则称公式,在,I,上为,非永真,公式。,例 讨论类型,x,y,F(,x,y),x,y,F(,x,y),证明,取解释,E,如下：,个体域为自然数集,N,，谓词解释,F(x,y),：,x,y,。,在解释,E,下，,该公式,的前、后件均为真，所以,该公式,为真，这说明,该公式,不是矛盾式；,再取解释,E,：个体域仍然为,N,，,谓词,F(x,y),：,x=y,。,在解释,E,下，,该公式,的前件为真，后件为假，故,该公式,为假，这又说明,该公式,不是永真式。,综上所述，,该公式,是非永真式的可满足式。,考察,xF(,x),xF(,x),I=2,3,I=2,4,I=a,b,F(x):x,为偶数,F,T=T,T,T=T,F,F=T,F(x):x,为奇数,F,T=T,F,F,=T,F,F=T,F(x):x5,T,T=T,T,T=T,F,F=T,F(x):x,是质数,T,T=T,F,T=T,F,F=T,定理,1(p33),如果,I,，,J,是个具有相同个数的个体域,(,个体本身可不相同,),，则任意一个公式,，,若在,I,中永真当且仅当其在,J,中永真；,若在,I,中可满足当且仅当其在,J,中可满足,。,证明：要证明该问题，首先要在两个个体域,I,和,J,上建立个体、谓词、解释等元素间的一一对应关系。,定理,1,的证明,(p33),构造一一对应关系如下：,(1),因为,I,和,J,具有相同个数的个体域，所以可在两者之间建立一一对应关系，即在,I,中有一个个体,a,，总能在,J,中找到一个个体与之对应，反之亦然。,(2),现作个体域,I,和,J,上谓词的一一对应关系,设,X(x1,，,x2,，,，,xn),是,I,上的,n,元谓词，令满足下列性质的,J,中,n,元谓词,X(x1,，,x2,，,，,xn),是其对应的谓词,:,X(x1,，,，,xn),为真当且仅当,X(x1,，,，,xn),为真,其中,x1,，,，,xn,在,I,中取值，,x1,，,，,xn,在,J,中取值。,定理,1,的证明,(p33-34),(3),把,I,中的解释与,J,中的解释作一一对应关系：,设有,I,中的一个解释,(,x,1,，,，,x,n,；,X,1,，,，,X,m,；,P,1,，,，,P,k,),=(,a,1,，,，,a,n,；,A,1,，,，,A,m,；,P,1,0,，,，,P,k,0,),记为：,(,x,；,X,；,P,)=(,a,；,A,；,P,0),则令,J,中的下列解释为其对应的解释,(,a,1,，,，,a,n,；,A,1,，,，,A,m,；,P,1,0,，,，,P,k,0,),记为：,(,a,；,A,；,P,0),利用归纳法可证明,(,见下页,),(,a,；,A,；,P,0,)=,(,a,；,A,；,P,0,),定理,1,的证明,(p34),利用归纳法可以证明,(a,；,A,；,P0)=,(a,；,A,；,P0),如果,为命题变元，命题显然成立。,如果,为谓词填式,X(x,1,，,x,2,，,，,x,n,),则有,，故命题成立。,如果,为下列五种情形之一,1,，,1,2,，,1,2,，,1,2,，,1,2,，,则有,，故命题成立。,如果,为,y,1,(x,；,X,；,P,，,y),之形，,则有,，故命题成立。,如果,为,y,1,(x,；,X,；,P,，,y),之形，同理可证。,定理,1,的证明,(p34),利用归纳法可证明,(,见上页,),(,a,；,A,；,P,0,)=,(,a,；,A,；,P,0,)(3.1),设,在,I,中可满足，即在,I,中存在一个解释,(,a,；,A,；,P,0,),使得,取真值，由解释的一一对应关系和式,(3.1),知，在,J,中也存在一个解释,(,a,；,A,；,P,0,),使得,取为真，故,在,J,中可满足。反之亦然。,同理可证，,在,I,中永真当且仅当,在,J,中永真。,K,域,定义：把个体域,1,，,2,，,3,，,，,k,称为,k,域,，,即由,k,个个体组成的个体域。,当,k,=1,时，就称为,1,域，依此类推。,永真性和可满足性,定理,2,：如果一公式在,k,域上,永真,，,则其在,h(hh),域上可满足。,例,(p35),试,讨论公式的永真性和可满足性,x(X(x),(,y(Y(y),Z(z),xY(x),解：,(1),讨论,1,域即个体域,1,的情形,公式,=,X(1),(Y(1),Z(,1),Y(,1)=X(1),T,=T,所以公式在,1,域上永真。,(2),讨论,2,域上的情形,此时个体域,I,=1,，,2,，于公式在,1,域上永真，由定理,3,知公式在,2,域上可满足。,例,(p35),(2),讨论,2,域上的情形,公式在,2,域上可满足。下面考察是否在,2,域上永真。,公式在解释,(,I,；,z,；,X,，,Y,，,Z,)=(1,，,2,；,2,；,X,1,，,X,2,，,X,2),下,原式,=,x,(,X,1(,x,),(,y,(,X,2(,y,),X,2(2),x X,2(,x,),=,x,(,X,1(,x,),(,y,(,X,2(,y,),T,),x X,2(,x,),=,x,(,X,1(,x,),(,yX,2(,y,),x X,2(,x,),=,x,(,X,1(,x,),(,T,x X,2(,x,),=,x,(,X,1(,x,),x X,2(,x,),=,x,(,X,1(,x,),F,),=,x,X,1(,x,),=,F,F=F,故公式在,2,域上可满足但非永真。,e X1 X2 X3 X4,1 T F T F,2 T T F F,图,3.3 2,域上的一元谓词,例,(p35),(3),讨论,k,域,(,k,2),上的情形,(3),讨论,k,域,(,k,2),上的情形,因为公式在,2,域上可满足，,根据定理,3,知，公式在,k,域上可满足；,设公式在,k,域上永真，根据定理,2,知，公式在,2,域上永真，与公式在,2,域上非永真矛盾。,故公式在,k,域上可满足但非永真。,命题,x(A(x),B,(x),(,xA(x),xB(x),在,k,域上,永真。,证明：在,k,域上，此时个体域,I,=1,，,2,，,，,k,原式,=(A(1)B(1)(A(2)B,(2),(A(k)B(k),(A(1)A(2)A(k),(B(1)B,(2),B(k),=T,所以公式在,k,域上永真。,例 试符号化“,鱼我所欲，熊掌亦我所欲”。,解：,F(e),表示“,e,为鱼”,P(e),表示“,e,为熊掌”,W(e,1,e,2,),表示“,e,1,要,e,2,”,，,a,表示“我”，,则原句译为,(,x(F(x)W(a,x),(,x(P(x),W,(a,x),x(F(x),P(x),W(a,x,),?,第三章 谓词演算基础,3.1,谓词与个体,3.2,函数与量词,3.3,自由变元和约束变元,3.4,永真性和可满足性,3.4.1,真假性,3.4.2,同真假性、永真性和可满足性,3.4.3,范式,3.5,唯一性量词与摹状词,一、前束范式,定义：如果一谓词演算公式,中的一切量词均在公式的最前面,(,量词前不含否定词,),且其作用域一直延伸到公式的末端，则称公式,为,前束形公式,。,前束形公式的一般形式为：,Q,1,x,1,Q,2,x,2,Q,n,x,n,M,(,x,1,，,x,2,，,，,x,n,),其中，,Q,i,为,或,，,M,称为公式,的母式且其中不含有量词。,定理,任意一个谓词演算公式均有一前束范式与之等价。,求前束范式的一般步骤,利用等值公式消去“,”和“,”,否定深入,改名,前移量词,例,求前束范式：,xX,(x),xY,(x),解：,(1),利用等值公式消去,“,”得：,(,xX,(,x,),xY,(,x,),(,xX,(,x,),xY,(,x,),(2),否定深入得：,(,x,X,(,x,),xY,(,x,),(,xX,(,x,),x,Y,(,x,),(3),改名：,(,x,X,(,x,),yY,(,y,),(,uX,(,u,),v,Y,(,v,),(4),前移量词得：,x,y,u,v,(,X,(,x,),Y,(,y,),(,X,(,u,),Y,(,v,),x,v,y,u,(,X,(,x,),Y,(,y,),(,X,(,u,),Y,(,v,),?,例,有一种液体可熔化任何金属,解：,L(e),表示“,e,是液体”,M(e),表示“,e,是金属”，,A(e1,e2),表示“,e1,熔化,e2”,，,则原句译为,x(L(x),(,y(M(y),A(x,y),x,y,(L(x),M(y),A(x,y),?,例 所有学生都佩服某些快乐女声,设,S(x),：,x,是学生，,G(x),：,x,是快乐女声，,A(x,y),：,x,佩服,y,。下面哪个答案正确？,(A),xS(x),A(x,y),(B),x(S(x),y(G(y)A(x,y),(C),x,y,(S(x),G(y)A(x,y),(D),x,y(S(x)G(y)A(x,y),(E),x,S(x)yG(y)A(x,y),(F),x(S(x),y(G(y)A(x,y),二、,SKOLEM,标准形,定义：仅含有全称量词的前束范式称为,SKOLEM,标准形。,定理：任一谓词演算公式,，均可以化成相应的,SKOLEM,标准形,且,为不可满足的当且仅当其,SKOLEM,标准形是不可满足的。,SKOLEM,标准形的求解算法,(1),先求谓词演算公式的前束范式；,(2),按如下方法消去存在量词,若存在量词,x,前无全称量词，则引入,SKOLEM,常量,a,，代替公式中受,x,约束的变元，消去存在量词；,若存在量词,x,前有,n,个全称量词，则引入,n,元,SKOLEM,函数,f,，代替公式中受,x,约束的变元，消去存在量词；,(3),从左至右重复上述过程，直至公式中不含有存在量词。,例,(p36),求公式的,SKOLEM,标准形,x,(,X,(,x,),(,yY,(,x,，,y,),xZ,(,x,),解：先把公式化为前束范式,原式,=,x,(,X,(,x,),(,yY,(,x,，,y,),xZ,(,x,),=,x,(,X,(,x,),(,y,Y,(,x,，,y,),xZ,(,x,),=,x,(,X,(,x,),(,y,Y,(,x,，,y,),uZ,(,u,),=,x,y,u,(,X,(,x,),(,Y,(,x,，,y,),Z,(,u,),化为,SKOLEM,标准形,原式,=,y,u,(,X,(,a,),(,Y,(,a,，,y,),Z,(,u,),=,y,(,X,(,a,),(,Y,(,a,，,y,),Z,(,f,(,y,),),例,(p36),求公式的,SKOLEM,标准形,x,(,X,(,x,),(,yY,(,x,，,y,),xZ,(,x,),另解：先把公式化为前束范式,原式,=,x,(,X,(,x,),(,yY,(,x,，,y,),xZ,(,x,),=,x,(,X,(,x,),(,y,Y,(,x,，,y,),xZ,(,x,),=,x,(,X,(,x,),(,y,Y,(,x,，,y,),uZ,(,u,),=,x,u,y,(,X,(,x,),(,Y,(,x,，,y,),Z,(,u,),化为,SKOLEM,标准形,原式,=,u,y,(,X,(,a,),(,Y,(,a,，,y,),Z,(,u,),=,y,(,X,(,a,),(,Y,(,a,，,y,),Z,(,b,),第三章 谓词演算基础,3.1,谓词与个体,3.2,函数与量词,3.3,自由变元和约束变元,3.4,永真性和可满足性,3.4.1,真假性,3.4.2,同真假性、永真性和可满足性,3.4.3,范式,3.5,唯一性量词与摹状词,