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

1、2.13 设解释 I 为：个体域 DI =-2,3,6, 一元谓词 F（X ）：X3，G（X）：X>5,R(X):X7。在 I 下求下列各式的真值。（ 1） x(F(x) G(x)解：x(F(x)G(x)(F(-2)G(-2)(F(3)G(3)(F(6)G(6)(-23)(-2>5)(33)(3>5)(63)(6<5)(10)(10)(00)0000(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)(-27)(-23)( 37)(33)( 67)(63)(5>5)(11)(11)(

2、10)011000(3) x(F(x) G(x)解：x(F(x) G(x)(F(-2)G(-2)(F(3)G(3)(F(6)G(6)(-23)(-2>5)(33)(3>5)(63)(6>5)(10)(10)(01)11112.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（2）xy( F(x) G(z,y) 定理 2.2（ 1）（ 2）（xF

3、(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)zt(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,

4、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） y(F(y) G(y) R(y)F （ c） G(c) R(c)UIF（ c） ( F（ c） G(c) R(c)F（ c） G(c) R(y)R(c)xR(x)EG应改为：xF(x

5、)xF(x ) y(F(x) G(y) R(y)y(F(x)G(y) R(y)F（ c）F（ c） G(c) R(c)F（ c） G(c) R(c)xR(x)（2）前提：x(F(x ) (G(y)R(x),xF(x).结论：x(F(x)R(x).证明：xF(x) F(c)x(F(x ) (G(y)R(x) F(c) (G(c)R(c) G(c)R(c) R(c) F(c)R(c)x(F(x)R(x)2.18 在一阶逻辑中构造下面推理的证明。大熊猫都产在中国，欢欢是大熊猫。所以，欢欢产在中国。解： 将命题符号化 .F(x):x 是大熊猫 .G(x):x 产在中国 .a: 欢欢 .前提 :x(F(

6、x ) G(x),F(a),结论 : G(a)证明 : x(F(x ) G(x), 前提引入 ;F(a) G(a) uI;前提引入EI前提引入 错了前提引入 错了假言推理假言推理前提引入前提引入假言推理 EI UI附加假言推理EG前提引入 EI前提引入 UI假言推理化简合取 EG 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

7、(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) ).结论：x(F(x) )证明ax(H(x) )前提引入bH(c)c x(G(x) H(x) ) 前提引入d G(c) H(c)e G(c)fx(F(x)G(x) )前提引入gF(c)G(c)f UIhF(c)ix(F(x) )在上述推理中，b 后面的推理规则为C，