离散数学屈婉玲版习题答案

1、2.13 设解释I为：个体域DI =-2,3,6,一元谓词F（X）：X£3，G（X）：X>5,R(X):X£7。在I下求下列各式的真值。（1）"x(F(x)ÙG(x) 解："x(F(x)ÙG(x)Û(F(-2) ÙG(-2) Ù(F(3) ÙG(3) Ù(F(6) ÙG(6)Û(-2£3) Ù(-2>5) Ù(3£3) Ù(3>5) Ù(6£3) Ù(6<5)&#

2、219;(1 Ù0)Ù(1 Ù0) Ù(0 Ù0)Û0Ù0Ù0Û0(2) "x(R(x)®F(x)ÚG(5) 解："x(R(x)®F(x)ÚG(5)Û(R(-2)®F(-2)Ù (R(3)®F(3)Ù (R(6)®F(6)Ú G(5)Û(-2£7) ®(-2£3)Ù ( 3£7) ®(3£3)

3、17; ( 6£7) ®(6£3) Ú (5>5)Û(1 ®1)Ù (1 ®1)Ù (1®0) Ú 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) Ú (-2>5) Ú

4、; (3£3) Ú (3>5) Ú (6£3) Ú (6>5)Û(1 Ú 0) Ú (1 Ú 0) Ú (0 Ú 1)Û1 Ú 1 Ú 1Û12.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) 代替规则 xF(x)yG(z,y) 定理2.1（2 ） x(F(x) yG(z,y) 定理2.2

5、（2） xy(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) ) zF(z,y) tG(x,z) z (F(z,y) tG(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)）

6、定理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）

7、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）

8、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) EG2.18在一阶逻辑中构造下面推理的证明。大熊猫都产在中国，欢欢是大熊猫。所以，欢欢产在中国。解： 将命题符号化. F

9、(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

10、规则 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).结论：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