屈婉玲版离散数学课后习题答案【2】

1、第四章局部课后习题参考答案3. 在一阶逻辑中将下面将下面命题符号化，并分别讨论个体域限制为(a),(b)条件时命 题的真值：(1) 对于任意x,均有/ -2=(x+ 点).(2) 存在x,使得x+5=9.其中(a)个体域为自然数集合.(b) 个体域为实数集合.解：F(x):-2=(x+点)(x 5).G(x): x+5=9.(1) 在两个个体域中都解释为xF(x)，在(a)中为假命题，在(b)中为真命题。 在两个个体域中都解释为xG(x)，在(a)(b)中均为真命题。4. 在一阶逻辑中将以下命题符号化：(1) 没有不能表示成分数的有理数.(2) 在北京卖菜的人不全是外地人.解：(1) F(x)

2、: x能表示成分数H(x): x 是有理数命题符号化为： x( F(x) H(x)(2) F(x): x是北京卖菜的人H(x): x 是外地人命题符号化为：x(F(x) H(x)5. 在一阶逻辑将以下命题符号化：(1)火车都比轮船快.(3) 不存在比所有火车都快的汽车.解：(1)F(x): x 是火车；G(x): x 是轮船；H(x,y): x 比 y 快命题符号化为：x y(F(x)G(y) H(x, y)(1)F(x): x 是火车;G(x): x 是汽车;H(x,y): x 比y快命题符号化为： y(G(y) x(F(x) H(x,y)9.给定解释I如下:(a)个体域D为实数集合R.(b

3、) D中特疋兀素匚=0.(c)特疋函数(x,y)=x -y,x,y D .(d)特疋谓词.(x,y):x=y,裁(x,y):x<y,x,yD说明以下公式在I下的含义,并指出各公式的真值：(1) x y(G(x,y) F(x, y)(2) x y(F(f(x,y),a)G(x,y)答:(1)对于任意两个实数x,y,如果x<y,那么x y.真值1.(2)对于任意两个实数x,y,如果x-y=0,那么x<y.真值0.10. 给定解释I如下：(a) 个体域D=N(N为自然数集合).(b) D中特定元素二=2.(c) D 上函数際罚=x+y, _ (x,y)=xy.(d) D 上谓词 X

4、(x,y):x=y.说明以下各式在I下的含义，并讨论其真值.(1) -xF(g(x,a),x)(2) -x-y(F(f(x,a),y)-F(f(y,a),x)答:(1)对于任意自然数x,都有2x=x,真值0.(2) 对于任意两个自然数x,y,使得如果x+2=y,那么y+2=x.真值0.11. 判断以下各式的类型：(1) 7 . - -.-(3) :二二、二二：TyF(x,y).解:(1)因为p (q p) p ( q p) 1为永真式；所以为永真式；(3) 取解释I个体域为全体实数F(x,y) : x+y=5所以,前件为任意实数x存在实数y使x+y=5,前件真；后件为存在实数x对任意实数y都有

5、x+y=5,后件假，此时为假命题再取解释I个体域为自然数N,F(x,y) : :x+y=5所以,前件为任意自然数x存在自然数y使x+y=5,前件假。此时为假命题。 此公式为非永真式的可满足式。13.给定以下各公式一个成真的解释，一个成假的解释。(1) j：(F(x)沁踣邈(2) =x(F(x) G(x) H(x)解：(1)个体域：本班同学F(x) : x会吃饭,G(x) : x会睡觉.成真解释F(x): x是泰安 人,G(x) : x是济南人.(2)成假解释个体域：泰山学院的学生F(x) : x出生在山东,G(x):x出生在北京,H(x):x出生在江苏，成假解释.F(x) : x会吃饭,G(x

6、) : x会睡觉,H(x) : x会呼吸.成真解释.第五章局部课后习题参考答案5.给定解释I如下：(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.试求以下公式在I下的真值.(1)x yF(x,y)(3)x y(F(x, y)F(f (x), f(y)解: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) 1x y(F(x, y)F(f(x), f(y)x(F(x,3)F(f(x), f(3)(F(x,4)F(f(

7、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)(0F(4,4)(F(3,4)F(4,3)(1F(3,4)(0 F (3,3)(0 0) (1 1) (11) (0 0)12. 求以下各式的前束范式。(1)xF(x) yG(x, y)X1F (X1,X2)(H (X1)X2G(Xi,X2)(此题课本上有错误)解:(1)xF(x) yG(x,y)xF(x) yG(t,y) x y(F(x) G(t,y)X1F (X1, X2)

8、 (H(xJX2G(Xi,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)前提:x(F(x) -(G(a) A R(x),=xF(x)结论:=x(F(x)A R(x)证明(1) xF(x)前提引入 F(c)El xF(x)y(F(y) G(y)R(y)前 y(F(y)G(y)R(y)假言推理(F(c) V G(c) -R(c)UIF(c) V G(c)附加 R(c)假言推理