北邮离散数学期末复习题1

离散数学期末复习题第一章集合论、判断题(1) 空集是任何集合的真子集.(错)(2)是空集.(错 )(3)a a,a( 对 )(4) 设集合A1,2, 1,2 ,则 1, 22A.( 对 )(5) 如果a AB，则aA或aB.(错 )解aA B则a A BA B,即aA且aB，所以a A且a B(6) 如果 AUBB,则 AB.(对 )(7) 设集合A, a2, a3,B b144，则A B a, b,a?, b?,a3,b3( 错 )(8)设集合A 0,1,则,0 ,1 , 0,0 , 0,1 是2A到A的关系.(对)A解2 ,0,1, A,A2 A,0 ,1 , 0,0, 0,1 , 1,0 , 1,1, A,0, A,1(9 )关系的复合运算满足交换律.(错 )(10)是集合 A 上的关系 具有传递性的充分必要条件.(错 )(11)设是集合A上的传递关系，则也是 A 上的传递关系(对)(12)集合 A 上的对称关系必不是反对称的 .(错)(13) 设1,2为集合A上的等价关系，则12也是集合A上的等价关系(对)(14)设 是集合A上的等价关系，则当a,b时，ab(对)尸1 &2二QcPj(15) 设1,2为集合A上的等价关系，则( 错)二、单项选择题(1 )设R为实数集合，下列集合中哪一个不是空集(A )2）设A,B为集合，若A B，则一定有C )A.x|x21 0,且 x RB .x | x29 0,且 x RC.x | x x 1,且 x RD.x | x21,且 x R（9）映射的复合运算满足A.交换律 B 结合律 C.10）设 A， B 是集合，则下列说法中（ C ）是正确的AA 到 B 的关系都是 A 到 B 的映射BA 到 B 的映射都是可逆的CA 到 B 的双射都是可逆的D A B时必不存在 A 到 B 的双射A.BBBC.ABD.AB（3）下列各式中不正确的是( C）A.B C.D., （4）设Aa,a，则下列各式中错误的是( B）A.Aa 2ABa 2AC.Aa 2AD.a2A（5）设A1,2，B a,b, c，Cc, d，则A (BC)为( B）A.c,1, 2,cB 1,c , 2,cC.1,c, c,2D.c,1 , c,2（6）设A0,b，B 1, b,3，则A B的恒等关系为（A）A.0,0, 1,1, b,b , 3,3B 0,0 , 1,1, 3,3C.0,0, b,b, 3,3D.0,1 , 1,b, b,3 ,3,0（7）设Aa,b, c上的二元关系如下，则具有传递性的为( D）A.1a,c ,c,a , a,b ,b,aB2a,c ,c,aC.3a,b ,c,c , b,a ,b,cD.4a,a（8）设 为集合A上的等价关系，对任意aA，其等价类a为( B）A. 空集； B 非空集；C. 是否为空集不能确定； D.x| x A.幂等律 D.分配律2）设A,B为集合，若A B，则一定有C )(11)设 A 是集合，则(B )成立A.#2A2#AB.X 2AX AC.2AD.A 2A(12 )设 A 是有限集(#A n),则 A 上既是 又是的关系共有(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. 设集合 代B中元素的个数分别为#A 5,#B 7,且#(A B) 9,则集合AB中元素的个数#(A B) _.34. 设集合A x|1 x 100, x 是 4 的倍数，x Z,B x|1 x 100, x 是 5 的倍数，x Z，则A B中元素的个数为.405. 设A a,b, 是2A上的包含于关系，则有,a ,b , ,A ,a, a, a,A , b, b , b,A , A,A 6. 设1, 2为集合A上的二元关系，贝U 12217. 集合A上的二元关系为传递的充分必要条件是 _.8. 设集合A 0,1,2 上的关系10,2 ,2,0及集合 A 到集合B 0,2,4的关系2a, b|a, b A B 且 a, b A n B ,贝 V12_.填0,0 ,0,2 ,2,0 ,2,2 四、解答题1.设A a,b,c,d, A上的关系 a,a , b,b , c,c , d,d , a,b , b,a , c,d , d,c (1)写出的关系矩阵；(2)验证是A上的等价关系；(3)求出A的各元素的等价类。2)解 （ 1） 的关系矩阵为11001100M001100112)从的关系矩阵可知：是自反的和对称的。又由于1100110 011001100110 01100MMM0011001 100110011001 10011或 满足所以 是传递的。因为 是自反的、对称的和传递的，所以 是A上的等价关系。 （3）a b a,b，c d c,d2. 设集合A 1,2,3,6,8,12,24,36， 是A上的整除关系，（ 1） 写出 的关系矩阵M；（ 2） 画出偏序集A,的哈斯图；（3） 求出A的子集B 2,3,6的最小上界和最大下界。111111111111010111010001解：( 1)M11100100000000000100000036(3)lubB=6, glbB=1五、证明题1设1,2为集合A上的等价关系，试证12也是集合A上的等价关系。证明：由于a, a若1,1a, b2是自反的，所以对任意a A,a, aa,b1,2,由于a, a2,因而2，即112是自反的。2，则a,b1,1,2是对称的，所以b, a1,b, a2,从而b, a1 2，即12是对称的。若a,b , b, c12则a,b ,b,c1,a,b , b,c2,由于1,2是传递的，所以a,c1,a,c2,从而a,c12, 即12是传递的。由于12是自反的、对称的和传递的，所以12是等价关系。第二章代数系统-、判断题(1)集合 A 上的任一运算对A 是封闭的.(对 )(2)代数系统的零元是可逆元.(错)(3)设 A 是集合，:A A A,abb，贝 U 是可结合的.(对 )(4)设a, b是代数系统A,的元素，如果a b b a e(e是该代数系统的单位元)，则1ab.(对)(5) 设a, b 是群 G,的兀素，则(a b)a b .(错)(6) 设G,是群.如果对于任意a,b G，有(a b)22 2a b,则G,是阿贝尔群.(对)(7) 设L,是格,则运算满足幕等律.(对)36(8)设集合Aa,b，则 ,a,b, A,是格.(对)(9) 设B,是布尔代数，则B,是格.(对)二、单项选择题(1 )在整数集Z上，下列哪种运算是可结合的A.a b abB.a b max a, b(D )A.xymaxx, yB.xymin x, yC.xyGCDx, y,即x, y的最大公约数D.xyLCM x, y，即x, y的最小公倍数(4)下列哪个集关于减法运算是封闭的(B )A.N(自然数集)；B .2x|x Z(整数集)；A.如果 A, 是群，则 A, 是阿贝尔群B.如果 A, 是阿贝尔群，则A, 是循环群C.如果 A, 是循环群，则A, 是阿贝尔群D.如果 A, 是阿贝尔群，则A, 必不是循环群(7)循环群Z,的所有生成元为(D )A. 1 , 0 B . -1 , 2 C. 1, 2 D. 1, -1三、填空题C.a b a 2bD.A.a ba a bB.aba 2a bC.abbD.aba b其中+1分别为实数的加法、乘法和取绝对值运算(2)下列定义的实数集R 上的运算*中可结合的是(3)设集合A 1,2, 3, 4,10，下面定义的哪种运算关于集合A 不是封闭的C.2x 1 | x Z;D.x | x 是质数.为a ba b为A.a；B.b；C. 1；(6) 设代数系统A, ，则下面结论成立的是D. 0(5)设Q是有理数集，在Q定义运算1.设A为非空有限集，代数系统2A,中，2A对运算的单位元为，零元填,A2代数系统Z,中x1. 填x3.在整数集合Z上定义 解设单位元为e,a e(其中运算为a 2又a ( 2) a 2( 2)a,(4.在整数集合Z上定义 解设单位元为e,a e运算为Z为整数集合,ae2)ae+为普通加法)，对任意的x I，其5.设G,是群，对任意a,b,cb a 2a，所以a (G，如果6.设G,是群，e为单位元，若四、解答题1设 为实数集R上的二元运算，其定义为2)b(1b，则2,aZ,的单位元为a，所以单位元为e 2ab，则0,所以ea)eG,则G元素a满足a2:R R, a b a b 2ab，对于任意a, b求运算的单位元和零元。解：设单位元为e,则对任意a R，有2ae即e(12a)0，由a的任意性知的单位元为0又对任意a所以单位元为设零元为，R,a 0 a 0 00则对任意a R，有a即a(12 )0,由a的任意性知2a又对任意a1212，(2)所以零元为2.设为集合0,1,2,3,4上的二元运算，其定义为：I52a b (ab)mod5，对于任意a,b(1)(2)(3)解：写出运算说明运算写出所有可逆元的逆元1 )运算表为的运算表；是否满足交换律、结合律，是否有单位元和零元、如果有请指出;01234000000101234202413303142404321(2) 运算 满足交换律、结合律，有单位元，单位元为 1，有零元，零元为 0;3) 1 的逆元为 1 , 2 的逆元为 3, 3 的逆元为 2, 4 的逆元 4, 0 没有逆元五、证明题1.设G,是一个群，试证G是交换群 当且仅当对任意的a, b G,有a2b2(a b)2.证明：充分性若在群G,中，对任意的a, bG,有a2b2(a b)2.则(a a) (b b) (a b)(a b)a (a b) ba (b a)ba bb a从而G,是一个交换群。必要性若G,是一个交换群，对任意的a, b G,有a b b a，则a (a b) ba (b a) b(a a) (b b)(a b) (ab)即a2b2(a b)2.2.证明代数系统Z,是群，其中二元运算定义如下:Z2Z，x y x y 3(这里，+，分别是整数的加法与减法运算)证明(1)运算满足交换律对任意x, y, zZ,由(xy) z(x y3) z xyz 6,x(yz)x (yz 3) xyz 6得(x y) z:x(yz),即满足结合律；(2 )有单位兀3 是单位元；(3 )任意兀素有逆兀对任意xZ,x16x.所以,Z,是群、判断题(1)n 阶完全图的任意两个不同结点的距离都为1.(对)(2)图 G 的两个不同结点Vj,Vj连接时一定邻接.(错)(3)图 G 中连接结点vi,vj的初级通路为 vi,vj之间的短程(错)(4) 在有向图中，结点v到结点vj的有向短程即为vj到vi的有向短程.(错 )(5)强连通有向图一定是单向连通的.( 对 )(6)不论无向图或有向图，初级回路一定是简单回路.(对 )(7)设图 G 是连通的，则任意指定 G 的各边方向后所得的有向图是弱连通的.(对 ) (8 )有生成树的无向图是连通的.(对)第三章图论(5) 在有 n 个结点的连通图G中，其边数二、单项选择题(1)仅由孤立点组成的图称为A.零图；B.平凡图；C.完全图；D.多重图(2 )仅由一个孤立点组成的图称为A.零图；B.平凡图；C.多重图；D.子图.(3)在任何图G中必有偶数个A.度数为偶数的结点；B.度数为奇，数的结点；C.入度为奇数的结点；D.出度为奇数的结点(A )(B )(B)(C)A.n(n 1)B .n(n 1)C.n(n 1) 2D.(n 1) 2A.最多n 1条;B.至少n 1条;(4)设G为有 n 个结点的无向完全图，贝 yG的边数为5C.最多n条；D.至少n条.(6)任何无向图G中结点间的连通关系是(B )A.偏序关系；B等价关系；C.既是偏序关系又是等价关系；D.既不是偏序关系也不是等价关系.(7)对于无向图，下列说法中正确的是. (B )A 不含平行边及环的图称为完全图B 任何两个不同结点都有边相连且无平行边及环的图称为完全图C.具有经过每条边一次且仅一次回路的图称为哈密尔顿图D 具有经过每个结点一次且仅一次回路的图称为欧拉图(8)设 D 是有向图，则 D 强连通的充分必要条件为.(C )A 略去 D 中各边方向后所得到的无向图是连通的B D 是单向连通图，且改变它的各边方向后所得到的有向图也是单向连通图C. D 的任意两个不同的结点都可以相互到达D D 是完全图(9)对于无向图 G,以下结论中 不正确的是.(A )A 如果 G 的两个不同结点是连接的，则这两个结点之间有初级回路B. 如果 G 的两个不同结点是连接的，则这两个结点之间至少有一条短程C. 如果 G 是树，则任何两个不同结点之间有且仅有一条初级通路D 如果 G 是欧拉图，则 G 有欧拉回路三、填空题1. 设树 T 中有 7 片树叶，3 个 3 度结点，其余都是 4 度结点，贝 U T 中有_ 个 4 度结点.解 用握手定理和树的性质列出方程求解，设有X个 4 度结点，7 9 4x 2(73 x 1),x 12. 设T V, E为树，T中有 4 度，3 度，2 度分支点各 1 个，问T中有 _片树叶。x片树叶，43 2 x 2(3 x 1),x 53. n 阶完全图的任意两个不同结点的距离都为 _ 14. 图G为n阶无向完全图，贝 UG共有_ 条边。n(n 1)/25. 设G为(n,m)图，则图中结点度数的总和为 _。2m6. 图 G 为欧拉图的充分必要条件是 _ . G 为无奇度结点的连通图四、解答题1.对下图所示的图 G,求(1) G 的邻接矩阵A；(2) G 的结点V1,V3之间长度为 3 的通路;解与上题解法相同，设有(3) G 的连接矩阵C；(4) G 的关联矩阵M。v1v3v1v3, v1v2v5v3, v1v2v1v3, v1v4v1v3, v1v3v5v3, v1v3v2v3, v1v3v4v3.3）由于图 G 是连通的，所以v1v2v3v4v5v111111v211111C=v311 111.v411111v511111（4）e1e2e3e4e5e6e7v110110 00v211000 01M=v301101 10v400011 00v50000 01 12. 在下面的有向图D中，回答下列问题v1v10v2v3v4v50111解 （ 1）A=v21010 1v31101 1.v41010 0v50110 0（2） 因为312121322 1A2=22411A31212 12 1112所以，结点v1,v3之间长度为 3 的通路共有7 条，它们是3 的所有有向回路;01010101010011101121(2)A200111A30112101010101011010101121所以结点V1到结点V3的长度为 3 的所有有向通路只有一条：V1V5V2V3V5V2V1V5(1)(2)(3)写出图D的邻接矩阵A; 写出结点写出结点V1到结点V3的长度为 3 的所有有向通路;V5到自身的长度为（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没有欧（3）结点V5到自身的长度为 3 的所有有向回路只有一条:3.在下面的无向图拉回路，因而不是欧拉图。第四章 数理逻辑、判断题(1) “如果 8 + 7 2,则三角形有四条边”是命题.(对(错)( 2)设P,Q都是命题公式,则PQ也是命题公式.(3)命题公式P,Q的真值分别为 0,1，则PQ的真值为 0(以上是在对P, Q所包含的命题变元的某个赋值下).(错)(4)设p :他生于 1963 年, q :他生于1964 年,则命题“他生于1963 年或 1964 年”可以符号化为p q.(对)( 5)设 P, Q 都是命题公式,则PQ 的充分必要条件为 PQ 1.( 对)(6 )逻辑结论是正确结论.(错)( 9)设A, B,C都是命题公式,则(A B C)(A C)也是命题公式.( 对)(10)命题公式P,Q的真值分别为 0, 1,则P Q的真值为 0(以上是在对P,Q所包含的命题变元的某个赋值下).(对)、单项选择题( 1 )下面哪个联结词不可交换( B)A. ；B.；C.；D.( 2)命题公式(p(p q)q是( C)A. 永假式；B.非永真式的可满足式；C. 永真式；D.等价式 .( 3 )记p:他懂法律,q:他犯法, 则命题“他只有懂法律,才不会犯法” 可符号化为(BA pqBq pCqpDp q( 4)下列命题中 假命题是( B )A 如果雪不是白的，则太阳从西边出来B 如果雪是白的，则太阳从西边出来C.如果雪不是白的，则太阳从东边出来D 只要雪不是白的，太阳就从西边出来(5 )设 A, B 都是命题公式，则 ATB 为可满足式是A B的(B ).A .充分而非必要条件B .必要而非充分条件C.充分必要条件D .既非充分又非必要条件三、填空题1. 设p:天气很冷，q:老王还是来了，则命题“虽然天气很冷，但老王还是来了”符号化为_._ p q2. 设p:天下雨，q:我骑自行车上班，则命题“如果天不下雨，我就骑自行车上班”符号化为_._ p q3. 设p, q的真值为 0,r,s的真值为 1，则命题公式(p r) ( q s)的真值为 Q4. 设p, q的真值为 0,r的真值为 1,则命题公式p (q r)的真值为 _卫_