浙江理工大学本科生课程离散数学-一阶逻辑

一阶逻辑浙江理工大学本科生课程计算机科学与技术系离散数学答案3.10

在一阶逻辑中将下列命题符号化:(1)没有不吃饭的人。(2)在北京卖菜的人不全是东北人。解：使用全总个体域(1)F(x):x是人，G(x):x吃饭

x(F(x)G(x))

或x(F(x)→G(x))(2)F(x):x在北京卖菜，G(x):x是东北人

x(F(x)→G(x))

或x(F(x)G(x))

3.103.11

在一阶逻辑中将下列命题符号化:(3)不存在比所有火车都快的汽车。(4)说凡是汽车都比火车慢是不对的。解：使用全总个体域，设F(x):x是火车，G(y):y是汽车

L(x,y):x比y快,H(x,y):x比y慢(3)y(G(y)x(F(x)→L(y,x))

y

(G(y)x(F(x)→L(y,x)))

y(G(y)∨x(F(x)→L(y,x)))

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

L(y,x)))

y(G(y)→x(F(x)∧

L(y,x)))3.11(4)y(G(y)→x(F(x)→H(y,x)))

y(G(y)→x(F(x)→H(y,x)))

y(G(y)∨x(F(x)→H(y,x)))

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

H(y,x)))3.113.143.14指出下列公式中的指导变元，量词的辖域，各个体变项的自由出现和约束出现

(1)x(F(x)→G(x,y))

(2)xF(x,y)→yG(x,y)解：(1)x(F(x)→G(x,y))

指导变元约束变元自由变元

(2)xF(x,y)→yG(x,y)

指导变元约束变元自由变元

3.173.17判断下列各式的类型

(1)F(x,y)→(G(x,y)→

F(x,y))

(2)x(F(x)→F(x))→y(G(y)∧

G(y))解：(1)方法一：等值演算法

A=F(x,y)→(G(x,y)→

F(x,y))

F(x,y)∨(

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

F(x,y)∨

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

1

方法二：重言式的代换实例

A为重言式p→(q→p)的代换实例，A为永真(2)B=x(F(x)→F(x))→y(G(y)∧

G(y))

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

G(y))

1→0

0

矛盾式3.293.29求下列各式的前束范式（只用换名规则）3.30求下列各式的前束范式（只用代替规则）（1）xF(x)→yG(x,y)解:xF(x)→yG(x,y)

uF(u)→

yG(x,y)(换名规则)

u(F(u)→

yG(x,y)(量词辖域收缩与扩展等值式)

uy(F(u)→G(x,y))(量词辖域收缩与扩展等值式)

xF(x)→yG(x,y)

xF(x)→

yG(u,y)(代替规则)

x(F(x)→

yG(u,y)(量词辖域收缩与扩展等值式)

xy(F(x)→G(u,y))(量词辖域收缩与扩展等值式)

2.392.39在自然推理系统F中构造下面推理的证明(个体域为中国人组成的集合):东北人都不怕冷，王国瑞怕冷，所以王国瑞不是东北人。解：设F(x)：x是东北人G(x)：x怕冷a：王国瑞前提:x(F(x)→G(x)),G(a)

结论：F(a)

1.G(a)前提引入

2.x(F(x)→G(x))前提引入

3.F(a)→G(a)2UI规则

4.F(a)1,3拒取式3.403.40每个喜欢步行的人都不喜欢自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车。所以有些人不喜欢步行（个体域为人类集合)。解：(1).设F(x)：x喜欢步行

G(x)：x喜欢骑自行车

H(x):x喜欢乘汽车

(2).前提:x(F(x)→G(x))

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

xH(x)

结论：xF(x)

3.40(3).证明

1.xH(x)前提引入

2.H(c)1EI规则

3.x(G(x)∨H(x))前提引入

4.G(c)∨H(c)3UI规则

5.G(c)2,4析取三段论

6.x(F(x)→G(x))前提引入

7.F(c)→G(c)6UI规则

8.F(c)5,7据取式

9.xF(x)8EG规则若为全总个体域前提:x(M(x)∧F(x)→G(x))

x(M(x)→(G(x)∨H(x)))

x(M(x)∧H(x))结论：x(M(x)∧F(x))证明

1.x(M(x)∧H(x))前提引入

2.M(c)∧H(c)1EI规则

3.M(c)2化简

4.

H(c)2化简证明（续）

5.x(M(x)→(G(x)∨H(x)))前提引入

6.M(c)→(G(c)∨H(c))5UI规则

7.G(c)∨H(c)3,6假言推理

8.G(c)4,7析取三段论

9.x(M(x)∧F(x)→G(x))前提引入

10.M(c)∧F(c)→G(c)9UI规则

11.（M(c)∧F(c)）8,10据取式

12.