2018年春季学期离散数学期末复习题

1、2018年春季学期离散数学期末复习题第一章集合论一、判断题（1）空集是任何集合的真子集.（错）（2） 是空集.（错）（3） aa,a（对）（4）设集合A1,2,1,2，则1,22A.（对）如果aAB,则aA或aB.（错）解aAB则aABAB,即a入且aB,所以aA且aB（4） 如果AUBB,则AB.（对）设集合A匕色冏'B"也避,则ABaC,a2,b2,a3,b3（错）(8)设集合A0,1,则,0,1,0,0,0,1是2A到A的关系.（对）A解2,0,1,A,A2A,0,1,0,0,0,1,1,0,1,1,A,0,A,1（5） 关系的复合运算满足交换律.（错）（10） 是集合

2、A上的关系具有传递性的充分必要条件.（错）（11）设是集合A上的传递关系，则也是A上的传递关系.（对）（12）集合A上的对称关系必不是反对称的.（错）（13）设1,2为集合A上的等彳关系，则12也是集合A上的等价关系（对）（14）设是集合A上的等价关系，则当a,b时，ab（对）户1°P：°Pr（15）设1,2为集合A上的等价关系，则（错）二、单项选择题（1）设R为实数集合，下列集合中哪一个不是空集（A）.22A.x|x10,且xRB.x|x90,且xR2C.x|xx1,且xRD.x|x1,且xR2)设A,B为集合，若AB，则一定有A. BB BC. AD. A B3)下列各

3、式中不正确的是A.BC.D., 4)设a,a,则下列各式中错误的是A. a2ABa2C.a2AD. a2A5)1,2，a, b, cc, dA (BC)为A.c,1 ,2,cB1,c2, cC.1,cc,2D.c,1 , c,26)0, b ，1, b, 3B 的恒等关系为A.0,0 , 1,1 , b,b , 3,3B0,0 , 1,1, 3,3C.0,0 , b,b3,3D. 0,1 , 1,b, b,33,07)a,b,上的二元关系如下，则具有传递性的为则具有传递性的为A.a,cc,a , a,b ,b,aBa,cc, aC.a,b ,c,c , b,a ,b,cD.a,a8)为集合 A

4、 上的等价关系，对任意a A ，其等价类A. 空集；B.非空集;C. 是否为空集不能确定；D.x|xA.9)映射的复合运算满足A. 交换律B.结合律C. 幂等律D.分配律10)设A，B是集合，则下列说法中(C)是正确的AA到B的关系都是A到B的映射BA到B的映射都是可逆的CA到B的双射都是可逆的DAB时必不存在A到B的双射（11）设A是集合，则（B）成立.A. #2A2#AAB. X2AXAC. 2AD. A2A（12）设A是有限集（#An）,则A上既是又是的关系共有（B）.A. 0个B. 1个C. 2个D. n个三、填空题1 .设A1,2,1,2,则2A.填2A,1,2,1,2,1,2,1,

5、1,2,2,1,2,A2 .设A,则2A=.填2A,A3 .设集合A,B中元素的个数分别为#A5,#B7,且#5B）9,则集合AB中元素的个数#（AB）.34 .设集合Ax|1x100,x是4的倍数,xZ,Bx|1x100,x是5的倍数，xZ,则AB中元素的个数为.405 .设Aa,b,是2A上的包含于关系，则有=.,a,b,A,a,a,a,A,b,b,b,A,A,A6 .设1,2为集合A上的二元关系，则12.217 .集合A上的二元关系为传递的充分必要条件是.8.设集合A 0,1, 2上的关系10, 2 , 2, 0 及集合A到集合B 0,2,4的关系 2 a, b | a, bA B且a,

6、b A n B ,则 12填0,0,0,2,2,0,2,2四、解答题1.设集合A,1,2,B1,2,B求（1）AU2B;（2）2A解（1）AU2b,1,2,U,1,2,B,1,2,1,2,B.2)A2B，所以2A2B2,2.设Aa,b,c,d,A上的关系a,a,b,b,c,c,d,d（1）写出的关系矩阵；（2）验证是A上的等价关系；（3）求出A的各元素的等价类。解（1）的关系矩阵为a,b,b,a,c,d,d,c11001100M001100112）从的关系矩阵可知：是自反的和对称的。又由于1100110011001100MM001100110011001111001100M00110011是

7、A 上的等价关系。或满足所以是传递的。因为是自反的、对称的和传递的，所以3）aba,b，cdc,d3.设集合A1,2,3,5,6,15,30,是A上的整除关系,1）写出的关系矩阵M；2）画出偏序集A,的哈斯图；（3）求出A的子集B（4）判断其是否为格。111010001解：（1）M0000003,6,15 的最小上界和最大下界；111101010111101101010011000(3)lubB=30,glbB=3五、证明题1.设2为集合证明：由于A上的等价关系，试证是自反的，所以对任意2也是集合A上的等价关系。A,a,aa,a2,因而a,a若以b,a若a,b,1a,b2,即12是自反的。1b

8、,a2,则a,b2,从而1,b,aa,b22,即油于2是对称的，所2是对称的。b,ca,c由于a,ca,b,b,ca,b,b,c2,从而a,c2是自反的、对称的和传递的,1所以、判断题(1)(2)(3)(4)(5)(6)群.第二章代数系统集合A上的任一运算对A是封闭的.代数系统的零元是可逆元.A是集合，：AAa,b是代数系统A,a,b是群G,的元素的元素，如果，则（ab）1G,是群.如果又于任意a,bb,则G,L,是格，则运算满足曷等律.传递的2是传递的。2是等价关系。是可结合的.（.2有(ab)e（e是该代数系统的单位元）G,是阿贝尔(8)设集合Aa,b,则,a,b,A,是格.(11) &l

9、t;0,1,2,3,4,max,min>是格.(对)(9)设B,是布尔代数，则B,是格.(对)(10)设B,/是布尔代数，则对任意a,bB,有abab.(对)二、单项选择题(1)在整数集Z上，下列哪种运算是可结合的(B)A.ababB.abmaxa,bC.aba2bd.ab|ab|(2)下列定义的实数集R上的运算*中可结合的是.(C)A. abaabB. aba2abC. abbD. abab其中，+,II分别为实数的加法、乘法和取绝对值运算.(3)设集合A1,2,3,4,10,下面定义的哪种运算关于集合A不是封闭的(D)A. xymaxx,yB. xyminx,yC. xyGCDx,y

10、,即x,y的最大公约数D. xyLCMx,y,即x,y的最小公倍数(4)下列哪个集关于减法运算是封闭的(B)A. N (自然数集)；B. 2x|x Z(整数集);C. 2x 1|x Z；D. x|x是质数.设Q是有理数集，在Q定义运算为ababab,则(Q,)的单位元为(D)A.a；B.b；C.1;D.0(6)设代数系统A,则下面结论成立的是.(C)A.如果A,是群，则A,是阿贝尔群B.如果A,是阿贝尔群，则A,是循环群C.如果A,是循环群，则A,是阿贝尔群D.如果A,是阿贝尔群，则A,必不是循环群循环群(Z,，的所有生成元为(D)A.1,0B.-1,2C.1,2D.1,-1三、填空题一AA1

11、 .设A为非空有限集，代数系统2,中，2对运算的单位元为,零元为.填,A2 .代数系统Z,中(其中Z为整数集合，+为普通加法)，对任意的xI,其x1填x3 .在整数集合Z上定义运算为aba2b,则Z,的单位元为.解设单位元为3,262262,所以32,又a(2)a2(2)a,(2)a(2)2aa,所以单位元为e24 .在整数集合Z上定义 解设单位元为e , a e运算为a b a b a e ae a, (1ab ,则 Z,的单位元为a)e 0 ,所以 e 05 .设G, 是群，又任意a, b,c.填 bc6 .设(G,)是群，e为单位元，若G元素a满足a2a,则a填e四、解答题1 .设为实数

12、集R上的二元运算，其定义为_2_.一.、._:RR,abab2ab,对于任意a,bR求运算的单位元和零元。解：设单位元为e,则对任意aR,有aeae2aea,即e(12a)0,由a的任意性知e0,0 a 0 a 0 aa 2a ,12111一，(一)a 一222又对任意aR,a0a00a；所以单位元为0设零元为，则对任意aR,有a即a(12)0,由a的任意性知一_11又对任息aR,a(-)a-a22一一.1所以零兀为122.设为集合150,1,2,3,4上的二元运算，其定义为.2:15I5,ab(ab)mod5,对于任意a,b15(1)写出运算的运算表；(2)说明运算是否满足交换律、结合律，是

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

14、a(ab)ba(ba)b(aa)(bb)(ab)(ab)即a2b2(ab)2.2.证明代数系统Z,是群，其中二元运算定义如下：2：ZZ,xyxy3(这里，+,-分别是整数的加法与减法运算.)证明(1)运算满足交换律对任意x,y,zZ,由(xy)z(xy3)zxyz6,x(yz)x(yz3)xyz6得(xy)zx(yz),即满足结合律；（2）有单位元3是单位元；（3）任意元素有逆元对任意xZ,x16x.所以，Z,是群.第三章图论一、判断题（1）n阶完全图的任意两个不同结点的距离都为1.（对）（2）图G的两个不同结点vi,vj连接时一定邻接.（错）图G中连接结点viY的初级通路为via之间的短程.

15、（错）（4）在有向图中，结点vi到结点Vj的有向短程即为Vj到Vi的有向短程.（错）（5）强连通有向图一定是单向连通的.（对）（6）不论无向图或有向图，初级回路一定是简单回路.（对）（7）设图G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的.（对）（8）设A是某个无向图的邻接矩阵，则AAT（AT是A的转置矩阵）.(9)设有向图D的可达矩阵为11110111P00110001（对 ）（对）（错 ）则G是单向连通的.（10）有生成树的无向图是连通的.（11）下图所示的图是欧拉图（12）下图所示的图有哈密尔顿回路(13)下图中为欧拉图的是( C )A.B.C.D.二、单项选择题(1)仅由孤

16、立点组成的图称为A.零图；B.平凡图；(2)仅由一个孤立点组成的图称为A.零图；B.平凡图；(3)在任何图G中必有偶数个A.度数为偶数的结点；C.入度为奇数的结点；C.完全图；D.多重图.C.多重图；D.子图.B.度数为奇数的结点；D.出度为奇数的结点.(4)设G为有n个结点的无向完全图，则 G的边数为(A )(B )(B )(C )A. n(n 1)B.n(n1)C.n(n1)2D.(n1),2(5)在有n个结点的连通图G中，其边数(B)A.最多n1条；B.至少n1条；C.最多n条；D.至少n条.(6)任何无向图G中结点间的连通关系是(B)A.偏序关系；B.等价关系；C.既是偏序关系又是等价

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

18、有初级回路B.如果G的两个不同结点是连接的，则这两个结点之间至少有一条短程C.如果G是树，则任何两个不同结点之间有且仅有一条初级通路D.如果G是欧拉图，则G有欧拉回路(10)设简单无向图G的邻接矩阵为A(aij)nn,记Al(a;)nn(l1,2,)，则正确的是.A.当Vi,Vj是G的两个不同结点时，a;为Vi,Vj之间长度为l的初级通路条数B.当Vi,Vj是G的两个不同结点时，a：为v,vj之间长度为l的简单通路条数C.当Vi,Vj是G的两个不同结点时，a：为Vi,Vj之间长度为l的的通路条数D.当w是G的结点时，a(l)为通过vi的长度为l的初级回路条数(11) Mmijnm是无向图GV,

19、E的关联矩阵，ViV是G中的孤立点，则(A)A.Vi对应的一行元素全为0;B.Vi对应的一行元素全为1;C.Vi对应的一列元素全为0;D.Vi对应的一列元素全为1.三、填空题1 .设树T中有7片树叶，3个3度结点，其余都是4度结点，则T中有个4度结点.解用握手定理和树的性质列出方程求解，设有X个4度结点，794x2(73x1),X12.设TV, E 为树，T中有4度，3度，2度分支点各1个，问T中有片树叶。解 与上题解法相同，设有 x片树叶,4 3 2 x 2(3 x 1) , x 5阶完全图的任意两个不同结点的距离都为.14 .图G为n阶无向完全图，则G共有条边。n(n1)/25 .设G为(

20、n,m)图，则图中结点度数的总和为6 .设图G有6结点，若各结点的度数分别为：用握手定理222m,m=117 .图G为欧拉图的充分必要条件是四、解答题1 .对下图所示的图G,求(1) G的邻接矩阵A;(2) G的结点v1,v3之间长度为3的通路；(3) G的连接矩阵C;(4) G的关联矩阵M。2m1,4,4,3,5,5,贝UG共有条边。.G为无奇度结点的连通图v1v10v2v3v41v5011解（1）A=v210101v311011.v410100v501100（2）因为31212713221A2=22411,A3=1212121112所以，结点Vi,V3之间长度为3的通路共有7条，它们是v1

21、v3v1v3,v1v2v5v3,v1v2v1v3,v1v4v1v3,v1v3v5v3,v1v3v2v3,v1v3v4v3.3由于图G是连通的，所以v1v2v3v4v5v111v211C=v311v411v5111111111111111114）e1e2e3e4e5e6e7000001110100011v11011v21100M=v30110v40001v500002 .在下面的有向图D中，回答下列问题(1)写出图D的邻接矩阵A;(2)写出结点Vi到结点V3的长度为3的所有有向通路;(3)写出结点V5到自身的长度为3的所有有向回路;0000110100解：(1)A0011001010A20 10

22、 100 0 1110 0 1110 10 1010 10 1所以结点V1到结点V3的长度为3的所有有向通路只有一条：V1V5v2v3(3)结点V5到自身的长度为3的所有有向回路只有一条:3.在下面的无向图1010101121A3011211010101121v5v2v1v5(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 1）“如果8+7>2,则三角形有四条边”是命题.（对）2 ）设P,Q都是命