离散数学试题(2008)_b(答案)

《离散数学试题(2008)_b(答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、班级：学号：姓名：装订线哈尔滨工程大学试卷考试科目：离散数学（061121，061131）考试时间：　2008.07.099:00-11:00题号一二三四五总分分数评卷人一、填空题（每小题3分，共15分）1.设F(x)：x是苹果，H(x，y)：x与y完全相同，L(x，y)：x=y，则命题“没有完全相同的苹果”的符号化（利用全称量词）为"x"y(F(x)ÙF(y)ÙØL(x，y)®ØH(x，y))．2.命题“设L是有补格，在L中求补元运算‘′’是L中的一元运算”的真值是　0　．3.设G={e，a，b，c}是Klein四元群，H=áañ是G的子群，则商群G/H={áañ，{b，

2、c}}={{e，a}，{b，c}}．4.设群G=áP({a，b，c})，Åñ，其中Å为集合的对称差运算，则由集合{a，b}生成的子群á{a，b}ñ={Æ，{a，b}}．5.已知n阶无向简单图G有m条边，则G的补图有n(n-1)/2-m　　　　条边．二、选择题（每小题3分，共15分）1.命题“只要别人有困难(p)，小王就会帮助他(q)，除非困难已经解决了(r)”的符号化为【B】A．Ø(pÙr)®q．B．(ØrÙp)®q．C．Ør®(pÙq)．D．Ør®(q®p)．2.设N为自然数集合，“£”为通常意义上的小于等于关系，则偏序集áN，£ñ是【C】A．有界格．B．有补格．C．分配

3、格．D．布尔代数．3.设n(n³3)阶无向图G=áV，Eñ是哈密尔顿图，则下列结论中不成立的是【D】A．"V1ÌV，p(G-V1)£

4、V1

5、．B．

6、E

7、³n．C．无1度顶点．D．d(G)³n/2．4.设A={a，b，c}，在A上可以定义　　个二元运算，其中有　　　　个是可交换的，有　　　　个是幂等的．【A】A．39，36，36．B．39，36，33．C．36，36，33．D．39，36，39．5.下列图中是欧拉图的有【C】A．K4，3．B．K6．C．K5．　D．K3，3．三、计算与简答题（每小题10分，共50分）1.利用等值演算方法求命题公式(pÚq)®(q®p)的主合取范

8、式；利用该主合取范式求公式的主析取范式，并指出该公式的成真赋值和成假赋值．(pÚq)®(q®p)ÛØ(pÚq)Ú(ØqÚp)Û(ØpÙØq)Ú(ØqÚp)Û(ØpÚØqÚp)Ù(ØqÚØqÚp)ÛØqÚpÛpÚØqÛM1此为公式的主合取范式．第5页共6页第6页共6页班级：学号：姓名：装订线该公式的主析取范式是m0Úm2Úm3．公式的成真赋值为00，10，11．公式的成假赋值为01．1.求群áZ18，Å18ñ的所有生成元和子群，画出áZ18，Å18ñ的子群格，指出该子群格的全下界、全上界和有补元，并求其补元．与18互质的数有1，5，7，11，13，17，因此，1，5，7，11

9、，13，17是群áZ18，Å18ñ的生成元．18的因数有1，2，3，6，9，18，因此，群áZ18，Å18ñ的子群有á1ñ=áZ18，Å18ñ，á2ñ=á{0，2，4，6，8，10，12，14，16}，Å18ñ，á3ñá9ñá1ñá2ñá6ñá18ñá3ñ=á{0，3，6，9，12，15}，Å18ñ，á6ñ=á{0，6，12}，Å18ñ，á9ñ=á{0，9}，Å18ñ，á18ñ=á{0}，Å18ñ．áZ18，Å18ñ的子群格为á{á18ñ，á9ñ，á6ñ，á3ñ，á2ñ，á1ñ}，Íñ，其哈斯图为全下界为á18ñ，全上界为á1ñ，á18ñ’=á1ñ，á1ñ’=á18ñ，á2

10、ñ’=á9ñ，á9ñ’=á2ñ，á3ñ和á6ñ没有补元．2.若R1，R2均是非空集合A上的等价关系，那么R1，R2的交R1∩R2、并R1∪R2和复合R1○R2也是A上的等价关系吗？若是，证明你的结论．R1∩R2是A上的等价关系．事实上，(1)因R1，R2是A上的自反关系，有IAÍR1，IAÍR2，因此，IAÍR1∩R2，即R1∩R2是A上的自反关系．(2)因R1，R2是A上的对称关系，有R1＝R1-1，R2＝R2-1，而(R1∩R2)-1=R1-1∩R2-1=R1∩R2，因此，R1∩R2是A上的对称关系．(3)因R1，R2是A上的传递关系，有R12ÍR1，R22ÍR2，而(

11、R1∩R2)2=(R1∩R2)o(R1∩R2)=R12∩R22∩R1oR2∩R2oR1ÍR12∩R22ÍR1∩R2，因此，R1∩R2是A上的传递关系．3265414ecbad3.设无向连通图G如下图，求其最小生成树T及T的权W(T)，写出G的对应于T的基本回路系统和基本割集系统．G的最小生成树T如图（以实线表示），权W(T)=11．G的对应于T的基本回路系统为{Cbd，Ccd，Cde}，其中Cbd=bdab，Ccd=cdabc，Cde=dead．G的对应于T的基本割集系统为{Sab，Sad，Sae，Sbc}，其中S