Question

怎么学好离散数学？

Answer 1

如何学好离散数学 \x0d\x0a离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。离散数学以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此他充分描述了计算机科学离散性的特点。由于离散数学在计算机科学中的重要性，因此，许多大学都把它作为研究生入学考试的专业课程中的一门，或者是一门中的一部分。 \x0d\x0a作为计算机系的一门课程，离散数学有与其它课程相通相似的部分，当然也有它自身的特点，现在我们就它作为考试内容时具有的特点作一个简要的分析。 \x0d\x0a1、定义和定理多。 \x0d\x0a离散数学是建立在大量定义上面的逻辑推理学科。因而对概念的理解是我们学习这门学科的核心。在这些概念的基础上，特别要注意概念之间的联系，而描述这些联系的实体则是大量的定理和性质。 \x0d\x0a在考试中的一部分内容就是考察大家对定义和定理的识记、理解和运用。如2002年上海交通大学的试题，问什么是相容关系。如果知道的话，很容易得分；如果不清楚，那么无论如何也得不到分数的。这类型题目往往因其难度低而在复习中被忽视。实际上这是一种相当错误的认识，在研究生入学考试的专业课试题中，经常出现直接考查对某知识点的识记的题目。对于这种题目，考生应该能够准确、全面、完整地再现此知识点。任何的模糊和遗漏，都会造成极为可惜的失分。我们建议读者，在复习的时候，对重要知识的记忆，务必以上面提到的“准确、全面、完整”为标准来要求自己，不能达到，就说明还不过关，还要下工夫。关于这一点，在后续章节中我们仍然会强调，使之贯穿于整个离散数学的复习过程中。 \x0d\x0a离散数学的定义主要分布在集合论的关系和函数部分，还有代数系统的群、环、域、格和布尔代数中。一定要很好地识记和理解。 \x0d\x0a2、方法性强。 \x0d\x0a离散数学的证明题中，方法性是非常强的，如果知道一道题用怎样的方法证明，很轻易就可以证出来，反之则事倍功半。所以在平常复习中，要善于总结，那么遇到比较陌生的题也可以游刃有余了。在本书中，我们为读者总结了不少解题方法。读者首先应该熟悉并且会用这些方法。同时我们还鼓励读者勤于思考，对于一道题，尽可能地多探讨几种解法。 \x0d\x0a3、有穷性。 \x0d\x0a由于离散数学较为“呆板”，出新题比较困难，不管什么考试，许多题目是陈题，或者稍作变化的来的。“熟读唐诗三百首，不会做诗也会吟。”如果拿到一本习题集，从头到尾做过，甚至背会的话。那么，在考场上就会发现绝大多数题见过或似曾相识。这时，要取得较好的成绩也就不是太难的事情了。 \x0d\x0a本书是专门针对研究生入学考试而编写的，适合于读者对研究生入学考试的复习。如果还有时间的话，我们可以推荐两本习题集。一本是左孝凌老师等编写的《离散数学理论、分析、题解》，另一套有三本，是耿素云老师等编写的《离散数学习题集》。这两套书大多数题都是相同的，只是由于某些符号和定义的不同，使得题目的设定和解法有些不同而已。 \x0d\x0a现在我们就分析一下研究生入学考试有哪些题型，以及我们应如何应付。 \x0d\x0a1、基础题 \x0d\x0a基础题就是考察对定义的识记，以及简单的证明和推理。题目主要集中在数理逻辑部分和集合论部分。这些题目不需要思考，很容易上手。 \x0d\x0a这一部分的题目主要问题是要防止粗心大意和对定义记忆似是而非而丢的分数。不重视这一点的人将会在考试中吃大亏。如在主合取范式中，极大项编码对应的指派与真值表对应的指派相反，这一点在许多的参考书里也会犯错误；还有是要防止没有按照一定的方法而引起的错误，如我们在数理逻辑或者集合论里作等价推演，可以省略若干不重要的步骤，只要老师和考生都清楚就可以了，而在推理理论里则不能省略任何步骤，否则被认为是逻辑错误。 \x0d\x0a我们在学习中，还要注意融会贯通，例如，数理逻辑和集合论是相通的，因此记忆或者总结方法的时候可以综合起来，这样便于比较和理解。 \x0d\x0a2、定理应用题 \x0d\x0a本部分是最“死”的一部分，它主要体现了离散数学的方法性强的特点。并且这一部分占了考试内容的大部分，我们必须在这一部分下功夫，记住了各种方法，也就拿到了离散数学的大部分分数。 \x0d\x0a下面我们就列出常用的几种应用： \x0d\x0a●证明等价关系：即要证明关系有自反、对称、传递的性质。 \x0d\x0a●证明偏序关系：即要证明关系有自反、反对称、传递的性质。（特殊关系的证明就列出来两种，要证明剩下的几种只需要结合定义来进行）。 \x0d\x0a●证明满射：函数f：X??Y，即要证明对于任意的y??Y，都有x??X，使得f(x)=y。 \x0d\x0a●证明入射：函数f：X??Y，即要证明对于任意的x1、x2??X，且x1≠x2，则f(x1) ≠f(x2)；或者对于任意的f(x1)=f(x2)，则有x1=x2。 \x0d\x0a●证明集合等势：即证明两个集合中存在双射。有三种情况：第一、证明两个具体的集合等势，用构造法，或者直接构造一个双射，或者构造两个集合相互间的入射；第二、已知某个集合的基数，如果为??，就设它和R之间存在双射f，然后通过f的性质推出另外的双射，因此等势；如果为??0，则设和N之间存在双射；第三、已知两个集合等势，然后再证明另外的两个集合等势，这时，先设已知的两个集合存在双射，然后根据剩下题设条件证明要证的两个集合存在双射。 \x0d\x0a●证明群：即要证明代数系统封闭、可结合、有幺元和逆元。（同样，这一部分能够作为证明题的概念更多，要结合定义把它们全部搞透彻）。 \x0d\x0a●证明子群：虽然子群的证明定理有两个，但如果考证明子群的话，通常是第二个定理，即设是群，S是G的非空子集，如果对于S中的任意元素a和b有a*b-1??S,则是的子群。对于有限子群，则可考虑第一个定理。 \x0d\x0a●证明正规子群：若是一个子群，H是G的一个子集，即要证明对于任意的a??G，有aH=Ha，或者对于任意的h??H，有a-1 *h*a??H。这是最常见的题目中所使用的方法。 \x0d\x0a●证明格和子格：子格没有条件，因此和证明格一样，证明集合中任意两个元素的最大元和最小元都在集合中。 \x0d\x0a图论虽然方法性没有前几部分的强，但是也有一定的方法，如最长路径法、构造法等等。 \x0d\x0a3、难题 \x0d\x0a难题就是考试中比较难以下手，大多考生作不出来，用来拉开分数档次的题。那么，遇到难题我们怎么下手分析呢？ \x0d\x0a难题主要有以下四种，我们来逐一进行分析： \x0d\x0a①综合题 \x0d\x0a综合题就是内容涵盖若干章的问题，这样的题大多数是在群论里面的陪集、拉格朗日定理、正规子群、商群这一部分中。这一部分结合的内容很多，而且既复杂又难理解，是整个离散数学中的难点。