离散数学总结ppt课件.ppt

(DiscreteMathematics)离散数学是以研究离散量的结构和相互间的关系为主要目标,其研究对象一般地是有限个或可数个元素,因此它充分描述了计算机科学离散性的特点。(关系代数)表达式解析(树)优化编译器的构造(闭包)编译技术、程序设计语言(代数结构)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的推理规则附加前提证明法-一阶逻辑个体词(个体域、全总个体域),谓词(特性谓词),量词(全称量词、存在量词)命题符号化:当给定个体域时,在给定个体域内将命题符号化。当没给定个体域时,应在全总个体域内符号化。在符号化时,当引入特性谓词时,注意全称量词与蕴含联结词的搭配,存在量词与合取联结词的搭配。 逻辑有效式、矛盾式、可满足式 闭式的性质:在任何解释下均为命题。 对给定的解释,会判别公式的真值或不能确定真值。.