《吉林大学远程教育课件003》由会员分享，可在线阅读，更多相关《吉林大学远程教育课件003（14页珍藏版）》请在金锄头文库上搜索。
1、吉林大学远程教育课件主讲人主讲人: 杨凤杰杨凤杰学学 时：时：64(第六十四讲)离散数学第二章第二章 命题逻辑命题逻辑基本要求基本要求1.1.掌握命题、逻辑联结词等概掌握命题、逻辑联结词等概念，能够将命题符号化。念，能够将命题符号化。2.2.掌握命题公式、解释、恒真掌握命题公式、解释、恒真公式、恒假公式等概念。能够公式、恒假公式等概念。能够判断一命题公式是恒真、恒假判断一命题公式是恒真、恒假还是可满足。还是可满足。3.3.掌握公式的等价、蕴涵等概念，熟记基本掌握公式的等价、蕴涵等概念，熟记基本的等价式、蕴涵式，会证明更复杂的等价的等价式、蕴涵式，会证明更复杂的等价式、式、蕴涵式蕴涵式。4.4.
2、掌握联结词的功能完备集的掌握联结词的功能完备集的概念，能够判别一个联结词集概念，能够判别一个联结词集合是否为联结词的功能完备集合是否为联结词的功能完备集。5.5.掌握演绎方法，能够使用演掌握演绎方法，能够使用演绎方法进行有效推理绎方法进行有效推理。6.6.掌握析取范式、合取范式、掌握析取范式、合取范式、极大项、极小项、主析取范式、极大项、极小项、主析取范式、主合取范式的概念和性质主合取范式的概念和性质。掌握求各种范式的方法，能够用等价掌握求各种范式的方法，能够用等价演算法和真值表法求命题公式的主析演算法和真值表法求命题公式的主析取范式、主合取范式。取范式、主合取范式。第三章 谓词逻辑3.1 基
3、本要求1.掌握谓词、全称量词、存在量词等概念，学会使用它们符号化一些命题并构成一些较复杂的命题。2.掌握约束变量、自由变量的概念，能够正确使用改名规则。3.掌握谓词公式、解释的概念，能够求出一给定公式在某一解释下的真值。4.掌握恒真公式、恒假公式、可满足公式等概念，了解与命题逻辑判定问题可解不同的是：谓词逻辑判定问题不可解，但谓词逻辑是半可判定的。 5.5.掌握谓词公式的等价、蕴涵掌握谓词公式的等价、蕴涵等概念，熟记基本的等价式、等概念，熟记基本的等价式、蕴涵式，会证明更复杂的等价蕴涵式，会证明更复杂的等价式、蕴涵式式、蕴涵式。6.6.掌握前束范式、掌握前束范式、SkolemSkolem范式范
4、式等概念，能够将一谓词公式化等概念，能够将一谓词公式化成与之等价的前束范式，并成与之等价的前束范式，并进一步化为进一步化为SlolemSlolem范式范式。第四章 图与网络4.1 基本要求1.掌握图、有限图、母图、子图、支撑子图、完全图、补图等概念，了解有限图中点的度的性质，掌握图的矩阵表示：关联矩阵、邻接矩阵。2.掌握路、简单路、回路、连通图等概念。3.理解Dijkstra算法，并能够在已知权图中使用该算法求出任意两点间的最短路。 4.掌握树、支撑树的概念以及图是树的几个等价命题。 5.理解Kruskal算法，并能够应用它求已知加权连通图的最优树。了解求最优树的Prim算法，会总结Solli
5、n算法。6.6.掌握有向图、有向子图、有掌握有向图、有向子图、有向路、简单有向路、有向回路向路、简单有向路、有向回路等概念等概念。7.7.掌握有向图的强连通性和有掌握有向图的强连通性和有向图的根的概念，了解二者的关系向图的根的概念，了解二者的关系。8.8.掌握掌握EulerEuler路、路、EulerEuler图的概念，图的概念，掌握有向图中和无向图中掌握有向图中和无向图中EulerEuler图图的充要条件，并能利用判断某图是否为的充要条件，并能利用判断某图是否为EulerEuler图。了解从图。了解从EulerEuler路得出有向支撑树路得出有向支撑树以及从有向支撑树得出以及从有向支撑树得出
6、EulerEuler路的方法。路的方法。10. 10. 掌握掌握HamiltonHamilton路、路、HamiltonHamilton回路、回路、HamiltonHamilton图的概念以及图的概念以及HamiltonHamilton图的必要图的必要条件和若干充分条件。条件和若干充分条件。第六章 群与环基本要求1.掌握二元代数运算、代数系统的定义，能够判断一运算是否为二元代数运算，运算是否满足交换律、结合律、分配律、幂等律、吸收律、消去律。2.掌握半群、群的定义以及群的性质，能够判断一代数系统是否为半群或群。3.掌握交换群的定义以及交换群中的三个指数律。4.掌握置换、轮换、不相杂轮换、对换等
7、概念，会做置换的乘法，会将任意置换写成不相杂轮换的乘积。了解置换的顺向圈表示。5.掌握奇置换、偶置换的概念，了解置换的定性数与置换的图型及奇偶性的关系。6. 6. 掌握掌握n n次对称群、次对称群、n n次交代群的次交代群的概念，会写出其中的元素。概念，会写出其中的元素。7.7.掌握子群的定义以及子群的判别掌握子群的定义以及子群的判别条件。掌握周期、循环群的定义和条件。掌握周期、循环群的定义和乘法群、加法群中周期的性质以及乘法群、加法群中周期的性质以及循环群中一元素作为生成元的充要条件。循环群中一元素作为生成元的充要条件。8.8.掌握群中合同、右陪集的定义。掌握群中合同、右陪集的定义。了解子群
8、在大群中的右陪集的一些性质。掌握正了解子群在大群中的右陪集的一些性质。掌握正规子群的概念以及一子群为大群的正规子群的规子群的概念以及一子群为大群的正规子群的充要条件。掌握并会正确应用充要条件。掌握并会正确应用LagrangeLagrange定理。定理。9.9.掌握同态映射、同构映射、自同构映射的概念掌握同态映射、同构映射、自同构映射的概念以及同态定理。会判断一个群与一乘法系以及同态定理。会判断一个群与一乘法系统间的映射是否为同态映射、同构映射或自同构统间的映射是否为同态映射、同构映射或自同构映射。映射。10. 10. 掌握同态核的概念，了解掌握同态核的概念，了解若若是群是群G G到到GG上的同
9、态映射，上的同态映射，则其核则其核N N为一正规子群。反过来，为一正规子群。反过来，设设N N是是G G的一个正规子群，则有的一个正规子群，则有一个群一个群GG以及一个以及一个G G到到GG上的上的同态映射同态映射，使使N N为为的核。掌的核。掌握并会正确应用联系同态与同构的基本定理。握并会正确应用联系同态与同构的基本定理。了解了解为群为群G G到到GG上的同态映射时，上的同态映射时，G G中中子群与子群与GG中子群的关系。中子群的关系。11. 11. 掌握环、交换环、含壹环、消去环的定掌握环、交换环、含壹环、消去环的定义及其性质，会判断。义及其性质，会判断。12.12.掌握整区、体、域、子环
10、、掌握整区、体、域、子环、子体、子域等概念，以及环的子体、子域等概念，以及环的子集作成子环的充要条件。子集作成子环的充要条件。13. 13. 掌握并会应用理想、主掌握并会应用理想、主理想的定义，掌握环中合同理想的定义，掌握环中合同关系、剩余类的定义以及环关系、剩余类的定义以及环中合同关系的性质。中合同关系的性质。14. 14. 掌握环同态映射、同构映射、剩余环的掌握环同态映射、同构映射、剩余环的定义，了解与群论中平行的环中的关于同定义，了解与群论中平行的环中的关于同态映射、同构映射的一些定理。态映射、同构映射的一些定理。15. 15. 掌握单纯环与极大理想的定义，掌握单纯环与极大理想的定义，以
11、及二者的关系，了解一个环是域的充要条以及二者的关系，了解一个环是域的充要条件。件。 第八章第八章 格与布尔代数格与布尔代数8.1 8.1 基本要求基本要求1.1.掌握半序格、半序子格、代数格、掌握半序格、半序子格、代数格、代数子格的定义，了解半序格和代代数子格的定义，了解半序格和代数格的定义是等价的。数格的定义是等价的。2.2.掌握互相对偶的两个关系、互掌握互相对偶的两个关系、互相对偶的两个格的定义，了解二相对偶的两个格的定义，了解二者关系。掌握格中表达式、对偶格者关系。掌握格中表达式、对偶格中的对偶表达式、本格中的对偶表达式的定义，中的对偶表达式、本格中的对偶表达式的定义，掌握并会应用对偶原
12、理掌握并会应用对偶原理1 1及对偶原理及对偶原理2 2。3.3.了解格的其它性质，如格的保序性、分配不等了解格的其它性质，如格的保序性、分配不等式、模不等式等。式、模不等式等。4.4.掌握并会应用格同态映射、格的自同态映射、掌握并会应用格同态映射、格的自同态映射、格同构映射的定义。了解格的同态映射一定是格同构映射的定义。了解格的同态映射一定是保序映射，同构映射的逆映射也是同构映射等保序映射，同构映射的逆映射也是同构映射等结论。结论。5. 5. 掌握有界格、有余格、分配格以及模掌握有界格、有余格、分配格以及模格的定义以及相关的结论。了解一个格为格的定义以及相关的结论。了解一个格为模格的充要条件。
13、模格的充要条件。6.6.掌握布尔代数的定义及其掌握布尔代数的定义及其1616个性质，个性质，掌握并会应用掌握并会应用HuntingtonHuntington公理来判定一代公理来判定一代数系统是否为布尔代数。了解电路代数、数系统是否为布尔代数。了解电路代数、集合代数、命题代数、开关代数。掌握并集合代数、命题代数、开关代数。掌握并会应用布尔代数的子集是其子代数的充要条件。会应用布尔代数的子集是其子代数的充要条件。7.7.掌握可唯一表示布尔代数中元素的基底的掌握可唯一表示布尔代数中元素的基底的定义及其性质。掌握极小元的定义及其性质。定义及其性质。掌握极小元的定义及其性质。掌握布尔代数的生成、极小项、
14、多项式、多项范式、掌握布尔代数的生成、极小项、多项式、多项范式、布尔代数中一组元素互相独立等概念，了解布尔代数中元布尔代数中一组元素互相独立等概念，了解布尔代数中元素与多项范式的关系和极小项、基底、极小元间的关系。素与多项范式的关系和极小项、基底、极小元间的关系。8.8.掌握布尔代数中同态、同构的概念及其相应结论。掌握布尔代数中同态、同构的概念及其相应结论。了解如果两个有限布尔代数的维数相同，则这两个代数同了解如果两个有限布尔代数的维数相同，则这两个代数同构；任意构；任意n n维布尔代数（维布尔代数（B B，+ +，0 0，1 1）与开关与开关代数（代数（B Bn n，+ +，0 0n n，1
15、 1n n）同构；同构；StoneStone定理。定理。 第九章第九章 语言和有限状态机语言和有限状态机基本要求基本要求1.1.掌握语法结构、语言、演绎、掌握语法结构、语言、演绎、演绎树的概念，能识别语法结构演绎树的概念，能识别语法结构的分类，能写出一个语法的的分类，能写出一个语法的Backus-Backus-NaurNaur form form。2.2.掌握带有输出的有限状态机的掌握带有输出的有限状态机的定义，能够使用状态图和状态表定义，能够使用状态图和状态表表示带有输出的有限状态机。表示带有输出的有限状态机。3.3.会求串联、会求串联、kleenekleene闭包，掌握没有输出的有限闭包，掌握没有输出的有限状态机（有限状态自动机）的概念，了解非确状态机（有限状态自动机）的概念，了解非确定的有限状态机，知道能被一个非确定的有限定的有限状态机，知道能被一个非确定的有限状态自动机是别的语言也可以被一个确定的有状态自动机是别的语言也可以被一个确定的有限状态自动机识别。限状态自动机识别。4.4.掌握正则表达式和正则集合的概念，了解掌握正则表达式和正则集合的概念，了解KLEENEKLEENE定理。知道一个集合是由一个正则语法定理。知道一个集合是由一个正则语法产生的当且仅当它是正则集合。产生的当且仅当它是正则集合。
