华南农业大学离散数学期末考试试卷及答案

华南农业大学期末考试试卷（华南农业大学期末考试试卷（A A 卷）卷） 2011-20122011-2012 学年第学年第一一 学期学期考试科目：离散结构考试科目：离散结构 考试类型：考试类型： （闭卷）考试（闭卷）考试考试时间：考试时间：120120分分 钟钟 学号姓名年级专业 题号题号 得分得分 一一二二三三四四五五总分总分 评阅人评阅人□□ 林旭东林旭东□□ 黄华伟黄华伟 □□ 朱梅阶朱梅阶 □□ 黄沛杰黄沛杰 考试注意事项：考试注意事项： ①本试题分为试卷与答卷①本试题分为试卷与答卷 2 2 部分。试卷有五大题，共部分。试卷有五大题，共4 4 页。页。 ②所有解答必须写在答卷上，写在试卷上不得分。②所有解答必须写在答卷上，写在试卷上不得分。 得分得分 一、选择题一、选择题（本大题共 10 小题，每小题 2 分，共 20 分） 1、重言式的否定是（） A、重言式B、矛盾式C、可满足式D、 A-C 均 有可能 2、 A(x)：x 在北京工作，B(x)： x 是北京人；则命题“在北京工 作的人都是北京人。 ”可表示为______。 A、xA(x) B(x) B、x(A(x)  B(x)) C、xA(x)  B(x) D、x(A(x)  B(x)) 3、 设p:天冷,q:小王穿羽绒服， 下列命题中， 和命题 “只要天冷， 小王就穿羽绒服。 ”一样符号化为p®q的是______。 A、如果天不冷，则小王不穿羽绒服。 B、小王穿羽绒服仅当天冷的时候。 C、除非小王穿羽绒服，否则天不冷。 D、只有天冷，小王才穿羽绒服 4、下列哪个表达式错误_____。 A、 B、 C、 D、 x(A(x)  B)  xA(x) B x(A(x) B)  xA(x) B x(P(x)Q(x))  xP(x)xQ(x) x(P(x) Q(x))  xP(x) xQ(x) 5、设A {1,2,3,.,10}，定义 A 上的关系R { x,y | x,yS  x y 10}， 则 R 具有的性质为______。 A、自反的B、对称的C、传递的，对称的D、 传递的 6、设V=是代数系统, R*为非零实数的集合，×为普通 乘法，下面函数中是V 的自同态的是______。 A、f(x)=2xB、f(x)= -xC、f(x)=1/xD、f(x)=x+1 1 / 11 7、设V=是代数系统, Z为整数的集合，+为普通加法在， 则(-2)-3= _____。 A、-8B、8C、-6D、6 8、 给定下列各序列， 可以构成无向简单图的度数序列为______。 A、1,1,2,2,3B、1,1,2,3,3C、0,1,1,3,3D、 1,3,4,4,5 9、具有6 个顶点，12条边的连通简单平面图中，次数为3的面有 ______个。 A、5B、 6C、 7D、 8 10、在下面所示的4个图中，______不是单向连通图。 得分得分 A、B、C、D、 二、填空题题（本大题共 15 空，每空 2 分，共 30 分） 1、p→q 的主合取范式是____________________。 2、表达式xyA(x, y)中谓词的个体域是 D {a,b}，将其中的量词 消去，写成与之等价的命题公式为__________________。 3、若明天是星期一或星期三，我就有课。若有课，今天必备课。 我今天下午备课。所以， 明天不是星期一和星期三。将命题 中的4个简单命题依次符号化为，p：明天是星期一，q：明 天是星期三，r：我有课，s：我备课。则推理的形式结构为： 前 提 ： ______________________________ ； 结 论 ： _____________________。 4、____________________。 x(yF(x, y)  yG(x, y))的前束范式为： 5 、 设R，S是 集 合 A {1,2,3,4} 上 的 两 个 关 系 ， 其 中 R {1,1, 2,2 , 2,3 , 4,4 }，S {1,1, 2,2 , 2,3 , 3,2 , 4,4 } , 则 (R S)1____________________。 6、设偏序集  A,的哈斯图如右所示，若 A的子集 B {3,4,5}，则B的最大下界为_____。 7、在整数集 Z 上定义二元运算  ， x, yZ 有 x y  x  y 2，则关于运算 的幺元是______。 8、设a是12阶群的生成元，则a3是阶元素 9、若连通平面图 G 有 4 个结点，3 个面，则 G 有条边。 10、在右边的PERT图中，关键路径为______。 11、一颗带权为2,3,5,7,8,9的最优2元树，其 权为______。 12、1400 的不同的正因子个数为______。 13、满足等式 x1 x2 x3 x48的非负整数解的个数有______。 14、n阶无向树至少有______片树叶。 （n=2） 得分得分 3 / 11 三、计算题三、计算题： （6+4+6+6，共 22 分）） 1、设A={1, 2, 3, 4}，R={|xA，yA且x+yÎRÛx+y =u+v，证明：R是A´A上的等价 关系。 3、符号化下列各命题，并说明结论是否有效（用推理规则） 。 甲乙丙丁四人参加拳击比赛，如果甲获胜，则乙失败；如果丙 获胜，则乙也获胜，如果甲不获胜，则丁不失败。所以，如果 丙获胜，则丁不失败。 4、设是群，给定a∈G，令H={y 明：是G的子群。 五、应用题（共五、应用题（共 4 4 分）分） 若有 n 个人，每个人都恰有三个朋友，则 n 必为偶数。 y*a=a*y, y∈G}，证 华南农业大学期末考试参考答案（华南农业大学期末考试参考答案（A A 卷）卷） 一、选择题一、选择题（本大题共 10 小题，每小题 2 分， 共 20 分） 1 6 B B C C 2 7 D D D D 3 8 C C B B 4 9 C C D D 得分得分 5 10 B B C C 5 / 11 二、填空题题（本大题共 15 空，每空 2 分，共 30 分） 得分得分 1、¬p∨q；2、(A(a,a) A(a,b))(A(b,a) A(b,b))； 3、 (p∨q)→r,r→s,s； ¬p∧¬q ； 4、 xyz(F(x, y)  G(x,z))； 5、{1,1,2,2 ,2,3 ,3,2 ,3,34,4 }； 6、2；7、 2； 8、4；9、5；10、v 1v3v7v8； 83 11、83；12、24；13、165（或C 11，或 C 11 ） 14、2 三、计算题：三、计算题： （（6+4+6+6，共 22 分）） 1 1、、 R的集合表达式： R {1,1,1,2 ,1,3, 2,1, 2,2 ,3,1} 得分得分 R的关系矩阵:R的关系图： 1 1  1  0 11 0 100  00 0  000 R的自反闭包r(R