自考离散数学第二章答案.doc-得力文库

资源描述

《自考离散数学第二章答案.doc》由会员分享，可在线阅读，更多相关《自考离散数学第二章答案.doc（28页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流自考离散数学第二章答案.精品文档.习题2.1答案(从本章起，习题答案由jhju提供，晓津补充。如有问题或不同意见，欢迎到分课论坛发表) 1、用谓词表达式写出下列命题 a)小张不是研究生；解：设A(x)：x是研究生； a:小张； |A(a)。 b)他是跳高或篮球运动员；解：设A(x):x是跳高运动员；B(x):x是篮球运动员； a: 他；A(a)B(a) 。 c)晓莉非常聪明和能干；解：设 A(x):x非常聪明；B(x):x能干； l: 晓莉；A(l)B(l) d)若m是奇数则2m是偶数解：设 A(x): x是奇数 B(y):y是

2、偶数 m:某数 A(m) B(2m) 2、将下列命题符号化并要分析到个体词及谓词 a)长江流经四川省；解：B(x,y):x流经y； a:长江 b:四川省 B(a,b)。个体词：长江、四川省谓词：流经 b)这架新式歼击机击沉了那艘老式快艇解：设A(x,y):x击沉了y a:新式歼击机 b:老式快艇 A(a,b). 个体词：歼击机、快艇谓词：击沉 3、用谓词表达式符号化下列命题。那位戴眼镜穿西服的大学生在看一本英文杂志。解：设：A(x): x戴眼镜；B(x): x穿西服；C(x): x在看英文杂志；a: 那位大学生 A(a)B(a)C(a) 这个表达式的含义就是一个陈述句：那位大学生

3、戴眼镜且那位大学生穿西服且那位大学生在看英文杂志。个体词是：那位大学生。谓词有：戴眼镜、穿西服、在看英文杂志。 2.2习题答案 (从本章起，习题答案由jhju提供，晓津补充。如有问题或不同意见，欢迎到分课论坛发表) 题号：1 2 3 4 5 6 1、对下列公式指出约束变元和自由变元，并指明量词的辖域。 a,(x)(P(x)Q(x)(x)R(x,y)； (x)的指导变元是x,其辖域是(P(x)Q(x) (x)的指导变元是x,其辖域是R(x,y) 对于(x)来说，x是约束出现，y则是自由出现。 b,(x)(y)(P(x)Q(y)(x)(R(x)S(z)； (x)和(y)的指导变元是x,y,其辖域

4、是(P(x)Q(y) (x)的指导变元是x,其辖域是(R(x)S(z) x,y在辖域是约束出现，z则是自由出现 (注，教材中本题原来是多一个括号的(或者说少一个)，现在jhju将它改成这个样子，请大家仔细在书中找BUG) c,(x)(y)(P(x,y)Q(z) (x)(y)的指导变元是x,y,自由变元是z,其辖域是P(x,y)Q(z) 2、在下列公式中，对约束变元进行换名，对自由变量进行代入。 a,(x)(y)(P(x,z)Q(y)S(x,y) 约束变元的换名，用t替换x,用g替换y (t)(g)(P(t,z)Q(g)S(x,y) 将自由变元z换为e (x)(y)(P(x,e)Q(y)S(x,

5、y) b,(x)(P(x)Q(x)(x)(k(x)S(x); 对约束变元x改名为z (z)(P(z)Q(z)(z)(k(z)S(z) c,(x)(P(x)(Q(x)R(x)(x)(R(x)(y)S(x,y); 对前件的约束变元x改名为z (z)(P(z)(Q(z)R(z)(z)(R(z)(y)S(z,y) 用g来代替自由变元y (z)(P(z)(Q(z)R(z)(z)(R(z)(g)S(z,g) d,(x)P(x,y)(x)(Q(x,z)(z)(x)R(x,y,z); 用g换名约束变元x (g)P(g,y)(g)(Q(g,z)(z)(g)R(g,y,z) 对自由变元y进行替换d (x)P(x,

6、d)(x)(Q(x,z)(z)(x)R(x,d,z) e,(x)(P(x,y)(z)Q(x,z); 对约束变元x进行替换g (g)(P(g,y)(z)Q(x,z) 对自由变元 x代为g y代为d (x)(P(x,d)(z)Q(g,z) 3、谓词公式 (x)(P(x)(y)R(y)Q(x)中量词(x)的辖域是： a,(x)(P(x)(y)R(y) b,P(x); c,(P(x)(y)R(y) d,P(x),Q(x) 答案：c 4、谓词公式 (x)(P(x)(y)R(y)Q(x)中变元x是答案。 a,自由变元 b,约束变元 c,既不是自由变元，也不是约束变元 d,既是自由变元又是约束变元；答案

7、是d (请注意，教材中又少一括号，如果按上面红色括号的位置添入，则答案为d,若加在最后，则答案为b,当然，括号还可以加在P(x)后面，则此时答案又变成d) 5、设论域为整数集，下列公式中哪个值为真。 a,(x)(y)(x+y=0); b,(y)(x)(x+y=0); c,(x)(y)(x+y=0); d,|(x)(|y)(x+y=0); 答案 (jhju的答案是c, 注意题中的|y，晓津觉得个体变元前面不应该加否定，前面三个答案是不对的，但是也不能说最后一个答案是对的，除非把|改成，大家说呢? 后来有学友指出本题中答案a是正确的，其解释是对于任意x存在y，有x+y=0,这是真的。所以本题的答案

8、应当是a) 6、取个体域为整数集，给定下列公式,指出下面公式中哪些是真命题，哪些是假命题： a, xy (x.y=0); e, x-y=-y+x ; b, xy (x.y=1); f, xy(x.y=y); c, yx (x.y=2); g, x(x.y=x); d, xyx (x-y=z); h, xy (x+y=2y)。答：a , e , f,h 为真 b ,c , g 为假 d 是否出错？ (以上是jhju答案，晓津认为：只有a,c,e是真命题，其他的都为假。至于d,我也觉得有个BUG，大约x应改为z吧。) 2.3 习题参考答案 (本章习题答案由jhju提供，晓津补充。如有问题或不同意

9、见，欢迎到分课论坛发表) 题号：1 2 3 4 5 6 7 81、设解释I如下： D=2,3, f(2)=3,f(3)=2,F(2,2)=0,F(2,3)=0,F(3,2)=1,F(3,3)=1 。试求出下列公式在I下的真值。 a) F(2,f(2)F(3,f(3); 解：a) F(2,f(2)F(3,f(3) F(2,3)F(3,2) 01 0 由于离散数学中 0与F对应故该式为假 b) xyF(y,x); b)参照P33页例2 c F(2,2)F(3,2)F(2,3)F(3,3) 0101 1 该式为真 (晓津观点：原式(F(2,2)F(3，2)(F(2，3)F(3，3)(01)(01)

10、11T我认为有些括号不能省略，虽然此题中结果相同) c) xy(F(x,y)F(f(x),f(y); 解：c) 原式(F(x,y)F(f(x),f(y)(F(x,y)F(f(x),f(y)(F(x,y)F(f(x),f(y)(F(x,y)F(f(x),f(y) (F(2,2)F(f(2),f(2)(F(2,3)F(f(2),f(3)(F(3,2)F(f(3),f(2)(F(3,3)F(f(3),f(3) (01)(01)(10)(10) 0 该式为假 (晓津认为红色部分应舍去，在消去量词后，个体变元就应该赋值代入了,且红色部分的表达式似无意义，每一行都是相同的。) 2、给定解释N如下： a)

11、个体域为自然数 DN； b) DN上特定元素 a=0; c) DN上特定函数 f(x,y)=x+y ,g(x,y)=x.y ; d) DN上特定谓词 F（x,y) 为 x=y 。在解释N下，哪些公式为真，哪些公式为假。 a) xF(g(x,a),x); b) xyF(f(x,a),y)F(f(y,a),x); c) xyzF(f(x,y),z); d) xyF(f(x,y),g(x,y); e) F(f(x,y),f(y,z)。解： a,为假，如果 a=1时，该式子便会成立的。 b, 为假，如果 a=1时，该式子也不会成立。 c, 为假 d, 为假 e, 为假 (晓津认为：b)式为真，解释

12、如下:在上述论域中，b式xyF(f(x,0),y)F(f(y,0),x) xyF(F(x,y)F(y,x)若x=y,式为真，若x不等于y，则前件为假，可得式为真。) 3、给定赋值R如下：DR是实数集，DR中特定元素 a=0 ,DR中特定函数 f(x,y)=x-y,特定谓词 F(x,y)为xy在赋值R之下，以下公式为真，哪些为假？ a) xF(f(a,x),a); b) xy(|F(f(x,y),x); c) xyz(F(x,y) F(f(x,z),f(y,z); d) xyF(x,f(f(x,y),y); 解： a, 由于实数的范围也包括负数，所以在包含负数的情况下，该数就不会成立。而在正整数

13、的情况便成立 b, 此式也为假 c, 只要满足 10的情况此式即为假，设 xy 时，则x-zy-z。那么就不会出现 10的情况。故此式为真。 d, 在众多的y取值中， x x-y-y 这个式子不成立，故其为假晓津观点，当y取负值时，式子为真，因此命题是成立的。4、给出赋值I，使下面两个公式在此赋值下均为假，从而说明这两个公式都不是逻辑有效式。a) x(F(x)G(x) (xF(x)xG(x); b) (x(F(x)x(G(x) x(F(x)G(x); 解：a, 如果要使该式均为假，那么必须是 10 的情况。即在赋值的情况下，始终保持 F(x)G(x) 为1且xF(x)为0，xG(x)也为0

14、。给定赋值I如下：IR是正整数集，IR中,特定谓词 G(x)为 x mod 2 F(x)为 (x+1) mod 2。(注意mod是求余运算） b, 如果要使该式均为假，那么必须是 10 的情况。即在赋值的情况下， x(F(x)x(G(x) 为1x(F(x)G(x)始终为0。采用以上的赋值条件即可实现。给定赋值I如下：IR是正整数集，IR中,特定谓词 G(x)为 x mod 2 F(x)为 (x+1) mod 2。(注意mod是求余运算） 5、试寻一个公式A，使A在某些解释下为真，而在另外一些解释下为假。解：DI=-2,3,1, F(x):x=3 xF(x) 为真 DI=6,7,8, F

15、(x):x=3 xF(x) 为假 6、在一阶逻辑中，将下面命题符号化，并且要求只能使用全称量词。a) 没有人长着绿色头发； b) 有的上海市民没有去过东方明珠塔；解：a, x(|F(x) F(x): x长着绿头发b, |x(F(x,a) F(x,a): x去过a x:表示上海的一个市民 a:是个常量，表示明珠电视塔。 7、设个体域为 D=a,b,c，消去以下各式中的量词： a) xF(x) yG(y); b) xF(x)yG(y); c) xyH(x,y)。解：a, abcabc b, abcabc abcbc bc c, H(a,a)H(a,b)H(a,c)H(b,a)H(b,b)H(b

16、,c)H(c,a)H(c,b)H(c,c) 晓津的答案是这样的： a)原式(F(a)F(b)F(c)(G(a)G(b)G(c);b)原式(F(a)(G(a)G(b)G(c)(F(b)(G(a)G(b)G(c)(F(c)(G(a)G(b)G(c)c)原式(H(a,a)H(a,b)H(a,c)(H(b,a)H(b,b)H(b,c)(H(c,a)H(c,b)H(c,c) 8、设个体域 DI=-2,3,6, F(x):x5,R(x):x=7,在此解释下，求以下各式真值。 a) x(F(x)G(x); b) x(R(x) F(x)G(5); c) x(F(x)G(x)。解： a) F b) F c)

20、(x,y,q)zH(r,s,z)z(xy|(F(x)G(x,y,q)H(r,s,z)zx(y(F(x)G(x,y,q)H(r,s,z)zxy(F(x)G(x,y,q)H(r,s,z)如果要加一个括号，那变数太多，就不做了吧。 2.5 习题参考答案(本章习题答案由jhju提供，晓津补充。我们的答案为引玉之砖，欢迎到分课论坛发表不同意见) 题号：1 2 3 4 5 6 说明：表示存在量词表示全称量词= 表示等价于。 1、构造下面推理的证明。 a) 前提： xF(x) y(F(y)G(y) R(y),xF(x), 结论： xR(x)。 (1) xF(x) y(F(y)G(y) R(y)P (2)

21、xF(x) y(|(F(y)|G(y) R(y)T(1) E (3) y(|(F(y)|G(y) R(y) T(2)I (4)|(F(c)|G(c) R(c) US(3) (5)R(c) T(4)I (6)xR(x) EG(5) 晓津的证法： (1) xF(x) P(2) xF(x) y(F(y)G(y) R(y)P (3) y(F(y)G(y) R(y) T(1)(2)I (4) F(c)ES(1)(5) (F(c)G(c) R(c)US(3) (6) R(c)T(4)(5)I(7) xR(x) EG(6) b) 前提： x(F(x) (G(y) R(x),xF(x), 结论： x(F(x)

22、R(x) (1)x(F(x) (G(y) R(x) P (2) F(c) (G(c) R(c) US(1) (3) F(c) T(2)I (4) G(y)R(c) T(2)I (5) R(c) T(4)I (6) F(c)R(c) T(3)(5) I (7) x(F(x)R(x) EG(4) 晓津证法:(1) xF(x)P(2) F(c) ES(1)(3) x(F(x) (G(y) R(x)P(4) F(c)(G(d)R(c)US(3)(5) G(d)R(c)T(4)(2)I(6) R(c)T(5)I(7) F(c)R(c)T(2)(6)I(8) x(F(x)R(x)EG(7) 2、构造下式的

23、推理证明：有理数都是实数，有的有理数是整数，因此有的实数是整数。 M(x): x是实数 G(x): x是整数 F(x): x是有理数 x(F(x) M(x) , x(F(x) G(x) x(M(x)G(x) (1)x(F(x) M(x) P (2)F(c)M(c) US(10 (3)x(F(x) G(x) P (4)F(c) G(c) ES(3) (5)M(c) G(c) T(2)(4) I (6)x(M(x)G(x) EG(5) 晓津解法：命题符号化为:x(F(x) M(x) , x(F(x) G(x) x(M(x)G(x)证明如下: (1) x(F(x) G(x)P(2) F(c)G(c

24、) ES(1)(3) F(c) T(2)I(4) G(c) T(2)I(5) x(F(x) M(x)P(6) F(c)M(c)US(5)(7) M(c) T(6)I(8) M(c)G(c)T(4)(7)I(9) x(M(x)G(x)EG(8)3、构造以下各式的推理证明。 a) (x)A(x) (x)B(x)(x)(A(x) B(x); (1) (x)A(x) (x)B(x) P (2) |(x)A(x)(x)B(x) T(1)E (3) (x)|A(x)(x)B(x) T(2)E (4) (x)(|A(x)B(x) T(3)E (5) (x)(A(x) B(x) T(4)E 我觉得红色E应为I

27、|M(x)EG(8)证到这里，发现没办法得到正确结论，只能得到有的人不爱步行的结论。请各位指教。5、符号化下列各命题，并给出构造推理证明： a) 每一个自然数不是奇数就是偶数；自然数是偶数，当且仅当它能被2整除；并不是所有自然数都能被2整除，因此有的自然数是奇数。晓津解法：设N(x): x 是自然数P(x): x 是偶数Q(x)：x 是奇数F(x): x 能被2整除则命题符号化为：前提：x(N(x)(P(x)|Q(x)(|P(x)Q(x)，x(N(x)(P(x)F(x),|x(N(x)F(x)结论：x(N(x)Q(x)。证明如下：(1) |x(N(x)F(x)P(2) x|(N(x)F(x)

29、)I(17) x(N(x)Q(x) EG(16)b)如果一个人怕困难，那么他就不会获得成功；每个人或者获得成功，或者曾经失败过；有些人未曾失败过，所以有些人不怕困难。解：设：论域是人的集合 P(x):x怕困难H(x):x获得成功S(x):x曾经失败过命题化为：x(P(x)|H(x),x(H(x)S(x),x|S(x) x|P(x).证明如下：(1) x|S(x)P(2) |S(c) ES(1)(3) x(H(x)S(x) P(4) H(c)S(c)US(3)(5) H(c) T(2)(4)I(6) x(P(x)|H(x)P(7) x(|P(x)|H(x)T(6)E(8) |P(c)|H(c)

30、 US(7)(9) |P(c) T(5)(8)I(10) x|P(x)EG(9)c)每个科学工作者都是刻苦钻研的；每个刻苦钻研而又聪明的人在他的事业中都将获得成功；某人是科学工作者，并且是聪明的，所以某人在他的事业中将获得成功。 A(x): x是科学工作者 B(x): x刻苦钻研 C(x): x聪明 D(x): x在他的事业中获得成功c: 某人前提： x(A(x)B(x) ,x(B(x)C(x)D(x) 结论： A(c)C(c)D(c) (1) x(A(x)B(x) P (2) A(c)B(c) US(1) (3) x(B(x)C(x)D(x) P (4) B(c)C(c)D(c) US(3)

展开阅读全文