全稱量詞消去課件

第5章謂詞邏輯的等值和推理演算謂詞邏輯研究的對(duì)象是重要的邏輯規(guī)律，普遍有效式是最重要的邏輯規(guī)律，而等值式、推理式都是普遍有效的謂詞公式，因此等值和推理演算就成了謂詞邏輯的基本內(nèi)容．這章的討論，主要是以語(yǔ)義的觀點(diǎn)進(jìn)行的非形式的描述，而嚴(yán)格的形式化的討論見(jiàn)第6章所建立的公理系統(tǒng)．第5章謂詞邏輯的等值和推理演算謂詞邏輯研究的對(duì)象是重要的15．1否定型等值式等值：若給定了兩個(gè)謂詞公式A，B，說(shuō)A和B是等值的，如果在公式A，B的任一解釋(注意在謂詞邏輯中，解釋的范圍還包含論域以外的其他要素，見(jiàn)P65)下，A和B都有相同的真值．其他說(shuō)法：A，B等值當(dāng)且僅當(dāng)A?B是普遍有效的公式(注意這里不再說(shuō)重言式了)．記作A＝B或AB。5．1否定型等值式等值：若給定了兩個(gè)謂詞公式A，B，說(shuō)A25．1．1由命題公式移植來(lái)的等值式若將命題公式的等值式，直接以謂詞公式代入命題變項(xiàng)便可得謂詞等值式．由 ﹁﹁p＝p,p→q=﹁p∨q, (p∧q)∨r=(p∨r)∧(q∨r)

可得(以下每?jī)蓚€(gè)為一對(duì)：無(wú)量詞、有量詞) ﹁﹁P(x)＝P(x) ﹁﹁(x)P(x)＝(x)P(x) P(x)→Q(x)＝﹁P(x)∨Q(x) (x)P(x)→(x)Q(x)＝﹁

(x)P(x)∨(x)Q(x) (P(x)∧Q(x))∨R(x)=(P(x)∨R(x))∧(Q(x)∨R(x)) ((x)P(x)∧Q(y))∨(z)R(z) =((x)P(x)∨(z)R(z))∧(Q(y)∨(z)R(z))5．1．1由命題公式移植來(lái)的等值式若將命題公式的等值式，35．1．2否定型等值式

（摩根律的推廣）

﹁(x)P(x)=(x)﹁P(x) ﹁(x)P(x)=(x)﹁P(x)形式上看這對(duì)公式，是說(shuō)否定詞”﹁”可越過(guò)量詞深入到量詞的轄域內(nèi)，但要把所越過(guò)的量詞轉(zhuǎn)換為，轉(zhuǎn)換為.5．1．2否定型等值式

（摩根律的推廣） ﹁(x)P4(1)從語(yǔ)義上說(shuō)明

(2)例：在{l，2}域上分析

﹁(x)P(x)=﹁(P(1)P(2))=﹁P(1)v﹁P(2)=(x)﹁P(x)

﹁(x)P(x)=﹁(P(1)vP(2))=﹁P(1)﹁P(2)=(x)﹁P(x)(1)從語(yǔ)義上說(shuō)明

(2)例：在{l，2}域上分析 ﹁(x5(3)語(yǔ)義上的證明證明方法：依等值式定義，A=B如果在任一解釋I下A真B就真，而且B真A就真．

若證明﹁(x)P(x)=(x)﹁P(x)

1.設(shè)某一解釋I下若﹁(x)P(x)=T 從而(x)P(x)=F，即有一個(gè)xoD,使P(Xo)=F 于是﹁P(xo)=T

故在I下(x)﹁P(x)=T 2.反過(guò)來(lái)，設(shè)某一解釋I下若(x)﹁P(x)=T 即有一個(gè)xoD,使﹁P(Xo)=T

從而P(Xo)=F 于是(x)P(x)=F 即﹁

(x)P(x)=T(3)語(yǔ)義上的證明證明方法：依等值式定義，A=B如果在任一解6(4)舉例例1“并非所有的動(dòng)物都是貓”的表示設(shè) A(x)：x是動(dòng)物 B(x)：x是描原語(yǔ)句可表示成﹁(x)(A(x)B(x))依否定型公式得(4)舉例例1“并非所有的動(dòng)物都是貓”的表示7例2“天下烏鴉—般黑”的表示設(shè) F(x)：x是烏鴉 G(x，y)：x與y是一般黑原語(yǔ)句可表示成

(x)(y)(F(x)^F(y)→G(x,y))不難知道與之等值的公式是

﹁(x)(y)(F(x)^F(y)^﹁G(x,y))即不存在x,y是烏鴉但不一般黑．這兩句話含義是相同的．經(jīng)計(jì)算有例2“天下烏鴉—般黑”的表示8全稱量詞消去課件9

5．2量詞分配等值式

一、含單獨(dú)的命題變項(xiàng)，與x無(wú)關(guān)

5．2．1量詞對(duì)、的分配律這是一組量詞對(duì)、的分配律，其中q是命題變項(xiàng)，與個(gè)體變?cè)獂無(wú)關(guān)，這是很重要的條件．我們僅對(duì)第一個(gè)等式給出證明，其余三個(gè)同樣可證．5．2量詞分配等值式

一、含單獨(dú)的命題變項(xiàng)，與x無(wú)關(guān)

10設(shè)在一解釋I下，(x)(P(x)q)=T，從而對(duì)任一xD，有P(x)q=T

若q＝T，則(x)P(x)q=T

若q＝F，從而對(duì)任一xD，有P(x)=T，即有(x)P(x)=T，故仍有，(x)P(x)q=T反過(guò)來(lái)，設(shè)在一解釋I下，(x)P(x)q=T，若q=T，則(x)(P(x)q)=T

若q=F，必有(x)P(x)=T，從而對(duì)任一xD有P(x)=T，于是對(duì)任一xD有P(x)q=T故(x)(P(x)q)=T．設(shè)在一解釋I下，(x)(P(x)q)=T，從而對(duì)任一x115．2．2量詞對(duì)→的分配律這是一組量詞對(duì)→的分配律，其中p，q是命題變項(xiàng)，與個(gè)體變?cè)獂無(wú)關(guān)，這是很重要的條件．5.2節(jié)介紹的等值公式中僅有這里的第一、二個(gè)公式有量詞的改變！！5．2．2量詞對(duì)→的分配律12先證明其中的第一個(gè)等式． 依5．2．1的等值式 依5．l．2的等值式先證明其中的第一個(gè)等式．13再證明其中的第三個(gè)等式

依5．2．l的等值式其余兩個(gè)等值式同樣可證．再證明其中的第三個(gè)等式14二、轄域中無(wú)單獨(dú)的命題變項(xiàng)

5．2．3量詞對(duì)

、量詞對(duì)V的分配律這是當(dāng)P(x)，Q(x)都含有個(gè)體變?cè)獂時(shí)，量詞對(duì)^，量詞對(duì)V所遵從的分配律．然而對(duì)V，對(duì)^的分配律一般并不成立．證明中使用了5.2.1中的解釋方法。(x)P(x)v(x)Q(x)=>(x)(P(x)vQ(x))(x)(P(x)^Q(x))=>(x)P(x)^(x)Q(x)二、轄域中無(wú)單獨(dú)的命題變項(xiàng)

5．2．3量詞對(duì)、量詞15一些例子一些例子165．2．4變?cè)酌蟮姆峙渎?/p>

(在求前束范式時(shí)有很大作用)這兩個(gè)等值式，說(shuō)明了通過(guò)變?cè)囊酌?，仍可?shí)現(xiàn)對(duì)V，對(duì)^的分配律．證明是容易的．首先有變?cè)酌戎凳?(x)P(x)=(y)P(y) (x)P(x)=(y)P(y) 于是(x)P(x)v(x)Q(x)=(x)P(x)v(y)Q(y)5．2．4變?cè)酌蟮姆峙渎?/p>

(在求前束范式時(shí)有很大作用17對(duì)x而言(y)Q(y)相當(dāng)于命題變項(xiàng)，與x無(wú)關(guān)，可推得 (x)P(x)v(y)Q(y)=(x)(P(x)v(y)Q(y))對(duì)y而言，P(x)相當(dāng)于命題變項(xiàng)與y無(wú)關(guān)，又可推得 (x)(P(x)v(y)Q(y))=(x)(y)(P(x)vQ(y)) 同理(x)(y)(P(x)^Q(y))=(x)P(x)^(x)Q(x) 然而(x)(y)(P(x)vQ(y))與(x)(P(x)vQ(x))

是不等值的(x)(y)(P(x)^Q(y))與(x)(P(x)^Q(x)) 也是不等值的對(duì)x而言(y)Q(y)相當(dāng)于命題變項(xiàng)，與x無(wú)關(guān)，可推得185．3范式在命題邏輯里．每一公式都有與之等值的范式，范式是一種統(tǒng)一的表達(dá)形式．對(duì)謂詞邏輯的公式來(lái)說(shuō)也有范式，其中前束范式與原公式是等值的，而其他范式與原公式只有較弱的關(guān)系。5．3范式在命題邏輯里．每一公式都有與之等值的范195．3．1前束范式定義5．3．1

說(shuō)公式A是一個(gè)前束范式，如果A中的一切量詞都位于該公式的最左邊(不含否定詞)且這些量詞的轄域都延伸到公式的末端，前束范式A的一般形式為 (Q1x1)…(Qnxn)M(xl，…，xn)

其中Qi為量詞或(i＝l，…，n)，M稱作公式A的母式(基式)，M中不再有量詞．定理5．3．1謂詞邏輯的任一公式都可化為與之等值的前束范式．但其前束范式并不唯一．5．3．1前束范式定義5．3．1說(shuō)公式A是一個(gè)前束范20全稱量詞消去課件21經(jīng)過(guò)這幾步，便可求得任一公式的前束范式．由于每一步變換都保持著等值性，所以，所得到的前束形與原公式是等值的．這里的S(a，b，x，y，z)便是原公式的母式．其中a,b為自由個(gè)體變項(xiàng)。由于前束中量詞的次序排列，以及對(duì)母式都沒(méi)有明確的限制，自然前束范式不是唯一的，如例1的前束范式也可以是 (x)(z)(y)(S(a,b,x,y,z)P) 其中P可以是任一不含量詞的普遍有效的公式。經(jīng)過(guò)這幾步，便可求得任一公式的前束范式．由于每一步變換都保持225．3．2Skolem標(biāo)準(zhǔn)形前束范式對(duì)前束量詞沒(méi)有次序要求，也沒(méi)有其他要求．如果對(duì)前束范式進(jìn)而要求所有存在量詞都在全稱量詞之左得到存在前束范式(略)，或是只保留全稱量詞而消去存在量詞得到Skolem標(biāo)準(zhǔn)形。不難想像，仍保持與原公式的等值性就不可能了，只能保持在某種意義下的等值關(guān)系．5．3．2Skolem標(biāo)準(zhǔn)形前束范式對(duì)前束量詞沒(méi)有次序要23(1)前束范式(略)一個(gè)公式的前束范式為(x1)…(xi)(xi+1)…(xn)M(x1，…，xn) 即存在量詞都在全稱量詞的左邊，且可保持至少有一個(gè)存在量詞(i≥1)，其中M(x1，…，xn)中不再含有量詞也無(wú)自由個(gè)體變項(xiàng)定理5.3.2

謂詞邏輯的任一公式A，都可化成相應(yīng)的前束范式，并且A是普遍有效的當(dāng)且僅當(dāng)其前束范式是普遍有效的。這定理是說(shuō)對(duì)普遍有效的公式，它與其前束范式是等值的，而一般的公式與其前束范式并不是等值的．自然僅當(dāng)A是普遍有效的，方使用前束范式．(1)前束范式(略)一個(gè)公式的前束范式為(24例2求(x)(y)(u)P(x，y，u)的前束范式(P中無(wú)量詞)．將一公式化成前束形，首先要求出前束形，再做前束，這個(gè)例子已是前束形了，便可直接求前束形．例2求(x)(y)(u)P(x，y，u)的25首先將全稱量詞(y)改寫(xiě)成存在量詞(y)，其次是引入謂詞S和一個(gè)變?cè)獄，得S(x，z)，建立公式 (

x)((y)(u)(P(x，y，u)^﹁S(x，y))V(z)S(x，z)) 其中﹁S(x，y)的變?cè)?，?y)的變?cè)獃和(y)左邊存在量詞(x)的變?cè)獂,附加的(z)S(x，z)中的變?cè)獄是新引入的未在原公式中出現(xiàn)過(guò)的個(gè)體，S也是不曾在M中出現(xiàn)過(guò)的謂詞．進(jìn)而將(z)左移(等值演算)，便得前束范式 (x)(y)(u)(z)((P(x，y，u)^﹁S(x，y))VS(x，z))． 當(dāng)原公式中，有多個(gè)全稱量詞在存在量詞的左邊，可按這辦法將全稱量詞逐一地右移．前束范式僅在普遍有效的意義下與原公式等值．前束形對(duì)謂詞邏輯完備性的證明是重要的．首先將全稱量詞(y)改寫(xiě)成存在量詞(y)，其次是引入26改寫(xiě)前=>改寫(xiě)后：簡(jiǎn)單改寫(xiě)后=>改寫(xiě)前：反證若A=(x)(y)(u)P(x，y，u)不是普遍有效，則存在解釋I使A為F,于是(x)(y)(u)P(x，y，u)為F.因此在解釋I下，改寫(xiě)后B=(x)(z)S(x，z)可為F,因?yàn)镾是謂詞變?cè)?。改?xiě)前=>改寫(xiě)后：簡(jiǎn)單27(2)Skolem標(biāo)準(zhǔn)形另一種Skolem標(biāo)準(zhǔn)形是僅保留全稱量詞的前束形．定理5.3.3

謂詞邏輯的任一公式A，都可化成相應(yīng)的Skolem標(biāo)準(zhǔn)形(只保留全稱量詞的前束形)，并且A是不可滿足的當(dāng)且僅當(dāng)其Skolem標(biāo)準(zhǔn)形是不可滿足的．這定理是說(shuō)對(duì)不可滿足的公式，它與其Skolem標(biāo)準(zhǔn)形是等值的，而一般的公式與其Skolem標(biāo)準(zhǔn)形并不是等值的．自然僅當(dāng)A是不可滿足的方使用Skolem標(biāo)準(zhǔn)形.(2)Skolem標(biāo)準(zhǔn)形另一種Skolem標(biāo)準(zhǔn)形是僅保留全28例3求公式(x)(y)(z)(u)(v)(w)P(x,y,z,u,v,w)的Skolem標(biāo)準(zhǔn)形．將一公式化成Skolem標(biāo)準(zhǔn)形，首先也要求出前束形．這個(gè)例子已是前束形了，便可直接求Skolem標(biāo)準(zhǔn)形了．首先將最左邊的(x)消去，而將謂詞P中出現(xiàn)的所有變?cè)獂均以論域中的某個(gè)常項(xiàng)a(a未在P中出現(xiàn)過(guò),且不知道a具體是哪個(gè)常量）代入。例3求公式29進(jìn)而消去從左邊數(shù)第二個(gè)存在量詞(u)，因(u)的左邊有全稱量詞(y)(z)，需將謂詞P中出現(xiàn)的所有變?cè)猽均以y，z的某個(gè)二元函數(shù)f(y，z)(f未在P中出現(xiàn)過(guò)，且不知道f具體是哪個(gè)函數(shù))代入．最后按同樣的方法消去存在量詞(w)，因(w)的左邊有全稱量詞(y)(z)和(v)，需將謂詞P中出現(xiàn)的所有變?cè)獁均以y，z，v的某個(gè)三元函數(shù)g(y，z，v)(g未在P中出現(xiàn)過(guò)也不同于f)代入．這樣便得消去全部存在量詞的Skolem標(biāo)準(zhǔn)形

(y)(z)(v)P(a,y,z,f(y,z),v,g(y,z,v))．進(jìn)而消去從左邊數(shù)第二個(gè)存在量詞(u)，因(u)的左邊有全305．4基本的推理公式命題邏輯中有關(guān)推理形式、重言蘊(yùn)涵以及基本的推理公式的討論和所用的術(shù)語(yǔ)，都可引入到謂詞邏輯中．并可把命題邏輯的推理作為謂詞邏輯推理的一個(gè)部分來(lái)看待．這里所介紹的是謂詞邏輯所特有的，在命題邏輯里不能討論的推理形式和基本的推理公式。5．4基本的推理公式命題邏輯中有關(guān)推理形式、重言蘊(yùn)涵以及31

5．4.1推理形式舉例例1所有的整數(shù)都是有理數(shù)，所有的有理數(shù)都是實(shí)數(shù)，所以所有的整數(shù)都是實(shí)數(shù)． 引入謂詞將這三句話形式化，可得如下推理形式:

(x)(P(x)→Q(x))(x)(Q(x)→R(x))→(x)(P(x)→R(x))5．4.1推理形式舉例例1所有的整數(shù)都是有理數(shù)，32例2所有的人都是要死的，孔子是人，所以孔子是要死的，引入謂詞將這三句話形式化，可得如下推理形式： (x)(A(x)→B(x))A(孔子)→B(孔子)．例2所有的人都是要死的，孔子是人，所以孔子是要死的，引入33例3有一個(gè)又高又胖的人，必有一個(gè)高個(gè)子而且有—個(gè)胖子。 引入謂詞將這兩句話形式化，可得如下推理形式： (x)(C(x)D(x))→(x)C(x)(x)D(x)．例3有一個(gè)又高又胖的人，必有一個(gè)高個(gè)子而且有—個(gè)胖子。34例4若某一個(gè)體a具有性質(zhì)E，那么所有的個(gè)體x都具有性質(zhì)E． 這兩句話形式化，可得如下推理形式： E(a)→(x)E(x)不難看出，由例1，2，3所建立的推理形式是正確的，而例4的推理形式是不正確的例4若某一個(gè)體a具有性質(zhì)E，那么所有的個(gè)體x都具有性質(zhì)E355.4.2基本的量詞推理公式(x)P(x)V(x)Q(x)=>(x)(P(x)VQ(x))量詞分配律p73(x)(P(x)Q(x))=>(x)P(x)(x)Q(x)注意(1)的逆否,例3(x)(P(x)→Q(x))=>(x)P(x)→(x)Q(x)5.2.2的推廣(x)(P(x)→Q(x))=>(x)P(x)→(x)Q(x)5.2.2的推廣(5)(x)(P(x)Q(x))=>(x)P(x)(x)Q(x)(3)的推廣(6)(x)(P(x)Q(x))=>(x)P(x)(x)Q(x)(4)的推廣5.4.2基本的量詞推理公式(x)P(x)V(x)Q36(7)(x)(P(x)→Q(x))(x)(Q(x)→R(x))=> (x)(P(x)→R(x))例1(8)(x)(P(x)→Q(x))

P(a)=>Q(a)例2(x)(y)P(x,y)=>(x)(y)P(x,y)易理解(x)(y)P(x,y)=>(y)(x)P(x,y)易理解，注意右邊x是y的函數(shù)這些推理公式或稱推理定理的逆一般是不成立的，所以正確地理解這些定理的前提與結(jié)論的不同是重要的。(7)(x)(P(x)→Q(x))(x)(Q(x375.5推理演算命題邏輯中引入推理規(guī)則的推理演算，可推廣到謂詞邏輯，有關(guān)的推理規(guī)則都可直接移入到謂詞邏輯，除此之外還需介紹4條有關(guān)量詞的消去和引入規(guī)則．(代入規(guī)則需補(bǔ)充說(shuō)明：保持合式公式和普遍有效性不被破壞，見(jiàn)p58)5.5推理演算命題邏輯中引入推理規(guī)則的推理演算，可推廣到385．5．1推理規(guī)則

(1)全稱量詞消去規(guī)則(x)P(x)=>P(y)注：1其中y是論域中任意一個(gè)體．2需限制y不在P(x)中約束出現(xiàn)(右側(cè)量不在左側(cè)約束出現(xiàn))

．如(x)P(x)＝(x)((y)(x<y))在實(shí)數(shù)上成立，不應(yīng)有(x)P(x)=>P(y)因P(y)會(huì)有問(wèn)題．5．5．1推理規(guī)則

(1)全稱量詞消去規(guī)則(x)P(x39(2)全稱量詞引入規(guī)則P(y)=>(x)P(x)注：1任一個(gè)體y(自由變項(xiàng))都具有性質(zhì)P2仍需限制x不在P(y)中約束出現(xiàn)(右側(cè)量不在左側(cè)約束出現(xiàn))．如P(y)＝(x)(x>y)時(shí)，P(x)會(huì)有問(wèn)題(2)全稱量詞引入規(guī)則P(y)=>(x)P(x)40(3)存在量詞消去規(guī)則(x)P(x)=>P(c)注1.c是論域中使P為真的某個(gè)個(gè)體常項(xiàng)．2.需限制(x)P(x)中沒(méi)有自由個(gè)體出現(xiàn)．.還需限制P(x)中不含有c(右側(cè)量不在左側(cè)出現(xiàn))

．如在實(shí)數(shù)域上(x)P(x)=(x)(c<x)時(shí)，P(c)會(huì)出問(wèn)題．思考方式：先定P再定c最后討論(x)P(x)=>P(c)的正確性(3)存在量詞消去規(guī)則(x)P(x)=>P(c)41(4)存在量詞引入規(guī)則P(c)=>(x)P(x)注：1.c是論域中使P為真的一個(gè)特定個(gè)體常項(xiàng)．2.需限制x不出現(xiàn)在P(c)中(右側(cè)量不在左側(cè)出現(xiàn))

．如實(shí)數(shù)域上，P(c)＝(

x)(x>c)時(shí)，P(x)會(huì)出問(wèn)題．(4)存在量詞引入規(guī)則P(c)=>(x)P(x)42這4條推理規(guī)則是基本的，對(duì)多個(gè)量詞下的量詞消去與引入規(guī)則的使用也已談到．再明確說(shuō)明一下．(x)(y)P(x，y)=>(y)P(x，y) 的右端，不允許寫(xiě)成(y)P(y，y)，(x)P(x，c)=>(y)(x)P(x，y) 的右端不允許寫(xiě)成(x)(x)P(x，x)。這4條推理規(guī)則是基本的，對(duì)多個(gè)量詞下的量詞消去與引入規(guī)則的使43(x)(y)P(x，y)=>(y)P(x，y)=>P(x，a) 但不允許再推演出(x)P(x，a)和(y)(x)P(x，y)．原因是(x)(y)P(x，y)成立時(shí)，所找到的y是依賴于x的，從而P(x，y)的成立是有條件的，不是對(duì)所有的x對(duì)同一個(gè)a都有P(x，a)成立，于是不能再推演出(y)(x)P(x,y)．(x)(y)P(x，y)=>(y)P(x，y)=>P(445．5．2使用推理規(guī)則的推理演算舉例和命題邏輯相比，在謂詞邏輯里使用推理規(guī)則進(jìn)行推理演算同樣是方便的，然而在謂詞邏輯里，真值表法不能使用，又不存在判明A→B是普遍有效的一般方法，從而使用推理規(guī)則的推理方法已是謂詞邏輯的基本推理演算方法．推理演算過(guò)程．首先是將以自然語(yǔ)句表示的推理問(wèn)題引入謂詞形式化，若不能直接使用基本的推理公式便消去量詞，在無(wú)量詞下使用規(guī)則和公式推理，最后再引入量詞以求得結(jié)論．5．5．2使用推理規(guī)則的推理演算舉例和命題邏輯相比，在謂45例1前提(x)(P(x)→Q(x))，(x)(Q(x)→R(x)) 結(jié)論(x)(P(x)→R(x))證明

(1)(x)(P(x)→Q(x)) 前提

(2)P(x)→Q(x) 全稱量詞消去

(3)(x)(Q(x)→R(x)) 前提

(4)Q(x)→R(x) 全稱量詞消去

(5)P(x)→R(x) (2)，(4)三段論

(6)(x)(P(x)→R(x)) 全稱量詞引入例1前提(x)(P(x)→Q(x))，(x)(Q46例2所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的． 首先引入謂詞形式化，令P(x)表x是人，Q(x)表x是要死的，于是問(wèn)題可描述為(x)(P(x)→Q(x))^P(蘇格拉底)→Q(蘇格拉底)證明

(1)(x)(P(x)→Q(x)) 前提

(2)P(蘇格拉底)→Q(蘇格拉底) 全稱量詞消去

(3)P(蘇格拉底) 前提

(4)Q(蘇格拉底) (2)(3)分離規(guī)則例2所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死47例3前提(x)P(x)→(x)((P(x)VQ(x))→R(x))，(x)P(x) 結(jié)論(x)(y)(R(x)^R(y))證明

(1)(x)P(x)→(x)((P(x)VQ(x))→R(x)) 前提

(2)(x)P(x) 前提

(3)(x)((P(x)VQ(x))→R(x)) (1)，(2)分離

(4)P(c) (2)存在量詞消去

(5)P(c)VQ(c)→R(c) (3)全稱量詞消去

(6)P(c)VQ(c) (4)(7)R(c) (5)，(6)分離

(8)(x)R(x) (7)存在量詞引入

(9)(y)R(y) (7)存在量詞引入

(10)(x)R(x)^(y)R(y) (8)，(9)(11)(x)(y)(R(x)^R(y)) (10)置換例3前提(x)P(x)→(x)((P(x)VQ(x)48例4(不正確)分析下述推理的正確性

(1)(x)(y)(x>y) 前提

(2)(y)(z>y) 全稱量詞消去,y與z有關(guān)

(3)z>b 存在量詞消去,b依賴z

(4)(z)(z>b) 全稱量詞引入,b不依賴z

(5)b>b 全稱量詞消去

(6)(x)(x>x) 全稱量詞引入推理(1)到(2)，應(yīng)明確指出y是依賴于x的，即(2)中y和z有關(guān)．(2)到(3)，其中的b是依賴于z的．從而(3)到(4)是不成立的．又由于b是常項(xiàng)，(5)到(6)也是不允許的，因個(gè)體常項(xiàng)不能用全稱量詞量化．例4(不正確)分析下述推理的正確性495．6謂詞邏輯的歸結(jié)推理法歸結(jié)方法可推廣到謂詞邏輯，困難在于出現(xiàn)了量詞，變?cè)C明過(guò)程同命題邏輯，只不過(guò)每一步驟都要考慮到有變?cè)?，從而帶?lái)復(fù)雜性．使用推理規(guī)則的推理演算過(guò)于靈活，技巧性強(qiáng)，而歸結(jié)法較為機(jī)械，容易使用計(jì)算機(jī)來(lái)實(shí)現(xiàn)。5．6謂詞邏輯的歸結(jié)推理法歸結(jié)方法可推廣到謂詞邏輯，困難505.6.1謂詞邏輯歸結(jié)證明過(guò)程四步驟

(從例子來(lái)理解步驟)(1)為證明A→B是定理(A，B為謂詞公式)，即AB,等價(jià)的是證明G=AB是矛盾式，這是歸結(jié)法的出發(fā)點(diǎn)(反證法)．(2)通過(guò)G的合取形式建立子句集S，在建立子句集S的時(shí)．利用前束范式及Skolem標(biāo)準(zhǔn)形(不嚴(yán)格)，消去存在量詞(以常項(xiàng)代替如a)，消去全稱量詞(注意新的自由變?cè)鐇,y)。理論：S中的前提與G在不可滿足的意義下是一致的。

5.6.1謂詞邏輯歸結(jié)證明過(guò)程四步驟

(從例子來(lái)理解步驟51(3)對(duì)S作歸結(jié):(P(x)Q(x))并且(﹁P(a)R(y))可以歸結(jié)出Q(a)R(y)理論：因?yàn)?P(a)Q(a))(﹁P(a)R(y))Q(a)R(y)理論：變?cè)獂統(tǒng)一換成特定個(gè)體a稱為合一置換{x／a}

(4)重復(fù)歸結(jié)方法，最后得到矛盾．(3)對(duì)S作歸結(jié):525．6．2歸結(jié)法證明舉例例1(x)(P(x)→Q(x))^(x)(Q(x)→R(x))=>(x)(P(x)→R(x)) 首先寫(xiě)出公式G G＝(x)(P(x)→Q(x))^(x)(Q(x)→R(x))^﹁

(x)(P(x)→R(x)) 為求G的子句集S，可分別對(duì)(x)(P(x)→Q(x))，(x)(Q(x)→R(x))，﹁

(x)(P(x)→R(x))作子句集，然后求并集來(lái)作為G的“子句集”(這個(gè)“子句集”不一定是S，但與S同時(shí)是不可滿足的，而且較S來(lái)得簡(jiǎn)單，于是為方便可將這個(gè)“子句集”視作S)． (x)(P(x)→Q(x))的子句集為{﹁P(x)VQ(x)) (x)(Q(x)→R(x))的子句集為{﹁Q(x)VR(x)}

﹁

(x)(P(x)→R(x))＝(x)﹁(﹁P(x)VR(x))＝(x)(P(x)^﹁R(x)) Skolem化，得子句集{P(a)，﹁R(a)} 于是G的子句集S＝{﹁P(x)VQ(x)，﹁Q(x)VR(x)，P(a)，﹁R(a)}5．6．2歸結(jié)法證明舉例例1(x)(P(x)→Q(53證明S是不可滿足的，有歸結(jié)過(guò)程：

(1)﹁P(x)VQ(x)(2)﹁Q(x)VR(x)(3)P(a)(4)﹁R(a)(5)Q(a) (1)(3)歸結(jié)

(6)R(a) (2)(5)歸結(jié)

(7)口 (4)(6)歸結(jié)證明S是不可滿足的，有歸結(jié)過(guò)程：54例2 A1＝(x)(P(x)^(y)(D(y)→L(x,y))) A2＝(x)(P(x)→(y)(Q(y)→﹁L(x，y))) B＝(x)(D(x)→﹁Q(x))

求證A1^A2=>B． 證明不難建立A1的子句集為{P(a)，﹁D(y)VL(a，y)}，A2的子句集為{﹁P(x)V﹁Q(y)V﹁L(x，y)},﹁B的子句集為{D(b)，Q(b)}，求并集得子句集S，進(jìn)而建立歸結(jié)過(guò)程：例2 A1＝(x)(P(x)^(y)(D(y)→L(55 (1)P(a) (2)﹁D(y)VL(a，y) (3)﹁P(x)V﹁Q(y)V﹁L(x，y) (4)D(b) (5)Q(b) (6)L(a，b) (2)(4)歸結(jié)

(7)﹁Q(y)V﹁L(a，y) (1)(3)歸結(jié)

(8)﹁L(a，b) (5)(7)歸結(jié)

(9)口 (6)(8)歸結(jié) (1)P(a)56第5章謂詞邏輯的等值和推理演算謂詞邏輯研究的對(duì)象是重要的邏輯規(guī)律，普遍有效式是最重要的邏輯規(guī)律，而等值式、推理式都是普遍有效的謂詞公式，因此等值和推理演算就成了謂詞邏輯的基本內(nèi)容．這章的討論，主要是以語(yǔ)義的觀點(diǎn)進(jìn)行的非形式的描述，而嚴(yán)格的形式化的討論見(jiàn)第6章所建立的公理系統(tǒng)．第5章謂詞邏輯的等值和推理演算謂詞邏輯研究的對(duì)象是重要的575．1否定型等值式等值：若給定了兩個(gè)謂詞公式A，B，說(shuō)A和B是等值的，如果在公式A，B的任一解釋(注意在謂詞邏輯中，解釋的范圍還包含論域以外的其他要素，見(jiàn)P65)下，A和B都有相同的真值．其他說(shuō)法：A，B等值當(dāng)且僅當(dāng)A?B是普遍有效的公式(注意這里不再說(shuō)重言式了)．記作A＝B或AB。5．1否定型等值式等值：若給定了兩個(gè)謂詞公式A，B，說(shuō)A585．1．1由命題公式移植來(lái)的等值式若將命題公式的等值式，直接以謂詞公式代入命題變項(xiàng)便可得謂詞等值式．由 ﹁﹁p＝p,p→q=﹁p∨q, (p∧q)∨r=(p∨r)∧(q∨r)

可得(以下每?jī)蓚€(gè)為一對(duì)：無(wú)量詞、有量詞) ﹁﹁P(x)＝P(x) ﹁﹁(x)P(x)＝(x)P(x) P(x)→Q(x)＝﹁P(x)∨Q(x) (x)P(x)→(x)Q(x)＝﹁

(x)P(x)∨(x)Q(x) (P(x)∧Q(x))∨R(x)=(P(x)∨R(x))∧(Q(x)∨R(x)) ((x)P(x)∧Q(y))∨(z)R(z) =((x)P(x)∨(z)R(z))∧(Q(y)∨(z)R(z))5．1．1由命題公式移植來(lái)的等值式若將命題公式的等值式，595．1．2否定型等值式

（摩根律的推廣）

﹁(x)P(x)=(x)﹁P(x) ﹁(x)P(x)=(x)﹁P(x)形式上看這對(duì)公式，是說(shuō)否定詞”﹁”可越過(guò)量詞深入到量詞的轄域內(nèi)，但要把所越過(guò)的量詞轉(zhuǎn)換為，轉(zhuǎn)換為.5．1．2否定型等值式

（摩根律的推廣） ﹁(x)P60(1)從語(yǔ)義上說(shuō)明

(2)例：在{l，2}域上分析

﹁(x)P(x)=﹁(P(1)P(2))=﹁P(1)v﹁P(2)=(x)﹁P(x)

﹁(x)P(x)=﹁(P(1)vP(2))=﹁P(1)﹁P(2)=(x)﹁P(x)(1)從語(yǔ)義上說(shuō)明

(2)例：在{l，2}域上分析 ﹁(x61(3)語(yǔ)義上的證明證明方法：依等值式定義，A=B如果在任一解釋I下A真B就真，而且B真A就真．

若證明﹁(x)P(x)=(x)﹁P(x)

1.設(shè)某一解釋I下若﹁(x)P(x)=T 從而(x)P(x)=F，即有一個(gè)xoD,使P(Xo)=F 于是﹁P(xo)=T

故在I下(x)﹁P(x)=T 2.反過(guò)來(lái)，設(shè)某一解釋I下若(x)﹁P(x)=T 即有一個(gè)xoD,使﹁P(Xo)=T

從而P(Xo)=F 于是(x)P(x)=F 即﹁

(x)P(x)=T(3)語(yǔ)義上的證明證明方法：依等值式定義，A=B如果在任一解62(4)舉例例1“并非所有的動(dòng)物都是貓”的表示設(shè) A(x)：x是動(dòng)物 B(x)：x是描原語(yǔ)句可表示成﹁(x)(A(x)B(x))依否定型公式得(4)舉例例1“并非所有的動(dòng)物都是貓”的表示63例2“天下烏鴉—般黑”的表示設(shè) F(x)：x是烏鴉 G(x，y)：x與y是一般黑原語(yǔ)句可表示成

(x)(y)(F(x)^F(y)→G(x,y))不難知道與之等值的公式是

﹁(x)(y)(F(x)^F(y)^﹁G(x,y))即不存在x,y是烏鴉但不一般黑．這兩句話含義是相同的．經(jīng)計(jì)算有例2“天下烏鴉—般黑”的表示64全稱量詞消去課件65

5．2量詞分配等值式

一、含單獨(dú)的命題變項(xiàng)，與x無(wú)關(guān)

5．2．1量詞對(duì)、的分配律這是一組量詞對(duì)、的分配律，其中q是命題變項(xiàng)，與個(gè)體變?cè)獂無(wú)關(guān)，這是很重要的條件．我們僅對(duì)第一個(gè)等式給出證明，其余三個(gè)同樣可證．5．2量詞分配等值式

一、含單獨(dú)的命題變項(xiàng)，與x無(wú)關(guān)

66設(shè)在一解釋I下，(x)(P(x)q)=T，從而對(duì)任一xD，有P(x)q=T

若q＝T，則(x)P(x)q=T

若q＝F，從而對(duì)任一xD，有P(x)=T，即有(x)P(x)=T，故仍有，(x)P(x)q=T反過(guò)來(lái)，設(shè)在一解釋I下，(x)P(x)q=T，若q=T，則(x)(P(x)q)=T

若q=F，必有(x)P(x)=T，從而對(duì)任一xD有P(x)=T，于是對(duì)任一xD有P(x)q=T故(x)(P(x)q)=T．設(shè)在一解釋I下，(x)(P(x)q)=T，從而對(duì)任一x675．2．2量詞對(duì)→的分配律這是一組量詞對(duì)→的分配律，其中p，q是命題變項(xiàng)，與個(gè)體變?cè)獂無(wú)關(guān)，這是很重要的條件．5.2節(jié)介紹的等值公式中僅有這里的第一、二個(gè)公式有量詞的改變！！5．2．2量詞對(duì)→的分配律68先證明其中的第一個(gè)等式． 依5．2．1的等值式 依5．l．2的等值式先證明其中的第一個(gè)等式．69再證明其中的第三個(gè)等式

依5．2．l的等值式其余兩個(gè)等值式同樣可證．再證明其中的第三個(gè)等式70二、轄域中無(wú)單獨(dú)的命題變項(xiàng)

5．2．3量詞對(duì)

、量詞對(duì)V的分配律這是當(dāng)P(x)，Q(x)都含有個(gè)體變?cè)獂時(shí)，量詞對(duì)^，量詞對(duì)V所遵從的分配律．然而對(duì)V，對(duì)^的分配律一般并不成立．證明中使用了5.2.1中的解釋方法。(x)P(x)v(x)Q(x)=>(x)(P(x)vQ(x))(x)(P(x)^Q(x))=>(x)P(x)^(x)Q(x)二、轄域中無(wú)單獨(dú)的命題變項(xiàng)

5．2．3量詞對(duì)、量詞71一些例子一些例子725．2．4變?cè)酌蟮姆峙渎?/p>

(在求前束范式時(shí)有很大作用)這兩個(gè)等值式，說(shuō)明了通過(guò)變?cè)囊酌钥蓪?shí)現(xiàn)對(duì)V，對(duì)^的分配律．證明是容易的．首先有變?cè)酌戎凳?(x)P(x)=(y)P(y) (x)P(x)=(y)P(y) 于是(x)P(x)v(x)Q(x)=(x)P(x)v(y)Q(y)5．2．4變?cè)酌蟮姆峙渎?/p>

(在求前束范式時(shí)有很大作用73對(duì)x而言(y)Q(y)相當(dāng)于命題變項(xiàng)，與x無(wú)關(guān)，可推得 (x)P(x)v(y)Q(y)=(x)(P(x)v(y)Q(y))對(duì)y而言，P(x)相當(dāng)于命題變項(xiàng)與y無(wú)關(guān)，又可推得 (x)(P(x)v(y)Q(y))=(x)(y)(P(x)vQ(y)) 同理(x)(y)(P(x)^Q(y))=(x)P(x)^(x)Q(x) 然而(x)(y)(P(x)vQ(y))與(x)(P(x)vQ(x))

是不等值的(x)(y)(P(x)^Q(y))與(x)(P(x)^Q(x)) 也是不等值的對(duì)x而言(y)Q(y)相當(dāng)于命題變項(xiàng)，與x無(wú)關(guān)，可推得745．3范式在命題邏輯里．每一公式都有與之等值的范式，范式是一種統(tǒng)一的表達(dá)形式．對(duì)謂詞邏輯的公式來(lái)說(shuō)也有范式，其中前束范式與原公式是等值的，而其他范式與原公式只有較弱的關(guān)系。5．3范式在命題邏輯里．每一公式都有與之等值的范755．3．1前束范式定義5．3．1

說(shuō)公式A是一個(gè)前束范式，如果A中的一切量詞都位于該公式的最左邊(不含否定詞)且這些量詞的轄域都延伸到公式的末端，前束范式A的一般形式為 (Q1x1)…(Qnxn)M(xl，…，xn)

其中Qi為量詞或(i＝l，…，n)，M稱作公式A的母式(基式)，M中不再有量詞．定理5．3．1謂詞邏輯的任一公式都可化為與之等值的前束范式．但其前束范式并不唯一．5．3．1前束范式定義5．3．1說(shuō)公式A是一個(gè)前束范76全稱量詞消去課件77經(jīng)過(guò)這幾步，便可求得任一公式的前束范式．由于每一步變換都保持著等值性，所以，所得到的前束形與原公式是等值的．這里的S(a，b，x，y，z)便是原公式的母式．其中a,b為自由個(gè)體變項(xiàng)。由于前束中量詞的次序排列，以及對(duì)母式都沒(méi)有明確的限制，自然前束范式不是唯一的，如例1的前束范式也可以是 (x)(z)(y)(S(a,b,x,y,z)P) 其中P可以是任一不含量詞的普遍有效的公式。經(jīng)過(guò)這幾步，便可求得任一公式的前束范式．由于每一步變換都保持785．3．2Skolem標(biāo)準(zhǔn)形前束范式對(duì)前束量詞沒(méi)有次序要求，也沒(méi)有其他要求．如果對(duì)前束范式進(jìn)而要求所有存在量詞都在全稱量詞之左得到存在前束范式(略)，或是只保留全稱量詞而消去存在量詞得到Skolem標(biāo)準(zhǔn)形。不難想像，仍保持與原公式的等值性就不可能了，只能保持在某種意義下的等值關(guān)系．5．3．2Skolem標(biāo)準(zhǔn)形前束范式對(duì)前束量詞沒(méi)有次序要79(1)前束范式(略)一個(gè)公式的前束范式為(x1)…(xi)(xi+1)…(xn)M(x1，…，xn) 即存在量詞都在全稱量詞的左邊，且可保持至少有一個(gè)存在量詞(i≥1)，其中M(x1，…，xn)中不再含有量詞也無(wú)自由個(gè)體變項(xiàng)定理5.3.2

謂詞邏輯的任一公式A，都可化成相應(yīng)的前束范式，并且A是普遍有效的當(dāng)且僅當(dāng)其前束范式是普遍有效的。這定理是說(shuō)對(duì)普遍有效的公式，它與其前束范式是等值的，而一般的公式與其前束范式并不是等值的．自然僅當(dāng)A是普遍有效的，方使用前束范式．(1)前束范式(略)一個(gè)公式的前束范式為(80例2求(x)(y)(u)P(x，y，u)的前束范式(P中無(wú)量詞)．將一公式化成前束形，首先要求出前束形，再做前束，這個(gè)例子已是前束形了，便可直接求前束形．例2求(x)(y)(u)P(x，y，u)的81首先將全稱量詞(y)改寫(xiě)成存在量詞(y)，其次是引入謂詞S和一個(gè)變?cè)獄，得S(x，z)，建立公式 (

x)((y)(u)(P(x，y，u)^﹁S(x，y))V(z)S(x，z)) 其中﹁S(x，y)的變?cè)?y)的變?cè)獃和(y)左邊存在量詞(x)的變?cè)獂,附加的(z)S(x，z)中的變?cè)獄是新引入的未在原公式中出現(xiàn)過(guò)的個(gè)體，S也是不曾在M中出現(xiàn)過(guò)的謂詞．進(jìn)而將(z)左移(等值演算)，便得前束范式 (x)(y)(u)(z)((P(x，y，u)^﹁S(x，y))VS(x，z))． 當(dāng)原公式中，有多個(gè)全稱量詞在存在量詞的左邊，可按這辦法將全稱量詞逐一地右移．前束范式僅在普遍有效的意義下與原公式等值．前束形對(duì)謂詞邏輯完備性的證明是重要的．首先將全稱量詞(y)改寫(xiě)成存在量詞(y)，其次是引入82改寫(xiě)前=>改寫(xiě)后：簡(jiǎn)單改寫(xiě)后=>改寫(xiě)前：反證若A=(x)(y)(u)P(x，y，u)不是普遍有效，則存在解釋I使A為F,于是(x)(y)(u)P(x，y，u)為F.因此在解釋I下，改寫(xiě)后B=(x)(z)S(x，z)可為F,因?yàn)镾是謂詞變?cè)?。改?xiě)前=>改寫(xiě)后：簡(jiǎn)單83(2)Skolem標(biāo)準(zhǔn)形另一種Skolem標(biāo)準(zhǔn)形是僅保留全稱量詞的前束形．定理5.3.3

謂詞邏輯的任一公式A，都可化成相應(yīng)的Skolem標(biāo)準(zhǔn)形(只保留全稱量詞的前束形)，并且A是不可滿足的當(dāng)且僅當(dāng)其Skolem標(biāo)準(zhǔn)形是不可滿足的．這定理是說(shuō)對(duì)不可滿足的公式，它與其Skolem標(biāo)準(zhǔn)形是等值的，而一般的公式與其Skolem標(biāo)準(zhǔn)形并不是等值的．自然僅當(dāng)A是不可滿足的方使用Skolem標(biāo)準(zhǔn)形.(2)Skolem標(biāo)準(zhǔn)形另一種Skolem標(biāo)準(zhǔn)形是僅保留全84例3求公式(x)(y)(z)(u)(v)(w)P(x,y,z,u,v,w)的Skolem標(biāo)準(zhǔn)形．將一公式化成Skolem標(biāo)準(zhǔn)形，首先也要求出前束形．這個(gè)例子已是前束形了，便可直接求Skolem標(biāo)準(zhǔn)形了．首先將最左邊的(x)消去，而將謂詞P中出現(xiàn)的所有變?cè)獂均以論域中的某個(gè)常項(xiàng)a(a未在P中出現(xiàn)過(guò),且不知道a具體是哪個(gè)常量）代入。例3求公式85進(jìn)而消去從左邊數(shù)第二個(gè)存在量詞(u)，因(u)的左邊有全稱量詞(y)(z)，需將謂詞P中出現(xiàn)的所有變?cè)猽均以y，z的某個(gè)二元函數(shù)f(y，z)(f未在P中出現(xiàn)過(guò)，且不知道f具體是哪個(gè)函數(shù))代入．最后按同樣的方法消去存在量詞(w)，因(w)的左邊有全稱量詞(y)(z)和(v)，需將謂詞P中出現(xiàn)的所有變?cè)獁均以y，z，v的某個(gè)三元函數(shù)g(y，z，v)(g未在P中出現(xiàn)過(guò)也不同于f)代入．這樣便得消去全部存在量詞的Skolem標(biāo)準(zhǔn)形

(y)(z)(v)P(a,y,z,f(y,z),v,g(y,z,v))．進(jìn)而消去從左邊數(shù)第二個(gè)存在量詞(u)，因(u)的左邊有全865．4基本的推理公式命題邏輯中有關(guān)推理形式、重言蘊(yùn)涵以及基本的推理公式的討論和所用的術(shù)語(yǔ)，都可引入到謂詞邏輯中．并可把命題邏輯的推理作為謂詞邏輯推理的一個(gè)部分來(lái)看待．這里所介紹的是謂詞邏輯所特有的，在命題邏輯里不能討論的推理形式和基本的推理公式。5．4基本的推理公式命題邏輯中有關(guān)推理形式、重言蘊(yùn)涵以及87

5．4.1推理形式舉例例1所有的整數(shù)都是有理數(shù)，所有的有理數(shù)都是實(shí)數(shù)，所以所有的整數(shù)都是實(shí)數(shù)． 引入謂詞將這三句話形式化，可得如下推理形式:

(x)(P(x)→Q(x))(x)(Q(x)→R(x))→(x)(P(x)→R(x))5．4.1推理形式舉例例1所有的整數(shù)都是有理數(shù)，88例2所有的人都是要死的，孔子是人，所以孔子是要死的，引入謂詞將這三句話形式化，可得如下推理形式： (x)(A(x)→B(x))A(孔子)→B(孔子)．例2所有的人都是要死的，孔子是人，所以孔子是要死的，引入89例3有一個(gè)又高又胖的人，必有一個(gè)高個(gè)子而且有—個(gè)胖子。 引入謂詞將這兩句話形式化，可得如下推理形式： (x)(C(x)D(x))→(x)C(x)(x)D(x)．例3有一個(gè)又高又胖的人，必有一個(gè)高個(gè)子而且有—個(gè)胖子。90例4若某一個(gè)體a具有性質(zhì)E，那么所有的個(gè)體x都具有性質(zhì)E． 這兩句話形式化，可得如下推理形式： E(a)→(x)E(x)不難看出，由例1，2，3所建立的推理形式是正確的，而例4的推理形式是不正確的例4若某一個(gè)體a具有性質(zhì)E，那么所有的個(gè)體x都具有性質(zhì)E915.4.2基本的量詞推理公式(x)P(x)V(x)Q(x)=>(x)(P(x)VQ(x))量詞分配律p73(x)(P(x)Q(x))=>(x)P(x)(x)Q(x)注意(1)的逆否,例3(x)(P(x)→Q(x))=>(x)P(x)→(x)Q(x)5.2.2的推廣(x)(P(x)→Q(x))=>(x)P(x)→(x)Q(x)5.2.2的推廣(5)(x)(P(x)Q(x))=>(x)P(x)(x)Q(x)(3)的推廣(6)(x)(P(x)Q(x))=>(x)P(x)(x)Q(x)(4)的推廣5.4.2基本的量詞推理公式(x)P(x)V(x)Q92(7)(x)(P(x)→Q(x))(x)(Q(x)→R(x))=> (x)(P(x)→R(x))例1(8)(x)(P(x)→Q(x))

P(a)=>Q(a)例2(x)(y)P(x,y)=>(x)(y)P(x,y)易理解(x)(y)P(x,y)=>(y)(x)P(x,y)易理解，注意右邊x是y的函數(shù)這些推理公式或稱推理定理的逆一般是不成立的，所以正確地理解這些定理的前提與結(jié)論的不同是重要的。(7)(x)(P(x)→Q(x))(x)(Q(x935.5推理演算命題邏輯中引入推理規(guī)則的推理演算，可推廣到謂詞邏輯，有關(guān)的推理規(guī)則都可直接移入到謂詞邏輯，除此之外還需介紹4條有關(guān)量詞的消去和引入規(guī)則．(代入規(guī)則需補(bǔ)充說(shuō)明：保持合式公式和普遍有效性不被破壞，見(jiàn)p58)5.5推理演算命題邏輯中引入推理規(guī)則的推理演算，可推廣到945．5．1推理規(guī)則

(1)全稱量詞消去規(guī)則(x)P(x)=>P(y)注：1其中y是論域中任意一個(gè)體．2需限制y不在P(x)中約束出現(xiàn)(右側(cè)量不在左側(cè)約束出現(xiàn))

．如(x)P(x)＝(x)((y)(x<y))在實(shí)數(shù)上成立，不應(yīng)有(x)P(x)=>P(y)因P(y)會(huì)有問(wèn)題．5．5．1推理規(guī)則

(1)全稱量詞消去規(guī)則(x)P(x95(2)全稱量詞引入規(guī)則P(y)=>(x)P(x)注：1任一個(gè)體y(自由變項(xiàng))都具有性質(zhì)P2仍需限制x不在P(y)中約束出現(xiàn)(右側(cè)量不在左側(cè)約束出現(xiàn))．如P(y)＝(x)(x>y)時(shí)，P(x)會(huì)有問(wèn)題(2)全稱量詞引入規(guī)則P(y)=>(x)P(x)96(3)存在量詞消去規(guī)則(x)P(x)=>P(c)注1.c是論域中使P為真的某個(gè)個(gè)體常項(xiàng)．2.需限制(x)P(x)中沒(méi)有自由個(gè)體出現(xiàn)．.還需限制P(x)中不含有c(右側(cè)量不在左側(cè)出現(xiàn))

．如在實(shí)數(shù)域上(x)P(x)=(x)(c<x)時(shí)，P(c)會(huì)出問(wèn)題．思考方式：先定P再定c最后討論(x)P(x)=>P(c)的正確性(3)存在量詞消去規(guī)則(x)P(x)=>P(c)97(4)存在量詞引入規(guī)則P(c)=>(x)P(x)注：1.c是論域中使P為真的一個(gè)特定個(gè)體常項(xiàng)．2.需限制x不出現(xiàn)在P(c)中(右側(cè)量不在左側(cè)出現(xiàn))

．如實(shí)數(shù)域上，P(c)＝(

x)(x>c)時(shí)，P(x)會(huì)出問(wèn)題．(4)存在量詞引入規(guī)則P(c)=>(x)P(x)98這4條推理規(guī)則是基本的，對(duì)多個(gè)量詞下的量詞消去與引入規(guī)則的使用也已談到．再明確說(shuō)明一下．(x)(y)P(x，y)=>(y)P(x，y) 的右端，不允許寫(xiě)成(y)P(y，y)，(x)P(x，c)=>(y)(x)P(x，y) 的右端不允許寫(xiě)成(x)(x)P(x，x)。這4條推理規(guī)則是基本的，對(duì)多個(gè)量詞下的量詞消去與引入規(guī)則的使99(x)(y)P(x，y)=>(y)P(x，y)=>P(x，a) 但不允許再推演出(x)P(x，a)和(y)(x)P(x，y)．原因是(x)(y)P(x，y)成立時(shí)，所找到的y是依賴于x的，從而P(x，y)的成立是有條件的，不是對(duì)所有的x對(duì)同一個(gè)a都有P(x，a)成立，于是不能再推演出(y)(x)P(x,y)．(x)(y)P(x，y)=>(y)P(x，y)=>P(1005．5．2使用推理規(guī)則的推理演算舉例和命題邏輯相比，在謂詞邏輯里使用推理規(guī)則進(jìn)行推理演算同樣是方便的，然而在謂詞邏輯里，真值表法不能使用，又不存在判明A→B是普遍有效的一般方法，從而使用推理規(guī)則的推理方法已是謂詞邏輯的基本推理演算方法．推理演算過(guò)程．首先是將以自然語(yǔ)句表示的推理問(wèn)題引入謂詞形式化，若不能直接使用基本的推理公式便消去量詞，在無(wú)量詞下使用規(guī)則和公式推理，最后再引入量詞以求得結(jié)論．5．5．2使用推理規(guī)則的推理演算舉例和命題邏輯相比，在謂101例1前提(x)(P(x)→Q(x))，(x)(Q(x)→R(x)) 結(jié)論(x)(P(x)→R(x))證明

(1)(x)(P(x)→Q(x)) 前提

(2)P(x)→Q(x) 全稱量詞消去

(3)(x)(Q(x)→R(x)) 前提

(4)Q(x)→R(x) 全稱量詞消去

(5)P(x)→R(x) (2)，(4)三段論

(6)(x)(P(x)→R(x)) 全稱量詞引入例1前提(x)(P(x)→Q(x))，(x)(Q102例2所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的． 首先引入謂詞形式化，令P(x)表x是人，Q(x)表x是要死的，于是問(wèn)題可描述為(x)(P(x)→Q(x))^P(蘇格拉底)→Q(蘇格拉底)證明

(1)(x)(P(x)→Q(x)) 前提

(2)P(蘇格拉底)→Q(蘇格拉底) 全稱量詞消去

(3)P(蘇格拉底) 前提

(4)Q(蘇格拉底) (2)(3)分離規(guī)則例2所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死103例3前提(x)P(x)→(x)((P(x)VQ(x))→R(x))，(x)P(x) 結(jié)論(x)(y)(R(x)^R(y))證明

(1)(x)P(x)→(x)((P(x)VQ(x))→R(x)) 前提

(2)(x)P(x) 前提

(3)(x)((P(x)VQ(x))→R(x)) (1)，(2)分離

(4)P(c) (2)存在量詞消去

(