离散试题B答案.doc

制卷人签名 刘星宝 刘玉珍 2005-6 审核人签名 审核日期 适用年级专业 2004级计算机科学与技术 .200 5 年上学期20 04 级 离散数学 期末考试学院 信息工程学院 专业 计算机科学与技术 班级 学号 姓名 考试时间 120 （分钟） 考试方式 闭 卷 考试成绩 说明：请把选择填空两题的答案在第3页按要求填写，否则无效 一、单项选择题（共16题每小题2分，总计32分）1、S，T是集合，若S-T=F，则有（ B ）成立。A. ST=S; B. ST=S; C. TS2、设S=a，b，c，r(S)是S的幂集，是一个偏序集，于是在r(S)中（ C ）。A 有最大元无最小元； B有最小元无最大元；C既有最大元又有最小元； D既无最大元也无最小元3、设简单无向图G=V1，V2是二分图，则G中（ B ）奇回路。A一定包含； B一定不包含； C不一定包含；D.不能确定4、下面的命题公式中，重言式是（D ）。 A. ； B. ； C. ； D. .5、任何有限集合与其真子集均（B ）。 A.等势; B. 不能等势; C. 等势或者不等势6、X是非空有限集，|X|=n,于是X上所有不同的自反关系共有（ B ）个。A. B. C. D. 7、是有理数集合，定义乘法运算“*”为：。则的单位元是（ D ）。 A.； B.； C. 1； D. 0.8、对于任意一个环R，在R中（C ）。A有零元并且有幺元； B有零元无幺元； C有零元但不一定有幺元；D不能确定9、设R为集合X上的等价关系，于是商集X/R中的任意两个元素 ( B )。A 一定相交； B一定不相交； C不一定相交10、设P:我看书，Q:你唱歌。命题“我看书，仅当你不唱歌。”符号化为（ C ）。A. PQ； B. PQ； C. PQ； D. PQ11、 设解释I如下，个体域D=a,b,F(a,a)=(b,b)=0, F(a,b)=F(b,a)=1，在解释I下，下列公式中真值为1的是( A )A.x$yF(x,y) B. $xyF(x,y) C. xyF(x,y) D. $x$yF(x,y) 12、设G是非空有限集合，若定义在G上的乘法运算是封闭的且满足结合律和消去律，则G（A ）。A一定是群； B不一定是群； C一定不是群13、L,和L，是两个等价的格，x，yL。于是xy=y当且仅当xy=x当且仅当（C ）。Axy； Bx=y； Cyx D. x与y无关系14、环R无零因子，当且仅当R中的乘法满足（ B ）。A结合律； B消去律； C交换律； D.不能确定15、设G是p阶完全图，P0,则G为E图当且仅当P为（ A ）。A奇数； B偶数； C正整数； D.满足题意的P不存在16、 设X=a,b,c,d,e,f，Y=1,a,c,2,f,则XY的非空真子集个数为(C ) A.7 ； B. 9； C.6； D.8二、填空题（共10题每题2分，总计20分）1、x=1，2，3 ,Y=a，b,则X到Y的不同的映射共有 23 个。2、设R是集合A上的二元关系，若R具有自反性、 对称性 、 传递性 ，则R是一个等价关系。3、12阶循环群的子群共有 6 个。4、任何质数阶的群必是 循环群 ，并且其子群必是 平凡子群 。5、设下面所有谓词的论域D=a、b、c。将命题中的量词消除，则与之等值的命题公式为。6、设P、Q是两个命题。于是，的真值为假，当且仅当 p与q同时取不同的真值 。7、设T是p（p3）个顶点的树，已知T的k个顶点的度数为k+1，其余顶点的度数为1，于是p= k2+2 。8、 设T是一个有58个叶结点的完全4元树，那么分枝结点数 19 。9、设Kp是p阶完全图，v是Kp的任意顶点，于是Kp的子图Kp-v的边数为 (p-1)(p-2)/2或者(p2-3p+2)/2。10、命题公式(P(QR)S的解释(1,1,1,0)使得该公式的真值为 真 ，(1,0,1,0)使其为 假 请把选择题的答案填在下面的表格中12345678910111213141516BCBDBBDCBCAACBAC请把填空题的答案填在下面的横线中1、 8 2、 自反性、 对称性 、 3、 6 4、 循环群，平凡子群 5、 6、p与q同时取不同的真值 7、 k2+2 8、 19 9、 (p-1)(p-2)/2或者(p2-3p+2)/2 10、 真，假 三、计算题或简答（共4题，总计24分） 1、（5分）设全集试求下列集合：（直接写出结果即可）。 (1) (2) (3) (4) (5) 解：(1) (2) (3) 4,3 (4) =, (5) 2、(6分)设简单连通平面图G有9个顶点，其顶点的度分别是2,2,2,3,3,3,4,4,5，试求该图的面数r。（要求写出计算过程，否则得分为0）。解：已知图G的顶点数和各顶点度，利用2q=Sd(vi)(i=1,p)求出边数。再利用欧拉公式p-q+r=2求面数r。这里p=9; q=(2+2+2+3+3+3+4+4+5)/2=28/2=14；代入欧拉公式：p-q+r=2 9-14+r=2 r=73、(6分)设R是集合上的整除关系。 （1）（2分） 请画出关系R的Hasse图；244解：361286231（2）（2分）请分别求出A的子集的极大元、极小元、最大元和最小元；解：极大元:6,8;极小元:2;最大元:无；最小元：2（3）（2分）请分别求出A的子集的上界、下界、上确界和下确界。36解：上界：12，24，36；下界：1，2，3,6；上确界：12；下确界：64. （7分）求命题公式的主析取范式和主合取范式。(要求：主析取范式和主合取范式分别用和mi ， Mi形式表示，并写出推导过程)解：原式主合取式为=M0 （5分）主析取式为m1m2m3=（2分）关于评分标准的说明：若试卷答案与参考答案的形式不一致，只要结论正确，仍按评分标准的分值给分。四、证明（共3题每题8分，总计24分）1. 设和是集合X的两个划分，令 试证明S也是X的一个划分。 证明: .(1) 由S 定义知, ;（2分）(2) 任取和, 1=i ,j=r, 1=j,m=s .（3分）(3) 故 S 是的一个划分. （3分）2、 在2006年德国世界杯亚洲区预选赛小组赛中国队与中国香港队的最后一轮比赛中出现如下情景：若郑智向中国香港队球门传球并且李毅把球踢进中国香港队的球门,则中国队将大比分取胜。或者中国队未大比分取胜,或中国队从小组赛中出线。中国队没有从小组赛中出线。郑智向中国香港队球门传球。因此,李毅没把球踢进中国香港队的球门。试用命题逻辑的理论和归谬证明法原理来证明下列推理的正确性。(注意首先把命题符号化，若不符号化，最多只能得3分)。证明：首先符号化 设P：郑智向中国香港队球门传球。Q：李毅把球踢进中国香港队的球门。 R：中国队取胜。S：中国队从小组赛中出线。 前提： () R, RS, S,P 结论： Q证明： (1)Q 结论的否定引入 (2) RS 前提引入 (3) S 前提引入 (4) R (2)(3)析取三段论 (5) () R 前提引入 (6) (b) (4)(5)拒取式 (7) P Q (6)置换 (8)P 前提引入 (9) Q (7)(8)析取三段论 (10)Q Q (1)(9)合取 所以由归谬法原理知结论正确。评分标准：命题符号化正确3分，推理正确5分。共8分。3、 设G是一个群，a,bG，且abba，a和b的周期分别为m和n，m与n互