东北师范大学2013年《离散数学》练习题和答案.doc
《东北师范大学2013年《离散数学》练习题和答案.doc》由会员分享,可在线阅读,更多相关《东北师范大学2013年《离散数学》练习题和答案.doc(58页珍藏版)》请在沃文网上搜索。
1、离散数学练习题一一、单项选择题1设集合,则下面集合与相等的是 。A BC D2设,是集合上的整除关系,下列叙述中错误的是 。A4,5,6全是的极大元 B没有最大元 C6是的上界 D1是的最大下界3. 设,则下列关系中为从到的映射是 。A BC D4. 设是4阶群,则其子群的阶不能是下面的 。A. 1 B. 2 C. 3 D. 45设,则下列集合中等于的是 。A B C D6下面有关集合之间的包含和属于关系的说法,正确的是 。 A和 B和 C和 D、和7. 设为个元素的集合,则上有 个二元关系。A B C2 D8. 数的加法在下列集合中 上是封闭的。A B C D9. 下列图形中为欧拉图的是 。
2、 10设是格,且,则 。A. = B. C. D. 没关系11设,则有 。A B C D12. 。A B C D 13. 对于一个只有4个不同元素的集合来说,上的不同的二元关系的总数为 。A4 B16 C D14. 下列代数系统中, 不构成群。A,*是模11乘法 B,*是模11乘法C为有理数集,*是普通加法 D为有理数集,*是普通乘法15. 设为有个顶点的简单图,则有 。A B C D 16设,则下列集合中等于的是( )。A B C D17设,下列选项正确的是( )。A B C D18设为个元素的集合,则上有( )个二元关系。A B C2 D19数的加法在下列集合中( )上是封闭的。A B C
3、 D20下列图形中为欧拉图的是( )。21设,则下列集合中等于的是( )。A B C D22设,下列选项正确的是( )。A B C D23设为个元素的集合,则上有( )个二元关系。A B C2 D24数的加法在下列集合中( )上是封闭的。A B C D25下列图形中为欧拉图的是( )。26下列命题中, 是错误的。A. B. C. 若,则且 D. 若,则27幂集是 。A BC D28. 下列命题公式中 为重言式。 A. B.和 C.和 D.、和29任意一个具有多个等幂元的半群 (若元素满足,则称为等幂元),该半群 。A不能构成群 B不一定能构成群 C必能构成群 D能构成交换群30设是整数集合,下
4、列集合中 关于数的加法和乘法构成整环。A B C D31设集合,又规定偏序关系“|”是集合上的“整除”关系,则下列偏序集中 能构成格。A B C D二、填空题1设为非空集合,且,则上不同的二元关系的个数为 ,上不同的映射的个数为 。2设、为两个命题,当且仅当 时,的真值为1。3. 在运算表中的空白处填入适当符号,使成为群。 *4. 当为 数时,必为欧拉图。5. 某校有足球队员38人,篮球队员15人,排球队员20人,三队队员总数为58人,且其中只有3人同时参加3种球队,那么仅仅参加两种球队的队员人数是 。6. 命题公式的主析取范式为 。7. 一棵无向树有两个2度顶点,一个3度顶点,三个4度顶点,
5、则它的树叶数为 。8设:我生病,:我去学校,命题“如果我生病,那么我不去学校”符号化为 。9 ,为两个命题,当且仅当 时,的值为0。10. 设是四个非空集合,则的充分必要条件是 。11. 在有理数集合上定义二元运算*:,则的幺元是 。12. 设是分配格,若对任意的,都有,则 。13. 某班有学生50人,有26人在第一次考试中得优,有21人在第二次考试中得优,有17人两次考试都没有得优,那么两次考试都得优的学生人数是 。14. 将布尔表达式化简得 。15. 设:我有钱,:我去看电影,命题“当且仅当我有钱时,我才去看电影”符号化为 。16. 设是群,且,则 。17命题公式是永( )式。18的主析取
6、范式中,含有( )个极小项。19. 设集合,上有一个划分,那么所对应的等价关系应有( )个序偶。20. 在有理数集合上定义二元运算*:,则的幺元是( )。21. 一个( )称为布尔代数。22命题公式是永( )式。23的主析取范式中,含有( )个极小项。24. 设集合,上有一个划分,那么所对应的等价关系应有( )个序偶。25. 在有理数集合上定义二元运算*:,则的幺元是( )。26. 一个( )称为布尔代数。27的主析取范式是 。(写出一般表示形式即可)28设集合,是上的二元关系,且,则的传递闭包 。 29设集合,是上的整除关系,则的关系矩阵 ,哈斯图为 。30. 一个连通平面图有9个顶点,它们
7、的度数分别为:2,2,2,3,3,3,4,4,5,则该图共有 个面。31. 集合上可以定义的二元运算的个数是 。三、解答题1.求带权值为 1, 3, 5, 5, 8, 12, 14, 19的最优二叉树。(只要最终结果,不要求中间过程)(8分)2求 的最小生成树。(只要最终结果,不要求中间过程。) (8分)3.设是平面图,有个顶点,条边,个面,个连通分支,证明: (10分)4.化简下列布尔表达式。 (1) (2) (8分)5.证明在格中,是格中的偏序关系,若,则有。 (8分)6. 设,是的幂集,是集合的对称差运算,已知是群,在群中,求:(1) 关于运算的幺元;(2) 中每个元素的逆元;(3) 求
8、元素,使得。 (9分)7. 设是半群,其运算表如下 (8分)证明:是循环群。*8. 设是集合上的二元关系,若是自反的和传递的,则。 (8分)9. 设是格,其中是75的的所有正因数的集合,是上的整除关系,求中每个元素的余元素。 (8分)10. 证明等价式:。 (6分)11.用推理规则证明:。12设是非空集合上的二元关系,令,证明:具有自反性,对称性。13. 设是独异点,并且对于中的每一个元素,都有,其中是幺元,证明:是一个阿贝尔群。14. 证明:循环群是交换群。15. 设是一个格,且,令 其中是格中的偏序关系,证明:是的子格。16. 证明在格中,是格中的偏序关系,若,则有。17. 给定树叶的权为
9、1,4,9,16,25,36,49,64,81,100,试构造一棵最优二叉杩。18. 证明:若无向图是不连通的,则其补图是连通的。19(10分)求带权1、2、3、4、5、6、7、8、9、10的最优二叉树。20. (10分) 设集合,是上的二元关系,试求:(1) ; (2) 的关系图与关系矩阵; (3) 、。21证明等价式:。22. 证明:树是一个偶图。23. 设是群,对任意的,令,证明:是的子群。24. 设为实数集,对任意的,定义:证明:是双射。25. 设是含幺环,且*满足等幂律,在上定义运算+,如下:, , 证明:是一个布尔代数,其中0和1分别是关于运算和*的幺元。26用推理规则证明: (1
10、0分)27设是非空集合上自反的二元关系,证明:也是自反的。(10分)28设是整数加群,在上定义:,证明:是交换群。(20分)29设是一个格,且,令其中是格中的偏序关系,证明:是的子格。(15分)30给定树叶的权为1,4,9,16,25,36,49,64,81,100,试构造一棵最优二叉杩。(10分)31假设一家化工厂要将多种化学产品利用铁路从精炼厂运到炼油厂,但是根据EPA(美国环保署)的规定,这些化学产品不能全部都装在同一节车厢里运输,因为如果它们混和起来,就会产生剧烈反应,从而引发事故,为了使费用最低,厂长希望使用尽可能少的车厢,问最少使用多少车厢?其中共有六种化学产品,不能与、或在同节车
11、厢里运输,不能与或一起运输,不能与一起运输,不能与一起运输。(15分)32用推理规则证明: (10分)33设是非空集合上自反的二元关系,证明:也是自反的。(10分)34设是整数加群,在上定义:,证明:是交换群。(20分)35设是一个格,且,令其中是格中的偏序关系,证明:是的子格。(15分)36给定树叶的权为1,4,9,16,25,36,49,64,81,100,试构造一棵最优二叉杩。(10分)37假设一家化工厂要将多种化学产品利用铁路从精炼厂运到炼油厂,但是根据EPA(美国环保署)的规定,这些化学产品不能全部都装在同一节车厢里运输,因为如果它们混和起来,就会产生剧烈反应,从而引发事故,为了使费
12、用最低,厂长希望使用尽可能少的车厢,问最少使用多少车厢?其中共有六种化学产品,不能与、或在同节车厢里运输,不能与或一起运输,不能与一起运输,不能与一起运输。(15分)38(10分)设是从群到群的同态映射,分别是群与的幺元,令证明:是群的子群。39. (14分)设是群,是的子群,在上定义二元关系如下:对任意的,当且仅当证明:(1) 是上的等价关系;(2) 对任意的,。40(10分)用推理规则证明:。41. (10分)设是阶简单无向图,是大于2的奇数,如果中有个奇数度的顶点,那么的补图中奇数度的顶点也是个。42. (12分)设是从格到格的满同态映射,证明:若是有界格,则格也是有界格。43设在一次国
13、际会议上有7个人,各懂的语言如下: a:英语 b:英语和西班牙语 c:英语、汉语和俄语d:日语和西班牙语 e:德语和汉语 f:法语、日语和俄语 g:法语和德语(1) 用无向简单图描述以上事实;(2) 他们中间是否任何两个人可对话(必要时通过别人作翻译)。44设是格,其中是30的所有正因数的集合,是上的整除关系,则 (1) 求每个元素的余元素; (2) 是否为有余格,是否为分配格?并说明理由。离散数学练习题二 一、填空题1幂集是 。2集合上可以定义的二元运算的个数是 。3集合上的关系的传递闭包 。 4一个连通平面图有8个顶点,它们的度数分别为:2,2,3,3,3,4,4,5,则该图共有 个面。5
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
10 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 东北师范大学 2013 练习题 答案