离散数学期末总复习总结.ppt

复 习 时 注 意 准确掌握每个概念 灵活应用所学定理 注意解题思路清晰 证明问题时,注意从定义入手的方式： （1）可以挖掘出隐含的背景条件 （2）定义的方式往往也揭示了问题解决的方式 总 复 习 复习重点 第一章 数理逻辑 A:命题逻辑 1.联结词的定义(含义及真值表定义). 2.命题符号化. 3.永真式的证明. 4.永真蕴涵式的证明,记住并能熟练应用常用公式. 5.等价公式的证明,记住并能熟练应用常用公式. 6.小项、大项、及（主）析/合取范式 7.熟练掌握构造证明的方法，并命题逻辑的三种推理方法. B: 谓词逻辑 1.准确掌握有关概念. 2.谓词符号化. 3.掌握常用的等价公式和永真蕴涵式.包括: 带量词的公式在论域内展开式,量词否定,量词辖域扩充量词分配公式. 4.会用等价公式求谓词公式的真值. 5.熟练掌握谓词逻辑推理. 第二章 集合论 1.集合的表示,幂集,全集,空集. 2.集合相等涵义及集合证明 第三章 二元关系 1.关系的概念,表示方法. 2.二元关系的 性质的定义, 熟练掌握性质的判断及证明. 3.掌握关系的复合,求逆及闭包运算(计算方法及有关性质) 4.掌握等价关系的判断,证明,求等价类、划分和商集. 5.偏序关系的判断,会画Hasse图,会求一个子集的极小(大)元,最小(大)元,上界与下界,最小上界及最大下界. 第四章 函数 1.如何去定义一个函数 2.理解“集合”、“关系”、“函数”之间的联系 3.特殊函数类及其判断和证明. 3.会计算函数的复合(左复合),求逆函数.知道有关性质. 第六章 代数系统 1.深入理解代数系统的概念，在函数基础上掌握运算的定义. 2.熟练掌握二元运算的性质的判断及证明. 3.掌握代数系统的同构定义,会证明.了解同构性质的保持. 4.掌握半群,独异点及其相关性质. 5.熟练掌握群, 了解循环群. *第七章 格与布尔代数 * 1.掌握格的定义,及格的判断 第八章 图论 1.掌握图的基本概念.(特别注意相似的概念) 2.熟练掌握图中关于结点度数的定理. (会应用) 3.无向图的连通性的判定,连通分支及连通分支数的概念. 4. 赋权图中最短路径的查找 5.欧拉图和哈密尔顿图的判定 6.会求图的矩阵、掌握邻接矩阵、可达矩阵 6.欧拉图和汉密尔顿图. 7.会判定平面图, 掌握欧拉公式. 总 复 习 复习重点 第一章 数理逻辑 A:命题逻辑 1.联结词的定义(含义及真值表定义). 2.命题符号化. 3.永真式的证明. 4.永真蕴涵式的证明,记住并能熟练应用常用公式. 5.等价公式的证明,记住并能熟练应用常用公式. 6.小项、大项、及（主）析/合取范式 7.熟练掌握构造证明的方法，并命题逻辑的三种推理方法. A: 命题逻辑 1.联结词 定义了五大类逻辑联结词，分别是： (1) 否定“?” (2) 合取“∧” (3) 析取“∨” (4) 蕴涵“?” (5) 等值“?” 要熟练掌握这五个联结词在自然语言中所表示的含义以 及它们的真值表的定义。 ? ：否定 表示“不” ∧：合取 表示“不但…,而且...”“并且” ∨：析取 表示“或者－可兼取的或” ?：蕴涵 表示“如果…,则...” ?: 等价 表示“当且仅当”“充分且必要” 可以将这五个联结词看成五种“运算”。 联结词的定义(包括真值表和含义). 特别要注意： “或者”的二义性, 即要区分给定的“或”是“可兼取的或∨”还是“不可兼取的或 ”。 “?”的用法，它既表示“充分条件”也表示“必要条件”,即要弄清哪个作为前件,哪个作为后件. 2.会命题符号化. 例如 P:我有时间. Q:我上街. R:我在家. 表示P是Q的充分条件: 如果p,则Q. 只要P,就Q. P?Q 表示P是Q的必要条件: 仅当P,才Q. 只有P,才Q. Q?P 如果P,则Q;否则R. (P?Q)?(?P?R) 3.永真式的证明. 方法1.列真值表. (?R?(Q?R)??(P??Q))??P 方法2.用公式的等价变换,化简成T. 例如证明(?R?(Q?R)??(P??Q))??P是永真式. 证:上式??(?R?(?Q?R)??(P??Q))??P(P?Q??P?Q) ?(R?(Q??R)? (P??Q))??P (公式的否定公式) ?((R?(Q??R))? ((P??Q)??P) (结合律) ? ((R?Q)?(R??R))?((P??P)?(?Q??P) (分配律) ?