• / 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))。 (3) 设A(x):x是这个班的学生; B(x):x请假了。 则原命题符号化为:∃x(A(x)∧B(x))。,,11.2 数理逻辑,谓词推理 谓词逻辑推理是命题逻辑推理的推广。谓词逻辑的推理也是利用命题公式间的各种等价关系、蕴涵关系,通过一些推理规则,从已知命题公式推出一些新的公式。,11.3 集合论,1.集合的基本概念与运算 是对简单命题做进一步的分解,分析命题内部的逻辑结构和命题间的内在联系,它是命题逻辑的扩充和发展。 集合的概念与表示 事物汇集在一起组成的一个整体叫做集合,而这些事物就可以称为这个集合的元素或者成员。集合通常用大写的英文字母来标记。 表示一个集合的方法 列举法 :A={1,2,3,…,n,…} 描述法 :B={x|x是大于等于8的正整数},11.3 集合论,集合间关系 设A ,B是集合,如果B中的每个元素都是A中的元素,则称B是A的子集合,简称子集。这时也称B被A包含,或A包含B。 设A,B为集合,如果A  B且B  A,则称A与B相等,记作A=B 。 设A,B为集合,如果BA且B≠A,则称B是A的真子集。记作B A。 不含任何元素的集合叫做空集,记作。 给定集合A,由集合A的所有子集为元素组成的集合,称为集合A的幂集,记作P(A) 。 在一个具体问题中,如果所涉及的集合都是某个集合的子集,则称这个集合为全集,记作E(或U)。,11.3 集合论,集合运算 (1) 定义:设A与B为集合,A与B的并运算、交运算、差运算 - ,分别定义为,A∪B={x|(x ∈A) ∨(x ∈ B)}A∩B={x|(x ∈ A) ∧(x ∈ B)}A - B ={x|(x ∈ A) ∧(x B)} (2) 定义:设E为全集,A E,则A的补运算,记作~,定义为,~A=E -A={xx∈E∧xA} 或 ~A={xxA} (3) 定义:设A与B为集合,A与B的对称差,记作,定义为, AB=(A∪B)—(A∩B,11.3 集合论,2.关系与函数 笛卡儿积 (1) 序偶由两个元素x和y(允许x =y)按一定的顺序排列成的二元组叫做一个有序对(也称序偶),记作,其中x是它的第一元素,y是它的第二元素。有序对的特点: ①当x y时,。 ②两个有序对相等,即 = 的充分必要条件是x=u且y=v。,11.3 集合论,(2)笛卡儿积 设A,B为集合,用A中元素作为第一元素,B中元素作为第二元素,构成有序对,所有这样的有序对组成的集合叫做A和B的笛卡儿积,记作A×B。符号化表示为A×B={(x,y)|x∈A∧y∈B} [例] 有两个集合A={a,b},B={0,1,2},则A×B={,,,,,}B×A={,,,,,},11.3 集合论,二元关系 (1) 二元关系定义如果一个集合为空集或者它的元素都是有序对,则称这个集合是一个二元关系,一般记作R。对于二元关系R,如果有序对∈R,则记作x R y 。设A,B为集合,A×B的任何子集所定义的二元关系称作从A到B的二元关系,特别当A=B时,则叫做A上的二元关系。 3种特殊的关系:①其中之一就是空集,称做空关系。②另外两种就是全域关系EA和恒等关系IA。对任何集合A, EA={|x∈A∧y∈A}=A×A IA={|x∈A},11.3 集合论,(2) 关系的表示通常用关系图来表示一个关系。 [例] A={1,2,3,4},R={,,,,},可以画出如下的关系图。,11.3 集合论,(3) 关系的基本运算Dom(R)={x y(∈R)}Ran(R)={y | x(∈R)} ①F的逆记作:{|∈F}。 ②F与G的左复合记作F ◦G,F ◦G ={|z(∈G∧∈F)} ③F与G的右复合记作F ◦G,F ◦G ={|z(∈F∧∈G)},11.3 集合论,(4) 关系的性质 ①自反性 若对于任意x属于集合A,都有 ,那么,就说R在A上是自反的。 ②反自反性 若对于任意x属于集合A,都不存在 ,那么,就说R在A上是反自反的。 ③对称性 若对于任意x,y属于集合A,都有 ∧∈R ,那么,就称R为A上的对称关系。 ④反对称性 若对于任意x,y属于集合A,都不存在∈ R ,那么,就称R为A上的反对称关系。 例如A上的全域关系,恒等关系,空关系都是A上的对称关系。而恒等关系和空关系也是A上反对称关系。 ⑤传递性 若对任意的x,y,z都属于集合A,假如都存在 ∧ ∧ ,那么,就称R为A上的传递关系。,,,,,,,,,,,,11.3 集合论,(5) 两类重要的二元关系 ①等价关系设R为非空集合A上的二元关系,若R具有自反性、对称性和传递性,则称R为A上的等价关系。利用等价关系,可以对一些对象进行分类。例如,集合上的恒等关系即是等价关系。 ②偏序关系 设R为非空集合A上的二元关系,若R具有自反性、反对称性和传递性,则称R为A上的偏序关系,偏序关系可以记为≤。集合A和A上的偏序关系R一起叫做偏序集,记为(A,≤),如果有(a,b)∈R,可以表示为a≤b 。根据偏序关系可以画出关系图,通常称为哈斯图。,,,,,,,,,11.3 集合论,[例] 已知为偏序集,集合A={a,b, c,d,e,f},关系≤={(b,a),(d,b),(c,a), (e,c),(e,b),(d,a),(e,a)},画出≤关系的哈斯图。 解:按照偏序集哈斯图的规则,可以得到如下哈斯图。,,,,,,,,,,11.3 集合论,函数 (1) 函数的定义设F为二元关系,若对于任意的x,都存在惟一的让xFy成立,则称F为函数。对于任意函数F,如果都有xFy,则记做,并称y为F在x上的值。 (2) 函数的性质 设函数f :A→B ① 若对于任何的x1,x2∈A,x1≠x2,都有f(x1)≠f(x2),则称f是单射的。②若Ran(f)=B,则称f是满射。③若f既是满射的,又是单射的,则称f是双射的。,11.3 集合论,(3) 特殊函数 ①复合函数 设f是从集合A到集合B的函数,g是从集合B到集合C的函数,f和g的复合用f ◦g 表示为f ◦g ={(a,c)|a∈A∧c∈C∧b(b∈B)∧(a,b)∈f∧(b,c)∈g } ②反函数 设函数f是集合X到集合Y的一个双射函数。则f的反函数是集合Y到集合X的函数,对于∀y∈Y,都分派一个惟一的x∈X和它对应,使得f(x)=y 。f的反函数记作:f –1: Y→X,即f –1(y)=x。,11.4 代数结构,1.代数结构概述 运算的定义及性质 (以二元运算为例) 设S为集合,函数 f:S ×S→S 称为S上的二元运算,简称为二元运算。 二元运算的一些性质。 (1) 设  为S上的二元运算,如果对于任意的x,y∈S都有x y =y x,则称运算 在S上满足交换律。 (2) 设  为S上的二元运算,如果对于任意的x,y,z∈S都有 (x y)z =x (y z),则称运算  在S上满足结合律。 (3) 设  S上的二元运算,如果对于任意的x∈S有x x =x,则称运算  在S上满足幂等律。 (4) 设  和为S上两个二元运算,如果对于任意的x,y,z∈S,有x(y z) = (xy) (xz) (左分配律) (y z)x = (yx) (zx) (右分配律)则称运算对运算满足分配律。 (5) 设  和为S上两个可交换的二元运算,如果对于任意的x,y∈S,都有x (x y)=xx (x y)=x则称运算和满足吸收律。,11.4 代数结构,代数结构的定义 代数结构通常指由以下三个部分组成的数学结构: ① 一个非空集合S,称为代数结构的载体。 ② S上的若干运算。 ③ 一组刻画载体S上各运算所满足性质的公理。 通常,代数结构用一个多元序组来表示,其中,S是载体,Δ,*,…为各种运算。有时,S中地位比较特殊的元素(如幺元、零元、逆元)也会被列入这个多元组的末尾。 例如,以自然数集N为载体,“+”运算可以作为二元运算组成一个代数结构,记为。,11.4 代数结构,2.格与布尔代数 格有序集称为格(lattice),如果A的任何两个元素的子集都有上确界和下确界。通常,用a∨b表示{a,b}的上确界,用a∧b表示{a,b}的下确界。 分配格称格为分配格,如果它满足分配律,即对任意的a,b,c∈A,a∧(b∨c)=(a∧b) ∨(a∧c)a∨(b∧c)=(a∨b) ∧(a∨c) 有界格格称为有界格,如果A中既有上确界1,又有下确界0。则,0和1称为A的界。 有补格对于A中的一个元素a,如果有 a∨b =1,a∧b=0 则称b为a 的补元或补。记为a’。如果A中的每个元素都有补元,则有界格称为有补格。,11.4 代数结构,布尔代数代数系统称为布尔代数,如果 B满足以下条件: ① 运算∨,∧满足交换律。 ② ∨运算对∧运算满足分配律,∧运算对∨运算也满足分配律。 ③ B有∨运算幺元1和∧运算零元0、∧运算幺元0和∨运算零元1。 ④ 对B中的每一个元素a,均存在元素a’,使a∨a’=1, a∧a’=0,11.5 图 论,1.图基本概念 图的由来哥尼斯堡七桥问题,,11.5 图 论,图的基本概念 (1) 图的定义 定义:图(graph)G由三个部分所组成: ① 非空集合V(G),称为图G的节点集,其成员称为节点或顶点(nodes or vertices)。 ② 集合 E(G),称为图G的边集,其成员称为边(edges)。 I ③ 函数Ψ(G):E(G)→(V(G),V(G)),称为边与顶点的关联映射(associatve mapping)。,11.5 图 论,图的基本概念 当(u,v)用作有序偶对时,(V(G),V(G)) =V(G)  V(G),e称为有向边,e以u为起点,以v为终点, 图G称为有向图(directed graph);当(u,v)用作无序偶对时,(u,v) = (v,u),称e为无向边(或边),图G称为无向图(或图)。,,11.5 图 论,图的基本概念 (2) 节点的度 在无向图中,节点v的度(degree)d(v)是v作为边的端点的数目。在有向图中,节点v的出度d +(v)(out-degree)是以v作为有向边起点的数目,v的入度d -(v)(in-degree)是v作为有向边终点的数目。节点的度是v的出度与入度之和。,11.5 图 论,2.路径、回路及连通性 图G的顶点v1到顶点vl的拟路径(pseudo path)是指如下顶点与边的序列:v1 ,e1 ,v2 ,e2 ,v3 ,… ,v l -1 ,el-1 , v l 其中v1 ,v2 ,v3 ,… ,v l -1 ,v l为G的顶点,e1 ,e2 ,… ,e l -1 为G的边,且e i( i= 1,2, … ,l-1 )以v i及v i +1为端点,(对有向图G,ei以vi为起点,以v i +1为终点);拟路径的边数l-1称为该拟路径的长度。当e i( i= 1,2, …, l-1 )各不相同时,该拟路径称为路径(walk),又当v i(i = 1,2, … ,l)各不相同时(除v1与v1),则称此路径为通路(Path)。v1=v1的路径称为闭路径(closed walk);v1= v1的通路称为回路(circuit)。,,11.5 图 论,3.图的矩阵表示 关联矩阵,,11.5 图 论,3.图的矩阵表示 邻接矩阵,,11.6 离散概率,样本空间样本空间指的是概率试验的所有结果的集合,通常记为S。样本空间中的每个元素分别称为样本点。如果样本空间含有有限个或可数的离散的样本点,该样本空间就是离散样本空间。 事件离散样本空间S的任意子集,称为是S中的事件。 离散概率设S为概率试验E的离散样本空间,且试验的每个结果的可能性相同,如果A是与E相关的一个事件,则A出现的概率即为离散概率,记为: ,其中,|A| 表示事件A的样本点数,|S|表示离散样本空间S中样本点总数。,,,11.7 数值分析,数值分析的特点 具有数学的科学性、严谨性,还具有实践性与技术性。 数值分析方法 常用的数值计算方法有构造法、离散法、递推法及近似替代法。 数值分析工具MATLAB,,,11.8 运筹学,运筹学的特点 运筹学以一定的数学模型为基础,同时具有综合性、实效性、全局性等特征。 运筹学的研究步骤 (1) 根据求解问题的目标,对问题进行分析和表述,抽象出问题本质,并构造合适的数学模型。 (2) 用已有的或寻求新的解法,对模型进行求解。 (3) 从以上两个步骤得到的可行方案中选出系统的最优解法。 (4) 对选择的模型进行检验,有必要的话,对模型进行修正。 (5) 布置实施方案,在现实系统中加以应用。,,,11.9 数学建模与计算机模拟,数学建模与计算机模拟的概念 (1) 数学模型数学模型是对客观世界中的事物或过程进行抽象和提取,并利用数学的方法加以形式化描述的结果。 (2) 数学建模数学建模实际上就是在充分理解现实问题的基础上,建立数学模型的过程的总和。 (3) 计算机模拟计算机模拟也叫计算机仿真,它是以计算机科学、系统科学、控制理论、信息技术等相关领域知识为基础,以计算机为工具,利用系统模型对真实系统进行模拟实现,以达到对实际系统进行分析与研究的目的。 数学建模的步骤 数学建模与计算机模拟的关系,,,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

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

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

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

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

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

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

收起
展开