离散数学 教学大纲(第七版)

《离散数学》教学大纲离散数学是信息科学技术相关专业的基础核心课程，其目标是培养学生的抽象思维能力，使学生初步掌握运用离散数学的知识建立数学模型进而分析问题、解决问题的方法。课程包括数理逻辑、集合论、图论、组合分析初步、代数系统简介、形式语言与自动机初步等6部分。本课程基本不需要先修课程，仅在个别地方用到一点高等数学和高等代数。对于某些应用实例，如果学生缺乏相关的知识，授课时可对相关知识作简单介绍或略去该实例。教材：耿素云、刘田、屈婉玲、张立昂编著，离散数学（第七版），清华大学出版社。第1章命题逻辑1．知识点命题、联结词、命题公式及其赋值、公式的分类、真值表、等值演算、范式、推理和推理证明。2．要求（1）深刻理解命题的概念，分清简单命题与复合命题。（2）熟练掌握常用联结词,,,,的涵义，并能准确地应用它们。（3）深刻理解命题的赋值、成真赋值、成假赋值、重言式、矛盾式、可满足式等概念。（4）能熟练地写出给定命题公式的真值表，并根据真值表判断公式的类型、求公式的成真赋值和成假赋值。（5）深刻理解等值式的定义，牢记基本等值式并能熟练地应用它们进行等值演算。（6）深刻理解文字、简单析取式、简单合取式、析取范式、合取范式、主析取范式、主合取范式等概念。熟练掌握极小项、极大项的定义、名称以及下角标与成真赋值、成假赋值的关系。（7）深刻理解主析取范式、主合取范式、真值表3者之间的关系。熟练掌握求主析取范式与主合取范式的方法，会用主析取范式和主合取范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值。（8）理解联结词完备集的定义，掌握联结词和，会将命题公式等值地化成指定联结词完备集上的公式。（9）会利用命题公式解决一些实际问题。（10）熟练掌握推理形式结构的两种形式和判断推理是否正确的（真值表法、等值演算法、主析取范式法等）。（11）牢记推理规则，掌握构造推理的证明以及附加前提证明法、归谬法。（12）会用推理解决一些实际问题.第2章一阶逻辑1．知识点个体词与个体域、谓词与量词、一阶逻辑公式及其解释、公式的分类、一阶逻辑等值式、前束范式。2．要求（1）深刻理解个体词与个体域、谓词、量词等概念，并能准确地运用这些概念将给定命题符号化。（2）深刻理解一阶逻辑公式、指导变元与量词的辖域、个体变项的约束出现与自由出现等概念。（3）深刻理解解释与赋值的概念，会在给定解释和赋值下解释公式。（4）深刻理解永真式、矛盾式、可满足式的概念并能判别一些公式的类型。（5）深刻理解一阶逻辑公式的等值概念，熟练掌握一阶逻辑中的重要等值式和换名规则。（6）能熟练地求出给定公式的前束范式。第3章集合的基本概念和运算1．知识点集合、集合的运算、有穷集合的计数。2．要求（1）深刻理解集合的概念，熟练掌握集合的两种表示法。（2）深刻理解集合之间的相等、包含关系以及子集、空集、全集、幂集等概念。（3）熟练掌握集合的基本运算（并、交、补、对称差等）及其运算律，并能用运算律化简集合表达式。（4）掌握证明集合相等和包含关系的方法。（5）掌握利用文氏图和包含排斥原理计数有穷集合方法。第4章二元关系和函数1．知识点笛卡儿积与二元关系、关系的运算、关系的性质和闭包、等价关系和划分、偏序关系和偏序集、函数的定义和性质、复合函数和反函数。2．要求（1）深刻理解有序对和笛卡儿积的概念，熟练掌握笛卡儿积的运算性质。（2）熟练掌握二元关系的定义及常用的二元关系，熟练掌握表示关系的3种方法。（3）熟练掌握关系的定义域、值域、逆、合成、限制、像、幂的计算方法。（4）熟练掌握判断和证明关系的自反性、反自反性、对称性、反对称性、传递性的方法，了解并、交、补、逆、合成等运算对这些性质的影响。（5）能熟练地计算关系的自反闭包、对称闭包和传递闭包。（6）深刻理解等价关系、等价类、商集、划分等概念，熟练掌握等价关系与划分的对应关系。（7）熟练掌握偏序关系、偏序集、哈斯图、偏序集中的特定元素等概念。（8）熟练掌握函数的概念以及单射、满射、双射等性质。（9）熟练掌握函数的复合、反函数及相关性质。第5章图的基本概念1．知识点无向图与有向图、通路与回路、图的连通性、图的矩阵表示、着色问题。2．要求（1）深刻理解无向图、有向图及相关的诸多概念，以及它们之间的相互关系。（2）深刻理解握手定理及其推论，并能熟练地应用它们。（3）深刻理解图的同构、简单图、完全图、正则图、子图、导出子图、补图等概念及它们的性质和相互关系，并能熟练地应用这些性质和关系。（4）理解通路与回路及相关概念，掌握图关于连通性的分类以及点割集、边割集、割点、割边等。（5）掌握图的矩阵表示和用邻接矩阵求图中通路数与回路数。（6）知道图的着色问题，能用着色问题解决一些实际问题。第6章特殊的图1．知识点二部图与匹配、Hall定理、欧拉图、哈密顿图、平面图、欧拉公式、库拉图斯基定理、平面图着色及四色定理。2．要求（1）熟练掌握二部图的概念及其判别定理。（2）掌握图和二部图的匹配及相关概念，掌握二部图具有完备匹配的充分必要条件（Hall定理）和充分条件（t条件），会利用匹配解决一些实际问题。（3）深刻理解欧拉回路与欧拉通路的定义，熟练掌握欧拉图与半欧拉图的判别定理。（4）深刻理解哈密顿回路和哈密顿通路的定义，掌握所给的存在哈密顿回路和通路的必要条件和充分条件。（5）深刻理解平面图及有关概念，掌握极大平面图的判别定理、欧拉公式和它的推广形式及相关的定理。（6）会用库拉图斯基定理证明某些非平面图。（7）理解对偶图的概念，知道地图的面着色与对偶图的点着色的对应关系，知道四色定理。第7章树1．知识点无向树、生成树、基本关联矩阵、拉普拉斯矩阵、最小生成树及避圈法、根树、Huffman算法、最佳前缀码、前缀符号法与后缀符号法、决策树。2．要求（1）深刻理解无向树的定义，熟练掌握无向树的性质。（2）深刻理解生成树和基本关联矩阵、拉普拉斯矩阵的概念，会用基本关联矩阵求所有不同生成树和用拉普拉斯矩阵求生成树个数。（3）熟练掌握求最小生成树的避圈法。（4）深刻理解有向树、根树及相关概念，熟练掌握有序树及其分类。（5）熟练掌握Huffman算法和用它求最佳前缀码。（6）了解行遍有序树的方法，掌握前缀符号法与后缀符号法。（7）了解决策树的概念，了解构造决策树的方法。第8章组合分析初步1．知识点加法法则和乘法法则、排列与组合、递推方程。2．要求（1）掌握加法法则和乘法法则在组合计数中的应用。（2）掌握排列组合问题的分类、排列组合的基本公式及其应用。（3）初步掌握递推方程的求解和应用。第9章代数系统简介1．知识点二元运算及其性质、代数系统、代数系统的同态与同构、半群与独异点、群、环与域、格。2．要求（1）深刻理解集合上的n元运算的概念，熟练掌握二元运算的性质（交换律、结合律、分配律、幂等律、消去律和吸收律等）。（2）掌握二元运算的幺元（含左幺元和右幺元）、零元（含左零元和右零元）、逆元（含左逆元和右逆元）等概念及其性质。（3）理解代数系统、子代数系统、积代数等概念，掌握同态与同构的概念及其性质。（4）了解半群和独异点的概念。（5）掌握群以及交换群、无限群、有限群、元素的阶、子群等概念和术语，掌握群的基本性质。（6）了解生成子群、循环群和置换群。（7）初步掌握环和域的定义及基本性质。（8）初步掌握格的2个等价定义和基本性质，了解分配格、有界格、有补格和布尔格等概念及相关性质。第10章形式语言与自动机初步1．知识点形式语言与形式文法及其分类、有穷自动机、正则表达式、图灵机。2．要求（1）掌握形式语言、形式文法及其生成的语言等概念。（2）掌握形式语言与形式文法的分类，知道4类语言之间的包含关系。（3）初步了解正则文法和上下文无关文法在计算机科学技术中应用。（4）掌握有穷自动机与它接受的语言。（5）掌握有穷自动机的多种变形及它们的等价性，会构造它们之间的模拟。（6）掌握正则表达式与它表示的语言。（7）了解正则表达式与有穷自动机的等价性，会用有穷自动机模拟正则表达式。（8）初步掌握图灵机及其