一階邏輯等值與前束范式

離散數(shù)學(xué)(第6講)章靜E-mail:2.2一階邏輯合式公式及解釋同在命題邏輯中一樣，為在一階邏輯中進(jìn)行演算和推理，必須給出一階邏輯中公式的抽象定義，以及它們的分類及解釋。一階語言是用于一階邏輯的形式語言，而一階邏輯就是建立在一階語言基礎(chǔ)上的邏輯體系，一階語言本身不具備任何意義，但可以根據(jù)需要被解釋成具有某種含義。一階語言的形式是多種多樣的，本書給出的一階語言是便于將自然語言中的命題符號化的一階語言，記為F。一階語言中的字母表定義2.1一階語言F的字母表定義如下:(1)個體常項：a,b,c,…,ai

,bi

,ci

,…,i

1(2)個體變項：x,y,z,…,xi

,yi

,zi

,…,i

1(3)函數(shù)符號：f,g,h,…,fi

,gi

,hi

,…,i

1(4)謂詞符號：F,G,H,…,Fi

,Gi

,Hi

,…,i

1(5)量詞符號:，(6)聯(lián)結(jié)詞符號:┐,∧,∨,→,(7)括號與逗號:(,),，定義2.2項的遞歸定義如下:(1)個體常項和個體變項是項。(2)若f(x1,x2,…,xn)是任意n元函數(shù)，t1,t2,…,tn是項，則f(t1,t2,…,tn)也是項。(3)只有有限次地使用(1)，(2)生成的符號串才是項?？磿鳳42例子定義2.3設(shè)R(x1,x2,…,xn)是的任意n元謂詞，t1,t2,…,tn是項，則稱R(t1,t2,…,tn)為原子公式。定義2.4合式公式定義如下:

合式公式也稱為謂詞公式，簡稱公式。1.原子公式是合式公式；2.若A，B是合式公式，則(┐A)、(┐B)、(A∨B)、(A∧B)、(A→B)、(AB)也是合適公式；3.若A是合式公式，x是個體變量，則(x)A、(x)A也是合式公式；4.只有有限次地應(yīng)用1-3構(gòu)成的符號串才是合式公式。

在定義2.4中出現(xiàn)的字母A，B是代表任意公式的元語言符號。為方便起見，公式(┐A)，(A∧B)，…中的最外層括號可以省去，使其變成┐A，A∧B，…。定義2.5在公式xA和xA中，稱x為指導(dǎo)變項，A為相應(yīng)量詞的轄域。在x和x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)。A中不是約束出現(xiàn)的其他變項均稱為是自由出現(xiàn)的。例2.6

指出下列各公式中的指導(dǎo)變元，各量詞的轄域，自由出現(xiàn)以及約束出現(xiàn)的個體變項。

(1)x(F(x,y)→G(x,z))

(2)x(F(x)→G(y))→y(H(x)∧L(x,y,z))解答(1)x是指導(dǎo)變項。量詞的轄域A=(F(x,y)→G(x,z))。在A中，x的兩次出現(xiàn)均是約束出現(xiàn)。y和z均為自由出現(xiàn)。(2)前件上量詞的指導(dǎo)變項為x，量詞的轄域A=(F(x)→G(y))，x在A中是約束出現(xiàn)的，y在A中是自由出現(xiàn)的。后件中量詞的指導(dǎo)變項為y，量詞的轄域為B=(H(x)∧L(x,y,z))，y在B中是約束出現(xiàn)的，x、z在B中均為自由出現(xiàn)的。再看書P43例2.6注意用A(x1,x2,…,xn)表示含x1,x2,…,xn自由出現(xiàn)的公式。用Δ表示任意的量詞或，則Δx1A(x1,x2,…,xn)是含有x2,x3,…,xn自由出現(xiàn)的公式，可記為A1(x2,x3,…,xn)。類似的，Δx2Δx1A(x1,x2,…,xn)可記為A2(x3,x4,…,xn)Δxn-1Δxn-2…Δx1A(x1,x2,…,xn)中只含有xn是自由出現(xiàn)的個體變項，可以記為An-1(xn)。Δxn…Δx1A(x1,x2,…,xn)沒有自由出現(xiàn)的個體變項。將x(F(x,y)→G(x,z))簡記為A(y,z)，表明公式含有自由出現(xiàn)的個體變項y，z。而yA(y,z)中只含有z為自由出現(xiàn)的公式，zyA(y,z)中已經(jīng)沒有自由出現(xiàn)的個體變項了，定義2.6設(shè)A是任意的公式，若A中不含有自由出現(xiàn)的個體變項，則稱A為封閉的公式，簡稱閉式。要想使含r（r1）個自由出現(xiàn)個體變項的公式變成閉式至少要加r個量詞。如x(F(x)→G(x))是閉式，

x(F(x)→G(x,y))不是閉式換名規(guī)則P43例2.6（2）

xF(x)∧G(x,y)換名為zF(z)∧G(x,y)讓公式中不會有既約束出現(xiàn)又自由出現(xiàn)的變項。P43換名規(guī)則:將一個指導(dǎo)變項及其在轄域中所有約束出現(xiàn)替換成公式中沒有出現(xiàn)的個體變項符號。P43例2.6（3）

x(R(x,y,z)∧yH(x,y,z))換名為x(R(x,y,z)∧tH(x,t,z))例2.7

將下列兩個公式中的變項指定成常項使其成為命題: (1)x(F(x)→G(x))

(2)xy(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))(1)指定個體變項的變化范圍，并且指定謂詞F，G的含義，下面給出兩種指定法:

(a)令個體域D1為全總個體域，

F(x)為x是人，

G(x)為x是黃種人， 則命題為“所有人都是黃種人”，這是假命題。(b)令個體域D2為實數(shù)集合R，

F(x)為x是自然數(shù)，

G(x)為x是整數(shù)， 則命題為“自然數(shù)都是整數(shù)”，這是真命題。(2)xy(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))

含有兩個2元函數(shù)變項，兩個1元謂詞變項，兩個2元謂詞變項。 指定個體域為全總個體域，

F(x)為x是實數(shù)， G(x,y)為x≠y，

H(x,y)為x>y， f(x,y)=x2+y2，

g(x,y)=2xy， 則表達(dá)的命題為“對于任意的x，y，若x與y都是實數(shù)，且x≠y，則x2+y2>2xy”，這是真命題。 如果H(x,y)改為x<y， 則所得命題為假命題。定義2.7一個解釋I由下面4部分組成:(a)非空個體域D；(b)給論及的每一個個體常項符號指定一個D中的元素；

(c)給論及的每一個函數(shù)變項符號指定一個D中的函數(shù)；(d)給論及的每一個謂詞變項符號指定一個D中的謂詞。例2.8

給定解釋I如下:(a)個體域D=N(N為自然數(shù)集合，即N={0,1,2,…})(b)元素a=0(c)函數(shù)f(x,y)=x+y,g(x,y)=x?y。(d)謂詞F(x,y)為x=y。在I下，下列哪些公式為真?哪些為假?哪些的真值還不能確定?(1)F(f(x,y),g(x,y))(2)F(f(x,a),y)→F(g(x,y),z)(3)┐F(g(x,y),g(y,z))(4)xF(g(x,y),z)(5)xF(g(x,a),x)→F(x,y)(6)xF(g(x,a),x)(7)xy(F(f(x,a),y)→F(f(y,a),x))(8)xyzF(f(x,y),z)

(9)xF(f(x,x),g(x,x))

(1)F(f(x,y),g(x,y))

公式被解釋成“x+y=x·y”，這不是命題。

(2)F(f(x,a),y)→F(g(x,y),z)

公式被解釋成“(x+0=y)→(x·y=z)”，這也不是命題。

(3)┐F(g(x,y),g(y,z))

公式被解釋成“x·y≠y·z”，同樣不是命題。

(4)xF(g(x,y),z)

公式被解釋成“x(x·y=z)”，不是命題。例2.8

給定解釋I如下:(a)個體域D=N(N為自然數(shù)集合，即N={0,1,2,…})(b)元素a=0(c)函數(shù)f(x,y)=x+y,g(x,y)=x?y。(d)謂詞F(x,y)為x=y。(5)xF(g(x,a),x)→F(x,y)

公式被解釋成“x(x·0=x)→(x=y)”，由于前件為假，所以被解釋的公式為真。

(6)xF(g(x,a),x)

公式被解釋成“x(x·0=x)”，為假命題。(7)xy(F(f(x,a),y)→F(f(y,a),x))

公式被解釋成“xy((x+0=y)→(y+0=x))”，為真命題。

例2.8

給定解釋I如下:(a)個體域D=N(N為自然數(shù)集合，即N={0,1,2,…})(b)元素a=0(c)函數(shù)f(x,y)=x+y,g(x,y)=x?y。(d)謂詞F(x,y)為x=y。(8)xyzF(f(x,y),z)

公式被解釋成“xyz(x+y=z)”，這也為真命題。(9)xF(f(x,x),g(x,x))

公式被解釋成“x(x+x=x·x)”，為真命題。例2.8

給定解釋I如下:(a)個體域D=N(N為自然數(shù)集合，即N={0,1,2,…})(b)元素a=0(c)函數(shù)f(x,y)=x+y,g(x,y)=x?y。(d)謂詞F(x,y)為x=y。書P44例題2.7，2.8閉式在給定的解釋中都變成了命題。如(6)(8)。不是閉式的公式在某些解釋下也可能變?yōu)槊}。如(5)。結(jié)論定理2.1封閉的公式在任何解釋下都變成命題。P45在給定的解釋和賦值下，任何公式都是命題。一階公式的分類定義2.8永真式、永假式、可滿足式設(shè)A為一個公式，若A在任何解釋下均為真，則稱A為永真式(或稱邏輯有效式)。設(shè)A為一個公式，若A在任何解釋下均為假，則稱A為矛盾式(或永假式)。設(shè)A為一個公式，若至少存在一個解釋使A為真，則稱A為可滿足式。永真式一定是可滿足式，但可滿足式不一定是永真式。在一階邏輯中，到目前為止，還沒有找到一種可行的算法，用來判斷任意一個公式是否是可滿足的，這與命題邏輯的情況是完全不同的。但對某些特殊的公式還是可以判斷的。說明例2.9

判斷下列公式中，哪些是邏輯有效式，哪些是矛盾式？（1）x(F(x)G(x))（2）x(F(x)G(x))（3）xF(x)(xyG(x,y)xF(x))（4）(xF(x)yG(y))yG(y)解:(1)x(F(x)G(x))

解釋1：個體域為實數(shù)集合R，F(xiàn)(x)：x是整數(shù)，G(x)：x是有理數(shù)，因此公式真值為真。解釋2：個體域為實數(shù)集合R，F(xiàn)(x)：x是無理數(shù)，G(x)：x能表示成分?jǐn)?shù)，因此公式真值為假。所以公式為非永真式的可滿足式。（2）x(F(x)G(x))

公式為非永真式的可滿足式。（3）xF(x)(xyG(x,y)xF(x))

為p(qp)（重言式）的代換實例，故為永真式。（4）(xF(x)yG(y))yG(y)

為(pq)q（矛盾式）的代換實例，故為永假式。代換實例定義2.9設(shè)A0是含有命題變項p1,p2,…,pn的命題公式，A1,A2,…,An是n個謂詞公式，用Ai(1≤i≤n)處處代替A0中的pi，所得公式A稱為A0的代換實例。例如，F(xiàn)(x)G(x),xF(x)yG(y)等都是pq的代換實例，而x(F(x)G(x))不是pq的代換實例。定理2.2重言式的代換實例都是永真式，矛盾式的代換實例都是矛盾式。例2.10

判斷下列公式的類型。

(1)xF(x)→xF(x)

(2)xyF(x,y)→xyF(x,y)

(3)x(F(x)∧G(x))→yG(y)解記(1)，(2)，(3)中的公式分別為A,B,C。(1)設(shè)I為任意一個解釋，個體域為D。 若存在x0∈D，使得F(x0)為假，則xF(x)為假，所以A的前件為假，故A為真。 若對于任意x∈D，F(xiàn)(x)均為真，則xF(x)，xF(x)都為真，從而A為真。 所以在I下A為真。由I的任意性可知，A是永真式。(2)xyF(x,y)→xyF(x,y)

取解釋I：個體域為自然數(shù)集合N，F(xiàn)(x,y)為x≤y。 在I下B的前件與后件均為真，所以B為真。這說明B不是矛盾式。（在xyF(x,y)中，x＝0） 再取I‘：個體域仍然為N，F(xiàn)(x,y)為x=y。 在I’下，B的前件真而后件假，所以B為假。這說明B不是永真式。 故B是非永真式的可滿足式。(3)x(F(x)∧G(x))→yG(y)

C也是非永真式的可滿足式。書P45例2.9課后練習(xí)P532.4-2.82.3一階邏輯等值式與置換規(guī)則在一階邏輯中，有些命題可以有不同的符號化形式。例如：沒有不犯錯誤的人 令M(x):x是人。F(x):x犯錯誤。 則將上述命題的符號化有以下兩種正確形式：

(1)┐x(M(x)∧┐F(x)) (2)

x(M(x)→F(x))我們稱(1)和(2)是等值的。說明等值式的定義定義2.10

設(shè)A，B是一階邏輯中任意兩個公式，若AB是永真式，則稱A與B是等值的。

記做AB，稱AB是等值式。例如：判斷公式A與B是否等值，等價于判斷公式

AB是否為永真式。謂詞邏輯中關(guān)于聯(lián)結(jié)詞的等值式與命題邏輯中相關(guān)等值式類似。說明一階邏輯中的一些基本而重要等值式代換實例消去量詞等值式量詞否定等值式量詞轄域收縮與擴(kuò)張等值式量詞分配等值式代換實例由于命題邏輯中的重言式的代換實例都是一階邏輯中的永真式，因而P9的24組等值式模式給出的代換實例都是一階邏輯的等值式的模式。例如：

(1)xF(x)┐┐xF(x) （雙重否定律）

(2)F(x)→G(y)┐F(x)∨G(y) （蘊涵等值式）

(3)x(F(x)→G(y))→zH(z)

┐x(F(x)→G(y))∨zH(z)

（蘊涵等值式）定理2.1量詞否定等值式設(shè)A(x)是任意的含自由出現(xiàn)個體變項x的公式，則（1）┐xA(x)x┐A(x)（2）┐xA(x)x┐A(x)否定內(nèi)移，量詞互換。任意變存在，存在變?nèi)我?。說明“并不是所有的x都有性質(zhì)A”與“存在x沒有性質(zhì)A”是一回事?！辈淮嬖谟行再|(zhì)A的x”與”所有X都沒有性質(zhì)A”是一回事。消去量詞等值式設(shè)個體域為有限集D={a1,a2,…,an},則有（1）xA(x)A(a1)∧A(a2)∧…∧A(an)（2）xA(x)A(a1)∨A(a2)∨…∨A(an)

P47（1）┐xA(x)x┐A(x)

（2）┐xA(x)x┐A(x)┐xA(x)┐(A(a1)∧A(a2)∧…∧A(an))┐

A(a1)∨┐A(a2)∨…∨┐A(an)

x┐A(x)┐xA(x)┐(A(a1)∨A(a2)∨…∨A(an)

)┐

A(a1)∧┐A(a2)∧…∧┐A(an)

x┐A(x)定理2.2量詞轄域收縮與擴(kuò)張等值式設(shè)A(x)是任意的含自由出現(xiàn)個體變項x的公式，B中不含x的出現(xiàn)，則（1）x(A(x)∨B)xA(x)∨B

x(A(x)∧B)xA(x)∧B

x(A(x)→B)xA(x)→B

x(B→A(x))B→xA(x)（2）x(A(x)∨B)xA(x)∨B

x(A(x)∧B)xA(x)∧B

x(A(x)→B)xA(x)→B

x(B→A(x))B→xA(x)（P47）定理2.2量詞轄域收縮與擴(kuò)張等值式設(shè)A(x)是任意的含自由出現(xiàn)個體變項x的公式，B中不含x的出現(xiàn)，則（1）x(A(x)∨B)xA(x)∨B

（P47）x(A(x)∨B)(A(a1)∨B)∧(A(a2)∨B)∧…∧(A(an)∨B)(A(a1)∧A(a2)∧…∧A(an))

∨B

xA(x)∨B證明:(2)3:

x(A(x)→B)xA(x)→Bx(A(x)→B)x(┐A(x)∨B)x┐A(x)∨B┐xA(x)∨BxA(x)→B證明:(1)3:

x(A(x)→B)xA(x)→B

x(A(x)→B)

x(┐A(x)∨B)x┐A(x)∨B┐xA(x)∨BxA(x)→B定理2.3量詞分配等值式設(shè)A(x)，B(x)是任意的含自由出現(xiàn)個體變項x的公式，則（1）x(A(x)∧B(x))xA(x)∧xB(x)（2）x(A(x)∨B(x))xA(x)∨xB(x)（P47）例如，“聯(lián)歡會上所有人既唱歌又跳舞”和“聯(lián)歡會上所有人唱歌且所有人跳舞”，這兩個語句意義相同。故有(1)式。由(1)式推導(dǎo)(2)式 x(A(x)∧B(x))xA(x)∧xB(x) x(┐A(x)∧┐B(x))x┐A(x)∧x┐B(x)

┐x(A(x)∨B(x))┐(xA(x)∨xB(x)) x(A(x)∨B(x))xA(x)∨xB(x)例2.10

證明 （1）x(A(x)∨B(x))<≠>xA(x)∨xB(x)

（2）x(A(x)∧B(x))<≠>

xA(x)∧xB(x)其中A(x)，B(x)為含x自由出現(xiàn)的公式。只要證明在某個解釋下兩邊的式子不等值。取解釋I：個體域為自然數(shù)集合N；(1)取F(x)：x是奇數(shù)，代替A(x)；

取G(x)：x是偶數(shù)，代替B(x)。 則x(F(x)∨G(x))為真命題， 而xF(x)∨xG(x)為假命題。 兩邊不等值。證明(2)x(A(x)∧B(x))<≠>

xA(x)∧xB(x) x(F(x)∧G(x))：有些x既是奇數(shù)又是偶數(shù)為假命題； 而xF(x)∧xG(x)：有些x是奇數(shù)并且有些x是偶數(shù)為真命題。 兩邊不等值。證明說明全稱量詞“”對“∨”無分配律。存在量詞“”對“∧”無分配律。當(dāng)B(x)換成沒有x出現(xiàn)的B時，則有

x(A(x)∨B)xA(x)∨B

x(A(x)∧B)xA(x)∧BP48定理2.4xyA(x,y)yxA(x,y)xyA(x,y)yxA(x,y)2.一階邏輯等值演算的三條原則置換規(guī)則：設(shè)Φ(A)是含公式A的公式，Φ(B)是用公式B取代Φ(A)中所有的A之后的公式，若AB，則Φ(A)Φ(B)。換名規(guī)則：設(shè)A為一公式，將A中某量詞轄域中某約束變項的所有出現(xiàn)及相應(yīng)的指導(dǎo)變元改成該量詞轄域中未曾出現(xiàn)過的某個體變項符號，公式的其余部分不變，設(shè)所得公式為A'，則A'A。代替規(guī)則：設(shè)A為一公式，將A中某個自由出現(xiàn)的個體變項的所有出現(xiàn)用A中未曾出現(xiàn)過的個體變項符號代替，A中其余部分不變，設(shè)所得公式為A'，則A'A。說明一階邏輯中的置換規(guī)則與命題邏輯中的置換規(guī)則形式上完全相同，只是在這里A，B是一階邏輯公式。例將下面公式化成與之等值的公式，使其沒有既是約束出現(xiàn)又是自由出現(xiàn)的個體變項。

(1)xF(x,y,z)→yG(x,y,z) (2)x(F(x,y)→yG(x,y,z))(1)xF(x,y,z)→yG(x,y,z)tF(t,y,z)→yG(x,y,z)(換名規(guī)則)tF(t,y,z)→wG(x,w,z)(換名規(guī)則)或xF(x,y,z)→yG(x,y,z)xF(x,t,z)→yG(x,y,z)(代替規(guī)則)xF(x,t,z)→yG(w,y,z)(代替規(guī)則)解答(2)x(F(x,y)→yG(x,y,z))x(F(x,t)→yG(x,y,z))(代替規(guī)則)或x(F(x,y)→yG(x,y,z))x(F(x,y)→tG(x,t,z))(換名規(guī)則)解答例—消去量詞如P54練習(xí)2.12例設(shè)個體域為D＝{a,b,c}，將下面各公式的量詞消去：

(1)x(F(x)→G(x)) (2)x(F(x)∨yG(y)) (3)xyF(x,y)說明如果不用量詞的轄域縮小，演算過程較長。注意，此時yG(y)是與x無關(guān)的公式B。解答(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))例—消去量詞(3)xyF(x,y)

x(F(x,a)∧F(x,b)∧F(x,c))

(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))

在演算中先消去存在量詞也可以，得到結(jié)果是等值的。xyF(x,y)

yF(a,y)∨yF(b,y)∨yF(c,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))例給定解釋I如下： （a）個體域D＝{2,3}

（b）D中特定元素

（c）D上的特定函數(shù)(x)為：

（d）D的特定謂詞在解釋I下求下列各式的值： （1）x(F(x)∧G(x,a))

（2）x(F(f(x))∧G(x,f(x))

（3）xyL(x,y)

（4）yxL(x,y)（1）x(F(x)∧G(x,a))

(F(2)∧G(2,2))∧(F(3)∧G(3,2)) (0∧1)∧(1∧1) 0例給定解釋I如下： （a）個體域D＝{2,3}

（b）D中特定元素

（c）D上的特定函數(shù)(x)為：

（d）D的特定謂詞（2）x(F(f(x))∧G(x,f(x)) (F(f(2))∧G(2,f(2)))∨(F(f(3))∧G(3,f(3))) (F(3)∧G(2,3))∨(F(2))∧G(3,2)) (1∧1)∨(0∧1) 1例給定解釋I如下： （a）個體域D＝{2,3}

（b）D中特定元素

（c）D上的特定函數(shù)(x)為：

（d）D的特定謂詞（3）xyL(x,y) (L(2,2)∨L(2,3))∧(L(3,2)∨L(3,3)) (1∨0)∧(0∨1) 1例給定解釋I如下： （a）個體域D＝{2,3}

（b）D中特定元素

（c）D上的特定函數(shù)(x)為：

（d）D的特定謂詞（4）yxL(x,y) y(L(2,y)∧L(3,y)) (L(2,2)∧L(3,2))∨(L(2,3)∧L(3,3)) (1∧0)∨(0∧1) 0說明由(3)，(4)的結(jié)果進(jìn)一步可以說明量詞的次序不能隨意顛倒。例給定解釋I如下： （a）個體域D＝{2,3}

（b）D中特定元素

（c）D上的特定函數(shù)(x)為：

（d）D的特定謂詞2.3一階邏輯前束范式定義2.11

設(shè)A為一個一階邏輯公式，若A具有如下形式

Q1x1Q2x2…QkxkB

則稱A為前束范式，其中Qi(1≤i≤k)為或，B為不含量詞的公式。前束范式的例子：

xy(F(x)∧G(y)→H(x，y))

xyz(F(x)∧G(y)∧H(z)→L(x，y，z))

不是前束范式的例子：

x(F(x)→y(G(y)∧H(x，y)))

x(F(x)∧y(G(y)→H(x，y)))前束范式存在定理定理

一階邏輯中的任何公式都存在與之等值的前束范式。說明求前束范式的過程，就是制造量詞轄域可以擴(kuò)大的條件，進(jìn)行量詞轄域擴(kuò)大。任何公式的前束范式都是存在的，但一般說來，并不唯一。利用一階邏輯等值式以及三條變換規(guī)則（置換規(guī)則、換名規(guī)則、代替規(guī)則）就可以求出與公式等值的前束范式，或所謂公式的前束范式。(1)利用量詞轉(zhuǎn)化公式，把否定深入到指導(dǎo)變元的后面。

┐xA(x)x┐A(x)

┐xA(x)x┐A(x)(2)利用x(A(x)∨B)xA(x)∨B和x(A(x)∧B)xA(x)∧B把量詞移到全式的最前面，這樣便得到前束范式。例2.11求公式的前束范式（1）xF(x)∧┐xG(x)

xF(x)∧┐yG(y) (換名規(guī)則)

xF(x)∧y┐G(y) (定理2.1第二式)

x(F(x)∧y┐G(y)) (定理2.1第二式)

xy(F(x)∧┐G(y)) (定理2.2第二式)

（

yx(F(x)∧┐G(y))）或者 xF(x)∧┐xG(x)

xF(x)∧x┐G(x) (定理2.1第二式)

x(F(x)∧┐G(x)) (定理2.3第一式)例2.11求公式的前束范式（2）xF(x)∨┐xG(x)

xF(x)∨x┐G(x) (定理2.1第二式)

xF(x)∨y┐G(y) (換名規(guī)則)

x(F(x)∨y┐G(y)) (定理2.2第一式)

xy(F(x)∨┐G(y)) (定理2.2第一式)說明公式的前束范式是不唯一的。例2.11求前束范式(3)xF(x)∧xG(x)

yF(y)∧xG(x) yx(F(y)∧G(x))(4)xF(x)→xG(x)

yF(y)→xG(x) yx(F(y)→G(x))(5)xF(x)→xG(x)

yF(y)→xG(x) yx(F(y)→G(x))(6)xF(x)→yG(y) xy(F(x)→G(x))例2.11求公式的前束范式(7)xF(x,y)→yG(x,y)

tF(t,y)→wG(x,w)(換名規(guī)則)

tw(F(t,y)→G(x,w))(定理2.2)或者 xF(x,y)→yG(x,y)

xF(x,t)→yG(w,y)(代替規(guī)則)

xy(F(x,t)→G(w,y))(定理2.2)說明解本題時一定注意，哪些個體變項是約束出現(xiàn)，哪些是自由出現(xiàn)，特別要注意那些既是約束出現(xiàn)又是自由出現(xiàn)的個體變項。不能混淆。例2.11求公式的前束范式(8)(x1F(x1,x2)→x2G(x2))→x1H(x1,x2,x3) (x4F(x4,x2)→x5G(x5))→x1H(x1,x2,x3)

x4x5(F(x4,x2)→G(x5))→x1H(x1,x2,x3)

x4x5x1((F(x4,x2)→G(x5))→H