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

1、一阶逻辑等值演算与推理一阶逻辑等值演算与推理51 一阶逻辑等值式与置换规那么 等值式定义：设A，B是一阶逻辑中恣意两个公式，假设AB是永真式，那么称A与B是等值的，记作AB。称AB为等值式。阐明：同命题逻辑一样，人们事先证明了一些重要的等值式，经过它们可推上演更多等值式。1.命题逻辑中等值式的推行命题逻辑中的16组等值式及其代换实例都是一阶逻辑中的等值式。xP(x) xP(x)xP(x)(xP(x)xQ(x) xP(x)xQ(x)x(P(x)Q(x)yR(y) ?2.消去量词等值式设个体域为有限集D=a1,a2,an，那么有xP(x) xP(x) P(a1)P(a2)P(an)P(a1)P(a

2、2)P(an)3.量词否认等值式1. xP(x) xP(x)2. xP(x) xP(x)在有限个体域上公式的验证：字面上了解。4.量词辖域收缩与扩张等值式设A(x)是恣意的含变量x的公式，B中不含x的出现，那么x(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(BA(x) BxA(x)x(A(x)B) xA(x)B4.量词辖域收缩与扩张等值式2. x(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(BA(x) BxA(x)x(A(x)B) xA(x)B5.量词分配等值式设A(x), B(x)是含x的恣意公式，那么x(A(x)B(x) xA(x)xB(x)x(A(x)B(

3、x) xA(x)xB(x)两个重言蕴涵式：xA(x)xB(x) x(A(x)B(x)x(A(x)B(x) xA(x)xB(x)6.多量词等值式多量词相连，同名量词无序，异名量词有序。xyQ(x,y) yxQ(x,y)xyQ(x,y) yxQ(x,y)等值演算的三条规那么 1. 置换规那么置换规那么2.设设X是合式公式是合式公式A的子公式，的子公式，假设假设XY，假设将，假设将A中的中的X用用Y来来置换，得到的公式置换，得到的公式B与公式与公式A等值，等值，即即AB。如，x(P(x)Q(x)yR(y)等值演算的三条规那么2. 换名规那么换名规那么设设A为一公式，将为一公式，将A中某量词的指中某量

4、词的指点变量，及其辖域中该变量的一点变量，及其辖域中该变量的一切约束出现，更改为量词辖域中切约束出现，更改为量词辖域中没有出现过的个体变量符号，最没有出现过的个体变量符号，最好是公式中未出现过的符号。公好是公式中未出现过的符号。公式中其他部分不变。设所得公式式中其他部分不变。设所得公式为为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)等值演算的三条规那么xP(x,x1,x2,xn) yP(y,x1,x2,xn)xP(x,x1,x2,xn) yP(y,x1,x2,xn) 其中yx1

5、,x2,xn等值演算的三条规那么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)等值演算的三条规那么例，使下面公式中每个个体变量只需一种方式的出现。x(P(x,y)yQ(x,y,z)S(x,z) x(P(x,y)yQ(x,y,z)S(x,z)u(P(

6、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)例设个体域D=a,b,c，消去公式中的量词。xy(F(x)G(y)xyF(x,y)x(F(x,y)yG(y)例n 给定解释I如下：n DI=2,3；n DI中特定元素a=2;n 函数f(x)：f(2)=3，f(3)=2；n 谓词n F(x)：F(2)=0，F(3)=1;n G(x,y)：G(2,2)=G(2,3)=G(3,2)=1, G(3,3)=0;n L(x,y)：L(2,2)=L(3,3)=1, L(2,3

7、)=L(3,2)=0.在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) 13) 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例证明以下各等值式。x(C(x)W(x) x(C(x)W(x)x(F