离散数学考研习题讲解.ppt

离 散 数 学 考研 复 习 复 习 时 注 意 准确掌握每个概念 灵活应用所学定理 注意解题思路清晰 证明问题时,先用反向思维(从结论入手)分析问题,再按正向思维写出证明过程. 总 复 习 复习重点 第一章 命题逻辑 1.联结词的定义(含义及真值表定义). 2.会命题符号化. 3.重言式的证明. 4. 等价公式的证明,记住并能熟练应用常用公式. 5.会写命题公式的范式, 能应用范式解决问题. 6.熟练掌握命题逻辑三种推理方法. 第二章 谓词逻辑 1.准确掌握有关概念. 2.会命题符号化.(如2.3题) 3.掌握常用的等价公式和重言蕴涵式.包括: 带量词的公式在个体域内展开式,量词否定,量词辖域扩充, 量词分配公式. 4.会用等价公式求谓词公式的真值.(如2.13) 5.会写前束范式 6.熟练掌握谓词逻辑推理. 第三章 集合论初步 1.集合的表示,幂集,全集,空集. 2.集合的三种关系(包含,相等,真包含)的定义. 3.集合的五种运算及相关性质. 4.应用包含排斥原理. 第四章 二元关系 1.关系的概念,表示方法. 2.二元关系的 性质的定义, 熟练掌握性质的判断及证明. 3.掌握关系的复合,求逆及闭包运算(计算方法及有关性质) 4.掌握等价关系的判断,证明,求等价类和商集. 5.偏序关系的判断,会画Hasse图,会求一个子集的极小(大) 元,最小(大)元,上界与下界,最小上界及最大下界. 第五章 函数 1.函数的定义. 2.函数的类型, 会判断,会证明. 3.会计算函数的复合(左复合),求逆函数.知道有关性质. 4.了解集合的特征函数. 第六章 代数系统 1.掌握运算的定义. 2.熟练掌握二元运算的性质的判断及证明. 3.掌握代数系统的同构定义,会证明.了解同构性质的保持. 4.了解半群,独异点,*环和*域的概念. 5.熟练掌握群,子群,交换群(会证明), 了解循环群. *6,子群的陪集, Lagrange定理及其推论,(会应用). *第七章 格与布尔代数 * 1.掌握格的定义,了解格的性质. * 2.会判断格,分配格,有补格和布尔格, * 3.重点掌握两个元素的布尔代数的性质(10个). * 4.会写两个元素的布尔表达式的范式.(实质是第一章的主析取和主合取范式). 第八章 图论 1.掌握图的基本概念.(特别注意同构的概念) 2.熟练掌握图中关于结点度数的定理. (会应用) 3.无向图的连通性的判定,连通分支及连通分支数的概念. 4.有向图的可达性,强连通,单侧连通和弱连通的判定.求强 分图,单侧分图和弱分图. 5.会求图的矩阵.有向图邻接矩阵的应用。 6.会判定欧拉图和汉密尔顿图. *7.二部图与匹配. *8.会判定平面图, 掌握欧拉公式，了解对偶图. 9.掌握树的基本定义,v和e间的关系式.会画生成树,会求最 小生成树.根树的概念,完全m叉树,会画最优树,*会 设计前缀码. 总 复 习 复习重点 第一章 命题逻辑 1.联结词的定义(含义及真值表定义). 2.会命题符号化. 3.重言式的证明. 4.重言蕴涵式的证明,记住并能熟练应用常用公式. 5.等价公式的证明,记住并能熟练应用常用公式. 6.会写命题公式的范式, *能应用范式解决问题. 7.熟练掌握命题逻辑三种推理方法. 第一章 命题逻辑 1.联结词 定义了六个逻辑联结词，分别是： (1) 否定“?” (2) 合取“∧” (3) 析取“∨” (4) 异或“ ” (5) 蕴涵“?” (6) 等价“?” 要熟练掌握这六个联结词在自然语言中所表示的含义以 及它们的真值表的定义。 ? ：否定 表示“不” ∧：合取 表示“不但…,而且...”“并且” ∨：析取 表示“或者－可兼取的或” ：异或 表示“或者－不可兼取的或” ?：蕴涵 表示“如果…,则...” ?: 等价 表示“当且仅当”“充分且必要” 可以将这六个联结词看成六种“运算”。 联结词的定义(包括真值表和含义). 特别要注意： “或者”的二义性, 即要区分给定的“或”是“可兼取的或∨”还是“不可兼取的或 ”。 “?”的用法，它既表示“充分条件”也表示“必要条件”,即要弄清哪个作为前件,哪个作为后件. 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)?