（最新）形成性考试

离散数学 作业要求： （1）禁止用附件提交作业。附件提交的作业计0 分。 （2）作业按题号顺序作答，乱序、不写题号等视情况扣分。 （3）选择题直接提供答案，不要抄题。 （4）卷面整洁，文字、符号以及粘贴的图等要清晰可辨。 一、单选题（每题2 分，共 15 小题） 1. 集合, ,cbaA，则下列不属于A的子集的是（） A. a B. b C. c D. ,ba 2.设全集1,2,.,9,10U的子集为A=偶数 ，B=奇数 ，则下列选项正确的是（） A.AB B.AB C.ABU D. 以上答案都不对 3. 已 知 集 合4, 3,2,1A，,cbaB，8 ,6,4 ,2, 1C, 定 义A到B的 关 系 c)(4,b),(3,a),(2,a),(1, 1，B到C的关系 (c,1)(b,6),(a,4), 2，则下列属于21 的是（） A.)8 ,1 ( B.)4, 1 ( C.)6 ,2( D.) 1 ,3( 4. 集合3,2,1A上的关系)3, 1(),1 ,2(),2, 1(R，则R具有（） A.对称性 B.自反性 C.可传递性 D.以上说法都不对 5.集合1,2,3A上的下列关系，是由A到A的函数的是（） A.(1,3),(2,3),(3,1)f B.(1,2),(3,1)g C.(1,1),(2,1),(3,2),(1,3)h D.(1,3),(2,1),(2,2)I 6. 集合,3,2, 1cbaBA，则 A到B的映射中，是单射的是（ ） A.b)b)(3,a)(2,(1, B.b)b)(3,a)(1,(1, C.c)b)(3,a)(2,(1, D.b)b)(3,b)(2,(1, 7. 下面各集合都是N的子集，（）集合在普通加法运算下是封闭的。 A.16|整除的幂可以被xx B.5|互质与xx C.30|的因子是xx D.30|xx 8. 设集合 A=1， 2，3，4，5 上偏序关系图为， 则子集 B=2，3，4的最大下界为（） D.无 9.设,L是格，则对任意 12 ,l lL，有（） A. 12212 ()()lllll B. 12212 ()()lllll C. 12112 ()()lllll D. 以上答案都不对 10. 设图G的相邻矩阵为 01101 10101 11011 00101 11110 ，则G的顶点数与边数分别为（） A.5,4 B.6, 5 C.10,4 D.8, 5 11. 无向简单图EVG,，, 54321 vvvvvV ，则|E的最大值是（） 12. 在如下各图中是欧拉图的是（） 13. QP,是真命题，R是假命题，则（） A.RQP为真 B.QPR为真 C.RPQ为假 D.PQR为假 14. 设是乌鸦x:P(x )，一样黑yx,:y),Q(x，则命题“天下乌鸦一般黑”可符号化为 （） A.),()(yxQxxP B.),()()(yxQyPxP C.),()()()(yxQyPxPyx D.),()()(yxQxPx 15. 谓词公式)()()(xQyySxFx中变元是（） 。 A. 自由变元 B. 约束变元 C. 既是自由变元也是约束变元 D. 以上答案都不对 二、简答题（每题5 分，共 6 小题） 1. 写出集合, , aa的幂集 . 2. 设(4,5)(3,3),(2,4),(1,2), 1 ，(5,4)(4,2),(2,4),(1,3), 2 ，试求关系 12的 定义域和值域。 3. 说明什么是等价关系。 4. 请解释什么是群. 5. 给定如图所示的图,GV E，求出从A到E的所有初级路。 6. 用二叉树表示算术表达式()abcd。 三、证明题（每题10 分，共 4 小题） 1. 已知CBgBAf:,:，f是单射，g是单射，证明gf是单射。 2. 设（ L, ）是一个格，, ,a b cL试证明 : 若cba，则 )()()()(cabacbba 3. 用推理法证明下式成立：(),|PQQRRP 4.由等值演算证明下列蕴涵式成立: ( ( )( )( )x y P xQ yxP x 二：简答题： 1.： 2.： 3.：等价关系定义为：设R是非空集合A上的二元关系，若R是自反的、对称的、传递的，则称R 是 A 上的等价关系。研究等价关系的目的在于将集合中的元素进行分类，选取每类的代表元素来 降低问题的复杂度，如软件测试时，可利用等价类来选择测试用例。 4.群表示一个拥有满足封闭性、结合律、有单位元、有逆元的二元运算的代数结构 5.： 6.： 三：证明题： 1.反证若 f 不是单射 , 则存在 a 不等于 b, 且都属于 A 满足 f(a)=f(b)因为 gf 是 A到 A的恒等映射 , 则有 a=gf(a)=gf(b)=b =a=b 矛盾故 f 是单射若 g 不是满射 , 则存在 aA,满足对任何bB,有 g(b) a故 gf(a ）含于 g(B), 所以 gf(a) a又因为 gf 是 A到 A的恒等映射 , 则有 a=gf(a) 故矛 盾 2.：证明因为 ab是 a,b 的最大下界 ,ab 是 a,b 的最小上界 , 故得 aba ,a ab,再由关系 的传递性得abab 因为bc是 b,c 的最大下界 ,bc 是 a,c 的最小上界 , 故得 bcc ,c bc, 再由关系的传递性得bcbc .同理： (ab)(bc)(ab)(bc) 3.：1）rs （2）? s （3）? r （4）? (pq)r （5）? (pq) （6）? p? q （7）p （8）? q 4.： 用附加前提证明法 前提： ? x(P(x) Q(x), ? xP(x) 结论： ? xp(x) 证明： 1、? xP(x) 2、P(a) 3、? x(P(x) Q(x) 4、P(a)Q( a) 5、q(a) 6、? xp(x) 已阅 1、答案： AABDA CABAD BBBCC，24 分 2、20 分 3、20 分