《《计算机科学导论(第2版)》第11章：离散结构》由会员分享，可在线阅读，更多相关《《计算机科学导论(第2版)》第11章：离散结构（43页珍藏版）》请在金锄头文库上搜索。
1、 1计算机科学导论第11章 离散结构2计算机科学导论本章要点：离散结构的研究对象及主要内容 数理逻辑与简单推理 集合论基础知识 代数结构 图论基本知识 离散概率 数值分析特点与方法 运筹学概念与步骤 数学建模与计算机模拟的概念与步骤 3计算机科学导论11.1离散结构的研究对象及 主要内容 1.研究对象 离散数量关系以及离散系统结构的数学模型以 及建模方法 。 2.研究的主要内容传统离散数学包含的数理逻辑、集合论、代数 结构和图论等四个部分，以及计算机应用对象的离 散结构的研究，离散概率、运筹学、数值计算、数 学建模与模拟等。 4计算机科学导论11.2 数理逻辑 1.命题逻辑 离散数量关系以及离
2、散系统结构的数学模型以 及建模方法 。 命题 在数理逻辑中，称能够分辨真假、但不能同时既真又假 的陈述句为命题 。 原子命题 在命题中，有些命题是简单的陈述句，并且它们不能够 被分成更为简单的陈述语句，这样的命题称为简单命题，或 者原子命题。 5计算机科学导论11.2 数理逻辑 (2) 复合命题 一个简单命题再加上了一个表示否定的连接词形成的复合命题。简单命题与复合命题都可以用简单的英文字母来表示。例 用Q表示命题：8是奇数！用P表示命题：李平不是学生。构成复合命题的连接词 否定连接词，记作“ ” 合取连接词，也称“与”，记作“” 或取连接词，也称“或”，记作“” 蕴涵连接词，也称“条件”，记
3、作“” 等价连接词，也称“双条件”，记作“ ” 6计算机科学导论11.2 数理逻辑 命题公式命题常元、命题变元与各种逻辑连接词组合形成的更 为复杂的命题，就可以称为命题公式，又叫做合式公式。 命题常元 单个的已知命题(可以是具体的命题、常真命题、常假 命题) 。 (2) 命题变元 不代表具体命题的、但是取值范围仍然为“真”与“假”或 “1”与“0”的符号表示的命题 。7计算机科学导论11.2 数理逻辑 等值演算 命题常元、命题变元与各种逻辑连接词组合形成的更 为复杂的命题，就可以称为命题公式，又叫做合式公式。 重言式 如果对命题公式A中命题变元的一切指派，A的真值均 为真，则称命题公式A为重言
4、式，重言式又称永真式。 (2) 等价式 设A,B为两个命题公式，若等价式A B是重言式，则 称A逻辑等价于B，或A与B是等值的，记作A B。A B不 是命题公式。 8计算机科学导论11.2 数理逻辑 命题推理 推理是从前提出发推出结论的思维过程，前提是已知 的命题公式，结论是从前提出发应用推理规则推出的命题公 式。 真值表法 等价证明法 构造证明法 9计算机科学导论11.2 数理逻辑 例 证明PQ和 Q的结论是P。 证明：只需证明(PQ) QP是重言式。 真值表法按真值表的构造步骤，构造真值表如下：(PQ)(PQ)P QPQ Q Q Q P 0 0 0 101 0 11 001 1 01 11
5、1 1 11 00110计算机科学导论11.2 数理逻辑 例 证明PQ和 Q的结论是P。 证明：只需证明(PQ) QP是重言式。 等价证明法 (PQ) QP (P Q) Q Q)P(P Q)PPQ PTQT 11计算机科学导论11.2 数理逻辑 例证明：pr, qs, pq rs 。 证明： 构造证明法 1) pr前提 2) pr1) 等价置换 3) r p2) 等价置换 4) r p3) 等价置换 5) pq前提 6) p q5) 等价置换 7) p q6) 等价置换 8) r q4)7)假言三段论 9) qs前提 10) r s8)9)假言三段论 11) rs 10) 等价置换 12计算机
6、科学导论11.2 数理逻辑 2.谓词逻辑 是对简单命题做进一步的分解，分析命题内部的逻辑结构和命题间的内在联系，它是命题逻辑的扩充和发展。 个体词 原子命题中所描述的对象，是可以独立存在的客体，可以是具体的，也 可以是抽象的。 谓词 用来描述个体词的性质或个体词之间关系的词。 量词 表示个体常元或变元之间数量关系的词称为量词。 13计算机科学导论11.2 数理逻辑 全称量词 全称量词表示“所有的”，“每一个”，“对任何 一个”，“一切”，“任意的”。符号为“”。 (2) 存在量词 表示“存在着”，“有一个”，“至少有一个”，“ 存在一些”，“对于一些”，“某个”等。符号为“”。 14计算机科学
7、导论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)。 15计算机科学导论11.2 数理逻辑 谓词推理 谓词逻辑推理是命题逻辑推理的推广。谓词逻 辑的推理也是利用命题公式间的各种等价关系、蕴 涵关系，通
8、过一些推理规则，从已知命题公式推出 一些新的公式。 16计算机科学导论11.3 集合论 1.集合的基本概念与运算 是对简单命题做进一步的分解，分析命题内部的逻辑结构和命题间的内在联系，它是命题逻辑的扩充和发展。 集合的概念与表示 事物汇集在一起组成的一个整体叫做集合，而这些事物 就可以称为这个集合的元素或者成员。集合通常用大写的英文字母来标记。 表示一个集合的方法 列举法 ：A1,2,3,n, 描述法 ：Bx|x是大于等于8的正整数 17计算机科学导论11.3 集合论 集合间关系 设A ，B是集合，如果B中的每个元素都是A中的元素，则称B是A的子集 合，简称子集。这时也称B被A包含，或A包含B
9、。 设A，B为集合，如果A B且B A，则称A与B相等，记作AB 。设A，B为集合，如果BA且BA，则称B是A的真子集。记作B A。 不含任何元素的集合叫做空集，记作。 给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集 ，记作P(A) 。在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个 集合为全集，记作E(或U)。 18计算机科学导论11.3 集合论 集合运算 (1) 定义：设A与B为集合，A与B的并运算、交运算、差运 算 - ，分别定义为，AB=x|(x A) (x B)AB=x|(x A) (x B)A - B =x|(x A) (x B) (2) 定义：设E
10、为全集，A E，则A的补运算，记作，定义为 ，AE -AxxExA 或 AxxA (3) 定义：设A与B为集合，A与B的对称差，记作，定义为， AB(AB)(AB 19计算机科学导论11.3 集合论 2.关系与函数 笛卡儿积 (1) 序偶由两个元素x和y(允许x =y)按一定的顺序排列成的二 元组叫做一个有序对(也称序偶)，记作，其中x是它的第 一元素，y是它的第二元素。有序对的特点： 当x y时，。 两个有序对相等，即 的充分必要条件 是xu且yv。 20计算机科学导论11.3 集合论 (2)笛卡儿积 设A，B为集合，用A中元素作为第一元素，B中元素 作为第二元素，构成有序对，所有这样的有序
11、对组成的集合 叫做A和B的笛卡儿积，记作AB。符号化表示为AB(x,y)|xAyB 例 有两个集合Aa,b，B0,1,2，则AB,BA, 21计算机科学导论11.3 集合论 二元关系 (1) 二元关系定义如果一个集合为空集或者它的元素都是有序对，则称这个集合是一 个二元关系，一般记作R。对于二元关系R，如果有序对R，则记作x R y 。设A,B为集合，AB的任何子集所定义的二元关系称作从A到B的二元关系，特别当AB时，则叫做A上的二元关系。 3种特殊的关系：其中之一就是空集，称做空关系。另外两种就是全域关系EA和恒等关系IA。对任何集合A， EAxAyAAA IAxA 22计算机科学导论11.
12、3 集合论 (2) 关系的表示通常用关系图来表示一个关系。 例 A=1,2,3,4，R=,，可以画出如下的关系 图。23计算机科学导论11.3 集合论 (3) 关系的基本运算Dom(R)x y(R)Ran(R)y | x(R) F的逆记作：|F。 F与G的左复合记作F G，F G z(GF) F与G的右复合记作F G，F G z(FG) 24计算机科学导论11.3 集合论 (4) 关系的性质 自反性 若对于任意x属于集合A，都有 ，那么，就说R在A上是自反的。 反自反性 若对于任意x属于集合A，都不存在 ，那么，就说R在A上是反自 反的。 对称性 若对于任意x,y属于集合A，都有 R ，那么，
13、就 称R为A上的对称关系。 反对称性 若对于任意x,y属于集合A，都不存在 R ，那么，就称R 为A上的反对称关系。 例如A上的全域关系，恒等关系，空关系都是A上的对称关系。而恒等关系和空 关系也是A上反对称关系。 传递性 若对任意的x,y,z都属于集合A，假如都存在 ，那么，就称R为A上的传递关系。 25计算机科学导论11.3 集合论 (5) 两类重要的二元关系 等价关系设R为非空集合A上的二元关系，若R具有自反性、对称 性和传递性，则称R为A上的等价关系。利用等价关系，可以对一些对象进行分类。例如，集合 上的恒等关系即是等价关系。 偏序关系 设R为非空集合A上的二元关系，若R具有自反性、反
14、对 称性和传递性，则称R为A上的偏序关系，偏序关系可以记为 。集合A和A上的偏序关系R一起叫做偏序集，记为(A,)，如果 有(a,b)R，可以表示为ab 。根据偏序关系可以画出关系图，通常称为哈斯图。 26计算机科学导论11.3 集合论 例 已知为偏序集，集合A=a,b, c,d,e,f，关系 =(b,a),(d,b),(c,a), (e,c),(e,b),(d,a),(e,a)，画出关系的哈斯图。 解：按照偏序集哈斯图的规则，可以得到如下哈斯图。27计算机科学导论11.3 集合论 函数 (1) 函数的定义设F为二元关系，若对于任意的x，都存在惟一的让xFy成立，则称F为函数。对于任意函数F，如果都有xFy，
