离散数学练习题1答案.doc

离散数学练习题1答案1、 单项选择题 14 D C B C 610 A C B C D A二、填空题1 2 、 的真值同时为13. *4. 奇 5. 12 6. 7. 9 8. 14 9. 10. 或 11. 三、判断题15 F F T T F 四、计算题1.设是平面图，有个顶点，条边，个面，个连通分支，证明：。证明：对于图的每个连通分支都是连通平面图，因此由欧拉公式，有 其中分别是第个连通分支中的顶点数、边数和面数，则将上述个等式相加，有，即2.化简下列布尔表达式。(1) (2) 解：(1) (2) 3. 证明在格中，若，则有。证明： 因为，所以， 因此，故4.设，是的幂集，是集合的对称差运算，已知是群，在群中，求：(1) 关于运算的幺元； (2) 中每个元素的逆元； (3) 求元素，使得。解：(1) ，对于任意的，有，所以关于运算的幺元是。(2) 对于任意的，有，所以的逆元是其自身。(3) ，使得。5. 设是半群，其运算表如下*证明：是循环群。证明：从运算表可知，是幺元，与互为逆元，以自身为逆元，所以是群。 因为，所以是生成元，则是循环群。6. 设是集合上的二元关系，若是自反的和传递的，则。证明：由于是传递的，必有。对任意的，因为是自反的，有，从而，所以。综上知，。7.设是格，其中是75的的所有正因数的集合，是上的整除关系，求中每个元素的余元素。解：由格的哈斯图可知：1与75互为余元素，3与25互为余元素，而5和15没有余元素。8. 证明等价式：。证明： 9. 设集合，是上的二元关系，试求：(1) ； (2) 的关系图与关系矩阵； (3)、。解：(1) (2) 工aaaaaaaaaaa关系图为：(3) 五、证明题1 证明等价式：证明：2. 证明：树是一个偶图。证明：设是一棵树，对任意的，令(1) 因为是连通的，所以对任意的，必有或，因此，(2) 因为是树，与之间的基本通路有且只有一条，所以，(3) 因为是树，中无回路，所以或中的任意的两个顶点不可能是相邻的。综上，是一个偶图。3.设是群，对任意的，令，证明：是的子群。证明：对任意的，有所以经整理，得所以因此，由子群判定定理，是的子群。4. 设为实数集，对任意的，定义：证明：是双射。证明：(1) 对任意的，存在，使得所以是满射。(2) 对任意的，若，即所以，有解得：即因此是单射。综上，是双射。5. 设是含幺环,且*满足等幂律,在上定义运算+,如下:, , 证明:是一个布尔代数，其中0和1分别是关于运算和*的幺元。证明：(1) 由题设条件可知，运算+和在上是封闭的。(2) 对任意的，由书上习题结论，有从而有即，运算+和在上是可交换的。(3) 对任意的，有即所以运算对+是可分配的。另外即所以运算+对是可分配的。(4) 对任意的，有(5) 对任意的，有综上，由亨廷顿公理，是布尔代数。离散数学练习题2 答案一、单项选择题15 C C B D C611 D C B A D C2、 填空题1. 假 2. 23. 17 4. 05. 有余(补)分配格6. 7. 8. 9. 7 10. 三、计算及证明题1 用推理规则证明：证明：(1) (2) (3) (1)(2) (4) (5) (3)(4)2 设是非空集合上自反的二元关系，证明：也是自反的。证明：因为是自反的，所以，则，故也是自反的。3. 设是整数加群，在上定义：，证明：是交换群。证明：由题设，运算*在上是封闭的。对任意的，有则，即运算*是可结合的。对任意的，有所以运算*是可交换的。，对任意的，有所以2是关于运算*的幺元。对任意的，有所以关于运算*，元素的逆元是。 综上，是交换群。4. 设是一个格，且，令其中是格中的偏序关系，证明：是的子格。证明：对任意的，则有，从而有即因此，故运算在上是封闭的，所以是的子格。5. 证明在格中，是格中的偏序关系，若，则有。证明：因为，所以， 因此，故6. 假设一家化工厂要将多种化学产品利用铁路从精炼厂运到炼油厂，但是根据EPA(美国环保署)的规定，这些化学产品不能全部都装在同一节车厢里运输，因为如果它们混和起来，就会产生剧烈反应，从而引发事故，为了使费用最低，厂长希望使用尽可能少的车厢，问最少使用多少车厢？其中共有六种化学产品，不能与、或在同节车厢里运输，不能与或一起运输，不能与一起运输，不能与一起运输。兰6兰兰红5兰2红1白3兰4解：在平面上画六个顶点分别表示六种化学产品，如果两种化学产品不能在一节车厢中运输，则在这两种产品所对应的顶点之间连一条边，从而得到一个无向图，现对该图的顶点着色，如图所示，用了三种颜色，所以最少用三节车厢，第一节车厢装、和，第二节车厢装，第三节车厢装和。7设是从群到群的同态映射，分别是群与的幺元，令证明：是群的子群。证明：显然，由于，所以，因此。对任意的，则有，故所以，由子群判定定理，是群的子群。8.设是群，是的子群，在上定义二元关系如下：对任意的，当且仅当证明：(1) 是上的等价关系；(2) 对任意的，。证明：(1) 对任意的，因为是的子群，所以，有，所以是自反的。 对任意的，则有，因为是的子群，所以有，所以是对称的。 对任意的，则有，因为是的子群，所以，有，所以是传递的。 综上，是等价关系。(2) 对任意的，有，对任意的，则，故，令，则所以。 对任意的，令，其中，则，所以，故，因此，。 综上，。9用推理规则证明：。证明： (1) P (2) P(附加前提) (3) P (4) T(1)(3) I (5) T(2)(4) I (6) T(5) I (7) CP10. 设是阶简单无向图，是大于2的奇数，如果中有个奇数度的顶点，那么的补图中奇数度的顶点也是个。证明：对任意的，则，因为是奇数，所以若在中是奇数度顶点，则在中也是奇数度顶点；若在中是偶数度顶点，则在中也是偶数度顶点，因此，如果中有个奇数度的顶点，那么的补图中奇数度的顶点也是个。11. 设是从格到格的满同态映射，证明：若是有界格，则格也是有界格。证明：设的最大元和最小元分别为1与0，往证和是的最大元和最小元。 对任意的，其中，则，因为是同态映射，所以是保序映射，故有，所以和是的最大元和最小元，因此是有界格。四、简答题1设在一次国际会议上有7个人，各懂的语言如下： a：英语 b：英语和西班牙语 c：英语、汉语和俄语d：日语和西班牙语 e：德语和汉语 f：法语、日语和俄语g：法语和德语(1) 用无向简单图描述以上事实；(2) 他们中间是否任何两个人可对话(必要时通过别人作翻译)。解：在平面上做7个点分别表示这7个人，如果两个人会同一门语言，则在对应的两个点之间连一条边，则得到一个连通图，因此任何两个人可对话。2设是