2005级-离散数学(1)教案-李占山,于海鸿,卢欣华

1、课程编码：（参考本科培养计划）离散数学I课程教案 2008 2009 学年第 1 学期任课教师： 李占山 于海鸿 卢欣华吉林大学计算机学院课程名称： 离散数学I 课程英文名称：discreted mathematics学时： 64学分：授课对象： 计算机科学与技术 专业 2007级1-14班教学目的：（参照教学大纲）教学方式：板书 多媒体 投影教材：孙吉贵等离散数学高等教育出版社，2002教学参考书：孙吉贵等离散数学学习指导与习题解答高等教育出版社，2003耿素云集合论与图论 北京大学出版社，1998 授课题目11集合的基本概念授课学时4授课时间第1周教学重点、难点：教学重点：1集合、子集、超

2、集、空集、幂集、集合族的概念。两个集合间相等和包含关系的定义和性质，利用定义证明两个集合相等。常用的集合表示方法。2集合的基本运算：并、交、余、差、直乘积，对称差的定义以及集合运算满足的基本算律，利用它们来证明更复杂的集合等式。教学难点：1如何去证明两个集合相等与包含；2笛卡儿积的深入理解与实际应用。教学要点：1集合及集合相关概念2集合的分类：有穷集（有限集）、无穷集。3空集和全集的定义。4给出集合的关系：集合相等和包含关系。5幂集的定义及性质。6集合族的定义。7集合的运算：差、并、余（补）与交运算8笛卡儿积的定义及性质。9集合的算律。10集合的表示方法主要有3种：描述法；列举法；文氏图法(J

3、ohn Venn) 讲述方法：本节在讲述基本概念时要引入大量的实例，让学生充分理解定义的内涵与外延；在给出集合相等定义的同时要引导学生思考如何去证明两个集合相等以及两个集合的包含关系；在讲解集合的算律时要讲、练结合，将书中所给的算律充分融入到习题中，让学生通过练习来掌握算律，而不是死记硬背。参考文献： 离散数学学习指导与习题解答 孙吉贵等 高等教育出版社离散数学精讲·精解·精练 黄健斌 西安电子科技大学出版社集合论与图论 耿素云 北京大学出版社 作业安排：教材中习题1.1中的第1、2题。答疑时间：另行安排授课题目12 关系授课学时6授课时间第2、3周教学重点、难点：教学重点

4、：1关系、二元关系、空关系、全域关系、相等关系、逆关系的概念以及关系的性质：自反性、对称性、反对称性、传递性。会做关系的乘积。了解关系的闭包运算：自反闭包、对称闭包、传递闭包。2等价关系、等价类、商集的概念，了解等价关系和划分的内在联系。3部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最大元、最小元、极大元、极小元、上确界、下确界的定义。能画出有限部分序集的Hasse图，并根据图讨论部分序集的某些性质。教学难点：1等价关系与等价类的理解；2部分序集的理解教学要点：1关系的基本概念及其性质关系的定义及特点讲授方法：通过例1.2.1 来引导学生理解关系的定义并总结出其特点。

5、关系的运算关系的并、交、差、余等运算。讲授方法：通过引导学生思考子关系的定义基础上，给出关系的并、交、差、余的运算。注：（1）集合的并、交、差、余运算性质对关系运算也成立。（2）作为关系时，余运算是对全域关系而言的，即A´B作为全集E。关系的性质自反性；对称性；传递性；反自反、反对称及递讲授方法：在讲关系的性质时，可以引入一些日常生活中的实例让学生理解关系的性质。2关系的乘法关系的乘法定义及定理1.2.1至1.2.43关系的闭包。关系的闭包定义及求解方法（定理1.2.5）4等价关系 等价关系、等价类的定义；商集的定义； 等价关系、等价类的计算（求解即定理1.2.6至1.2.8） 讲授

6、方法：通过1.2.2至1.2.5等例子来讲解。让学生逐步理解等价关系、等价类和商集的定义，并求解集合上等价关系和等价类，引导学生思考定理的局限性。5部分序关系。 部分序关系的定义及部分序集的定义集合的最大、最小元素、极大、极小元素部分序集的哈斯图的画法讲授方法：通过具体的例子来讲解该部分内容。作业安排：教材中习题1.2中的第9、10题。答疑时间：另行安排授课题目13映射授课学时4授课时间第3、4周教学重点、难点：1掌握映射、映像、1-1映射等概念，会做映射的乘积。2了解可数集合的概念，掌握可数集合的判定方法。教学难点：1判断集合的可数、不可数2证明集合的可数、不可数教学要点：1映射的基本概念映

7、射的定义；单射、满射的定义；1-1映射的定义；映射的复合定义；逆映射的定义；讲授方法：通过大量的示意图来让学生理解这些基本概念。2集合的基数集合基数的定义，表示形式；两个集合基数相等的定义；集合间基数的比较；讲授方法：本部分内容的讲解可以结合一些具体的例子特别是自然数，学生较好理解。3可数集合可数集合的定义；判断集合可数的方法；讲授方法：通过给出可数集合的概念，以及讲解定理证明的过程，引导学生逐步掌握集合可数的判断方法。4不可数集合不可数集合的定义；判断集合不可数的方法；讲授方法：通过定理1.3.6证明过程的讲解，让学生掌握康托尔对角线法；通过定理1.3.8的证明过程讲解，引导学生逐步掌握构造

8、性证明方法，以及反证法的应用。5本章内容小结参考文献： 离散数学学习指导与习题解答 孙吉贵等 高等教育出版社离散数学精讲·精解·精练 黄健斌 西安电子科技大学出版社集合论与图论 耿素云 北京大学出版社 作业安排：教材中习题1.3中的第1、2题。答疑时间：另行安排授课题目2.1 命题以及逻辑联结词授课学时1.5授课时间第4周教学重点：掌握命题、简单命题、复合命题的概念，掌握命题真假的判断方法教学难点：理解蕴涵命题为真为假的前提条件教学要点：1命题的基本概念。命题的定义；理解和掌握简单命题和复合命题；讲授方法：首先给出定义，然后通过例子理解和掌握定义，并且要求学生区分出简单命题

9、和复合命题。2命题的真值 命题的真值有两种：0（假），1（真）讲授方法：首先要求学生明确定义，然后给出一些命题要求学生判断真假值。从而让学生进一步明确命题的定义（引申）。3常用的联结词 联结词的定义：五种常用的联结词符号：Ø（否）Ú（析取）Ù（合取）®（蕴含）«（等价）联结词的运算表联结词的运算优先级联结词的含义以及自然语言描述参考文献： 离散数学学习指导与习题解答 孙吉贵等 高等教育出版社离散数学精讲·精解·精练 黄健斌 西安电子科技大学出版社作业安排：教材中习题2.1中的第3题。答疑时间：另行安排授课题目2.2 命题公式

10、授课学时2.5授课时间第4、5周教学重点：掌握命题公式的概念，理解命题公式的解释的定义教学难点：给定一个公式，判定其是否为恒真公式或恒假公式教学要点： 1公式的基本概念。原子的定义；命题逻辑中的公式定义；讲授方法：给出命题逻辑中的公式定义，逐步引导学生领会递归定义的方法。2解释的定义解释的定义；例子； 讲授方法：回顾命题的相关知识，给出一个命题公式，进行赋值，判断其真、假值，引出解释的定义。3真值表 真值表的定义：真值表的画法；记住一个结论：n个不同原子的公式，共有2n个解释。讲授方法：通过一具体例子，教会学生会画真值表，并引导学生学会利用真值表来判断公式是否恒真、恒假、可满足。4公式G恒真的

11、定义；公式G恒假的定义；公式G可满足的定义。5如何判断一个公式恒真、恒假、可满足。 参考文献： 离散数学学习指导与习题解答 孙吉贵等 高等教育出版社离散数学精讲·精解·精练 黄健斌 西安电子科技大学出版社作业安排：习题2.2.4 答疑安排：另行通知授课题目2.3 命题公式的等价关系和蕴涵关系授课学时4授课时间第5、6周教学重点：掌握命题公式的等价的相关概念；掌握命题公式蕴涵的相关概念；掌握演绎的相关概念和有关定理；掌握基本蕴涵式；理解公式蕴涵的证明方法。教学难点：公式蕴涵的证明方法；区别公式蕴涵和命题蕴涵的差异。教学要点：1公式的等价相关概念。公式等价的定义；公式G、H等价

12、的充要条件；基本等价式；完备集的定义以证明。讲授方法：给出公式等价的定义及一些基本等价式（要求学生通过上节课所学内容可以证明）。 2公式的蕴涵相关概念及相关定理公式的蕴涵的定义；公式G蕴涵公式H的充要条件；定理2.3.1 讲授方法：通过一个例子给出公式蕴涵的定义（注意区别Þ和=），给出定理2.3.1利用基本等价公式证明。3演绎的相关概念及相关定理 演绎的定义：引理定理2.3.2定理2.3.3一些基本蕴涵式4公式蕴涵的证明方法讲授方法：通过回忆的方法逐一引导学生思考如何证明公式G蕴涵H。 参考文献： 离散数学学习指导与习题解答 孙吉贵等 高等教育出版社离散数学精讲·精解

13、83;精练 黄健斌 西安电子科技大学出版社离散数学 耿素云等 高等教育出版社 作业安排：习题2.3.1、8 答疑安排：另行通知授课题目2.4 范式授课学时4授课时间第6、7周教学重点、难点：教学重点：1析取范式、合取范式、极大项、极小项、主析取范式、主合取范式的概念和性质。2掌握求各种范式的方法，能够用等价演算法和真值表法求命题公式的主析取范式、主合取范式。3了解一个命题公式的主合取范式与主析取范式的关系。教学难点：1命题公式的析取范式与合取范式的转化；2命题公式恒真、恒假的判断。教学要点： 1范式的概念 文字的定义；子句的定义；短语的定义。 提醒学生注意：一个文字既可称为是一个子句，也可称为

14、是一个短语。 析取范式的定义；合取范式的定义 提醒学生注意：一个文字既可称为是一个合取范式，也可称为是一个析取范式。一个子句，一个短语既可看做是合取范式，也可看做是析取范式。 讲授方法：讲解时可以通过一个具体的例子来展示定义的内涵。 对于任意命题公式，都存在等价于它的析取范式和合取范式。2主析取范式和主合取范式 极小（大）项的定义； 结论：n个不同原子的公式，有2n个不同的极小（大）项。主析取范式的概念；主合取范式的概念。 对于命题公式G，都存在等价于它的主析取范式。 设公式G，H是关于原子P1，Pn的两个主析取范式。 如果G，H不完全相同，则G，H不等价。 对于任意公式G，存在唯一一个与G等

15、价的主析取范式。讲授方法：讲解本部分内容可以做这样的教学设计：给出一个公式G，它的范式是不唯一的，能否有唯一的标准形式呢? （提出问题）答案是有（引导学生分析问题），引出主析取范式和主合取范式的概念。（解决问题）3恒真恒假性的判定 解决判定问题的方法：短语是恒假的当且仅当至少有一个原子及其否定(也称互补对)同时在此短语中出现。命题公式G是恒假的当且仅当在等价于它的析取范式中，每个短语均至少包含一个原子及其否定。 把公式化成主析取范式：公式恒假时，主析取范式没有极小项；公式恒真时，主析取范式有全部极小项。 一种判定算法：对任给要判定的命题公式G，设其中有原子P1，P2，Pn，令P1取1值，求G的

16、真值，或为1，或为0，或成为新公式G1且其中只有原子P2，Pn，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G恒假，若最终结果有1，有0，则是可满足的。4本章内容小结作业安排：教材中习题2.4中的第4、5题。授课题目3.1 谓词逻辑的基本概念授课学时2授课时间第7周教学重点、难点：教学重点：谓词、全称量词、存在量词等概念，学会使用它们符号化一些命题并构成一些较复杂的命题。约束变量、自由变量的概念，能够正确使用改名规则。教学难点：n元谓词的理解；存在量词或全称量词限定的公式真值的理解 教学要点：1谓词和量词谓词定义、量词定义量

17、词限定公式的真值变量和命题函数中的变量区别量词的作用域教学方法：通过逻辑学中的著名的三段论案例，让学生理解命题逻辑的局限性，以及研究谓词逻辑的必要性，从而引出谓词逻辑的基本概念。2改名规则 变量的约束与自由的含义改名规则教学方法：通过一些例子的练习让学生正确理解与掌握改名规则及其使用。参考文献： 离散数学学习指导与习题解答 孙吉贵等 高等教育出版社离散数学精讲·精解·精练 黄健斌 西安电子科技大学出版社离散数学 耿素云等 高等教育出版社 作业安排：教材中习题3.1中的第3题。答疑时间：另行安排授课题目3.2 谓词公式 授课学时2授课时间第8周教学重点、难点：教学重点：谓词公

18、式、解释的概念，能够求出一给定公式在某一解释下的真值。恒真公式、恒假公式、可满足公式等概念，了解与命题逻辑判定问题可解不同的是：谓词逻辑判定问题不可解，但谓词逻辑是半可判定的。教学难点：函数符号的理解谓词公式的解释教学要点：1 谓词公式四种符号：常量符号、变量符号、函数符号、谓词符号项的定义公式的定义教学方法：通过例子进一步理解谓词逻辑的递归定义，让学生分析对比这些概念与命题逻辑中相关知识的区别与联系，从而提高分析问题解决问题的能力2 解释解释的定义解释包含的内容与形式结构公式的恒真、恒假以及可满足的定义教学方法：通过一些具体案例的讲解也可结合实际应用问题进行讲解，让学生领会解释的实际含义，并

19、学会对具体公式给出满足或弄假公式的解释参考文献： 离散数学学习指导与习题解答 孙吉贵等 高等教育出版社离散数学精讲·精解·精练 黄健斌 西安电子科技大学出版社离散数学 耿素云等 高等教育出版社 作业安排：教材中习题3.2中的第2、3题答疑时间：另行安排授课题目3.3 谓词公式的等价关系和蕴含关系授课学时2授课时间第8周教学重点、难点：教学重点：谓词公式的等价、蕴涵等概念，熟记基本的等价式、蕴涵式，会证明更复杂的等价式、蕴涵式。教学难点：谓词演算的推理方法的掌握教学要点：1谓词公式的等价关系 谓词公式等价的定义谓词公式等价的充要条件教学方法；通过例子的讲解使学生能够分析对比谓

20、词公式等价与命题公式等价的区别和联系，从而加深学生对问题的理解2谓词公式的蕴涵关系 谓词公式蕴涵的定义谓词公式蕴涵的充要条件基本蕴涵式教学方法；通过三段论例子的进一步讲解使学生能够分析对比谓词公式蕴涵与命题公式蕴涵的区别和联系，从而加深学生对问题的理解，并看到谓词逻辑的不足，引导和启发学生深入思考一些相关问题3谓词演算的推理方法谓词演算规则演算规则的使用规则错误使用的识别教学方法；通过例子的讲解过程使学生掌握这些规则和推理方法的具体运用，并能够识别推理过程中的规则使用错误参考文献： 离散数学学习指导与习题解答 孙吉贵等 高等教育出版社离散数学精讲·精解·精练 黄健斌 西安电

21、子科技大学出版社离散数学 耿素云等 高等教育出版社 数理逻辑 王捍贫 北京大学出版社作业安排：教材中习题3.3中的第1题。答疑时间：另行安排授课题目34 范 式授课学时2授课时间第9周教学重点、难点：教学重点：1掌握前束范式、Skolem范式等概念；2掌握将谓词公式化成与之等价的前束范式，并进一步化为Slolem范式。教学难点：公式与其Slolem范式可满足性的等价性证明。教学要点：1范式的概念前束范式的定义； 等价公式；对任意公式G，都存在与其等价的前束范式；改名公式在谓词逻辑中的应用；公式的等价前束范式求解方法；教学方法：在讲解本部分内容时要注意提出问题，引导学生去思考求解问题的方法。例如

22、为什么提出改名，它的意义在哪里？2Skolem范式的概念Skolem范式的定义及理解；公式G的Skolem函数定义；设S是公式G的Skolem范式，于是，公式G是恒假的充要条件是公式S是恒假的；公式G与它的Skolem范式S可满足性是等价的；教学方法：在讲解本部分内容时要注意提出问题，引导学生去思考求解问题的方法。例如为什么提出Skolem范式？它的意义在哪里？是否存在更好的解决方案？最后让学生了解谓词逻辑在计算机科学中的应用。3本章内容小结参考文献： 离散数学学习指导与习题解答 孙吉贵等 高等教育出版社离散数学精讲·精解·精练 黄健斌 西安电子科技大学出版社离散数学 耿素

23、云等 高等教育出版社 数理逻辑 王捍贫 北京大学出版社作业安排：教材中习题3.4中的第2、3题。答疑时间：另行安排授课题目41 图授课学时4授课时间第9、10周教学重点、难点：教学重点：1掌握图的概念。2理解Dijkstra算法，并能够在已知权图中使用该算法求出任意两点间的最短路教学难点：Dijkstra算法的正确性证明。教学要点：1图的概念图的定义； 子图的定义；图的矩阵表示：相邻矩阵和关联矩阵；有限图中点的度；教学方法：在讲解本部分内容时多举例子，让学生对于图有一个直观的理解。2权图和Dijkstra算法权图的定义；Dijkstra算法；Dijkstra算法的执行过程；Dijkstra算法

24、的正确性证明；教学方法：在讲解本部分内容时要注意提出问题，引导学生去思考算法的本质。例如Dijkstra算法的原理是什么？它主要适合那些问题？有没有更好的方法？并鼓励学生通过编程实现算法加深对于算法的理解。参考文献： 离散数学学习指导与习题解答 孙吉贵等 高等教育出版社集合论与图论 耿素云 北京大学出版社 网络优化 谢金星 邢文训 清华大学出版社作业安排：教材中习题4.1中的第7题。答疑时间：另行安排授课题目42 树授课学时4授课时间第10、11周教学重点、难点：教学重点：1掌握树、支撑树的概念以及图是树的几个等价命题。2理解Kruskal算法，并能够应用它求已知加权连通图的最优树。了解求最优

25、树的Prim算法，会总结Sollin算法。教学难点：树的等价命题；Kruskal算法的正确性证明。教学要点：1树及其等价命题数和森林的定义； 引理1；树的等价命题；定理4.2.1 如果G是图，则下列诸命题等价：1） G是树。2） G连通并且删去G的任意一边，所得之图都不连通。3） 对G中任意两点v，v(v¹v)，恰有一条从v到v的简单路。如果G还是有限图，设P(G)元数为n，则下列命题也与上面命题等价：4） G不含回路，并且G有（n-1）条边。5） G连通，并且G有（n-1）条边。教学方法：在讲解定理4.2.1时，注意让学生领会证明方法，并着重强调反证法的作用2最优树和Kruskal

26、算法 最优树定义及理解；Kruskal算法；Kruskal算法的正确性证明；了解求最优树的其他算法教学方法：在讲解本部分内容时要注意提出问题，引导学生去思考求解问题的方法。在讲授Kruskal算法的时候注意让学生理解算法的原理，并剖析其“闭圈法”的本质，同时鼓励学生上机编程实现。参考文献： 离散数学学习指导与习题解答 孙吉贵等 高等教育出版社集合论与图论 耿素云 北京大学出版社 网络优化 谢金星 邢文训 清华大学出版社作业安排：教材中习题4.2中的第4题。答疑时间：另行安排授课题目43 有向图 Euler路授课学时6授课时间第11、12周教学重点、难点：教学重点：1 掌握有向图、有向子图、有向

27、路、简单有向路、有向回路等概念。2. 掌握有向图的强连通性和有向图的根的概念，了解二者的关系。3. 掌握有向树的概念以及有向树与树的转化定理。4. 掌握Euler路、Euler图的概念，掌握有向图中和无向图中Euler图的充要条件，并能利用判断某图是否为Euler图。了解从Euler路得出有向支撑树以及从有向支撑树得出Euler路的方法。教学难点：转化定理的证明；无孤立点有限有向图中有Euler路的充分必要条件；教学要点：1有向图与有向树的相关定义有向图的定义；有向路的定义；有向图的强连通性和有向图的根的概念；有向树的概念；转化定理：对有向树G，若无视各弧之方向，则得一树G0；反之，若G0是树

28、，可选取任一点做根，并适当指定各边之方向，则得一有向树G。教学方法：在讲解本部分内容时要注意联系直观，尤其是对于转化定理，能给学生以直观的方式，这样能够加深对于证明方法以及定理本身的理解。2Euler路Euler路和Euler图的概念；有向图中和无向图中Euler图的充要条件以应用：设G是无孤立点的有限有向图。于是，G有Euler路当且仅当G是平衡的，并且强连通。Euler路得出有向支撑树以及从有向支撑树得出Euler路的方法教学方法：在讲解本部分内容时要注意避免把着眼点局限在证明上，要多举例子和讲授证明的方法，以加深学生对于复杂证明的理解。参考文献： 离散数学学习指导与习题解答 孙吉贵等 高

29、等教育出版社集合论与图论 耿素云 北京大学出版社 网络优化 谢金星 邢文训 清华大学出版社作业安排：教材中习题4.3中的第1题。答疑时间：另行安排授课题目44 Hamilton图授课学时4授课时间第13周教学重点、难点：教学重点：1掌握Hamilton路、Hamilton回路、Hamilton图的概念以及Hamilton图的必要条件和若干充分条件。2了解流动推销员问题和求解Hamilton路的逼近算法。教学难点：Hamilton图的必要条件和若干充分条件的证明。教学要点：1Hamilton路的相关概念Hamilton路的提出； Hamilton路的定义；Hamilton图的定义；Hamilto

30、n图的必要条件；教学方法：在讲解本部分内容时要注意提出问题，引导学生去思考求解问题的方法。2Hamilton图的若干充分条件教学方法：在讲解本部分内容时要注意让学生对于定理应用的掌握，同时通过讲授巧妙的证明过程，使得学生能够理解找到判定Hamilton图充分必要条件的困难，并激发学生探索的精神3. 本章小结参考文献： 离散数学学习指导与习题解答 孙吉贵等 高等教育出版社集合论与图论 耿素云 北京大学出版社 网络优化 谢金星 邢文训 清华大学出版社作业安排：由于课后习题比较难，选择部分作为例题讲授答疑时间：另行安排授课题目51 整除性 辗转相除授课学时2.5授课时间第14周教学重点、难点：教学重

31、点：1掌握整除、因数、倍数等概念，记住并会应用整除的性质。2. 掌握最高公因数的概念，能够使用辗转相除法求两个数的最高公因数并表示为它们的倍数和。会利用数的数码特征判别某些整除性教学难点：辗转相除法的原理和应用。教学要点：1整除的相关定义整除的定义；整除的性质教学方法：在讲解本部分内容时要注意提出问题，引导学生去思考求解问题的方法。例如为什么要研究整除，它的意义在哪里？2辗转相除辗转相除求两个数最高公因的证明；辗转相除的运用教学方法：在讲解本部分内容时要注意强调对于知识的应用和掌握基本的方法。例如对于辗转相除法，要让学生理解它的原理，操作步骤。并让学生了解它在数论中的地位。参考文献： 离散数学

32、学习指导与习题解答 孙吉贵等 高等教育出版社离散数学精讲·精解·精练 黄健斌 西安电子科技大学出版社初等数论 闵嗣鹤 严士健 人民教育出版社 作业安排：教材中习题5.1中的第2题。答疑时间：另行安排授课题目52 互质 质因数分解授课学时1.5授课时间第14周教学重点、难点：教学重点：1 掌握互质的概念和质数的性质。2 掌握质数、合数的概念以及算术基本定理、欧几里得定理。教学难点：算数基本定理。教学要点：1掌握互质的概念和质数的性质互质的定义； 质数的性质；教学方法：在讲解本部分内容时要注意提出问题，引导学生去思考求解问题的方法。例如为什么要研究质数，它的意义在哪里？合数的定义2算术基本定理、欧几里得定理算术基本定理；欧几里得定理教学方法：在讲解本部分内容时要注意提出问题，引导学生去思考求解问题的方法。同时掌握定理证明的思想，如在欧几里得定理证明质数无穷多时对于反证法的应用。参考文献： 离散数学学习指导与习题解答 孙吉贵等 高等教育出版社离散数学精讲·精解