一阶逻辑等值演算与推理 5．1 一阶逻辑等值式与置换规则.ppt

一阶逻辑等值演算与推理,51 一阶逻辑等值式与置换规则,2,等值式,定义：设A，B是一阶逻辑中任意两个公式，若AB是永真式，则称A与B是等值的，记作AB。 称AB为等值式。,说明：同命题逻辑一样，人们事先证明了一些重要的等值式，通过它们可推演出更多等值式。,3,1.命题逻辑中等值式的推广,命题逻辑中的16组等值式及其代换实例都是一阶逻辑中的等值式。 xP(x) xP(x)xP(x) (xP(x)xQ(x) xP(x)xQ(x) x(P(x)Q(x)yR(y) ?,4,2.消去量词等值式,设个体域为有限集D=a1,a2,an，则有 xP(x) xP(x) ,P(a1)P(a2)P(an),P(a1)P(a2)P(an),5,3.量词否定等值式,xP(x) xP(x) xP(x) xP(x),在有限个体域上公式的验证：,字面上理解。,6,4.量词辖域收缩与扩张等值式,设A(x)是任意的含变量x的公式，B中不含x的出现，则 x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(BA(x) BxA(x) x(A(x)B) xA(x)B,7,4.量词辖域收缩与扩张等值式,2. x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(BA(x) BxA(x) x(A(x)B) xA(x)B,8,5.量词分配等值式,设A(x), B(x)是含x的任意公式，则 x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) xA(x)xB(x),两个重言蕴涵式： xA(x)xB(x) x(A(x)B(x) x(A(x)B(x) xA(x)xB(x),9,6.多量词等值式,多量词相连，同名量词无序，异名量词有序。 xyQ(x,y) yxQ(x,y) xyQ(x,y) yxQ(x,y),10,等值演算的三条规则,置换规则 设X是合式公式A的子公式，若XY，如果将A中的X用Y来置换，得到的公式B与公式A等值，即AB。,如，x(P(x)Q(x)yR(y),11,等值演算的三条规则,2. 换名规则 设A为一公式，将A中某量词的指导变量，及其辖域中该变量的所有约束出现，更改为量词辖域中没有出现过的个体变量符号，最好是公式中未出现过的符号。公式中其余部分不变。设所得公式为A，则AA。,x(P(x,y) yQ(x,y,z)S(x,z),如:x(P(x)D(x) y(P(y)D(y),u(P(u,y) vQ(u,v,z)S(x,z),12,等值演算的三条规则,xP(x,x1,x2,xn) yP(y,x1,x2,xn) xP(x,x1,x2,xn) yP(y,x1,x2,xn) 其中yx1,x2,xn,13,等值演算的三条规则,3. 代替规则 设A为一公式，将A中某自由出现的个体变量的所有出现，更改为A中没有出现过的个体变量符号，公式中其余部分不变。设所得公式为A，则AA。,x(P(x,y) yQ(x,y,z)S(x,z),如，P(x) P(y),x(P(x,v) yQ(x,y,w)S(u,w),14,等值演算的三条规则,例，使下面公式中每个个体变量只有一种形式的出现。 x(P(x,y)yQ(x,y,z)S(x,z),x(P(x,y)yQ(x,y,z)S(x,z),u(P(u,y)yQ(u,y,z)S(x,z),u(P(u,y)vQ(u,v,z)S(x,z),x(P(x,u)yQ(x,y,z)S(x,z),x(P(x,u)yQ(x,y,z)S(v,z),15,例,设个体域D=a,b,c，消去公式中的量词。 xy(F(x)G(y) xyF(x,y) x(F(x,y)yG(y),16,例,给定解释I如下： DI=2,3； DI中特定元素a=2; 函数f(x)：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)=1, G(3,3)=0; L(x,y)：L(2,2)=L(3,3)=1, L(2,3)=L(3,2)=0.,17,在I下求下列各式的真值。 1) x(F(x)G(x,a) 2) x(F(f(x)G(x,f(x) ,(F(2)G(2,2)(F(3)G(3,2),(01)(11) 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),(11) (01) 1,18,3) xyL(x,y) 4) yxL(x,y) ,x(L(x,2)L(x,3),(L(2,2)L(2,3)(L(3,2)L(3,3),(10) (01) 1,(xL(x,2)(xL(x,3),(L(2,2)L(3,2)(L(2,3)L(3,3),(10)(01) 0,19,例,证明下列各等值式。 x(C(x)W(x) x(C(x)W(x) x(F(x)G(x) x(