西南大学2020年春季离散数学【0004】课程考试大作业参考答案

西南大学培训与继续教育学院课程考试试题卷 学期：2020年春季 课程名称【编号】：离散数学【0004】 A卷 考试类别:大作业 满分：100 分 - 1 -

1.请给出集合A到集合B的映射f的定义. 设R是实数集合，f: (0,1) ? R, f(x)?11?, 1?xx证明f是双射. 答： 任意给定两个集合A和B，若存在对应法则f，使得对于任意x ∈ A，均存在唯一的y∈B与它对应，则称f是集合A到B的一个映射，或称其为A到B的一个函数，记为f:A→B。 对于任意，进而且，故f是单射。 R×R，若 。由此可得，，因而，于是 对于任意R×R，取，容易得知。 由上可知，f是双射。 2. 设R是集合A上的关系，请给出R的传递闭包t(R)的定义. 下图给出的是集合A = {1，2，3，4，5}上关系R的关系图，试画出R的传递闭包t(R)的关系图,并用集合表示. 2 所求的最优2叉树树如下： 1 3 4 5 3. 请给出谓词逻辑的研究对象，并将“任何整数的平方均非负”使用谓词符号化. 答： 研究对象:个体词,谓词,量词,命题符号化 二、大作业要求 大作业共需要完成三道题： 第1题必做，满分30分； 第2-3题选作一题，满分30分； 第4-5题选作一题，满分40分. 4.解释命题公式真值表的含义，并利用真值表求命题公式?p?(q?r)???r?(q?p)?的主合取范式. 5. 给出叶赋权m叉树的定义，并求叶赋权分别为2, 3, 5, 7, 8的最优2叉树. 答： 定义： 对于2, 3, 5, 7, 8，先组合两个最小的权2+3=5, 得5, 5, 7, 8；在所得到的序列中再组合5+5=10, 重新排列后为7, 8, 10；再组合7+8=15, 得10, 15；最后组合10+15=25。 - 2 -

- 3 -