离散答案4

12013–2014学年第二学期网络工程1201~03、计算机科学技术1201~05、计算机科学技术接本1308离散数学试卷（A）参考答案及评分标准一、选择题．（小题3分,共15分）1.下列语句是命题的有C。A.现在开会吗？；B.32x。；C.地球外的星球上也有人。；D.今天天气真好！。2.设():Fxx是人，():Gyy是花，(,):Hxyx喜欢y，则命题“有些人喜欢所有的花”可以逻辑符号化为B。A.(()(()(,)))xFxyGxHxy；B.(()(()(,)))xFxyGxHxy；C.(()(()(,)))xyFxGxHxy；D.(()(()(,)))xFxyGxHxy。3.设S={1,2}，()PS表示S的幂集，表示空集，则代数系统(),PS的幺元和零元分别是A。A.S与；B.与S；C.{1}与；D.{1}与S。4.设集合,ZV，其中+为普通加法，Zx，令xx2)(，则映射ZZ:是V的C。A.同构；B.满同态；C.单同态；D.零同态。5.连通非平凡的无向图G有一条欧拉回路当且仅当图GB。A.只有一个奇度顶点；B.没有奇度顶点；C.只有三个奇度顶点；D.只有两个奇度顶点。二、填空题．（每空3分，共21分）。1.(()())xAxBx的量词分配等值式为()()xAxxBx。2.设{{,},}Aabc，{,}Bcd，则AB{{,},}abd。题号一二三四五六七合计得分阅卷人河北科技师范学院装订线系（部）班级学号姓名得分阅卷人1、设p：我将去看电影，q：我看完这本书．将“得分阅卷人1、设p：我将23.设S是有穷集合，A、B是S的子集，ASA、BSB，若已知||S，||A，||B，||AB，则由包含排斥原理可得||||||||||ABSABAB。4.设有向简单图D的度序列为2,2,3,3，入度序列0,0,2,3，则D的出度序列为2,2,1,0。5.若无向图G有18条边，其顶点中除了3个顶点的度为4外，其余顶点的度均为3，则G共有11个顶点。6.设无向图,GVE是哈密顿图，1V是V的任意非空子集，则1GV的连通分支数1()pGV与1||V的关系是11()||pGVV。7.设n阶无向简单图G有m条边，T是G的一棵生成树，则对应于生成树T，G的基本回路共有1mn个。三、（16分）用等值演算法求命题公式()pqr的主析取范式与主合取范式，成真赋值及成假赋值，并指出公式类型。解先求命题公式的主析取范式()pqr(())()pqrpqr--------------2分()()()()pqrrppqqr--------------4分()()()()()()pqrpqrpqrpqrpqrpqr---------------6分()()()()()pqrpqrpqrpqrpqr13567(1,3,5,6,7)mmmmm。----------------8分根据主合取范式与主析取范式的对偶关系，得命题公式的主合取范式()pqr024(0,2,4)MMM。----------------10分根据极小项和极大项的脚码与二进制数的对应关系，可得成真赋值为：001，011，101，110，111；-----------------12分成假赋值为：000，010，100。-----------------14分公式为非永真的可满足式。-----------------16分得分阅卷人1、设p：我将去看电影，q：我看完这本书3四、1.（8分）设{1,2,3,4,6,8,12,24}A，≼是A上的整除关系，（1）画出偏序集A,≼的哈斯图；（2）指出它最大元、最小元、极大元和极小元。解（1）偏序集A,≼的哈斯图如右图所示。--------------------4分（2）偏序集A,≼的极小元为1，极大元为24；--------------6分偏序集A,≼的最小元为1，最大元为24。--------------8分2.（8分）设集合{,,}Aabc，{,}Bab，（1）求B的特征函数()Bxx；（2）在A上定以等价关系{,,,}ARIabba，求商集AR。解（1）B的特征函数为：1,;()0,BxBxxxAB。即1,;()0,Bxabxxxc或。---------------4分（2）根据A上等价关系R的定义，可得{{,},{}}ARabc。----------------8分五、（12分）设Z为整数集合，在Z上定义二元运算，Zyx,有5yxyx，证明,Z是群。证Zyx,，有*5xyyxxyZ，所以,Z是代数系统。----------------2分对Zzyx,,，有105)5()5()(zyxzyxzyxzyx，105)5()5()(zyxzyxzyxzyx，所以)()(zyxzyx，即,Z满足结合律。------------5分对xZ，令xexxeex5，则5e，即x存在单位元为5。-------------8分对xZ，令1155xxxxe，则xx101，即任意元素x存在得分阅卷人1、设p：我将去看电影，q：我看完这本书．将“我将去看电影，得分阅卷人1、设p：我将去看电影4逆元。------------11分综上所述,Z是群。--------------12分六、（10分）有向图G如图所示，给出其邻接矩阵，并用矩阵法求出G的长度为2的通路和回路总数，以及3v到1v的长度不超过2的通路总数。解所给图的邻接矩阵为0110100001011001A。-------------------3分由2011001101101100010000110010101012001100110011111A，-------------------5分可得G的长度为2的通路总数为12条，回路总数为3条；-------------------8分3v到1v的长度不超过2的通路总数为2条。-----------------10分七、（10分）电力公司在6个地点之间架设供电网，各地之间架设线路的可能情况及相应路线的费用如右图所示，边上的数字为相应线路的费用。试用Kruskal算法设计架设供电网络的方案使费用最低，并求最低费用。解问题归结为求相应图的最小生成树。--------------------1分将所给图边按权由小到大排序：34155616453614122324,,,,,,,,,vvvvvvvvvvvvvvvvvvvv，--------------------3分依据Kruskal的避圈法算法，依次添加顶点个数减一条边：3415564512,,,,vvvvvvvvvv，--------------------7分得到所给图的最小生成树如下图所示。-----8分按照所得最小生成树架设供电网络即可使费用最低，最低费用即为最小生成树的权：1224+615w。----------10分得分阅卷人1、设p：我将去看电影，q：我看完这本书．将“我将去看得分阅卷人1、设p：我将去看电影，q：我