怎样又快又好地学好离散数学.docx
《怎样又快又好地学好离散数学.docx》由会员分享，可在线阅读，更多相关《怎样又快又好地学好离散数学.docx（10页珍藏版）》请在冰点文库上搜索。
怎样又快又好地学好离散数学
怎样学好离散数学
最常和理论计算机科学放在一起的一个词是什么?
答:
离散数学。
这两者的关系是如此密切,以至于它们在不少场合下成为同义词。
（这一点在前面的那本书中也有体现）传统上,数学是以分析为中心的。
数学系的同学要学习三四个学期的数学分析,然后是复变函数,实变函数,泛函数等等。
实变和泛函被很多人认为是现代数学的入门。
在物理,化学,工程上应用的,也以分析为主。
随着计算机科学的出现,一些以前不太受到重视的数学分支突然重要起来。
人们发现,这些分支处理的数学对象与传统的分析有明显的区别:
分析研究的问题解决方案是连续的,因而微分,积分成为基本的运算;而这些分支研究的对象是离散的,因而很少有机会进行此类的计算。
人们从而称这些分支为“离散数学”。
“离散数学”的名字越来越响亮,最后导致以分析为中心的传统数学分支被相对称为“连续数学”。
《离散数学》作为一个单独的分枝,在世界上出现的时间并不久,不过几十年,但它的各部分内容中有相当一部分却早已出现在数学中。
为什么将各个数学分支中的一些内容集中起来加以研究,并且冠上一个新的名称——离散数学呢?
这主要是因为计算机科学的产生和发展。
正如恩格斯所说:
“……科学的状况还更多的从属于技术的状况和需要。
倘若社会上有了一种技术上的需要,那就比十个大学还更能推动科学前进。
”①计算机的出现,在很大程度上影响到了人们的思想和生活,对社会生产起了重大作用。
为了研究计算机科学的理论基础,离散数学也就应运而生。
因此,如果我们不从纯数学的角度,而从应用数学的角度来考虑,也许给离散数学换一个名称一一计算机科学的数学基础——更能说明问题。
正是因为这个原因,在计算机科学系。
信息管理系都将离散数学作为必须学习的基础课程。
而实践证明这种做法是正确的。
离散数学（Discretemathematics）是研究离散量的结构及其相互关系的数学学科,是现代数学的一个重要分支。
它在各学科领域,特别在计算机科学与技术领域有着广泛的应用,同时离散数学也是计算机专业的许多专业课程,如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。
通过离散数学的学习,不但可以掌握处理离散结构的描述工具和方法,为后续课程的学习创造条件,而且可以提高抽象思维和严格的逻辑推理能力,为将来参与创新性的研究和开发工作打下坚实的基础。
随着信息时代的到来,工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化,离散数学的重要性逐渐被人们认识。
离散数学课程所传授的思想和方法,广泛地体现在计算机科学技术及相关专业的诸领域,从科学计算到信息处理,从理论计算机科学到计算机应用技术,从计算机软件到计算机硬件,从人工智能到认知系统,无不与离散数学密切相关。
由于数字电子计算机是一个离散结构,它只能处理离散的或离散化了的数量关系,因此,无论计算机科学本身,还是与计算机科学及其应用密切相关的现
代科学研究领域,都面临着如何对离散结构建立相应的数学模型;又如何将已用连续数量关系建立起来的数学模型离散化,从而可由计算机加以处理。
离散数学是传统的逻辑学,集合论（包括函数）,数论基础,算法设计,组合分析,离散概率,关系理论,图论与树,抽象代数（包括代数系统,群、环、域等）,布尔代数,计算模型（语言与自动机）等汇集起来的一门综合学科。
离散数学的应用遍及现代科学技术的诸多领域。
离散数学课程主要介绍离散数学的各个分支的基本概念、基本理论和基本方法。
这些概念、理论以及方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中;同时,该课程所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高,十分有益于学生严谨、完整、规范的科学态度的培养。
离散数学课程的教学目的,不但作为计算机科学与技术及相关专业的理论基础及核心主干课,对后续课程提供必需的理论支持。
更重要的是旨在“通过加强数学推理,组合分析,离散结构,算法构思与设计,构建模型等方面专门与反复的研究、训练及应用,培养提高学生的数学思维能力和对实际问题的求解能力。
”
离散数学通常研究的领域包括:
数理逻辑、集合论、代数结构、关系论、函数论、图论、组合学、数论等。
它是高校计算机及相关专业的重要基础课程之一。
课程内容涉及:
1.集合论部分:
集合及其运算、二元关系与函数、自然数及自然数集、集合的基数
2.图论部分:
图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用
3.代数结构部分:
代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数
4.组合数学部分:
组合存在性定理、基本的计数公式、组合计数方法、组合计数定理
5.数理逻辑部分:
命题逻辑、一阶谓词演算、消解原理
如何学习《离散数学》?
首先要明确的是,由于《离散数学》是一门数学课,且是由几个数学分支综合在一起的,内容繁多,非常抽象,因此即使是数学系的学生学起来都会倍感困难,对计算科学专业的学生来说就更是如此。
大家普遍反映这是大学四年最难学的一门课之一。
但鉴于《离散数学》在计算科学中的重要性,这是一门必须牢牢掌握的课程。
既然如此,在学习《离散数学》时,大家最应该牢记的是唐诗“熟读唐诗三百首,不会做诗也会吟。
”学习过程是一个扎扎实实积累的过程,不能打马虎眼。
离散数学是理论性较强的学科,学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握,对基本原理及基本运算的运用,并要多做练习。
《离散数学》的特点是:
1、知识点集中,概念和定理多:
《离散数学》是建立在大量概念之上的逻辑推理学科,概念的理解是我们学习这门学科的核心。
不管哪本离散数学教材,都会在每一章节列出若干定义和定理,接着就是这些定义定理的直接应用。
掌握、理解和运用这些概念和定理是学好这门课的关键。
要特别注意概念之间的联系,而描述这些联系的则是定理和性质。
2、方法性强:
离散数学的特点是抽象思维能力的要求较高。
通过对它的学习,能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力,从而今后在学习任何一门计算机科学的专业主干课程时,都不会遇上任何思维理解上的困难。
《离散数学》的证明题多,不同的题型会需要不同的证明方法（如直接证明法、反证法、归纳法、构造性证明法）,同一个题也可能有几种方法。
但是《离散数学》证明题的方法性是很强的,如果知道一道题用什么方法讲明,则很容易可以证出来,否则就会事倍功半。
因此在平时的学习中,要勤于思考,对于同一个问题,尽可能多探讨几种证明方法,从而学会熟练运用这些证明方法。
同时要善于总结,
在学习《离散数学》的过程,对概念的理解是学习的重中之重。
一般来说,由于这些概念（定义）非常抽象（学习《线性代数》时会有这样的经历）,初学者往往不能在脑海中建立起它们与现实世界中客观事物的联系。
这往往是《离散数学》学习过程中初学者要面临的第一个困难,他们觉得不容易进入学习的状态。
因此一开始必须准确、全面、完整地记住并理解所有的定义和定理。
具体做法是在进行完一章的学习后,用专门的时间对该章包括的定义与定理实施强记。
只有这样才可能本课程的抽象能够适应,并为后续学习打下良好的基础。
学数学就要做数学、做数学题,《离散数学》的学习也不例外。
学习数学不仅限于学习数学知识,更重要的还在于学习数学思维方法。
要做到这一点,学习者将要面临的第二个困难是需要花费大量的时间做课后习题。
但是切记离散数学的题目数量自然是无穷无尽的,但题目的种类却很有限。
尤其是在命题证明的过程中,最重要的是要掌握证明的思路和方法。
解离散数学的题,方法是非常重要的,如果拿到一道题,立即能够看出它所属的类型及关联的知识点,就不难选用正确的方法将其解决,反之则事倍功半。
例如在命题逻辑部分,无非是这么几种题目:
将自然语言表述的命题符号化,等价命题的相互转化（包括化为主合取范式与主析取范式）,以给出的若干命题为前提进行推理和证明。
相应的对策也马上就可以提出来。
以推理题为例,主要是利用P、T规则,加上蕴涵和等价公式表,由给定的前提出发进行推演,或根据题目特点采用真值表法、CP规则和反证法。
由此可见,在平常学习中,要善于总结和归纳,仔细体会题目类型和此类题目的解题套路。
如此多作练习,则即使遇到比较陌生的题也可以较快地领悟其本质,从而轻松解出。
因此,只要肯下功夫,人人都能有扎实的基础,拥有足够的数学知识,特别是能大大提高本身的逻辑推理能力、抽象思维能力和形式化思维能力,从而今后在学习任何一门计算机科学的专业主干课程时,都不会遇上任何思维理解上的困难。
怎样学好离散数学
离散数学是现代数学的一个重要分支,是计算机科学中基础理论的核心课程。
离散数学以研究离散量的结构和相互间的关系为主要目标,其研究对象一般地是有限个或可数个元素,因此他充分描述了计算机科学离散性的特点。
由于离散数学在计算机科学中的重要性,因此,许多大学都把它作为研究生入学考试的专业课程中的一门,或者是一门中的一部分。
作为计算机系的一门课程,离散数学有与其它课程相通相似的部分,当然也有它自身的特点,现在我们就它作为考试内容时具有的特点作一个简要的分析。
1、定义和定理多。
离散数学是建立在大量定义上面的逻辑推理学科。
因而对概念的理解是我们学习这门学科的核心。
在这些概念的基础上,特别要注意概念之间的联系,而描述这些联系的实体则是大量的定理和性质。
在考试中的一部分内容就是考察大家对定义和定理的识记、理解和运用。
如2002年上海交通大学的试题,问什么是相容关系。
如果知道的话,很容易得分;如果不清楚,那么无论如何也得不到分数的。
这类型题目往往因其难度低而在复习中被忽视。
实际上这是一种相当错误的认识,在研究生入学考试的专业课试题中,经常出现直接考查对某知识点的识记的题目。
对于这种题目,考生应该能够准确、全面、完整地再现此知识点。
任何的模糊和遗漏,都会造成极为可惜的失分。
我们建议读者,在复习的时候,对重要知识的记忆,务必以上面提到的“准确、全面、完整”为标准来要求自己,不能达到,就说明还不过关,还要下工夫。
关于这一点,在后续章节中我们仍然会强调,使之贯穿于整个离散数学的复习过程中。
离散数学的定义主要分布在集合论的关系和函数部分,还有代数系统的群、环、域、格和布尔代数中。
一定要很好地识记和理解。
2、方法性强。
离散数学的证明题中,方法性是非常强的,如果知道一道题用怎样的方法证明,很轻易就可以证出来,反之则事倍功半。
所以在平常复习中,要善于总结,那么遇到比较陌生的题也可以游刃有余了。
在本书中,我们为读者总结了不少解题方法。
读者首先应该熟悉并且会用这些方法。
同时我们还鼓励读者勤于思考,对于一道题,尽可能地多探讨几种解法。
3、有穷性。
由于离散数学较为“呆板”,出新题比较困难,不管什么考试,许多题目是陈题,或者稍作变化的来的。
“熟读唐诗三百首,不会做诗也会吟。
”如果拿到一本习题集,从头到尾做过,甚至背会的话。
那么,在考场上就会发现绝大多数题见过或似曾相识。
这时,要取得较好的成绩也就不是太难的事情了。
本书是专门针对研究生入学考试而编写的,适合于读者对研究生入学考试的复习。
如果还有时间的话,我们可以推荐两本习题集。
一本是左孝凌老师等编写的《离散数学理论、分析、题解》,另一套有三本,是耿素云老师等编写的《离散数学习题集》。
这两套书大多数题都是相同的,只是由于某些符号和定义的不同,使得题目的设定和解法有些不同而已。
现在我们就分析一下研究生入学考试有哪些题型,以及我们应如何应付。
1、基础题
基础题就是考察对定义的识记,以及简单的证明和推理。
题目主要集中在数理逻辑部分和集合论部分。
这些题目不需要思考,很容易上手。
这一部分的题目主要问题是要防止粗心大意和对定义记忆似是而非而丢的分数。
不重视这一点的人将会在考试中吃大亏。
如在主合取范式中,极大项编码对应的指派与真值表对应的指派相反,这一点在许多的参考书里也会犯错误;还有是要防止没有按照一定的方法而引起的错误,如我们在数理逻辑或者集合论里作等价推演,可以省略若干不重要的步骤,只要老师和考生都清楚就可以了,而在推理理论里则不能省略任何步骤,否则被认为是逻辑错误。
我们在学习中,还要注意融会贯通,例如,数理逻辑和集合论是相通的,因此记忆或者总结方法的时候可以综合起来,这样便于比较和理解。
2、定理应用题
本部分是最“死”的一部分,它主要体现了离散数学的方法性强的特点。
并且这一部分占了考试内容的大部分,我们必须在这一部分下功夫,记住了各种方法,也就拿到了离散数学的大部分分数。
下面我们就列出常用的几种应用:
●证明等价关系:
即要证明关系有自反、对称、传递的性质。
●证明偏序关系:
即要证明关系有自反、反对称、传递的性质。
（特殊关系的证明就列出来两种,要证明剩下的几种只需要结合定义来进行）。
X,使得f（x）=y。
∈Y,都有x∈Y,即要证明对于任意的y→●证明满射:
函数f:
X
X,且x1≠x2,则f（x1）≠f（x2）;或者对于任意的f（x1）=f（x2）,则有x1=x2。
∈Y,即要证明对于任意的x1、x2→●证明入射:
函数f:
X
●证明集合等势:
即证明两个集合中存在双射。
有三种情况:
第一、证明两个具体的集合等势,用构造法,或者直接构造一个双射,或者构造两个集合相互间的入射;第二、已知某个集合的基数,如果为?
就设它和R之间存在双射f,然后通过f的性质推出另外的双射,因此等势;如果为?
0,则设和N之间存在双射;第三、已知两个集合等势,然后再证明另外的两个集合等势,这时,先设已知的两个集合存在双射,然后根据剩下题设条件证明要证的两个集合存在双射。
●证明群:
即要证明代数系统封闭、可结合、有幺元和逆元。
（同样,这一部分能够作为证明题的概念更多,要结合定义把它们全部搞透彻）。
●证明子群:
虽然子群的证明定理有两个,但如果考证明子群的话,通常是第二个定理,即设S,则∈是群,S是G的非空子集,如果对于S中的任意元素a和b有a*b-1是的子群。
对于有限子群,则可考虑第一个定理。
●证明正规子群:
若H。
这是最常见的题目中所使用的方法。
∈H,有a-1*h*a∈G,有aH=Ha,或者对于任意的h∈是一个子群,H是G的一个子集,即要证明对于任意的a
●证明格和子格:
子格没有条件,因此和证明格一样,证明集合中任意两个元素的最大元和最小元都在集合中。
图论虽然方法性没有前几部分的强,但是也有一定的方法,如最长路径法、构造法等等。
3、难题
难题就是考试中比较难以下手,大多考生作不出来,用来拉开分数档次的题。
那么,遇到难题我们怎么下手分析呢?
难题主要有以下四种,我们来逐一进行分析:
①综合题
综合题就是内容涵盖若干章的问题,这样的题大多数是在群论里面的陪集、拉格朗日定理、正规子群、商群这一部分中。
这一部分结合的内容很多,而且既复杂又难理解,是整个离散数学中的难点。
首先拉格朗日定理把群和等价关系、划分结合在一起,又与群的阶数相挂钩（在子群中有一部分阶方面的题是比较难的题,它的解法依据就在此处）;然后商群将两个群结合在一起,因为两个群的元素是不同的,因此必须时刻概念清楚才不至于混乱;接着同余关系把群和关系相结合,定义了一种新的关系;自然同态把正规子群和商群相联系,也成为某些证明题的着眼处;核的定义和群同态定理给出了正规子群的另一种证明方法,因为核就是正规子群……
当然,综合题不仅此一处,离散数学是一个融会贯通的学科,像集合论,图论等都可能成为综合题的命题点。
对于综合题,我们可以从两方面下手,首先不管题设如何,看所要证明的问题,按照定理应用的题型着眼,设出所需要的格式,然后进行进一步推演;其次可以先看题设,应用已知条件的性质定理向前推几步,看看哪一个性质更能够接近所问,题目也就迎刃而解了。
②例外题
例外题有两个含义,首先是对于定理应用题而言的,对于一个概念的判定定理和性质定理不是唯一的,而定理应用题是给出的是最常出题的定理,因此有的考题可能考出一个不常用的定理。
其次例外题还有一种题型是与我们平常思维相悖的问题,如:
有一些题目给出一个结论,说如果它正确的话请指出来,错误的话则请证明,凭做题经验通常是要选择证明的那条思路。
其实也不妨用一些时间看看能不能指出来,从而不用证明。
请看下面的例子:
③偏题
常常有的参考书会说某某章是非重点,不会考到之类的话,这是非常错误和有害的。
其结果是令这些章成为读者复习中的盲点,成为难题的又一种。
这些章通常概念少,定理不多,因此题目本身不难。
但由于没有好好复习或者根本没有复习,考试中又出了题目,故此拿不到分数则是非常令人懊丧的。
所以我们建议读者进行全面复习,除非是所报考院校明确说明不考的部分,其余内容一律要认真复习。
即使是复习时间比较少,也必须做到至少是了解了基本概念和定义。
对于离散数学而言,函数一章中的基数部分和格和布尔代数一章是人们容易忽略的问题。
我们平时复习的时候,不管是什么课程,一定不能留死角,而这些地方出的题目由于它的本身内容的局限性,又往往是非常简单的。
丢了十分可惜。
④错题
专业课的题目是由较少老师出的,并不像基础课那样经过多方面的论证,因此出错题也不奇怪（虽然非常非常之少）,如果我们遇到了一道题目,经过我们判断和推演得到相悖的答案,不要过分迷信题目的权威性,因为它可能是错题。
下面讲一下离散证明题的证明方法:
1、直接证明法
直接证明法是最常见的一种证明的方法,它通常用作证明某一类东西具有相同的性质,或者符合某一些性质必定是某一类东西。
直接证明法有两种思路,第一种是从已知的条件来推出结论,即看到条件的时候,并不知道它怎么可以推出结论,则可以先从已知条件按照定理推出一些中间的条件（这一步可能是没有目的的,要看看从已知的条件中能够推出些什么）,接着,选择可以推出结论的那个条件继续往下推演;另外一种是从结论反推回条件,即看到结论的时候,首先要反推一下,看看从哪些条件可以得出这个结论（这一步也可能是没有目的的,因为并不知道要用到哪个条件）,以此类推一直到已知的条件。
通常这两种思路是同时进行的。
2、反证法
反证法是证明那些“存在某一个例子或性质”,“不具有某一种的性质”,“仅存在唯一”等的题目。
它的方法是首先假设出所求命题的否命题,接着根据这个否命题和已知条件进行推演,直至推出与已知条件或定理相矛盾,则认为假设是不成立的,因此,命题得证。
3、构造法
证明“存在某一个例子或性质”的题目,我们可以用反证法,假设不存在这样的例子和性质,然后推出矛盾,也可以直接构造出这么一个例子就可以了。
这就是构造法,通常这样的题目在图论中多见。
值得注意的是,有一些题目其实也是本类型的题目,只不过比较隐蔽罢了,像证明两个集合等势,实际上就是证明“两个集合中存在一个双射”,我们即可以假设不存在,用反证法,也可以直接构造出这个双射。
4、数学归纳法
数学归纳法是证明与自然数有关的题目,而且这一类型的题目可以递推。
作这一类型题目的时候,要注意一点就是所要归纳内容的选择。
升级会员 