搜索
1课程编码：（参考本科培养计划）离散数学I课程教案2008～2009学年第1学期任课教师：李占山于海鸿卢欣华吉林大学计算机学院2课程名称：离散数学I课程英文名称：discretedmathematics学时：64学分：授课对象：计算机科学与技术专业2007级1-14班教学目的：（参照教学大纲）教学方式：板书多媒体投影教材：孙吉贵等《离散数学》高等教育出版社，2002教学参考书：孙吉贵等《离散数学学习指导与习题解答》高等教育出版社，2003耿素云《集合论与图论》北京大学出版社，19983授课题目1．1集合的基本概念授课学时4授课时间第1周教学重点、难点：教学重点：1．集合、子集、超集、空集、幂集、集合族的概念。两个集合间相等和包含关系的定义和性质，利用定义证明两个集合相等。常用的集合表示方法。2．集合的基本运算：并、交、余、差、直乘积，对称差的定义以及集合运算满足的基本算律，利用它们来证明更复杂的集合等式。教学难点：1．如何去证明两个集合相等与包含；2．笛卡儿积的深入理解与实际应用。教学要点：1．集合及集合相关概念2．集合的分类：有穷集（有限集）、无穷集。3．空集和全集的定义。4．给出集合的关系：集合相等和包含关系。5．幂集的定义及性质。6．集合族的定义。7．集合的运算：差、并、余（补）与交运算8．笛卡儿积的定义及性质。9．集合的算律。10．集合的表示方法主要有3种：描述法；列举法；文氏图法(JohnVenn)讲述方法：本节在讲述基本概念时要引入大量的实例，让学生充分理解定义的内涵与外延；在给出集合相等定义的同时要引导学生思考如何去证明两个集合相等以及两个集合的包含关系；在讲解集合的算律时要讲、练结合，将书中所给的算律充分融入到习题中，让学生通过练习来掌握算律，而不是死记硬背。参考文献：《离散数学学习指导与习题解答》孙吉贵等高等教育出版社《离散数学——精讲·精解·精练》黄健斌西安电子科技大学出版社《集合论与图论》耿素云北京大学出版社作业安排：教材中习题1.1中的第1、2题。答疑时间：另行安排4授课题目1．2关系授课学时6授课时间第2、3周教学重点、难点：教学重点：1．关系、二元关系、空关系、全域关系、相等关系、逆关系的概念以及关系的性质：自反性、对称性、反对称性、传递性。会做关系的乘积。了解关系的闭包运算：自反闭包、对称闭包、传递闭包。2．等价关系、等价类、商集的概念，了解等价关系和划分的内在联系。3．部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最大元、最小元、极大元、极小元、上确界、下确界的定义。能画出有限部分序集的Hasse图，并根据图讨论部分序集的某些性质。教学难点：1．等价关系与等价类的理解；2．部分序集的理解教学要点：1．关系的基本概念及其性质关系的定义及特点讲授方法：通过例1.2.1来引导学生理解关系的定义并总结出其特点。关系的运算关系的并、交、差、余等运算。讲授方法：通过引导学生思考子关系的定义基础上，给出关系的并、交、差、余的运算。注：（1）集合的并、交、差、余运算性质对关系运算也成立。（2）作为关系时，余运算是对全域关系而言的，即AB作为全集E。关系的性质自反性；对称性；传递性；反自反、反对称及递讲授方法：在讲关系的性质时，可以引入一些日常生活中的实例让学生理解关系的性质。2．关系的乘法关系的乘法定义及定理1.2.1至1.2.43．关系的闭包。关系的闭包定义及求解方法（定理1.2.5）4．等价关系等价关系、等价类的定义；商集的定义；等价关系、等价类的计算（求解即定理1.2.6至1.2.8）讲授方法：通过1.2.2至1.2..5等例子来讲解。让学生逐步理解等价关系、等价类和商集的定义，并求解集合上等价关系和等价类，引导学生思考定理的局限性。5．部分序关系。部分序关系的定义及部分序集的定义集合的最大、最小元素、极大、极小元素部分序集的哈斯图的画法讲授方法：通过具体的例子来讲解该部分内容。作业安排：教材中习题1.2中的第9、10题。答疑时间：另行安排5授课题目1．3映射授课学时4授课时间第3、4周教学重点、难点：1．掌握映射、映像、1-1映射等概念，会做映射的乘积。2．了解可数集合的概念，掌握可数集合的判定方法。教学难点：1．判断集合的可数、不可数2．证明集合的可数、不可数教学要点：1．映射的基本概念映射的定义；单射、满射的定义；1-1映射的定义；映射的复合定义；逆映射的定义；讲授方法：通过大量的示意图来让学生理解这些基本概念。2．集合的基数集合基数的定义，表示形式；两个集合基数相等的定义；集合间基数的比较；讲授方法：本部分内容的讲解可以结合一些具体的例子特别是自然数，学生较好理解。3．可数集合可数集合的定义；判断集合可数的方法；讲授方法：通过给出可数集合的概念，以及讲解定理证明的过程，引导学生逐步掌握集合可数的判断方法。4．不可数集合不可数集合的定义；判断集合不可数的方法；讲授方法：通过定理1.3.6证明过程的讲解，让学生掌握康托尔对角线法；通过定理1.3.8的证明过程讲解，引导学生逐步掌握构造性证明方法，以及反证法的应用。5．本章内容小结参考文献：《离散数学学习指导与习题解答》孙吉贵等高等教育出版社《离散数学——精讲·精解·精练》黄健斌西安电子科技大学出版社《集合论与图论》耿素云北京大学出版社作业安排：教材中习题1.3中的第1、2题。答疑时间：另行安排6授课题目2.1命题以及逻辑联结词授课学时1.5授课时间第4周教学重点：掌握命题、简单命题、复合命题的概念，掌握命题真假的判断方法教学难点：理解蕴涵命题为真为假的前提条件教学要点：1．命题的基本概念。命题的定义；理解和掌握简单命题和复合命题；讲授方法：首先给出定义，然后通过例子理解和掌握定义，并且要求学生区分出简单命题和复合命题。2．命题的真值命题的真值有两种：0（假），1（真）讲授方法：首先要求学生明确定义，然后给出一些命题要求学生判断真假值。从而让学生进一步明确命题的定义（引申）。3．常用的联结词联结词的定义：五种常用的联结词符号：（否）（析取）（合取）（蕴含）（等价）联结词的运算表联结词的运算优先级联结词的含义以及自然语言描述参考文献：《离散数学学习指导与习题解答》孙吉贵等高等教育出版社《离散数学——精讲·精解·精练》黄健斌西安电子科技大学出版社作业安排：教材中习题2.1中的第3题。答疑时间：另行安排7授课题目2.2命题公式授课学时2.5授课时间第4、5周教学重点：掌握命题公式的概念，理解命题公式的解释的定义教学难点：给定一个公式，判定其是否为恒真公式或恒假公式教学要点：1．公式的基本概念。原子的定义；命题逻辑中的公式定义；讲授方法：给出命题逻辑中的公式定义，逐步引导学生领会递归定义的方法。2．解释的定义解释的定义；例子；讲授方法：回顾命题的相关知识，给出一个命题公式，进行赋值，判断其真、假值，引出解释的定义。3．真值表真值表的定义：真值表的画法；记住一个结论：n个不同原子的公式，共有2n个解释。讲授方法：通过一具体例子，教会学生会画真值表，并引导学生学会利用真值表来判断公式是否恒真、恒假、可满足。4．公式G恒真的定义；公式G恒假的定义；公式G可满足的定义。5．如何判断一个公式恒真、恒假、可满足。参考文献：《离散数学学习指导与习题解答》孙吉贵等高等教育出版社《离散数学——精讲·精解·精练》黄健斌西安电子科技大学出版社作业安排：习题2.2.4答疑安排：另行通知8授课题目2.3命题公式的等价关系和蕴涵关系授课学时4授课时间第5、6周教学重点：掌握命题公式的等价的相关概念；掌握命题公式蕴涵的相关概念；掌握演绎的相关概念和有关定理；掌握基本蕴涵式；理解公式蕴涵的证明方法。教学难点：公式蕴涵的证明方法；区别公式蕴涵和命题蕴涵的差异。教学要点：1．公式的等价相关概念。公式等价的定义；公式G、H等价的充要条件；基本等价式；完备集的定义以证明。讲授方法：给出公式等价的定义及一些基本等价式（要求学生通过上节课所学内容可以证明）。2．公式的蕴涵相关概念及相关定理公式的蕴涵的定义；公式G蕴涵公式H的充要条件；定理2.3.1讲授方法：通过一个例子给出公式蕴涵的定义（注意区别和=），给出定理2.3.1利用基本等价公式证明。3．演绎的相关概念及相关定理演绎的定义：引理定理2.3.2定理2.3.3一些基本蕴涵式4．公式蕴涵的证明方法讲授方法：通过回忆的方法逐一引导学生思考如何证明公式G蕴涵H。参考文献：《离散数学学习指导与习题解答》孙吉贵等高等教育出版社《离散数学——精讲·精解·精练》黄健斌西安电子科技大学出版社《离散数学》耿素云等高等教育出版社作业安排：习题2.3.1、8答疑安排：另行通知9授课题目2.4范式授课学时4授课时间第6、7周教学重点、难点：教学重点：1．析取范式、合取范式、极大项、极小项、主析取范式、主合取范式的概念和性质。2．掌握求各种范式的方法，能够用等价演算法和真值表法求命题公式的主析取范式、主合取范式。3．了解一个命题公式的主合取范式与主析取范式的关系。教学难点：1．命题公式的析取范式与合取范式的转化；2．命题公式恒真、恒假的判断。教学要点：1．范式的概念文字的定义；子句的定义；短语的定义。提醒学生注意：一个文字既可称为是一个子句，也可称为是一个短语。析取范式的定义；合取范式的定义提醒学生注意：一个文字既可称为是一个合取范式，也可称为是一个析取范式。一个子句，一个短语既可看做是合取范式，也可看做是析取范式。讲授方法：讲解时可以通过一个具体的例子来展示定义的内涵。对于任意命题公式，都存在等价于它的析取范式和合取范式。2．主析取范式和主合取范式极小（大）项的定义；结论：n个不同原子的公式，有2n个不同的极小（大）项。主析取范式的概念；主合取范式的概念。对于命题公式G，都存在等价于它的主析取范式。设公式G，H是关于原子P1，…，Pn的两个主析取范式。如果G，H不完全相同，则G，H不等价。对于任意公式G，存在唯一一个与G等价的主析取范式。讲授方法：讲解本部分内容可以做这样的教学设计：给出一个公式G，它的范式是不唯一的，能否有唯一的标准形式呢?（提出问题）答案是有（引导学生分析问题），引出主析取范式和主合取范式的概念。（解决问题）3．恒真恒假性的判定解决判定问题的方法：短语是恒假的当且仅当至少有一个原子及其否定(也称互补对)同时在此短语中出现。命题公式G是恒假的当且仅当在等价于它的析取范式中，每个短语均至少包含一个原子及其否定。把公式化成主析取范式：公式恒假时，主析取范式没有极小项；公式恒真时，主析取范式有全部极小项。一种判定算法：对任给要判定的命题公式G，设其中有原子P1，P2，…，Pn，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，Pn，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G恒假，若最终结果有1，有0，则是可满足的。4．本章内容小结作业安排：教材中习题2.4中的第4、5题。10授课题目3.1谓词逻辑的基本概念授课学时2授课时间第7周教学重点、难点：教学重点：谓词、全称量词、存在量词等概念，学会使用它们符号化一些命题并构成一些较复杂的命题。约束变量、自由变量的概念，能够正确使用改名规则。教学难点：n元谓词的理解；存在量词或全称量词限定的公式真值的理解教学要点：1谓词和量词谓词定义、量词定义量词限定公式的真值变量和命题函数中的变量区别量词的作用域教学方法：通过逻辑学中的著名的三段论案例，让学生理解命题逻辑的局限性，以及研究谓词逻辑的必要性，从而引出谓词逻辑的基本概念。2改名规则变量的约束与自由的含义改名规则教学方法：通过一些例子的练习让学生正确理解与掌握改名规则及其使用。参考文献：《离散数学学习指导与习题解答》孙吉贵等高等教育出版社《离散数学——精讲·精解·精练》黄健斌西安电子科技大学出版社《离散数学》耿素云等高等教育出版社作业安排：教材中习题3.1中的第3题。答疑时间：另行安排11授课题目3.2谓词公式授课