计算机科学导论(第2版)第11章 离散结构

计算机科学导论 学习计算机专业的第一门基础课程 第 11章 离散结构 本章要点： 离散结构的研究对象及主要内容 数理逻辑与简单推理 集合论基础知识 代数结构 图论基本知识 离散概率 数值分析特点与方法 运筹学概念与步骤 数学建模与计算机模拟的概念与步骤 离散数量关系以及离散系统结构的数学模型以及建模方法 。 传统离散数学包含的数理逻辑、集合论、代数结构和图论等四个部分，以及计算机应用对象的离散结构的研究，离散概率、运筹学、数值计算、数学建模与模拟等。 理逻辑 离散数量关系以及离散系统结构的数学模型以及建模方法 。 命题 在数理逻辑中，称能够分辨真假、但不能同时既真又假的陈述句为命题 。 (1) 原子命题 在命题中，有些命题是简单的陈述句，并且它们不能够被分成更为简单的陈述语句，这样的命题称为简单命题，或者原子命题。 理逻辑 (2) 复合命题 一个简单命题再加上了一个表示否定的连接词形成的复合命题。 简单命题与复合命题都可以用简单的英文字母来表示。 例 用 8是奇数！ 用 平不是学生。 构成复合命题的连接词 否定连接词，记作“ ” 合取连接词，也称“与”，记作“ ” 或取连接词，也称“或”，记作“ ” 蕴涵连接词，也称“条件”，记作“ ” 等价连接词，也称“双条件”，记作“ ” 理逻辑 命题公式 命题常元、命题变元与各种逻辑连接词组合形成的更为复杂的命题，就可以称为命题公式，又叫做合式公式。 (1) 命题常元 单个的已知命题 (可以是具体的命题、常真命题、常假命题 ) 。 (2) 命题变元 不代表具体命题的、但是取值范围仍然为“真”与“假”或“ 1”与“ 0”的符号表示的命题 。 理逻辑 等值演算 命题常元、命题变元与各种逻辑连接词组合形成的更为复杂的命题，就可以称为命题公式，又叫做合式公式。 (1) 重言式 如果对命题公式 称命题公式 言式又称永真式。 (2) 等价式 设 A,等价式 A 称 ，或 是等值的，记作 A B。 A 理逻辑 命题推理 推理是从前提出发推出结论的思维过程，前提是已知的命题公式，结论是从前提出发应用推理规则推出的命题公式。 (1) 真值表法 (2) 等价证明法 (3) 构造证明法 理逻辑 例 证明 P 。 证明 ：只需证明 (P Q) QP 是重言式。 真值表法 按真值表的构造步骤，构造真值表如下： (P Q) (P Q) P Q P Q Q Q Q P 0 0 0 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 理逻辑 例 证明 P 。 证明 ：只需证明 (P Q) QP 是重言式。 等价证明法 (P Q) Q P (P Q) Q Q) P (P Q) P P Q P T Q T 理逻辑 例 证明： p r, q s, p q r s 。 证明 ： 构造证明法 1) pr 前提 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) qs 前提 10) r s 8)9)假言三段论 11) r s 10) 等价置换 理逻辑 是对简单命题做进一步的分解，分析命题内部的逻辑结构和命题间的内在联系，它是命题逻辑的扩充和发展。 个体词 原子命题中所描述的对象，是可以独立存在的客体，可以是具体的，也可以是抽象的。 谓词 用来描述个体词的性质或个体词之间关系的词。 量词 表示个体常元或变元之间数量关系的词称为量词。 理逻辑 (1) 全称量词 全称量词表示“所有的”，“每一个”，“对任何一个”，“一切”，“任意的”。符号为“ ”。 (2) 存在量词 表示“存在着”，“有一个”，“至少有一个”，“存在一些”，“对于一些”，“某个”等。符号为“ ”。 理逻辑 例 将以下命题用谓词逻辑符号化。 (1) 所有的自然数都是大于零的。 (2) 没有不犯错误的人。 (3) 这个班有些学生请假了。 解： (1) 设 A(x)： B(x)： 则原命题符号化为： x(A(x) B(x)。 (2) 设 A(x)： B(x)： 则原命题符号化为： x(A(x) B(x)。 (3) 设 A(x)： B(x)： 则原命题符号化为： x(A(x) B(x)。 理逻辑 谓词推理 谓词逻辑推理是命题逻辑推理的推广。谓词逻辑的推理也是利用命题公式间的各种等价关系、蕴涵关系，通过一些推理规则，从已知命题公式推出一些新的公式。 合论 是对简单命题做进一步的分解，分析命题内部的逻辑结构和命题间的内在联系，它是命题逻辑的扩充和发展。 集合的概念与表示 事物汇集在一起组成的一个整体叫做集合，而这些事物就可以称为这个集合的元素或者成员。 集合通常用大写的英文字母来标记。 表示一个集合的方法 (1) 列举法 ： A 1,2,3,n, (2) 描述法 ： B x|的正整数 合论 集合间关系 (1) 设 A ， 果 中的元素，则称 的子集合，简称子集。这时也称 包含，或 。 (2) 设 A， 果 A A，则称 相等 ，记作 A B 。 (3) 设 A， 果 BA，则称 的 真子集 。记作 B A。 (4) 不含任何元素的集合叫做 空集 ，记作 。 (5) 给定集合 A，由集合 为集合 集 ，记作P(A) 。 (6) 在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集 ，记作 E(或 U)。 合论 集合运算 (1) 定义： 设 为集合， 的并运算 、交运算 、差运算 - ，分别定义为， A B=x|(x A) (x B) AB=x|(x A) (x B) A - B =x|(x A) (x B) (2) 定义： 设 A E，则 作 ，定义为， A E xx E xA 或 A xxA (3) 定义： 设 为集合， 的对称差，记作 ，定义为， AB (A B)(AB 合论 笛卡儿积 (1) 序偶 由两个元素 x和 y(允许 x =y)按一定的顺序排列成的二元组叫做一个有序对 (也称序偶 )，记作 ，其中 有序对的特点： 当 x 。 两个有序对相等，即 的充分必要条件是 x u且 y v。 合论 (2)笛卡儿积 设 A， 成有序对，所有这样的有序对组成的集合叫做 的笛卡儿积，记作A B。符号化表示为 A B (x,y)|x A y B 例 有两个集合 A a,b， B 0,1,2，则 A B , B A , 合论 二元关系 (1) 二元关系定义 如果一个集合为空集或者它的元素都是有序对，则称这个集合是一个二元关系，一般记作 R。 对于二元关系 R，如果有序对 R，则记作 x R y 。 设 A,A 到 别当 A 叫做 3种特殊的关系： 其中之一就是空集 ，称做空关系。 另外两种就是全域关系 A。 对任何集合 A， x A y A A A x A 合论 (2) 关系的表示 通常用关系图来表示一个关系。 例 A=1,2,3,4， R=,，可以画出如下的关系图。 合论 (3) 关系的基本运算 ) x y( R) ) y | x( R) | F。 的左复合记作 F G， F G z( G F) 的右复合记作 F G， F G z( F G) 合论 (4) 关系的性质 自反性 若对于任意 ，都有 ，那么，就说 上是自反的。 反自反性 若对于任意 ，都不存在 ，那么，就说 上是反自反的。 对称性 若对于任意 x,，都有 R ，那么，就称 上的对称关系。 反对称性 若对于任意 x,，都不存在 R ，那么，就称 上的反对称关系。 例如 等关系，空关系都是 恒等关系和空关系也是 传递性 若对任意的 x,y,，假如都存在 ，那么，就称 上的传递关系。 ,x A x x R ,x A x x R ,x y A ,y x R ,y x R ,x y z A ,x y R ,y z R ,x z R 合论 (5) 两类重要的二元关系 等价关系 设 上的二元关系，若 称性和传递性，则称 上的等价关系。 利用等价关系，可以对一些对象进行分类。例如，集合上的恒等关系即是等价关系。 偏序关系 设 上的二元关系，若 对称性和传递性，则称 上的偏序关系，偏序关系可以记为 。集合 上的偏序关系 为 (A,)，如果有 (a,b) R，可以表示为 ab 。 根据偏序关系可以画出关系图，通常称为哈斯图。 合论 例 已知 为偏序集，集合 A=a,b, c,d,e,f，关系 =(b,a),(d,b),(c,a), (e,c),(e,b),(d,a),(e,a)，画出 关系的哈斯图。 解：按照偏序集哈斯图的规则，可以得到如下哈斯图。 合论 函数 (1) 函数的定义 设 对于任意的 x，都存在惟一的让 称 于任意函数 F，如果都有 记做，并称 在 (2) 函数的性质 设函数 f :AB 若对于任何的 x1,A， x1有 f(f(则 称 若 f) B，则称 若 是单射的，则称 合论 (3) 特殊函数 复合函数 设 到集合 到集合 f和 f g 表示为 f g =(a,c)|a A c C b(b B) (a,b) f (b,c) g 反函数 设函数 到集合 到集合 于 y Y，都分派一个惟一的 x 得 f(x)=y 。f 1: YX ，即 f 1(y)=x。 数结构 运算的定义及性质 （以二元运算为例） 设 数 f： S SS 称为 称为二元运算。 二元运算的一些性质。 (1) 设 为 果对于任意的 x,y x y =y x，则称运算 在 换律 。 (2) 设 为 果对于任意的 x,y,z (x y)z =x (y z)，则称运算 在 合律 。 (3) 设 果对于任意的 x S有 x x =x，则称运算 在 等律 。 (4) 设 和 为 果对于任意的 x,y,z S，有 x(y z) (xy) (xz) (左分配律 ) (y z)x (yx) (zx) (右分配律 ) 则称 运算 对运算 满足分配律 。 (5) 设 和 为 果对于任意的 x,y S，都有 x (x y) x x (x y) x 则称 运算 和 满足吸收律 。 数结构 代数结构的定义 代数结构通常指由以下三个部分组成的数学结构： 一个非空集合 S，称为代数结构的载体。 一组刻画载体 通常，代数结构用一个多元序组 来表示，其中， ，*， 为各种运算。有时， 如幺元、零元、逆元 )也会被列入这个多元组的末尾。 例如，以自然数集 +”运算可以作为二元运算组成一个代数结构，记为 。 数结构 格 有序集 称为格 (如果 常，用 a a,b的上确界，用 a a,b的下确界。 分配格 称格 为分配格，如果它满足分配律，即对任意的 a,b,c A, a (b c)=(a b) (a c) a (b c)=(a b) (a c) 有界格 格 称为有界格，如果 ，又有下确界 0。则， 0和 1称为 有补格 对于 a，如果有 a b =1， a b=0 则 称 b为 a 的补元或补。记为 a。 如果 有界格 称为有补格。 数结构 布尔代数 代数系统 称为布尔代数，如果 运算 ， 满足交换律。 运算对 运算满足分配律， 运算对 运算也满足分配律。 运算幺元 1和 运算零元 0、 运算幺元 0和 运算零元 1。 对 a，均存在元素 a，使 a a=1， a a=0 论 图的由来 哥尼斯堡七桥问题 论 图的基本概念 (1) 图的定义 定义： 图 (由三个部分所组成： 非空集合 V(G)，称为图 成员称为节点或顶点 (or 集合 E(G)，称为图 成员称为边 ( I 函数 (G):E(G)(V(G) ， V(G)，称为边与顶点的关联映射 ( 论 图的基本概念 当 (u,v)用作有序偶对时， (V(G),V(G) =V(G) V(G)， e以 图 当 (u,v)用作无序偶对时， (u,v) = (v,u)，称 或边 )，图 或图 )。 论 图的基本概念 (2) 节点的度 在无向图中，节点 d(v)是 有向图中，节点 度 d +(v)(以 d -(v)( 点的度是 论 路及连通性 图 指如下顶点与边的序列： ,v l v l 其中 ,v l v 的顶点， ,e l e i( i= 1,2, ,l 以 v i及 v i +1为端点， (对有向图 G， v i +1为终点 )；拟路径的边数 l 1称为该拟路径的长度。当 e i( i= 1,2, , l 各不相同时，该拟路径称为路径 (又当 v i(i = 1,2, ,l) 各不相同时 (除 则称此路径为通路 ( 论 关联矩阵 论 邻接矩阵 散概率 样本空间 样本空间指的是概率试验的所有结果的集合，通常记为 S。样本空间中的每个元素分别称为样本点。如果样本空间含有有限个或可数的离散的样本点，该样本空间就是离散样本空间 。 事件 离散样本空间 为是 离散概率 设 的离散样本空间，且试验的每个结果的可能性相同，如果 相关的一个事件，则 为： ，其中，|A| 表示事件 |S|表示离散样本空间 |()|A 值分析 数值分析的特点 具有数学的科学性、严谨性，还具有实践性与技术性。 数值分析方法 常用的数值计算方法有构造法、离散法、递推法及近似替代法。 数值分析工具 筹学 运筹学的特点 运筹学以一定的数学模型为基础，同时具有综合性、实效性、全局性等特征。 运筹学的研究步骤 (1) 根据求解问题的目标，对问题进行分析和表述，抽象出问题本质，并构造合适的数学模型。 (2) 用已有的或寻求新的解法，对模型进行求解。 (3) 从以上两个步骤得到的可行方案中选出系统的最优解法。 (4) 对