1、课程简介—本课程的教学内容简介、学习目标、重点、难点、学习要求等。
离散数学主要研究离散对象和它们之间的关系。它是现代数学的重要分支之一，是计算机科学的基础理论核心课程。离散数学的内容很广泛，包括数理逻辑、集合论、图论、代数结构积应用部分。它们来源于不同的数学分支，从不同的角度研究各种离散量之间的关系。
学习它目的是为计算机科学的数据结构、编译理论、操作系统、算法分析、人工智能等提供了必要的数学基础知识。
通过本课程的学习，期待各位学员对离散数学有一个较全面的概念，培养出抽象思维和严谨的逻辑推理能力。 学习要点
一、命题逻辑：
掌握命题、命题变元、联结词、复合命题等概念，能够将命题符号化；掌握命题公式、重言式、矛盾式、可满足式、公式真值表等概念，能够利用公式的真值表判断较简单的公式类型；掌握命题公式的等值式、*对偶式，命题公式的代入与置换等概念，能够利用基本等值式、代入规则和置换规则进行等值演算；掌握命题公式的逻辑蕴涵式、逆换式、反换式、逆反式等概念，对于较简单的A和B，能够判断
A?B是否
成立，*能够用基本的逻辑蕴涵式推证更复杂的逻辑蕴涵式；掌握全功能联结词集合的概念，能够判断一个联结词集合是否为全功能联结词集合，*会求最小联结词集合；掌握范式、极小（大）项、主范式的概念和性质，掌握求各种范式的方法，*能够用等值演算法和真值表法求命题公式的主范式，熟悉一个命题公式的主合取范式与主析取范式的关系——如何根据一种主范式立刻写出另一种主范式；
*掌握形式证明、前提引入规则、结论引入规则、置换规则、代入规则、蕴涵证明规则等概念，能够根据推理规则以及一些基本等值式和逻辑蕴涵式，利用直接法和间接法作有效推理，并最终得到一个有效的结论。 二、谓词逻辑：
掌握个体、个体变量、个体域、谓词、全称量词、存在量词等概念，并学会利用它们符号化一些命题和构成一些较复杂的命题；掌握谓词公式的正确概念，理解约束变量和自由变量的形式和意义；正确使用约束变量的改名规则和自由变量的代入规则；掌握谓词公式的永真、等价、蕴含等概念，并能比较与命题公式演算中同样的概念及其异同；能用定义证明几个定理中给出的各个含有量词的等价关系式和蕴涵关系式；能记住主要的等值式，即量词否定等值式、量词作用域扩张与收缩等值式、量词分配等值式、在有限个体域内消去量词等值式；能使用约束变量和自由变量改名规则进行等值演算，掌握前束范式的概念以及把谓词公式化成与之等价的前束范式的方法；掌握谓词演算中推理的概念，并能利用正确的方法判断一个推理过程是否正确。 三、集合与关系：
掌握集合、子集、全集、空集等概念；熟悉常用的表示集合的方法以及用文氏图表示集合的方法；能判定元素与集合、集合与集合之间的关系；懂得两个集合之间的相等关系和包含关系的定义及性质，能够利用
华南理工大学理学院李少白教学参考资料，仅供内部使用。 共7页，第1页
定义证明两个集合相等；掌握集合的五种基本运算：并、交、补、差和对称差，并熟记集合运算的基本等式，能够利用它们来证明更复杂的集合等式；掌握幂集的定义，以及计算有限集的幂集所含元素个数所使用的方法和思想；掌握序偶和迪卡尔积的概念；了解抽屉原理，熟记简单情形的容斥原理；理解划分与覆盖的概念，清除两者之间的差异。
掌握二元关系的形式定义及其各种表示方法：序偶、矩阵、关系图等；能准确使用集合表示式、关系矩阵、关系图等表示给定的关系，并要求能从一种形式写出另一种形式；掌握关系的运算，包括集合运算以及关系的复合和关系的逆运算；掌握二元关系的各种特殊性质：自反、反自反、对称、反对称、传递等，并理解这些性质如何反映在关系图上、关系矩阵上等；掌握集合中二元关系闭包的意义和简单性质，能求出优限集上的二元关系的闭包；掌握等价关系、相容关系的概念（重点是等价关系），并掌握覆盖、划分、等价类、商集的定义和基本性质，弄清楚等价关系与划分之间的关系；掌握偏序、偏序集、全序、良序等概念，以及偏序集的极大元、极小元、最大元、最小元、上界、下界、最大下界、最小上界等概念；能画出有限偏序集的哈斯图，并根据图讨论偏序集的某些性质。
四、函数：要求掌握函数的基本概念，弄清楚单射、满射和双射之间的区别；给定一个函数，要求能够确定它是否是单射、满射和双射；掌握复合函数和反函数的定义，弄清楚它们存在的条件；理解集合的象及原象的定义及相关性质；给定一个函数，能确定一点的象，一个集合的象，一个集合的原象及两个函数的复合等；掌握集合的势、可数集、不可数集的概念。 五、代数结构：
掌握代数系统的概念，对于运算的封闭性、单位元、零元、逆元等幂元的定义及相关的结论有清晰的理解；给定集合和集合上的运算表确定单位元、零元、逆元等（如果存在的话）。对于交换律、结合律、分配律、吸收律等的表示要十分清楚；给定集合及二元运算表，能够判断运算是否满足交换律、是否满足结合律；掌握代数系统的同态与同构的定义；能判断两个给定的代数系统之间的某个映射是否为同态、同构映射；。掌握半群及独异点等概念；掌握群的概念，并能够灵活应用群的一些基本性质，理解群的同态与同构；给定一个代数系统及其运算，能够判断是否为半群、独异点、群等；掌握子群的的概念并清楚其判别方法；掌握左陪集、右陪集及正规子群的定义，了解拉格朗日定理；掌握环及整环的定义；给定集合及两个二元运算，能够判断其是否为环、域、整环等。 七、图论：
掌握图、无向图、有向图、关联、邻接，节点度数，以些特殊图、子图、同构、通路、回路，通路长度、节点之间的连通性与可达性、图的连通性、点割集、割点、边割集、割边、点连通度、边连通度等概念以及有关性质，并能够判定或证明图的有关结论；掌握图的邻接矩阵和关联矩阵的概念以及有关性质，能够利用邻接矩阵计算图中各种长度的通路和回路的数目；掌握求图中某个节点到其它任一节点的最短路径的华南理工大学理学院李少白教学参考资料，仅供内部使用。 共7页，第2页
Dijkstra算法，以及求图中任意两个节点之间的最短路径的Warshall算法；掌握欧拉图和哈密顿图的概念及其判别方法，能够利用Fleury算法求欧拉回路，了解邮路问题，能够用近邻法求哈密顿回路；掌握平面图、面、边界、极大平面图、同肧等概念以及有关性质，能够判别一个图是否为平面图；掌握最小点覆盖集，最小边覆盖集，最大点独立集，最大边独立集（匹配）、最大匹配、完美匹配，完备匹配、可增广路径等概念，能够利用相异性条件和t条件判定二部图是否存在完备匹配，了解利用可增广路径球完备匹配的方法和思想；掌握节点着色、边着色、面着色等概念以及有关性质，能够用Welch-power算法确定一个图的颜色数尽可能少的节点着色。 2. 教学大纲—本课程的教学目的、主要学习内容、学时安排。 离散数学的内容多，概念多，公式也多，望勤学多记多练。我们对第一、二、三、五、七章有较高的要求，第四章仅第一节有点要求。凡打星号的章节不作考试要求，供有兴趣的同学自学提高之用。时间紧，望抓住重点要点。 序号 内容 教学基本要求 学时数 1 第一章 命题逻辑：掌握命题、原子命题、复合命题和联结词等概念，能够将命题符号命题及其表示法，化；掌握命题的合式公式、翻译等概念，能够判断一公式是否为合25 联结词，命题公式，式公式，会翻译自然语句；掌握公式的等价、蕴含等概念，书记基真值表与等价公式、重言式与蕴含式，对偶与范式，推理理论 本的等价式、蕴含式，会证明更复杂的等价式、蕴含式；掌握对偶式、析取范式、合取范式、极大（小）项、主范式的概念和性质，掌握各种范式的求解方法，能够用等价演算法和真政值表法求命题公式的主析取范式、主合取范式，了解两种主要范式的关系及根据一种主范式写出另一种主范式的方法（转换方法）；掌握论证的基本方法：真值表法、直接证法和间接证法，掌握推理定律和推理规则，并能熟练应用。 2 第二章 谓词逻辑：掌握谓词、全称量词、存在量词等概念，学会使用它们幅好画一些谓词概念、命题函数与量词，命题函数与量词，谓词公式与解释，变元的约束，谓词演算的命题并能够构成一些较复杂的命题；掌握谓词公式的概念，并能够判定给定公式是否为谓词的合式公式；掌握约束变量和自由变量的概念，并能够正确使用换名规则；掌握永真公式、永假公式、可满足式等概念；掌握谓词公式的等价、蕴含等概念，熟记基本的等价式、蕴含式，会证明更复杂的等价式、蕴含式；掌握前束范式概念，20 华南理工大学理学院李少白教学参考资料，仅供内部使用。 共7页，第3页
等价式与蕴含式，前束范式，谓词演算的推理理论 3 第三章 集合与关系：集合的概念和表示法，集合的运并能够正确使用推理规则进行有效推理，并能判断一推理过程是否正确。 掌握集合、元素、子集、真子集、空集、全集、幂集的概念，了解两个集合间相等关系和包含关系的定义和性质，能够利用定义证明两个集合相等，熟悉常用的集合表示方法；掌握集合的基本运算：20 算，包含排斥原理，并、交、差、补、对称差的定义以及集合运算满足的基本运算律，序偶和笛卡尔积，关系及其表示，关系的性质，复合关系和逆关系，关系的闭包运算，集合的划分和覆盖，等价关系和等价类，能够利用它们来证明更复杂的集合等式；掌握序偶与笛卡尔积，并能计算集合的笛卡尔积；掌握关系、二元关系、空关系、全域关系、相等关系、逆关系、复合关系的概念以及关系的性质：自反性、反自反性、对称性、传递性，会做关系的乘积，了解关系的闭包运算：自反闭包、对称闭包、传递闭包；掌握集合的划分与覆盖的概念和求法，掌握等价关系、等价类、商集的概念，了解等价关系和划分的内在联系；掌握相容关系、相容类、偏序关系、偏序集、全序关相容关系，序关系 系、全序集的概念以及偏序集中的特殊元素：最大元、最小元、极大元、极小元、（最小）上界、（最大）下界的定义，能画出有限偏序集的哈斯图，并根据图讨论偏序的某些性质。 4 第四章 函数：函数的概念，逆函数和复合函数，特征函数与模糊子集，基数、可数集和不可数集 5 第五章 代数系统：代数系统的引* * 掌握函数的基本概念，会判断给定集合是否为从A到B的函数，能够熟练求函数的值、像、原像，会判断函数是否相等；会判断和证明函数的单射、满射、双射的性质；给定集合A和B，会构造A到B的双射函数；掌握复合函数和逆函数的概念，会求复合函数、双射函数的反函数；掌握集合的势、基数的概念以及比较基数的大小；了解可数集、不可数集的概念。 会判断给定函数f是否为集合S上的二元运算或一元运算，会判断或证明二元运算的性质；掌握子代数的概念；判断或证明给定集合10 20 入，运算及其性质，或运算是否构成半群、独异点或群，会运用群的基本性质证明相关半群，群与子群，阿贝尔群和循环群，置换群与伯恩* 的命题；会证明G的子集构成G的子群，会判断和证明子群的正规性；会求循环群的生成元及其子群；了解n元置换的表示方法、乘法及n元置换群；了解商群的概念；熟悉陪集的定义和性质；熟悉华南理工大学理学院李少白教学参考资料，仅供内部使用。 共7页，第4页
相关推荐：
loading