2013-2014年《离散数学》复习要点.pdf

关于离散数学的复习 复 习 范 围 第一部分：数理逻辑 1. 命题概念，连接词，真值表，矛盾式、重言式、可满足式，（主析取、主合取）范式、极大项、 极小项 2. 谓词逻辑，存在量词、全称量词，自由变元、约束变元、作用域、解释 3. 逻辑推理 第二部分：二元关系 1. 关系的定义、序偶，关系的图表示、矩阵表示 2. 关系的特性、自反、对称、传递、反自反、反对称 3. 关系的基本运算、闭包计算、逆运算 4. 等价关系、等价类，偏序关系、特殊元界计算、哈斯图、整除关系 第三部分：图论 1. 图论基本概念，连通、通路、回路，握手定理，节点、分支、层数之间的关系，（n 元）完全树、 节点分支层数之间的关系、哈夫曼树、前缀码 2. 特殊图的概念和判定，欧拉通（回）路、哈密顿通（回）路、平面图、偶图的概念和判定 第四部分：代数系统 1. 代数系统的概念和判定、各种元（幺元、逆元）的计算、周期元、生成元 2. （半）群、子（半）群、陪集、商群、交换群 3. 无限群和有限群，n 模加群 复习方法 1、确实掌握基本概念，这门课程概念极其重要，所有概念都是从现有的初等数学中抽象出来，因此概 念记住了，结合技巧的叙述方法，应该就是这些。 2、围绕课本相关例题，确实掌握基本计算方法。 3、可以考虑花点时间将书本课程范围所有概念（定义）、重要定理写在一写小纸片上做成卡片之类的， 随身携带，或做成图片放在手机上，任何空闲无聊的时间随时拿出来看上一眼，想上一想，就记住了。 第三章：命题逻辑 重要概念： 命题、原子命题、复合命题 五大命题联结词、其各自基本语义、与自然语言之间的对应关系 命题公式、常值命题、命题变量、原子命题变元 命题公式的解释与真值表、命题公式分类（永真、可满足、矛盾式）、命题公式的等价、代入定理、替 换定理 命题公式标准型：析取范式、合取范式、文字、子句、短语、主析取范式、主合取范式、极大项、极 小项 求取主析取范式和主合取范式的方法、它们之间的转换、真值表技术 第四章：谓词逻辑 重要概念： 谓词、个体常量、个体变量、个体域、全种个体域、n 元命题函数或 n 元谓词、量词、全称量词、存 在量词、作用变量、辖域、谓词符号化的两条规则、谓词的语言翻译、谓词合式公式、常量符号、变量符 号、函数符号、谓词符号、项、原子谓词公式、自由变元、约束变元、约束的改名规则、自由变元的代入 规则、封闭合式公式、解释、谓词合式公式的分类（有效公式、矛盾公式和可满足公式）、谓词合式公式的 等价关系、原子公式的代入实例、公式的标准型（范式）、前束范式、Skolem 标准型、前束范式和 Skolem 标准型的求解 第五章：推理和证明技术 重要概念： 命题逻辑的三个内容：概念、判断和推理 推理的前提、结论和有效推理 逻辑结果、有效的或无效的 判断有效结论的常用方法：真值表技术、推理定律、演绎法、间接证明法 演绎法中的P 规则、T规则和CP规则 谓词逻辑的推理理论 推理规则：US规则、ES规则、UG规则、EG 规则 第六章：二元关系 重要概念： 序偶、n元序偶、笛卡尔积；二元关系、空关系、全关系；定义域、值域 关系的表示：集合表示法、关系图表示法、邻接矩阵表示法 关系的运算：关系的集合运算、关系的复合运算、关系的逆运算、关系的幂运算 关系的性质：自反和反自反、对称和反对称、传递 关系性质的判定：图表示法中的判定、矩阵表示法中的判定 关系的闭包运算：自反闭包、传递闭包、对称闭包，及其运算方法（矩阵法、图示法） 第七章：特殊关系 重要概念： 等价关系：自反、对称、传递，集合的划分、覆盖，等价类、商集 次序关系：拟序关系、偏序关系、全序关系、良序关系 拟序关系：反自反和传递 偏序关系：自反、对称和传递，哈斯图 Hasse 构造，特殊元素：极大元素、最大元素、极小元素、最 小元素、上界、下界、上确界、下确界 全序关系：线序关系、链 良序关系：