第12章离散结构

1、第第1212章章 离离 散散 结结 构构2计算机科学导论计算机科学导论学习目标学习目标了解离散结构的研究对象及主要内容、了解离散结构的研究对象及主要内容、代数结构、离散概率。代数结构、离散概率。掌握数理逻辑与简单推理、集合论基础掌握数理逻辑与简单推理、集合论基础知识、图论基本知识。知识、图论基本知识。第第1212章章 离离 散散 结结 构构3计算机科学导论计算机科学导论12.1 离散结构的研究对象及主要内容离散结构的研究对象及主要内容 离散结构离散结构(Discrete Structure)是现代数学的一是现代数学的一个重要学科，它所涉及的概念、方法和理论，个重要学科，它所涉及的概念、方法和理

2、论，被大量应用于计算机科学与技术的研究。被大量应用于计算机科学与技术的研究。 本章将系统介绍传统离散数学包含的数理逻辑、本章将系统介绍传统离散数学包含的数理逻辑、集合论、代数结构、图论等集合论、代数结构、图论等4部分的基本内容，部分的基本内容，使读者初步了解离散结构的基本知识。使读者初步了解离散结构的基本知识。4计算机科学导论计算机科学导论12.1.1 离散结构的研究对象离散结构的研究对象 离散结构的研究对象是离散量的结离散结构的研究对象是离散量的结构和相互关系，以及离散系统结构构和相互关系，以及离散系统结构的数学模型以及建模方法。的数学模型以及建模方法。5计算机科学导论计算机科学导论12.1

3、.2 离散结构研究的主要内容离散结构研究的主要内容 离散结构研究的内容主要有传统离散数离散结构研究的内容主要有传统离散数学包含的数理逻辑、集合论、代数结构学包含的数理逻辑、集合论、代数结构和图论等和图论等4个部分，另外还包括计算机个部分，另外还包括计算机应用对象的离散结构的研究，离散概率、应用对象的离散结构的研究，离散概率、运筹学、数值计算、数学建模与模拟等。运筹学、数值计算、数学建模与模拟等。6计算机科学导论计算机科学导论12.2 数理逻辑数理逻辑12.2.1 命题逻辑命题逻辑u 命题命题 在数理逻辑中，称能够分辨真假、但不能同在数理逻辑中，称能够分辨真假、但不能同时既真又假的陈述句为命题时

4、既真又假的陈述句为命题 。u 原子命题原子命题 在命题中，有些命题是简单的陈述句，并且在命题中，有些命题是简单的陈述句，并且它们不能够被分成更为简单的陈述语句，这它们不能够被分成更为简单的陈述语句，这样的命题称为简单命题，或者原子命题。样的命题称为简单命题，或者原子命题。 7计算机科学导论计算机科学导论12.2.1 命题逻辑命题逻辑u 复合命题复合命题 一个简单命题再加上了一个表示否定的连接词形成的复一个简单命题再加上了一个表示否定的连接词形成的复合命题。合命题。 简单命题与复合命题都可以用简单的英文字母来表示。简单命题与复合命题都可以用简单的英文字母来表示。例例 用用Q表示命题：表示命题：8

5、是奇数！是奇数！ 用用P表示命题：李平不是学生。表示命题：李平不是学生。 构成复合命题的连接词构成复合命题的连接词 否定连接词，记作否定连接词，记作“ ” 合取连接词，也称合取连接词，也称“与与”，记作，记作“” 或取连接词，也称或取连接词，也称“或或”，记作，记作“” 蕴涵连接词，也称蕴涵连接词，也称“条件条件”，记作，记作“” 等价连接词，也称等价连接词，也称“双条件双条件”，记作，记作“ ” 8计算机科学导论计算机科学导论u2命题公式命题公式由命题常元、命题变元与各种逻辑连接词组合形成的由命题常元、命题变元与各种逻辑连接词组合形成的更为复杂的命题，称为命题公式，又称为合式公式。更为复杂的

6、命题，称为命题公式，又称为合式公式。u3等值演算等值演算(1)重言式重言式 如果对命题公式如果对命题公式A中命题变元的一切指派，中命题变元的一切指派，A的真值均的真值均为真，则称命题公式为真，则称命题公式A为重言式，重言式又称永真式。为重言式，重言式又称永真式。 (2)等价式等价式 设设A,B为两个命题公式，若等价式为两个命题公式，若等价式A B是重言式，则是重言式，则称称A逻辑等价于逻辑等价于B，或，或A与与B是等值的，记作是等值的，记作A B。A B不是命题公式。不是命题公式。 12.2.1 命题逻辑命题逻辑9计算机科学导论计算机科学导论u4命题推理命题推理推理是从前提出发推出结论的思维过

7、程，推理是从前提出发推出结论的思维过程，前提是已知的命题公式，结论是从前提出前提是已知的命题公式，结论是从前提出发应用推理规则推出的命题公式。发应用推理规则推出的命题公式。推理常用的方法推理常用的方法:真值表法真值表法等价证明法等价证明法 构造证明法构造证明法 12.2.1 命题逻辑命题逻辑10计算机科学导论计算机科学导论例例 证明证明PQ和和 Q的结论是的结论是P。证明：只需证明证明：只需证明(PQ) QP是重言式。是重言式。 真值表法真值表法按真值表的构造步骤，构造真值表如下：按真值表的构造步骤，构造真值表如下： P P Q QP PQ Q Q Q Q QQ Q P P0 0 0 0 0

8、01 10 01 10 10 11 10 00 01 11 01 01 11 11 11 11 11 11 10 00 01 112.2.1 命题逻辑命题逻辑11计算机科学导论计算机科学导论例例 证明证明PQ和和 Q的结论是的结论是P。证明证明：只需证明：只需证明(PQ) QP是重言式。是重言式。 等价证明法等价证明法(PQ) QP (P Q) Q Q)P (P Q)P PQ P TQ T 12.2.1 命题逻辑命题逻辑12计算机科学导论计算机科学导论例例证明：证明：pr, qs, pq rs 。证明证明： 构造证明法构造证明法1) pr前提前提2) pr1) 等价置换等价置换3) r p2)

9、 等价置换等价置换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.2.1 命题逻辑命题逻辑13计算机科学导论计算机科学导论12.2.2 谓词逻辑谓词逻辑 u对简单命题做进一步的分解，分析命题内部的逻辑结构对简单命题做进一步的分解，分析命题内部的逻辑结构和命题间的内在联系，它是命题逻辑的扩充和发展。和命题间的内在联系，它是命题逻辑的扩充和发展。 1.个体词个体词 原子命题中所描述的

10、对象，是可以独立存在的客体原子命题中所描述的对象，是可以独立存在的客体，可以是具体的，也可以是抽象的。，可以是具体的，也可以是抽象的。 2.谓词谓词 用来描述个体词的性质或个体词之间关系的词。用来描述个体词的性质或个体词之间关系的词。 3.量词量词 表示个体常元或变元之间数量关系的词称为量词。表示个体常元或变元之间数量关系的词称为量词。 14计算机科学导论计算机科学导论例例 将以下命题用谓词逻辑符号化。将以下命题用谓词逻辑符号化。(1) 所有的自然数都是大于零的。所有的自然数都是大于零的。(2) 没有不犯错误的人。没有不犯错误的人。(3) 这个班有些学生请假了。这个班有些学生请假了。解：解：(

11、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)。 12.2.2 谓词逻辑谓词逻辑 15计算机科学导论计算机科学导论u4谓词推理谓词推理(1) 全称量词消去规则。如果谓词公式全称量词消去规则。如果谓词公式xA(x)为真为真，则可推出，则可推

12、出A(c) 为真，即为真，即 xA(x) A(c)式中，式中，c是个体域中任意一个确定的个体。是个体域中任意一个确定的个体。(2) 存在量词消去规则。如果谓词公式存在量词消去规则。如果谓词公式xA(x)为真为真，则可推出，则可推出A(c) 为真，即为真，即 xA(x) A(c)式中，式中，c是个体域中满足条件是个体域中满足条件A的个体常元。的个体常元。12.2.2 谓词逻辑谓词逻辑 16计算机科学导论计算机科学导论 (3) 全称量词引入规则。如果谓词公式全称量词引入规则。如果谓词公式A(x)中的中的自由个体变元自由个体变元x无论取个体论域中的任何值，无论取个体论域中的任何值，A(x)都为真，则

13、可推出都为真，则可推出xA(x)为真，即为真，即 A(x) xA(x)式中，式中，x是个体域中任意一个个体。是个体域中任意一个个体。 (4) 存在量词引入规则。如果谓词公式存在量词引入规则。如果谓词公式A(c)为真为真，则可推出，则可推出xA(x) 为真，即为真，即 A(c)xA(x)式中，式中，c是个体域中满足条件是个体域中满足条件A的个体常元。的个体常元。12.2.2 谓词逻辑谓词逻辑 17计算机科学导论计算机科学导论12.3 集合论集合论12.3.1 集合的基本概念与运算集合的基本概念与运算 对简单命题做进一步的分解，分析命题内部的逻辑结构对简单命题做进一步的分解，分析命题内部的逻辑结构

14、和命题间的内在联系，它是命题逻辑的扩充和发展。和命题间的内在联系，它是命题逻辑的扩充和发展。 u 1.1.集合的概念与表示集合的概念与表示 事物汇集在一起组成的一个整体叫做集合，而这些事物事物汇集在一起组成的一个整体叫做集合，而这些事物就可以称为这个集合的元素或者成员。就可以称为这个集合的元素或者成员。集合通常用大写的英文字母来标记。集合通常用大写的英文字母来标记。 表示一个集合的方法：表示一个集合的方法： 列举法列举法 ：A A 1,2,3,n,1,2,3,n, 描述法描述法 ：B Bx|xx|x是大于等于是大于等于8 8的正整数的正整数 18计算机科学导论计算机科学导论12.3.1 集合的

15、基本概念与运算集合的基本概念与运算 u2.集合间关系集合间关系 设设A ，B是集合，如果是集合，如果B中的每个元素都是中的每个元素都是A中的元素中的元素，则称，则称B是是A的子集合，简称子集。这时也称的子集合，简称子集。这时也称B被被A包含包含，或，或A包含包含B。 设设A，B为集合，如果为集合，如果A B且且B A，则称，则称A与与B相等相等，记作，记作AB 。设设A，B为集合，如果为集合，如果B A且且BA，则称，则称B是是A的真子集的真子集。记作。记作B A。 不含任何元素的集合叫做空集，记作不含任何元素的集合叫做空集，记作。 给定集合给定集合A，由集合，由集合A的所有子集为元素组成的集

16、合，的所有子集为元素组成的集合，称为集合称为集合A的幂集，记作的幂集，记作P(A) 。在一个具体问题中，如果所涉及的集合都是某个集合在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作的子集，则称这个集合为全集，记作E(或或U)。 19计算机科学导论计算机科学导论u3.集合运算集合运算 (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为全集，为

17、全集，A E，则，则A的补运算，记作的补运算，记作，定，定义为，义为， AE -Ax xEx A 或或 Ax x A (3) 定义：设定义：设A与与B为集合，为集合，A与与B的对称差，记作的对称差，记作 ，定，定义为义为 A B(AB)(AB )12.3.1 集合的基本概念与运算集合的基本概念与运算 20计算机科学导论计算机科学导论12.3.2 关系与函数关系与函数u1.笛卡儿积笛卡儿积 (1) 序偶序偶 由两个元素由两个元素x和和y(允许允许x =y)按一定的顺序排列成按一定的顺序排列成的二元组叫做一个有序对的二元组叫做一个有序对(也称序偶也称序偶)，记作，记作，其中其中x是它的第一元素，是

18、它的第一元素，y是它的第二元素。是它的第二元素。u 有序对的特点：有序对的特点：当当x y时，时， 。两个有序对相等，即两个有序对相等，即 的充分必的充分必要条件是要条件是xu且且yv。 21计算机科学导论计算机科学导论 (2)笛卡儿积笛卡儿积 设设A，B为集合，用为集合，用A中元素作为第一元素，中元素作为第一元素，B中元素中元素作为第二元素，构成有序对，所有这样的有序对组成的集作为第二元素，构成有序对，所有这样的有序对组成的集合叫做合叫做A和和B的笛卡儿积，记作的笛卡儿积，记作AB。符号化表示为。符号化表示为 AB(x,y)|xAyB例例 有两个集合有两个集合Aa,b，B0,1,2，则，则

19、AB, BA, 12.3.2 关系与函数关系与函数22计算机科学导论计算机科学导论u 2.二元关系二元关系 (1) 二元关系定义二元关系定义 如果一个集合为空集或者它的元素都是有序对，则称这如果一个集合为空集或者它的元素都是有序对，则称这个集合是一个二元关系，一般记作个集合是一个二元关系，一般记作R 对于二元关系对于二元关系R，如果有序对，如果有序对R，则记作，则记作x R y 设设A,B为集合，为集合，AB的任何子集所定义的二元关系称作的任何子集所定义的二元关系称作从从A到到B的二元关系，特别当的二元关系，特别当AB时，则叫做时，则叫做A上的二上的二元关系元关系12.3.2 关系与函数关系与

20、函数23计算机科学导论计算机科学导论u3种特殊的关系：种特殊的关系：其中之一就是空集其中之一就是空集，称做空关系。，称做空关系。另外两种就是全域关系另外两种就是全域关系EA和恒等关系和恒等关系IA。对任何集合对任何集合A， EAxAyAAA IAxA 12.3.2 关系与函数关系与函数24计算机科学导论计算机科学导论u(2) 关系的表示关系的表示 通常用关系图来表示一个关系。通常用关系图来表示一个关系。 例例 A=1,2,3,4，R=,，可以画出如下的关系图。可以画出如下的关系图。12.3.2 关系与函数关系与函数25计算机科学导论计算机科学导论u(3) 关系的基本运算关系的基本运算 Dom(

21、R)x y(R) Ran(R)y | x(R) F的逆记作：的逆记作：|F。 F与与G的左复合记作的左复合记作G F ， G F z(GF) F与与G的右复合记作的右复合记作F G， F G z(FG) 12.3.2 关系与函数关系与函数26计算机科学导论计算机科学导论u (4) 关系的性质关系的性质自反性自反性若对于任意若对于任意x属于集合属于集合A，都有，都有 ，那么，就说，那么，就说R在在A上是自反的。上是自反的。反自反性反自反性若对于任意若对于任意x属于集合属于集合A，都不存在，都不存在 ，那么，就说，那么，就说R在在A上是反自反的。上是反自反的。对称性对称性若对于任意若对于任意x,y

22、属于集合属于集合A，都有，都有 R ，那么，就称，那么，就称R为为A上的对称关系。上的对称关系。反对称性反对称性若对于任意若对于任意x,y属于集合属于集合A，都不存在，都不存在 R ，那么，就称那么，就称R为为A上的反对称关系。上的反对称关系。例如例如A上的全域关系，恒等关系，空关系都是上的全域关系，恒等关系，空关系都是A上的对称关系。而上的对称关系。而恒等关系和空关系也是恒等关系和空关系也是A上反对称关系。上反对称关系。传递性传递性若对任意的若对任意的x,y,z都属于集合都属于集合A，假如都存在，假如都存在 ，那么，就称，那么，就称R为为A上的传递关系。上的传递关系。 ,x Ax xR ,x

23、Ax xR, x yA, y xR, y xR, ,x y zA, y zR, x yR, x zR27计算机科学导论计算机科学导论u(5) 两类重要的二元关系两类重要的二元关系 等价关系等价关系设设R为非空集合为非空集合A上的二元关系，若上的二元关系，若R具有自反性、具有自反性、对称性和传递性，则称对称性和传递性，则称R为为A上的等价关系。上的等价关系。利用等价关系，可以对一些对象进行分类。例如，利用等价关系，可以对一些对象进行分类。例如，集合上的恒等关系即是等价关系。集合上的恒等关系即是等价关系。 偏序关系偏序关系 设设R为非空集合为非空集合A上的二元关系，若上的二元关系，若R具有自反性、

24、具有自反性、反对称性和传递性，则称反对称性和传递性，则称R为为A上的偏序关系，偏序关上的偏序关系，偏序关系可以记为系可以记为。集合。集合A和和A上的偏序关系上的偏序关系R一起叫做偏序一起叫做偏序集，记为集，记为(A,)，如果有，如果有(a,b)R，可以表示为，可以表示为ab 。根据偏序关系可以画出关系图，通常称为哈斯图。根据偏序关系可以画出关系图，通常称为哈斯图。 12.3.2 关系与函数关系与函数28计算机科学导论计算机科学导论例例 已知已知为偏序集，集合为偏序集，集合A=a,b, c,d,e,f，关系，关系=(b,a),(d,b),(c,a), (e,c),(e,b),(d,a),(e,a

25、)，画出，画出关系关系的哈斯图。的哈斯图。解：按照偏序集哈斯图的规则，可以得到如下哈斯图解：按照偏序集哈斯图的规则，可以得到如下哈斯图12.3.2 关系与函数关系与函数29计算机科学导论计算机科学导论u 4.函数函数 函数函数(Functions)也称映射也称映射(Mapping)。函数也。函数也是一种二元关系，与普通的二元关系相比，函数可是一种二元关系，与普通的二元关系相比，函数可以看作是一种特殊的二元关系。以看作是一种特殊的二元关系。(1) 函数的定义函数的定义 设设F为二元关系，若对于任意的为二元关系，若对于任意的x，都存在惟，都存在惟一的让一的让xFy成立，则称成立，则称F为函数。对于

26、任意函数为函数。对于任意函数F，如果都有如果都有xFy，则记做，并称，则记做，并称y为为F在在x上的值。上的值。 12.3.2 关系与函数关系与函数30计算机科学导论计算机科学导论u(2) 特殊函数特殊函数 函数的性质函数的性质 设函数设函数f :AB 若对于任何的若对于任何的x1,x2A，x1x2，都有，都有 f(x1)f(x2)，则，则 称称f是单射的。是单射的。 若若Ran(f)B，则称，则称f是满射。是满射。 若若f既是满射的，又是单射的，则称既是满射的，又是单射的，则称f是双射的。是双射的。 12.3.2 关系与函数关系与函数31计算机科学导论计算机科学导论 复合函数复合函数 设设f

27、是从集合是从集合A到集合到集合B的函数，的函数，g是从集合是从集合B到集合到集合C的函数，的函数，f和和g的复合用的复合用f g 表示为表示为 f g =(a,c)|aAcC b(bB)(a,b)f(b,c)g 反函数反函数 设函数设函数f是集合是集合X到集合到集合Y的一个双射函数。则的一个双射函数。则f的反的反函数是集合函数是集合Y到集合到集合X的函数，对于的函数，对于yY，都分派一个，都分派一个惟一的惟一的xX和它对应，使得和它对应，使得f(x)=y 。f的反函数记作：的反函数记作：f 1: YX，即，即f 1(y)=x。 12.3.2 关系与函数关系与函数32计算机科学导论计算机科学导论

28、12.4 代数结构代数结构12.4.1 代数结构概述代数结构概述u1.运算的定义及性质运算的定义及性质 （以二元运算为例）（以二元运算为例） 设设S为集合，函数为集合，函数 f：S SS 称为称为S上的二元运算上的二元运算，简称为二元运算。，简称为二元运算。 二元运算的一些性质：二元运算的一些性质： (1) 设设 为为S上的二元运算，如果对于任意的上的二元运算，如果对于任意的x,yS都都有有x y =y x，则称运算，则称运算 在在S上满足交换律。上满足交换律。 (2) 设设 为为S上的二元运算，如果对于任意的上的二元运算，如果对于任意的x,y,zS都都有有 (x y) z =x (y z)，

29、则称运算，则称运算 在在S上满足结合律。上满足结合律。33计算机科学导论计算机科学导论12.4.1 代数结构概述代数结构概述(3) (3) 设设 S S上的二元运算，如果对于任意的上的二元运算，如果对于任意的xSxS有有x x x =xx =x则称运算则称运算 在在S S上满足幂等律。上满足幂等律。(4) (4) 设设 和和 为为S S上两个二元运算，如果对于任意的上两个二元运算，如果对于任意的x,y,zSx,y,zS，有，有 x x (y (y z) z) (x(x y) y) (x(x z)z)( (左分配律左分配律) ) (y (y z)z) x x (y(y x) x) (z(z x)

30、x)( (右分配律右分配律) )则称运算则称运算 对运算对运算 满足分配律。满足分配律。 (5) (5) 设设 和和 为为S S上两个可交换的二元运算，如果对于任意上两个可交换的二元运算，如果对于任意的的x,ySx,yS，都有，都有x x (x (x y)y)x xx x (x (x y)y)x x则称运算则称运算 和和 满足吸收律。满足吸收律。 34计算机科学导论计算机科学导论u2运算中的特殊元素运算中的特殊元素集合中有些元素在运算过程中具有特殊的性质，它们集合中有些元素在运算过程中具有特殊的性质，它们是集合运算中的特殊元素。是集合运算中的特殊元素。(1)(1)幺元。设幺元。设* *为为S

31、S上的二元运算，如果元素上的二元运算，如果元素eSeS且对任且对任意元素意元素xSxS，有，有x x* *e=ee=e* *x=x x=x 则称则称e e为为S S上关于上关于* *运算的幺元，且唯一。运算的幺元，且唯一。(2)(2)零元。设零元。设* *为为S S上的二元运算，如果元素上的二元运算，如果元素OSOS且对任且对任意元素意元素xSxS，有，有x x* *O=OO=O* *x=O x=O 则称则称O O为为S S上关于上关于* *运算的零元，且唯一。运算的零元，且唯一。(3)(3)逆元。设逆元。设* *为为S S上的二元运算，上的二元运算，eSeS为运算为运算* *的幺元。的幺元。

32、对于元素对于元素xSxS，且对任意元素，且对任意元素ySyS，有，有x x* *y =yy =y* *x =e x =e 则称则称y y为为x x的逆元。的逆元。35计算机科学导论计算机科学导论12.4.1 代数结构概述代数结构概述u3.3.代数结构的定义代数结构的定义 代数结构通常指由以下三个部分组成的数学结构：代数结构通常指由以下三个部分组成的数学结构： 一个非空集合一个非空集合S S，称为代数结构的载体。，称为代数结构的载体。 S S上的若干运算。上的若干运算。 一组刻画载体一组刻画载体S S上各运算所满足性质的公理。上各运算所满足性质的公理。通常，代数结构用一个多元序组通常，代数结构用

33、一个多元序组S来来表示，其中，表示，其中，S S是载体，是载体，* *，为各种运算。有为各种运算。有时，时，S S中地位比较特殊的元素中地位比较特殊的元素( (如幺元、零元、逆元如幺元、零元、逆元) )也会被列入这个多元组的末尾。也会被列入这个多元组的末尾。例如，以自然数集例如，以自然数集N N为载体，为载体，“+”+”运算可以作为二运算可以作为二元运算组成一个代数结构，记为元运算组成一个代数结构，记为。 36计算机科学导论计算机科学导论12.4.2 格与布尔代数格与布尔代数u1.格格 (1)格的定义：格的定义：有序集有序集称为格称为格(lattice)，如果，如果A的任何两个的任何两个元素的

34、子集都有上确界和下确界。通常，用元素的子集都有上确界和下确界。通常，用ab表表示示a,b的上确界，用的上确界，用ab表示表示a,b的下确界。的下确界。(a) 格 (b) 非格37计算机科学导论计算机科学导论 (2)分配格分配格 称格称格为分配格，如果它为分配格，如果它满足分配律，即对任意满足分配律，即对任意a,b,cA, a(bc)=(ab) (ac) a(bc)=(ab) (ac)12.4.2 格与布尔代数格与布尔代数38计算机科学导论计算机科学导论(3)有界格有界格格格称为有界格，如果称为有界格，如果A中既有上中既有上确界确界1，又有下确界，又有下确界0。则，。则，0和和1称为称为A的界。

35、的界。 对于对于A中的一个元素中的一个元素a，如果有，如果有 ab =1，ab=0 则称则称b为为a 的补元或补。记为的补元或补。记为a。 如果如果A中的每个元素都有补元，则有界格中的每个元素都有补元，则有界格称为有补格。称为有补格。 12.4.2 格与布尔代数格与布尔代数39计算机科学导论计算机科学导论u2.布尔代数的定义布尔代数的定义 定义：代数系统定义：代数系统称为布尔代数，如果称为布尔代数，如果 B满足以下条件：满足以下条件： 运算运算，满足交换律。满足交换律。 运算对运算对运算满足分配律，运算满足分配律，运算对运算对运算运算也满足分配律。也满足分配律。 B有有运算幺元运算幺元1和和运

36、算零元运算零元0、运算幺元运算幺元0和和运算零元运算零元1。 对对B中的每一个元素中的每一个元素a，均存在元素，均存在元素a，使，使 aa=1， aa=0 12.4.2 格与布尔代数格与布尔代数40计算机科学导论计算机科学导论12.5 图图 论论12.5.1 图的基本概念图的基本概念u1图的由来图的由来 哥尼斯堡七桥问题哥尼斯堡七桥问题 41计算机科学导论计算机科学导论12.5.1 图的基本概念图的基本概念u2.图的基本概念图的基本概念 (1) 图的定义图的定义图图(graph)G由三个部分所组成：由三个部分所组成： 非空集合非空集合V(G)，称为图，称为图G的节点集，其成员称为节点或的节点集

37、，其成员称为节点或顶点顶点(nodes or vertices)。 集合集合 E(G)，称为图，称为图G的边集，其成员称为边的边集，其成员称为边(edges)。 函数函数(G):E(G)(V(G)，V(G)，称为边与顶点的关联，称为边与顶点的关联映射映射(associatve mapping)。 42计算机科学导论计算机科学导论u(2) 关于图的更多概念关于图的更多概念设图设图G为为 当当V和和E为有限集时，称为有限集时，称G为有限图，否则称为有限图，否则称G为为无限图。在此只讨论有限图。无限图。在此只讨论有限图。 当当G为单射时，称为单射时，称G为单图；当为单图；当G为非单射时为非单射时，称

38、，称G为重图，又称满足为重图，又称满足(e1) = (e2)的不同边的不同边e1、e2为重边，或平行边。为重边，或平行边。 当当(e)(v,v)(或或)时，称时，称e为环为环(loops)。无环。无环和重边的无向单图称为简单图。当和重边的无向单图称为简单图。当G为有限简单图为有限简单图时，也常用时，也常用(n,m)表示图表示图G，其中，其中n = V，m = E 。12.5.1 图的基本概念图的基本概念43计算机科学导论计算机科学导论 在单图在单图G中，中，(e)(u,v)(或或)时，也用时，也用(u,v)(或或)表示边表示边e，这时称，这时称u,v邻接邻接e, u,v是是e的端点的端点(或称

39、或称u为为e的起点，的起点，v为为e的终点的终点)；也称；也称e关联结点关联结点u,v 。不是。不是任何边的端点的节点称为孤立结点，仅由孤立结点构任何边的端点的节点称为孤立结点，仅由孤立结点构成的图成的图(E = )称为零图。称为零图。12.5.1 图的基本概念图的基本概念44计算机科学导论计算机科学导论u (3) 结点的度结点的度 定义：在无向图中，结点定义：在无向图中，结点v的度的度(degree)d(v)是是v作为边的端点的数目。在有向图中，结作为边的端点的数目。在有向图中，结点点v的出度的出度d +(v)(out-degree)是以是以v作为有向作为有向边起点的数目，边起点的数目，v的

40、入度的入度d -(v)(in-degree)是是v作为有向边终点的数目。结点的度是作为有向边终点的数目。结点的度是v的出的出度与入度之和。度与入度之和。 12.5.1 图的基本概念图的基本概念45计算机科学导论计算机科学导论12.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

41、 l -1 为为G的边，且的边，且e i( i= 1,2, ,l-1 )以以v i及及v i +1为端点，为端点，(对对有向图有向图G，ei以以vi为起点，以为起点，以v i +1为终点为终点)；拟路径的边；拟路径的边数数l1称为该拟路径的长度。当称为该拟路径的长度。当e i( i= 1,2, , l-1 )各不相各不相同时，该拟路径称为路径同时，该拟路径称为路径(walk)，又当，又当v i(i = 1,2, ,l)各各不相同时不相同时(除除v1与与v1)，则称此路径为通路，则称此路径为通路(Path)。v1v1的路径称为闭路径的路径称为闭路径(closed walk)；v1= v1的通路称

42、为回路的通路称为回路(circuit)。46计算机科学导论计算机科学导论 定义：定义：称无向图称无向图G是连通的是连通的(Connected)，如果，如果G的的任何两个顶点都是相互可达的。任何两个顶点都是相互可达的。 定义：定义：称有向图称有向图G是强连通的，如果是强连通的，如果G的任何两个的任何两个顶点都是相互可达的；称有向图顶点都是相互可达的；称有向图G是单向连通的，是单向连通的，如果如果G的任何两个顶点中，至少从一个顶点到另一的任何两个顶点中，至少从一个顶点到另一个顶点是可达的；称有向图个顶点是可达的；称有向图G是弱连通的，如果是弱连通的，如果G的有向边被看作无向边时是连通的。的有向边被

43、看作无向边时是连通的。(a) 强连通图 (b) 单向连通图 (c)弱连通图12.5.2 路径、回路及连通性路径、回路及连通性47计算机科学导论计算机科学导论12.5.3图的矩阵表示图的矩阵表示 (1)关联矩阵关联矩阵 48计算机科学导论计算机科学导论 (2) 邻接矩阵邻接矩阵 12.5.3图的矩阵表示图的矩阵表示 49计算机科学导论计算机科学导论12.6 离散概率离散概率概率概率(Probability)在推理过程中具有非常重要的在推理过程中具有非常重要的作用，它通常用来衡量事件发生的可能性的大小，作用，它通常用来衡量事件发生的可能性的大小，或者说用来衡量人们期待的事件占总体事件的比例或者说用

44、来衡量人们期待的事件占总体事件的比例u离散概率离散概率(Discrete Probability)的一些基本知识：的一些基本知识： 定义：概率试验通常指人们对随机现象的结果进行定义：概率试验通常指人们对随机现象的结果进行观察、记录的过程，通常记为观察、记录的过程，通常记为E。 定义：样本空间指的是概率试验的所有结果的集合，定义：样本空间指的是概率试验的所有结果的集合，通常记为通常记为S。样本空间中的每个元素分别称为样本点。样本空间中的每个元素分别称为样本点。如果样本空间含有有限个或可数的离散的样本点，如果样本空间含有有限个或可数的离散的样本点，该样本空间就是离散样本空间。该样本空间就是离散样本空间。 同一个概率试验可以有不同的样本空间。同一个概率试验可以有不同的样本空间。50计算机科学导论计算机科学导论 定义：定义：离散样本空间离散样本空间S的任意子集，称为的任意子集，称为S中的事件。不能中的事件。不能分解的事件为简单事件，即简单事件只有唯一的一个样本分解的事件为简单事件，即简单事件只有唯一的一个样本点。如果与概率试验点。如果与概率试验E相关联的多个事件不能同时出现，相关联的多个事件不能同时出现，称为互斥事件。称为互斥事件。 定义：定义：设设S为概率试验为概率试验E的离散样本空间，且试验的每个的离散样本空间，且试验的每