一階邏輯等值與前束范式

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

,bi

,ci

,…,i

1(2)個(gè)體變項(xiàng)：x,y,z,…,xi

,yi

,zi

,…,i

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

,gi

,hi

,…,i

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

,Gi

,Hi

,…,i

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

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

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

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

(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)變項(xiàng)。量詞的轄域A=(F(x,y)→G(x,z))。在A中，x的兩次出現(xiàn)均是約束出現(xiàn)。y和z均為自由出現(xiàn)。(2)前件上量詞的指導(dǎo)變項(xiàng)為x，量詞的轄域A=(F(x)→G(y))，x在A中是約束出現(xiàn)的，y在A中是自由出現(xiàn)的。后件中量詞的指導(dǎo)變項(xiàng)為y，量詞的轄域?yàn)锽=(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)的個(gè)體變項(xiàng)，可以記為An-1(xn)。Δxn…Δx1A(x1,x2,…,xn)沒有自由出現(xiàn)的個(gè)體變項(xiàng)。將x(F(x,y)→G(x,z))簡(jiǎn)記為A(y,z)，表明公式含有自由出現(xiàn)的個(gè)體變項(xiàng)y，z。而yA(y,z)中只含有z為自由出現(xiàn)的公式，zyA(y,z)中已經(jīng)沒有自由出現(xiàn)的個(gè)體變項(xiàng)了，定義2.6設(shè)A是任意的公式，若A中不含有自由出現(xiàn)的個(gè)體變項(xiàng)，則稱A為封閉的公式，簡(jiǎn)稱閉式。要想使含r（r1）個(gè)自由出現(xiàn)個(gè)體變項(xiàng)的公式變成閉式至少要加r個(gè)量詞。如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)讓公式中不會(huì)有既約束出現(xiàn)又自由出現(xiàn)的變項(xiàng)。P43換名規(guī)則:將一個(gè)指導(dǎo)變項(xiàng)及其在轄域中所有約束出現(xiàn)替換成公式中沒有出現(xiàn)的個(gè)體變項(xiàng)符號(hào)。P43例2.6（3）

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

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

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

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

F(x)為x是人，

G(x)為x是黃種人， 則命題為“所有人都是黃種人”，這是假命題。(b)令個(gè)體域D2為實(shí)數(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)))

含有兩個(gè)2元函數(shù)變項(xiàng)，兩個(gè)1元謂詞變項(xiàng)，兩個(gè)2元謂詞變項(xiàng)。 指定個(gè)體域?yàn)槿倐€(gè)體域，

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

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

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

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

給定解釋I如下:(a)個(gè)體域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)個(gè)體域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)個(gè)體域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)個(gè)體域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為一個(gè)公式，若A在任何解釋下均為真，則稱A為永真式(或稱邏輯有效式)。設(shè)A為一個(gè)公式，若A在任何解釋下均為假，則稱A為矛盾式(或永假式)。設(shè)A為一個(gè)公式，若至少存在一個(gè)解釋使A為真，則稱A為可滿足式。永真式一定是可滿足式，但可滿足式不一定是永真式。在一階邏輯中，到目前為止，還沒有找到一種可行的算法，用來判斷任意一個(gè)公式是否是可滿足的，這與命題邏輯的情況是完全不同的。但對(duì)某些特殊的公式還是可以判斷的。說明例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：個(gè)體域?yàn)閷?shí)數(shù)集合R，F(xiàn)(x)：x是整數(shù)，G(x)：x是有理數(shù)，因此公式真值為真。解釋2：個(gè)體域?yàn)閷?shí)數(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)（重言式）的代換實(shí)例，故為永真式。（4）(xF(x)yG(y))yG(y)

為(pq)q（矛盾式）的代換實(shí)例，故為永假式。代換實(shí)例定義2.9設(shè)A0是含有命題變項(xiàng)p1,p2,…,pn的命題公式，A1,A2,…,An是n個(gè)謂詞公式，用Ai(1≤i≤n)處處代替A0中的pi，所得公式A稱為A0的代換實(shí)例。例如，F(xiàn)(x)G(x),xF(x)yG(y)等都是pq的代換實(shí)例，而x(F(x)G(x))不是pq的代換實(shí)例。定理2.2重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式。例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為任意一個(gè)解釋，個(gè)體域?yàn)镈。 若存在x0∈D，使得F(x0)為假，則xF(x)為假，所以A的前件為假，故A為真。 若對(duì)于任意x∈D，F(xiàn)(x)均為真，則xF(x)，xF(x)都為真，從而A為真。 所以在I下A為真。由I的任意性可知，A是永真式。(2)xyF(x,y)→xyF(x,y)

取解釋I：個(gè)體域?yàn)樽匀粩?shù)集合N，F(xiàn)(x,y)為x≤y。 在I下B的前件與后件均為真，所以B為真。這說明B不是矛盾式。（在xyF(x,y)中，x＝0） 再取I‘：個(gè)體域仍然為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ī)則在一階邏輯中，有些命題可以有不同的符號(hào)化形式。例如：沒有不犯錯(cuò)誤的人 令M(x):x是人。F(x):x犯錯(cuò)誤。 則將上述命題的符號(hào)化有以下兩種正確形式：

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

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

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

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

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

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

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

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

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

（蘊(yùn)涵等值式）定理2.1量詞否定等值式設(shè)A(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)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è)個(gè)體域?yàn)橛邢藜疍={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)個(gè)體變項(xiàng)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)個(gè)體變項(xiàng)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)個(gè)體變項(xiàng)x的公式，則（1）x(A(x)∧B(x))xA(x)∧xB(x)（2）x(A(x)∨B(x))xA(x)∨xB(x)（P47）例如，“聯(lián)歡會(huì)上所有人既唱歌又跳舞”和“聯(lián)歡會(huì)上所有人唱歌且所有人跳舞”，這兩個(gè)語句意義相同。故有(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)的公式。只要證明在某個(gè)解釋下兩邊的式子不等值。取解釋I：個(gè)體域?yàn)樽匀粩?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ù)為真命題。 兩邊不等值。證明說明全稱量詞“”對(duì)“∨”無分配律。存在量詞“”對(duì)“∧”無分配律。當(dāng)B(x)換成沒有x出現(xiàn)的B時(shí)，則有

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àng)的所有出現(xiàn)及相應(yīng)的指導(dǎo)變?cè)某稍摿吭~轄域中未曾出現(xiàn)過的某個(gè)體變項(xiàng)符號(hào)，公式的其余部分不變，設(shè)所得公式為A'，則A'A。代替規(guī)則：設(shè)A為一公式，將A中某個(gè)自由出現(xiàn)的個(gè)體變項(xiàng)的所有出現(xiàn)用A中未曾出現(xiàn)過的個(gè)體變項(xiàng)符號(hào)代替，A中其余部分不變，設(shè)所得公式為A'，則A'A。說明一階邏輯中的置換規(guī)則與命題邏輯中的置換規(guī)則形式上完全相同，只是在這里A，B是一階邏輯公式。例將下面公式化成與之等值的公式，使其沒有既是約束出現(xiàn)又是自由出現(xiàn)的個(gè)體變項(xiàng)。

(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è)個(gè)體域?yàn)镈＝{a,b,c}，將下面各公式的量詞消去：

(1)x(F(x)→G(x)) (2)x(F(x)∨yG(y)) (3)xyF(x,y)說明如果不用量詞的轄域縮小，演算過程較長。注意，此時(shí)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）個(gè)體域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）個(gè)體域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）個(gè)體域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）個(gè)體域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）個(gè)體域D＝{2,3}

（b）D中特定元素

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

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

設(shè)A為一個(gè)一階邏輯公式，若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)變?cè)暮竺妗?/p>

┐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)說明解本題時(shí)一定注意，哪些個(gè)體變項(xiàng)是約束出現(xiàn)，哪些是自由出現(xiàn)，特別要注意那些既是約束出現(xiàn)又是自由出現(xiàn)的個(gè)體變項(xiàng)。不能混淆。例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