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

1、学习文档仅供参考2.13 设解释 i 为： 个体域 di =-2,3,6, 一元谓词 f x ： x 3， g x ：x5,r(x):x7。在 i 下求以下各式的真值。1x(f(x) g(x) 解：x(f(x)g(x) (f(-2) g(-2) (f(3) g(3) (f(6) g(6) (-2 3) (-25) (3 3) (35) (6 3) (65) (1 1) (1 1) (10) 0 1 1 0 0 0 (3) x(f(x) g(x) 解： x(f(x)g(x) (f(-2) g(-2) (f(3) g(3) (f(6) g(6) (-2 3) (-25) (3 3) (35) (6

2、 3) (65) (1 0) (1 0) (0 1) 1 1 1 学习文档仅供参考1 2.14 求以下各式的前束范式，要求使用约束变项换名规则。1xf(x) yg(x,y) (2) xf(x,y) yg(x,y) 解： 1xf(x) yg(x,y) xf(x) yg(z,y) 代替规则xf(x)yg(z,y) 定理 2.12 x(f(x) yg(z,y) 定理 2.22xy(f(x) g(z,y) ) 定理 2.21 2xf(x,y) yg(x,y) (zf(z,y) tg(x,t) 换名规则(zf(z,y) )(tg(x,t) ) zf(z,y) tg(x,z) z (f(z,y) tg(x

3、,z) z t(f(z,y) g(x,t)2.15 求以下各式的前束范式，要求使用自由变项换名规则。代替规则1xf(x) yg(x,y) xf(x) yg(z,y) 代替规则xf(x) yg(z,y)定理 2.21x yf(x) g(z,y)定理 2.222x(f(x) yg(x,y,z) zh(x,y,z) x(f(x) yg(x,y,t) zh(s,r,z) 代替规则xy (f(x) g(x,y,t) zh(s,r,z) 定理 2.21xy (f(x) g(x,y,t) zh(s,r,z)定理 2.22x y(f(x) g(x,y,t) zh(s,r,z)定理 2.21x y z(f(x)

4、 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 ) 前提引入fcei y(f(y)g(y) r(y)前提引入 错了fc g(c) r(c) ui fc ( fc g(c) r(c) 前提引入 错了fc 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) 假言推理fceifc g(c) r(c) ui fc g(c) 附加 r

5、(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)

6、证明 : x(f(x ) g(x), 前提引入 ; f(a)g(a)ui; f(a) 前提引入g(a) 假言推理学习文档仅供参考2.19 在一阶逻辑中构造下面推理的证明。有理数都是实数，有的有理数是整数。因此，有的实数是整数。设全总个体域为数的集合fx ：x 是有理数gx ：x 是实数hx ：x 是整数前提：x(f(x) g(x) x(f(x) h(x) 结论：x(g(x) h(x) 证明：x(f(x) h(x) 前提引入fc h cei 规则x(f(x) g(x) 前提引入fc g cui 规则fc化简 gc假 言推理 hc化简 gc h c合取xg x hx eg规则2.23 一阶逻辑中构

7、造下面推理的证明。每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行个体域为人类集合。命题符号化： f(x): x 喜欢步行。 g(x):x 喜欢坐汽车。h(x): x 喜欢骑自行车。前提：x(f(x) g(x), x(g(x)h(x) ), x(h(x). 结论：x(f(x) 证明a x(h(x) 前提引入b h(c) c x(g(x) h(x) ) 前提引入d g(c) h(c) e g(c) f x(f(x) g(x) 前提引入g f(c) g(c) f ui h f(c) i x(f(x) h eg 学习文档仅供参考在上述推理中，b 后面的推理规则为a,d 后面的规则为b,e 后用的