
一阶逻辑等值演算与推理51一阶逻辑等值式与置换规则ppt课件.ppt
20页一阶逻辑等值演算与推理一阶逻辑等值演算与推理5.1 一阶逻辑等值式与置换规那么 等值式定义:设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(a2)…P(an)3.量词否认等值式1.xP(x) xP(x)2.xP(x) xP(x)2)在有限个体域上公式的验证:1)字面上了解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(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中某量中某量词的指的指点点变量,及其量,及其辖域中域中该变量的一量的一切切约束出束出现,更改,更改为量量词辖域中域中没有出没有出现过的个体的个体变量符号,最量符号,最好是公式中未出好是公式中未出现过的符号公的符号公式中其他部分不式中其他部分不变设所得公式所得公式为A’,那么,那么A’Ax(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) 其中y{x1,x2,…,xn}等值演算的三条规那么3. 替代替代规规那么那么设设A为为一公式,将一公式,将A中某自在出中某自在出现现的个体的个体变变量的一切出量的一切出现现,更改,更改为为A中没有出中没有出现过现过的个体的个体变变量符号,量符号,公式中其他部分不公式中其他部分不变变。
设设所得公所得公式式为为A’,那么,那么A’Ax(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(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如下:nDI={2,3};nDI中特定元素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)=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) x yL(x,y)4) y xL(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(x)G(x)) x(F(x)G(x))xy(F(x)G(y)H(x,y)) xy(F(x)G(y)H(x,y))xy(F(x)G(y)L(x,y)) xy(F(x)G(y)L(x,y))作业n习题五n2. (2),(3)n5.。
