离散数学总结ppt课件.ppt

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