吉林大学离散数学串讲ppt

1、2021年11月26日星期五1 离散数学吉大吉大 11春学期考前串讲春学期考前串讲2第一章第一章 集合论基础集合论基础1.掌握集合、子集、差集、空集、幂集、集合族的概念。懂得两个集合间相等和包含关系的定义和性质，能够利用定义证明两个集合相等。熟悉常用的集合表示方法。2.掌握集合的基本运算：并、交、余、差、直乘积、对称差的定义以及集合运算满足的基本算律，能够利用它们来证明更复杂的集合等式。3.掌握关系、二元关系、空关系、全域关系、相等关系、逆关系的概念以及关系的性质：自反性、对称性、反对称性、传递性。会做关系的乘积。了解关系的闭包运算：自反闭包、对称闭包、传递闭包。4.掌握等价关系、等价类、商集

2、的概念，了解等价关系和划分的内在联系。5.掌握部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最大元、最小元、极大元、极小元、上确界、下确界的定义。能画出有限部分序集的Hasse图，并根据图讨论部分序集的某些性质。6.掌握映射、映像、1-1映射等概念，会做映射的乘积。了解可数集合的概念，掌握可数集合的判定方法。400-810-6736 3400-810-6736 4第二章第二章 命题逻辑命题逻辑1.掌握命题、逻辑联结词等概念，能够将命题符号化。2.掌握命题公式、解释、恒真公式、恒假公式等概念。能够判断一命题公式是恒真、恒假，还是可满足。3.掌握公式的等价、蕴涵等概念，熟记

3、基本的等价式、蕴涵式，会证明更复杂的等价式、蕴涵式。4.掌握联结词的功能完备集的概念，能够判别一个联结词集合是否为联结词的功能完备集。5.掌握演绎方法，能够使用演绎方法进行有效推理。6.掌握析取范式、合取范式、极大项、极小项、主析取范式、主合取范式的概念和性质。掌握求各种范式的方法，能够用等价演算法和真值表法求命题公式的主析取范式、主合取范式。400-810-6736 5400-810-6736 6第三章第三章 谓词逻辑谓词逻辑1.掌握谓词、全称量词、存在量词等概念，学会使用它们符号化一些命题并构成一些较复杂的命题。2.掌握约束变量、自由变量的概念，能够正确使用改名规则。3.掌握谓词公式、解释

4、的概念，能够求出一给定公式在某一解释下的真值。4.掌握恒真公式、恒假公式、可满足公式等概念，了解与命题逻辑判定问题可解,不同的是：谓词逻辑判定问题不可解，但谓词逻辑是半可判定的。 5.掌握谓词公式的等价、蕴涵等概念，熟记基本的等价式、蕴涵式，会证明更复杂的等价式、蕴涵式。6.掌握前束范式、Skolem范式等概念，能够将一谓词公式化成与之等价的前束范式，并进一步化为Slolem范式。400-810-6736 7400-810-6736 8第四章第四章 图与网络图与网络1.掌握图、有限图、母图、子图、支撑子图、完全图、补图等概念，了解有限图中点的度的性质，掌握图的矩阵表示：关联矩阵、邻接矩阵。2.

5、掌握路、简单路、回路、连通图等概念。3.理解Dijkstra算法，并能够在已知权图中使用该算法求出任意两点间的最短路。4.掌握树、支撑树的概念以及图是树的几个等价命题。5.理解Kruskal算法，并能够应用它求已知加权连通图的最优树。了解求最优树的Prim算法，会总结Sollin算法。6.掌握有向图、有向子图、有向路、简单有向路、有向回路等概念。7.掌握有向图的强连通性和有向图的根的概念，了解二者的关系。8.掌握Euler路、Euler图的概念，掌握有向图中和无向图中Euler图的充要条件，并能利用判断某图是否为Euler图。了解从Euler路得出有向支撑树以及从有向支撑树得出Euler路的方

6、法。10. 掌握Hamilton路、Hamilton回路、Hamilton图的概念以及Hamilton图的必要条件和若干充分条件。400-810-6736 9400-810-6736 10第六章第六章 群与环群与环1.掌握二元代数运算、代数系统的定义，能够判断一运算是否为二元代数运算，运算是否满足交换律、结合律、分配律、幂等律、吸收律、消去律。2.掌握半群、群的定义以及群的性质，能够判断一代数系统是否为半群或群。3.掌握交换群的定义以及交换群中的三个指数律。4.掌握置换、轮换、不相杂轮换、对换等概念，会做置换的乘法，会将任意置换写成不相杂轮换的乘积。了解置换的顺向圈表示。5.掌握奇置换、偶置换

7、的概念，了解置换的定性数与置换的图型及奇偶性的关系。6.掌握n次对称群、n次交代群的概念，会写出其中的元素。7.掌握子群的定义以及子群的判别条件。掌握周期、循环群的定义和乘法群、加法群中周期的性质以及循环群中一元素作为生成元的充要条件。8.掌握群中合同、右陪集的定义。了解子群在大群中的右陪集的一些性质。掌握正规子群的概念以及一子群为大群的正规子群的充要条件。掌握并会正确应用Lagrange定理。400-810-6736 11第六章第六章 群与环群与环9.掌握同态映射、同构映射、自同构映射的概念以及同态定理。会判断一个群与一乘法系统间的映射是否为同态映射、同构映射或自同构映射。10. 掌握同态核

8、的概念，了解若是群G到G上的同态映射，则其核N为一正规子群。反过来，设N是G的一个正规子群，则有一个群G以及一个G到G上的同态映射，使N为的核。掌握并会正确应用联系同态与同构的基本定理。了解为群G到G上的同态映射时，G中子群与G中子群的关系。11. 掌握环、交换环、含壹环、消去环的定义及其性质，会判断。12.掌握整区、体、域、子环、子体、子域等概念，以及环的子集作成子环的充要条件。13. 掌握并会应用理想、主理想的定义，掌握环中合同关系、剩余类的定义以及环中合同关系的性质。14. 掌握环同态映射、同构映射、剩余环的定义，了解与群论中平行的环中的关于同态映射、同构映射的一些定理。15. 掌握单纯

9、环与极大理想的定义，以及二者的关系，了解一个环是域的充要条件。 400-810-6736 12400-810-6736 13第八章第八章 格与布尔代数格与布尔代数1.掌握半序格、半序子格、代数格、代数子格的定义，了解半序格和代数格的定义是等价的。2.掌握互相对偶的两个关系、互相对偶的两个格的定义，了解二者关系。掌握格中表达式、对偶格中的对偶表达式、本格中的对偶表达式的定义，掌握并会应用对偶原理1及对偶原理2。3.了解格的其它性质，如格的保序性、分配不等式、模不等式等。4.掌握并会应用格同态映射、格的自同态映射、格同构映射的定义。了解格的同态映射一定是保序映射，同构映射的逆映射也是同构映射等结论。5. 掌握有界格、有余格、分配格以及模格的定义以及相关的结论。了解一个格为模格的充要条件。6.掌握布尔代数的定义及其16个性质，掌握并会应用Huntington公理来判定一代数系统是否为布尔代数。了解电路代数、集合代数、命题代数、开关代数。掌握并会应用布尔代数的子集是其子代数的充要条件。400-810-6736 14第八章第八章 格与布尔代数格与布尔代数7.掌握可唯一表示布尔代数中元素的基底的定义及其性质。掌握极小元的定义及其性质。掌握布尔代数的生成、极小项、多项式、多项范式、布尔代数中一组元素互相独立等概念，了解