kok电子竞技

1、2018年春季学期离散数学期末复习题第一章集合论、判断题 TOC o 1-5 h z （1）空集是任何集合的真子集.（错）是空集.（错 ）a a, a（对）（4）设集合 A 1,2, 1, 2，则 1, 22a.（对）（5）如果a A B,则aA或a B.（错）解a A B则a ABA B,即a入且a B,所以a A且aB（6）如果 AU B B,则 A B.（对）（7）设集合A3电自, B 6也白,则A B a1，b1 , a2,b2 , a3,b3 （错）（8）设集合 A 0,1,则 ,0 ,1 , 0, 0 , 0,1 是 2A到 A的关系.（对）一 A解 2 ,0,1, A，A2 A

2、,0 ,1 , 0,0 , 0,1 , 1,0 , 1,1 , A,0 , A,1 TOC o 1-5 h z （9）关系的复合运算满足交换律.（错 ）（10）是集合A上的关系具有传递性的充分必要 条件.（错 ）（11）设 是集合A上的传递关系，则也是A上的传递关系.（对）（12 ）集合A上的对称关系必不是反对称的.（错）（13）设1, 2为集合A上的等价关系，则12也是集合A上的等价关系（对）（14）设 是集合A上的等价关系，则当 a,b 时，ab（对 ）(15 )设2为集合A上的等价关系，则二、单项选择题(1)设R为实数集合，下列集合中哪一个不是空集2A. x| x 1 0,且x R2B.

3、 x | x 9 0,且xC. x| x x 1,且xR2D. x | x1,且 x R(2)设A, B为集合，若AA. BB. BC. AD.(3)下列各式中不正确的是A.B.C.D.，( )(4)设a,a,则下列各式中错误的是A. a2AB.C.a2AD. a2Aa, b,cc, dA (BC)为A.c,1 ,2,cB.1,c2,cC.1,c ,c,2D.c,1 , c,2A.C.A.B.C.D.1,b,3B的恒等关系为0,0 , 1,10,0 , b,ba, b,a,ca,ca,ba,a,b,b , 3,3B.0,0 , 1,1,3,33,3上的二元关系如下,c,a , a,b ,c,

4、ac, c , b, a ,D. 0,1 , 1,b则具有传递性的为b,ab,c,b,3 ,3,0(8)设 为集合A上的等价关系，对任意 a A,其等价类a为 (B )A.空集；B.非空集；C.是否为空集不能确定；D. x|x A.(9)映射的复合运算满足(B )A.交换律B.结合律C.哥等律D.分配律(10)设A, B是集合，则下列说法中( C )是正确的.A至ij B的关系都是 A至ij B的映射A到B的映射都是可逆的A到B的双射都是可逆的AB时必不存在 A到B的双射(11 )设A是集合，则(B )成立.#2a 2#aAX2AX A2AAD . A 2(12)设A是有限集(#A n),则A

5、上既是 又是的关系共有( B).0个1个2个n个三、填空题.设 A 1, 2,1,2,则 2A .填 2A ,1,2,1,2, 1,2,1,1,2, 2,1,2, A.设 A ,则 2A=.填 2A , , , A.设集合A, B中元素的个数分别为 #A 5, #B 7,且#5 B) 9,则集合A B中元素的个数#(A B) .3.设集合A x|1 x 100,x是4的倍数，x Z,B x|1 x 100,x是5的倍数,x Z,则A B中元素的个数为.40A.设 A a,b, 是2 上的包含于关系，则有=.,a ,b , ,A , a, a , a, A , b, b , b, A , A,

6、A .设1, 2为集合 A上的二元关系，则1.集合A上的二元关系为传递的充分必要条件是 .设集合A 0,1, 2上的关系i 0, 2 , 2, 0 及集合A到集合B 0,2,4的关系 2 a,b | a,b A B 且 a, b AnB,则 12填 0,0 , 0,2 , 2,0 , 2,2 )四、解答题1.设集合 A ,1, 2, B 1,2 ,B_ A 2B求(1) AU 2 ; (2) 2B解(1) AU 2, 1, 2, U , 1 , 2 , B,1,2, 1 , 2, B.(2) A 2B 匕所以 2A 2B2 , a,b , b,a , c,d , d,c 2.设A a,b, c

7、, d, A上的关系 a,a , b,b , c,c , d,d(1)写出的关系矩阵；(2)验证是A上的等价关系；(3)求出A的各元素的等价类。解(1)的关系矩阵为110 0110 0 M0 0 110 0 11(2)从 的关系矩阵可知：是自反的和对称的。又由于110 0110 00 0 110 0 11110 0110 00 0 110 0 11110 0110 0 M0 0 110 0 11或满足 所以是传递的。因为是自反的、对称的和传递的，所以是A上的等价关系。(3) a b a,b, c d c,d3.设集合A 1,2,3,5 ,6,15,30, 是A上的整除关系，写出的关系矩阵M画出

8、偏序集A,的哈斯图;(3)求出A的子集B 3,6,15的最小上界和最大下界;(4)判断其是否为格。1111111 TOC o 1-5 h z 0100101解：(1) M001011100010 1100001 01(3) lubB=30, glbB=3五、证明题1.设1, 2为集合A上的等价关系，试证12也是集合A上的等价关系。证明：由于1, 2是自反的，所以对任意a A, a, aa, a2 ,因而a, a i 2,即 i 2是自反的。若 a,b i 2,则 a,b i, a,b 2,由于i, 2是对称的，所以 b, a i, b, a 2,从而 b, a i 2,即i 2是对称的。若a,

9、b , b, c i 2,则a,b , b,c i, a,b , b,c 2 ,由于 i, 2是传递的，所以a,c i, a,c 2,从而 a,c i 2,即 i2是传递的。由于i2是自反的、对称的和传递的，所以 i 2是等价关系。第二章代数系统一、判断题 TOC o 1-5 h z （i ）集合A上的任一运算对 A是封闭的.（对 ）（2）代数系统的零元是可逆元.（错）（3）设A是集合，：A A A, a b b,则 是可结合的. （对 ）（4）设a, b是代数系统 A,的元素，如果abba e（e是该代数系统的单位元），则ab.（对 ）设a, b是群G,的元素，则（a b） i a i b

10、i.（错）2. 2（6）设 G,是群.如果对于任意 a,b G,有（a b） a b ,则 G,是阿贝尔群.（对）（7）设L,是格,则运算满足曷等律.（对 ）（8）设集合 A a,b,则 ,a,b, A, 是格.（对 ）（ii ） 是格.（对 ）（9）设 B,是布尔代数，则 B, 是格.（对 ）（10）设 B,是布尔代数，则对任意a,b B,有、单项选择题 TOC o 1-5 h z （1）在整数集Z上，下列哪种运算是可结合的（B ）A. a b a bB.ab maxa, bC. a b a 2bD. a b | a b |（2）下列定义的实数集 R上的运算*中可结合的是.（C ）a b a

11、 a baba2ababbabab其中，+, I I分别为实数的加法、乘法和取绝对值运算.（3）设集合A 1,2, 3,4,10 ,下面定义的哪种运算关于集合A不是封闭的xymax x, yxymin x, yxyGCDx, y,即x,y的最大公约数xyLCMx, y,即x,y的最小公倍数 TOC o 1-5 h z （4）下列哪个集关于减法运算是封闭的（B ）A. N （自然数集）；B. 2x|x Z（整数集）;C. 2x 1| x Z ;D. x|x是质数.设Q是有理数集，在 Q定义运算为a b a b ab ,则（Q,，的单位元为（D ）A. a ；B. b；C. 1 ;D. 0（6）设

12、代数系统 A, ,则下面结论成立的是.（C ）A.如果A, 是群，则 A, 是阿贝尔群B.如果 A, ,是阿贝尔群，则 A, ,是循环群C.如果A, 是循环群，则 A, 是阿贝尔群D.如果 A, 是阿贝尔群，则 A, 必不是循环群(7)循环群(Z,)的所有生成元为(D )A. 1,0B, -1 , 2C, 1,2D. 1 , -1三、填空题AA.设A为非空有限集，代数系统2 , 中，2对运算的单位元为 ,零元为.填，A.代数系统Z, 中(其中 Z为整数集合，+为普通加法)，对任意的 x I,其x 1 .填 x.在整数集合Z上定义 运算为a b a 2b,则Z, 的单位元为.解设单位元为e, a

13、 e a 2 e a ,所以e 2,又 a ( 2) a 2 ( 2) a, (2) a (2)2 aa,所以单位元为e 2.在整数集合Z上定义运算为a b a b ab,则 Z,的单位元为 .解设单位元为e, a e a e ae a, (1 a)e 0,所以e 0.设(G,)是群，对任意a,b,c G ,如果a b a c,则.填b c.设(G,)是群，e为单位元，若 G元素a满足a2 a,则a .填e 四、解答题.设 为实数集R上的二元运算，其定义为a, b2:R R, a b a b 2ab求运算的单位元和零元。2ae解：设单位元为e,则对任意a R,不0,即e(1 2a) 0 ,由a

14、的任意性知 e又对任意a R, a 0 a 0 0 a所以单位元为02a设零元为，则对任意a R,有a即 a(1 2 ) 0 ,由a的任意性知、1又对任息a R, a ( -) a - a2所以零元为2.设 为集合I5 0,1,2,3,4上的二元运算，其定义为1 2:I5 I5, a b (ab)mod5 ,对于任意 a,b I5写出运算的运算表;说明运算 是否满足交换律、结合律，是否有单位元和零元、如果有请指出;(3)写出所有可逆元的逆元解：(1 )运算表为01234000000101234202413303142404321(2)运算满足交换律、结合律，有单位元，单位元为1 ,有零元，零元

15、为0;1的逆元为 1, 2的逆元为 3, 3的逆元为2, 4的逆元 4, 0没有逆元五、证明题.设 G,是一个群，试证 G是交换群 当且仅当对任意的a, b G ,有22a b (a b).证明：充分性若在群 G,中，对任意的a, b G，有a2 b2 (a b)2 .则(a a) (b b) (a b) (a b)a (a b) b a (b a) b abba 从而 G,是一个交换群。必要性若 G,是一个交换群，对任意的a, b G ,有a b b a,则a (a b) b a (b a) b(a a) (b b) (a b) (a b) TOC o 1-5 h z -222即 a b (

16、a b).2.证明代数系统Z, 是群，其中二元运算定义如下:r 2rc：Z Z , x y x y 3(这里，+,分别是整数的加法与减法运算.)证明(1)运算满足交换律对任意x, y, z 乙由(x y) z(x y3) zxyz6,x (y z)x (yz 3)xyz6得(x y) z x (y z),即满足结合律；(2)有单位元 3是单位元；(3)任意元素有逆元对任意x Z, x 16 x.所以，Z, 是群.第三章图论一、判断题 TOC o 1-5 h z (1) n阶完全图的任意两个不同结点的距离都为1.(对)(2)图G的两个不同结点Vi,Vj连接时一定邻接.(错)(3)图G中连接结点V

17、i,Vj的初级通路为Vi,Vj之间的短程.(错)(4)在有向图中，结点 Vi到结点Vj的有向短程即为Vj到Vi的有向短程.( 错)(5)强连通有向图一定是单向连通的.( 对 )(6)不论无向图或有向图，初级回路一定是简单回路.(对 )(7)设图G是连通的，则任意指定 G的各边方向后所得的有向图是弱连通的.(对 )(8)设A是某个无向图的邻接矩阵，则 A AT (AT是A的转置矩阵).(9)设有向图D的可达矩阵为则G是单向连通的.(对)(10)有生成树的无向图是连通的.(13 )下图中为欧拉图的是( CA.B.C.D.二、单项选择题(1)仅由孤立点组成的图称为A.零图;B.平凡图;C.完全图;D

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

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

20、是树，则任何两个不同结点之间有且仅有一条初级通路D.如果G是欧拉图，则G有欧拉回路(10)设简单无向图G的邻接矩阵为A (aj)nn，记Al (ai(l)nn(l 1,2,)，则正确的是.(C )A.当M,Vj是G的两个不同结点时，a;为Vi,Vj之间长度为l的初级通路条数B.当M,Vj是G的两个不同结点时，a为w,Vj之间长度为l的简单通路条数C.当Vi,Vj是G的两个不同结点时，a;为Vi,Vj之间长度为l的的通路条数D.当V是G的结点时，a)为通过Vi的长度为l的初级回路条数M mijnm是无向图G V, E 的关联矩阵，Vi V是G中的孤立点，则(A )A.Vi对应的一行元素全为0;B

21、 .Vi对应的一行元素全为1;C.Vi对应的一列元素全为0;D.Vi对应的一列元素全为1.三、填空题.设树T中有7片树叶，3个3度结点，其余都是 4度结点，则T中有 个4度结点.解 用握手定理和树的性质列出方程求解，设有X个4度结点，7 9 4x 2(7 3 x 1) , X 1.设T V, E 为树，T中有4度，3度，2度分支点各1个，问T中有一片树叶。解与上题解法相同，设有 x片树叶，4 3 2 x 2(3 x 1) , x 5.n阶完全图的任意两个不同结点的距离都为 . 1.图G为n阶无向完全图，则 G共有 条边。n(n 1)/2.设G为(n,m)图，则图中结点度数的总和为 。 2m.设

22、图G有6结点，若各结点的度数分别为：1, 4, 4, 3, 5, 5,则G共有 条边。用握手定理 22 2m, m=11.图G为欧拉图的充分必要条件是 .曲无奇度结点的连通图 四、解答题1.对下图所示的图G,求(1 ) G的邻接矩阵A;G的结点VV3之间长度为3的通路;G的连接矩阵C ；G的关联矩阵M 。解(1)V1V2V3V4V5V101110A= V210101V311011V410100V5011007A3 =(2)因为3 12 121 3 2 2 1A2= 2 2 4 1 112 12 12 1112所以，结点V1,V3之间长度为3的通路共有7条，它们是V1V3V1V3 ,%V2 V5

23、 V3,V1V2V1V3,V1V4V1V3, V1 v3 V5 V3,V1V3V2V3, V1V3V4V3.(3)由于图G是连通的，所以V1 V2 V3 V4 V5 TOC o 1-5 h z V111111V211111C=v311111V411111(4)V511111ee263V1101v2110M=v3011v4000v500010 0000010110110000112.在下面的有向图 D中，回答下列问题(1)写出图D的邻接矩阵A;(2)写出结点v1到结点v3的长度为3的所有有向通路;(3)写出结点v5到自身的长度为3的所有有向回路；解：(1) A0 0 0 0 110 10 00

24、0 1100 0 0 0 10 10 10(2) A20 10 100 0 1110 0 1110 10 1010 10 110 1010 1121A30 112110 1010 1121所以结点v1到结点v3的长度为3的所有有向通路只有一条：v1v5V2V3(3)结点v5到自身的长度为3的所有有向回路只有一条：v5V25丫53.在下面的无向图bC: c(1)写出a,d之间的所有初级通路；(2)写出a,d之间的所有短程，并求 d(a,d)；(3)判断无向图G是否为欧拉图并说明理由。解(1) a,d之间的所有初级通路共有 7条，分别为aed, aecd, aebcd, abed, abcd, a

25、becd, abced(2) a, d之间的长度最短的通路只有1条，即aed,因而它是a,d之间唯一的短程，d(a,d) 2(3)由于无向图 G中有两个奇度顶点 deg(b) 3,deg(c) 3,所以无向图 G没有 欧拉回路，因而不是欧拉图。第四章数理逻辑一、判断题 TOC o 1-5 h z (1) “如果8 + 72,则三角形有四条边”是命题.(对 )(2)设P, Q都是命题公式，则 PQ也是命题公式.(错 )(3)命题公式P,Q的真值分别为0, 1,则P Q的真值为0(以上是在对P, Q所包含的命题变元的某个赋值下).(错)可以(4)设p :他生于1963年，q :他生于1964年，则

26、命题“他生于1963年或1964年”符号化为p q.(对)(5)设P, Q都是命题公式，则 PQ的充分必要条件为 P Q 1.(对(6)逻辑结论是正确结论.(错 )(9)设A, B, C都是命题公式，则(A B C) (A C)也是命题公式.(对(10)命题公式P,Q的真值分别为0, 1,则PQ的真值为0(以上是在对P,Q所包含的命题变元的某个赋值下)、单项选择题(1)下面哪个联结词不可交换A.B.;C.D.(2)命题公式(p (p q) q是A.永假式;B.非永真式的可满足式;C.永真式；D.等价式.(3)记p:他懂法律，q:他犯法，则命题“他只有懂法律，才不会犯法”可符号化为(B ).p

27、qq pq pD - p q(4)下列命题中假命题是(B ).A.如果雪不是白的，则太阳从西边出来B.如果雪是白的，则太阳从西边出来C.如果雪不是白的，则太阳从东边出来D.只要雪不是白的，太阳就从西边出来(5)设A, B都是命题公式，则 A-B为可满足式是 A B的(B ).A .充分而非必要条件B.必要而非充分条件C.充分必要条件D.既非充分又非必要条件三、填空题.设p:天气很冷，q:老王还是来了，则命题“虽然天气很冷，但老王还是来了符号化为. p q.设p:天下雨，q :我骑自行车上班，则命题 “如果天不下雨，我就骑自行车上班” 符号化为. p q.设p,q的真值为0, r,s的真值为1,则命题公式(p r) ( q s)的真值为.0.设p, q的真值为0 , r的真值为1,则命题公式p (q r)的真值为.0