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

1装订线华南农业大学期末考试试卷（A卷）2011-2012学年第一学期考试科目：离散结构考试类型：（闭卷）考试考试时间：120分钟学号姓名年级专业题号一二三四五总分得分评阅人□林旭东□黄华伟□朱梅阶□黄沛杰考试注意事项：①本试题分为试卷与答卷2部分。试卷有五大题，共4页。②所有解答必须写在答卷上，写在试卷上不得分。一、选择题（本大题共10小题，每小题2分，共20分）1、重言式的否定是（）A、重言式B、矛盾式C、可满足式D、A-C均有可能2、)(xA：x在北京工作，)(xB：x是北京人；则命题“在北京工作的人都是北京人。”可表示为______。A、)()(xBxxAB、))()((xBxAxC、)()(xBxxAD、))()((xBxAx3、设p:天冷,q:小王穿羽绒服，下列命题中，和命题“只要天冷，小王就穿羽绒服。”一样符号化为pq的是______。A、如果天不冷，则小王不穿羽绒服。B、小王穿羽绒服仅当天冷的时候。C、除非小王穿羽绒服，否则天不冷。得分2D、只有天冷，小王才穿羽绒服4、下列哪个表达式错误_____。A、BxxABxAx)())((B、BxxABxAx)())((C、)()())()((xxQxxPxQxPxD、)()())()((xxQxxPxQxPx5、设}10,...,3,2,1{A，定义A上的关系}10,|,{yxSyxyxR，则R具有的性质为______。A、自反的B、对称的C、传递的，对称的D、传递的6、设V=R*,是代数系统,R*为非零实数的集合，为普通乘法，下面函数中是V的自同态的是______。A、f(x)=2xB、f(x)=xC、f(x)=1/xD、f(x)=x+17、设V=Z,+是代数系统,Z为整数的集合，+为普通加法在，则(2)3=_____。A、-8B、8C、-6D、68、给定下列各序列，可以构成无向简单图的度数序列为______。A、1,1,2,2,3B、1,1,2,3,3C、0,1,1,3,3D、1,3,4,4,59、具有6个顶点，12条边的连通简单平面图中，次数为3的面有______个。A、5B、6C、7D、810、在下面所示的4个图中，______不是单向连通图。二、填空题（本大题共15空，每空2分，共30分）1、p→q的主合取范式是____________________。得分A、B、C、D、3装订线2、表达式),(yxyAx中谓词的个体域是},{baD，将其中的量词消去，写成与之等价的命题公式为__________________。3、若明天是星期一或星期三，我就有课。若有课，今天必备课。我今天下午备课。所以，明天不是星期一和星期三。将命题中的4个简单命题依次符号化为，p：明天是星期一，q：明天是星期三，r：我有课，s：我备课。则推理的形式结构为：前提：______________________________；结论：_____________________。4、)),(),((yxyGyxyFx的前束范式为：____________________。5、设R，S是集合}4,3,2,1{A上的两个关系，其中}4,4,3,2,2,2,1,1{R，}4,4,2,3,3,2,2,2,1,1{S,则1)(SR____________________。6、设偏序集,A的哈斯图如右所示，若A的子集}5,4,3{B，则B的最大下界为_____。7、在整数集Z上定义二元运算，Zyx,有2yxyx，则关于运算的幺元是______。8、设a是12阶群的生成元，则a3是阶元素9、若连通平面图G有4个结点，3个面，则G有条边。10、在右边的PERT图中，关键路径为______。11、一颗带权为2,3,5,7,8,9的最优2元树，其权为______。12、1400的不同的正因子个数为______。13、满足等式84321xxxx的非负整数解的个数有______。14、n阶无向树至少有______片树叶。（n=2）三、计算题：（6+4+6+6，共22分）1、设A={1,2,3,4}，R={x，y|xA，yA且x+y5}得分1.5CM4（1）写出R的集合表达式和关系矩阵，画出R的关系图。（2）画出关系R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)的关系图。2、分别画出下面无向图A的关联矩阵和有向图B的邻接矩阵。3、求下面带权图中v1到其它顶点的最短路径及对应的权。4、设有5个城市54321,,,,vvvvv，任意两城市之间的铁路造价如下（以百万元为单位）：W(v1,v2)=4,W(v1,v3)=7,W(v1,v4)=16,W(v1,v5)=10,W(v2,v3)=13,W(v2,v4)=8,W(v2,v5)=17,W(v3,v4)=3,W(v3,v5)=10，W(v4,v5)=12。试求出连接5个城市的且造价最低的铁路网。四、证明题：（本大题共4个小题，每题6分，共24分）1、用等值演算法证明下面的等值式))(())()((RQPRPQP2、设A为整数集合，在AA上定义二元关系R：x,y,u,vRx+y=u+v，证明：R是AA上的等价关系。3、符号化下列各命题，并说明结论是否有效（用推理规则）。甲乙丙丁四人参加拳击比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。4、设G,*是群，给定a∈G，令H={yy*a=a*y,y∈G}，证明：H,*是G的子群。五、应用题（共4分）若有n个人，每个人都恰有三个朋友，则n必为偶数。华南农业大学期末考试参考答案（A卷）v1v4v2v3v5v63106432224v1v2v3v4图Be1e2e3e5e4v1v2V4V3图Ae2e1e3e4e55装订线一、选择题（本大题共10小题，每小题2分，共20分）1B2D3C4C5B6C7D8B9D10C二、填空题（本大题共15空，每空2分，共30分）1、¬p∨q；2、)),(),(()),(),((bbAabAbaAaaA；3、(p∨q)→r,r→s,s；¬p∧¬q；4、)),(),((zxGyxFzyx；5、{1,1,2,2,2,3,3,2,3,34,4}；6、2；7、2；8、4；9、5；10、v1v3v7v8；11、83；12、24；13、165（或811C，或311C）14、2三、计算题：（6+4+6+6，共22分）1、R的集合表达式：}1,3,2,2,1,2,3,1,2,1,1,1{RR的关系矩阵:R的关系图：R的自反闭包r(R)关系图：对称闭包s(R)关系图：传递闭包t(R)关系图：得分得分得分00000001001101111.5CM62、图A的关联矩阵：图B的邻接矩阵：1000011000001100111200002000100100103、解：用标号法解题如下：rviv1v2v3v4v5v6003413/v141324/v176376/v31047/v3959/v4w034769v1到v2的最短路径:v1v2，对应的权为3v1到v3的最短路径:v1v3，对应的权为4v1到v4的最短路径:v1v3v4，对应的权为7v1到v5的最短路径:v1v3v5，对应的权为6v1到v6的最短路径:v1v3v4v6，对应的权为94、解：将本题用带权图来描述，如下图(a)，于是求解此题便成为求带权图的最小生成树问题。按Kruskal算法，下图中(b)-(e)就是求解最小生成树的过程。7装订线总造价=3+4+7+10=24万元四、证明题：（本大题共4个小题，每题5分，共20分）1、证明：从左边开始演算:)()(RPQP)()(RPQP)(RQP)((RQP2、证明：(1)自反性：对于任意的AyxA,Ryxyxyxyx,,,(2)对称性：对于任意的Rvuyx,,,Ryxvuyxvuvuyx,,,(3)传递性：对于任意的RsrvuRvuyx,,,,,,Rsryxsryxsrvuvuyx,,,3、证明：1.解：设p:甲获胜；q：乙获胜；r：丙获胜；s：丁不败（或丁获胜）。得分8前提为：qp；qr；sp结论为：sr（1）r（2）qr（3）q（4）qp（5）p（6）sp（7）s4、证明：对于任一a∈G，e*a=a*e，群G的幺元e∈H,所以H是G的非空子集。任取a,b∈H，下面证明a*b1与G中所有的元素都可交换.x∈G，有(a*b1)*x=a*b1*x=a*b1*(x1)1=a*(x1*b)1=a*(b*x1)1=a*(x*b1)=(a*x)*b1=(x*a)*b1=x*(a*b1)由此可知，a*b1∈H由子群判定定理可知H,*是G的子群。五、应用题：（共4分）证明：证明：将每个人用结点表示，当两个人是朋友时，则对应两结点连一条边，则得一无向图EVG,。因为每个人恰有三个朋友，所以，)(,3)deg(Vuu，由任意图奇数度结点一定是偶数个，可知，此图结点数一定是偶数。得分