《离散数学习题》由会员分享，可在线阅读，更多相关《离散数学习题（3页珍藏版）》请在金锄头文库上搜索。
1、集合论集合论1.1.A=A=,1,1，B=aB=a求求 A A 的幂集、的幂集、ABAB、ABAB、A+BA+B。 2.2.A=1,2,3,4,5,A=1,2,3,4,5, R=(x,y)|x,|xv=yu,R=,|xv=yu,证明：证明：R R 是等价关系。是等价关系。 19.19. f:Af:AB B，R R 是是 B B 上的等价关系，令上的等价关系，令 S=|xS=|x A A 且且 y y A A 且且 RR，证明：，证明：S S 是是 A A 上的等价关系。上的等价关系。 20.20. R R 是集合是集合 A A 上的自反关系，上的自反关系，S S 是是 A A 上的自反和对称关
2、系，上的自反和对称关系， 证明证明 t(RS)t(RS)是是 A A 上的等价关系。上的等价关系。 21.21. P P 和和 Q Q 都是集合都是集合 A A 上的划分，请问上的划分，请问 PQPQ，P-QP-Q 是否是是否是 A A 上的划分，上的划分， 22.22. R R AXA,RirrefAXA,Rirref且且 Rtra,Rtra,证明：证明：r(R)r(R)是是 A A 上的偏序关上的偏序关 系。系。 23.23. 画出画出1,2,3,4,61,2,3,4,6上整除关系的哈斯图，求上整除关系的哈斯图，求2,3,62,3,6的的 4 4 种元素。种元素。 24.24. A=a,b
3、,c,d,e,f,g,R=(a,c),(a,e),(b,d),(b,f),(d,A=a,b,c,d,e,f,g,R=(a,c),(a,e),(b,d),(b,f),(d, e),(d,f),S=tr(R),e),(d,f),S=tr(R),画出画出 S S 的哈斯图并求的哈斯图并求b,c,d,fb,c,d,f的极的极 大元等大元等 8 8 种元素。种元素。 25.25. f:AB,g:BCf:AB,g:BC 都是单（满）射，证明：复合映射都是单（满）射，证明：复合映射 gofgof 一定是单（满）射。一定是单（满）射。 26.26. f:AB,g:BCf:AB,g:BC，gofgof 是单射，
4、请问是单射，请问 f f 和和 g g 是否一定是单是否一定是单 射？请证明或举出反例。射？请证明或举出反例。 27.27. R R 是实数集，是实数集，f:Rf:RR RR RR,f()=,R,f()=,请问请问 f f 是否为单射？是否为满射？分别证明或举反例。是否为单射？是否为满射？分别证明或举反例。 28.28. 已知已知 BC=BC=, ,令令 f f：P(BC)P(BC)P(B)P(B)P(C)P(C)，对，对 X X P(BC),P(BC),令令 f(X)=(BX,CX),f(X)=(BX,CX),证明：证明：f f 是双射。是双射。代数系统代数系统 1.1. 是模是模 8 8
5、加群，加群，Z Z8 8=0,1,2,3,4,5,6,7,+=0,1,2,3,4,5,6,7,+8 8是模是模 8 8 加法，求出加法，求出,+8的单位元、每个元素的逆元、所有的单位元、每个元素的逆元、所有的生成元和所有的子群。的生成元和所有的子群。 2.2.求求 的单位元，零元，每个元素的逆元，每个元素的单位元，零元，每个元素的逆元，每个元素 的阶，它是循环群吗？求出它所有的子群。的阶，它是循环群吗？求出它所有的子群。 3.3.R R 是实数集，在是实数集，在 R R 上定义运算上定义运算* *为为 x*y=x+y+xy,x*y=x+y+xy,问：问：是是 代数系统吗？有单位元吗？每个元素都
6、有逆元吗？代数系统吗？有单位元吗？每个元素都有逆元吗？ 4.4.R R* *是非零实数集合，是非零实数集合，,o是代数系统，对于是代数系统，对于 R R* *中元素中元素 x,yx,y，令，令 xoy=2x+2y-2xoy=2x+2y-2。请问。请问,o中是否存在单位元、中是否存在单位元、 零元、哪些元素有逆元？运算零元、哪些元素有逆元？运算 o o 是否满足交换律和结合是否满足交换律和结合 律。分别说明理由。律。分别说明理由。 5.5.R R 是实数集，是实数集，R R 上的上的 6 6 运算定义如下：对运算定义如下：对 R R 中元素中元素 x,yx,y，f f1 1()=x+y()=x+
7、y；f f2 2()=x-y()=x-y；f f3 3()() =xy=xy；f f4 4()=x/y()=x/y；f f5 5()=maxx,y()=maxx,y；f f6 6()() =|x-y|=|x-y|。问：哪些满足交换律、结合律、有单位元、有。问：哪些满足交换律、结合律、有单位元、有 零元？说明理由。零元？说明理由。 6.6.是一个群，证明：是一个群，证明：G G 是交换群当且仅当对任意是交换群当且仅当对任意 G G 中中 元素元素 x,y,x,y,都有等式都有等式(xy)(xy)2 2=x=x2 2y y2 2成立。成立。 7.7.证明：如果群证明：如果群 G G 中每个元素的逆
8、元素都是它自已，则中每个元素的逆元素都是它自已，则 G G 是交换群。是交换群。 8.8.循环群一定是交换群。循环群一定是交换群。 9.9.证明：阶为素数的群一定是循环群。证明：阶为素数的群一定是循环群。 10.10. 是一个群，是一个群，u u G,G,定义运算定义运算* *：x*y=xoux*y=xou-1-1oy,oy, 证明：证明： 是一个群。是一个群。 11.11. 整数集整数集 Z Z 上定义运算上定义运算* *：对任意整数：对任意整数 x x 和和 y,x*y=x+y-4,y,x*y=x+y-4, 其中其中+ +，- -为普通加减法。证明：为普通加减法。证明：是一个群。是一个群。
9、 12.12. 证明：如果群证明：如果群 G G 中至少有两个元素，则群中没有零元。中至少有两个元素，则群中没有零元。 13.13. S S 是是 G G 的子群，证明：的子群，证明：x|xx|x 是是 S S 的左陪集的左陪集 是是 G G 的一个的一个 划分划分 14.14. 是一个群是一个群,a,a G,nG,n 是是 a a 的阶的阶( (周期周期) )，证明：，证明： |k=0,2,n-1,o是是的一个子群。的一个子群。 15.15. H H，K K 都是群都是群 G G 的子群，请问的子群，请问 HK,HK,H-KHK,HK,H-K 是否一定是是否一定是 G G 的子群？的子群？
10、16.16. H H，K K 是是 G G 的两个子群，的两个子群，a a G,G, 试证：试证：aHaH aKaK 当且仅当当且仅当 H H K K。 17.17. G=1,3,4,5,9,*G=1,3,4,5,9,*是模是模 1111 的乘法的乘法( (即即 x*y=xyx*y=xy modmod 11)11)， 请问请问(G,*)(G,*)是否构成群？是否构成群？ 18.18. 是群，是群，e e 是单位元，是单位元，a a G,aG,a 的阶为的阶为 k,k,证明：证明：a an n=e=e 当且仅当当且仅当 n n 是是 k k 的倍数。的倍数。 19.19. S S 是是 G G
11、的子群，证明：的子群，证明：x|xx|x 是是 S S 的左陪集的左陪集 是是 G G 的一个的一个 划分划分 20.20. G G 是群，证明：是群，证明：S=aS=a G|G| x x G(ax=xa),G(ax=xa),则则 S S 是是 G G 的子的子 群。群。 21.21. 是偶数阶群，则是偶数阶群，则 G G 中必存在中必存在 2 2 阶元素。阶元素。 22.22. 证明：证明：6 6 个元素的群在同构意义下只有两个。个元素的群在同构意义下只有两个。 23.23. R R 为实数集，为实数集，R R+ +为正实数集，为正实数集，与与 是否同构？是否同构？ 24.24. 是有限群，
12、证明：是有限群，证明：G G 不可能表示成两个真子群的并。不可能表示成两个真子群的并。25.25. 图论图论 1.1.如何判断二部图？完全图、完全二部图的边数。如何判断二部图？完全图、完全二部图的边数。 2.2.如何求如何求 E E 回路？回路？ 3.3.PetersenPetersen 图是否为图是否为 E E 图或图或 H H 图。图。 4.4.哪些完全图是哪些完全图是 H H 图？哪些完全图是图？哪些完全图是 E E 图？图？ 5.5.n n 为何值时轮图为为何值时轮图为 H H 图？图？ 6.6.如何求最小生成树。如何求最小生成树。 7.7.证明：奇数个顶点的二部图（两步图）不是哈密尔
13、顿图。证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。 8.8.证明：如果证明：如果 G G 是欧拉图，则其边图是欧拉图，则其边图 L(G)L(G)也是欧拉图。也是欧拉图。 9.9.证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。10.10. G G 是平面图，是平面图，G G 有有 m m 条边，条边，n n 个顶点，证明：个顶点，证明：m m 3n-63n-6。并。并 由此证明由此证明 K K5 5不是平面图。不是平面图。 11.11. 证明：有证明：有 6 6 个顶点的简单无向图个顶点的简单无向图 G G 和它的补图中至少有一和它的补
14、图中至少有一 个三角形。个三角形。 12.12. 证明：在至少有两个顶点的无向树中，至少有证明：在至少有两个顶点的无向树中，至少有 2 2 个一度顶个一度顶 点。点。 13.13. G G 是无向简单连通图，是无向简单连通图，G G 有有 n n 个顶点，则个顶点，则 G G 最少有几条边，最少有几条边， 最多有几条边？最多有几条边？ 14.14. 证明：简单无向图证明：简单无向图 G G 和它的补图中至少有一个是连通图。和它的补图中至少有一个是连通图。 15.15. 证明：无向图中奇度点（度数为奇数的点）有偶数个。证明：无向图中奇度点（度数为奇数的点）有偶数个。 16.16. 证明：证明：n
15、 n 个顶点的无向连通图至少有个顶点的无向连通图至少有 n-1n-1 条边。条边。 17.17. G G 是是 H H 图，图，V V 是是 G G 的顶点集，证明：对任意顶点集的顶点集，证明：对任意顶点集 S S，S S V V，都有，都有 （G-SG-S）|S|S|。其中。其中 （G-SG-S）表示）表示 G-SG-S 的分图数目。的分图数目。 18.18. 一棵无向树有一棵无向树有 3 3 个个 3 3 次点，次点，1 1 个顶点次数为个顶点次数为 2 2，其余顶点，其余顶点 次数为次数为 1 1，问它有几个次数为，问它有几个次数为 1 1 的顶点？写出求解过程。的顶点？写出求解过程。 19.19. 证明：每个简单平面图都包含一个次至多为证明：每个简单平面图都包含一个次至多为 5 5 的顶点。的顶点。 20.20. 连通平面图连通平面图 G G 有有 n n 个顶点，个顶点，m m 条边和条边和 f f 个面，证明：个面，证明：n-n- m+f=2m+f=2。 21.21. 如果图如果图 G G 的最大顶点次数的最大顶点次数，证明：，证明：G G 是是 +1+1 可点着可点着 色的。色的。 22.22. G G 是无向简单连通图，是无向简单连通图，G G 有有 n n 个顶点，则个顶点，则 G G 最少有几条边，最少有几条边， 最多有几条边？最多有几条边？
