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

华中农业大学《离散数学》2016-2017学年第一学期期末试卷A卷姓名 年级 院系 软件学院 专业 软件工程 学号 考试科目 《离散数学》 总分 是整环。 五、（5分）求无向连通赋权图（图2）的一棵最优树，并求最优树的权。 六、（10分）求图3的一个平面嵌入并求出对偶图。图3是否是极大可平面图？为什么？ 七、（5分）设f1和f2是从代数系统<A,*>到代数系统<B,+>的同态。设g是从A到B的一个映射，使得对任意aÎA，都有：g(a)= f1(a)+ f2(a)。证明：如果<B,+>是一个可交换半群，则g是一个从<A,*>到<B,+>的同态。 e1 2 42 h h h h h h h h h 图3 4 v2 v1 v3 v4 e2 e3 e4 e5 e6 e7 e8 图1 v5 4 3 6 7 5 8 1 图2 订 线 装 （卷面成绩满分70分，平时成绩满分30分） 一、 （共20分，每小题4分）完成下列各题： 1、 求公式（P®Q）®（PÚR）的主析取范式及主合取范式。 2、 设集合X={a，b，c }，X上有多少种不同的二元关系？其中有多少种是等价关系？为什么？ 3、 试用哈斯图构造偏序集L，使L有子集Q同时满足：有最大元和最小上界、有极小元但没有最小元、有下界但没有最大下界，并解释原因。 4、 求出图1的关联矩阵、邻接矩阵和可达矩阵。 5、 设U=<X,*>是代数系统,若O是U中的零元，试证明O是U中唯一的零元。 二、 （10分）符号化下列命题，并证明结论的有效性。 每一个正整数不是奇数就是偶数，一个正整数当且仅当不能被2整除时才是奇数，7是正整数且不能被2整除。所以，7不是偶数。 三、 （10分）设R是集合X上的自反、传递的二元关系，S也是X上的二元关系，且满足：<x,y>ÎS Û <x,y>ÎR且<y,x>ÎR。证明S是X上的等价关系。 四、（10分）设〈X，+，*〉是一个代数系统，其中X={3x|x属于整数集合}，+和*是一般数的加法和乘法。证明或反证：〈X，+，*〉 本卷为 开 闭 Ö 卷 本卷为 A Ö B 卷 出题院系 信息学院 出题人 出题日期 审批人