一階邏輯等值演算與推理 5．1 一階邏輯等值式與置換規(guī)則ppt課件

1、一階邏輯等值演算與推理一階邏輯等值演算與推理51 一階邏輯等值式與置換規(guī)那么 等值式定義：設(shè)A，B是一階邏輯中恣意兩個公式，假設(shè)AB是永真式，那么稱A與B是等值的，記作AB。稱AB為等值式。闡明：同命題邏輯一樣，人們事先證明了一些重要的等值式，經(jīng)過它們可推上演更多等值式。1.命題邏輯中等值式的推行命題邏輯中的16組等值式及其代換實(shí)例都是一階邏輯中的等值式。xP(x) xP(x)xP(x)(xP(x)xQ(x) xP(x)xQ(x)x(P(x)Q(x)yR(y) ?2.消去量詞等值式設(shè)個體域?yàn)橛邢藜疍=a1,a2,an，那么有xP(x) xP(x) P(a1)P(a2)P(an)P(a1)P(a

2、2)P(an)3.量詞否認(rèn)等值式1. xP(x) xP(x)2. xP(x) xP(x)在有限個體域上公式的驗(yàn)證：字面上了解。4.量詞轄域收縮與擴(kuò)張等值式設(shè)A(x)是恣意的含變量x的公式，B中不含x的出現(xiàn)，那么x(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(BA(x) BxA(x)x(A(x)B) xA(x)B4.量詞轄域收縮與擴(kuò)張等值式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.量詞分配等值式設(shè)A(x), B(x)是含x的恣意公式，那么x(A(x)B(x) xA(x)xB(x)x(A(x)B(

3、x) xA(x)xB(x)兩個重言蘊(yùn)涵式：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)等值演算的三條規(guī)那么 1. 置換規(guī)那么置換規(guī)那么2.設(shè)設(shè)X是合式公式是合式公式A的子公式，的子公式，假設(shè)假設(shè)XY，假設(shè)將，假設(shè)將A中的中的X用用Y來來置換，得到的公式置換，得到的公式B與公式與公式A等值，等值，即即AB。如，x(P(x)Q(x)yR(y)等值演算的三條規(guī)那么2. 換名規(guī)那么換名規(guī)那么設(shè)設(shè)A為一公式，將為一公式，將A中某量詞的指中某量

4、詞的指點(diǎn)變量，及其轄域中該變量的一點(diǎn)變量，及其轄域中該變量的一切約束出現(xiàn)，更改為量詞轄域中切約束出現(xiàn)，更改為量詞轄域中沒有出現(xiàn)過的個體變量符號，最沒有出現(xiàn)過的個體變量符號，最好是公式中未出現(xiàn)過的符號。公好是公式中未出現(xiàn)過的符號。公式中其他部分不變。設(shè)所得公式式中其他部分不變。設(shè)所得公式為為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)等值演算的三條規(guī)那么xP(x,x1,x2,xn) yP(y,x1,x2,xn)xP(x,x1,x2,xn) yP(y,x1,x2,xn) 其中yx1

5、,x2,xn等值演算的三條規(guī)那么3. 替代規(guī)那么替代規(guī)那么設(shè)設(shè)A為一公式，將為一公式，將A中某自在出現(xiàn)中某自在出現(xiàn)的個體變量的一切出現(xiàn)，更改為的個體變量的一切出現(xiàn)，更改為A中沒有出現(xiàn)過的個體變量符號，中沒有出現(xiàn)過的個體變量符號，公式中其他部分不變。設(shè)所得公公式中其他部分不變。設(shè)所得公式為式為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)等值演算的三條規(guī)那么例，使下面公式中每個個體變量只需一種方式的出現(xiàn)。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)例設(shè)個體域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 函數(shù)f(x)：f(2)=3，f(3)=2；n 謂詞n F(x)：F(2)=0，F(xiàn)(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