2010离散数学试卷A(共2页).doc

《2010离散数学试卷A(共2页).doc》由会员分享，可在线阅读，更多相关《2010离散数学试卷A(共2页).doc（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上命题人：杨晓帆 涂风华 组题人：涂风华 审题人： 命题时间：2010.6.20 教务处制学院 专业、班 年级 学号 姓名 公平竞争、诚实守信、严肃考纪、拒绝作弊封线密重庆大学 离散数学试卷 2009 2010 学年 第 2 学期开课学院： 计算机学院 课程号： 考试日期： 2010.6.25考试时间： 120 分钟题 号一二三四五六七八九十总 分得 分一、 单项选择题（2分/每小题，共30分）题号12345678910答案题号1112131415答案1用P：天下大雨，Q：他去学校上课，则命题“只有天下大雨，他才不去学校上课”符号化为 【 】APQ BPQ CPQ DP

2、Q2命题公式（P（PQ）Q是 【 】A矛盾式 B蕴含式 C重言式 D可满足式3设B是不含变元x的公式，谓词公式($x)（B A（x）等价于 【 】A B ($x)A（x） BB (x)A（x） C($x) A（x）B DB A（x）4集合A=a ,B=a，b，c则下列命题不正确的是 【 】AAB= a，b BAB CA-B= DAB=b, c5设A= ，B=(A) 下列哪个表达式不成立？ 【 】A B C D6设S=1，2，3，R为S上的关系，其关系图为 则R具有（ ）的性质。A自反、对称、传递； B什么性质也没有；C反自反、反对称、传递； D自反、对称、反对称、传递。7设A=a,b，c,d,

3、B=1,2，3,4,5,则A到B的函数个数为 【 】A4+5 B4 C45 D54 8设集合A=0，1，2，3，4，5，6，+7 ：关于模7的加法，则系统A，+7的生成元的个数为 【 】A1 B2 C6 D79在自然数集合N上，下列定义的运算中可结合的只有 【 】A B C D 10下列系统中，构成群的系统是 【 】A B C D11任意具有多个等幂元的半群，它（ ）。A不能构成群 B不一定能构成群；C不能构成交换群 D能构成交换群12完全图K3的所有不同构的子图有多少个 【 】A5 B6 C7 D8学院 专业、班 年级 学号 姓名 公平竞争、诚实守信、严肃考纪、拒绝作弊封线密13在无向图中,

4、( )的结点个数必为偶数 【 】A度为偶数 B度为奇数 C入度为奇数 D出度为奇数14给定无向图，如下图所示，下面哪个边集不是其边割集（ ）。A BCD15一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ ）。A5 B7 C9 D8二、 解答题（7分/每小题，共28分）16求命题公式P(P(Q(QR)的主析取范式和主合取范式。17设，偏序集的哈斯图为求 A中极大元、极小元、最大元与最小元； 的上界和上确界，下界和下确界。18设是一个群，这里+12是模12加法，Z12=0 ，1，11，试求出的所有子群及阶为4的子群的陪集。19设有向图G=（V,E）如下图所示，求邻接矩阵，可达性矩阵P，并求长度为3的路的总数以及回路数.三、 证明题（每小题8分，共32分）20用CP规则推证： 21设R是A上一个二元关系，试证明若R是A上一个等价关系，则S也是A上的一个等价关系。22设是群，和是的子群，定义。证明：是的子群当且仅当。23设是简单的连通平面图，|V|11。证明：中存在顶点，满足deg(v)4。四、 综合应用题（共10分）24符号化并证明其结论：“每个旅客或者坐头等舱或者坐二等车。每个旅客当且仅当他富裕时坐头等舱。有些旅客富裕，并非所有的旅客都富裕。因此，有些旅客坐二等舱。”专心-专注-专业