2007年1月广工离散数学B试题

广东工业大学试卷用纸，共6页，第1页学院：专业：学号：姓名：装订线广东工业大学考试试卷(B)课程名称:离散数学考试时间:2007年1月26日(第21周星期五)题号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、单项选择题(本大题共8小题，每小题2分，共16分)1、下列语句中为命题的是[]A、天气真暖和啊！B、请别生气。C、你还记得我吗！D、我是老王。2、设P表示“天下大雨”，Q表示“他在室内运动”，将命题“如果天不下雨，他一定不会在室内运动”符号化为：[]A、P→QB、P∧QC、┐P→＞QD、┐P∨Q3、在自然数集N上，下列哪种运算是可结合的？[]Aa*b=a-bBa*b=max{a,b}Ca*b=a+2bDa*b=|a-b|4、设A={1,2,3}B={a,b,c}下列关系中为映射的是[]A、{1,a2,b3,a}B、{1,a2,c1,b}C、{1,c3,a}D、{1,a2,a2,c}5、集合A={1,2,…,10}上的关系R={x,y|x+y=10,x,yA}，则R的性质为[]A自反的B对称的C传递的，对称的D反自反的6、一棵树有2个2次结点，1个3次结点，3个4次结点，则1次结点数目是：[]A、5B、7C、9D、8广东工业大学试卷用纸，共6页，第2页7、任何图中必定有偶数个：[]A、度数为偶数的结点B、入度为偶数的结点C、度数为奇数的结点D、出度为奇数的结点8、在右图描述的偏序集中，{b,c,d}的上确界是[]A、{a,b}B、{b}C、{a}D、{f}二、填空题(本大题共10小题，每空3分，共24分)9、两个重言式的析取是_____________式，一个重言式和一个永假式的合取式是_____________式。10、公式┐(P∨Q)←→(P∧Q)的主析取范式是_____________。11、令A={}，则A的子集是_____________12、(x)(P(x)∨(y)R(y))→Q(x))中x)的辖域是_____________。13、在代数系统Z,+中，Z是整数集合，+运算是普通加法，则(2)3=_____________。14、设A={a,b}，则P(A)=_____________15、已知Π={{a}{b,c}}是A={a,b,c}的一个划分，由Π决定的A上的一个等价关系是_____________。16、已知群G的阶是8，G只能有_____________阶非平凡子群。三、简答及证明(本大题共6小题，每小题10分，共60分)17、(10分)设A，B，C为集合，证明A∩(B－C)=(A－C)∩(B－C)18、(10分)已知带权图G，如题图所示．试求图G的最小生成树，并计算该生成树的权。19、(10分)集合Ａ＝｛111、122、341、456、795、893｝，当a、b∈A，且a、b中至少有一个数字相同时，(a，b)∈R，试画出R的关系图，并写出R的所有最大相容类。20、(10分)设R是实数集，在R上定义二元运算*，x,yR–{21}，定义x*y=x+y+2xy判断R,*是否为可交换群，并给出证明。21、(10分)作出权值为7，8，9，12，16的最优树，并求该最优树的权值22、(10分)有120位学生参加考试，这次考试有A、B和C三道题。考试结果如下：有12位学生3道题都做对了，20位学生做对了A题和B题，16位学生做对了A和C，28位做对了B和C，做对A题的学生有48位学生，做对B题的56位学生，还有16位学生一道题也没做对。试求做对C题的学生有多少位？1928743第六题图5610第18题图第8题图广东工业大学试卷用纸，共6页，第3页课程名称:离散数学B卷标准答案考试时间:第21周星期五(2007年1月26日)一、单项选择题(本大题共8小题，每小题2分，共16分)12345678DCBAACCB二、填空题(本大题共8小题，每空3分，共24分)1.重言、永假2.(P￢Q)(￢PQ)3.,{}4.P(x)(y)R(y)5.66.{,{a},{b},{a,b}}7.{a,a,b,b,c,c,b,c,c,b}8.4三、(8分)解：设做对A题的学生构成集合A，做对B题的学生构成集合B，做对C题的学生构成集合C，由题意有：︱A︱＝48；︱B︱＝56；并可求得：|A∩B∩C︱＝12；1分︱A∩B︱＝20；1分︱A∩C︱＝16，1分︱B∩C︱＝28，1分︱A∪B∪C︱＝16；1分︱A∪B∪C︱＝120－16＝104；1分由容斥原理可知：︱A∪B∪C︱＝︱A︱＋︱B︱＋︱C︱－︱A∩B︱－︱A∩C︱－︱B∩C︱＋︱A∩B∩C︱1分故：︱C︱＝20＋16＋28＋104－12－48－56＝521分四、(10分)证明：①n阶无向简单图的顶点度数只可能为0,1,2,……,n–1中的某个值。2分②当存在度数为0的顶点时，不可能存在度数为n–1的顶点，顶点度数只可能为0,1,2,……,n–2，共n–1种可能；1分因为有n个顶点，有n–1种情况，所以由鸽洞定理得，必有2个或2个以上的顶点度数相同。2分③当存在度数为n–1的顶点时，不可能存在度数为0的顶点，顶点度数只可能为1,2,……,n–1，共n–1种可能；1分因为有n个顶点，有n–1种情况，所以由鸽洞定理得，必有2个或2个以上的顶点度数相同。广东工业大学试卷用纸，共6页，第4页2分综上所述，在无相简单途中，必至少有2个顶点的度数相对。2分五、(10分)1)5分2)由关系图可知最大相容类：{111,122,341}1分{341,456}1分{341,893}1分{456,893}1分{795,893}1分六、(12分)解：①封闭性。3分∵对于x,yR–{21}，x*y=x+y+2xyR，现证明x+y+2xy≠21，反证法。假设x+y+2xy=21，则212121yyx，与xR–{21}矛盾，∴二元运算*在R上是封闭的。②可结合性对于a,b,cR，2分(a*b)*c=(a+b+2ab)*c=a+b+2ab+c+2ac+2bc+4abca*(b*c)=a*(b+c+2bc)=a+b+c+2bc+2ab+2ac+4abc∴二元运算*在R上满足结合律。③求幺元2分111122341456795893广东工业大学试卷用纸，共6页，第5页对于aR，a*0=a+0+0=a0*a=0+a+0=a∴0是幺元。④求逆元，对于xR3分012221221212*222xxxxxxxxxxxxx0122212212*12222xxxxxxxxxxxxx∴12xx与x互为逆元∴R,*是群。⑤对于x,yR，2分x*y=x+y+2xyy*x=y+x+2yx=x+y+2xy∴x*y=y*x∴R,*是群可交换群七、(10分)最优树如图所示：6分最优树的权值为：4分W=(7+8)×3＋(9+12+16)×2=45+74=119八、(10分)解：前提：(x)(P(x)(Q(x)∨R(x)))，(x)(P(x)S(x))，P(a)∧┐Q(a)2分结论：(S(x)∧R(x))1分构造推理证明如下：(1)P(a)∧┐Q(a)P(2)(x)P(x)S(x)P广东工业大学试卷用纸，共6页，第6页(3)P(a)S(a)US(2)(4)P(a)T(1)(5)S(a)T(3)(4)(6)(x)(P(x)(Q(x)∨R(x)))P(7)P(a)(Q(a)∨R(a))US(6)(8)Q(a)∨R(a)T(4)(7)(9)┐Q(a)R(a)T(8)(10)┐Q(a)T(1)(11)R(a)T(9)(10)(12)S(a)∧R(a)T(5)(11)(13)(S(x)∧R(x))EG(12)上面的证明过程并不唯一。在证明中，推理过程正确：4分；推理规则使用正确：3分。