离散数学习题.doc

集合论1. A=,1，B=a求A的幂集、AB、AB、A+B。2. A=1,2,3,4,5,R=(x,y)|xy且y=4, S=(x,y)|2x+y=6,求RS,R-S,RoS,SoR。R,S具有哪些性质？3. A=a,b,c,R=(a,a),(b,a),求R-1,R2,R-IA,IA-R,r(R),s(R),t(R),st(R),ts(R)。4. A=a,b,c,R= IA (a,b),(b,a)，求a和b关于R的等价类。5. R是A上的等价关系，A/R=1,2，3,求A，R。6. 请分别判断以下结论是否一定成立，如果一定成立请证明，否则请举出反例。如果ABC，则AC或者BC。如果AB=AC且A，则B=C。7. 如果R是A上的等价关系，R2,r(R)是否一定是A上的等价关系？证明或举例。8. 已知ACBC,A-CB-C,证明：AB。9. 证明：AX(BC)=(AXB)(AXC)10. 证明：P(A)P(B)P(AB)11. 证明：Rsym iff R=R-112. 证明：r(R)=RIA,S(R)=RR-1,t(R)=RR2.13. 证明：s(RS)=s(R)s(S)14. R是A上的关系，证明：如果R是对称的，则r(R)也是对称的。15. I是整数集，R=(x,y)|x-y是3的倍数，证明：R是I上的等价关系。16. 如果R是A上的等价关系，则A/R一定是A的划分。17. R是集合A上的自反关系，S是A上的自反和对称关系，证明t(RS)是A上的等价关系。18. I是正整数集合，R是II上的二元关系，R=,|xv=yu,证明：R是等价关系。19. f:AB，R是B上的等价关系，令S=|xA且yA且R，证明：S是A上的等价关系。20. R是集合A上的自反关系，S是A上的自反和对称关系，证明t(RS)是A上的等价关系。21. P和Q都是集合A上的划分，请问PQ，P-Q是否是A上的划分，22. RAXA,Rirref且Rtra,证明：r(R)是A上的偏序关系。23. 画出1,2,3,4,6上整除关系的哈斯图，求2,3,6的4种元素。24. A=a,b,c,d,e,f,g,R=(a,c),(a,e),(b,d),(b,f),(d,e),(d,f),S=tr(R),画出S的哈斯图并求b,c,d,f的极大元等8种元素。25. f:AB,g:BC都是单（满）射，证明：复合映射gof一定是单（满）射。26. f:AB,g:BC，gof是单射，请问f和g是否一定是单射？请证明或举出反例。27. R是实数集，f:RRRR,f()=,请问f是否为单射？是否为满射？分别证明或举反例。28. 已知BC=,令f：P(BC)P(B)P(C)，对XP(BC),令f(X)=(BX,CX),证明：f是双射。代数系统1. 是模8加群，Z8=0,1,2,3,4,5,6,7,+8是模8加法，求出的单位元、每个元素的逆元、所有的生成元和所有的子群。2. 求的单位元，零元，每个元素的逆元，每个元素的阶，它是循环群吗？求出它所有的子群。3. R是实数集，在R上定义运算*为x*y=x+y+xy,问：是代数系统吗？有单位元吗？每个元素都有逆元吗？4. R*是非零实数集合，是代数系统，对于R*中元素x,y，令xoy=2x+2y-2。请问中是否存在单位元、零元、哪些元素有逆元？运算o是否满足交换律和结合律。分别说明理由。5. R是实数集，R上的6运算定义如下：对R中元素x,y，f1()=x+y；f2()=x-y；f3()=xy；f4()=x/y；f5()=maxx,y；f6()=|x-y|。问：哪些满足交换律、结合律、有单位元、有零元？说明理由。6. 是一个群，证明：G是交换群当且仅当对任意G中元素x,y,都有等式(xy)2=x2y2成立。7. 证明：如果群G中每个元素的逆元素都是它自已，则G是交换群。8. 循环群一定是交换群。9. 证明：阶为素数的群一定是循环群。10. 是一个群，uG,定义运算*：x*y=xou-1oy, 证明：是一个群。11. 整数集Z上定义运算*：对任意整数x和y,x*y=x+y-4,其中+，-为普通加减法。证明：是一个群。12. 证明：如果群G中至少有两个元素，则群中没有零元。13. S是G的子群，证明：x|x是S的左陪集是G的一个划分14. 是一个群,aG,n是a的阶(周期)，证明：是的一个子群。15. H，K都是群G的子群，请问HK,HK,H-K是否一定是G的子群？16. H，K是G的两个子群，aG, 试证：aHaK当且仅当HK。17. G=1,3,4,5,9,*是模11的乘法(即x*y=xy mod 11)，请问(G,*)是否构成群？18. 是群，e是单位元，aG,a的阶为k,证明：an=e当且仅当 n是k的倍数。19. S是G的子群，证明：x|x是S的左陪集是G的一个划分20. G是群，证明：S=aG|xG(ax=xa),则S是G的子群。21. 是偶数阶群，则G中必存在2阶元素。22. 证明：6个元素的群在同构意义下只有两个。23. R为实数集，R+为正实数集，与是否同构？24. 是有限群，证明：G不可能表示成两个真子群的并。25.图论1. 如何判断二部图？完全图、完全二部图的边数。2. 如何求E回路？3. Petersen图是否为E图或H图。4. 哪些完全图是H图？哪些完全图是E图？5. n为何值时轮图为H图？6. 如何求最小生成树。7. 证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。8. 证明：如果G是欧拉图，则其边图L(G)也是欧拉图。9. 证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。10. G是平面图，G有m条边，n个顶点，证明：m3n-6。并由此证明K5不是平面图。11. 证明：有6个顶点的简单无向图G和它的补图中至少有一个三角形。12. 证明：在至少有两个顶点的无向树中，至少有2个一度顶点。13. G是无向简单连通图，G有n个顶点，则G最少有几条边，最多有几条边？14. 证明：简单无向图G和它的补图中至少有一个是连通图。15. 证明：无向图中奇度点（度数为奇数的点）有偶数个。16. 证明：n个顶点的无向连通图至少有n-1条边。17. G是H图，V是G的顶点集，证明：对任意顶点集S，SV，都有（G-S）|S|。其中（G-S）表示G-S的分图数目。18. 一棵无向树有3个3次点，1个顶点次数为2，其余顶点次数为1，问它有几个次数为1的顶点？写出求解过程。19. 证明：每个简单平面图都包含一个次至多为5的顶点。20. 连通平面图G有n个顶点，m条边和f个面，证明：n-m+f=2。21. 如果图G的最大顶点次数，证明：G是+1可点着色的。22. G是无向简单连通图，G有n个顶点，则G最少有几条边，最多有几条边？23. 如果一个简单图G和它的补图同构，则称G是自补图，求所有4个顶点自补图。24. G是平面图，G有m条边，n个顶点，证明：m3n-6。如果G中无三角形，则m2n-4。数理逻辑1. 如果今天是星期一，则要进行英语或数理逻辑考试。没有不犯错误的人。整数都是有理数。 有的有理数不是整数。不存在最大的整数。有且只有一个偶数是素数。2. 求真值表及范式：P(QR)、(QR)(PR)3. 推理：p(qr)，sp，q srpr，qs，pq rspq，pr，st，sr，t qp(rs)q),p,s q4