北京科技大学– 离散试题

上传人:1777****777 文档编号:37074674 上传时间:2021-11-02 格式:DOC 页数:10 大小:514.50KB
收藏 版权申诉 举报 下载
北京科技大学– 离散试题_第1页
第1页 / 共10页
北京科技大学– 离散试题_第2页
第2页 / 共10页
北京科技大学– 离散试题_第3页
第3页 / 共10页
资源描述:

《北京科技大学– 离散试题》由会员分享,可在线阅读,更多相关《北京科技大学– 离散试题(10页珍藏版)》请在装配图网上搜索。

1、北京科技大学 2007 2008学年 第 I 学期 离散数学 试卷(A)院(系) 班级 学号 姓名 试卷卷面成绩占课程考核成绩70平时 成绩占30%课程考核成绩题号一二三四五六七八小计得分装 订 线 内 不 得 答 题自 觉 遵 守 考 试 规 则,诚 信 考 试,绝 不 作 弊得 分一、判断正误(共30分,每小题1.5分)1. 树是无环连通简单图。 ( )2. 命题具有确定的真假值。 ( )3. pq和pq命题等价。 ( )4. 有向图中结点入度之和等于出度之和。 ( )5. 设R和S是非空集合A上的等价关系,则也是A上的等价关系。 ( )6. 若A为矛盾式,则A的主析取范式为1。 ( )7

2、. 量词的约束顺序对公式真假值无影响。 ( )8. 自然数集是无限集中最小的集合。 ( )9. 质数阶群必是循环群。 ( )10. 若r(R)=R,则R一定是自反的。 ( )11. 若f为函数,则(f-1)-1=f。 ( )12. 群中有幺元,零元。 ( )13. 若无向图中有两对结点的度数为奇数,则存在欧拉路。 ( )14. 任意一棵树至少有两片树叶。 ( )15. ( )16. 设是群G到群H的同态映射,若G是交换群,则H也是交换群。 ( )17. 设V,其中 + 和分别代表普通加法和乘法,则集合S-1, 0, 1可以构成V的子代数。 ( )18. 偶数阶群必含2阶元。 ( )19. 任何

3、一个循环群必定是阿贝尔群。 ( )20. , =, ( )得 分二、填空题(共30分,每个空格2分)1. 已知集合A =,1,2,则A的幂集合P(A)= 。2. 设集合A= a, b, c, d,A上的关系R= , ,则关系R2= 。3. 设集合A = 0, 1, 2, 3, 4, 5,A上的关系R = ,则R在A上构成的等价类是_ 。4. 设集合A = a, b, c, d, e,A上半序关系R的哈斯图如图1所示,则A的极小元为_ 。图15. 已知命题公式G = (PQ)R,则G的主析取范式是_ 。6. 设D:a , b,将表达式x$ y (x, y)中的量词消除后,与之等价的命题公式是 。

4、7. 设G是完全二叉树,G有15个点,其中有8个叶点,则G的分枝点数是 。8. 对下图(图2)中树的点图2中序遍历的次序是 。9. 设有限集A, B,|A| = m, |B| = n, 则笛卡儿积 AB 的子集个数有 _个.10. 设X= x | xR, x 0,1, 在X上如下定义6个函数:f1(x) = x, f2(x) =1/x, f3(x) = 1-x, f4(x) = 1/(1-x), f5(x) = (x-1)/x, f6(x) = x/(x-1), 则G = f1, f2, f3, f4, f5, f6关于函数合成运算构成群. 则子群 f1, f2 的所有的右陪集是_.11. 设

5、G是由K1, K2, K3 3个连通分支组成的平面图,则G共有 个面。12. 设GS4为4元对称群,则= .13. 设S=,则下列集合S,P(S),N,NNN,P(N),R,RR装 订 线 内 不 得 答 题自 觉 遵 守 考 试 规 则,诚 信 考 试,绝 不 作 弊中基数为的有: 。14. 一个班70个学生,在第一次考试中有36人得5分,在第二次考试中有29人得5分,如果两次考试中都没有得5分的有26人,那么两次考试都得5分的有 人。15. 的前束范式是 。得 分三、在自然推理系统F中构造下面推理的证明(8分)前提:,结论: 得 分四、试证:一个有限非交换群至少含有6个元(8分)得 分五、

6、设A=a,b,c,求出A上所有的等价关系。(10分)得 分六、对下图(图3)所示无向带权图G求一棵最小生成树T,并计算出T的权W(T)。(6分)装 订 线 内 不 得 答 题自 觉 遵 守 考 试 规 则,诚 信 考 试,绝 不 作 弊图3得 分七、设为单射函数,为在下的像。证明也是单射的。(4分)得 分八、求当连通平面图的每个面至少有5条边围成时,边数与结点数所满足的关系式(4分)一、判断正误(共30分,每小题1.5分)1. 2. 3 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.二、填空题(共30分,每个空格2分)

7、a) ,1,2,1,2,1,2,Ab) ,c) M1 0,M2 1,2,3,M3 4,5d) c,de) PQR或m5f) (F(a,a)F(a,b)(F(b,a)F(b,b)或(F(a,a)F(b,a)(F(a,b)F(b,b)g) 7h) DBKHLEAFICGMJNi)j) f1, f2,f1, f2f3 = f3, f5, f1, f2f4 = f4, f6.k) 2个l) (1234), (13)(24), (1432), (1)m) N,NNNn) 21人o)三、证明(8分)在自然推理系统F中构造下面推理的证明前提:,结论:证明:(1) 附加前提引入(2) (1) EI (1分)(

8、3) (2)化简(4) (2)化简(5) 前提引入(6) (3)EG (1分)(7) (5)(6)假言推理 (1分)(8) 前提引入(9) (4)EG (1分)(10) (8) (9)假言推理 (1分)(11) (10)EI (1分)(12) (7)UI (1分)(13) (11) (12) 假言推理 (1分)(14) (13)EG四、试证:一个有限非交换群至少含有6个元(8分)证明:由拉格朗日定理的推论知,1,2,3,5阶群都是循环群,从而是可交换的。(4分)若G为4阶群,除单位元e外,G的元素的阶或为2或为4。只有两种可能。(1) G中存在一个阶为4的元素a。此时必有G=,是由a生成的循环

9、群,由上一步的讨论知G是可交换的。(2分)(2) 若G中不存在阶为4的元素,由拉格朗日定理的推论知,除e外,G的所有元素的阶为2。设G=e,a,b,c。则。由于,(反之有a或b等于e),且,所以必有。同理,。也是可交换的。(2分)故非交换群至少有6个元素。五、设A=a,b,c,求出A上所有的等价关系。(10分)解 先求出A上有多少个不同的分划。分成一个分划块的分划 分成两个分划块的分划 、分成三个分划块的分划 因此,A上有5个不同的分划(5分),记与分划 相对应的等价关系为(5分)六、对下图所示无向带权图G求一棵最小生成树T,并计算出T的权W(T)。(6分)解:按Kruskal算法,细心的寻找在最小生成树中的边,所得最小生成树如下图所示(4分),W(T)31。(2分)七、设为单射函数,为在下的像。证明也是单射的。(4分)证明:假设,且。(1分)不妨设存在,因此且,于是,(2分)从而。(1分)八、求当连通平面图的每个面至少有5条边围成时,边数与结点数所满足的关系式(4分)解:设平面图G有n个结点,m条边和r个面,则欧拉公式为:nm+r2。(1分)因图中每个面至少有5条边围成,所以有,即,(2分)代入欧拉公式化简后得: (1分)即为所求。 离散数学 试卷 第 10 页 共 10 页

展开阅读全文
温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!