习题参考解答.docx

《习题参考解答.docx》由会员分享，可在线阅读，更多相关《习题参考解答.docx（34页珍藏版）》请在三一办公上搜索。

1、习题参考解答离散数学部分课后习题答案 离散数学部分课后习题答案 习题1.1 1、P：银行利率降低 Q：股价没有上升 PQ P：他今天乘火车去了北京 Q：他随旅行团去了九寨沟 PQ P：不识庐山真面目 Q：身在此山中 QP，或 PQ P：一个整数能被6整除 Q：一个整数能被3整除 R：一个整数能被2整除 T：一个整数的各位数字之和能被3整除 PQR ，QT 2、T F F T F T T 悖论 习题 1.3 1、 P(QR)P(QR)(PQ)(PR)(PQ)(PR)(PQ)(QR)(RP)=(PR)Q)(RP)=(PR)(RP)(Q(RP)=(PR)(PR)(QR)(QP)=右2、不， 不， 能

2、 习题 1.4 2、 1 离散数学部分课后习题答案 离散数学部分课后习题答案 3、，4、 习题 1.5 1、(3) P(R(QP)=P(R(QP)=(PR)(T)=PR=(PR(QQ) =(PRQ)(PRQ) 主合取范式 P(R(QP)=P(R(QP)=P(RQ)(RP)=(P(QQ)(RR)(RQ(PP)(RP(QQ)=(PQR)(PQR)(PQR)(PQR) (RQP)(RQP)(RPQ)(RPQ)=(PQR)(PQR)(PQR)(RQP)(RQP)(RPQ)主析取范式 2、(2) Q(PQ)(PR)=(PQ)(PR)=(PQ(RR)(PR(QQ) =(PQR)(PQR)(PRQ) P(Q

3、R)=P(QR)=(PQ)(PR)=(PQR)(PQR)(PRQ)等价3、解：根据给定的条件有下述命题公式： ） 2 离散数学部分课后习题答案 离散数学部分课后习题答案 ） ） ） 三种方案：A和D、 B和D、 A和C 习题 1.6 1、 需证(PQ)(P(PQ)为永真式 Q(PQ)(P(PQ)=(PQ)(P(PQ)PP)(PQ)T=(PQ)(PQ)=T=(PQ)(PQP(PQ)需证PPRS为永真式 3 离散数学部分课后习题答案 离散数学部分课后习题答案 QPPRSFRSFST PPRS3、QABAB为永真式。即AB永真 QABBABA永真 AB当且仅当BA 4、设： P：珍宝藏在东厢房 Q：

4、藏宝的房子靠近池塘 R：房子的前院栽有大柏树 S：珍宝藏在花园正中地下 t：后院栽有香樟树 m：珍宝藏在附近 命题化后进行推理： (Qp)(RP)Q(RS)(tm)p(RP)(RS)(tm)R(RS)(tm) S(tm)即S为真，珍宝藏在花园正中地下 5、(1)F (P=0,Q=1) (2)F (P=1,Q=R=0) (3)F (P=0,Q=1) 习题 1.7 1.PQ,RQPR 证：利用CP规则 P P(附加前提) PQP QTI RQP RTI 4 离散数学部分课后习题答案 离散数学部分课后习题答案 结论成立 CP规则 (PQ)(RS),(SVE)BP B证： PP(附加) PQ T (P

5、Q)(RS)P RST ST SE T SEB P BT PBCP() 2. (2) P：无任何痕迹 Q：失窃时，小花在OK厅 R：失窃时，小英在OK厅 S：失窃时，小胖在附近 T：金刚是偷窃者 M：瘦子是偷窃者 命题可符号化为： P, QR, SP, QT, SR, RM 证： P P SP P S T SR P R T QR P Q T QT P T T 5 离散数学部分课后习题答案 离散数学部分课后习题答案 金刚是窃贼。 3. (1) 不相容 (2) 相容 (P=1,R=Q=S=0) 不相容 不相容 4. (1)证：(PQ)(RS)(SQ)(PQ)P (PQ)(RS)(SQ)(PQ)P

6、即 F=PQ, RS, SQ, PQ, P 利用消解原理： P P PQ P Q PQ P P PP=F 习题 2.1 1. (1)A(x)：x是实数 B(x)：x是有理数 (x)(B(x)A(x) x(A(x)B(x) $x(A(x)B(x) (2)A(x)：x是直线 F(x,y)：x与y平行 G(x,y)：x与y相交 abA(a)A(b)(F(a,b)G(a,b) (3)A(x)：x是会员 F(x)：x参加活动 Px(A(x)F(x) P: 这个活动有意义 或者 x(A(x)F(x)P 6 离散数学部分课后习题答案 离散数学部分课后习题答案 A(x)：x是正整数 x(A(x)B(x)C(x

7、) B(x)：x是合数 C(x)：x是质数 A(x)：x是存钱的人 B：x想有利息 P:存钱没有利息 Q：人们不存钱 2.(1)P(0)P(1)P(2)(R(0)R(1)Q(2) (2)P(0)Q(0)P(1)Q(1)P(2)Q(2) 4.(1) (x)($y)P(x,y)Q(y,t)(z)R(x,y,z) 习题 2.2 1.D：数 A(x):x=0f(x,y)=xy xyA(f(x,y)A(x)A(y)A(x-1)A(f(x-1,x+1) 可满足式 (2)A(x):x是诚实的人，B(x):x讲实话 ，a：小林 xB(x)A(x)A(a)B(a) T (3) A(x):x不便宜，B(x):x是

8、好货，a：小王买的衣服 xA(x)B(x) A(a)B(a) T A(x):x是懂得人性本质的作家 B(x):x是真正的诗人 D(x):x很高明 a：莎士比亚 C(x):x能刻画人们内心世界 P(x,y):x创作了y b：哈姆雷特 2.(1) T 3.(1) F T (2) T 7 离散数学部分课后习题答案 离散数学部分课后习题答案 4. D: 实数 P(x,y):y=ex, Q(y):y0 习题 2.3 1.$x$yP(x)Q(y) $x$yP(x)Q(y) $x$yP(x)$yQ(y) $xP(x)$yQ(y) xP(x)$yQ(y) (Ax)P(x)($y)Q(y) 2. 不成立 P(0

9、)P(1)P(2)Q(0)Q(1)Q(2), ,D=0,1,2 0101013.(1)(x)P(x)($y)P(y) (x)P(x)($y)P(y) ($x)(P(x)($y)P(y) (x)P(x)(y)(P(y) (x)(y)(P(x)P(y) skolem范式 (2)(x)P(x)($y)(z)Q(y,z) (x)P(x)$(y)(z)Q(y,z) (x)P(x)(y)($z)Q(y,z) (x)(y)($z)(P(x)Q(y,z) 前束范式 (x)(y)(P(x)Q(y,f(x,y) skolem范式 习题 2.4 1. 证：在某个解释下，($x)($y)P(x)Q(y)取值1，必有a

10、,bD, 8 离散数学部分课后习题答案 离散数学部分课后习题答案 P(a)Q(b)，取值1，因此，$aD P(a)取值1。 ($x)P(x)取值1，由定义，蕴含关系成立。 ($x)P(x)Q(a)($x)P(x)Q(a) ($x)P(x)Q(a) (2) 证: 在某个解释下，($x)P(x)Q(a)取值1 即($x)P(x)Q(a)取值0，分二种情况： i)($x)P(x)=0，则无论Q(a)为何值，($x)P(x)Q(a)取值1。 ii) Q(a)=0($x)P(x)=1，则($x)P(x)Q(a)取值1 由定义，蕴含关系成立。 习题 2.5 1 ($x)P(x)Q(x) P (x)P(x)

11、Q(x) T,E (x)(P(x)Q(x) T,I (x)(P(x)Q(x) T,I P(x)Q(x) US P(x) T,I (x)P(x) UG (x)P(x)(x)Q(x) P (x)Q(x) T,I Q(x) T,I 11Q(x) US 9 离散数学部分课后习题答案 离散数学部分课后习题答案 12 T11I 2. (1) 错误，应换元，即 (x)P(x)Q(x)， P(y)Q(x) 正确 错误，a、b应是同一个常元 错误，因为在P(x)($x)Q(x)R(x) 中x并不是自由出现 (5) 错误，因为在($x)P(x)Q(x)中，前件是命题， 而后件不是命题 错误，因为a、b并不是同一个

12、常量 错误，和的顺序不对 应先使用ES，再使用US 3(1)解：设F(x,y):xy; G(z):z0 ; f(x,y)=x-y 前提： (x)(y) 证明： (x)(y) G(f(a,b) G(f(b,a) 10 离散数学部分课后习题答案 离散数学部分课后习题答案 (x)(y) 证：首先，将结论否定否作为前提加入到原有前提中 ($x)P(x)(x)(P(x)Q(x)R(x)($x)P(x)($x)Q(x) ($x)($y)R(x)R(x) (x)P(x)(x)(P(x)Q(x)R(x)($u)P(u)($v)Q(v) ($w)($y)R(w)R(y) (x)($u)($v)(w)(y)(P(

13、x)R(x)(P(x)Q(x)R(x) P(u)R(u)(R(w)R(w) (x)(w)(y)(P(x)R(x)(P(x)Q(x)R(x)P(a)Q(b) (R(w)R(y) Skolem 范式 子句集为P(x)R(x),P(x)Q(x)R(x),P(a),R(b),R(w)R(y) P(x)R(x) P(a) 11 离散数学部分课后习题答案 离散数学部分课后习题答案 R(x) ,代换a/x R(c) 代换c/x R(w)R(y) R(y) ,代换c/w R(c) 代换c/y 习题 3.3 5、 (1)x2AU2Bx2A或x2BxA或xBxAUB x2AUB等号成立的条件为：AIB=f“”x2

14、AI2Bx2A和x2BxA和xBxAIBx2AIB“”如x2AIB，由于上述过程可逆x2AI2B习题 4.2 2. 关系 性质 自反性 R1 R2 R3 R4 R5 反自反性 对称性 反对称性 传递性 习题 4.3 12 离散数学部分课后习题答案 离散数学部分课后习题答案 2. “”R是对称的，设QR-1x,yR则 y,xRx,yR-1 RR，即R-1=R x,yR，由R-1“” R=R-1的定义，y,xR-1 y,xR，即R是对称的。 “”R是传递的，对R2 $yA 即R2R RRR “”R2R，对R有R2RR，由R的定义， 2R，即R是可传递的。 4. 解：QR=R1UR2，且R1IR2=

15、F Rm=Rm1URm23R1=IA15R2=IA2,A=A1UA2 需3|m，5|m m=15，即 n=16 1616R16=R1UR2=R1UR2=R 故使Rm=Rn的最小正整数m=1,n=16 习题 4.4 2、解： 0010MR=00001000010000000001000000000000Mt(R)0010000 0100000010000000001001110=000013 1110111000010001000100010011110011110011110011110001 1111离散数学部分课后习题答案 离散数学部分课后习题答案 iR3. (3)证：Qt(R1)=iU=

16、11t(R1UR2)=U(R1UR2)i i=1+it(R2)=UR i=12由归纳法可证：对 iNiiRUR(R1UR2)i 12iiiiUUR=U(RUR)U(R1UR2)i=t(R1UR2) t(R1)Ut(R2)=URi=11i=12i=112i=1(4)证：(R+)=R+QR=t(R)=URi i=1+(R)(R)+=(t(R)=U(t(R)j +j=1由归纳法可证：jN+j(t(R)j=t(R) =U(t(R)=U(t(R)=t(R)=R+ j=1j=1RoR*=R+QR*=IAUt(R) RoR*=Ro(IAUt(R)=RoIAURot(R) =RURot(R)=t(R)=R+

17、习题 5.1 1. 证：QA=(a,b)|a,bN+ R=(a,b),(c,d)|ad=bc 自反性 由A的定义，ab=baa,bN (a,b),(a,b)R 对称性 设(a,b),(c,d)R，则ad=bc 即 cb=da(c,d),(a,b)R 传递性 设(a1,b1),(c1d1)R，则a1d1=b1c1 14 离散数学部分课后习题答案 离散数学部分课后习题答案 (c1,d1),(c2d2)R，则c1d2=d1c2 a1d1d2=b1c1d2=b1d1c2a1d2=b1c2 (a1,b1),(c2,d2)R 3. 解：QA=1,2,3,4, S0=1,2,4,3 设A1=1,2,3,4,

18、A2=3 (1，(1，(2，(2，(4，(4，(4，(3，R=(1，1)，2)，4)(2，1)，2)，4)，1)，2)，4)，3) 4. 解：每个集合的划分就可以确定一个等价关系 集合有多少个划分就可以确定多少个等价关系 4321C+C+C+C=15种。 44445. 解： R1UR2不是A上的等价关系 R1R2是A上的等价关系 r(R1-R2) 是A上的等价关系 R1oR2不是A上的等价关系 习题 5.2 2. 解：A=a,b,c 2A=F,(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c) a,b,c a,b a,c a F Cb b,c c 3. 解：集合A上的空

19、关系F、恒等关系IA都是等价关系和偏序关系。 15 离散数学部分课后习题答案 离散数学部分课后习题答案 6. 证：i）自反性，对bBA,显然(b,b)BB (b,b)R，(b,b)RI(BB) ii)反对称性，对a,bB,(a,b)RI(BB),(b,a)RI(BB) 即(a,b)R,(b,a)R，由R的反对称性，a=b iii)传递性，对a,b,cB，设(a,b)RI(BB),(b,c)RI(BB)， 则(a,b)R，(b,c)R。 由R的传递性，(a,c)R，显然(a,c)BB (a,c)RI(BB) 习题 5.3 2. 解：A=(a,b,c,d) 2A=F,(a),(b),(c),(d)

20、,(a,b),(a,c),(a,d),(b,c),(b,d),(c,d),(a,b,c),(a,b,d),(b,c,d),(a,c,d),(a,b,c,d)F(a)(b)(c)(d)(a,b)(a,c)(a,d)(b,c)(b,d)(c,d)(a,b,c)(a,b,d)(a,c,d)(b,c,d)(a,b,c,d) 习题6.2 4、证： 1）对b1、b2B，b1b2 Qf(x)是满射，$a1、a2A,f(a1)=b1,f(a2)=b2 由g(x)的定义，a1g(b1),a2g(b2)，且a1g(b2),a2g(b1) 否则，如 a1g(b2), a2g(b1)，有 f(a1)=b2, f(a2

21、)=b与函数的定义相矛盾， g(b1)g(b2), 即g(x)为单射 2）而g(x)为单射时，对bB,并不能保证 g(b)f,f(x)不一定是满射习题6.3 16 离散数学部分课后习题答案 离散数学部分课后习题答案 4、证： f:AB,g:BC 反证法：设不是单射 $，x1x2A,f(x1)=f(x2) 即gof(x1)=g(f(x1)=g(f(x2)=gof(x2) 与gof为单射矛盾Qgof为满射 对zC, $xA, gof(x)=g(f(x)=z 令f(x)=yB $ yB, g(y)=z 即g为满射(3)由的结论可得习题10.1 1、Q G=(n,m) 由Euler定理 2m=d(k)

22、 d(k)表示第k个结点的度数k=1nQ2m=d(k)(n-1)k=1k=1nn(G是简单图，d(k)n-1,等号成立当且仅号G是完全图时）n(n-1)2 2mn(n-1) 即 =Cn23、解：不是图的序列，因为奇数度结点的 个数不是偶数。 、都是图的序列。 4、证： 习题10.3 由欧拉定理， 2m=d(v)vGQdd(v)DvGvGvGndd(v)=2mnDvG2mdDn17 离散数学部分课后习题答案 离散数学部分课后习题答案 1、证：设v与u不连通 G=V1，V2 ，v与u分别属于V1，V2二个子图 v与u是G中仅有的二个奇数度结点 v与u即是V1与V2中仅有的一个奇数度结点，与 欧拉定

23、理的推论相矛盾，故v与u必连通 3、证： n=2时, m0 二个结点至少有一条边，即G是连通图 1设 n=k 时，结论成立,即 时， G是连通图 m(k-1)(k-2) 21证n=k+1时，结论成立，即 mk(k-1)时， G是连通图 2 如果G是非连通图，必存在一个结点v，使1d(v)k(k-1)矛盾；22完全图，与假设矛盾） 从G中删除该结点v所得子图G=G-v 11其边数 mm-(k-1)2k(k-1)-(k-1)=2(k-1)(k-2)由归纳假设，G=G-v的结点数为k，所以G是简单图， G=G+v ，G连通 故由归纳法，结论成立 习题10.4 3、解： e1v1e2e3v3v6e9e

24、5e6v5e8e10e11e12e7v2e4v4v7v5 v6 v7v1 v2 v3 v4 0 1 1 0 0 0 00 0 0 1 0 0 00 0 0 1 1 0 0A=1 0 1 0 1 0 00 0 0 0 0 00 0 0 0 0 1 0 10 0 0 0 1 1 0v1 v2 v3 v4 v5 v6 v71 1 1 1 1 0 01 1 1 1 0 0 1 1 1 1 1 1 0 0P= 1 1 1 1 1 0 00 0 0 0 0 0 0 0 0 0 0 1 1 10 0 0 1 1 10 PQPT18 v1 v2 v3 v4 v5 v6 v71 1 1 1 0 0 01 1 1

25、 1 0 0 01 1 1 1 0 0 0=1 1 1 1 0 0 00 0 0 0 1 0 00 0 0 0 0 1 1 0 0 0 1 0 0离散数学部分课后习题答案 1离散数学部分课后习题答案 三个强分图 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e121 1 -1 0 0 0 0 0 0 0 0 0-1 0 0 1 0 0 0 0 0 0 0 00 -1 0 0 1 -1 1 0 0 0 0 0MG=0 0 1 -1 -1 1 0 1 0 0 0 00 0 0 0 0 0 -1 -1 -1 -1 0 00 0 0 0 0 0 0 0 1 0 -1 11 1

26、-10 0 0 0 0 0 0 0 0 习题11.1 1、解：设L是叶的数目，m是树的边数 由Euler定理 knk+L=2mk=2 im=nk+L-1 由树的定义 k=2iknk+L=2nk+2L-2k=2k=2iiL=(k-2)nk+2 (ik2)k=2i2、证明： 习题11.3 6、证明：由正则二叉树的定义，其叶结点的个数必为偶数，设叶数为t，分支数为i 由定理10-2.1 (m-1)i=t-1 m=1 i=t-1 有分支点数是奇数 故结点数=i+t=奇数 习题12.2 1、证： 设G=和G=都是平面图 由G的定义 m+m=n(n-1)/2 由定理10-4.2 m3n-6 , m3n-6

27、 m+m=n(n-1)/2 6n-12 有 n2-13n+24=(n-11)2+9n-97 0 又 设所有顶点的度数5 由Euler公式， 由定理10-4.2 m3n-6 3n-65n/2 即n12 则 m5n/2512/2=30 与 m30矛盾 至少存在一个顶点的度数不超过4 习题13.2 2、证： G是2k正则图， 对任意的u、vG，d(u)+d(v)=4k 由定理10-6-2 在G中存在一条Hamilton道路，设为： v1v2,v4k+1 1) v1v4k+1E， 则v1v2,v4k+1v1构成一个Hamilton圈 2) v1v4k+1 E， 则$vi1,vi2,L,vi2k与v1邻

28、接 G的阶数为4k+1 v4k+1必与vi1-1,vi2-1,L,vi2k-1中的一个点邻接， 假设G不是哈密尔顿图，则 $s,tG,deg(s)+deg(t)nQ2m=deg(v)=v)+deg(s)+deg(t) deg(vGvG-s,t2mvG-s,tv)+deg(n因为G除结点s,t外的其余n-2结点之间最多可以构成完全 图，所以 2m(n-2)(n-3)+n+nn2-3n+6=(n-1)(n-2)+4 从而 12 m(n-1)(n-2)+2=Cn-1+2 22mCn-1+220 离散数学部分课后习题答案 离散数学部分课后习题答案 与已知 矛盾，故结论成立。 习题15.1 4、证： 设

29、$aA,aaa 构造 b=aa ，则 ab=aaa=ba 即 a、b可交换，与已知条件相矛盾 aA，aa=a 习题15.2 1、证明：群中只有幺元是幂等元。 证： 设$aA,ae,a2=a，Qa-1 $, a=a2a-1=aa-1=e 矛盾 5、写出s,o中的全部子群。 3解：， ，和二个平凡子群。 6、证明：1） S、T是G的子群 eS , eT 即 eS T 设 a，bS T，即a，bS 和a，bT b-1 S 和b-1T ab-1 S 和ab-1T 即 ab-1 ST ST，是G的子群 2） eST，设c、dST 则 $ a1S，b1T ， c=a1b1， $ a2S，b2T ， d=a

30、2b2， d-1=b2-1a2-1 又 S和T中的元素关于“” 可交换 cd-1= a1b1b2-1a2-1= a1a2-1b1b2-1 ST 即 ST是子群 习题15.3 2、证明：设G是阶数大于1的群， 21 离散数学部分课后习题答案 离散数学部分课后习题答案 则 $ aeG 构造G=e,aG， 则 G是G的交换群。 3、证明： 设 G=(a),G是G的子群，则G中的每个元素具有am的形式，设k是所有m中最小的正整数，则 G= 即 (a)=e,a,a2 或 (a)=e Q G=U(a)aG G 的阶数n必是奇数 习题16.2 5、证：1）对任何 aR，由已知 对 由定理16-1.1， 2222） (a*b)=a*b=a*b 由定理15-3.1 R，*为交换半群 故R，+，*为交换环 22 离散数学部分课后习题答案