习题参考解答.doc

离散数学部分课后习题答案离散数学部分课后习题答案习题1.1 1、（3）P：银行利率降低 Q：股价没有上升 PQ（5） P：他今天乘火车去了北京 Q：他随旅行团去了九寨沟 （7） P：不识庐山真面目 Q：身在此山中 QP，或 PQ（9） P：一个整数能被6整除 Q：一个整数能被3整除 R：一个整数能被2整除 T：一个整数的各位数字之和能被3整除 PQR ，QT2、（1）T （2）F （3）F （4）T （5）F （6）T （7）T（F） （8）悖论习题 1.31、（3） （4）2、不，不，能习题 1.42、 PQPPQPP（PQ）（PQ）（PQ）（PQ）PPPP PQRPPQRPPPPPQQRRRRQQRRRRPPPPPPQQRRRRQQRRRRPP 3、 PQPQ，而，是最小功能完备集，是最小功能完备集。又PQPcQ，c也是最小功能完备集。4、习题 1.5 主合取范式主析取范式3、解：根据给定的条件有下述命题公式：（A（CD）（BC）（CD）（A（CD）（CD）（BC）（CD）（AB）（CDB）（CDB）（AC）（CDC）（CDC）（CD）（AB）（CDB）（CDB） （AC）（CDC） （CD）（ABC）（CDBC）（CDBC）（ACC）（CDCC）（ABD）（CDBD）（CDBD）（ACD）（CDCD）（由题意和矛盾律可得下式） （CDB）（AC）（CD）（CDB）（CDBA） （CDBA） （ACB） （ACB） （CDA） （CDA）（CDBA）（CDBA）（CDBA） （ACBD） （ACBD） （ACBD） （ACBD） （CDAB） （CDAB） （CDAB） （CDAB）（CDBA）（CDBA） （由题意可得下式） （CDBA） （ACBD） （CDAB） （CDAB） （CDBA）（CDBA） （ACBD）（CDBA）三种方案：A和D、B和D、A和C习题 1.61、 （1）需证为永真式（3）需证为永真式为永真式。即永真永真当且仅当4、设：P：珍宝藏在东厢房Q：藏宝的房子靠近池塘R：房子的前院栽有大柏树S：珍宝藏在花园正中地下t：后院栽有香樟树m：珍宝藏在附近（后院）命题化后进行推理：即S为真，珍宝藏在花园正中地下5、(1)F (P=0,Q=1) (2)F (P=1,Q=R=0) (3)F (P=0,Q=1)习题 1.71.（1）证：利用CP规则 P P(附加前提) I I 结论成立 CP规则（2） 证： (附加) PQ T SE T SEB P ()2. (2) P：无任何痕迹 Q：失窃时，小花在OK厅 R：失窃时，小英在OK厅 S：失窃时，小胖在附近 T：金刚是偷窃者M：瘦子是偷窃者命题可符号化为：证：金刚是窃贼。3. (1) 不相容 (2) 相容 （3）不相容 （4）不相容4. (1)证：即 利用消解原理：P P P 习题 2.11. (1)：是实数 ：是有理数 (2)：是直线：与平行：与相交(3)：是会员 P: 这个活动有意义：参加活动或者（4）：是正整数：是合数：是质数（5）：是存钱的人B（x）：x想有利息P:存钱没有利息 Q：人们不存钱xAxBx PQ 2.(1)(2)4.(1)习题 2.21.（1）D：数 可满足式(2)是诚实的人，讲实话，a：小林T (3) 不便宜，是好货，a：小王买的衣服T（4）是懂得人性本质的作家 是真正的诗人能刻画人们内心世界很高明创作了a：莎士比亚b：哈姆雷特xAxDxxCxBxPa,b xCxAxxPx,bBxDa T2.(1) 3.(1) (2) 4. 习题 2.31.（1）2. 不成立D=0,1,2 3.(1) skolem范式(2) 前束范式 skolem范式习题 2.41. （1）证：在某个解释下，取值1，必有,，取值1，因此， 取值1。取值1，由定义，蕴含关系成立。（2）(2) 证: 在某个解释下，取值1即取值0，分二种情况：i)，则无论为何值，取值1。ii) ，则取值1由定义，蕴含关系成立。习题 2.51（2）（反证法）PT,ET,IT,IUST,IUGPT,IT,I USTI2. (1) 错误，应换元，即， （2） 正确 （3） 错误，a、b应是同一个常元 （4） 错误，因为在 中x并不是自由出现(5) 错误，因为在中，前件是命题，而后件不是命题（6） 错误，因为a、b并不是同一个常量（7） 错误，和的顺序不对应先使用ES，再使用US3(1)解：设F(x,y):xy; G(z):z0 ; f(x,y)=x-y前提： (x)(y)（F(x,y)G(f(x,y) (x)(y)（F(x,y)G(f(x,y) (x)(y)(G(f(x,y) G(f(y,x)结论： (x)(y)（G(f(x,y)G(f(y,x)）证明（反证法）： (x)(y)（G(f(x,y)G(f(y,x)） （$）（$）（G(f(x,y)G(f(y,x)） G(f(a,b) G(f(b,a) (x)(y)（F(x,y)G(f(x,y) F(a,b)G(f(a,b) G(f(a,b)F(a,b) (x)(y)(G(f(x,y) G(f(y,x) G(f(b,a)G(f(a,b) (x)(y)（F(x,y)G(f(x,y) F(a,b)G(f(a,b) G(f(a,b) F(a,b) F(a,b) F(a,b)4. （2）证：首先，将结论否定否作为前提加入到原有前提中 Skolem 范式子句集为,代换a/x代换c/x,代换c/w代换c/y习题 3.35、习题 4.22. 关系性质R1R2R3R4R5自反性反自反性对称性反对称性传递性习题 4.32. （3）“”R是对称的，设则 ，即“” ，由的定义，即R是对称的。（5）“”R是传递的，对即“”，对，由R2的定义，有，即R是可传递的。4. 解：，且需3|m，5|m，即 故使的最小正整数习题 4.42、解：3. (3)证：由归纳法可证：对(4)证：由归纳法可证：习题 5.11. 证：自反性 由A的定义， 对称性 设，则即 传递性 设，则，则3. 解：设4. 解：每个集合的划分就可以确定一个等价关系集合有多少个划分就可以确定多少个等价关系种。5. 解：不是A上的等价关系 是A上的等价关系 是A上的等价关系 不是A上的等价关系习题 5.22. 解： Fabca,ba,cb,ca,b,c3. 解：集合A上的空关系、恒等关系IA都是等价关系和偏序关系。6. 证：i）自反性，对，（的自反性）显然ii)反对称性，对即，由R的反对称性，iii)传递性，对，设，则，。由R的传递性，显然习题 5.32. 解：习题6.24、证： 习题6.34、证：习题10.11、3、解：（1）不是图的序列，因为奇数度结点的个数不是偶数。（2）、（3）、（4）都是图的序列。4、证：习题10.31、证：（反证法）设v与u不连通G=V1，V2 ，v与u分别属于V1，V2二个子图 v与u是G中仅有的二个奇数度结点v与u即是V1与V2中仅有的一个奇数度结点，与欧拉定理的推论相矛盾，故v与u必连通3、证：（归纳法，对n进行归纳） n=2时, m0 二个结点至少有一条边，即G是连通图设 n=k 时，结论成立,即 时， G是连通图证n=k+1时，结论成立，即 时， G是连通图（用反证法）如果G是非连通图，必存在一个结点v，使1d(v)k(否则，如d(v)=0，则G-v是一个有k个结点的简单图，其边数 与 矛盾；如d(v)=k,则G是一个完全图，与假设矛盾）从G中删除该结点v所得子图G=G-v其边数由归纳假设，G=G-v的结点数为k，所以G是简单图，G=G+v ，G连通 故由归纳法，结论成立 习题10.43、解：三个强分图习题11.11、解：设L是叶的数目，m是树的边数 由Euler定理 由树的定义2、证明：习题11.36、证明：由正则二叉树的定义，其叶结点的个数必为偶数，设叶数为t，分支数为i由定理10-2.1 (m-1)i=t-1 m=1 i=t-1 有分支点数是奇数 故结点数=i+t=奇数习题12.21、证：（反证法）设G=（n，m）和G=（n，m）都是平面图由G的定义 m+m=n(n-1)/2 由定理10-4.2 m3n-6 , m3n-6 m+m=n(n-1)/2 6n-12有 n2-13n+24=(n-11)2+9n-97 0又（n-11)2 0，n 11时,9n-97 2 （n-11)2 +9n-97 2与上式相矛盾， 故G与G至少有一个是非平面图2、证：由Euler公式，n-m+f=2 6-12+f=2 f=8 即面数为8，对每个面，其度数 3总面度38=24总面度=2m=24每个面的度数为33、证：（反证法）设所有顶点的度数5由Euler公式，由定理10-4.2 m3n-63n-65n/2 即n12则 m5n/2512/2=30 与 m30矛盾 至少存在一个顶点的度数不超过4习题13.22、证： G是2k正则图， 对任意的u、vG，d(u)+d(v)=4k由定理10-6-2 在G中存在一条Hamilton道路，设为： v1v2,v4k+11) v1v4k+1E， 则v1v2,v4k+1v1构成一个Hamilton圈2) v1v4k+1 E， 则 G的阶数为4k+1 （否则d(v4k+1)=4k-1-2k=2k-1与d(v4k+1)=2k矛盾)设 ，可构造即为G的一个Hamilton圈，故G是一个Hamilton图5、证：（反证法）假设G不是哈密尔顿图，则因为G除结点s,t外的其余n-2结点之间最多可以构成完全图，所以 2m(n-2)(n-3)+n+nn2-3n+6=(n-1)(n-2)+4从而与已知 矛盾，故结论成立。 习题15.14、证：（反证法） 设 构造 ，则 即 可交换，与已知条件相矛盾 习题15.21、证明：群中只有幺元是幂等元。证：（反证法） 设，矛盾5、写出中的全部子群。解：（1），（1 2），（1），（1 3），（1），（2 3），（1），（1 2 3），（1 3 2）和二个平凡子群。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=a2b2， d-1=b2-1a2-1 又 S和T中的元素关于“” 可交换 cd-1= a1b1b2-1a2-1= a1a2-1b1b2-1 ST 即 ST是子群习题15.32、证明：设G是阶数大于1的群， 则 $ aeG 构造G=e,aG， 则 G是G的交换群。3、证明： 设 G=(a