离散数学课后习题问题详解

《离散数学课后习题问题详解》由会员分享，可在线阅读，更多相关《离散数学课后习题问题详解（32页珍藏版）》请在装配图网上搜索。

1、word习题参考解答习题1.1 1、3P：银行利率降低 Q：股价没有上升PQ5P：他今天乘火车去了 Q：他随旅行团去了九寨沟7 P：不识庐山真面目 Q：身在此山中QP，或 PQ9P：一个整数能被6整除 Q：一个整数能被3整除 R：一个整数能被2整除T：一个整数的各位数字之和能被3整除PQR ，QT2、1T 2F 3F 4T 5F 6T 7F 8悖论1342、不，不，能 主合取式主析取式3、解：根据给定的条件有下述命题公式：ACDBCCDACDCDBCCDABCDBCDBACCDCCDCCDABCDBCDB ACCDCCDABCCDBCCDBCACCCDCCABDCDBDCDBDACDCDCD由

2、题意和矛盾律CDBACCDCDBCDBA CDBA ACBACB CDA CDACDBACDBACDBA ACBD ACBDACBD ACBD CDAB CDAB CDAB CDABCDBACDBACDBA ACBD CDABCDAB CDBACDBA ACBDCDBA三种方案：A和D、B和D、A和C1、 1需证为永真式3需证为永真式为永真式。即永真永真当且仅当4、设：P：珍宝藏在东厢房Q：藏宝的房子靠近池塘R：房子的前院栽有大柏树S：珍宝藏在花园正中地下t：后院栽有香樟树m：珍宝藏在附近后院命题化后进展推理：即S为真，珍宝藏在花园正中地下5、(1)F (P=0,Q=1) (2)F (P=1,

3、Q=R=0) (3)F (P=0,Q=1)1.1证：利用CP规如此 P P(附加前提)II 结论成立 CP规如此2 证：(附加)PQ TSE TSEB P()2. (2) P：无任何痕迹 Q：失窃时，小花在OK厅 R：失窃时，小英在OK厅 S：失窃时，小胖在附近 T：金刚是偷窃者M：瘦子是偷窃者命题可符号化为：证：金刚是窃贼。3. (1) 不相容 (2) 相容 3不相容 4不相容4. (1)证：即 利用消解原理：PPP1. (1)：是实数 ：是有理数(2)：是直线：与平行：与相交(3)：是会员：有意义：参加：这个活动或者4：是正整数：是合数：是质数5：是人Bx：x存钱a：利息 P:存钱有利息

4、：想有2.(1)(2)4.(1)1.1D：数 可满足式(2)是诚实的人讲实话a：小林可满足式 (3)不廉价是好货买的a：衣服b：小王可满足式4是作家 懂得人性本质是诗人是真正的能刻画人们心世界很高明创作了a：莎士比亚b：哈姆雷特2.(1)3.(1) (2)4. 1.12. 不成立D=0,1,2 3.(1)skolem式(2)前束式skolem式1. 1证：在某个解释下，取值1，必有,，取值1，因此，取值1。取值1，由定义，蕴含关系成立。2(2) 证: 在某个解释下，取值1即取值0，分二种情况：i)，如此无论为何值，取值1。ii)，如此取值1由定义，蕴含关系成立。12反证法PT,ET,IT,IU

5、ST,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

6、,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/y3、2. 关系性质R1R2R3R4R5自反性反自反性对称性反对称性传递性2. 3“R

7、是对称的，设如此 ，即“ ，由的定义，即R是对称的。5“R是传递的，对即“，对，由R2的定义，有，即R是可传递的。4. 解：，且需3|m，5|m，即故使的最小正整数2、解：3. (3)证：由归纳法可证：对(4)证：由归纳法可证：1. 证：自反性 由A的定义，对称性 设，如此即 传递性 设，如此，如此3. 解：设4. 解：每个集合的划分就可以确定一个等价关系集合有多少个划分就可以确定多少个等价关系种。5. 解：不是A上的等价关系是A上的等价关系 是A上的等价关系不是A上的等价关系2. 解：Fabca,ba,cb,ca,b,c3. 解：集合A上的空关系、恒等关系IA都是等价关系和偏序关系。6. 解

8、：7. 证：i自反性，对，的自反性显然ii)反对称性，对即，由R的反对称性，iii)传递性，对，设，如此，。由R的传递性，显然4、证：7、证：习题6.4:3证明：非空有限集A与可数集B的笛卡尔积AB也是可数集。证明：设A=a1,a2,anB=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

9、c12 c22 c13 c23 c1(n/2) c2(n/2) 所以2个可数集的并集为可数集。假设m=k-1(k3)时结论成立，即k-1个可数集的并集为可数集，记为D。如此m=k时，可以构造类似的双射g:NDCk,所以为可数集。因而有限个可数集的并集为可数集。所以AB是可数集。1设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假如，

10、称G是自补图。确定一个图为自补图的最低条件；画出一个自补图来。解：设G=(n,m)，G=(n,m)如此m+m=n(n-1)/2,所以m=m=n(n-1)/4v2v1v3v4Gv2v1v3v41、假如u和v是图中仅有的两个奇度数结点，证明u和v必是连通的。证：反证法设v与u不连通G=V1，V2 ，v与u分别属于V1，V2二个子图 v与u是G中仅有的二个奇数度结点v与u即是V1与V2中仅有的一个奇数度结点，与欧拉定理的推论(9-相矛盾,故v与u必连通3、设(n,m)简单图G满足m(n-1)(n-2)/2，证明G必是连通图。构造一个m=(n-1)(n-2)/2的非连通简单图。书上证明更好5、设G=(

11、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时

12、结论成立，当n=k+1时，设v1、vk是Pk上的两个非割点，vk+1是在Pk上增加的一个割点，如果结点vk+1不在Pk上的任意两个结点之间，如此必与Pk上某两个结点构成一个回路，vk+1就不是割点，与只有两个非割点矛盾。故结论成立。3、解：三个强分图5.证明：支数为k，阶数为n的无环图G，其关联矩阵的秩是n-k.证明：将各支结点和边集中编号后，G的关联矩阵由分块矩阵子公式与定理，(M)=(M1)+(M2)+(Mk) =(n1-1)+(n2-1)+(nk-1) =n-k1、设一个树中度为k的结点数是nk，求它的叶的数目。解：设L是叶的数目，m是树的边数,由Euler定理:由树的定义:6、证明正如

13、此二叉树必有奇数个结点。证明：由正如此二叉树的定义，其叶结点的个数必为偶数，设叶数为t，分支数为i。： (m-1)i=t-1 m=1 i=t-1 有分支点数是奇数故结点数=i+t=奇数3、证：反证法设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。证：

14、由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。2、证明：4k+1阶的所有2k正如此简单图都是哈密顿图。证： G是2k正如此图， 对任意的u、vG，d(u)+d(v)=4k由定理10-6-2 在G中存在一条Hamilton道路，设为：v1v2,v4k+11)

15、v1v4k+1E， 如此v1v2,v4k+1v1构成一个Hamilton圈2) v1v4k+1E， 如此 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,

16、cS使ba=e(或ac=e),如此称b是a的左逆元(或c是a的右逆元)。证明：如果一个元既有左逆元b又有右逆元c，如此必b=c.证明：S上的运算是可结合的。 b=be=b (a c)=(b a) c=e c=c4、设半群中任何两个不同元素关于运算“不可交换，证明：对任何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,(1

17、010)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)m1111010001、证明：群中只有幺元是幂等元。证：反证法矛盾 设，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 和

18、a，bTb-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+

19、i=ajai)对于 4阶群 G, 假如G中有4阶元素, 设为a, 如此G=( a), G是交换群; 假如 G 中无 4 阶元, 如此由拉格朗日定理, G只可能含1阶元和2阶元. G也 是交换群 2、证明：设G是阶数大于1的群， 如此 $ aeG 构造G=e,aG， 如此 G是G的交换群。3.循环群的子群必是循环群证明：设是循环群，a是生成元，是子群。设H1=ai|iZ+,aiHHG,记H1中所有元素ai的幂指数中最小的是ar，如此=(ar)。这是因为，对xH,x可表示成an(nZ+。设n=pr+t(0tr-1)，假定t0,如此有at=an-pr=an-pr=an(ar)-pH这与r 的最小性相

20、矛盾，因此t=0，n=pr,x=an=(ar)p，所以是以ar为生成元有循环群。5、证明：习题11.5:4.证明下述结论：(1)群中指数为2的子群是正规子群。(2)两个正规子群S和T的交ST仍是正规子群。证明：(1)设群G的子群H的指数为2，如此H有两个左陪集H1、H2，H1H2，而且其中必有一个是H。假设H1=H，对aG，假如aH=H,如此Ha=HaG，假如aH=H2,如此HaH，故Ha=H2所以aH=Ha，即H是正规子群。(2) aST，对xG，有xax-1S且xax-1T，即xax-1ST，所以x(ST)x-1ST.习题11.77、证：1对任何 aR， a*a=a (a+a)*a=a*a+a*a=a+a=a*(a+a) a+a=q2 (a*b)2=a*b=a2*b2 由定理11-4.1 R，*为交换半群 故R，+，*为交换环32 / 32