离散数学谓词逻辑课件

2-7谓词演算的推理理论推理方法：直接推理、条件论证、反证法所用公式：43页和70页的I1——I19，E1——E33推理规则：P、T、CP、US、ES、EG、UG后四个规则，是处理量词的，因为推理时要使用不含量词的命题公式，所以要去掉量词，如果结论有量词，还要添加量词。下面介绍四个新规则：一.全称指定规则

US(UniversalSpecialization)

形式：

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

A(y)(其中c是论域内指定客体)

含义：如果xA(x)为真，则在论域内任何指定客体c，都使得A(c)为真。

作用：去掉全称量词。条件：（1）c为任意客体常量。

（2）取代x的y应为任意的，不在A(x)中约束出现的个体变量。（3）用c或y去取代A(x)中x时，一定要在x自由出现的一切地方进行取代。二.全称推广规则UG(UniversalGeneralization)

形式：A(y)xA(x)(其中y是论域内任何指定客体)

含义：如果在论域内任何指定客体y都使得A(y)为真，则

xA(x)为真。

作用：添加全称量词。

条件：(1)无论A(y)中变量y取何值，A(y)均为真。

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

注意：y一定是任意的客体，否则不可使用全称推广规则。三.存在指定规则ES(ExistentialSpecialization)

形式：

xA(x)A(c)(其中c是论域内指定客体)

含义：如果

xA(x)为真，则在论域内指定客体c，

都使得A(c)为真。

作用：去掉存在量词。

条件：⑴c是使A(x)为真的特定的个体常量。⑵c不在A(x)中出现。

(3)若A(x)中除了x外，还有其他自由变元出现，此规则不能使用。

请看下面两个例子：

例：个体域为实数集，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规则。四.存在推广规则EG(ExistentialGeneralization)

形式：A(c)xA(x)(其中c是论域内指定客体)

含义：如果在论域内指定客体c使得

A(c)为真，则

xA(x)为真。

作用：添加存在量词。

条件:(1)c是特定的个体常量。

(2)x不是A(c)中的符号。注意：只能对前束范式使用UG、US、EG、ES规则，就是说一定要将公式化成等价的前束范式再使用这些规则。例2.7.1

所有金属都导电。铜是金属。故铜导电。令M(x):x是金属。C(x):x导电。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

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

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)转化后

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

xP(x)→

xQ(x)用CP规则证：

(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.推理中，对于同一个客体变元，既有带

也有带的前提，去量词时，应先去后去，这样才可以特指同一个客体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.添加量词时，也要加在公式的最左边，(即新加的量词前也无任何符号！！)且其辖域作用到公式的末尾。作业：79页⑴c)d)⑵、⑶第二章小结本章重点掌握内容：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)，应将⑷中的换成

即：

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规则证明

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)所有有理数是实数，某些有理数是整数，因此某些实数是整数。设Q(x):x是有理数R(x):x是实数I(x):x是整数

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)任何人如果他喜欢步行，他就不喜欢乘汽车；每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因此有的人不爱步行。设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)每个大学生不是文科生就是理工科生，有的大学生是优等生，小张不是理工科生，但他是优等生，因此如果小张是大学生，他就是文科生。设A(x):x是大学生,B(x):x是文科生,C(x):x是理工科生，D(x):x是优等生,

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)