《离散数学》练习题答案.docVIP

《离散数学》练习题一答案 一、单项选择题（每小题2分，共8分） 1—5 . D C B C C 6—10 ． A B D C A 11—15 C B C D A 16—20 C C B D C 21—25 C C B D C 26—30. D C B A D 31. C 二、填空题（每空1分，共11分） 1． 2． 、 的真值同时为1 3. * 4. 奇 5. 12 6. 7. 9 8． 9． , 的真值都为0 10. 11. 0 12. 13. 14 14. 15. 或 16. 17. 假 18. 2 19. 17 20. 0 21. 有余(补)分配格 22. 假 23. 2 24. 17 25. 0 26. 有余(补)分配格 27. 28. 29. 30. 7 31. 三、解答题（共81分） 3.(10分)设是平面图，有个顶点，条边，个面，个连通分支，证明：。 证明：对于图的每个连通分支都是连通平面图，因此由欧拉公式，有 … … 其中分别是第个连通分支中的顶点数、边数和面数，则 将上述个等式相加，有，即 4.(8分)化简下列布尔表达式。 (1) (2) 解：(1) (2) 5. (8分)证明在格中，若，则有。 证明： 因为，所以，，，， 因此， 故 6.(9分) 设，是的幂集，是集合的对称差运算，已知是群，在群中，求： (1) 关于运算的幺元； (2) 中每个元素的逆元； (3) 求元素，使得。 解：(1) ，对于任意的，有，所以关于运算的幺元是。 (2) 对于任意的，有，所以的逆元是其自身。 (3) ，使得。 7.(8分) 设是半群，其运算表如下 * 证明：是循环群。 证明：从运算表可知，是幺元，与互为逆元，以自身为逆元，所以 是群。 因为，，，所以是生成元，则是循环群。 8. (8分) 设是集合上的二元关系，若是自反的和传递的，则。 证明：由于是传递的，必有。 对任意的，因为是自反的，有，从而，所以。 综上知，。 9.(8分)设是格，其中是75的的所有正因数的集合，是上的整除关系，求中每个元素的余元素。 解：由格的哈斯图可知：1与75互为余元素，3与25互为余元素，而5和15没有余元素。 10.(6分) 证明等价式：。 证明： 11．用推理规则证明：。 证明：(1) (2) (3) (1)(2) (4) (5) (3)(4) (6) (7) (5)(6) 12．设是非空集合上的二元关系，令，证明：具有自反性，对称性。 证明：显然，所以是自反性的。 又 所以是对称的。 13. 设是独异点，并且对于中的每一个元素，都有，其中是幺元，证明：是一个阿贝尔群。 证明：由可知，中的每一个元素都以自身为逆元，所以是群。 对任意的，有 所以运算*是可交换的，因此，是一个阿贝尔群。 14. 证明：循环群是交换群。 证明：对任意的，不妨令，其中，则 因此循环群是交换群。 15. 设是一个格，，且，令 其中是格中的偏序关系，证明：是的子格。 证明：对任意的，则有，从而有 即 因此，故运算在上是封闭的，所以是的子格。 16. 证明在格中，是格中的偏序关系，，若，，则有。 证明：因为，，，所以 ，， 因此右边，故。 18. 证明：若无向图是不连通的，则其补图是连通的。 证明：因为是不连通的，则至少有两个连通分支，对于其中任意两个顶点， (1) ，在同一个连通分支中，则在另一个连通分支中任取一点，与以及与在中皆是不相邻的，因而与以及与在中都是相邻的，那么在中找到一条从到的路。 (2