离散数学学习指南

PAGEPAGE3离散数学学习指南学习目标1、理解集合的概念；理解子集、空集、全集、集合相等等基本概念；掌握集合的表示方法；文氏图；掌握集合的交、并、差、补等运算；掌握交换律、结合律、分配律、DeMorgan律等运算律；掌握证明集合等式的方法；掌握集合的笛卡尔积；2、理解关系的定义，熟练掌握二元关系的关系矩阵与关系图及其求法；理解二元关系的基本性质：自反关系、对称关系、传递关系，反自反关系、反对称关系（概念与判定）；掌握关系的运算：复合关系与逆关系（概念与求法）；掌握关系的闭包（概念与求法）；掌握等价关系（判定与证明、等价类的求法）；理解偏序关系，偏序集，哈斯图，最大元，最小元，极大元，极小元，上界，下界，上确界，下确界等偏序关系中的特殊元素的概念；3、了解关系在计算机科学中的应用；4、理解函数的定义、函数的定义域和值域；理解函数的性质：单射函数、满射函数、双射函数（概念与判定）；掌握函数的运算：复合函数、逆函数（概念与求法）；5、理解代数运算的概念，掌握代数运算的判定；理解代数系统的概念，掌握代数系统的判定；掌握代数运算的性质（交换律、结合律、分配律、吸收律、等幂律、消去律）和特殊元素（等幂元，幺元，逆元，零元）；理解代数系统同构的概念，掌握证明两个代数系统同构的方法；理解代数系统同态的概念，掌握证明两个代数系统同构的方法；6、理解半群和子半群的定义，掌握半群和子半群的性质和判定；理解独异点和子独异点的定义，掌握独异点和子独异点的性质和判定；理解群的概念，掌握群的性质；理解子群的概念，掌握子群的性质和判定；理解陪集的概念，掌握陪集的性质及拉格朗日定理；掌握循环群和置换群的定义与性质；理解正规子群的概念和性质；理解格的概念，掌握格的性质；理解并掌握有界格、分配格、有补格的定义和性质；理解布尔代数的定义及性质。7、掌握图的定义、图的阶数、n阶图的概念；理解有向边、无向边的概念及其序偶表示；掌握端点、始点、终点的概念，以及始点和终点与端点之间的关系；掌握关联边、平行边、自环的概念；理解邻接结点、邻接边的概念；掌握简单图、无向图、有向图、无向简单图、有向简单图、完全图、有向完全图的概念；理解多重图、混合图的概念；掌握子图、真子图、生成子图、导出子图的概念，以及各子图之间的关系。掌握结点的度数、出度、入度的概念，以及度数与出度、入度之间的关系；掌握握手定理及其推论；掌握图的同构的概念。掌握通路、简单通路、初级通路的概念；掌握回路、简单回路、初级回路的概念；掌握连通图、连通分支、连通分支数的概念；掌握弱连通图、单向连通图、强连通图的概念，以及连通图与通路、回路之间的关系；掌握弱连通分支、单向连通分支、强连通分支的概念。8、理解图的操作，包括删除边、删除结点、收缩边；掌握图的矩阵表示，包括关联矩阵、邻接矩阵、可达矩阵；9、掌握赋权图及最短通路的概念；理解边权矩阵；掌握Dijkstra算法并学会运用；理解Floyd算法。10、掌握欧拉通路、欧拉回路、半欧拉图、欧拉图的概念；掌握欧拉图的判定定理；掌握哈密顿通路、哈密顿回路、半哈密顿图、哈密顿图的概念；掌握哈密顿图的判定定理；理解货郎担问题及最邻近算法。11、掌握二部图、完全二部图的定义及二部图的判定定理；掌握匹配、完全匹配的概念及霍尔定理。掌握平面图、面的概念；理解对偶图的概念；掌握欧拉公式、库拉托夫斯基定理；理解图的着色问题。12、掌握无向树、森林、叶结点、内部结点的概念；掌握树的性质；理解赋权树、权函数、权的概念；掌握生成树、树枝、弦、余树的概念；掌握最小生成树的概念；掌握避圈法和破圈法；掌握有向树、叶结点、根、内部结点的概念；掌握根树、树根、树叶、层数、树高、子树的概念；掌握根树的性质，理解k-元树；掌握根树遍历方法、（叶）带权树、最优树的概念；掌握Huffman算法及应用。13、识记命题表示方法、真值判断、命题（谓词）公式的定义；14、领会联结词真值确定、翻译、命题（谓词）公式的等价性和蕴含性证明、任给命题公式化为主析（合）取范式、任给谓词公式化为前束范式、命题（谓词）逻辑的推理证明方法（包括：真值表法、等值演算、主析取范式法和构造证明法）；15、应用命题（谓词）逻辑推理演算；二、重点难点1、掌握元素与集合之间的关系，集合与集合之间的关系；2、运用集合运算的基本定律去化简集合表达式或证明集合等式；3、掌握二元关系的五个性质和二元关系的运算；4、等价关系的证明、等价类的求解，偏序关系的特殊元素的求解；5、函数的性质，求复合函数和逆函数；6、代数运算的性质（交换律、结合律、分配律、吸收律、等幂律、消去律）；7、代数运算的特殊元素（等幂元，幺元，逆元，零元）；8、代数系统的同构与同态；9、群的概念，群的性质及判定，子群的概念，子群的性质及判定；10、陪集的定义与性质，拉格朗日定理；11、群中元素的阶数，循环群的概念，循环群的性质；12、格的定义与性质；13、掌握子图、真子图、生成子图、导出子图的概念。14、掌握握手定理的应用。15、掌握连通分支数与可达关系的等价类之间的关系。16、掌握图的连通性概念，以及弱连通图、单向连通图、强连通图与通路、回路之间的关系。17、掌握图的同构。18、掌握欧拉图、哈密顿图的概念及其应用。19、掌握二部图、匹配的概念。20、掌握最小生成树概念及其算法。21、掌握Huffman算法及应用。22、命题公式间的等价关系和蕴含关系；23、命题演算的推理理论；24、谓词公式间的等价关系和蕴含关系；25、谓词演算的推理理论；三、学习方法“常思考，多做题”熟读教材。准确理解各个概念和定理的含义（结合多个例子进行理解），必须的证明过程要看懂、理解（它可以帮助你熟悉和深刻理解定理的含