国开大学2015年01月1009《离散数学（本）》期末考试参考答案

一、单项选择题(每小题3分，本题共15分)座位号C国家开放大学(中央广播电视大学)2014年秋季学期“开放本科”期末考试2015年1月题号一二三四五六分数1.若集合A={b,c,d},则下列表述正确的是().2.已知无向图G的邻接矩阵为,则G有().3.无向图G是个棵树，结点数为10,则G的边数是().A.(Vx)(A(x)AB(x))B.-(Vx)(A(x)C.(3x)(A(x)AB(x))D.-(3x)5.下面的推理正确的是().前提引入US(1).前提引入ES(1).9.设G是有8个结点的连通图，结点的度数之和为28,则可从G中删去条边后使之变成树.10.设个体域D={1,2},则谓词公式(Vx)P(x)V(3x)Q(x)消去量词后的等值式为13.存在集合A与B,使得A∈B与ASB同时成立.14.完全图K₅是平面图.五、计算题(每小题12分，本题共36分)15.设A={2,3,6,12,24,36},B为A的子集，其中B={6,12},R是A上的整除关(1)写出R的关系表达式；(2)说明R为偏序关系；(3)画出关系R的哈斯图；16.设图G=<V,E>,V={u,v₂,v₃,v₄,v₅},E={(v₁,v₂),(v₁,v₃),(v₁,v₅),(v₂,v₃),(vz,v₄),(v₂,vs),(v₃,v₄),vsvs(1)画出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出图G的补图的图形，17.求P→(QAR)的合取范式与主合取范式.六、证明题(本题共8分)18.对任意集合A,B和C,若有C≠O,则有：ASB的充分必要条件是C×AEC×B.试卷代号：1009离散数学(本)试题答案及评分标准(半开卷)(供参考)2015年1月一、单项选择题(每小题3分，本题共15分)二、填空题(每小题3分，本题共15分)三、逻辑公式翻译(每小题6分，本题共12分)11.设P:小张可以完成这项工作，Q:小李可以完成这项工作12.设P:a是偶数，Q:a能被2整除.四、判断说明题(每小题7分，本题共14分)13.正确.(3分)则有AEB且AEB.说明：举出符合条件的例均给分.14.错误.完全图Ks是有5个结点10条边，因3×5-6<10,即e≤3v-6对Ks不成立，(5分)故Ks不是平面图.(7分)五、计算题(每小题12分，本题共36分)15.(1)因为在集合A={2,3,6,12,24,36}中，集合A上的整除关系R为：R={<2,2>,<3,3>,<6,6>,<12,12>,<24,24>,<36,36>,<2,6<2,12>,<3,12>,<6,12>,<2,24>,<3,24>,<6<2,36>,<3,36>,<6,36>,<12,36>}.(3分)(2)R中的每个有序对的第一个元素都可以整除第二个元素，即R为整除关系.每个数可以整除自身，则关系R是自反的；由R的元素可看出，若x≠y,当存在<x,y>∈R,就有<y,x>+R,则说明关系R是反对称的；则说明关系R是传递的.所以A上的整除关系R为偏序关系.(6分)(3)关系R的哈斯图如图一所示：一(9分)(4)集合B的最大元素12、极大元素12、上确界为1216.(1)关系图如图二所示：图二(2)邻接矩阵(12分)(3分)(6分)(9分)