授课题目 授课学时 2 3.2 谓词公式 授课时间 第8周 教学重点、难点： 教学重点： 谓词公式、解释的概念，能够求出一给定公式在某一解释下的真值。 恒真公式、恒假公式、可满足公式等概念，了解与命题逻辑判定问题可解不同的是：谓词逻辑判定问题不可解，但谓词逻辑是半可判定的。 教学难点： 函数符号的理解 谓词公式的解释 教学要点： 1 谓词公式 四种符号：常量符号、变量符号、函数符号、谓词符号 项的定义 公式的定义 教学方法：通过例子进一步理解谓词逻辑的递归定义，让学生分析对比这些概念与命题逻辑中相关知识的区别与联系，从而提高分析问题解决问题的能力 2 解释 解释的定义 解释包含的内容与形式结构 公式的恒真、恒假以及可满足的定义 教学方法：通过一些具体案例的讲解也可结合实际应用问题进行讲解，让学生领会解释的实际含义，并学会对具体公式给出满足或弄假公式的解释 参考文献： 《离散数学学习指导与习题解答》 孙吉贵等 高等教育出版社 《离散数学——精讲·精解·精练》 黄健斌 西安电子科技大学出版社 《离散数学》 耿素云等 高等教育出版社 作业安排： 教材中习题3.2中的第2、3题 答疑时间：另行安排
11
授课题目 授课学时 2 3.3 谓词公式的等价关系和蕴含关系 授课时间 第8周 教学重点、难点： 教学重点： 谓词公式的等价、蕴涵等概念，熟记基本的等价式、蕴涵式，会证明更复杂的等价式、蕴涵式。 教学难点： 谓词演算的推理方法的掌握 教学要点： 1谓词公式的等价关系 谓词公式等价的定义 谓词公式等价的充要条件 教学方法；通过例子的讲解使学生能够分析对比谓词公式等价与命题公式等价的区别和联系，从而加深学生对问题的理解 2谓词公式的蕴涵关系 谓词公式蕴涵的定义 谓词公式蕴涵的充要条件 基本蕴涵式 教学方法；通过三段论例子的进一步讲解使学生能够分析对比谓词公式蕴涵与命题公式蕴涵的区别和联系，从而加深学生对问题的理解，并看到谓词逻辑的不足，引导和启发学生深入思考一些相关问题 3谓词演算的推理方法 谓词演算规则 演算规则的使用 规则错误使用的识别 教学方法；通过例子的讲解过程使学生掌握这些规则和推理方法的具体运用，并能够识别推理过程中的规则使用错误 参考文献： 《离散数学学习指导与习题解答》 孙吉贵等 高等教育出版社 《离散数学——精讲·精解·精练》 黄健斌 西安电子科技大学出版社 《离散数学》 耿素云等 高等教育出版社 《数理逻辑》 王捍贫 北京大学出版社 作业安排： 教材中习题3.3中的第1题。 答疑时间：另行安排
12
授课题目 授课学时 2 3．4 范 式 授课时间 第9周 教学重点、难点： 教学重点： 1．掌握前束范式、Skolem范式等概念； 2．掌握将谓词公式化成与之等价的前束范式，并进一步化为Slolem范式。 教学难点： 公式与其Slolem范式可满足性的等价性证明。 教学要点： 1．范式的概念 前束范式的定义； 等价公式； 对任意公式G，都存在与其等价的前束范式； 改名公式在谓词逻辑中的应用； 公式的等价前束范式求解方法； 教学方法：在讲解本部分内容时要注意提出问题，引导学生去思考求解问题的方法。例如为什么提出改名，它的意义在哪里？ 2．Skolem范式的概念 Skolem范式的定义及理解； 公式G的Skolem函数定义； 设S是公式G的Skolem范式，于是，公式G是恒假的充要条件是公式S是恒假的； 公式G与它的Skolem范式S可满足性是等价的； 教学方法：在讲解本部分内容时要注意提出问题，引导学生去思考求解问题的方法。例如为什么提出Skolem范式？它的意义在哪里？是否存在更好的解决方案？最后让学生了解谓词逻辑在计算机科学中的应用。 3．本章内容小结 参考文献： 《离散数学学习指导与习题解答》 孙吉贵等 高等教育出版社 《离散数学——精讲·精解·精练》 黄健斌 西安电子科技大学出版社 《离散数学》 耿素云等 高等教育出版社 《数理逻辑》 王捍贫 北京大学出版社 作业安排： 教材中习题3.4中的第2、3题。 答疑时间：另行安排
13
授课题目 授课学时 4 4．1 图 授课时间 第9、10周 教学重点、难点： 教学重点： 1．掌握图的概念。 2．理解Dijkstra算法，并能够在已知权图中使用该算法求出任意两点间的最短路 教学难点： Dijkstra算法的正确性证明。 教学要点： 1．图的概念 图的定义； 子图的定义； 图的矩阵表示：相邻矩阵和关联矩阵； 有限图中点的度； 教学方法：在讲解本部分内容时多举例子，让学生对于图有一个直观的理解。 2．权图和Dijkstra算法 权图的定义； Dijkstra算法； Dijkstra算法的执行过程； Dijkstra算法的正确性证明； 教学方法：在讲解本部分内容时要注意提出问题，引导学生去思考算法的本质。例如Dijkstra算法 的原理是什么？它主要适合那些问题？有没有更好的方法？并鼓励学生通过编程实现算法加深对于算法的理解。 参考文献： 《离散数学学习指导与习题解答》 孙吉贵等 高等教育出版社 《集合论与图论》 耿素云 北京大学出版社 《网络优化》 谢金星 邢文训 清华大学出版社 作业安排： 教材中习题4.1中的第7题。 答疑时间：另行安排
14
授课题目 授课学时 4 4．2 树 授课时间 第10、11周 教学重点、难点： 教学重点： 1．掌握树、支撑树的概念以及图是树的几个等价命题。 2．理解Kruskal算法，并能够应用它求已知加权连通图的最优树。了解求最优树的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算法 最优树定义及理解； Kruskal算法； Kruskal算法的正确性证明； 了解求最优树的其他算法 教学方法：在讲解本部分内容时要注意提出问题，引导学生去思考求解问题的方法。在讲授Kruskal算法的时候注意让学生理解算法的原理，并剖析其“闭圈法”的本质，同时鼓励学生上机编程实现。 参考文献： 《离散数学学习指导与习题解答》 孙吉贵等 高等教育出版社 《集合论与图论》 耿素云 北京大学出版社 《网络优化》 谢金星 邢文训 清华大学出版社 作业安排： 教材中习题4.2中的第4题。 答疑时间：另行安排
15