• / 43
  • 下载费用:10 金币  

《计算机科学导论(第2版)》第11章:离散结构.ppt

关 键 词:
《计算机科学导论(第2版)》第11章:离散结构.ppt
资源描述:
第11章 离散结构,本章要点:,◆离散结构的研究对象及主要内容 ◆数理逻辑与简单推理 ◆集合论基础知识 ◆代数结构 ◆图论基本知识 ◆离散概率 ◆数值分析特点与方法 ◆运筹学概念与步骤 ◆数学建模与计算机模拟的概念与步骤,11.1离散结构的研究对象及主要内容,1.研究对象 离散数量关系以及离散系统结构的数学模型以及建模方法 。 2.研究的主要内容传统离散数学包含的数理逻辑、集合论、代数结构和图论等四个部分,以及计算机应用对象的离散结构的研究,离散概率、运筹学、数值计算、数学建模与模拟等。,11.2 数理逻辑,1.命题逻辑 离散数量关系以及离散系统结构的数学模型以及建模方法 。 命题 在数理逻辑中,称能够分辨真假、但不能同时既真又假的陈述句为命题 。 原子命题 在命题中,有些命题是简单的陈述句,并且它们不能够被分成更为简单的陈述语句,这样的命题称为简单命题,或者原子命题。,11.2 数理逻辑,(2) 复合命题 一个简单命题再加上了一个表示否定的连接词形成的复合命题。简单命题与复合命题都可以用简单的英文字母来表示。 [例] 用Q表示命题:8是奇数!用P表示命题:李平不是学生。 构成复合命题的连接词 ① 否定连接词,记作“ ” ② 合取连接词,也称“与”,记作“∧” ③ 或取连接词,也称“或”,记作“∨” ④ 蕴涵连接词,也称“条件”,记作“→” ⑤ 等价连接词,也称“双条件”,记作“ ”,,,,11.2 数理逻辑,命题公式命题常元、命题变元与各种逻辑连接词组合形成的更为复杂的命题,就可以称为命题公式,又叫做合式公式。 命题常元 单个的已知命题(可以是具体的命题、常真命题、常假命题) 。 (2) 命题变元 不代表具体命题的、但是取值范围仍然为“真”与“假”或“1”与“0”的符号表示的命题 。,11.2 数理逻辑,等值演算 命题常元、命题变元与各种逻辑连接词组合形成的更为复杂的命题,就可以称为命题公式,又叫做合式公式。 重言式 如果对命题公式A中命题变元的一切指派,A的真值均为真,则称命题公式A为重言式,重言式又称永真式。 (2) 等价式 设A,B为两个命题公式,若等价式A B是重言式,则称A逻辑等价于B,或A与B是等值的,记作A B。A B不是命题公式。,,11.2 数理逻辑,命题推理 推理是从前提出发推出结论的思维过程,前提是已知的命题公式,结论是从前提出发应用推理规则推出的命题公式。 真值表法 等价证明法 构造证明法,11.2 数理逻辑,[例] 证明P∨Q和 Q的结论是P。 证明:只需证明(P∨Q)∧ Q→P是重言式。 ① 真值表法 按真值表的构造步骤,构造真值表如下:,,(P∨Q)∧,(P∨Q)∧,,,11.2 数理逻辑,[例] 证明P∨Q和 Q的结论是P。 证明:只需证明(P∨Q)∧ Q→P是重言式。② 等价证明法 (P∨Q)∧ Q→P (P∨ Q) ∨ Q ∨ Q)→P(P∨ Q)→PP∨Q ∨PT∨QT,,,,,,,,11.2 数理逻辑,[例]证明:p→r, q→s, p∨q ⇒ r∨s 。 证明:③ 构造证明法 1) p→r 前提 2) p∨r 1) 等价置换 3) r∨ p 2) 等价置换 4) r → p 3) 等价置换 5) p∨q 前提 6) p∨ q 5) 等价置换 7) p →q 6) 等价置换 8) r →q 4)7)假言三段论 9) q→s 前提 10) r →s 8)9)假言三段论 11) r∨s 10) 等价置换,,,,,,,,,,,,11.2 数理逻辑,2.谓词逻辑 是对简单命题做进一步的分解,分析命题内部的逻辑结构和命题间的内在联系,它是命题逻辑的扩充和发展。 个体词 原子命题中所描述的对象,是可以独立存在的客体,可以是具体的,也可以是抽象的。 谓词 用来描述个体词的性质或个体词之间关系的词。 量词 表示个体常元或变元之间数量关系的词称为量词。,11.2 数理逻辑,全称量词 全称量词表示“所有的”,“每一个”,“对任何一个”,“一切”,“任意的”。符号为“∀”。 (2) 存在量词 表示“存在着”,“有一个”,“至少有一个”,“存在一些”,“对于一些”,“某个”等。符号为“∃”。,,11.2 数理逻辑,[例] 将以下命题用谓词逻辑符号化。 (1) 所有的自然数都是大于零的。 (2) 没有不犯错误的人。 (3) 这个班有些学生请假了。 解:(1) 设A(x):x是自然数;B(x):x大于零。则原命题符号化为:∀x(A(x) →B(x))。 (2) 设A(x):x是人;B(x):x犯错误。 则原命题符号化为:∀x(A(x) →B(x))。
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:《计算机科学导论(第2版)》第11章:离散结构.ppt
链接地址:https://www.weizhuannet.com/p-10087910.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开