哈工建离散数学总结.ppt

离散数学 离散数学(Discrete Mathematics) 离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。 离散数学的应用举例 关系型数据库的设计(关系代数) 表达式解析(树) 优化编译器的构造(闭包) 编译技术、程序设计语言(代数结构) Lisp和Prolog、人工智能、自动推理、机器证明(数理逻辑) 网络路由算法(图论) 游戏中的人工智能算法(图论、树、博弈论) 专家系统(集合论、数理逻辑—知识和推理规则的计算机表达) 软件工程—团队开发—时间和分工的优化(图论—网络、划分) (各种)算法的构造、正确性的证明和效率的评估(离散数学的各分支) 离散数学的学习要领 概念（正确）必须掌握好离散数学中大量的概念 判断（准确）根据概念对事物的属性进行判断 推理（可靠）根据多个判断推出一个新的判断 数理逻辑－命题逻辑 命题、真值、简单命题与复合命题、命题符号化。 联结词：┐，∧，∨，→，?。 命题公式、求公式的赋值。 真值表、公式的成真赋值和成假赋值。 公式的类型：重言式、矛盾式、可满足式。 等值式与等值演算。 基本的等值式，其中含：双重否定律、幂等律、交换律、结合律、分配律、德·摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。 与范式有关的概念：简单合取式、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式。 求给定公式范式的步骤 (1)消去联结词→、?(若存在)。A→B ? ┐A∨BA?B ? (┐A∨B)∧(A∨┐B) (2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。┐┐A ? A┐(A∧B) ? ┐A∨┐B┐(A∨B) ? ┐A∧┐B (3)利用分配律：利用∧对∨的分配律求析取范式， ∨对∧的分配律求合取范式。A∧(B∨C) ? (A∧B)∨(A∧C)A∨(B∧C) ? (A∨B)∧(A∨C) 求公式A的主析取范式的方法与步骤 方法一、等值演算法 (1)化归为析取范式。 (2)除去析取范式中所有永假的析取项。 (3)将析取式中重复出现的合取项和相同的变元合并。 (4)对合取项补入没有出现的命题变元，即添加如(p∨┐p)式，然后应用分配律展开公式。 方法二、真值表法 (1)写出 A 的真值表。 (2)找出 A 的成真赋值。 (3)求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取。 求公式A的主合取范式的方法与步骤 方法一、等值演算法 (1)化归为合取范式。 (2)除去合取范式中所有永真的合取项。 (3)将合取式中重复出现的析取项和相同的变元合并。 (4)对析取项补入没有出现的命题变元，即添加如(p∧┐p)式，然后应用分配律展开公式。 方法二、真值表法 (1)写出 A 的真值表。 (2)找出 A 的成假赋值。 (3)求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序析取。 数理逻辑－命题逻辑 推理的形式结构?推理的前提?推理的结论?推理正确 判断推理是否正确的方法?真值表法?等值演算法?主析取范式法 ? 对于正确的推理，在自然推理系统P中构造证明 ?自然推理系统P的定义?自然推理系统P的推理规则?附加前提证明法?归谬法 数理逻辑－ 一阶逻辑 个体词（个体域、全总个体域），谓词(特性谓词)，量词（全称量词、存在量词） 命题符号化： 当给定个体域时，在给定个体域内将命题符号化。 当没给定个体域时，应在全总个体域内符号化。 在符号化时，当引入特性谓词时，注意全称量词与蕴含联结词的搭配，存在量词与合取联结词的搭配。? 逻辑有效式、矛盾式、可满足式? 闭式的性质：在任何解释下均为命题。? 对给定的解释，会判别公式的真值或不能确定真值。 数理逻辑－一阶逻辑 深刻理解重要的等值式，并能熟练地使用它们。 熟练地使用置换规则、换名规则和代替规则。 准确地求出给定公式的前束范式（形式可以不唯一）。 正确地使用UI、UG、EI、EG规则，特别地要注意它们之间的关系。 一定对前束范式才能使用UI、UG、EI、EG规则，对不是前束范式的公式要使用它们，一定先求出公式的前束范式。 记住UI、UG、EI、EG规则的各自使用条件。 在同一推理的证明中，如果既要使用UI规则，又要使用EI规则，一定要先使用EI规则，后使用UI规则，而且UI规则使用的个体常项一定是EI规则中使用过的。 对于给定的推理，正确地构造出它的证明。 集合论－集合代数 掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示。 B ? A ? ?x (x∈B → x∈A) ? B ? A ? ?x (x?B ?