離散數(shù)學(xué)及應(yīng)用（第3版）課件第三章 謂詞邏輯

第三章謂詞邏輯《離散數(shù)學(xué)及應(yīng)用》第三章謂詞邏輯蘇格拉底三段論：凡是人都是要死的。蘇格拉底是人。所以蘇格拉底是要死的。p∧q

r重言式？正確的推理？2第三章謂詞邏輯為了克服命題邏輯的局限性，引入了謂詞和量詞對原子命題和命題間的相互關(guān)系做進一步的剖析，從而產(chǎn)生了謂詞邏輯。謂詞邏輯亦稱一階邏輯，它同命題邏輯一樣，是數(shù)理邏輯中最基礎(chǔ)的內(nèi)容。原子命題是命題邏輯中最基本的組成單元，不能對它再作進一步的分解，但同時也無法反映出某些原子命題的共同特征和相互關(guān)系。3第三章謂詞邏輯§3.1謂詞與量詞§3.2謂詞公式及分類§3.3自然語句形式化§3.4謂詞邏輯的等值演算§3.5前束范式§3.6謂詞邏輯的推理4謂詞與量詞個體詞（individual）是一個命題里表示思維對象的詞，表示獨立存在的具體或抽象的客體具體的、確定的個體詞稱為個體常項，一般用

a,b,c

表示抽象的、不確定的個體詞稱為個體變項，一般用

x,y,z

表示個體變項的取值范圍稱作個體域或論域（domainofthediscourse）宇宙間一切事物組成的個體域稱作全總個體域（universaldomainofindividuals）5謂詞與量詞表示個體詞性質(zhì)或相互之間關(guān)系的詞稱作謂詞（predicate）。6謂詞與量詞如果命題里只有一個個體詞，這時表示該個體詞性質(zhì)或?qū)傩缘脑~便稱為謂詞。這是一元（目）謂詞，以

P(x),Q(x),…表示。例Human(Socrates)Mortal(Socrates)7謂詞與量詞如果在命題里的個體詞多于一個，那么表示這幾個個體詞間的關(guān)系的詞稱作謂詞。這是多元（目）謂詞，有

n

個個體的謂詞

P(x1,…,xn)稱

n元（目）謂詞，以

P(x,y),Q(x,y),R(x,y,z),…表示。例

Greater(x,y)Equal(x,y)Friend(俞伯牙,鐘子期)8謂詞與量詞準(zhǔn)確地講，謂詞

P(x),Q(x,y),…是命題形式而不是命題因為既沒有指定謂詞符號

P,Q

的含義，而且個體詞

x,y

也是個體變項而不代表某個具體的事物，從而無法確定P(x),Q(x,y)

的真值。僅當(dāng)賦予謂詞確定含義，并且個體詞取定為個體常項時，命題形式才化為命題。9謂詞與量詞世界上有黑天鵝。世界上所有天鵝都是黑色的。Black(swan)？10謂詞與量詞用來表示個體數(shù)量的詞是量詞（quantification），給謂詞加上量詞稱作謂詞的量化可看作是對個體詞所加的限制、約束的詞，但不是對數(shù)量一個、二個、三個…的具體描述，而是討論兩個最通用的數(shù)量限制詞：11謂詞與量詞全稱量詞(universalquantification)

“

”讀作“所有的x”、“任意x”或“一切x”含意相當(dāng)于自然語言中的“任意的”、“所有的”、“一切的”、“每一個”、“凡”等(

x)P(x)意指對論域

D

中的所有個體都具有性質(zhì)

P命題

(

x)P(x)

當(dāng)且僅當(dāng)對論域中的所有

x

來說，P(x)

均為真時方為真。

12謂詞與量詞例假設(shè)個體x的論域是全總個體域“一切事物都是運動的”可以形式描述為：(

x)(x是運動的)若以

P(x)

表示“x是運動的”，則可寫作(

x)(P(x))，或簡寫成(

x)P(x)或

xP(x)例

凡是人都是要死的。D={所有人}

xMortal(x)13謂詞與量詞存在量詞(existentialquantification)

“

”讀作“存在x”含意相當(dāng)于自然語言中的“某個”、“存在”、“有的”、“至少有一個”、“有些”等(

x)P(x)意指對論域

D

中至少有一個個體具有性質(zhì)

P

14謂詞與量詞例假設(shè)個體x的論域是全總個體域“有的事物是水果”可以形式描述為：(

x)(x是水果)若以

Q(x)

表示“x是水果”，則可寫作(

x)(Q(x))，或簡寫成(

x)Q(x)或

xQ(x)15謂詞與量詞注意：指定了論域且賦予謂詞確定含義時，(

x)P(x)和(

x)P(x)都是命題?！皒”不是隨意可變的了類似于16

第三章謂詞邏輯§3.1謂詞與量詞§3.2謂詞公式及分類§3.3自然語句形式化§3.4謂詞邏輯的等值演算§3.5前束范式§3.6謂詞邏輯的推理17謂詞公式及分類謂詞邏輯中的謂詞公式(wellformedformula，簡記為wff)遞歸地定義為：(1)命題常項、命題變項和原子謂詞公式（不含聯(lián)結(jié)詞的謂詞）是謂詞公式；(2)如果

A

是謂詞公式，則

~A

也是謂詞公式；(3)如果

A

和

B

是謂詞公式，則由邏輯聯(lián)結(jié)詞聯(lián)結(jié)

A

和

B

的符號串也是謂詞公式，(4)若

A

是謂詞公式，且

A

中無

x

及

x出現(xiàn)，則

(

x)A(x),

(

x)A(x)

也是謂詞公式；(5)只有有限次地應(yīng)用(1)-(4)構(gòu)成的符號串才是謂詞公式。謂詞公式也稱為合式公式，簡稱公式。18謂詞公式及分類例

p,

P(x,y)∧Q(x),

x(F(x)

G(x)),

x(A(x)

yF(x,y))

x(

x(F(x))

19謂詞公式及分類類似于命題邏輯中對命題公式進行的真值指派，可以對謂詞邏輯公式賦予不同的解釋：

20謂詞公式及分類謂詞公式的一個解釋（interpretation）由下面4部分組成：(1)非空的論域

D；(2)D

中一部分特定元素；(3)D

上一些特定的函數(shù)；(4)D

上一些特定的謂詞。21F(x)

G(x+y,2)

D

謂詞公式及分類解釋規(guī)定了相應(yīng)的個體常項、個體變項、函數(shù)符號及謂詞符號的具體意義，以及個體變項的取值范圍如果兩個解釋的四個組成部分中至少有一部分不同，則這兩個解釋是不同的一個公式可以用不同的解釋給定含義，一個解釋可以對多個不同的公式22謂詞公式及分類例

謂詞公式

(

x)P(f(x),2)解釋1：論域

D

是正整數(shù)集合2是一個特定的整數(shù)函數(shù)

f(x)=4x謂詞

P(x,y)表示

x<y那么在解釋1下該命題是假命題。23謂詞公式及分類例

謂詞公式

(

x)P(f(x),2)解釋2：論域

D

為實數(shù)集2是一個特定的實數(shù)函數(shù)

f(x)=x2謂詞

P(x,y)

表示

x=y那么在解釋2下該命題是真命題。24謂詞公式及分類類似于命題邏輯，也可以對謂詞邏輯公式進行分類：設(shè)

A

為一個謂詞公式，若

A

在任何解釋下真值均為真，則稱

A

為普遍有效的公式或邏輯有效式（logicallyvalidformula）例(

x)(P(x)∨

P(x))(

x)P(x)

P(y)25謂詞公式及分類設(shè)

A

為一個謂詞公式，若

A

在任何解釋下真值均為假，則稱

A

為不可滿足的（unsatisfiable）公式或矛盾式例(

x)(P(x)∧

P(x))(

x)P(x)∧(

y)

P(y)26謂詞公式及分類設(shè)

A

為一個謂詞公式，若至少存在一個解釋使

A

為真，則稱

A

為可滿足的（satisfiable）公式邏輯有效式一定是可滿足式；反之不然27謂詞公式及分類在命題邏輯中，一個公式是否是重言式是很容易驗證的而對于謂詞邏輯的判定問題：定理（丘奇-圖靈（Church-Turing）定理）

對任一謂詞公式而言，沒有一個可行的方法判明它是否是普遍有效的。即謂詞邏輯是不可判定的(undecidabilityoffirst-orderlogic)。但是謂詞邏輯的某些子類是可判定的28謂詞公式及分類設(shè)命題公式

A0

含命題變項

p1,p2,…,pn，用

n

個謂詞公式

A1,A2,…,An

分別處處代換

p1,p2,…,pn

，所得公式

A

稱為

A0

的代換實例。例P(y)

Q(z)，(

x)P(x)

(

x)Q(x)都是命題公式

p

q的代換實例。29謂詞公式及分類定理

命題公式中的重言式的代換實例都是邏輯有效式，在謂詞公式中可仍稱為重言式；命題公式中的矛盾式的代換實例都是矛盾式。例(1)

xP(x)

(

x

yQ(x,y)

xP(x))

p

(q

p)(2)

xP(x)

(

xP(x)∨

yG(y)) p

(p∨q)30謂詞公式及分類設(shè)

A為謂詞公式，B為

A

中的一個連續(xù)的符號串，且

B

為謂詞公式，則稱

B

為

A

的子公式（subformula）31謂詞公式及分類設(shè)

A為謂詞公式，(

x)P(x)或

(

x)P(x)為公式

A

的子公式緊跟在

、

之后的

x

稱為量詞的指導(dǎo)變項或作用變項，P(x)稱為相應(yīng)量詞的作用域或轄域（scope）在轄域中

x

的一切出現(xiàn)均稱為約束出現(xiàn)，受指導(dǎo)變項所約束所有約束出現(xiàn)的變項稱為約束變項（boundedvariable）在

A

中除了約束變項外出現(xiàn)的變項均稱為自由變項（freevariable），不受指導(dǎo)變項的約束32謂詞公式及分類

x

(

P(x,z)

y

Q(x,

y))∧

xR(x,y)33第三章謂詞邏輯§3.1謂詞與量詞§3.2謂詞公式及分類§3.3自然語句形式化§3.4謂詞邏輯的等值演算§3.5前束范式§3.6謂詞邏輯的推理34自然語句形式化基本方法是：1.

首先要將問題分解成一些原子命題和邏輯聯(lián)結(jié)符2.

之后分解出各個原子命題的個體詞、謂詞和量詞3.

按照合式公式的表示規(guī)則翻譯出自然語句35自然語句形式化

xOdd(x)

xEven(x)

x

(Even(x)∨Odd(x))

x(Even(x)∧Odd(x))

x(Even(x)∧Prime(x))

x(Prime(x)(Equal(x,2)∨Odd(x)))36論域：正整數(shù)集Greater(x,y)表示“x>y”Equal(x,y)表示“x=y”自然語句形式化

x

y(Greater(y,x)∧Prime(y))

x

y(Equal(x,y+2)∧Prime(x)∧Prime(y))

x

y

z

((Equal(z,x+y)∧Odd(x)∧Odd(y))

Even(z))3738所有的素數(shù)都是正奇數(shù)

x(Prime(x)Odd(x))而不是

x(Prime(x)∧Odd(x))一般地講，"所有的A是B”、“是A的都是B”、“一切A都是B的?！边@類語句的形式描述只能使用“

”而不能使用“∧”自然語句形式化39沒有正偶數(shù)是素數(shù)

x(Prime(x)∧Even(x))其他“等價的”寫法

x(Even(x)

Prime(x))

x

(Prime(x)

Even(x))一般地講，“有的A是B?！边@類語句的形式描述只能使用“∧”而不能使用“

”。自然語句形式化40有一個偶的正奇數(shù)

x(Even(x)∧Odd(x))有一個正偶數(shù)，也有一個正奇數(shù)

xEven(x)∧

xOdd(x)

或

x

y(Even(x)∧Odd(y))這二者是不“等價”的！自然語句形式化41所有正整數(shù)都是正偶數(shù)或者正奇數(shù)

x(Odd(x)∨Even(x))所有正整數(shù)都是正偶數(shù)，或者所有正整數(shù)都是正奇數(shù)

xOdd(x)∨

x

Even(x)這二者是不“等價”的！自然語句形式化42對于任一個正整數(shù)而言，都存在比它大的正整數(shù)

x

yGreater(y,x)

y

x

Greater(y,x)存在一個正整數(shù)，大于任何正整數(shù)這二者是不“等價”的！

X自然語句形式化自然語句形式化對于任一個正奇數(shù)而言，都存在比它大的正偶數(shù)

x(Odd(x)y(Even(y)∧Greater(y,x)))43自然語句形式化存在某個正奇數(shù)，它小于所有正偶數(shù)

x(Odd(x)∧

y

(Even(y)Greater(y,x)))4445存在唯一的偶素數(shù)“存在且唯一”

x(P(x)∧

y(P(y)Equal(x,y)))

x((Prime(x)∧Even(x))∧

y(Prime(y)∧Even(y)Equal(x,y)))自然語句形式化自然語句形式化金子一定閃光，但閃光的不一定是金子G(x)：x

是金子L(x)：x

會閃光原語句可表示成(

x)(G(x)

L(x))∧(

x)(L(x)∧~G(x))4647天下烏鴉一般黑F(x)：x是烏鴉G(x,

y)：x

與

y

一般黑

原語句可表示成(

x)(

y)(F(x)∧F(y)

G(x,

y))或者~(

x)(

y)(F(x)∧F(y)∧~G(x,

y))自然語句形式化第三章謂詞邏輯§3.1謂詞、量詞與自然語句形式化§3.2謂詞公式及分類§3.3自然語句形式化§3.4謂詞邏輯的等值演算§3.5前束范式§3.6謂詞邏輯的推理48謂詞邏輯的等值演算天下烏鴉一般黑F(x)：x是烏鴉G(x,

y)：x

與

y

一般黑

原語句可表示成(

x)(

y)(F(x)∧F(y)

G(x,

y))或者~(

x)(

y)(F(x)∧F(y)∧~G(x,

y))49謂詞邏輯的等值演算設(shè)

A,B

是兩個謂詞公式，若

A

B是普遍有效的公式，則稱

A

與

B

等值，記作

A

B

。類似于命題邏輯，兩個謂詞公式

A,B

等值當(dāng)且僅當(dāng)在任何解釋下，A和

B

的真值都相同。謂詞邏輯的等值演算仍是以基本等值式為基礎(chǔ)，應(yīng)用等值演算規(guī)則，逐步推演50謂詞邏輯的等值演算謂詞邏輯中的基本等值式主要分兩類：其一是從命題公式移植來的等值式，即命題邏輯中基本等值式的代換實例如(

x)F(x)

(

y)G(y)

(

x)F(x)∨(

y)G(y)另一類是謂詞邏輯所特有的等值式，與量詞有關(guān)

51謂詞邏輯的等值演算（消去量詞等值式）設(shè)論域

D={a1,a2,…,am}

是有限集合，則有(

x)A(x)

A(a1)∧A(a2)∧…∧A(am)(

x)A(x)

A(a1)∨A(a2)∨…∨A(am)52謂詞邏輯的等值演算例設(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

yF(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))53謂詞邏輯的等值演算（量詞否定等值式/德·摩根律）設(shè)

A(x)

是含

x

自由出現(xiàn)的公式，則

(

x)A(x)

(

x)

A(x)

(

x)A(x)

(

x)

A(x)54

當(dāng)

D={a1,a2,…,am}時

xA(x)

A(a1)∧A(a2)∧…∧A(am)，

xA(x)

A(a1)∨A(a2)∨…∨A(am)

~

xA(x)

~(A(a1)∧A(a2)∧…∧A(am))

~A(a1)∨~A(a2)∨…∨~A(am)

x

A(x)55謂詞邏輯的等值演算（量詞轄域收縮與擴張等值式）設(shè)

A(x)是含

x

自由出現(xiàn)的公式，謂詞公式

B

中不含

x

的出現(xiàn)，則有

x(A(x)∨B)

xA(x)∨B

x(A(x)∧B)

xA(x)∧B

x(A(x)∨B)

xA(x)∨B

x(A(x)∧B)

xA(x)∧B56（量詞分配等值式）設(shè)

A(x),B(x)是含

x

自由出現(xiàn)的謂詞公式，則有

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

xA(x)∧xB(x)

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

xA(x)∨xB(x)注意：

對∨不滿足分配律，

對∧不滿足分配律

當(dāng)

D={a1,a2,…,am}時

xA(x)

A(a1)∧A(a2)∧…∧A(am),

xA(x)

A(a1)∨A(a2)∨…∨A(am)

謂詞邏輯的等值演算謂詞邏輯的等值演算設(shè)

A(x,y)

是含

x,y

自由出現(xiàn)的謂詞公式，則有

x

yA(x,y)y

xA(x,y)

x

yA(x,y)y

xA(x,y)這組等值式表明相同量詞與排列的次序無關(guān)，但是對于不同量詞，不能隨意更換次序，即

(

x)(

y)A(x,y)與

(

y)(

x)A(x,y)不等值57謂詞邏輯的等值演算謂詞邏輯包括以下三條等值演算規(guī)則：置換規(guī)則設(shè)

(A)

是含謂詞公式

A

的公式，

(B)

是用謂詞公式

B

取代

(A)

中的

A

（不一定是每一處）之后得到的謂詞公式，若

A

B，則

(A)

(B)

。代替規(guī)則換名規(guī)則58謂詞邏輯的等值演算

x

(

P(x,z)

y

Q(x,

y))∧

xR(x,y)59

謂詞邏輯的等值演算

x

(

P(x,z)

y

Q(x,

y))∧

xR(x,y)同一個個體變項符號既有約束出現(xiàn)又有自由出現(xiàn)，容易引起概念上的混淆。為避免這種情況，引入了下面的代替規(guī)則和換名規(guī)則，使得同一個個體變項符號在一個公式中只呈現(xiàn)一種形式，要么為約束出現(xiàn)，要么為自由出現(xiàn)同時使不同的量詞所約束的個體變項不同名，便于計算機處理60謂詞邏輯的等值演算（代替規(guī)則）將謂詞公式

A

中某個自由出現(xiàn)的個體變項的所有自由出現(xiàn)改成

A

中未曾出現(xiàn)的某個個體變項符號，其余部分不變，記所得謂詞公式為

A

，則

A

A

61謂詞邏輯的等值演算（換名規(guī)則）將謂詞公式

A

中某量詞的指導(dǎo)變項及其在轄域內(nèi)的所有約束出現(xiàn)改成該量詞轄域內(nèi)未曾出現(xiàn)的某個個體變項符號，其余部分不變，記所得謂詞公式為

A

，則A

A

62謂詞邏輯的等值演算換名規(guī)則

xφ(x,x1,

x2,

…,

xn)

y

φ(y,x1,

x2,

…,

xn)

xφ(x,x1,

x2,

…,

xn)

y

φ(y,x1,

x2,

…,

xn)其中

y

{x1,

x2,

…,

xn}6364謂詞邏輯的等值演算

x

(

P(x,y)

yQ(x,z))∧

xR(x,y)

u

(

P(u,y)

yQ(u,z))∧

xR(x,y)

x(

P(x,y)

yQ(x,z))∧

v

R(v,y)

謂詞邏輯的等值演算例將公式

(

x)F(x,y,z)

(

y)G(x,y,z)

化為與之等值的公式，使其沒有既是約束出現(xiàn)又是自由出現(xiàn)的個體變項符號解(

x)F(x,y,z)

(

y)G(x,y,z)

(

u)F(u,y,z)

(

y)G(x,y,z)

（換名規(guī)則）

(

u)F(u,y,z)

(

v)G(x,v,z)

（換名規(guī)則）或者(

x)F(x,y,z)

(

y)G(x,y,z)

(

x)F(x,u,z)

(

y)G(x,y,z)

（代替規(guī)則）

(

x)F(x,

u,

z)

(

y)G(v,

y,

z)

（代替規(guī)則）65

謂詞邏輯的等值演算

代替規(guī)則換名規(guī)則使用對象任一謂詞公式改名對象自由變項指導(dǎo)變項及其在轄域內(nèi)的所有約束出現(xiàn)改名方式對公式中出現(xiàn)的所有同名的自由變項進行改名對指導(dǎo)變項及其量詞轄域中所出現(xiàn)的約束變項處處進行改名改名限制公式中未曾出現(xiàn)的某個個體變項符號新的變項符號應(yīng)是該量詞轄域內(nèi)未曾出現(xiàn)的改名結(jié)果與原公式等值6667謂詞邏輯的等值演算例證明等值式

x(P(x)Q(x))xP(x)xQ(x)證明

x(P(x)Q(x))

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

x

P(x)∨

xQ(x)

xP(x)∨

xQ(x)

xP(x)xQ(x)謂詞邏輯的等值演算天下烏鴉一般黑F(x)：x是烏鴉G(x,

y)：x

與

y

一般黑

原語句可表示成(

x)(

y)(F(x)∧F(y)

G(x,

y))或者~(

x)(

y)(F(x)∧F(y)∧~G(x,

y))6869謂詞邏輯的等值演算

(

x)(

y)(F(x)∧F(y)∧

G(x,y))

(

x)

(

y)(F(x)∧F(y)∧

G(x,y))

(

x)(

y)

(F(x)∧F(y)∧

G(x,y))

(

x)(

y)(

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

(

x)(

y)(F(x)∧F(y)

G(x,y))謂詞邏輯的等值演算證明

x(P(x)

Q(x))是假命題的方法——由~(

x(P(x)

Q(x)))

(

x)(P(x)∧

Q(x)))則只需要找到論域D

中一個個體x0使得P(x0)同時Q(x0)為假這個過程稱作反駁（disproof）x0

稱作反例（counterexample）70第三章謂詞邏輯§3.1謂詞、量詞與自然語句形式化§3.2謂詞公式及分類§3.3自然語句形式化§3.4謂詞邏輯的等值演算§3.5前束范式§3.6謂詞邏輯的推理71前束范式設(shè)

A為一謂詞公式，如果滿足(1)所有量詞都位于該公式的最左邊；

(2)所有量詞前都不含否定詞；

(3)量詞的轄域都延伸到整個公式的末端，

則稱

A為前束范式（prenexformalform）72前束范式前束范式的一般形式為：Q1

x1

Q2

x2

Qn

xn

M(x1,x2,

,xn)其中

Qi(1

i

n)為

或

Q1

x1

Q2

x2

Qn

xn稱為前束M

為不含量詞的公式，稱作公式的基式或母式73前束范式

xP(x)∨

xQ(x)

x

y

~(P(x)

Q(y))

x

yR(x,y)R(x,y)~

xR(x,y)

x(P(x)

Q(x))∨R(z)74

前束范式化前束范式的基本方法：步驟1.

消去謂詞公式中的聯(lián)結(jié)詞

，

；步驟2.

將謂詞公式中的否定詞

右移步驟3.

將謂詞公式中的量詞左移（使用量詞分配等值式、量詞轄域收縮與擴張等值式），必要時將變項改名7576前束范式例求

((

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

(

(

x)(

y)P(a,x,y)∨(

x)(

(

y)Q(y,b)∨R(x)))步驟2.

否定連接詞右移

(

(

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

(

x)(

y)P(a,x,y)∧(

x)((

y)

Q(y,b)∧

R(x))

77前束范式步驟3.量詞左移

(

x)(

y)P(a,x,y)∧(

x)((

y)

Q(y,b)∧

R(x))

(

x)((

y)P(a,x,y)∧(

y)

Q(y,b)∧

R(x))

(

x)((

y)(

z)((P(a,x,y)∧

Q(z,b))∧

R(x))

(

x)(

y)(

z)(P(a,x,y)∧

Q(z,b)∧

R(x))

(

x)(

y)(

z)M(a,b,x,y,z)

前束范式

注

((

x)(

y)P(a,x,y)

(

x)(

(

y)Q(y,b)

R(x)))

(

x)(

y)(

z)(P(a,x,y)∧

Q(z,b)∧

R(x))

(

x)(

z)(

y)(P(a,x,y)∧

Q(z,b)∧

R(x))

(

x)(

y)(

z)(P(a,x,y)∧

Q(z,b)∧

R(x)∧T)78任一不含量詞的普遍有效的公式等值的前束范式不唯一前束范式定理（前束范式存在定理）

任一謂詞公式都存在與之等值的前束范式，但其前束范式并不唯一。79第三章謂詞邏輯§3.1謂詞、量詞與自然語句形式化§3.2謂詞公式及分類§3.3自然語句形式化§3.4謂詞邏輯的等值演算§3.5前束范式§3.6謂詞邏輯的推理80謂詞邏輯的推理從前提

H1,H2,…,Hn出發(fā)推出結(jié)論

C

的推理形式結(jié)構(gòu)，依然采用如下的蘊涵式形式：(H1∧H2∧…∧Hn)

C若上式為邏輯有效式，則稱推理正確，稱

C為前提

H1,H2,…,Hn的邏輯結(jié)論或有效結(jié)論81謂詞邏輯的推理由于在謂詞邏輯中不能使用真值表法，又不存在判別

A

B是否普遍有效的一般方法，從而使用基本推理公式及推理規(guī)則是謂詞邏輯的基本推理演算方法82謂詞邏輯的推理（基本推理公式）以下蘊含式都是普遍有效公式(

x)P(x)∨(

x)Q(x)

(

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

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

(

x)P(x)∧(

x)Q(x)(

x)(P(x)

Q(x))

((

x)P(x)

(

x)Q(x))(

x)(P(x)

Q(x))

((

x)P(x)

(

x)Q(x))(

x)(

y)P(x,y)

(

x)(

y)P(x,y)(

x)(

y)P(x,y)

(

y)(

x)P(x,y)(

x)(

y)P(x,y)

(

x)(

y)P(x,y)83謂詞邏輯的推理而所使用的推理規(guī)則除命題邏輯的推理演算中用到的幾條基本推理規(guī)則外，還包括四條有關(guān)量詞的消去和引入規(guī)則：全稱推廣規(guī)則/全稱量詞引入規(guī)則(UG)全稱舉例規(guī)則/全稱量詞消去規(guī)則(US)存在推廣規(guī)則/存在量詞引入規(guī)則(EG)

存在舉例規(guī)則/存在量詞消去規(guī)則(ES)84謂詞邏輯的推理全稱量詞消去規(guī)則：

x

P(x)

P(y)或

x

P(x)

P(a)

其中y是論域中一個體

意指如果所有的x

D都具有性質(zhì)P，那么D中任一個體y必具有性質(zhì)P該規(guī)則使用的條件是：(1)第一式中，取代x的y應(yīng)為任意的不在P(x)中約束出現(xiàn)的個體變項(2)第二式中，a為任意個體常項(3)用y或a去取代P(x)

中自由出現(xiàn)的x

時，必須在x自由出現(xiàn)的一切地方進行取代85謂詞邏輯的推理分析下述推理的正確性(1)(

x)(

y)G(x,y)

（前提引入）(2)(

y)G(y,y)

（全稱量詞消去）假定論域是整數(shù)集，謂詞G(x,y)表示“x>y”違反條件(1)，用約束變項

y取代

x86謂詞邏輯的推理全稱量詞引入規(guī)則：P(y)

(

x)P(x)，其中

y

是論域中任一個體。意指如果任一個個體

y

D

都具有性質(zhì)

P，那么D

中所有個體

x

都具有性質(zhì)

P。該規(guī)則使用的條件是：(1)無論

P(y)

中自由出現(xiàn)的個體變項

y

取何值，P(y)應(yīng)該均為真。(2)取代自由出現(xiàn)的

y

的

x

不能在

P(y)

中約束出現(xiàn)。87謂詞邏輯的推理分析下述推理的正確性(1)(

x)G(x,y)（對任意給定的y都成立）(2)(

x)(

x)G(x,x)

（全稱量詞引入）論域是整數(shù)集，謂詞G(x,y)表示“x>y”結(jié)論(2)明顯不正確違反條件(2)，用約束變項

x取代

y88謂詞邏輯的推理存在量詞引入規(guī)則：P(a)

(

x)P(x)，其中

a

是論域中一個體常項。意指如果有個體常項

a

具有性質(zhì)

P

，那么

(

x)P(x)

必真。該規(guī)則使用的條件是：(1)a是特定的個體常項(2)取代

a

的

x

不在

P(a)

中出現(xiàn)過89謂詞邏輯的推理存在量詞消去規(guī)則：(

x)P(x)

P(a)，其中

a

是論域中的一個個體常項。意指如果論域

D

中存在某個體具有性質(zhì)

P，那么必有特定個體

a

具有該性質(zhì)

P。該規(guī)則使用的條件是：(1)a

是使

P

為真的特定的個體常項(2)a

不在

P(x)

中出現(xiàn)(3)P(x)中沒有其它自由出現(xiàn)的個體變項(4)a

是在推導(dǎo)中未曾使用過的90謂詞邏輯的推理分析下述推理的正確性(1)(

x)Q(x)

（前提引入）(2)(

x)

Q(x)

（前提引入）(3)Q(a)

（對(1)的存在量詞消去）(4)

Q(a)

（對(2)的存在量詞消去）(5)Q(a)∧

Q(a)

（(3)(4)合?。?6)(

x)(Q(x)∧

Q(x))

（存在量詞引入）論域是整數(shù)集，謂詞

Q(x)

表示“x是偶數(shù)”結(jié)論(6)明顯不正確違反條件(4)，使用了在推導(dǎo)中曾使用過的

a91謂詞邏輯的推理分析下述推理的正確性(1)(

x)(

y)G(x,y) （前提引入）(2)(

y)G(x,y)

（全稱量詞消去）(3)G(x,a)

（存在量詞消去）(4)(

x)G(x,a)

（全稱量詞引入）(5)(

y)(

x)G(x,y)

（存在量詞引入）假定論域是整數(shù)集，G(x,y)表示“x>y”結(jié)論(5)不正確違反條件(3)，(

y)的轄域G(x,y)中存在自由變項

x從語義上解釋，G(x,a)成立時個體a是依賴于x

的，不是對所有的

x

對同一個

a

都有G(x,a)

成立92謂詞邏輯的推理使用推理規(guī)則的推理演算過程是：步驟1.首先將以自然語句表示的推理問題形式化，轉(zhuǎn)換為謂詞公式步驟2.若不能直接使用基本的推理公式則消去量詞步驟3.在無量詞下使用規(guī)則和公式進行推理步驟4.最后再引入量詞，得到相應(yīng)結(jié)論93謂詞邏輯的推理特別注意如下兩點： (1)在既需要消去存在量詞又需要消去全稱量詞時，一般要先使用存在量詞消去規(guī)則，再使用全稱量詞消去規(guī)則。 (2)使用US，UG，ES，EG規(guī)則時，量詞的轄域都必須延伸到整個公式的末端。

換言之，在含有多個量詞的謂詞推理中，使用消去規(guī)則應(yīng)該按照從左到右的順序，而引入規(guī)則的使用應(yīng)該按照從右到左的順序。94謂詞邏輯的推理例

分析下述推理的正確性。(1)(

x)(P(x)

Q(x))

（前提引入）(2)(

x)P(x)

（前提引入）(3)P(c)

Q(c)

（對(1)的全稱量詞消去）(4)P(c)

（對(2)的存在量詞消去）(5)Q(c)

（(3)(4)假言推理）(6)(

x)Q(x)

（存在量詞引入）解由前提“(

x)(P(x)

Q(x))”和“(

x)P(x)”得到結(jié)論“(

x)Q(x)”是一個正確推理，整個推理過程從表面上看也是正確的但是步驟(4)違反了存在量詞消去規(guī)則的使用條件(4)從語義上講，步驟(3)中的c可以為任意個體常項，不見得使P為真，因此步驟(4)不一定成立只要調(diào)換步驟(3)和步驟(4)就得到了正確的推理過程95謂詞邏輯的推理構(gòu)造下述推理的證明：前提：(

x)(G(x)∨H(x))，(

x)~G(x)

結(jié)論：(

x)H(x)證明(1)(

x)(G(x)∨H(x)) （前提引入）(2)G(a)∨H(a)

（全稱量詞消去）(3)(

x)~G(x)

（前提引入）(4)~G(a)

（全稱量詞消去）(5)H(a)

（(2)(4)析取三段論）(6)(

x)H(x)

（存在量詞引入）96謂詞邏輯的推理構(gòu)造下述各推理的證明：前提：(

x)P(x)

(

x)Q(x)

結(jié)論：(

x)(P(x)

Q(x))證明(1)(

x)P(x)

(

x)Q(x)

（前提引入）(2)(

x)(

y)(P(x)

Q(y))

（(1)置換）(3)(

y)(P(z)

Q(y))

（全稱量詞消去）(4)P(z)

Q(z)

（全稱量詞消去）(5)(

x)(P(x)

Q(x))

（全稱量詞引入）97謂詞邏輯的推理例

在謂詞邏輯中構(gòu)造下面推理的證明所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。解P(x)表示“x是人”Q(x)表示“x會死”則得到如下推理