华中农业大学《离散数学》2016-2017学年第一学期期末试卷B卷.doc

华中农业大学《离散数学》2016-2017学年第一学期期末试卷B卷姓名 年级 院系 软件学院 专业 软件工程 学号 考试科目 《离散数学》 总分 四、（10分）设G={}（Q是有理数集合），“”是数的乘法。 1、证明<G，>是群。 2、设映射f: GG，f()=，证明f是群<G, >上的自同态映射。 五、（8分）证明或反证：一个代数系统中两个同余关系的合成关系是同余关系。 六、（共12分，每小题6分） 1、 分别构造满足下列条件的图： （1） 是欧拉图，但不是哈密顿图； （2） 是哈密顿图，但不是欧拉图； （3） 既不是欧拉图也不是哈密顿图。 a f b c d e 图1 g 2、 设简单连通平面图G有n个顶点、m条边和k个面，试给出它们之间的关系式，并给出证明。 订 线 装 （卷面成绩满分70分，平时成绩满分30分） 一、 （共20分，每小题5分）完成下列各题： 1、 证明（"x）（C（x）®（W（x）ÙR（x））），（$x）C（x）ÙQ（x）Þ（$x）Q（x）Ù（$x）R（x） 2、 求Ø（P®Q）Ù (R®P)的析取范式和合取范式。 3、 设R是定义在集合X={1，2，3，4}上的二元关系，R={<1,1>,<1,2>,<1,4>},试求R的自反闭包、对称闭包和传递闭包。 4、 设树T有3个度为3的顶点，2个度为2的顶点，其余顶点均为树叶，问T有几片树叶？为什么？ 二、 （10分）符号化下列命题，并证明结论的有效性。 如果我去图书馆，我就去查资料；如果我去查资料，我就不去实验室；我去图书馆，或者我去上课。结论：如果我去实验室，则我去上课。 三、（10分）设集合X={a，b，c，d，e，f，g}，R是X上的偏序关系，其哈斯图见图1. 1、 写出R中的所有元素, X是否存在子集Q，Q有最大下界和最小上界。 2、 是否可给R去掉一个有序对，使Q有上界，但没有最小上界？为什么？ 本卷为 开 闭 Ö 卷 本卷为 A B Ö 卷 出题院系 信息学院 出题人 出题日期 审批人