离散数学（屈婉玲版）第二章习题答案

2.13 设解释I为：个体域DI ={-2,3,6},一元谓词F（X）：X（X）：X>5,R(X):X（1） 解：

x(F(x)x(F(x)(F(-2) ((-2((1 00

(2)

x(R(x)

F(x))

G(5) G(5)

F(3)) (( 3

(R(6)7)

(3

F(6))3))

03)

7。在I下求下列各式的真值。

3，G

G(x)) G(x)) G(-2))

(F(3) ((3((0 G(3)) 3)

(F(6) (3>5)) 0))

G(6)) ((6

3)

(6<5))

(-2>5))

0))

0))((1 0

解：x(R(x)(R(-2)((-2

F(x))

F(-2)) (R(3)7)

(-2

3))

G(5)

7)

(( 6

(63)) (5>5) (1 10

1) 1

(1 0

1) 0

(1

0)

0

(3)解：

x(F(x)x(F(x)

G(x)) G(x))

(F(3)

((3 (0

G(3)) 3) 1)

(F(6) (3>5))

G(6)) ((6

3)

(6>5))

(F(-2) ((-2(1

G(-2)) 3)

(-2>5)) (1

0)

0)

1 1

1 1

2.14 求下列各式的前束范式，要求使用约束变项换名规则。

（1）??xF(x)→?yG(x,y)

(2) ?（?xF(x,y) ??yG(x,y) ） 解：（1） ??xF(x)→?yG(x,y)

? ??xF(x)→ ?yG(z,y) 代替规则

? ?x?F(x)→?yG(z,y) 定理2.1（2 ） ? ?x(?F(x) →?yG(z,y) 定理2.2（2）③

?x?y(?F(x) →G(z,y)) 定理2.2（1）④

（2） ?（?xF(x,y) ??yG(x,y) ）

?(?zF(z,y) ??tG(x,t)) 换名规则 ?(?zF(z,y) )??(?tG(x,t) ) ?z?F(z,y) ??t?G(x,z) ?z (?F(z,y) ??t?G(x,z)) ?z ?t(?F(z,y) ??G(x,t))

2.15 求下列各式的前束范式，要求使用自由变项换名规则。（代替规则）

（1） ?xF(x)∨?yG(x,y)

??xF(x) ∨?yG(z,y) 代替规则 ??x（F(x) ∨?yG(z,y)） 定理2.2（1）① ??x?y（F(x) ∨G(z,y)） 定理2.2（2）① （2） ?x(F(x) ∧?yG(x,y,z)) →?zH(x,y,z)

??x(F(x) ∧?yG(x,y,t)) →?zH(s,r,z) 代替规则 ??x?y (F(x) ∧G(x,y,t)) →?zH(s,r,z) 定理2.2（1）② ??x（?y (F(x) ∧G(x,y,t)) →?zH(s,r,z)） 定理2.2（2）③ ??x?y（(F(x) ∧G(x,y,t)) →?zH(s,r,z)） 定理2.2（1）③

??x?y?z（(F(x) ∧G(x,y,t)) →H(s,r,z)） 定理2.2（2）④

2.17构造下面推理的证明。

（1） 前提 ：?xF(x)→?y((F(y)∨G(y))→R(y))

?xF(x) 结论：?xR(x)

证明：① ?xF(x) 前提引入 ② F（c） EI ③ ?y((F(y)∨G(y))→R(y)) 前提引入错了 ④ F（c）∨G(c) →R(c) UI ⑤ F（c）→(F（c）∨G(c) →R(c)) 前提引入错了 ⑥ F（c）∨G(c) →R(y) 假言推理②⑤ ⑦ R(c) 假言推理②⑥ ?xR(x) EG 应改为： ① ?xF(x) 前提引入 ② ?xF(x)→?y((F(x)∨G(y))→R(y)) 前提引入 ③ ?y((F(x)∨G(y))→R(y)) ①②假言推理

④ F（c） ①EI ⑤ F（c）∨G(c) →R(c) ③UI ⑥ F（c）∨G(c) ④附加

⑦ R(c) ⑤⑥假言推理 ⑧ ?xR(x) ⑦EG

（2）前提：x(F(x)→(G(y) R(x))),xF(x). 结论：x(F(x)R(x)). 证明：

①xF(x) 前提引入 ②F(c) ①EI

③x(F(x)→(G(y) R(x))) 前提引入 ④F(c)→(G(c) R(c)) ③UI

⑤G(c) R(c) ②④假言推理 ⑥R(c) ⑤化简 ⑦F(c)R(c) ②⑥合取 ⑧x(F(x)R(x)) ⑦EG 2.18在一阶逻辑中构造下面推理的证明。

大熊猫都产在中国，欢欢是大熊猫。所以，欢欢产在中国。 解： 将命题符号化. F(x):x是大熊猫. G(x):x产在中国. a: 欢欢.

前提: ?x(F(x )→G(x)),F(a), 结论: G(a) 证明:

①?x(F(x )→G(x)), 前提引入; ②F(a)→G(a) ①uI;

③F(a) 前提引入

④G(a) ② ③ 假言推理

2.19在一阶逻辑中构造下面推理的证明。

有理数都是实数，有的有理数是整数。因此，有的实数是整数。 设全总个体域为数的集合 F（x）：x是有理数 G（x）：x是实数 H（x）：x是整数 前提：?x(F(x)→G(x)) ?x(F(x)∧H(x)) 结论：?x(G(x)∧H(x))

证明：① ?x(F(x)∧H(x)) 前提引入 ② F（c）∧H（C） ①EI规则 ③ ?x(F(x)→G(x)) 前提引入 ④ F（c）→G（c） ③UI规则

⑤ F（c） ②化简

⑥ G（c） ④⑤假言推理 ⑦ H（c） ②化简 ⑧ G（c）∧H（c） ⑥⑦合取 ⑨ ?x（G（x）∧H（x）） ⑧EG规则 2.23一阶逻辑中构造下面推理的证明。 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行（个体域为人类集合）。

命题符号化：F(x): x喜欢步行。G(x):x喜欢坐汽车。H(x): x喜欢骑自行车。 前提：?x(F(x)

→

G(x)), ?x(G(x)∨H(x)),

?x(

H(x)).

F(x))

结论：?x(证明 a ?x(b

H(x)) 前提引入 H(c)

c ?x(G(x) ∨H(x)) 前提引入

d G(c) ∨H(c) e G(c) f ?x(F(x) →g F(c) →

G(x)) 前提引入

G(c)) f UI

h F(c)

本文来源：https://www.bwwdw.com/article/2bcd.html