2-7謂詞演算的推理理論推理方法：直接推理、條件論證、反證法所用公式：43頁和70頁的I1——I19，E1——E33推理規(guī)則：P、T、CP、US、ES、EG、UG后四個規(guī)則，是處理量詞的，因為推理時要使用不含量詞的命題公式，所以要去掉量詞，如果結(jié)論有量詞，還要添加量詞。下面介紹四個新規(guī)則：一.全稱指定規(guī)則

US(UniversalSpecialization)

形式：

xA(x)A(c)或xA(x)

A(y)(其中c是論域內(nèi)指定客體)

含義：如果xA(x)為真，則在論域內(nèi)任何指定客體c，都使得A(c)為真。

作用：去掉全稱量詞。條件：（1）c為任意客體常量。

（2）取代x的y應(yīng)為任意的，不在A(x)中約束出現(xiàn)的個體變量。（3）用c或y去取代A(x)中x時，一定要在x自由出現(xiàn)的一切地方進行取代。二.全稱推廣規(guī)則UG(UniversalGeneralization)

形式：A(y)xA(x)(其中y是論域內(nèi)任何指定客體)

含義：如果在論域內(nèi)任何指定客體y都使得A(y)為真，則

xA(x)為真。

作用：添加全稱量詞。

條件：(1)無論A(y)中變量y取何值，A(y)均為真。

(2)x不是A(y)中的符號。

注意：y一定是任意的客體，否則不可使用全稱推廣規(guī)則。三.存在指定規(guī)則ES(ExistentialSpecialization)

形式：

xA(x)A(c)(其中c是論域內(nèi)指定客體)

含義：如果

xA(x)為真，則在論域內(nèi)指定客體c，

都使得A(c)為真。

作用：去掉存在量詞。

條件：⑴c是使A(x)為真的特定的個體常量。⑵c不在A(x)中出現(xiàn)。

(3)若A(x)中除了x外，還有其他自由變元出現(xiàn)，此規(guī)則不能使用。

請看下面兩個例子：

例：個體域為實數(shù)集，A(x,y)為x>y，指出

x

yA(x,y)（真命題）推出

xA(x,c)（假命題）原因。⑴x

yA(x,y)P⑵yA(z,y)US⑴⑶A(z,c)ES⑵⑷xA(x,c)UG⑶第三步錯了，由于

yA(z,y)中除了y，還有自由變元z，此處不能用ES規(guī)則。四.存在推廣規(guī)則EG(ExistentialGeneralization)

形式：A(c)xA(x)(其中c是論域內(nèi)指定客體)

含義：如果在論域內(nèi)指定客體c使得

A(c)為真，則

xA(x)為真。

作用：添加存在量詞。

條件:(1)c是特定的個體常量。

(2)x不是A(c)中的符號。注意：只能對前束范式使用UG、US、EG、ES規(guī)則，就是說一定要將公式化成等價的前束范式再使用這些規(guī)則。例2.7.1

所有金屬都導(dǎo)電。銅是金屬。故銅導(dǎo)電。令M(x):x是金屬。C(x):x導(dǎo)電。a:銅。符號化為：

x(M(x)→C(x)),M(a)C(a)⑴

x(M(x)→C(x))

P

⑵M(a)→C(a)US⑴⑶M(a)P⑷C(a)T⑵⑶I11

例2.7.2

所有自然數(shù)都是整數(shù)。有些數(shù)是自然數(shù)。因此有些數(shù)是整數(shù)。令A(yù)(x)表示x是自然數(shù)，B(x)表示x是整數(shù)。

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

xA(x)

xB(x)⑴

xA(x)P⑵A(c)ES⑴⑶

x(A(x)→B(x))P⑷A(c)→B(c)US⑶⑸B(c)T⑵⑷I11⑹

xB(x)EG⑸例2中，如果按下面方法推理，是否正確？

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

xA(x)

xB(x)⑴

x(A(x)→B(x))P⑵A(c)→B(c)US⑴⑶

xA(x)P⑷A(c)ES⑶⑸B(c)T⑵⑷I11⑹

xB(x)EG⑸問題在哪里？（ES必須在US前）例題2.7.3證明：

x(C(x)→W(x)∧R(x))∧

x(C(x)∧Q(x))

x(Q(x)∧R(x))證明:(1)

x(C(x)∧Q(x))

P(2)C(a)∧Q(a)

ES(1)(3)C(a)T(2)I(4)

x(C(x)→W(x)∧R(x))P(5)

C(a)→W(a)∧R(a)US(4)(6)W(a)∧R(a)

T(3)(5)I(7)R(a)

T(6)I

(8)Q(a)T(2)I(9)Q(a)∧R(a)T(7)(8)I(10)

x(Q(x)∧R(x))EG(9)例題2.7.4證明：

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

xP(x)∨xQ(x)證明：方法1，反證法

(1)

（

xP(x)∨xQ(x)）P（附加前提）

(2)

xP(x)∧

xQ(x)

T(1)E(3)

xP(x)T(2)I(4)

x

P(x)T(3)E(5)

xQ(x)T(2)I

(6)

x

Q(x)T(5)E(7)

P(c)ES(4)(8)Q(c)ES(6)(9)P(c)∧Q(c)T(7)(8)I(10)(P(c)∨Q(c))T(9)E(11)

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

P

(12)P(c)∨Q(c)US(11)(13)

(P(c)∨Q(c))∧(P(c)∨Q(c))

T(10)(12)I矛盾方法2：因為

xP(x)∨xQ(x)

(

xP(x))∨xQ(x)

xP(x)→

xQ(x)轉(zhuǎn)化后

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

xP(x)→

xQ(x)用CP規(guī)則證：

(1)

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

x

P(x)T(1)E(3)

P(c)ES(2)(4)

x(P(x)∨Q(x))P(5)P(c)∨Q(c)

US(4)(6)Q(c)

T(3)(5)I(7)

xQ(x)EG(6)(8)

xP(x)→

xQ(x)CP推理時注意事項：1.注意使用ES、US、EG、UG的限制條件。2.推理中，對于同一個客體變元，既有帶

也有帶的前提，去量詞時，應(yīng)先去后去，這樣才可以特指同一個客體c.3.去量詞時，該量詞必須是公式的最左邊的量詞，且此量詞的前邊無任何符號，它的轄域作用到公式末尾。下面的作法是錯誤的：正確作法是：⑴

xP(x)→

yQ(y)P⑴

xP(x)→

yQ(y)P⑵xP(x)→Q(b)×ES⑴(2)xP(x)∨

yQ(y)T(1)E(3)P(a)→Q(b)×US(2)(3)

xP(x)∨

yQ(y)T(2)E

(4)xy(P(x)∨Q(y))T(3)E

(5)y(P(a)∨Q(y))ES(4)

實際上x的轄域擴

(6)P(a)∨Q(b))ES(4)充后量詞改成為

x

(7)P(a)→Q(b)T(5)E下面的作法是錯誤的：⑴

xP(x)P⑵

P(c)US⑴正確作法是：⑴

xP(x)P

(2)xP(x)T(1)E(3)

P(c)ES(2)實際上⑴中不是

x而是x4.添加量詞時，也要加在公式的最左邊，(即新加的量詞前也無任何符號?。?且其轄域作用到公式的末尾。作業(yè)：79頁⑴c)d)⑵、⑶第二章小結(jié)本章重點掌握內(nèi)容：1.各基本概念清楚。2.會命題符號化。3.熟練掌握等價公式和永真蘊涵式。4.會寫前束范式。5.熟練掌握謂詞邏輯的三種推理方法。66頁(3)b)P:2>1,Q(x):x≤3,R(x):x>5,a:5,{-2,3,6}

x(P→Q(x))∨R(a)(P→xQ(x))∨R(a)(P→(Q(-2)∧Q(3)∧Q(6)))∨R(5)(T→(T∧T∧F))∨F(T→F)∨F

F∨F

F(4)b)對約束變元換名

x(P(x)→(R(x)∨Q(x)))∧

xR(x)→

zS(x,z)

y(P(y)→(R(y)∨Q(y)))∧

tR(t)→

uS(x,u)(5)a)對自由變元代入(yA(x,y)→xB(x,z))∧

xzC(x,y,z)(yA(u,y)→xB(x,v))∧

xzC(x,w,z)(6)判斷下面推證是否正確。

x(A(x)→B(x))⑴x(

A(x)∨B(x))⑵x(A(x)∧

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

B(x))⑷(xA(x)∧

x

B(x))⑸xA(x)∨

x

B(x)⑹xA(x)∨

xB(x)⑺xA(x)→

xB(x)第⑷步錯，由⑶到⑷用的是公式：

x(A(x)∧

B(x))(xA(x)∧

x

B(x))無此公式，而是

x(A(x)∧

B(x))

xA(x)∧

x

B(x)，應(yīng)將⑷中的換成

即：

x(A(x)→B(x))⑴x(

A(x)∨B(x))⑵x(A(x)∧

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

B(x))⑷

(xA(x)∧

x

B(x))⑸xA(x)∨

x

B(x)⑹xA(x)∨

xB(x)⑺xA(x)→

xB(x)因為由公式E18P→QQ→P

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

xA(x)∧

xB(x)

，

PQ得(xA(x)∧

xB(x))

x(A(x)∧B(x))75頁(1)b)

x(

yP(x,y)→(

zQ(z)→R(x)))

x(

yP(x,y)∨(

zQ(z)∨R(x)))

x(

yP(x,y)∨(

z

Q(z)∨R(x)))

x(

yP(x,y)∨

z(

Q(z)∨R(x)))

x

y

z(P(x,y)∨(

Q(z)∨R(x)))(2)c)xP(x)→

x(zQ(x,z)∨zR(x,y,z))

xP(x)∨

x(zQ(x,z)∨zR(x,y,z))

x

P(x)∨

x(zQ(x,z)∨zR(x,y,z))

x

P(x)∨

u(zQ(u,z)∨tR(u,y,t))

x

uzt(

P(x)∨(Q(u,z)∨R(u,y,t)))

x

uzt(

P(x)∨Q(u,z)∨R(u,y,t))此式既是前束析取范式，也是前束合取范式。79頁(2)a)用CP規(guī)則證明

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

x

Q(x)因為

xP(x)∨

x

Q(x)xP(x)→

x

Q(x)⑴xP(x)P(附加前提)⑵

xP(x)T⑴E⑶P(a)ES⑵⑷x(P(x)∨Q(x)P⑸P(a)∨Q(a)US⑷⑹Q(a)T⑶⑸I⑺

x

Q(x)EG⑹⑻xP(x)→

x

Q(x)CP(3)a)所有有理數(shù)是實數(shù)，某些有理數(shù)是整數(shù)，因此某些實數(shù)是整數(shù)。設(shè)Q(x):x是有理數(shù)R(x):x是實數(shù)I(x):x是整數(shù)

x(Q(x)→R(x)),x(Q(x)∧I(x))

x(R(x)∧I(x))⑴

x(Q(x)∧I(x))P⑵Q(a)∧I(a)ES⑴⑶Q(a)T⑵I⑷I(a)T⑵I⑸x(Q(x)→R(x))P⑹Q(a)→R(a)US⑸

⑺R(a)T⑶⑹I⑻R(a)∧I(a)T⑷⑺I⑼

x(R(x)∧I(x))EG⑻b)任何人如果他喜歡步行，他就不喜歡乘汽車；每個人或者喜歡乘汽車或者喜歡騎自行車。有的人不愛騎自行車，因此有的人不愛步行。設(shè)A(x):x是人,B(x):x是喜歡步行,C(x):x喜歡乘汽車，D(x):x喜歡騎自行車

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

C(x))),x(A(x)→(C(x)∨D(x))),x(A(x)∧

D(x))

x(A(x)∧

B(x))⑴

x(A(x)∧

D(x))P⑵A(a)∧

D(a))

ES⑴⑶A(a)T⑵I⑷

D(a))T⑵I⑸x(A(x)→(B(x)→

C(x)))P⑹A(a)→(B(a)→

C(a))US⑸⑺B(a)→

C(a))T⑶⑹I⑻x(A(x)→(C(x)∨D(x)))P⑼A(a)→(C(a)∨D(a)))US⑻⑽C(a)∨D(a)T⑶⑼I⑾C(a)T⑷⑽I⑿

B(a)T⑺⑾I⒀A(a)∧

B(a))T⑶⑿I⒁

x(A(x)∧

B(x))EG⒀

x(A(x)→(C(x)∨D(x))),x(A(x)∧

D(x))

x(A(x)∧

B(x))c)每個大學(xué)生不是文科生就是理工科生，有的大學(xué)生是優(yōu)等生，小張不是理工科生，但他是優(yōu)等生，因此如果小張是大學(xué)生，他就是文科生。設(shè)A(x):x是大學(xué)生,B(x):x是文科生,C(x):x是理工科生，D(x):x是優(yōu)等生,

a:小張

x(A(x)→(

B(x)→C(x))),

x(A(x)∧D(x))

C(a)∧D(a)

A(a)→B(a)

x(A(x)→(

B(x)→C(x))),x(A(x)∧D(x)),

C(a)∧D(a)

A(a)→B(a)⑴A(a)P(附加前提)⑵x(A(x)→(

B(x)→C(x)))P⑶A(a)→(

B(a)→C(a))US⑵⑷B(a)→C(a))T⑴⑶I⑸C(a)∧D(a)P⑹C(a)T⑸I⑺B(a)T⑷⑹I⑻B(a)T⑺E⑼A(a)→B(a)