东北师范大学2013年《离散数学》练习题和答案.doc

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

14、设集合，是上的整除关系，则的关系矩阵 ，哈斯图为 。6设：我们勤奋，：我们好学，：我们取得好成绩。命题“只要勤奋好学，我们就能取得好成绩”符号化为 。7某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数是 。8. 设集合，是上的二元关系，且，则的对称闭包= 。9. 设、是集合，若，则到的单射函数有 个。10. 整数加法群的幺元是 。11. 设是分配格，若对任意的，都有，则 。12. 任何简单图中顶点的度数之和等于边数的 倍。13. 当为 数时，必为欧拉图。14设：我有钱，：我去看电影，命题“如果我有钱，那么我就去看

15、电影”符号化为 。15某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数是 。1616. 设集合，是上的二元关系，且，则的传递闭包= 。17. 设、是集合，若，则到的单射函数有 个。18. 整数加法群的幺元是 。19. 设是分配格，若对任意的，都有，则 。20. 无向图中具有一条欧拉回路，当且仅当是连通的，并且所有顶点的度数都是 。21. 若连通简单平面图有4个顶点，3个面，则有 条边。22设、是集合，其中，则 。23集合上的关系的传递闭包 。17 第 页（共58页）24. 设是非空集合，则中的幺元是 ，零元是 。

16、25. 若连通简单平面图有6个顶点，3个面，则有 条边。26. 设是格，其中，是整除关系，则3的补元是 ，6的补元是 。 27. 设、是集合，若，则到的单射函数有 个。28设集合，则 。29设集合，是上的二元关系，且，则的传递闭包= 。30. 若连通平面简单图有4个顶点，3个面，则有 条边。31. 设是非空集合，则中的幺元是 ，零元是 。32. 设是格，其中，是整除关系，则8的补元是 ，4的补元是 。33.已知集合和，且，则从到有 个二元关系，从到有 个映射。二、单项选择题1下列集合运算中 是正确的。A. B. C. D. 2下面 是重言式。A. B. C. D. 3. 的主析取范式是 A 。

17、A. B. C. D. 4. 若是一个群，则运算“*”一定满足 。A. 交换律 B. 消去律 C. 幂等律 D. 分配律5设是整数集合，下列集合中 关于数的加法和乘法构成整环。A B C D6如下的哈斯图所示偏序集为格的是 。 7设，则下列集合中等于的是 。A B C D8下列公式中， 是析取范式。A. B. C. D. 9. 下列语句中为命题的是 。 A. 今天是阴天； B. 你身体好吗？ C. 我真快乐； D. 请不要走。10. 设是连通简单平面图，中有6个顶点8条边，则G的面的数目是 。A2个面 B3个面 C4个面 D5个面11. 设，是集合上的二元关系，称关系为的 关系。 A. 交 B

18、. 并 C. 补 D.逆12. 下面集合中, 关于数的减法是封闭的。A B C D13. 设A是有界格，若它也是有余格，只要 。A. 每一个元素有一个余元 B. 每一个元素至少有两个余元C. 每一个元素无余元 D. 每一个元素仅有一个余元14设集合，则下面集合与相等的是 。A B C D15下列公式中， 是关于两个命题变元，的极小项。A B C D16. 下列语句中不是命题的是 。A. 3是奇数 B. 请勿吸烟 C. 我是中学生 D. 4+3517. 数的加法在下列 集合上是封闭的。A B C D18. 给定下列序列，可构成无向简单图的顶点度数序列的是 。A. B. C. D. 19. 若是一

19、个群，则运算“*”一定满足 。A. 交换律 B. 消去律 C. 幂等律 D. 分配律20. 设是非空集合上的关系，则的对称闭包= 。A. B. C. D. 21下列集合运算中 是正确的。A. B. C. D. 22下面的二元关系中， 具有传递性。A. 父子关系 B. 朋友关系 C. 集合的包含关系 D. 实数的不相等关系23. 设是整数集，且设，对每一个，有， 元素0的原象的集合为 。A B C D24. 数的加法在下列集合中 上是封闭的。 A B C D25. 设无向树由3个3度顶点，2个2度顶点。其余顶点都是树叶，则有 片树叶。A. 3 B. 4 C. 5 D. 626. 设命题，的真值是

20、0，命题，的真值是1，则下列公式中真值为1的是 。A. B. C. D. 27设，则方程的解集是 。A B C D28设是非空集合上的关系，则的对称闭包= 。A. B. C. D. 29. 数的加法在下列集合中 上是封闭的。A B C D30. 给定下列序列，可构成无向简单图的顶点度数序列的是 。A. B. C. D. 31. 设是整数集，且设，对每一个，有， 元素0的原象的集合为 。A B C D32. 命题公式为 。A.重言式 B.可满足式 C.矛盾式 D.等价式三、判断题1若，则必有。( )2一个不是自反的关系，一定是反自反的。( )3. 凡陈述句都是命题。( )4有限半群必存在等幂元。

21、( )5. 任何非平凡无向图中的奇数度顶点的个数是偶数。( )6设，均为非空的集合，已知且，则一定有。( )7一个不是自反的关系，一定是反自反的。( )8. “王兰和王英是姐妹”是复合命题。( )9. 设是代数格，它所诱导的偏序格为，则对任意的，当且仅当。( )10任何非平凡树都至少有两片树叶。( )11设是偏序集，是的非空子集，若有上界，则必有最小上界。( )12. 在有界分配格中，一个元素若有补元，则补元一定是唯一的。( )13. “王兰和王英是姐妹”是复合命题。( )14若半群存在左幺元，则左幺元是唯一的。( )15. 具有两个或多个元素的格中不存在以自身为补元的元素。( )16. 两个

22、无向图同构的充分必要条件是它们的顶点个数与边的个数分别相等。( )四、解答题1(10分) 设，上的二元运算为矩阵的乘法运算，求 (1) 的运算表； (2) 的所有子群；2. (14分) 设是一个群，定义集合上的一个关系如下：证明：是集合上的一个等价关系。3. (12分)设是从格到格的满同态映射，证明：若是有界格，则格也是有界格。4. (10分) 试用推理规则证明： 5. (10分) 设是连通简单图，其中每个顶点的度数都是偶数，则对于任一顶点，图的连通分支数小于等于的度数的一半。6设是格，其中是45的所有正因数的集合，是上的整除关系，则 (1) 求每个元素的余元素； (2) 是否为有余格，是否为

23、分配格？并说明理由。7洛杉矶地区有7家汽车旅游公司，在一天中每家公司最多参观下列景点中的三个不同景点，这些景点是好莱坞、贝弗利山、迪斯尼乐园和通用电影制片厂，同一天中，参观一个景点的旅游公司不能超过一个，第一家旅游公司只参观好莱坞，第二家公司只参观好莱坞和迪斯尼乐园，第三家公司只参观通用电影制片厂，第四家只参观迪斯尼乐园和通用电影制片厂，第五家只参观好莱坞和贝弗利山，第六家只参观贝弗利山和通用电影制片厂，第七家只参观迪斯尼乐园和贝弗利山。请问这些游览可以只安排在星期一、星期三和星期五吗？8设、是命题公式，试用两种方法分别证明等价式：。9设是非空集合上的二元关系，若是自反的，证明：是自反的。10

24、. 设为实数集，：，对任意的，令，证明：是满射，并说明不是单射。11. 证明：任一序集都是格。12. 求带权1，2，3，4，5，6，7，8，9，10的最优二叉树。13. 设和都是群的子群，令，证明是的子群的充要条件是。14. 设为实数集，：，对任意的，令，证明是满射，并说明不是单射。15设、是命题公式，试用两种方法分别证明等价式：。16. 证明：三个元素以上的链不是有余格。17. 求带权1，2，3，4，5，6，7，8，9，10的最优二叉树。18设是非空集合上的二元关系，若是自反的，证明：是自反的。19. 设，其中是整数集合，证明：是整环，其中运算“+”和“ ”是关于数的普通加法和乘法。20(1

25、0分)用推理规则证明：，。21. (20分) 设是含幺环,且*满足等幂律,在上定义运算+,如下:, , 证明:是一个布尔代数，其中0和1分别是关于运算和*的幺元。22. (15分)证明：在中任意删去条边后所得到的图是哈密尔顿图。12345671-4-62-32-52-313-7-224-41-5-1-6-27-23(5分) Gladbrook饲料公司有7个谷物箱，要通过谷物管道将它们连接起来，以使谷物能从任意一个箱子转移到其它箱子，为了使建造费用最少，希望建造尽可能少的管道，在两个箱子之间建造管道的费用(以10万美元计)由下表给出，其中“-”表示不能建造管道，应该怎样建造管道才能使费用最少。2

26、4(15分)给定群，其中，是上的模6加法运算，试求： (1) 的所有生成元； (2) 的所有子群； (3) 每个子群的所有右陪集。25. (5分)设集合，是上的二元关系，试求的关系图与关系矩阵。26. (5分)设集合，是上的二元关系，试求的关系图与关系矩阵。27. (15分)给定群，其中，是上的模15加法运算，试求： (1) 的所有生成元； (2) 的所有子群； (3) 每个子群的所有右陪集。28(5分)试用克鲁斯卡尔算法求下列表格所确定的权图的最小支撑树。/47914632007695283479/96615676663011463966/837998126720071567837/1213

27、17246956669981213/41228330112671724412/29(15分)证明：如果是一个具有奇数个顶点的偶图，则不是哈密尔顿图。30(10分)用推理规则证明：，31(20分) 设是一个布尔代数，在上定义运算*，如下：，证明: 是含幺交换环。离散数学练习题一答案 一、单项选择题（每小题2分，共8分） 15 . D C B C C 610 A B D C A1115 C B C D A 1620 C C B D C 2125 C C B D C 2630. D C B A D 31. C 二、填空题（每空1分，共11分）1 2 、 的真值同时为13. *4. 奇 5. 12 6. 7. 9 8 9 , 的真值都为010. 11. 0 12. 13. 14 14. 15. 或 16. 17. 假 18. 219. 17 20. 0 21. 有余(补)分配格 22. 假 23. 2 24. 17 25. 0 26. 有余(补)分配格 27. 28. 29. 30. 731. 三、解答题（共81分）3.(10分)设是平面图，