第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(Predicateanditsexpression)2.2謂詞公式與翻譯(Predicateformulae)2.3變元的約束(Boundofvariable)2.4謂詞演算的等價(jià)式與蘊(yùn)含式(Equivalences&implicationsofpredicatecalculus)2.5謂詞公式范式(Prenexnormalform)2.6謂詞演算的推理理論(Inferencetheoryofpredicatecalculus)第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)命題邏輯的局限性：

在命題邏輯中，命題是命題演算的基本單位，不再對原子命題進(jìn)行分解，因而無法研究命題的內(nèi)部結(jié)構(gòu)、成分及命題之間的內(nèi)在聯(lián)系，甚至無法處理一些簡單而又常見的推理過程。例如，下列推理：所有的人都是要死的。蘇格拉底是人。蘇格拉底是要死的。眾所周知,這是真命題。但在命題邏輯中,如果用P,Q,R表示以上三個(gè)命題，則上述推理過程為：(P∧Q)R。借助命題演算的推理理論不能證明其為重言式。第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)原因：命題邏輯不能將命題之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系反映出來。解決辦法：將命題進(jìn)行分解。第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)2.1謂詞的概念與表示(Predicateanditsexpression)2.1.1客體和謂詞在謂詞邏輯中，可將原子命題劃分為客體和謂詞兩部分?？腕w：可以獨(dú)立存在的具體事物的或抽象的概念。例如，電子計(jì)算機(jī)、李明、玫瑰花、黑板、實(shí)數(shù)、中國、思想、唯物主義等，客體也可稱之為主語。第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)謂詞：用來刻劃客體的性質(zhì)或客體之間的相互關(guān)系的詞。例如在下面命題中：（1）張明是個(gè)勞動(dòng)模范。（2）李華是個(gè)勞動(dòng)模范?？虅澘腕w的性質(zhì)（3）王紅是個(gè)大學(xué)生。（4）小李比小趙高2cm。（5）點(diǎn)a在b與c之間?？虅澘腕w之間的相互關(guān)系（6）阿杜與阿寺同歲。

“是個(gè)勞動(dòng)模范”、“是個(gè)大學(xué)生”、“…比…高2cm”、“…

在…與…之間”都是謂詞。第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)刻劃一個(gè)客體性質(zhì)的詞稱之為一元謂詞,刻劃n個(gè)客體之間關(guān)系的詞稱之為n元謂詞.一般我們用大寫英文字母表示謂詞，用小寫英文字母表示客體名稱，例如，將上述謂詞分別記作大寫字母F、G、H、R，S則上述命題可表示為：

(1)F(a)a：張明(2)F(b)b：李華

(3)G(c)c：王紅(4)H(s,t)s：小李t：小趙

(5)R(a,b,c)(6)S(a,b)a:阿杜。b:阿寺。其中(1)、(2)、(3)為一元謂詞，(4)、(6)為二元謂詞，

(5)為三元謂詞。第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)注:(1)單獨(dú)一個(gè)謂詞并不是命題，在謂詞字母后填上客體所得到的式子稱之為謂詞填式。(2)在謂詞填式中，若客體確定，則A(a1，a2,...,an)就變成了命題。(3)在多元謂詞表達(dá)式中，客體字母出現(xiàn)的先后次序與事先約定有關(guān),一般不可以隨意交換位置(如,上例中H(s,t)與H(t,s)代表兩個(gè)不同的命題)。

第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)

設(shè)謂詞H表示“是勞動(dòng)模范”,a表示客體名稱張明,b表示客體名稱李華,c表示客體名稱這只老虎，那么H(a)

、H(b)、H(c)表示三個(gè)不同的命題,但它們有一個(gè)共同的形式,即H(x).一般地，H(x)表示客體x具有性質(zhì)H。這里x表示抽象的或泛指的客體，稱為客體變元，常用小寫英文字母x,y,z,…表示。相應(yīng)地，表示具體或特定的客體的詞稱為客體常項(xiàng)，常用小寫英文字母a,b,c,…表示。

第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)同理，客體變元x，y具有關(guān)系L，記作L(x,y);客體變元x,y,z具有關(guān)系A(chǔ)，記作A(x,y,z).H(x)、L(x,y)、A(x,y,z)本身并不是一個(gè)命題.只有用特定的客體取代客體變元x,y,z后，它們才成為命題。我們稱H(x)、L(x,y)、A(x,y,z)為命題函數(shù)。一般地我們有第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)定義2.1.1:由一個(gè)謂詞H和n個(gè)客體變元組成的表達(dá)式H(x1,x2,

…,

xn)稱為n元簡單命題函數(shù).由定義可知,n元謂詞就是有n個(gè)客體變元的命題函數(shù).當(dāng)n=0時(shí),稱為0元謂詞.因此,一般情況下,命題函數(shù)不是命題;特殊情況0元謂詞就變成一個(gè)命題.復(fù)合命題函數(shù):由一個(gè)或幾個(gè)簡單命題函數(shù)以及邏輯聯(lián)結(jié)詞組合而成的表達(dá)式.第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)例1:若x的學(xué)習(xí)好,則x的工作好設(shè)S(x):x學(xué)習(xí)好；W(x):x工作好則有S(x)

W(x)例2:將下列命題用0元謂詞符號化.(1)2是素?cái)?shù)且是偶數(shù).(2)如果2大于3,則2大于4.(3)如果張明比李民高,李民比趙亮高,則張明比趙亮高.第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)解:(1)設(shè)F(x):x是素?cái)?shù).G(x):x是偶數(shù).

則命題符號化為：F(2)∧G(2)

(2)設(shè)L(x,y)：x大于y.

則命題符號化為：L(2,3)

L(2,4)(3)設(shè)H(x,y):x比y高.a:張明b:李民c：趙亮則命題符號化為：H(a,b)∧H(b,c)

H(a,c)第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)在命題函數(shù)中，客體變元的取值范圍稱為個(gè)體域，又稱之為論域。個(gè)體域可以是有限事物的集合，也可以是無限事物的集合。全總個(gè)體域：宇宙間一切事物組成的個(gè)體域稱為全總個(gè)體域。第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)2.1.2量詞(Quantifiers)量詞：分為全稱量詞()和存在量詞()1.全稱量詞(TheUniversalQuantifiers)對日常語言中的“一切”、“所有”、“凡”、“每一個(gè)”、“任意”等詞，用符號“

”表示，

x表示對個(gè)體域里的所有個(gè)體，

xＦ(x)表示個(gè)體域里的所有個(gè)體具有性質(zhì)F.符號“

”稱為全稱量詞.第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)例3：在謂詞邏輯中將下列命題符號化.（1）凡是人都呼吸。（2）每個(gè)學(xué)生都要參加考試。

(3)任何整數(shù)或是正的或是負(fù)的。解:(1)當(dāng)個(gè)體域?yàn)槿祟惣蠒r(shí)：令F(x):x呼吸。則（1）符號化為

xF(x)

當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)：令M(x):x是人。則（1）符號化為

x(M(x)

F(x)).第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)(2)當(dāng)個(gè)體域?yàn)槿w學(xué)生的集合時(shí)：令P(x):x要參加考試。則（2）符號化為

x

P(x)

當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)：令S(x):x是學(xué)生。則（2）符號化為

x(S(x)

P(x)).第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)(3)當(dāng)個(gè)體域?yàn)槿w整數(shù)的集合時(shí)：令P(x):x是正的。N(x):x是負(fù)的。則（3）符號化為

x(P(x)∨N(x))

當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)：令I(lǐng)(x):x是整數(shù)。則（3）符號化為

x(I(x)(P(x)∨N(x))).

第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)2.存在量詞(TheExistentialQuantifiers)對日常語言中的“有一個(gè)”、“有的”、“存在著”、“至少有一個(gè)”、“存在一些”等詞，用符號“

”表示，

x表示存在個(gè)體域里的個(gè)體，

xＦ(x)表示存在個(gè)體域里的個(gè)體具有性質(zhì)F.符號“

”稱為存在量詞.例4：在謂詞邏輯中將下列命題符號化.

（1）一些數(shù)是有理數(shù)。（2）有些人活百歲以上。第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)解:(1)令Q(x):x是有理數(shù)。則（1）符號化為

x

Q(x)

（2）當(dāng)個(gè)體域?yàn)槿祟惣蠒r(shí)：令G(x):x活百歲以上。則（2）符號化為

x

G(x)

當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)：令M(x):x是人。則（2）符號化為

x(M(x)

∧

G(x))

第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)有時(shí)需要同時(shí)使用多個(gè)量詞。例5.

命題“對任意的x,存在y,使得x+y=5”,取個(gè)體域?yàn)閷?shí)數(shù)集合,則該命題符號化為:

x

y

H(x,y).其中H(x,y):x+y=5.這是個(gè)真命題.第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)3.使用量詞時(shí)應(yīng)注意的問題（1）在不同的個(gè)體域，同一命題的符號化形式可能相同也可能不同。（2）在不同的個(gè)體域，同一命題的真值可能相同也可能不同。(如,R(x)表示x為大學(xué)生。如果個(gè)體域?yàn)榇髮W(xué)里的某個(gè)班級的學(xué)生，則

x

R(x)為真；若個(gè)體域?yàn)橹袑W(xué)里的某個(gè)班級的學(xué)生，則

x

R(x)為假).第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)（3）約定以后如不指定個(gè)體域，默認(rèn)為全總個(gè)體域。對每個(gè)客體變元的變化范圍,用特性謂詞加以限制.特性謂詞:限定客體變元變化范圍的謂詞(如例3中的M(x)).一般而言，對全稱量詞，特性謂詞常作蘊(yùn)含的前件，如（

x）(M(x)

F(x))；對存在量詞，特性謂詞常作合取項(xiàng)，如(x)(M(x)∧G(x)).第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)(4)一般來說，當(dāng)多個(gè)量詞同時(shí)出現(xiàn)時(shí)，它們的順序不能隨意調(diào)換。如：在實(shí)數(shù)域上用H(x,y)表示x+y=5,則命題“對于任意的x,都存在y使得x+y=5”可符號化為：x

yH(x,y),其真值為1.若調(diào)換量詞順序后為：y

xH(x,y)

,其真值為0。(5)當(dāng)個(gè)體域?yàn)橛邢藜蠒r(shí),如D={a1,a2…,an},對任意謂詞A(x),有第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)

(x)A(x)

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

)

(x)A(x)

A(a1)∨A(a2)∨…∨A(an)例6：在謂詞邏輯中將下列命題符號化.（1）所有的人都長頭發(fā)。（2）有的人吸煙。（3）沒有人登上過木星。（4）清華大學(xué)的學(xué)生未必都是高素質(zhì)的。解：令M(x):x是人。（特性謂詞）（1）令F(x):x長頭發(fā)。則符號化為：（x）(M(x)

F(x))

第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)（2）令S(x):x吸煙。則符號化為：（x）(M(x)∧S(x))（3）令D(x):x登上過木星。則符號化為：

┐(

x)(M(x)∧D(x))（4）令Q(x):x是清華大學(xué)的學(xué)生。H(x):x是高素質(zhì)的。則符號化為：

┐(

x)(Q(x)

H(x))第二章謂詞邏輯（PredicateLogic）

2.1謂詞的概念與表示(PredicateandItsExpression)小結(jié):本節(jié)將原子命題進(jìn)行分解,分為客體和謂詞兩部分.進(jìn)而介紹了客體和謂詞、一元謂詞和n元謂詞、命題函數(shù)、全稱量詞和存在量詞等概念。重點(diǎn)掌握一元謂詞和n元謂詞的概念、全稱量詞和存在量詞及量化命題的符號化。作業(yè):1.預(yù)習(xí)第二章§2.2,§2.3第二章謂詞邏輯（PredicateLogic）

2.2謂詞公式與翻譯(Predicateformulae)2.2謂詞公式與翻譯(Predicateformulae)

n元謂詞A(x1,x2,...,xn)

稱為謂詞演算的原子公式。定義2.2.1謂詞演算的合式公式,可由下述各條組成:（1）原子公式是合式公式。（2）若A

是合式公式，則(┐A)也是合式公式。（3）若A，B是合式公式，則(A∧B)，(A∨B)，

(A

B)，(A

B)也是合式公式。（4）若A是合式公式，x是A中出現(xiàn)的任何變元,則(x)A,(

x)A，也是合式公式。

(5)只有有限次應(yīng)用(1)~(4)得到的公式是合式公式.第二章謂詞邏輯（PredicateLogic）

2.2謂詞公式與翻譯(Predicateformulae)例1：在謂詞邏輯中將下列命題符號化.（1）凡正數(shù)都大于零。（2）存在小于2的素?cái)?shù)。（3）沒有不能表示成分?jǐn)?shù)的有理數(shù)。（4）并不是所有參加考試的人都能取得好成績。解：（1）令F(x):x是正數(shù)。M(x):x大于零。則符號化為：（x）(F(x)M(x))第二章謂詞邏輯（PredicateLogic）

2.2謂詞公式與翻譯(Predicateformulae)（2）令E(x):x小于2。S(x):x是素?cái)?shù)。則符號化為：

（x)(E(x)∧S(x))

真值為0。（3）令D(x):x是有理數(shù)。F(x):x能表示成分?jǐn)?shù)。則符號化為：(x)(D(x)

F(x))

或

┐(x)(D(x)∧┐F(x))

真值為１。（4）令M(x)：x是人.Q(x):x參加考試。H(x):x取得好成績。則符號化為：

┐(x)(M(x)∧Q(x)H(x))

或

(x)(M(x)∧Q(x)∧┐H(x))第二章謂詞邏輯（PredicateLogic）

2.2謂詞公式與翻譯(Predicateformulae)例2：在謂詞邏輯中將下列命題符號化.

（1）所有運(yùn)動(dòng)員都?xì)J佩某些教練.（2）有些運(yùn)動(dòng)員不欽佩教練.設(shè)：L(x):x是運(yùn)動(dòng)員J(y):y是教練

A(x,y):x欽佩y(1)(x)(L(x)

（y)(J(y)∧A(x,y)))(2)(x)(L(x)

∧(y)(J(y)

┐A(x,y)))第二章謂詞邏輯（PredicateLogic）

2.2謂詞公式與翻譯(Predicateformulae)例3：在謂詞邏輯中將下列命題符號化.

（1）那位戴眼鏡的用功的大學(xué)生在看這本大而厚的巨著.（2）取個(gè)體域?yàn)閷?shí)數(shù)集R,函數(shù)f在a點(diǎn)連續(xù)的定義是：f在a點(diǎn)連續(xù)當(dāng)且僅當(dāng)對每個(gè)ε＞０,存在一個(gè)δ＞０，使得對所有x,若│x-

a│<δ,則│f(x)–

f(a)│<ε.第二章謂詞邏輯（PredicateLogic）

2.2謂詞公式與翻譯(Predicateformulae)例3：解:(1)設(shè)：S(x):x是大學(xué)生.A(x):x戴眼鏡.

B(x):x用功.D(x):x是巨著.F(x,y):x看y.

E(y):y是大的.G(y):y是厚的.a:那位b:這本(1)符號化為:A(a)∧B(a)∧S(a)∧D(b)∧E(b)∧G(b)∧F(a,b)第二章謂詞邏輯（PredicateLogic）

2.2謂詞公式與翻譯(Predicateformulae)（2）設(shè)：P(x,y):x在y連續(xù).Q(x,y):x大于y.(2)符號化為:

P(f,a)(ε)(Q(ε,0)

((

δ)

Q(δ,0)∧(x)(Q(δ,)

Q(ε,))))

P(f,a)(ε)(

δ)(x)(Q(ε,0)

(Q(δ,0)∧(Q(δ,)

Q(ε,)))).

第二章謂詞邏輯（PredicateLogic）

2.2謂詞公式與翻譯(Predicateformulae)小結(jié)：本節(jié)介紹了謂詞合式公式的概念，重點(diǎn)掌握謂詞公式的翻譯.第二章謂詞邏輯（PredicateLogic）

2.3變元的約束(Boundofvariable)2.3變元的約束(Boundofvariable)第二章謂詞邏輯（PredicateLogic）

2.3變元的約束(Boundofvariable)定義2.3.1:在謂詞公式中,形如(x)P(x)和(

x)P(x)的部分,稱為謂詞公式的x約束部分.

(

x)P(x)或(

x)P(x)中的x叫做量詞的指導(dǎo)變元或作用變元，P(x)稱為相應(yīng)量詞的作用域或轄域。第二章謂詞邏輯（PredicateLogic）

2.3變元的約束(Boundofvariable)在

x和

x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，相應(yīng)的x稱為約束變元;P(x)中除約束變元以外出現(xiàn)的變元稱為是自由變元。例1：1、x(H(x,y)y(W(y)

∧L(x,y,z)))2、x(H(x)W(y))

y(

F(x)∧L(x,y,z))第二章謂詞邏輯（PredicateLogic）

2.3變元的約束(Boundofvariable)說明:(1)n元謂詞公式A(x1，x2,...,xn)

中有n個(gè)自由變元,若對其中的k(k≤n)個(gè)進(jìn)行約束,則構(gòu)成了n-k元謂詞;如果一個(gè)公式中沒有自由變元出現(xiàn),則該公式就變成了一個(gè)命題(2)一個(gè)公式的約束變元所使用的名稱符號是無關(guān)緊要的,如(x)M(x)與(y)M(y)意義相同.第二章謂詞邏輯（PredicateLogic）

2.3變元的約束(Boundofvariable)在例1中,一個(gè)變元在同一個(gè)公式中既是自由出現(xiàn)又是約束出現(xiàn),這樣在理解上容易發(fā)生混淆.為了避免這種混亂,可對約束變元進(jìn)行換名.換名規(guī)則:(對約束變元而言）對約束變元進(jìn)行換名,使得一個(gè)變元在一個(gè)公式中只呈一種形式出現(xiàn).第二章謂詞邏輯（PredicateLogic）

2.3變元的約束(Boundofvariable)(1)約束變元可以換名,其更改的變元名稱范圍是量詞中的指導(dǎo)變元以及該量詞作用域中所出現(xiàn)的該變元,公式的其余部分不變.(2)換名時(shí)一定要更改為作用域中沒有出現(xiàn)的變元名稱.第二章謂詞邏輯（PredicateLogic）

2.3變元的約束(Boundofvariable)例1:

x(P(x)R(x,y))∧L(x,y)換名為

t(P(t)R(t,y))∧L(x,y)

x(H(x,y)y(W(y)∧L(x,y,z)))換名為

x(H(x,y)s(W(s)∧L(x,s,z)))第二章謂詞邏輯（PredicateLogic）

2.3變元的約束(Boundofvariable)代入規(guī)則（對自由變元而言）對公式中自由變元的更改稱為代入(1)對于謂詞公式中的自由變元可以作代入,代入時(shí)需要對公式中出現(xiàn)該自由變元的每一處進(jìn)行;(2)用以代入的變元與原公式中所有變元的名稱不能相同.例如對例1中的公式

x(P(x)R(x,y))∧L(x,y)自由變元y用z來代入,得

x(P(x)R(x,z))∧L(x,z)第二章謂詞邏輯（PredicateLogic）

2.3變元的約束(Boundofvariable)小結(jié)：本節(jié)介紹了約束變元、自由變元的概念，重點(diǎn)掌握約束變元的換名與自由變元的代入.第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式2.4謂詞演算的等價(jià)式與蘊(yùn)含式(Equivalences&implicationsofpredicatecalculus)2.4.1謂詞公式的賦值2.4.2謂詞公式的分類2.4.3謂詞演算的等價(jià)式2.4.4謂詞演算的蘊(yùn)含式第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式2.4.1謂詞公式的賦值設(shè)G是一個(gè)謂詞公式，個(gè)體域?yàn)?/p>

E，G的個(gè)體變元符號、命題變元符號、函數(shù)符號、謂詞符號按下列規(guī)則進(jìn)行的一組指派稱為

G的一個(gè)賦值或解釋。（1）每一個(gè)個(gè)體變元符號指定

的一個(gè)元素。（2）每一個(gè)命題變元符號指定一個(gè)確定的命題。（3）每一

n元函數(shù)符號指定一個(gè)函數(shù)。（4）每一n元謂詞符號指定一個(gè)謂詞。第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式設(shè)給出以下兩個(gè)公式試判斷公式的真值。：，，，第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式解:第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式例設(shè)個(gè)體域

為{0，1，2}，試消去下列公式中的量詞：第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式定義:給定任意的謂詞公式A,其個(gè)體域?yàn)镋,對于A的所有賦值,公式A都為真,則稱A在E上是永真的(或有效的);若對于A的所有賦值,公式A都為假,則稱A在E上是永假的(或不可滿足的);若至少存在著一種賦值使得公式A為真,則稱A在E上是可滿足的.第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式定義:給定任何兩個(gè)謂詞公式A

、B，設(shè)它們有共同的個(gè)體域E，若對A和B的任一組變元進(jìn)行賦值，所得命題的真值相同，則稱謂詞公式A和B在E上等價(jià)，并記為A

B第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式1、命題公式的推廣在命題公式中成立的式子，用謂詞公式去代換其中相應(yīng)的命題變元，得到的公式依然成立如：

x(P(x)Q(x))

x(┐P(x)∨Q(x))┐P(x)∨┐Q(x)

┐（P(x)∧Q(x)）等2、量詞與┐之間的關(guān)系

┐(

x)P(x)

(

x)┐P(x)

┐(

x)P(x)

(

x)┐P(x)第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式3、量詞轄域的擴(kuò)張與收縮量詞轄域中如果有合取或析取項(xiàng)，且其中有一個(gè)是命題，則可將該命題移至量詞轄域之外。如：（x）（A(x)∨B）

（x）A(x)∨B（x）（A(x)∧B）

（

x）A(x)∧B（x）（A(x)∨B）

（x）A(x)∨B（x）（A(x)∧B）

（x）A(x)∧B第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式量詞轄域的擴(kuò)張（

xA(x)B）

(x)(A(x)

B）

((x)A(x)B)

(

x)(A(x)B）

(B(x)A(x))

(x)(B

A(x))(B(x)A(x))

(x)(B

A(x))

第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式4、量詞分配等值式設(shè)A(x)、B(x)是任意的含自由出現(xiàn)個(gè)體變元x的公式，則(1)x(A(x)∧B(x))x

A(x)∧x

B(x)(2)x(A(x)∨B(x))

x

A(x)∨

x

B(x)(3)x(A(x)∨B(x))x

A(x)∨x

B(x)(4)x(A(x)∧B(x))x

A(x)∧x

B(x)5.謂詞演算蘊(yùn)含式

xA(x)∨xB(x)

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

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

A(x)∧xB(x)

6.多個(gè)量詞的使用

多個(gè)量詞同時(shí)出現(xiàn)時(shí),其順序是至關(guān)重要的.第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式

設(shè)P(x)：x今天來上課，個(gè)體域?yàn)橛?jì)算機(jī)系2008級全體同學(xué)的集合。則：1.(x)P(x)表示所有同學(xué)今天都來上課了；┐(x)P(x)表示不是所有的同學(xué)今天來上課了；

(x)┐P(x)表示今天有同學(xué)沒來上課。所以┐(x)P(x)

(x)┐P(x)2.類似地┐(x)P(x)

(x)┐P(x)1.設(shè)G(x)：x勤奮學(xué)習(xí)；H(x)：x喜歡體育活動(dòng)。其中：個(gè)體域是大學(xué)里的學(xué)生。則(x)(G(x)∧H(x))表示：大學(xué)里的所有學(xué)生即勤奮學(xué)習(xí)又喜歡體育活動(dòng)”；

(x)G(x)∧(x)H(x)表示：

“大學(xué)里的所有學(xué)生都勤奮學(xué)習(xí)且大學(xué)里所有的學(xué)生都喜歡體育活動(dòng)”。

兩者意義是相同的。即有(x)(G(x)∧H(x))

(x)G(x)∧(x)H(x)。2.設(shè)G(x)：x勤奮學(xué)習(xí)；H(x)：x喜歡體育活動(dòng)。其中：個(gè)體域是大學(xué)里的學(xué)生。則(x)(G(x)∨H(x))表示：“大學(xué)里有些學(xué)生勤奮學(xué)習(xí)或喜歡體育活動(dòng)”；

(x)G(x)∨(x)H(x)表示：

“大學(xué)里有些學(xué)生勤奮學(xué)習(xí)或大學(xué)里有些學(xué)生喜歡體育活動(dòng)”。

兩者意義是相同的。所以,(x)(G(x)∨H(x))

(x)G(x)∨(x)H(x)謂詞合式公式難點(diǎn)3命題邏輯與謂詞邏輯中的公式及其解釋的不同1掌握并能夠靈活運(yùn)用謂詞，個(gè)體詞和量詞；2注意量詞的作用域。通過緊跟量詞后面的是否為括號進(jìn)行判定；謂詞合式公式的應(yīng)用利用謂詞之間的等價(jià)關(guān)系證明下列公式之間的關(guān)系：(

x)P(x)→Q(x)

(

y)(P(y)→Q(x))證明

(

x)P(x)→Q(x)

┐(

x)P(x)∨Q(x)

(

x)┐P(x)∨Q(x)

(

y)┐P(y)∨Q(x)

(

y)(┐P(y)∨Q(x))

(

y)(P(y)→Q(x))判斷((

x)P(x)→Q(x))→((

x)P(x)→(

x)Q(x))是否為一個(gè)有效公式。解設(shè)個(gè)體域D={2,4,6,8}，

P(x)

：x能被2整除；Q(x)：x能被4整除?？芍?

x)P(x)真值為真，(

x)Q(x)真值為假。1）自由變元x=4

原式真值=（1→Q(4))→（1→0）=0

故

((

x)P(x)→Q(4))→((

x)P(x)→(

x)Q(x))的真值為假。所以原式不是有效公式。

2）自由變元x=6原式真值=（1→Q(6)）→（1→0）=1故((

x)P(x)→Q(6))→((

x)P(x)→(

x)Q(x))的真值為真。綜上所述，個(gè)體域中有些個(gè)體使原式的真值為真，有些個(gè)體使原式的真值為假，因此，該公式只能是一個(gè)可滿足公式。第二章謂詞邏輯（PredicateLogic）

2.4謂詞演算的等價(jià)式與蘊(yùn)含式小結(jié)：本節(jié)介紹了謂詞公式的概念及謂詞演算的等價(jià)式與蘊(yùn)涵式，重點(diǎn)掌握謂詞演算的等價(jià)式與蘊(yùn)涵式第二章謂詞邏輯（PredicateLogic）

2.5謂詞公式范式(PrenexNormalForm)2.5謂詞公式范式(Prenexnormalform)2.5.1前束范式(Prenexnormalform)

2.5.2前束析取范式和前束合取范式(Prenexdisjunctivenormalform&Prenexconjunctivenormalform)

第二章謂詞邏輯（PredicateLogic）

2.5謂詞公式范式(PrenexNormalForm)2.5.1前束范式(Prenexnormalform)

定義2.5.1:任何一個(gè)謂詞公式A，如果具有如下形式：

(□x1)(□x2)…(□xn)B其中□可能是量詞或量詞，xi（i=1,…,n）是客體變元，B是不含量詞的謂詞公式，則稱A是前束范式。說明:前束范式的量詞均在全式的開頭,它們的作用域延伸到整個(gè)公式的末尾。例1:

x

y((F(x)∧G(y))∧┐H(x,y))

√

x

y(F(x,y)∧G(y,z))∨x

H(x,y,z)×第二章謂詞邏輯（PredicateLogic）

2.5謂詞公式范式(PrenexNormalForm)定理2.5.1:任何一個(gè)謂詞公式,均和一個(gè)前束范式等價(jià)。前束范式的求法：第一步：否定深入。即利用量詞轉(zhuǎn)化公式，把否定聯(lián)結(jié)詞深入到命題變元和謂詞填式的前面。第二步：改名。即利用換名規(guī)則、代入規(guī)則更換一些變元的名稱，以便消除混亂。第三步：量詞前移。即利用量詞轄域的收縮與擴(kuò)張把量詞移到前面。這樣便可求出與公式等價(jià)的前束范式。第二章謂詞邏輯（PredicateLogic）

2.5謂詞公式范式(PrenexNormalForm)例2:求下列公式的前束范式。第二章謂詞邏輯（PredicateLogic）

2.5謂詞公式范式(PrenexNormalForm)解:第二章謂詞邏輯（PredicateLogic）

2.5謂詞公式范式(PrenexNormalForm)

第二章謂詞邏輯（PredicateLogic）

2.5謂詞公式范式(PrenexNormalForm)2.5.2前束析取范式和前束合取范式(Prenexdisjunctivenormalform&Prenexconjunctivenormalform)

在前束范式的基礎(chǔ)上,可以定義前束析(合)取范式.定義2.6.2:任何一個(gè)謂詞公式A，如果具有如下形式則稱為前束合取范式：

(□x1)(□x2)…(□xn)[(A11∨A12∨…∨A1k1)∧

(A21∨A22∨…∨A2k2)∧…∧(Am1∨Am2∨…∨Amkm)]

其中n大于等于1,Aij(j=1,…,ki,i=1,2,3,…,m)為原子謂詞公式或其否定,□為量詞或量詞，xi（i=1,…,n）為客體變元.第二章謂詞邏輯（PredicateLogic）

2.5謂詞公式范式(PrenexNormalForm)任何一個(gè)謂詞公式A，如果具有如下形式則稱為前束析取范式：

(□x1)(□x2)…(□xn)[(A11∧A12∧…∧A1k1)∨(A21∧A22∧…∧A2k2)∨…∨(Am1∧Am2∧…∧Amkm)]

其中n大于等于1,Aij(j=1,…,ki,i=1,2,3,…,m)為原子謂詞公式或其否定,□為量詞或量詞，xi（i=1,…,n）為客體變元.定理2.6.2:每一個(gè)謂詞公式都可以轉(zhuǎn)化為與其等價(jià)的前束析(合)取范式.求

((

x)(

y)P(a,x,y)

(

x)(

(

y)Q(y,b)

R(x)))的前束范式。

解

（1）消去聯(lián)結(jié)詞“

”、“

”，得：

(

(

x)(

y)P(a,x,y)

(

x)(

(

y)Q(y,b)

R(x)))（2）

內(nèi)移，得：

(

x)(

y)P(a,x,y)

(

x)((

y)Q(y,b)

R(x))

=(

x)(

y)P(a,x,y)

(

x)((

y)

Q(y,b)

R(x))（3）量詞左移，得：

(

x)((

y)P(a,x,y)

(

y)

Q(y,b)

R(x))=(

x)((

y)P(a,x,y)

(

z)

Q(z,b)

R(x))=(

x)(

y)(

z)(P(a,x,y)

Q(z,b)

R(x))=(

x)(

y)(

z)S(a,b,x,y,z)即：(

x)(

y)(

z)S(a,b,x,y,z)為原式的前束范式第二章謂詞邏輯（PredicateLogic）

2.5謂詞公式范式(PrenexNormalForm)小結(jié)：本節(jié)介紹了謂詞公式的前束范式、前束析取范式和前束合取范式.重點(diǎn)掌握前束析取范式和前束合取范式求法。第二章謂詞邏輯（PredicateLogic）

2.6謂詞演算的推理理論2.6謂詞演算的推理理論(Inferencetheoryofpredicatecalculus)在謂詞演算中，推理的形式結(jié)構(gòu)仍為

H1

H2

H3

....

Hn

C若H1

H2

H3

....

Hn

C是永真式，則稱由前提H1,H2,H3,....,Hn邏輯的推出結(jié)論C，但在謂詞邏輯中,H1,H2,H3,....,Hn,C均為謂詞公式。命題演算中的推理規(guī)則，可在謂詞推理理論中用。第二章謂詞邏輯（PredicateLogic）

2.6謂詞演算的推理理論與量詞有關(guān)的四條重要推理規(guī)則：1、全稱指定規(guī)則（US規(guī)則）2、全稱推廣規(guī)則（UG規(guī)則）3、存在指定規(guī)則（ES規(guī)則）4、存在推廣規(guī)則（EG規(guī)則）注意：只能對前束范式適用上述規(guī)則。第二章謂詞邏輯（PredicateLogic）

2.6謂詞演算的推理理論1.全稱指定規(guī)則（US

）：

x

P(x)

∴P(c)使用此規(guī)則時(shí)要注意：

c是論域中的某個(gè)任意的客體.

第二章謂詞邏輯（PredicateLogic）

2.6謂詞演算的推理理論2.全稱推廣規(guī)則（UG）：

P(y)

∴x

P(x)使用此規(guī)則時(shí)注意:(1)y在P(y)中自由出現(xiàn)，且y取任何值時(shí)P均為真。

(2)x不在P(y)中約束出現(xiàn).

第二章謂詞邏輯（PredicateLogic）

2.6謂詞演算的推理理論第二章謂詞邏輯（PredicateLogic）

2.6謂詞演算的推理理論3.存在指定規(guī)則(ES):

x

P(x)∴P(c)注:c是論域中的某些客體,c并不是任意的使用此規(guī)則時(shí)應(yīng)注意：

c是使P為真的特定客體；第二章謂詞邏輯（PredicateLogic）

2.6謂詞演算的推理理論

(4)存在推廣規(guī)則(EG):

P(c)∴

x

P(x)使用此規(guī)則時(shí)注意:(1)c是個(gè)體域中某個(gè)確定的個(gè)體。

(2)代替c的x不能已在P(c)中出現(xiàn)。第二章謂詞邏輯（PredicateLogic）

2.6謂詞演算的推理理論例1證明蘇格拉底三段論:凡是人都是要死的。蘇格拉底是人。蘇格拉底是要死的。設(shè)：M(x):x是人。D(x):x是要死的。a:蘇格拉底。則前提：

x(M(x)D(x))，M(a).

結(jié)論：D(a).證明：①x(M(x)D(x))P②M(a)D(a)US①③M(a)P④D(a)T②③I11

(直接證法)第二章謂詞邏輯（PredicateLogic）

2.6謂詞演算的推理理論

例2:前提：

x(F(x)∨G(x))，┐

x

G(x).

結(jié)論：x

F(x).證明：①┐

x

G(x)P②x

┐G(x)T①置換規(guī)則③┐G(a)US②④x(F(x)∨G(x))P⑤F(a)∨G(a)US④⑥F(a)T③⑤⑦x

F(x)

EG⑥第二章謂詞邏輯（PredicateLogic）

2.6謂詞演算的推理理論例3:前提：

x(A(x)B(x))，

x

A(x)

結(jié)論：x

B(x)證明：①

xA(x)P前提引入②A(c)ES①③

x(A(x)B(x))P前提引入④A(c)B(c)US③⑤B(c)T②④⑥

x

B(x)EG⑤注意：①③引入的順序不可更改！第二章謂詞邏輯（PredicateLogic）

2.6謂詞演算的推理理論例4:前提：

x(F(x)∨G(x)),x(┐R(x)∨┐G(x)),x

R(x).

結(jié)論：x

F(x)

.(歸謬法)證明(1)

┐

x

F(x)P結(jié)論否定引入

(2)x

┐F(x)T(1)E(3)┐F(a)ES(2)(4)x(F(x)∨G(x))P(5)F(a)∨G(a)US(4)(6)G(a)T(3)(5)I第二章謂詞邏輯（PredicateLogic）

2.6謂詞演算的推理理論

(7)x(┐R(x)∨┐G(x))P(8)┐R(a)∨┐G(a))US(7)(9)┐R(a)T(6)(8)I(10)x

R(x)P(11)R(a)US(10)(12)┐R(a)∧R(a)矛盾式謂詞演算的綜合推理方法（1）推導(dǎo)過程中可以引用命題演算中的規(guī)則P和規(guī)則T

。（2）如果結(jié)論是以條件的形式(或析取形式)給出，我們還可以使用規(guī)則CP。（3）若需消去量詞，可以引用規(guī)則US和規(guī)則ES。（4）當(dāng)所要求的結(jié)論可能被定量時(shí)，此時(shí)可引用規(guī)則UG和規(guī)則EG將其量詞加入。謂詞演算的綜合推理方法（續(xù)）（5）證明時(shí)可采用如命題演算中的直接證明方法和間接證明方法。（6）在推導(dǎo)過程中，對消去量詞的公式或公式中不含量詞的子公式，完全可以引用命題演算中的基本等價(jià)公式和基本蘊(yùn)涵公式。（7）在推導(dǎo)過程中，對含有量詞的公式可以引用謂詞中的基本等價(jià)公式和基本蘊(yùn)涵公式。證明：1)(

x)(P(x)∧Q(x)) P 2)(P(c)∧Q(c)) ES,1) 3)P(c) T,2),I 4)Q(c) T,2),I 5)(

x)P(x) EG,3) 6)(

x)Q(x) EG,4) 7)(

x)P(x)∧(

x)Q(x) T,5),6),I證明：(

x)(P(x)∧Q(x))(

x)P(x)∧(

x)Q(x)1)(

x)P(x)∧(

x)Q(x) P2)(

x)P(x) T,1),I3)P(c) ES,2)4)(

x)Q(x) T,1),I5)Q(c) ES,4)6)(P(c)∧Q(c)) T,3),4),I7)(

x)(P(x)∧Q(x)) EG,6)請看上述推論的逆推導(dǎo)：正確地推導(dǎo)：1)(

x)P(x)∧(

x)Q(x) P2)(

x)P(x) T,1),I3)P(c) ES,2)4)(

x)Q(x) T,1),I5)Q(b) ES,4)6)(P(c)∧Q(b)) T,3),4),I7)(

x)(

y)(P(x)∧Q(y)) EG,6)證明(采用反證法，CP規(guī)則的方法由學(xué)生完成)：1)((x)P(x)∨(

x)Q(x)) P(附加前提)2)

(x)P(x)∧

(

x)Q(x) T,1),E3)(x)P(x)

T,2),I4)(

x)Q(x) T,2),I5)(

x)P(x) T,3),E6)P(c) ES,5)證明(x)(P(x)∨Q(x))(x)P(x)∨(

x)Q(x)7)(x)Q(x)

T,4),E8)Q(c)

US,7)9)P(c)∧Q(c)

T,6),8),I10)(P(c)∨Q(c))

T,9),E11)(x)(P(x)∨Q(x))

P12)(P(c)∨Q(c))

US,11)13)(P(c)∨Q(c))∧(P(c)∨Q(c))T,10),12)謂詞邏輯推理的難點(diǎn)（1）在推導(dǎo)過程中，如既要使用規(guī)則US又要使用規(guī)則ES消去公式中的量詞，而且選用的個(gè)體是同一個(gè)符號，則必須先先使用規(guī)則ES，再使用規(guī)則US。然后再使用命題演算中的推理規(guī)則，最后使用規(guī)則UG或規(guī)則EG引入量詞，得到所要的結(jié)論。（2）如一個(gè)變量是用規(guī)則ES消去量詞，對該變量在添加量詞時(shí)，則只能使用規(guī)則EG，而不能使用規(guī)則UG；如使用規(guī)則US消去量詞，對該變量在添加量詞時(shí)，則可使用規(guī)則EG和規(guī)則UG。謂詞邏輯推理的難點(diǎn)（續(xù)）（3）如有兩個(gè)含有存在量詞的公式，當(dāng)用規(guī)則ES消去量詞時(shí)，不能選用同樣的一個(gè)常量符號來取代兩個(gè)公式中的變元，而應(yīng)用不同的常量符號來取代它們。（4）在用規(guī)則US和規(guī)則ES消去量詞時(shí)，此量詞必須位于整個(gè)公式的最前端。謂詞邏輯推理的難點(diǎn)（續(xù)）（5）在添加量詞(

x)、(

x)時(shí)，所選用的x不能在公式G(c)或G(y)中以任何約束出現(xiàn)。（6）在使用EG規(guī)則引入存在量詞(

x)，此x不得僅為G(c)或G(y)中的函數(shù)變元。在使用UG規(guī)則引入全稱量詞(

x)時(shí)，此x不得為G(y)中的函數(shù)變元(因該函數(shù)變元不得作為自由變元)。謂詞邏輯推理的應(yīng)用每個(gè)喜歡步行的人都不喜歡坐汽車；每個(gè)人或者喜歡坐汽車或者喜歡騎自行車；有的人不喜歡騎自行車。因而有的人不喜歡步行。證明設(shè)H(x)：x是人；P(x)：x喜歡坐汽車；

Q(x)：x喜歡騎自行車；R(x)：x喜歡步行。則上述語句可符號化為：(

x)(H(x)∧R(x)→P(x))，(

x)(H(x)→P(x)∨Q(x))，(

x)(H(x)∧Q(x))

(

x)(H(x)∧R(x))

(1)(

x)(H(x)∧Q(x))P(2)H(c)∧Q(c)ES，(1)

(3)H(c)T，(2)

(4)Q(c)T，(2)

(5)(

x)(H(x)→P(x)∨Q(x))P

(6)H(c)→P(c)∨Q(c)US，(5)

(7)P(c)∨Q(c)T，(3)，(6)，I

(8)P(c)T，(4)，(7)，I(9)

(

x)(H(x)∧R(x)→P(x))P(10)H(c)∧R(c)→P(c)US，(9)(11)

(H(c)∧R(c))T，(8)，(10)，I(12)H(c)∨R(c)T，(11)，E(13)R(c)T，(3)，(12)，I(14)H(c)∧R(c)T，(3)，(13)，I(15)

(

x)(H(x)∧R(x))EG，(14)證明下述論斷的正確性：所有的哺乳動(dòng)物都是脊椎動(dòng)物；并非所有的哺乳動(dòng)物都是胎生動(dòng)物；故有些脊椎動(dòng)物不是胎生的。證明

設(shè)謂詞如下：

P(x)：x是哺乳動(dòng)物；

Q(x)：x是脊椎動(dòng)物；

R(x)：x是胎生動(dòng)物。則有：

(x)(P(x)Q(x)),(x)(P(x)R(x))

(

x)(Q(x)∧R(x))請看下