离散数学课后习题答案

习题参考解答习题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）F （8）悖论习题 1.31（3）（4）2、不，不，能习题 1.4 主合取范式主析取范式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.51、 （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.61.（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)：是会员：有意义：参加：这个活动或者（4）：是正整数：是合数：是质数（5）：是人B（x）：x存钱a：利息 P:存钱有利息 ：想有2.(1)(2)4.(1)习题 2.21.（1）D：数 可满足式(2)是诚实的人讲实话a：小林可满足式 (3) 不便宜是好货买的a：衣服b：小王可满足式（4）是作家 懂得人性本质是诗人是真正的能刻画人们内心世界很高明创作了a：莎士比亚b：哈姆雷特2.(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.43、习题 5.22. 关系性质R1R2R3R4R5自反性反自反性对称性反对称性传递性习题 5.32. （3）“”R是对称的，设则 ，即“” ，由的定义，即R是对称的。（5）“”R是传递的，对即“”，对，由R2的定义，有，即R是可传递的。4. 解：，且需3|m，5|m，即 故使的最小正整数习题 5.42、解：3. (3)证：由归纳法可证：对(4)证：由归纳法可证：习题 5.51. 证：自反性 由A的定义， 对称性 设，则即 传递性 设，则，则3. 解：设4. 解：每个集合的划分就可以确定一个等价关系集合有多少个划分就可以确定多少个等价关系种。5. 解：不是A上的等价关系是A上的等价关系 是A上的等价关系不是A上的等价关系习题 5.62. 解：Fabca,ba,cb,ca,b,c3. 解：集合A上的空关系、恒等关系IA都是等价关系和偏序关系。6. 解：7. 证：i）自反性，对，（的自反性）显然ii)反对称性，对即，由R的反对称性，iii)传递性，对，设，则，。由R的传递性，显然习题6.24、证： 7、证：习题6.4:3证明：非空有限集A与可数集B的笛卡尔积AB也是可数集。证明：设A=a1,a2,an B=b1,b2,bn,令Bi =(ai,b1),(ai,b2),(ai,bn), (in),则 AB= ,因为B为可数集，所以Bi为可数集。AB为有限个可数集的并集。下面用归纳法证明有限个(m个)可数集的并集为可数集。设Cm=cm1,cm2, ,cmn, 当m=2时，构造双射f:NC1C2, N 1 2 3 4 5 6 n-1 n f(N) c11 c21 c12 c22 c13 c23 c1(n/2) c2(n/2) 所以2个可数集的并集为可数集。假设m=k-1(k3)时结论成立，即k-1个可数集的并集为可数集，记为D。则m=k时，可以构造类似的双射g:NDCk,所以为可数集。因而有限个可数集的并集为可数集。所以AB是可数集。习题9.11设G是一个(n,m)简单图。证明：m ,等号成立当且仅当G是完全图.证明：由欧拉定理，2m= ，d(k)表示第k个结点的度因为G是简单图，所以d(k) n-1,等号成立当且仅当G是完全图2m= ,所以 2mn(n-1)即 m =3、解：（1）不是图的序列，因为奇数度结点的个数不是偶数。（2）、（3）、（4）都是图的序列。4、证：9若，称G是自补图。确定一个图为自补图的最低条件；画出一个自补图来。解：设G=(n,m)，G=(n,m)则m+m=n(n-1)/2,所以m=m=n(n-1)/4v2v1v3v4Gv2v1v3v4习题9.21、若u和v是图中仅有的两个奇度数结点，证明u和v必是连通的。证：（反证法）设v与u不连通G=V1，V2 ，v与u分别属于V1，V2二个子图 v与u是G中仅有的二个奇数度结点v与u即是V1与V2中仅有的一个奇数度结点，与欧拉定理的推论(9-1.1.1相矛盾,故v与u必连通3、设(n,m)简单图G满足m(n-1)(n-2)/2，证明G必是连通图。构造一个m=(n-1)(n-2)/2的非连通简单图。（书上证明更好）5、设G=(V，E)是点度均为偶数的连通图。证明：对任何vV,(G-v)d(v)/2证：（反证法）设结论不成立，即存在: vV,(G-v) d(v)/2.因为G是连通的，所以G-v的每个分支都至少有一个点与v相邻接，而且存在一个分支，其与v相邻接的点只有一条边与v相连（因为如每个分支中有二个以上的点与v相连，则 ，出现矛盾）存在一个分支，其中只有一条边与v相连；因为G中每个结点的度数为偶数，所以在这个分支中就会出现一个奇度数结点，其余结点的度数全为偶数，与欧拉定理的推论相矛盾，故故对任何vV,(G-v)d(v)/29.证明：恰有两个非割点的简单连通图必是Pn(n2)证明：归纳法。n=2时，结论显然成立。设n=k时结论成立，当n=k+1时，设v1、vk是Pk上的两个非割点，vk+1是在Pk上增加的一个割点，如果结点vk+1不在Pk上的任意两个结点之间，则必与Pk上某两个结点构成一个回路，vk+1就不是割点，与只有两个非割点矛盾。故结论成立。习题9.33、解：三个强分图5.证明：支数为k，阶数为n的无环图G，其关联矩阵的秩是n-k.证明：将各支结点和边集中编号后，G的关联矩阵由分块矩阵子公式及定理9-3.2， (M)=(M1)+(M2)+(Mk) =(n1-1)+(n2-1)+(nk-1) =n-k习题10.11、设一个树中度为k的结点数是nk，求它的叶的数目。解：设L是叶的数目，m是树的边数,由Euler定理: 由树的定义:习题10.26、证明正则二叉树必有奇数个结点。证明：由正则二叉树的定义，其叶结点的个数必为偶数，设叶数为t，分支数为i。由定理10-2.1： (m-1)i=t-1 m=1 i=t-1 有分支点数是奇数故结点数=i+t=奇数习题10.43、证：（反证法）设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至少有一个是非平面图4、证明：具有6个结点，12条边的简单连通平面图，它的面度都是3。证：由Euler公式，n-m+f=2 6-12+f=2 f=8，即面数为8。对每个面，其度数 3总面度38=24总面度=2m=24每个面的度数为35、少于30条边的简单平面图至少有一个顶点的度不大于4。证：（反证法）设所有顶点的度数5由Euler公式，由定理10-4.2 m3n-63n-65n/2 即n12则 m5n/2512/2=30 与 m30矛盾 因此，至少存在一个顶点的度数不超过4。习题10.62、证明：4k+1阶的所有2k正则简单图都是哈密顿图。证： 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是(n,m)简单图，若 ,证明G必是哈密顿图。证：（反证法）假设G不是哈密尔顿图，则因为G除结点s,t外的其余n-2结点之间最多可以构成完全图，所以 2m(n-2)(n-3)+n+nn2-3n+6=(n-1)(n-2)+4从而：与已知 矛盾，故结论成立。 习题11.1：4.设是一个含有幺元e的代数系统，aS.如果存在元b,cS使ba=e(或ac=e),则称b是a的左逆元(或c是a的右逆元)。证明：如果一个元既有左逆元b又有右逆元c，则必b=c.证明：S上的运算是可结合的。 b=be=b (a c)=(b a) c=e c=c习题11.24、设半群中任何两个不同元素关于运算“”不可交换，证明：对任何aA,aa=a证明：（反证法） 设aA,使得a aa,构造b= a a ，则 ab= a a a =b a 即a、b 可交换，与已知条件相矛盾 aA, aa=a5.设S=00,111,1010是字符集=0,1上的字集合。试构造*的一个包含集合S的最小的含幺子半群。解：令空字符为.m,n,k为正整数，T=,(00)m,(111)n,(1010)k (00)m (111)n (1010)k (00)m (1010)k(111)n (111)n (00)m (1010)k (111)n (1010)k(00)m (1010)k(00)m (111)n (1010)k (111)n(00)m111101000习题11.31、证明：群中只有幺元是幂等元。证：（反证法）矛盾 设，5、写出中的全部子群。解：（1），（1 2），（1），（1 3），（1），（2 3），（1），（1 2 3），（1 3 2）和二个平凡子群。6、设和都是的子群，令ST=x|xSST,ST=st|sStT，证明：和也都是的子群。证明：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是子群习题11.41.阶数小于6的群必是交换群。证明：1阶群 是平凡的 , 显然是交换群.2, 3和5都是素数, 由拉格朗日定理的推论2可知, 2阶、 3阶和5阶群 都是由一个元素生成的 , 它们都 是交换群 . (ai,ajG,有aiaj=ai+j=aj+i=ajai)对于