復(fù)試2離散結(jié)構(gòu)

12.3一階邏輯等值式等值式基本等值式量詞否定等值式量詞轄域收縮與擴張等值式量詞分配等值式前束范式2等值式定義若AB是永真式,則稱A與B是等值的,記作AB,并稱AB為等值式基本等值式命題邏輯中基本等值式的代換實例如:xF(x)xF(x)xF(x)yG(y)xF(x)yG(y)(xF(x)yG(y))xF(x)yG(y)等3等值式消去量詞等值式設(shè)D={a1,a2,…,an}xA(x)A(a1)A(a2)…A(an)xA(x)A(a1)A(a2)…A(an)4實例例2

設(shè)個體域D={a,b,c},消去下面公式中的量詞:(1)x(F(x)G(x))(F(a)G(a))(F(b)G(b))(F(c)G(c))(2)x(F(x)yG(y))xF(x)yG(y)量詞轄域收縮(F(a)F(b)F(c))(G(a)G(b)G(c))x(F(x,a)F(x,b)F(x,c))(3)xyF(x,y)(F(a,a)F(a,b)F(a,c))(F(b,a)F(b,b)F(b,c))(F(c,a)F(c,b)F(c,c))5基本等值式(續(xù))量詞否定等值式設(shè)A(x)是含x自由出現(xiàn)的公式xA(x)xA(x)xA(x)xA(x)6基本等值式(續(xù))量詞分配等值式

x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)注意：對無分配律，對無分配律7基本等值式(續(xù))量詞轄域收縮與擴張等值式

設(shè)A(x)是含x自由出現(xiàn)的公式，B中不含x的出現(xiàn)關(guān)于全稱量詞的：x(A(x)B)xA(x)Bx(A(x)B)xA(x)B

x(A(x)B)xA(x)Bx(BA(x))BxA(x)關(guān)于存在量詞的:x(A(x)B)xA(x)Bx(A(x)B)xA(x)B

x(A(x)B)xA(x)Bx(BA(x))BxA(x)8置換規(guī)則、換名規(guī)則、代替規(guī)則置換規(guī)則設(shè)Φ(A)是含公式A的公式,Φ(B)是用公式B取代Φ(A)中的所有A得到的公式,則Φ(A)Φ(B)換名規(guī)則將公式A中某量詞的指導(dǎo)變元及其在轄域內(nèi)的所有約束出現(xiàn)改成該量詞轄域內(nèi)未曾出現(xiàn)的某個個體變項,其余部分不變,記所得公式為A,則AA

例:x(F(x,y)

yG(x,y,z))x(F(x,y)

tG(x,t,z))

代替規(guī)則將公式A中某個自由出現(xiàn)的個體變項的所有自由出現(xiàn)改成A中未曾出現(xiàn)的某個個體變項,其余部分不變,記所得公式為A,則AA例:x(F(x,y)

yG(x,y,z))x(F(x,t)

yG(x,y,z))

9實例例1

消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個體變項

(1)xF(x,y,z)

yG(x,y,z)sF(s,y,z)

yG(x,y,z)換名規(guī)則sF(s,y,z)

tG(x,t,z)換名規(guī)則或者xF(x,u,z)

yG(x,y,z)代替規(guī)則xF(x,u,z)

yG(w,y,z)代替規(guī)則(2)x(F(x,y)

yG(x,y,z))x(F(x,y)

tG(x,t,z))換名規(guī)則或者x(F(x,t)

yG(x,y,z))代替規(guī)則10實例解(F(f(2))G(2,f(2)))(F(f(3))G(3,f(3)))例3

給定解釋I:(a)D={2,3},(b)(c):x是奇數(shù),:x=2y=2,:x=y.在I下求下列各式的真值:(1)x(F(f(x))G(x,f(x)))

(2)xyL(x,y)(11)(01)1解yL(2,y)yL(3,y)(L(2,2)L(2,3))(L(3,2)L(3,3))(10)(01)011實例例4

證明下列各等值式:

x(M(x)F(x))x(M(x)F(x))12實例例4

證明下列各等值式:

x(M(x)F(x))x(M(x)F(x))證左邊x(M(x)F(x))量詞否定等值式x(M(x)F(x))置換規(guī)則x(M(x)F(x))置換規(guī)則13實例例5

證明下列各等值式:x(F(x)G(x))x(F(x)G(x))14實例例5

證明下列各等值式:x(F(x)G(x))x(F(x)G(x))證左邊x(F(x)G(x))量詞否定等值式x(F(x)G(x))

置換規(guī)則x(F(x)G(x))置換規(guī)則15實例例6

證明下列各等值式:xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y))16實例例6

證明下列各等值式:xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y))證左邊x(y(F(x)G(y)H(x,y)))量詞否定等值式xy(F(x)G(y)H(x,y)))置換規(guī)則

xy((F(x)G(y)H(x,y)))量詞否定等值式

xy((F(x)G(y))H(x,y)))置換規(guī)則17實例例7

證明下列各等值式:xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y))例8

證明下列各等值式:xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y))18實例例7

證明下列各等值式:xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y))證左邊x(y(F(x)G(y)H(x,y))量詞否定等值式xy(F(x)G(y)H(x,y))置換規(guī)則

xy((F(x)G(y))H(x,y))量詞否定等值式

xy((F(x)G(y))H(x,y)))置換規(guī)則19前束范式定義設(shè)A為一個一階邏輯公式,若A具有如下形式

Q1x1Q2x2…QkxkB則稱A為前束范式,其中Qi

為或,1ik,B為不含量詞的公式.例如xy(F(x)(G(y)H(x,y)))x(F(x)G(x))是前束范式x(F(x)y(G(y)H(x,y)))x(F(x)G(x))不是前束范式20公式的前束范式定理

(前束范式存在定理)一階邏輯中的任何公式都存在與之等值的前束范式求前束范式的過程：(1)否定量詞內(nèi)移：否定量詞等值式(2)合并變量：量詞分配律（可選）(3)消除重名個體變項：換名規(guī)則和替換規(guī)則(4)等值推演：置換規(guī)則(5)量詞前置：量詞轄域收縮與擴張21公式的前束范式例9

求公式的前束范式(1)xF(x)xG(x)解xF(x)xG(x)量詞否定等值式x(F(x)G(x))

量詞分配等值式解2xF(x)yG(y)換名規(guī)則xF(x)yG(y)量詞否定等值式x(F(x)yG(y))量詞轄域擴張xy(F(x)G(y))量詞轄域擴張22實例(續(xù))(2)xF(x)xG(x)解xF(x)xG(x)量詞否定規(guī)則xF(x)yG(y)換名規(guī)則x(F(x)yG(y))

量詞轄域擴張xy(F(x)G(y))量詞轄域擴張23實例