离散数学学习体会.doc

 我的离散数学学习心得 (1)  -- 一类抽象代数题的解题思路
学习离散数学已经有一段时间了，书读了不少，题也做了一些。最近又常在群里和研友们讨论离散数学中的问题。所以对离散数学也有了一些心得和体会。在今后的一段时间里，我会不定期的写一些小的经验总结，以供后来人参考。：）
    因为是“心得体会”，所以多半是想到什么写什么，组织和条理方面可能会比较差。还望各位看官多多包涵。；）
    这次我们来讨论一类代数问题的解题思路。
    问题：设R为含幺环，求证：对任意a,b∈R，若1-ab可逆，则1-ba也可逆。
    分析：
    我们知道，证明问题的方法大致可以分为两类：构造性证明和存在性证明。前者要求给出一个切实的方法，找出符合命题要求的元素（在这道题中，就是找到1-ba的逆元）。后者则只证明这样的元素必然存在，但并不给出切实的寻找方法。反证法是存在性证明的基本方法。

    无论打算采用是哪种证明方法，确认一下我们可以使用的前提条件总是必要的。
    就这道题而言，我们可以使用这些前提：
    1、R是含幺环。这就意味着R对加法构成Abel群（从而我们可以自由地使用加法交换律、加法消去律、加法逆元等），R对乘法构成独异点（从而可以使用乘法单位元1），当然还有乘法对加法的分配律。
    2、1-ab是可逆的，这就是说，存在c∈R，使得c(1-ab)=(1-ab)c=1。移项后得到：cab=abc=c-1。
    需要注意的是：
    1、在题设中没有假设R的可换性（事实上，如果R可换的话，整个问题就没有任何难度了），也没有假设a、b是可逆的。所以，在解题时，不能使用乘法交换律，也不能随便使用a、b的逆元（除非已经证明了它们的存在性）。
    2、如果没有1-ab可逆这个条件，肯定是推不出1-ba可逆的（我们在环中可以找到太多的反例）。所以，cab=abc=c-1将是解题的关键。观察这个式子，我们注意到，它提供了在c的参与下，移动和消去ab的方法。
    我们的目的是，证明存在这样的一个元素d∈R，满足(1-ba)d=d(1-ba)=1。

    初看到这道题，我们并不知道使用构造性证明容易还是使用反证法容易。
    不过推理一下我们可以发现，如果要使用反证法的话，我们需要反设1-ba不存在乘法逆元，然后由此推出1-ab也不可能有逆元（或者推出R不是含幺环）。
    但反设1-ba不存在乘法逆元后，我们到底能推出哪些结论来呢？似乎很少。我们甚至连“对任意x∈R，必有x(1-ba)≠1”这样简单的情况都难以证明（因为我们只假设了1-ba没有“乘法逆元”，并不能由此推出1-ba没有“乘法左逆元”）。

    另一方面，利用等式cab=abc=c-1直接构造出一个1-ba的逆元应该一个比较有希望的方法。
    这时，我们可以“取巧”了。注意到：
    1、如果我们相信题目给的命题没有错的话，我们只要找到1-ba的左逆元（或者右逆元）就基本完成任务了（虽然最终书写证明时，我们需要证明我们找到的元素既是左逆元又是右逆元）。因为如果一个元素的左右逆元都存在的话，它的左右逆元是唯一且相等的（所以，1-ba确实可逆，而我们又找到了它的一个左逆元x，那么这个x自然也是1-ba的右逆元）。
    2、不要指望证明c本身也是1-ba的逆元。因为假如是这样的话，(1-ab)和(1-bc)就都是c的逆元，由逆元的唯一性可知，1-ab=1-ba，利用消去律，我们可以得到ab=ba。这就说，在这个环里，只要1-ab有逆元，a和b就是可换的。这个符合“含幺环R”的一般情况吗？显然不符合。比如，由所有实矩阵对矩阵加法和矩阵乘法组成的环，它是含幺环。但只要|a|·|b|≠1，1-ab就可逆，但这样的矩阵都可换吗？显然不是的。这就说明，即使1-ab的逆元c存在，1-ba的逆元（如果存在的话）也未必是c。
    3、我们前面看到，在这道题中，c的存在性是1-ba可逆的一个不可缺少的条件，但c本身并不一定就是1-ba的逆元（仅当ab=ba时，c是1-ba的逆元）。那么，1-ba的逆元应该是一个与c有某种关系的元素。

    根据这些线索，我们来寻找1-ba的乘法逆元（不妨先寻找左逆元）。

    前面已经提到，cab=abc=c-1应该是解题的一个关键。那么，如果要使用它，就得用一个式子（不妨记为X）与(1-ba)相乘，使得它们的乘积中出现包含cab或者abc的项。
    因为 X(1-ba) = X - Xba。我们很容易看出，如果X中有以ca结尾的项（不妨记作Yca），那么就可以得到 Ycaba 这样的项，而这个项可以换成 Yabca 或 Y(c-1)a。这些式子也许有助于我们消掉那些不需要的项。
    这样，我们不妨设 X = (Yca + Z)，其中Y和Z分别是两个式子（注意到，这样的假设是具有一般性的，任何含有以ca结尾的项的式子都能写成Yca+Z的样子）。
    看看这样乘出来的式子是什么样的：
    X(1-ba) = (Yca + Z)(1 - ba)
            = Yca + Z - Ycaba - Zba
            = Yca + Z - Y(c-1)a - Zba
            = Yca + Z - Yca + Ya - Zba
            = Z - Zba + Ya
    好了，现在我们得到一个当 X = (Yca + Z) 时，乘积的一般形式，如果能给Y和Z适当的值，使得Z - Zba + Ya = 1，那么相应的X就是我们要找的逆元了。
    我们发现，要想把Zba消掉，Ya就应该也以ba结尾。看到这里，结果已经很明显了，令Y=b，Z=1，则 Z - Zba + Ya = 1 - ba + ba = 1。
    这就是说，我们已经发现，当 X = (bca + 1) 时，X(1-ba)=1。这样的X就是1-ba的左逆元了。
    证明X是右逆元的工作是简单的，和前面这段推导一样，只需利用等式abc = c-1就可以了。

    写在答题纸上的证明只不过是后面那小小的一段：
    (bca+1)(1-ba) = bca+1-bcaba-ba
                  = bca+1-b(c-1)a-ba
                  = bca+1-bca+ba-ba
                  = 1
    (1-ba)(bca+1) = bca-babca+1-ba
                  = bca-b(c-1)a+1-ba
                  = bca-bca+ba+1-ba
                  = 1
    而寻找bca+1的过程才是解题的关键。
    总结一下我们的思路：
    1、我们得到一些已知条件，需要找到一个未知的、满足某种特定条件的元素d。
    2、整理出我们可以使用的条件和不可以使用的条件（在抽象代数里要特别注意“不可以使用的条件”。因为抽象代数里常常使用以往算术运算中的符号，使人容易不自觉地使用一些在实数域上成立，但在其它代数系统上未必成立的性质和原理）。
    3、找到一些重要的等式，把它们变形为容易利用的形式（通常一边是一个单项，这样才方便在等式中代换）。
    4、写出待求元素的一般形式，考虑如何在其中利用我们在第3步找出的等式。
    5、根据推导的结果，确定待求元素的具体形式。
    6、证明结果的正确性。

    抽象代数中许多构造性证明都可以按这一思路进行。
    从这里也可以看出，虽然抽象代数中绝大多数题都是证明题，但在大多数情况下，观察、分析和试探仍然是解决问题的关键所在。

学习了一学期的离散数学，要说颇有成就、深有体会之类的话嘛，那还谈不上；要说是一点体会都没有，那也不可能。只是在这一年的离散数学的学习过程中，有一些个人体会想与大家分享。
离散数学是一门计算机专业的基础课程，也是比较难学的一门课程。这门课程里有太多的概念需要记忆。那是不是要把所有的概念的定义都要完完整整地背下来呢？我认为大可不必。要想在一学期中的那么一点有限的时间里，背完所有的概念的定义是不太现实的，况且也没有那个必要！学理工科最重要的就是理解。只有真正理解了概念的内在涵义，才能真正掌握这个概念。理解了概念的内在涵义，就为学好这门课程打好了坚实的基础。
在理解概念的基础上，再形成适合于离散数学本身的思维模式。学习物理，要用物理思维模式；学习高等数学，要用高数的思维模式；学习线性代数，也要用线性代数式思维模式。所以学习任何一门课程，都要有适合于该课程的思维模式。当然离散数学也不例外，它也有自己独特的思考问题的方式。只有找到了，并理解了这种思维方式，才能为后继学习作好铺垫。
最后最重要的就是要找到解决问题的方法。学习任何一门课程，都是为了解决实际问题。离散数学也是如此。有了对概念的理解，有了正确的思考问题的方式，在解决问题的时候就不会走弯路了，也就是说基本的解决问题的方法也就自然而然地掌握了。
学习这门课的目的，我认为并不是说要学得如何的精通，因为这是不可能的，课时有限嘛。其真正的目的就是要让你打好基础，为以后向更深、更广的方向发展垫定基础。有了以上三个方面的掌握，学习目的就可以达到了。
以上这些仅是我个人的看法，仅供参考。如果有什么说的不确切的地方，还请指正！

离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。
　　随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。
　　由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系， 因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。
离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。
　　离散数学课程主要介绍离散数学的各个分支的基本概念、基本理论和基本方法。这些概念、理论以及方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中；同时，该课程所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。
　　离散数学课程的教学目的，不但作为计算机科学与技术及相关专业的理论基础及核心主干课，对后续课程提供必需的理论支持。更重要的是旨在“通过加强数学推理，组合分析，离散结构，算法构思与设计，构建模型等方面专门与反复的研究、训练及应用，培养提高学生的数学思维能力和对实际问题的求解能力。”
　　离散数学通常研究的领域包括：数理逻辑、集合论、代数结构、关系论、函数论、图论、组合学、数论等。它是高校计算机及相关专业的重要基础课程之一。
　　课程内容涉及：
　　1．集合论部分：集合及其运算、二元关系与函数、自然数及自然数集、集合的基数
　　2．图论部分：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用
　　3．代数结构部分：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数
　　4．组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理
　　5．数理逻辑部分：命题逻辑、一阶谓词演算、消解原理
　　离散数学被分成三门课程进行教学，即集合论与图论、代数结构与组合数学、数理逻辑。
[编辑本段]
　　Discrete Mathematics and Its Applications此书的价值已经被全世界几百所大学所证实,作为离散数学领域的经典教材,全世界几乎所有知名的院校都曾经使用本书作为教材.以我个人观点看来,这本书可以称之为离散数学百科.书中不但介绍了离散数学的理论和方法,还有丰富的历史资料和相关学习网站资源.更为令人激动的便是这本书少有的将离散数学理论与应用结合得如此的好.你可以看到离散数学理论在逻辑电路,程序设计,商业和互联网等诸多领域的应用实例.本书的英文版(第六版)当中更增添了相当多的数学和计算机科学家的传记,是计算机科学历史不可多得的参考资料.作为教材这本书配有相当数量的练习.每一章后面还有一组课题,把学生已经学到的计算和离散数学的内容结合在一起进行训练.这本书也是我个人在学习离散数学时读的唯一的英文教材,实为一本值得推荐的好书。
[编辑本段]

内容简介

　　离散数学和微积分不同，离散数学是以离散对象为研究对象的，是计算机专业和其他一些工程专业的数学基础。本书包含了数理逻辑、集合论、数函数和递推关系、图论、代数系统及布尔代数等主要内容。本书注重理论的系统性和准确性，特别重视对理论难点的诠释，叙述通俗易读。
　　本书适合作为高等学校计算机专业或其他工程类专业教材使用，也可以供对离散数学有兴趣的读者自学。

内容简介
　　《离散数学》作为一个单独的分枝，在世界上出现的时间并不久，不过几十年，但它的各部分内容中有相当一部分却早已出现在数学中。为什么将各个数学分支中的一些内容集中起来加以研究，并且冠上一个新的名称——离散数学呢？这主要是因为计算机科学的产生和发展。正如恩格斯所说：“……科学的状况还更多的从属于技术的状况和需要。倘若社会上有了一种技术上的需要，那就比十个大学还更能推动科学前进。”①计算机的出现，在很大程度上影响到了人们的思想和生活，对社会生产起了重大作用。为了研究计算机科学的理论基础，离散数学也就应运而生。因此，如果我们不从纯数学的角度，而从应用数学的角度来考虑，也许给离散数学换一个名称一一计算机科学的数学基础——更能说明问题。
　　正是因为这个原因，在计算机科学系。信息管理系都将离散数学作为必须学习的基础课程。而实践证明这种做法是正确的。
[编辑本段]
如何学好离散数学
离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。离散数学以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此他充分描述了计算机科学离散性的特点。由于离散数学在计算机科学中的重要性，因此，许多大学都把它作为研究生入学考试的专业课程中的一门，或者是一门中的一部分。
作为计算机系的一门课程，离散数学有与其它课程相通相似的部分，当然也有它自身的特点，现在我们就它作为考试内容时具有的特点作一个简要的分析。
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之间存在双射；第三、已知两个集合等势，然后再证明另外的两个集合等势，这时，先设已知的两个集合存在双射，然后根据剩下题设条件证明要证的两个集合存在双射。
●证明群：即要证明代数系统封闭、可结合、有幺元和逆元。（同样，这一部分能够作为证明题的概念更多，要结合定义把它们全部搞透彻）。
●证明子群：虽然子群的证明定理有两个，但如果考证明子群的话，通常是第二个定理，即设<G,*>S,则Î是群，S是G的非空子集，如果对于S中的任意元素a和b有a*b-1<S,*>是<G,*>的子群。对于有限子群，则可考虑第一个定理。
●证明正规子群：若<G,*>H。这是最常见的题目中所使用的方法。ÎH，有a-1 *h*aÎG，有aH=Ha，或者对于任意的hÎ是一个子群，H是G的一个子集，即要证明对于任意的a
●证明格和子格：子格没有条件，因此和证明格一样，证明集合中任意两个元素的最大元和最小元都在集合中。
图论虽然方法性没有前几部分的强，但是也有一定的方法，如最长路径法、构造法等等。
3、难题
难题就是考试中比较难以下手，大多考生作不出来，用来拉开分数档次的题。那么，遇到难题我们怎么下手分析呢？
难题主要有以下四种，我们来逐一进行分析：
①综合题
综合题就是内容涵盖若干章的问题，这样的题大多数是在群论里面的陪集、拉格朗日定理、正规子群、商群这一部分中。这一部分结合的内容很多，而且既复杂又难理解，是整个离散数学中的难点。
首先拉格朗日定理把群和等价关系、划分结合在一起，又与群的阶数相挂钩（在子群中有一部分阶方面的题是比较难的题，它的解法依据就在此处）；然后商群将两个群结合在一起，因为两个群的元素是不同的，因此必须时刻概念清楚才不至于混乱；接着同余关系把群和关系相结合，定义了一种新的关系；自然同态把正规子群和商群相联系，也成为某些证明题的着眼处；核的定义和群同态定理给出了正规子群的另一种证明方法，因为核就是正规子群……
当然，综合题不仅此一处，离散数学是一个融会贯通的学科，像集合论，图论等都可能成为综合题的命题点。
对于综合题，我们可以从两方面下手，首先不管题设如何，看所要证明的问题，按照定理应用的题型着眼，设出所需要的格式，然后进行进一步推演；其次可以先看题设，应用已知条件的性质定理向前推几步，看看哪一个性质更能够接近所问，题目也就迎刃而解了。
②例外题
例外题有两个含义，首先是对于定理应用题而言的，对于一个概念的判定定理和性质定理不是唯一的，而定理应用题是给出的是最常出题的定理，因此有的考题可能考出一个不常用的定理。
其次例外题还有一种题型是与我们平常思维相悖的问题，如：有一些题目给出一个结论，说如果它正确的话请指出来，错误的话则请证明，凭做题经验通常是要选择证明的那条思路。其实也不妨用一些时间看看能不能指出来，从而不用证明。请看下面的例子：
③ 偏题
常常有的参考书会说某某章是非重点，不会考到之类的话，这是非常错误和有害的。其结果是令这些章成为读者复习中的盲点，成为难题的又一种。这些章通常概念少，定理不多，因此题目本身不难。但由于没有好好复习或者根本没有复习，考试中又出了题目，故此拿不到分数则是非常令人懊丧的。所以我们建议读者进行全面复习，除非是所报考院校明确说明不考的部分，其余内容一律要认真复习。即使是复习时间比较少，也必须做到至少是了解了基本概念和定义。对于离散数学而言，函数一章中的基数部分和格和布尔代数一章是人们容易忽略的问题。
我们平时复习的时候，不管是什么课程，一定不能留死角，而这些地方出的题目由于它的本身内容的局限性，又往往是非常简单的。丢了十分可惜。
④ 错题
专业课的题目是由较少老师出的，并不像基础课那样经过多方面的论证，因此出错题也不奇怪（虽然非常非常之少），如果我们遇到了一道题目，经过我们判断和推演得到相悖的答案，不要过分迷信题目的权威性，因为它可能是错题。

下面讲一下离散证明题的证明方法：
1、直接证明法
直接证明法是最常见的一种证明的方法，它通常用作证明某一类东西具有相同的性质，或者符合某一些性质必定是某一类东西。
直接证明法有两种思路，第一种是从已知的条件来推出结论，即看到条件的时候，并不知道它怎么可以推出结论，则可以先从已知条件按照定理推出一些中间的条件（这一步可能是没有目的的，要看看从已知的条件中能够推出些什么），接着，选择可以推出结论的那个条件继续往下推演；另外一种是从结论反推回条件，即看到结论的时候，首先要反推一下，看看从哪些条件可以得出这个结论（这一步也可能是没有目的的，因为并不知道要用到哪个条件），以此类推一直到已知的条件。通常这两种思路是同时进行的。
2、反证法
反证法是证明那些“存在某一个例子或性质”，“不具有某一种的性质”，“仅存在唯一”等的题目。
它的方法是首先假设出所求命题的否命题，接着根据这个否命题和已知条件进行推演，直至推出与已知条件或定理相矛盾，则认为假设是不成立的，因此，命题得证。
3、构造法
证明“存在某一个例子或性质”的题目，我们可以用反证法，假设不存在这样的例子和性质，然后推出矛盾，也可以直接构造出这么一个例子就可以了。这就是构造法，通常这样的题目在图论中多见。值得注意的是，有一些题目其实也是本类型的题目，只不过比较隐蔽罢了，像证明两个集合等势，实际上就是证明“两个集合中存在一个双射”，我们即可以假设不存在，用反证法，也可以直接构造出这个双射。
4、数学归纳法
数学归纳法是证明与自然数有关的题目，而且这一类型的题目可以递推。作这一类型题目的时候，要注意一点就是所要归纳内容的选择。

经过了一年的离散数学学习，自己对离散数学这门学科或多或少也有了一些感受，今天便和大家一起分享一下。
离散数学是计算机专业必修的一门课程，在学习这门课程之前，只能感到这是一门很不一般的学科。现在细细想来，其实里面充满了无限的奥秘
数理逻辑作为离散数学的第一部分，充满着对逻辑思维的挑战，同时锻炼了我们思考问题的严密性，当然最重要的是学会如何用数学方法去分析逻辑问题。
集合论是一个离散数学中第一个抽象难关，在老师的生动讲解下，深入浅出，使得集合论成了相当有趣的知识。只是对于以后的应用还不是很了解，感觉学好它很重要。
代数结构可以说是集合论知识的延续和发展，其中概念的知识很多，还好都是循序渐进的，只要完成了老师的作业，基本上可以理解其意思。
图论是作为我们计算机专业的一门很有用处的知识，也是新兴的一个数学分支，在计算机迅速发展的同时，图论也迅速发展。因此，图论给我们以一种神奇的感觉，在学习图论中，老师总是把图论分析得很透彻，学起来很有趣，同时也很简单。图论在数据结构方面的应用极其广泛，对我们学计算机专业的人来说，是一门必须要学好的知识。
总的来说，一个学期下来，自认为较好地掌握了离散数学的知识，并在平时的编程及其他方面得到了很好的应用。

最常和理论计算机科学放在一起的一个词是什么？答：离散数学。这两者的关系是如此密切，以至于它们在不少场合下成为同义词。（这一点在前面的那本书中也有体现）传统上，数学是以分析为中心的。数学系的同学要学习三四个学期的数学分析，然后是复变函数，实变函数，泛函数等等。实变和泛函被很多人认为是现代数学的入门。在物理，化学，工程上应用的，也以分析为主。 

随着计算机科学的出现，一些以前不太受到重视的数学分支突然重要起来。人们发现，这些分支处理的数学对象与传统的分析有明显的区别：分析研究的问题解决方案是连续的，因而微分，积分成为基本的运算；而这些分支研究的对象是离散的，因而很少有机会进行此类的计算。人们从而称这些分支为“离散数学”。“离散数学”的名字越来越响亮，最后导致以分析为中心的传统数学分支被相对称为“连续数学”。 

离散数学经过几十年发展，基本上稳定下来。一般认为，离散数学包含以下学科： 
1) 集合论，数理逻辑与元数学。这是整个数学的基础，也是计算机科学的基础。 
2) 图论，算法图论；组合数学，组合算法。计算机科学，尤其是理论计算机科学的核心是 
算法，而大量的算法建立在图和组合的基础上。 
3) 抽象代数。代数是无所不在的，本来在数学中就非常重要。在计算机科学中，人们惊讶地发现代数竟然有如此之多的应用。