哈工程离散数学总结.ppt

演2红共享HARBINENGINEERINGUNERSIWEY离散数学总结a日题离散数学口离散数学(Discretemathematics口离散数学是以研究离散量的结构和相互间的关系为主要目标,其研究对象一般地是有限个或可数个元素,因此它充分描述了计算机科学离散性的特点。代数结构数理逻辑集合论图论离散数学的应用举例口关系型数据库的设计(关系代数)口表达式解析(树)口优化编译器的构造(闭包)口编译技术、程序设计语言(代数结构)口Lisp和Prolog、人工智能、自动推理、机器证明(数理逻辑)口网络路由算法(图论)口游戏中的人工智能算法(图论、树、博弈论)口专家系统(集合论、数理逻辑一知识和推理规则的计算机表达口软件工程—团队开发—时间和分工的优化(图论—网络、划分)口(各种)算法的构造、正确性的证明和效率的评估(离散数学的各分支)离散数学的学习要领口概念(正确)必须掌握好离散数学中大量的概念口判断(准确)根据概念对事物的属性进行判断口推理(可靠)根据多个判断推出一个新的判断数理逻辑一命题逻辑口命题、真值、简单命题与复合命题、命题符号化。口联结词:1,∧,V,→,口命题公式、求公式的赋值口真值表、公式的成真赋值和成假赋值口公式的类型:重言式、矛盾式、可满足式。口等值式与等值演算。口基本的等值式,其中含:双重否定律、幂等律、交换律、结合律、分配律、德摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。口与范式有关的概念:简单合取式、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式求给定公式范式的步骤(1)消去联结词→、X(若存在)。AB冷1AVBAB(AVB)∧(AV1B)(2)否定号的消去利用双重否定律)或内移(利用德摩根律)。11A分A1(∧B)分1AV1B1(A∨B)冷14AB(3)利用分配律:利用∧对∨的分配律求析取范式,V对∧的分配律求合取范式。A∧(BVC)分(A∧B)∨(A∧CAV(B∧C)分(AVB)∧(AVC)求公式A的主析取范式的方法与步骤方法一、等值演算法(1)化归为析取范式。(2)除去析取范式中所有永假的析取项。(3)将析取式中重复出现的合取项和相同的变元合并。(4)对合取项补入没有出现的命题变元,即添加如V1p)式,然后应用分配律展开公式方法二、真值表法(1)写出A的真值表。(2找出A的成真赋值。(3)求出每个成真赋值对应的极小项(用名称表示),按角标从小到大顺序析取求公式A的主合取范式的方法与步骤方法一、等值演算法(1)化归为合取范式。(2)除去合取范式中所有永真的合取项。(3)将合取式中重复出现的析取项和相同的变元合并。(4)对析取项补入没有出现的命题变元,即添加如∧1P)式,然后应用分配律展开公式方法二、真值表法(1)写出A的真值表。(2找出A的成假赋值。(3)求出每个成假赋值对应的极大项(用名称表示),按角标从小到大顺序析取