离散数学教学要求资料.docVIP

1、课程简介—本课程的教学内容简介、学习目标、重点、难点、学习要求等。 离散数学主要研究离散对象和它们之间的关系。它是现代数学的重要分支之一，是计算机科学的基础理论核心课程。离散数学的内容很广泛，包括数理逻辑、集合论、图论、代数结构积应用部分。它们来源于不同的数学分支，从不同的角度研究各种离散量之间的关系。 学习它目的是为计算机科学的数据结构、编译理论、操作系统、算法分析、人工智能等提供了必要的数学基础知识。 通过本课程的学习，期待各位学员对离散数学有一个较全面的概念，培养出抽象思维和严谨的逻辑推理能力。 学习要点 一、命题逻辑： 掌握命题、命题变元、联结词、复合命题等概念，能够将命题符号化；掌握命题公式、重言式、矛盾式、可满足式、公式真值表等概念，能够利用公式的真值表判断较简单的公式类型；掌握命题公式的等值式、*对偶式，命题公式的代入与置换等概念，能够利用基本等值式、代入规则和置换规则进行等值演算；掌握命题公式的逻辑蕴涵式、逆换式、反换式、逆反式等概念，对于较简单的A和B，能够判断是否成立，*能够用基本的逻辑蕴涵式推证更复杂的逻辑蕴涵式；掌握全功能联结词集合的概念，能够判断一个联结词集合是否为全功能联结词集合，*会求最小联结词集合；掌握范式、极小（大）项、主范式的概念和性质，掌握求各种范式的方法，*能够用等值演算法和真值表法求命题公式的主范式，熟悉一个命题公式的主合取范式与主析取范式的关系——如何根据一种主范式立刻写出另一种主范式； *掌握形式证明、前提引入规则、结论引入规则、置换规则、代入规则、蕴涵证明规则等概念，能够根据推理规则以及一些基本等值式和逻辑蕴涵式，利用直接法和间接法作有效推理，并最终得到一个有效的结论。 二、谓词逻辑： 掌握个体、个体变量、个体域、谓词、全称量词、存在量词等概念，并学会利用它们符号化一些命题和构成一些较复杂的命题；掌握谓词公式的正确概念，理解约束变量和自由变量的形式和意义；正确使用约束变量的改名规则和自由变量的代入规则；掌握谓词公式的永真、等价、蕴含等概念，并能比较与命题公式演算中同样的概念及其异同；能用定义证明几个定理中给出的各个含有量词的等价关系式和蕴涵关系式；能记住主要的等值式，即量词否定等值式、量词作用域扩张与收缩等值式、量词分配等值式、在有限个体域内消去量词等值式；能使用约束变量和自由变量改名规则进行等值演算，掌握前束范式的概念以及把谓词公式化成与之等价的前束范式的方法；掌握谓词演算中推理的概念，并能利用正确的方法判断一个推理过程是否正确。 三、集合与关系： 掌握集合、子集、全集、空集等概念；熟悉常用的表示集合的方法以及用文氏图表示集合的方法；能判定元素与集合、集合与集合之间的关系；懂得两个集合之间的相等关系和包含关系的定义及性质，能够利用定义证明两个集合相等；掌握集合的五种基本运算：并、交、补、差和对称差，并熟记集合运算的基本等式，能够利用它们来证明更复杂的集合等式；掌握幂集的定义，以及计算有限集的幂集所含元素个数所使用的方法和思想；掌握序偶和迪卡尔积的概念；了解抽屉原理，熟记简单情形的容斥原理；理解划分与覆盖的概念，清除两者之间的差异。 掌握二元关系的形式定义及其各种表示方法：序偶、矩阵、关系图等；能准确使用集合表示式、关系矩阵、关系图等表示给定的关系，并要求能从一种形式写出另一种形式；掌握关系的运算，包括集合运算以及关系的复合和关系的逆运算；掌握二元关系的各种特殊性质：自反、反自反、对称、反对称、传递等，并理解这些性质如何反映在关系图上、关系矩阵上等；掌握集合中二元关系闭包的意义和简单性质，能求出优限集上的二元关系的闭包；掌握等价关系、相容关系的概念（重点是等价关系），并掌握覆盖、划分、等价类、商集的定义和基本性质，弄清楚等价关系与划分之间的关系；掌握偏序、偏序集、全序、良序等概念，以及偏序集的极大元、极小元、最大元、最小元、上界、下界、最大下界、最小上界等概念；能画出有限偏序集的哈斯图，并根据图讨论偏序集的某些性质。 四、函数：要求掌握函数的基本概念，弄清楚单射、满射和双射之间的区别；给定一个函数，要求能够确定它是否是单射、满射和双射；掌握复合函数和反函数的定义，弄清楚它们存在的条件；理解集合的象及原象的定义及相关性质；给定一个函数，能确定一点的象，一个集合的象，一个集合的原象及两个函数的复合等；掌握集合的势、可数集、不可数集的概念。 五、代数结构： 掌握代数系统的概念，对于运算的封闭性、单位元、零元、逆元等幂元的定义及相关的结论有清晰的理解；给定集合和集合上的运算表确定单位元、零元、逆元等（如果存在的话）。对于交换律、结合律、分配律、吸收律等的表示要十分清楚；给定集合及二元运算表，能够判断运算是否满足交换律、是否满足结合律；掌握代数系统的同态与同构的定义；能