课程导学-离散数学
离散数学1：集合论与图论
顾名思义，集合论与图论包含两大部分：集合论、图论。集合论起源于对于数学基础的研究，又有公理集合论和朴素集合论之分。本课程讲授朴素集合论，包括集合的表示和运算、集合之间的关系和基本的集合恒等式；用集合去定义二元关系，并且研究二元关系的表示、运算、性质，以及等价关系、序关系、函数等特殊的二元关系；还研究自然数的公理化定义和用集合去构造自然数的方法；以及集合的等势、有穷集和无穷集、集合的基数及其运算等内容。通过集合论的学习，可以训练学生严密的逻辑思维能力，以及运用集合论语言去定义各种数学对象和描述实际问题的能力，将有益于后续课程的学习。图论是既古老又现代的离散数学分支，现代公认图论起源于1736年欧拉对于七桥问题的研究，1936年才出版了图论的第一本专著，电子计算机诞生后，图论及其算法研究变得空前活跃起来。本课程主要讲授图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图的着色、图中的支配集、独立集、覆盖、匹配、以及带权图等内容。通过图论的学习，可以训练学生用图作为工具为各种二元关系建立模型，来表示和解决各种实际问题的能力。通过集合论与图论的学习，将为后续课程的学习打下良好的基础。
下面先介绍本课程十三个模块的内容，再给出一些学习方面的建议。
集合论部分主要包括五个模块，分别是：模块1集合、模块2二元关系、模块3函数、模块4自然数、模块5基数，如图1所示。
图1 集合论知识框架
图论部分主要包括八个模块，分别是：模块6图、模块7欧拉图与哈密顿图、模块8树、模块9图的矩阵表示、模块10平面图、模块11图的着色、模块12支配集、覆盖集、独立集与匹配、模块13带权图及其应用，如图2所示。
图2 图论知识框架
集合论与图论课程总的特点是：概念多、结论多、知识点分散，证明方法和应用技巧灵活多变。在学习的时候除了要花费一定的精力去熟悉和掌握各种概念和结论，还要下一番功夫去总结和梳理各个知识点之间的内在联系，并且要通过解题练习和实际应用来巩固和提高，以达到真正得心应手地掌握的程度。下面以集合论为例，说明如何去总结和梳理各个知识点之间的内在联系；并以图论为例，说明如何结合实际问题加以灵活运用。
集合论部分的五个模块的主要内容可以总结如下。在模块1集合中，首先介绍了命题逻辑和一阶谓词逻辑的预备知识，为定义和证明集合之间的各种关系、运算、及其性质做好了准备；随后介绍了列举法、描述法等集合表示方法，定义了集合之间的包含、相等、真包含关系，以及空集、全集、幂集、集合的元素个数、集族、多重集等概念；接着定义了并集、交集、相对补集、对称差、绝对补集、广义并集、广义交集等集合运算以及集合运算的优先级，介绍了文氏图和容斥原理；最后介绍了包括幂等律、交换律、结合律、分配律、吸收律、德?摩根律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律在内的基本的集合恒等式，以及从定义出发和利用已知结论的两类半形式化证明方法。在模块2二元关系中，首先定义了有序对、有序3元组、有序n元组、卡氏积的概念；接着定义了二元关系、A到B的二元关系、A上的二元关系，介绍了空关系、恒等关系、全域关系、关系定义域、关系值域、关系域、关系逆、关系合成、关系限制、关系象、单根关系、单值关系等概念；随后介绍了关系矩阵、关系图等关系表示法，以及自反性、反自反性、对称性、反对称性、传递性等关系性质；又定义了关系的n次幂、关系的自反闭包、对称闭包、传递闭包等关系运算；最后分别介绍了等价关系和序关系，包括等价关系、等价类、商集、同余关系、划分、划分的块、划分的加细、Stirling子集数、偏序关系、偏序集、可比、覆盖、哈斯图、全序关系、全序集、拟序关系、拟序集、三歧性、拟全序关系、拟全序序集、良序、良序集、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界、链、反链等概念。在模块3函数中，先定义了函数、偏函数、全函数、真偏函数等概念，再介绍了单射、满射、双射等函数性质，以及象、原象的概念和常数函数、恒等函数、特征函数、单调函数、自然映射等特殊函数，最后介绍了函数合成、反函数、单边逆等概念。在模块4自然数中，先介绍了集合A在函数F下封闭的概念和皮亚诺系统的五条公设，接着介绍了从空集出发利用后继运算构造归纳集、自然数、自然数集的方法以及数学归纳法原理；最后介绍了传递集的概念，加m函数、二元加法、乘m函数、二元加法的递归定义，以及自然数集上的序。在模块5基数中，先定义了集合的等势、有穷集、无穷集等概念和对角化证明方法；然后介绍了集合的基数，以及优势、
劣势、绝对优势、绝对劣势等基数的比较，最后介绍了可数集、有穷可数集、无穷可数集，以及基数运算。这是经过整理后总结的集合论五个模块的详细内容。
上述集合论部分的五个模块之间有密切的联系。模块1集合是基础部分，后续各模块中概念的定义和性质的证明都离不集合的表示、运算、和证明，因此要熟练掌握集合的各种运算及其性质，以及半形式化的证明方法。模块2二元关系和模块3函数是核心部分，这部分中的等价关系、序关系、函数等重要概念在本课程的其他地方和其他课程中将反复出现，因此也要熟练掌握这部分内容。模块4自然数和模块5基数是提高部分，展示了如何运用集合、关系、函数等概念和工具来表示、构造、分析特定数学对象（自然数、基数），这部分内容较为抽象，学习起来难度较大，但对于培养抽象和严谨的逻辑思维能力、巩固和强化基础部分和核心部分的学习效果大有好处。由上述讨论可以看出，本课程介绍的朴素集合论，在概念繁杂的表象下，隐藏着严密的逻辑体系，各种概念和结论层层递进、相互关联。因此，善于梳理总结概念之间的关联，对于学好集合论和图论来说就是个关键。如果不这样做，就容易落得“只见树木、不见森林”的结果。
下面试举一例说明如何梳理总结概念之间的关联。集合、关系、函数的知识点关联可如图3所示。
图3 集合、关系与函数
图论部分的八个模块之间也有密切的联系。模块6图是基础部分，顶点与边、相邻与关联、度与同构、图的运算等都是后续模块经常用到的概念。模块7欧拉图与哈密顿图、模块8树、模块9图的矩阵表示、模块10平面图是核心部分，欧拉图、哈密顿图、树、平面图是重要的图类，欧拉图的充要条件和算法、哈密顿图的充分条件和必要条件、树的等价定义、平面图的判断方法和欧拉公式都是重要的结论。模块11图的着色、模块12支配集、覆盖集、独立集与匹配、模块13带权图及其应用是提高部分，这部分内容与各种实际应用问题密切相关，例如象排课表这样的调度问题可以用图的着色来表示和求解，各种资源分配问题可以用二部图的匹配来表示和求解。这部分内容相关的大量研究问题还没有解决，目前依然是图论及其算法研究中的热点和前沿方向。
在开始学习第一遍时，一下子接触到上面列举的这么多概念，难免死记硬背、生吞活剥，这才只是经历了一个“由薄到厚”的过程。等到学完一遍之后，经过一番梳理和总结，发现了各部分内容之间的关联，有所融会贯通，这就又经历了一个“由厚到薄”的过程。最后，还要经过反复练习和实际运用，才能达到得心应手、为我所用的阶段。下面举例说明如何灵活运用图论中的概念解决实际问题。
渡河问题：一个人带着一只狼、一只羊、一棵白菜要过河，小船一次只能容下一个人和一样动植物。人不在场的时候，狼要吃掉羊、羊要吃掉白菜。应当如何渡河？
首先，我们要把问题符号化，表示成集合论或图论的语言。我们用英文字母来表示人和动植物：狼=W，羊=G，白菜=C，人=M。我们用(X|Y)或X|Y来表示问题的状态，即在河的一侧有X而在另一侧有Y。由于{W,G,C,M}的子集共有16个，因此问题可能的状态有16种，如下图所示。
图4 一个应用
在图4中，每个顶点表示一个状态，每条边表示一次渡河行动前后关联的两个状态。注意每条边对应着往返两个方向的渡河行动。我们可以为状态分类：红色顶点代表不允许的状态，绿色顶点代表初始状态和结束状态。原来的问题就转化为图论问题：寻找图中连接两个绿色顶点而不经过红色顶点的路径。由于每个绿色顶点各自只有一条长度为2的路径不经过红色顶点而到达一个蓝色顶点（用蓝色边表示这条路径），因此问题转化为寻找两个蓝色顶点之间的路径，这样的路径是存在的（实际有2条），且长度为3。于是得到问题的一个解是长度为7的路径：(CGMW|) - (CW|GM) - (CMW|G) - (W|CGM) - (GMW|C) - (G|CMW) - (GM|CW) - (|CGMW)。通过上述分析还可以看出，最优解法至少要经过7次渡河行动，而且本质上只有2种不同的解法（路径）。
上述例子说明了如何灵活运用图论知识解决实际问题，捎带着也用到集合论知识。
总之，学好集合论和图论的两个关键是：一要善于总结和归纳，二要多做练习和实际应用。
离散数学2：代数结构与组合数学
代数结构与组合数学包含两大部分：代数结构、组合数学。代数结构来源于抽象代数，主要研究由集合及运算构成的代数模型，如半群、独异点、群、环、域、格与布尔代数；这些结构应用于计算机硬件设计、密码学等领域。组合数学来源于组合学。组合学是一个古老的数学分支，图论曾经是组合学的组成部分，由于图论在计算机科学的广泛应用和飞速发展，已经成为一个独立的研究领域。这里的组合学重点研究某些组合配置的存在性、计数、枚举及优化问题；主要用于实际中的组合优化问题的建模、计算机算法的设计与分析等领域。
下面分别介绍代数结构与组合数学的特点及学习方法。 一、代数结构学习中的重点、难点及其学习方法
1. 代数结构的大量概念是建立在集合、函数基础上的。集合论中学到的集合、函数的表示和证明方法在代数结构中经常用到。在学习代数结构前先把相关概念复习一下是有好处的。
2. 代数结构有如下特点：定义和定理比较多；概念抽象；证明题多。
学习时要注意建立有关的知识框架，即各个知识点及其关联。为了加深对这些概念的理解，在相关知识模块（基本上对应于教材的一章）的PPT电子教案上都给出了知识框架图，如图5和图6分别是有关一般代数系统和群的知识框架图。以图5为例说明如下：
第十五章代数系统半群与群环域分类格与布尔代数子集子代数积代数商代数新代数系统同种的同类型的?代数推广成分：载体及运算公理：运算性质代数系统的构成映射笛卡儿积产生等价关系代数系统的同态与同构代数系统间关系2 图5代数系统的知识框架
一般代数系统的知识模块主要讨论以下问题：代数系统的构成、代数系统的产生、代数系统间的关系、几类重要的代数系统。
? 代数系统的构成。构成代数系统有两个要素：成分和公理。成分指明该系统的集合和集
合上的代数运算；公理规定了系统所具有的性质。
? 代数系统的产生。由已知的代数系统可以通过子代数、积代数、商代数的方式构成新的
代数系统。这些新系统与原有代数系统具有同种类型的成分，能够保持原系统的若干主要性质（公理）。
? 代数系统间的关系。通过同态（或同构）映射可以建立代数系统间的关系。同构的代数
系统在抽象的意义上可以看作是一个代数系统。
课程导学-离散数学
