2005-2006学年第一学期离散数学期末考试试卷A卷(终稿)

第1页共7页南昌大学2005～2006学年第一学期期末考试试卷试卷编号：12062(A)卷课程名称：离散数学适用班级：计算机2004级1-6班姓名：学号：班级：专业：学院：信息工程学院系别：计算机系考试日期：2006年1月9日题号一二三四五六七八四十总分累分人签名12345612题分20245566810610100得分考生注意事项：1、本试卷共7页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、填空题(每小题2分，共20分)得分评阅人1、设Q表示今天我们踢足球，P表示今天下午我们有时间，则命题“今天我们踢足球，仅当下午我们有时间。”可符号化为.2、设集合A={,{a}}，则A的幂集P(A)=.3、已知序偶x-2，18=9，2x-y，则x=，y=.4、设集合A={1,2,3,4},B={6,8,12},A到B的关系R＝},,2,{ByAxxyyx,那么R－1＝.5、设X＝{a,b,c}，R是X上的二元关系，其关系矩阵为MR＝001001101，那么R的关系图为：.第2页共7页6、集合A上的关系R是反自反的，当且仅当其关系矩阵中，其关系图中.7、设A={a,b}，B={0,1,2}，那么可定义种不同的A到B的单射函数。8、设集合A={1,2,3}，B={a,b}，C={x,y,z}，BAf:，CAg:的函数，且有},3,,2,,1{bbaf，},3,,2,,1{zyxg，则f是函数，g是函数。9、设无向图G中有5条边，已知G中度为2的节点有2个，其余结点的度为3，则G中共有个结点。10、图G如右图一所示，则图G的邻接矩阵为：A=____________________二、单项选择题(每小题2分，共24分)得分评阅人1、命题公式QQP)(为()(A)矛盾式(B)可满足式(C)重言式(D)合取范式2、设C(x):x是国家级运动员，G(x):x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为()))()(()A(xGxCx))()(()B(xGxCx))()(()C(xGxCx))()(()D(xGxCx3、设集合A={{1,2,3},{4,5},{6,7,8}}，则下式为真的是()(A)1A(B){1,2,3}A(C){{4,5}}A(D)A4、设A＝{1,2},B={a,b,c},C={c,d},则A×(BC)=()(A){1,c,2,c}(B){c,1,2,c}(C){c,1,c,2,}(D){1,c,c,2}图一4v3v2v1v第3页共7页5、设命题公式)(),(PQPHQPG,则G与H的关系是（）。(A)GH(B)GH(C)HG(D)以上都不是6、设A={1，2，3}，A上的二元关系R的关系图如图二所示，则R具有的性质是（）(A)自反性(B)反对称性(C)传递性(D)反自反性7、设A={a,b,c}，A上的二元关系R={a,a,b,b,a,c}，则关系R的对称闭包s(R)为（）(A)R∪IA(B)R(C)R∪{c,a}(D)RIA8、设I是如下一个解释，D={a,b},0101),(),(),(),(bbPabPbaPaaP,则在解释I下取真值为1的公式是（）(A)(,)xyPxy.(B)(,)xyPxy.(C)(,)xPxx.(D)(,)xyPxy.9、谓词公式),()(),()()),()((yxRyzxQzyxPx中变元x（）(A)是自由变元但不是约束变元(B)既不是自由变元又不是约束变元(C)既是自由变元又是约束变元(D)是约束变元但不是自由变元10、设R为实数集合，映射:,RR2()21,xxx则是（）(A)单射而非满射(B)满射而非单射(C)双射(D)既不是单射也不是满射.11、设简单图G所有结点的度之和为12，则G一定有（）。(A)3条边(B)4条边(C)6条边(D)8条边12、设V＝{a,b,c,d},与V能构成强连通图的边集E＝（）(A){a,b,a,c,d,a,b,d,c,d}(B){a,d,b,a,b,c,b,d,d,c}(C){a,c,b,a,b,c,d,a,d,c}(D){a,d,b,a,b,d,c,d,d,c}213图二第4页共7页三、计算题及应用题(共6小题，40分)得分评阅人1、求命题公式)))(((RQQPP的主析取范式和主合取范式并表示成im和jM的形式。(5分)2、判断谓词公式))()(())((BxAxBAx是否为永真式。（其中A和B为任何公式）(5分)3、设}20,,3,2,1{S，R是S上的等价关系，且)}5(mod,|,{yxSyxyxR，求由R导出的S的划分。(6分)第5页共7页4、已知R是集合A={a,b,c,d,e}上的二元关系，且R={a,a,a,b,a,c,a,d,a,e,b,b,b,c,b,e,c,c,c,e,d,d,d,e,e,e}，(1)画出A,R的哈斯图；(2)写出子集B={a,b,c,d}的极小元、极大元、最大元、最小元。(6分)5、设某校足球队有球衣38件，篮球队有球衣15件，排球队有球衣20件，三队队员的总数为58人，其中有三人同时参加三队，试求同时参加两队的队员共有多少人？(8分)第6页共7页6、设集合X={1,2,3,4}，f和g是从X到X的函数，且}4,2max{)(mmf，mmg5)(，(1)将f和g作为关系，确定其关系矩阵fM和gM；(2)求出gfMM和fgM，并作比较；(3)求出1fM，并判断1f是否为函数？(10分)第7页共7页四、证明题(第一小题6分，第二小题10分，共16分)得分评阅人1、设R和S是二元关系，证明：111)(SRSR2、符号化下面命题，并给出构造推理证明：任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车，或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。（注：论域为人）