离散数学总复习,西工大离散复习.ppt

* 考试时间、地点 时间：2012年1月4日-1月10日 地点：??? * The End 好好复习，考出好成绩！ 感谢大家一个学期的配合及努力 同学们辛苦了~ PS:欢迎大家在四年后报考我的研究生 * * * * * * * {x}属于{x}-{{x}}是否正确 * 重点说明矩阵 * * * * * * * 教学相长，成语，出自《礼记·学记》：“是故学然后知不足，教然后知困。知不足然后能自反也，知困然后能自强也。故曰教学相长也。” 意为教和学两方面互相影响和促进，都得到提高。 离散数学总复习 2011/12/21 * 教学内容： 数理逻辑 集合 二元关系 函数 代数 图论 * 复 习 时 注 意 准确掌握每个概念 灵活应用所学定理 注意解题思路清晰（细节推不出来时，别忘了写解题思路） 证明问题时,先用反向思维(从结论入手)分析问题,再按正向思维写出证明过程. 如果是后面几章的证明，一般从定义入手。 * 第一章 数理逻辑-命题逻辑?? 知识点 1．命题的概念、表示方法 = 会将命题符号化 2. 联结词的逻辑意义 (含义及真值表定义). 3．命题公式的递归定义= 会用真值表计算命题公式 4．真值表的构造、命题公式等价的概念(P6)。 5．重言式与蕴涵式的定义、逻辑意义（P8）， 逻辑等价与逻辑蕴涵的意义和证明方法(P12)。 常用的逻辑等价公式和逻辑蕴涵公式(E和I)。 * 第一章 数理逻辑-命题逻辑? 知识点（续） 6．命题公式的对偶式(P12)、合取范式、析取范式、主合取范式、主析取范式。逻辑小项、逻辑大项。任给公式化为析取范式、任给公式化为主析取范式、任给公式化为合取范式、任给公式化为主合取范式(P16-P20)。 7．命题逻辑的证明：真值表、推理理论 常用推理规则：P规则、T规则(P26)。 * 命题逻辑重点 主析（合）取范式求取方法 命题逻辑推理方法： 直接证明方法 间接证明方法 反证法（逆反证明法） CP规则 归谬法 * 第一章 数理逻辑-谓词逻辑? 知识点 1.谓词与量词的概念与表示方法(P35) 2.谓词逻辑的合式公式与自然语言的翻译(P36-37) 3.谓词中变元约束（P38） 4.谓词逻辑的等价式和蕴含式（P43） 带量词的公式在论域内展开式,量词否定,量词辖域扩充, 量词分配公式. 5.推理理论(P49)，参看下页 * 谓词逻辑的推理方法 规则：US、UG、ES、EG、命题逻辑的规则 可使用的公式表：命题逻辑的等价式、蕴含式；谓词逻辑的常用等价式和蕴含式； 推理方法： 同命题逻辑 * 谓词逻辑重点 自然语言的形式化（注意量词如何加入和论述域） 谓词逻辑推理方法 * 知识点 1. 集合的基本概念与表示方法，全集与空集 2. 集合的运算:交并补差、环和(对称差)、环积、幂集 3. 集合的三种关系(包含,相等,真包含)的定义及证明. 4. 归纳法的证明方法 5. 序偶与笛卡尔积； 第二章 集合 * 集合相等、包含等关系的证明 幂集 归纳法的应用 集合的重点 * 知识点 1. 关系的概念、表示方法 ：关系矩阵、关系图（P93）； 2．关系的特性：自反、对称、传递（P94），关系闭包（P106） 3.关系的运算：合成关系、逆关系、闭包运算（P106）； 合成关系的矩阵表示 4．次序关系(偏序、拟序（反自反)、线序、良序)、偏序集、哈斯图（P112）。 5. 偏序集中特殊的元素（P113） 极小元、极大元 最小元、最大元 上界、下界 上确界、下确界 6. 集合的等价关系与等价类，R诱导的等价关系（P123） 7. 集合的划分与覆盖，划分的大小与等价关系的大小(P127) 第三章 二元关系 第三章 二元关系 * 关系的重点 偏序集的特殊元素（极小元、极大元等） 关系的性质的证明与判别（P94） 关系闭包的计算，R诱导的等价关系(P124) 划分与等价关系（A/R）、划分是等价关系的证明（P125） * 知识点 1．函数的概念，定义域、值域、定义域与前域的关系、值域与陪域的关系 2. 函数的类型：单射函数、满射函数、双射函数，会判断，会证明（P140） 3.复合函数、逆函数的概念，复合函数与关系复合的联系与区别，逆函数与逆关系的联系与区别。 合成函数fg满射、单射、双射，f,g分别是?(P141) 4. f诱导的等价关系，规范映射的定义 5. 置换的定义，置换的合成运算 第四章 函数 * 函数的重点 单射函数、满射函数、双射函数的判断 函数的运算(合成、逆运算等) f诱导的等价关系，规范映射 * 第六章 代数 知识点 代数系统、子