华中科技大学计算机学院2016年离散数学一考试点评.docx

2016年上期离散数学（一）考试点评 选择题以及填空题： 这30分题目都是基础题，不用再说什么。 解答题点评：（40分），比例较大 求主范式。 这内容说过要考的，而且我群里面也回答过同学说要考的。这道题，只要把真值表画出来，主范式立即处理了。这也是以后大家学逻辑设计时需要的知识。 当然，也可以是通过现有表达式逐步做等值变换求得。 不少人不知道怎么做。 P(x,y)为二元谓词， ?x? yP(x,y)与? y?x P(x,y)等价吗？为什么，举例说明。 这道题是教材里面的一道练习题。没做任何变化。 我在课堂上明确讲过，这不同的量词是不可以交换的，而且举例说明过。 课件上也有现成的。 还是有同学不知道怎么做，也不知道是否等价。 用谓词逻辑将下列命题符号化：（注意：不要出现代数表达式）有些实数小于其平方，但并不是每个实数小于其平方。 逻辑问题符号化是必考的内容，多次说过。这道题的表述是基本的，没有多少绕弯子的地方，也没有什么难以理解的内容。 一般在没有指定个体域的情况下，我们都用全总个体域，再用特性谓词来说明。 如： R(x)表示x是实数，L（x）表示xx的平方。则那么命题表示为 ?x(R(x) ∧L（x）) ∧?x(R(x) ∧? L（x）) 或者是：　?x(R(x) ∧L（x）) ∧?? x(R(x) →L（x）) 如果指定个体域为实数R，那么上面这个表达就不需要特性谓词了。就简单地表达成：?xL（x）∧?x? L（x） 用2元谓词的表示方法也可： R(x)表示x是实数，L（x,y）表示xy, S(x,y)表示y=x2 则那么命题表示为: ?x?y(R(x) ∧R(y) ∧S(x,y) ∧L（x,y）) ∧?x?y(R(x) ∧R(y) ∧S(x,y) ∧?L（x,y）) 出现比较多的问题： 没有指定个体域，也没有特性谓词来说明个体。 在使用全总个体域时，特性谓词跟主谓词之间到底是用合取∧ 还是蕴含→， 不少同学没搞清楚。 这一点在课堂上是讲清楚了的。 已知A={0，1，2，3，4，…, 100}, B是参加离散数学考试的90个同学. f是A到P(B) (B的幂集)的函数，其中?k∈A, f( k ) = {x|x的离散数学成绩为k，x∈B}. 问：f是否是单射？为什么 这道题答案：不是单射！ 如果大家好好做样板题（去年的考题），好好理解，这道题就不会有问题。 这道题得分率可以说是最低的。 这道题目的情况是一个很好的例子，说明一个问题：数学，尤其是离散数学，要学好就必须要理解！ 依靠死背，或者是临时复习一下，或者是刷几道题目，是解决不了什么问题的。 这道题目就是从样板题里的一道题目的一问改过来的，要想回答正确，就需要正确理解这道题目。 这道题，只有少数同学说是单射，那就错了，没办法。 大部分同学都说不是单射，能的2分。 后面的理由说对的很少。 绝大部分同学说不是单射的理由都是：因为不同的人可以有相同的分数。 但这完全不是这个函数不是单射的理由。 错误的原因： 同学们对函数的理解还不够，还停留在中学和高等数学中常见的初等函数， 还是老想着从数映射到数，或者从一般集合映射到数集的函数，也即函数值是数。 然而一般函数的概念已经推广到了任何集合到任何集合的映射。 这道题目的这个函数式从分数集合{0,1,2,3，…，100}到一个人的集合的幂集合的函数，函数值是一个集合（人的集合的一个子集）， 是幂集合的一个元素！ 这就是大家没理解清楚的。 这个函数的每一个函数值都是一个集合！ 比如说函数值f(60)就是分数是60分的所有同学，它是整个90个人的集合的一个子集。 同学们错误地把函数理解成了人的集合到分数的结合，每个人对应与一个分数！ 如果定义个函数g（大家理解的）从人的集合到分数的集合，每个人对于的函数值是其分数, 那么这道题目的函数的函数值其实就是g下的源像集合。 （正是样板题里的有的问题）。 理解清楚这个函数就容易了。 因为分数集的基数是101， 人的集合是90. 就一定会议不少分数对于不了任何人， 于是其函数值都是空集！ 所以有多个不同的分数（自变量）， 对于与相同的函数值（空集）， 当然就不是单射了。参考下面的图： 已知关系矩阵，列出二元关系，并求其传递闭包。 列出二元关系，也就是理解了关系矩阵的形成，就可以写出来，最基础的题目。至于求传递闭包，我在课堂上讲过例题，把二元关系的关系有向图画出了，对图形进行演变，如何体现课传递性，求传递闭包即可。当然也可以用矩阵计算来求，但由于是4阶的矩阵，计算比较麻烦。 如图是集合A上的一个偏序关系≤的HASSE图，请列出该二元关系≤，并指出是否存在极大极小元、最大最小元，如果存在请指出来。 这种题目我在课堂上讲过类似的例题，至少集合不同而已。一般情况下是要求同学们画出已知偏序关