北邮离散数学期末复习题

1、学习资料收集于网络，仅供参考北邮离散数学期末复习题第一章集合论一、判断题(1)空集是任何集合的真子集.(错)(2)他是空集.(错)(3)awa,a(对)(4)设集合A=42,l,28则1,212A.(对)(5)如果a正A=B,则a更A或a更B.(错)解a是A=B则awA.B=AcB,即awA且awB,所以a是A且a叁B(6)如果AUB=B,则A=B.(对)设集合A=ai,a2,a3,B=6也笛3,则A父B=<a1,b1A,<a2,b2A<a3,b3a(错)(8)设集合A=0,1,则P=<®,0a,(电1>,<0,0>,<0,1>是

2、2A到A的关系.(对)解2A=*0,1,a,2AA=：,0,：,1j0,0”0,1J1,01,1-：A,0jA,1(9)关系的复合运算满足交换律.(错)(10)PoP=P是集合A上的关系P具有传递性的充分必要条件.(错)(11)设P是集合A上的传递关系，则也是A上的传递关系.(对)(12)集合A上的对称关系必不是反对称的.(错)(13)设P1，P2为集合A上的等彳关系，则PcP2也是集合A上的等彳关系(对)(14)设P是集合A上的等价关系，则当<a,bwP时，ap=bp(对)P0户0=P。(15)设%p2为集合A上的等价关系，则(错)二、单项选择题(1)设R为实数集合，下列集合中哪一个不

3、是空集(A)A.&|x2-1=0，且xwrB.&|x2+9=0，且xwr)C.4|x=x+1，且xwR)d.x|x2=-1，且xwR)学习资料(2)设A,B为集合，若AB=4，则一定有A. B= B .B#4 C.(3)下列各式中不正确的是A. B B .C.A B D. A = B(C )；.，二。 D. 。三<', )(4)设A = a,a,则下列各式中错误的是A.右< 2A B . a=2A C. 4aw 2A D.'a：'2A设A = 2,B=a,b,c, C=L,d,则 Am(BPIC)为A. <c,1>, <2,

4、c> B . <1,0, < 2, c>C. L1,c ，:二 c,2 襄 D. 1； c,1 ., ： c,2(6)设庆=0, b, B =l, b, 3,则AU B的恒等关系为(A )A. <0,0 >, <1,1 >,<b,b >, <3,3 U B . <0,0 >,<1,1 >,<3,3 UC. L0,0 , ：b,b ,：二3,3 .) D.L 0,1 ,：二 1,b .,:二 b,3 ,：二 3,0 j(7)设A=Qb,c上的二元关系如下，则具有传递性的为(D)A. P1=匚二a,c,

5、:二c,a,:二a,b,：b,aJB. 72-1；a,c,:二c,aC. P3-：a,b,：c,c，:b,a，:：b,cD. ：'4-I；a,aJ(8)设P为集合A上的等价关系，对任意awA,其等价类a】p为(b)A.空集； B .非空集；C.(9)映射的复合运算满足A.交换律 B .结合律 C.(10)设A, B是集合，则下列说法中(A. A至ij B的关系都是A至ij B的映射B. A到B的映射都是可逆的C. A到B的双射都是可逆的D. A二B时必不存在 A到B的双射是否为空集不能确定； D.x|x A.(B )嘉等律 D.分配律C )是正确的.（11）设A是集合，则（B）成立.A

6、#2a=2#aAB.Xw2A修X工AC.你k2AD.bk2A（12）设A是有限集（#A=n）,则A上既是E又是的关系共有（B）A. 0个B. 1个C. 2个D. n个三、填空题1 .设A=1,2,1,2,则2A=.填2A=,1,2,1,2,1,2,1,1,2,2,1,2,A2 .设A=电螫,则2A=.填2A=*,*,*,A3 .设集合A,B中元素的个数分别为#A=5,#B=7,且#(AuB)=9,则集合AcB中元素的个数#(AcB)=.34 .设集合A=x|1ExW100,x是4的倍数,xwZ,B=x|1ExE100,x是5的倍数，xwZ,则AUB中元素的个数为.405 .设A=a,b,P是2

7、A上的包含于关系，则有P=.：，:二，a,:二，b,二，A，：a,a,二a,A,二b,b,：二b,A,:二A,A6 .设耳，2为集合A上的二元关系，则巳迅=P2°P17 .集合A上的二元关系P为传递的充分必要条件是.P口P1P8 .设集合A=6,1,2汪的关系R=<0,2>,<2,0'及集合A到集合B=0,2,4的关系P2=<a,b>|<a,b>wAmB且a,bAnB）则P1。P2=填：二0,0,<0,2,:二2,0,:二2,2四、解答题1 .设A=a,b,c,d,A上的关系P=二a,a，二b,b，二c,c，二d,d',

8、:a,b,：:：b,a，二c,d，二d,c(1)写出P的关系矩阵；(2)验证P是A上的等价关系；(3)求出A的各元素的等价类。解(1)P的关系矩阵为(2)从p的关系矩阵可知: 又由于P是自反的和对称的。<0或p。p = p满足 所以P是传递的。1010因为P是自反的、对称的和传递的，所以(3) a=b=a,b, c=d=c,dP是A上的等价关系。2.设集合A =1,2,3,6,8,12,24,36 , 2是A上的整除关系,(1) 写出P的关系矩阵M p；(2) 画出偏序集< A, P A的哈斯图;(3) 求出A的子集B =2,3,6的最小上界和最大下界。解：(1)00M p =01

9、111110 1110 110 10 0 10 10 0 0 1 01111111110(2)<0 0 0 0 0 00 1J(3)lubB=6,glbB=1五、证明题1.设R,p2为集合A上的等价关系，试证Pqp2也是集合A上的等价关系。证明：由于P1，P2是自反的，所以对任意awA,ca,aP，<a,a>wP2,因而<a,ap1cp2,即P1cP2是自反的。若<a,b*PcP2,则<a,b*P1，<a,b*p?，由于P1，P2是对称的，所以<b,a4,<b,aP2,从而<b,aPqP2,即PqP2是对称的。若<a,ba,cb

10、,cRcP2,则<a,ba,<b,cP，<a,ba,<b,c*P2,由于P1，P2是传递的，所以<a,c>P1,<a,c>£P2,从而<a,cP1cp2,即P1cP2是传递的。由于RcP2是自反的、对称的和传递的，所以P2是等价关系。第二章代数系统一、判断题（1）集合A上的任一运算对A是封闭的.（对）（2）代数系统的零元是可逆元.（错）（3）设A是集合，:AMATA,a°b=b，则。是可结合的.（对）（4）设a,b是代数系统A,的元素，如果a°b=b'a=e（e是该代数系统的单位元），则4a=b.（对）

11、设a,b是群彳G,：的元素，则（a匕尸=a匕.（错）222（6）设<G>是群.如果又于任意a,b=G,有（ab）=ab，则<G,0是阿贝尔群.（对）（7）设L,ha>是格，则运算¥满足曷等律.（对）（8）设集合A=a,b,则<4,a,b,A,5cA是格.（对）（9）设<B,¥,a,a是布尔代数，则<B,ha>是格.二、单项选择题（1）在整数集Z上，下列哪种运算是可结合的（B）A.a°b=a-bB.ab=maxa,bC.ab=a2bD.ab=|a-b|（2）下列定义的实数集R上的运算*中可结合的是.（C）A. a*b=

12、a+abB. a*b=a+2abC. ab=bD. a*b=|a+b其中，+,II分别为实数的加法、乘法和取绝对值运算.（3）设集合A=/2,3,4,，10,下面定义的哪种运算关于集合A不是封闭的（D）A. xy=maxx,yB. xy=minx,yC. x©y=GCDx,y,即x,y的最大公约数D. x°y=LCMx,y,即x,y的最小公倍数（4）下列哪个集关于减法运算是封闭的（B）A.N（自然数集）；B.2x|xwZ（整数集）；C.2x+1|xWZ；D.x|x是质数.（5）设Q是有理数集，在Q定义运算*为2*b=a+bab,则（Qj）的单位元为（D）A.a;B.b;C.

13、1;D.0（6）设代数系统A,工则下面结论成立的是.（C）A.如果（A,）是群，则A,，是阿贝尔群B.如果（A,是阿贝尔群，则A,）是循环群C.如果（A,）是循环群，则A,）是阿贝尔群D.如果（A,）是阿贝尔群，则A,）必不是循环群循环群亿,十）的所有生成元为（D）A.1,0B,-1,2C.1,2D.1,-1三、填空题1 .设A为非空有限集，代数系统2A,Ua中，2A对运算U的单位元为,零元为.填电A2 .代数系统Z,+中(其中Z为整数集合，+为普通加法)，对任意的xwI,其X=.填-x3 .在整数集合Z上定义。运算为a©b=a+2+b,则Z,的单位元为解设单位元为e,a0e=a+2

14、+e=a，所以e=2,又a。(-2)=a+2+(2)=a,(-2)-a=(2)+2+a=a,所以单位元为e=-24 .在整数集合Z上定义。运算为a©b=a+bab,则Z,©a的单位元为.解设单位元为e,aoe=a+e-ae=a,(1一a)e=0,所以e=05 .设(G,)是群，又任意a,b,cwG，如果ab=ac,则.填b=c6 .设(G,，是群，e为单位元，若G元素a满足a2=a,则a=填e四、解答题1 .设'为实数集R上的二元运算，其定义为2:RtR,a”b=a+b+2ab,对于任意a,b二R求运算*的单位元和零元。解：设单位元为e,则对任意awR,有a'

15、;e=a+e+2ae=a,即e(1+2a)=0,由a的任意性知e=0,又对任意awR,a0=a+0+0=a;0'a=0+a+0=a所以单位元为0设零元为6,则对任意awR,有a©e=a+6+2a9=日，1即a(1+26)=0,由a的任意性知6=2111111又对任息a=R,a°()=aa=,(-)°a=-+a-a=-222222一一.1所以零兀为一122 .设'为集合I5=0,1,2,3,4上的二元运算，其定义为,2:15TI5,ab=(ab)mod5,对于任意a,b匚15(1) 写出运算的运算表；(2) 说明运算。是否满足交换律、结合律，是否有单

16、位元和零元、如果有请指出;(3)写出所有可逆元的逆元解：(1)运算表为Q01234000000101234202413303142404321(2)运算二满足交换律、结合律，有单位元，单位元为1,有零元，零元为0;(3)1的逆元为1,2的逆元为3,3的逆元为2,4的逆元4,0没有逆元五、证明题1 .设G,：是一个群，试证G是交换群当且仅当对任意的a,bwG，有a2b2=(ab)2.证明：充分性若在群G,中，对任意的a,bwG,有a2*2=(a*)2.则(aa)(bb)=(ab)(ab)a(ab)b=a(ba)bab=ba从而G,：是一个交换群。必要性若G,。是一个交换群，对任意的a,bG,有a

17、+bnba,则a(ab)b=a(ba)b(aa)(bb)=(ab)(ab)即a2b2=(ab)2.2 .证明代数系统Z,0是群，其中二元运算'定义如下：。：Z2tZ,x0y=x+y-3(这里，+,-分别是整数的加法与减法运算.)证明(1)运算满足交换律对任意x,y,zwZ,由(xy)z=(xy-3)z=xyz-6,x(yz)=x(yz-3)=xyz-6得(x*y)*z=x*(y*z),即“满足结合律;(2)有单位元3是单位元；(3)任意元素有逆元对任意xwZ,x*=6x.所以，(Z,是群.第三章图论、判断题(1)n阶完全图的任意两个不同结点的距离都为1.(对)(2)图G的两个不同结点v

18、i,vj连接时一定邻接.(错)图G中连接结点vi,vj的初级通路为vi,vj之间的短程.(错)(4)在有向图中，结点Vi到结点Vj的有向短程即为Vj到v的有向短程.(错)(5)强连通有向图一定是单向连通的.(对)(6)不论无向图或有向图，初级回路一定是简单回路.(对)(7)设图G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的.(对)(8)有生成树的无向图是连通的.(对)(9)下图所示的图是欧拉图.(错)(10)下图所示的图有哈密尔顿回路(A)(B)(B)(C)二、单项选择题(1)仅由孤立点组成的图称为A.零图；B.平凡图；C.完全图；D.多重图.(2)仅由一个孤立点组成的图称为A.零

19、图；B.平凡图；C.多重图；D.子图.(3)在任何图G中必有偶数个A.度数为偶数的结点；B.度数为奇数的结点；C.入度为奇数的结点；D.出度为奇数的结点.(4)设G为有n个结点的无向完全图，则G的边数为n(n -1). 2D. (n -1). 2A. n(n-1)B,n(n+1)C.A.最多n -1条;.至少n -1条;(5)在有n个结点的连通图G中，其边数C.最多n条；D.至少n条.(6)任何无向图G中结点间的连通关系是(B)A.偏序关系；B.等价关系；C.既是偏序关系又是等价关系；D.既不是偏序关系也不是等价关系.(7)对于无向图，下列说法中正确的是.(B)A.不含平行边及环的图称为完全图

20、B.任何两个不同结点都有边相连且无平行边及环的图称为完全图C.具有经过每条边一次且仅一次回路的图称为哈密尔顿图D.具有经过每个结点一次且仅一次回路的图称为欧拉图(8)设D是有向图，则D强连通的充分必要条件为.(C)A.略去D中各边方向后所得到的无向图是连通的B. D是单向连通图，且改变它的各边方向后所得到的有向图也是单向连通图C. D的任意两个不同的结点都可以相互到达D. D是完全图(9)对于无向图G,以下结论中不正确的是.(A)A.如果G的两个不同结点是连接的，则这两个结点之间有初级回路B.如果G的两个不同结点是连接的，则这两个结点之间至少有一条短程C.如果G是树，则任何两个不同结点之间有且

21、仅有一条初级通路D.如果G是欧拉图，则G有欧拉回路三、填空题1 .设机T中有7片树叶，3个3度结点，其余都是4度结点，则T中有个4度结点.解用握手定理和树的性质列出方程求解，设有X个4度结点，7+9+4x=2(7+3+x-1),X=12 .设T=<V,E>为树，T中有4度，3度，2度分支点各1个，问T中有一片树叶。解与上题解法相同，设有x片树叶，4+3+2+x=2(3+x1),x=53 .n阶完全图的任意两个不同结点的距离都为.14 .图G为n阶无向完全图，则G共有条边。n(n1)/25 .设G为(n,m)图，则图中结点度数的总和为。2m6 .图G为欧拉图的充分必要条件是.G为无奇

22、度结点的连通图四、解答题1.对下图所示的图G,求(1) G的邻接矩阵A;(2) G的结点Vi,V3之间长度为3的通路;(3) G的连接矩阵C；(4) G的关联矩阵M。解(1)(2)因为1v2v3v4v5v101110Av2A=10101v311011v410100v5<0110031212、仅M7M13221XXXXXa322411,A=MMMMM12121XXXXX、21112,.x：XXXX<JA2=3的通路共有7条，它们是所以，结点必”3之间长度为V1V3V1V3,VlV2v5v3,V1V2V1V3,V1V4V1V3,v1v3v5v3,v1v3v2v3,v1v3v4v3.v1

23、v2v3v4v11111v21111C=v31111v41111v5J111(4)e1e2e3e4v1p011v21100M=v30110v40001v590002.在卜面的有向图D中回答t、夕U问题(3)由于图G是连通的，所以v5r11.11e5e6e000、001110100011,(1)写出图D的邻接矩阵A;(2)写出结点vi到结点V3的长度为3的所有有向通路;(3)写出结点V5到自身的长度为3的所有有向回路;0 0 11 0 01 1 00 0 10 1 0,0010解：(1)A=0000101101 01、01121A3 = 011 2110101:0112 1,0022 2)A2=

24、00I1010'0111011110100101,v5v2v1v5所以结点V1到结点V3的长度为3的所有有向通路只有一条：v1v5v2v3(3)结点V5到自身的长度为3的所有有向回路只有一条:3 .在下面的无向图G中，回答下列问题(1)写出a,d之间的所有初级通路；(2)写出a,d之间的所有短程，并求d(a,d)；(3)判断无向图G是否为欧拉图并说明理由。解(1)a,d之间的所有初级通路共有7条，分别为aed,aecd,aebcd,abed,abcd,abecd,abced(2) a,d之间的长度最短的通路只有1条，即aed,因而它是a,d之间唯一的短程，d(a,d)=2(3)由于无向图G中有两个奇度顶点deg(b)=3,deg(c)=3,所以无向图G没有欧拉回路，因而不是欧拉图。第四章数理逻辑一、判断题（1） “如果8+7>