我的离散数学学习心得 (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)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。

它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。

通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。

离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。

由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。

离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。

离散数学的应用遍及现代科学技术的诸多领域。

离散数学课程主要介绍离散数学的各个分支的基本概念、基本理论和基本方法。

这些概念、理论以及方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中；同时，该课程所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。