2010离散数学试卷A

重庆大学试卷教务处07版第1页共2页重庆大学离散数学试卷2009~2010学年第2学期开课学院：计算机学院课程号：18007440考试日期：2010.6.25考试方式：考试时间：120分钟题号一二三四五六七八九十总分得分一、单项选择题（2分/每小题，共30分）题号12345678910答案题号1112131415答案1．用P：天下大雨，Q：他去学校上课，则命题“只有天下大雨，他才不去学校上课”符号化为【】A．P→┑QB．┑P→QC．P∨┑QD．P∧┑Q2．命题公式（P∧（P→Q））∨┑Q是【】A．矛盾式B．蕴含式C．重言式D．可满足式3．设B是不含变元x的公式，谓词公式(x)（B→A（x））等价于【】A．B→(x)A（x）B．B→(x)A（x）C．(x)A（x）→BD．B→A（x）4．集合A={a},B={a，b，c}则下列命题不正确的是【】A．AB={a，b}B．ABC．A-B=D．AB={b,c}5．设A={}，B=ρ(ρ(A))下列哪个表达式不成立？【】A．BB．BC．BD．B6．设S={1，2，3}，R为S上的关系，其关系图为则R具有（）的性质。A．自反、对称、传递；B．什么性质也没有；C．反自反、反对称、传递；D．自反、对称、反对称、传递。7．设A={a,b，c,d},B={1,2，3,4,5},则A到B的函数个数为【】A．4+5B．4C．4•5D．548．设集合A={0，1，2，3，4，5，6}，+7：关于模7的加法，则系统〈A，+7〉的生成元的个数为【】A．1B．2C．6D．79．在自然数集合N上，下列定义的运算中可结合的只有【】A．babaB．),max(babaC．baba5D．baba10．下列系统中，构成群的系统是【】A．Z+,+B．N,×C．R,×D．R,+11．任意具有多个等幂元的半群，它（）。A．不能构成群B．不一定能构成群；C．不能构成交换群D．能构成交换群12．完全图K3的所有不同构的子图有多少个【】A．5B．6C．7D．8命题人：杨晓帆涂风华组题人：涂风华审题人：命题时间：2010.6.20教务处制学院专业、班年级学号姓名公平竞争、诚实守信、严肃考纪、拒绝作弊封线密重庆大学试卷教务处07版第2页共2页13．在无向图中,()的结点个数必为偶数【】A．度为偶数B．度为奇数C．入度为奇数D．出度为奇数14．给定无向图EVG,，如下图所示，下面哪个边集不是其边割集（）。A．},,,{4341vvvvB．},,,{6451vvvvC．},,,{8474vvvvD．},,,{3221vvvv15．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（）。A．5B．7C．9D．8二、解答题（7分/每小题，共28分）16．求命题公式P∨(┑P(Q∧(┑QR)))的主析取范式和主合取范式。17．设},,,,{54321xxxxxA，偏序集RA,的哈斯图为求①A中极大元、极小元、最大元与最小元；②},{32xx的上界和上确界，下界和下确界。18．设Z12,+12是一个群，这里+12是模12加法，Z12={[0]，[1]，…，[11]}，试求出Z12,+12的所有子群及阶为4的子群的陪集。19．设有向图G=（V,E）如下图所示，求邻接矩阵Ａ，可达性矩阵P，并求长度为3的路的总数以及回路数.三、证明题（每小题8分，共32分）20．用CP规则推证：SRRPQSQP,),(21．设R是A上一个二元关系，)},,,(),(|,{RbcRcaAcAbabaS且有对于某一个试证明若R是A上一个等价关系，则S也是A上的一个等价关系。22．设G是群，H和K是G的子群，定义|,HKhkhHkK。证明：HK是G的子群当且仅当HKKH。23．设G是简单的连通平面图，|V|≤11。证明：G中存在顶点v，满足deg(v)≤4。四、综合应用题（共10分）24．符号化并证明其结论：“每个旅客或者坐头等舱或者坐二等车。每个旅客当且仅当他富裕时坐头等舱。有些旅客富裕，并非所有的旅客都富裕。因此，有些旅客坐二等舱。”学院专业、班年级学号姓名公平竞争、诚实守信、严肃考纪、拒绝作弊封线密