《离散数学[C》课程教学大纲.doc

《离散数学[C]》教学大纲课程编【英文译名】：Discrete Mathematics 【适用专业】：信息管理与信息系统 一般离散数学课程包括数理逻辑、集合论、图论、代数结构等几个部分。数理逻辑的重点是公式演算与推理证明；集合论的重点是关系理论与映射的描述；图论着重于数形结合的描述以及各种实际应用；代数结构则主要是从系统宏观的代数方法去研究客观事物的各种性质与特征。 三、本课程与其他课程的关系 离散数学是一门体系独立自行封闭的基础数学课程，但为了论述方便，此课程应安排在高等数学与线性代数课程之后。为了加强离散结构方法的训练，在讲授本课程的基础上，可讲授数据结构、数据库原理，这样对于集合和图论的应用能够加深理解，温故而知新。另外离散数学与计算机网络与通信，以及计算机系统结构等课程关系紧密，是本专业其它专业基础和专业课的先修课。 四、课程内容 一 命题演算（8学时） 主要内容： 1.命题概念 2.基本联合词与复习命题 3.合式公式与联合词优先次序 4.命题公式的等价变换、命题符号化 5.构造真值表证明等价式 6.不构造真值表证明蕴含式 7.范式与主范式 8.应用P、T规则的推理证明 9.CP规则与间接推理证明 基本要求： 数理逻辑的任务是采用数学方法研究抽象的思维规律，研究的中心问题是推理，而推理基本要素是命题，故学习本章首先要深刻理解命题的概念。理解原子命题与复合命题的关系，在了解复合命题的基础上，理解联结词的定义。命题演算中两个重要内容是命题公式的范式表示与命题的推理理论，前者主要是命题公式化简与主范式表示，后者则需要熟悉直接推理与间接推理两种方法。 重点：命题概念及其表示、命题公式化简、主范式及其互化、P规则、T规则以及CP规则。难点：推理理论及应用。 教学要点： １．掌握： 命题、逻辑联结词的概念；公式与解释的概念，公式的递归定义，用基本等价式化简其他公式；主析取范式及其唯一性，用真值表法判断公式的类型；公式蕴涵与逻辑结果的概念；推理理论及应用。 ２．理解：用联结词产生复合命题的方法；公式在解释下的真值；公式范式的概念；形式演绎和蕴涵的关系。 二 谓词演算（4学时） 主要内容： 1.谓词概念 2.量词及合式公式 3.谓词演算的等价式与蕴含式 4.谓词演算的推理理论 基本要求： 谓词演算是命题演算的继续和深入，它不仅研究命题间的逻辑结构，而且要考察命题间的内部性质。在命题演算中，基本主成单位是原子命题并且把它看成是不可分解的。在谓词演算中，对于命题的内部逻辑结构作了进一步刻画分析，在此引进了客体和谓词概念。在讨论谓词公式中引入量词及其辖域的概念，对于带量词的谓词公式，也存在公式变换和推理理论。 本章的重点是带量词的公式变换，即前束范式。难点是谓词演算的推理理论。本章在重点讲解清楚谓词概念情况下，对带量词的蕴含，等价公式表只作解释性推论。 重点：带量词的公式变换，即前束范式。 难点：谓词演算的推理理论。本章在重点讲解清楚谓词概念情况下，对带量词的蕴含，等价公式表只作解释性推论。 教学要点： １．掌握：个体词、个体域、谓词、量词的概念和使用；原子、公式、解释的概念；公式在解释下的真值；求公式的前束范式；谓词演算的推理理论． ２．理解：用谓词、量词、逻辑联结词描述一个简单命题；公式的递归定义；用解释的方法证明等价式和蕴涵式。 ３．了解：以谓词逻辑为工具，将命题符号化。 三 集合与二元关系（8学时） 主要内容： 1.集合概念与运算 2.关系概念与运算 3.关系表示法与性质 4.关系矩阵与闭包 5.等价关系与划分 6.序关系 基本要求： 集合论式现代各学科数学的基础。本章从集合概念出发，引出了关系的种运算性质，即等价关系与序关系等。 集合代数的运算与逻辑代数性质相对应。这为以后代数系统的讨论做出准备。 重点：关系运算及分类，还有相容关系，等价关系与序关系等有关性质。 难点：关系闭包概念及求法，这里将略去复杂的证明。映射的一些定理证明，亦从略。 教学要点： １．掌握：子集、空集、全集、相等、幂集等基本概念；集合的表示法；集合的交、并、差、补等概念；交换律、结合律、分配律、De Morgan律等运算律，证明集合等式；序偶与迪卡尔积的概念和应用；关系的概念；关系的性质；自反闭包、对称闭包、传递闭包的概念；等价关系与等价类的概念，划分的有关概念；偏序关系、偏序集的概念及用哈斯图表示；函数的概念。 ２．理解：文氏图；关系矩阵与关系图；复合关系与逆关系的概念及求法；单射、满射、双射的概念；复合函数与反函数的概念。 ３．了解：序关系与序集的概念。 四 图 论（10学时） 主要内容： 1.图的基本概念 2.图的连通性