屈婉玲版离散数学课后习题答案.pdf

第四章部分课后习题参考答案第四章部分课后习题参考答案3. 在一阶逻辑中将下面将下面命题符号化 ,并分别讨论个体域限制为(a),(b)条件时命题的真值:(1) 对于任意 x,均有2=(x+)(x).(2) 存在 x,使得 x+5=9.其中(a)个体域为自然数集合. (b)个体域为实数集合.解解：F(x):F(x):2=(x+2=(x+)(x)(x).). G(x): x+5=9. G(x): x+5=9.(1)(1)在两个个体域中都解释为在两个个体域中都解释为xF(x)，在（，在（a a）中为假命题，）中为假命题，在在(b)(b)中为真命题中为真命题2)(2)在两个个体域中都解释为在两个个体域中都解释为xG(x)，在（，在（a a））(b)(b)中均为真命中均为真命题4.在一阶逻辑中将下列命题符号化:(1) 没有不能表示成分数的有理数.(2) 在北京卖菜的人不全是外地人.解解: :(1)F(x): x(1)F(x): x 能表示成分数能表示成分数 H(x): x H(x): x 是有理数是有理数命题符号化为命题符号化为: :x(F(x)  H(x))(2)F(x): x(2)F(x): x 是北京卖菜的人是北京卖菜的人 H(x): x H(x): x 是外地人是外地人命题符号化为命题符号化为: :x(F(x)  H(x))5.在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车.解解: :(1)F(x): x(1)F(x): x 是火车是火车; G(x): x; G(x): x 是轮船是轮船; H(x,y): x; H(x,y): x 比比 y y 快快命题符号化为命题符号化为: :xy((F(x) G(y))  H(x, y))(2) (1)F(x): x(2) (1)F(x): x 是火车是火车; G(x): x; G(x): x 是汽车是汽车; H(x,y): x; H(x,y): x 比比 y y快快命题符号化为命题符号化为: :y(G(y) x(F(x)  H(x, y)))9.给定解释 I 如下: (a) 个体域 D 为实数集合 R. (b) D 中特定元素 =0. (c) 特定函数(x,y)=x y,x,yD. (d) 特定谓词 (x,y):x=y, (x,y):x

此时，前件假此时为假命题为假命题此公式为非永真式的可满足式此公式为非永真式的可满足式13.给定下列各公式一个成真的解释，一个成假的解释1)(F(x)(2)x(F(x) G(x) H(x))解解:(1):(1)个体域个体域: :本班同学本班同学F(x)F(x)：：x x 会吃饭会吃饭, G(x), G(x)：：x x 会睡觉会睡觉. .成真解释成真解释F(x)F(x)：：x x 是泰安人是泰安人,G(x),G(x)：：x x 是济南人是济南人. .（（2 2）成假解释）成假解释(2)(2)个体域个体域: :泰山学院的学生泰山学院的学生F(x)F(x)：：x x 出生在山东出生在山东,G(x):x,G(x):x 出生在北京出生在北京,H(x):x,H(x):x 出生在江出生在江苏苏, ,成假解释成假解释. .F(x)F(x)：：x x 会吃饭会吃饭,G(x),G(x)：：x x 会睡觉会睡觉,H(x),H(x)：：x x 会呼吸会呼吸. . 成真解成真解释释. .第五章部分课后习题参考答案第五章部分课后习题参考答案5.给定解释Ｉ如下:(a)个体域 D={3,4};(b)f (x)为f (3)  4, f (4)  3(c)F(x, y)为F(3,3)  F(4,4)  0, F(3,4)  F(4,3) 1.试求下列公式在Ｉ下的真值.(1)xyF(x, y)(3)xy(F(x, y)  F( f (x), f (y)))解解:(1):(1)xyF(x, y)  x(F(x,3) F(x,4))(F(3,3) F(3,4))(F(4,3) F(4,4))(01)  (1 0) 1(2)(2)xy(F(x, y)  F( f (x), f (y))) x((F(x,3)  F( f (x), f (3)))(F(x,4)  F( f (x), f (4)))) x((F(x,3)  F( f (x),4))(F(x,4)  F( f (x),3))) ((F(3,3)  F( f (3),4))(F(3,4)  F( f (3),3)))((F(4,3)  F( f (4),4))(F(4,4)  F( f (4),3))) ((0  F(4,4))(F(3,4)  F(4,3))) ((1 F(3,4))(0  F(3,3))) (0  0) (11) (11) (0  0)112.求下列各式的前束范式。

1)xF(x)  yG(x, y) (5)x1F(x1,x2)  (H(x1)  x2G(x1,x2)) (本题课本上有错误)解解:(1):(1)xF(x)  yG(x, y)  xF(x)  yG(t, y)  xy(F(x)  G(t, y)) (5) (5)x1F(x1,x2)  (H(x1)  x2G(x1,x2)) x1F(x1,x2)  (H(x3)  x2G(x3,x2)) x1F(x1,x4)  x2(H(x3)  G(x3,x2)) x1x2(F(x1,x4)  (H(x3)  G(x3,x2)))15.在自然数推理系统 F 中,构造下面推理的证明:(1)前提:xF(x)  y((F(y)G(y))  R(y)),xF(x)结论:xR(x)(2)前提:x(F(x)→(G(a)∧R(x))),xF(x)结论: x(F(x)∧R(x))证明证明(1)(1)①xF(x)前提引入②F(c)①EI③xF(x)  y((F(y)G(y))  R(y))前提引入④y((F(y)G(y))  R(y))①③假言推理⑤(F(c)∨G(c))→R(c))④UI⑥F(c)∨G(c)②附加⑦R(c)⑤⑥假言推理⑧xR(x)⑦EG(2)(2)①xF(x)前提引入②F(c)①EI③x(F(x)→(G(a)∧R(x)))前提引入④F(c)→(G(a)∧R(c))③UI⑤G(a)∧R(c)②④假言推理⑥R(c)⑤化简⑦F(c)∧R(c)②⑥合取引入⑧x(F(x)∧R(x))。