专必计算机科学导论复习第12章离散结构

1、第12章离散结构学习目标 了解离散结构的研究对象及主要内容、代数结构、离散概率。 掌握数理逻辑与简单推理、集合论基础知识、图论基本知识。2计算机科学导论12.1离散结构的研究对象及主要内容 离散结构(Discrete Structure)是现代数学的一个重要学科，它所涉及的概念、方法和理论，被大量应用于计算机科学与技术的研究。 本章将系统传统离散数学包含的数理逻辑、集合论、代数结构、图论等4部分的基本内容，使读者初步了解离散结构的基本知识。3计算机科学导论12.1.1离散结构的研究对象 离散结构的研究对象是离散量的结构和相互关系，以及离散系统结构的数学模型以及建模方法。4计算机科学导论12.1

2、.2离散结构研究的主要内容 离散结构研究的内容主要有传统离散数学包含的数理逻辑、集合论、代数结构 和图论等4个部分，另外还包括计算机 应用对象的离散结构的研究，离散概率、运筹学、数值计算、数学建模与模拟等。5计算机科学导论12.212.2.1数理逻辑命题逻辑u命题在数理逻辑中，称能够分辨真假、但不能同时既的陈述句为命题 。u原子命题在命题中，有些命题是简单的陈述句，并且它们不能够被分成更为简单的陈述语句，这样题称为简单命题，或者原子命题。6计算机科学导论12.2.1命题逻辑u 复合命题一个简单命题再加上了一个表示合命题。的连接词形成的复简单命题与复合命题都可以用简单的英文字母来表示。例 用Q表

3、示命题：8是奇数！用P表示命题：不是学生。复合命题的连接词连接词，记作“” 合取连接词，也称“与”，记作“” 或取连接词，也称“或”，记作“” 蕴涵连接词，也称“条件”，记作“” 等价连接词，也称“双条件”，记作“ ”7计算机科学导论12.2.1命题逻辑u 2命题公式由命题常元、命题变元与各种逻辑连接词组合形成的更为复杂题，称为命题公式，又称为合式公式。u 3等值演算 (1)重言式如果对命题公式A中命题变元的一切指派，A的真值均为真，则称命题公式A为重言式，重言式又称 (2)等价式设A,B为两个命题公式，若等价式A B是重言式，则称A逻辑等价于B，或A与B是等值的，记作AB。A B式。不是命题

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

5、导论12.2.1例证明：pr, qs, pq证明：命题逻辑 rs 。构造证明法1) pr前提1) 等价置换2) 等价置换3) 等价置换前提5) 等价置换6) 等价置换4)7)假言 前提8)9)假言10) 等价置换2) pr3) r p4) r p5) pq6) p q 7) p q 8) r q9) qs10) r s11) rs12计算机科学导论12.2.2 谓词逻辑u 对简单命题做进一步的分解，分析命题内部的逻辑结构和命题间的内在，它是命题逻辑的扩充和发展。 1.词原子命题中所描述的对象，是可以，可以是具体的，也可以是抽象的。 2.谓词存在的客体词的性质或词之间关系的词。 3.量词表示常变

6、元之间数量关系的词称为量词。13计算机科学导论12.2.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)。14计算机科学导论12.2.2 谓词逻辑u 4谓词推理 (1) 全称量词消去规则。如果谓词公式xA(x)为真， 则可推出A(c)

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

8、运算对简单命题做进一步的分解，分析命题内部的逻辑结构和命题间的内在，它是命题逻辑的扩充和发展。u1.集合的概念与表示事物汇集在一起组成的一个整体叫做集合，而这些事物就可以称为这个集合的元素或者成员。集合通常用大写的英文字母来标记。表示一个集合的方法：A1,2,3,n,：Bx|x是大于等于8的正整数列举法描述法17计算机科学导论12.3.1u 2.集合间关系 设A ，B是集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。这时也称B被A包含，或A包含B。 设A，B为集合，如果A B且B A，则称A与B相等，记作AB 。 设A，B为集合，如果BA且BA，则称B是A的真子集。记作B

9、 A。 不含任何元素的集合叫做空集，记作。集合的基本概念与运算 给定集合A，由集合A的集为元素组成的集合，称为集合A的幂集，记作P(A) 。 在一个具体问题中，如果所涉及的集合都是某个集合 的子集，则称这个集合为全集，记作E(或U)。18计算机科学导论12.3.1u 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为全集，A E，则A的补运算，记作，定义为，AE -AxxExA 或 AxxA (3) 定义：设A与B为集合，A与

10、B的对称差，记作，定义为集合的基本概念与运算AB(AB)(AB )19计算机科学导论12.3.2u 1.笛卡儿积 (1) 序偶由两个元素x和y(关系与函数x =y)按一定的顺序排列成的二元组叫做一个有序对(也称序偶)，记作，其中x是它的第一元素，y是它的第二元素。u 有序对的特点： 当x y时，。 两个有序对相等，即 的充分必要条件是xu且yv。20计算机科学导论12.3.2关系与函数 (2)笛卡儿积设A，B为集合，用A中元素作为第一元素，B中元素作为第二元素，有序对，所有这样的有序对组成的集合叫做A和B的笛卡儿积，记作AB。符号化表示为AB(x,y)|xAyB例 有两个集合Aa,b，B0,1

11、,2，则AB,BA,21计算机科学导论12.3.2关系与函数u 2.二元关系(1) 二元关系定义如果一个集合为空集或者它的元素都是有序对，则称这个集合是一个二元关系，一般记作R对于二元关系R，如果有序对R，则记作x R y设A,B为集合，AB的任何子集所定义的二元关系称作从A到B的二元关系，特别当AB时，则叫做A上的二元关系22计算机科学导论12.3.2 关系与函数u 3种特殊的关系： 其中之一就是空集，称做空关系。 另外两种就是全域关系EA和恒等关系IA。 对任何集合A，EAxAyAAA IAxA23计算机科学导论12.3.2u (2) 关系的表示 通常用关系图来表示一个关系。关系与函数例A

12、=1,2,3,4，R=,，可以画出如下的关系图。24计算机科学导论12.3.2关系与函数u (3) 关系的基本运算Dom(R)x $y(R)Ran(R)y | $x(R) F的逆记作：|F。 F与G的左复合记作GF ，GF $z(GF) F与G的右复合记作F G，FG $z(FG)25计算机科学导论u(4) 关系的性质自反性若对于任意x属于集合A，都有x A R ，那么，就说R在A 上是自反的。反自反性若对于任意x属于集合A，都不存在x A R ，那么，就说R在A上是反自反的。对称性若对于任意x,y属于集合A，都有x, y A R R，那么，就称R为A上的对称关系。称性若对于任意x,y属于集合

13、A，都不存在 R R，那么，就称R为A上的称关系。例如A上的全域关系，恒等关系，空关系都是A上的对称关系。而恒等关系和空关系也是A上传递性称关系。若对任意的x,y,z都属于集合A，假如都存在 x, y, z A R R R，那么，就称R为A上的传递关系。26计算机科学导论12.3.2关系与函数u (5) 两类重要的二元关系 等价关系设R为非空集合A上的二元关系，若R具有自反性、对称性和传递性，则称R为A上的等价关系。利用等价以对一些对象进行分类。例如，集合上的恒等关系即是等价关系。 偏序关系设R为非空集合A上的二元关系，若R具有自反性、 称性和传递性，则称R为A上的偏序关系，偏序关系可以记为。

14、集合A和A上的偏序关系R一起叫做偏序集，记为(A,)，如果有(a,b)R，可以表示为ab 。根据偏序以画出关系图，通常称为。27计算机科学导论12.3.2关系与函数例 已知为偏序集，集合A=a,b, c,d,e,f，关系=(b,a),(d,b),(c,a), (e,c),(e,b),(d,a),(e,a)，画出关系的。解：按照偏序集的规则，可以得到如下28计算机科学导论12.3.2关系与函数u 4.函数函数(Functions)也称(Mapping)。函数也是一种二元关系，与普通的二元关系相比，函数可以看作是一种特殊的二元关系。 (1) 函数的定义设F为二元关系，若对于任意的x，都存在惟一的让

15、xFy成立，则称F为函数。对于任意函数F， 如果都有xFy，则记做，并称y为F在x上的值。29计算机科学导论12.3.2u (2) 特殊函数 函数的性质 设函数f :AB若对于任何的x1,x2A，x1x2，都有f(x1)f(x2)，则关系与函数称f是的。 若Ran(f)B，则称f是。的，则称f是 若f既是的，又是的。30计算机科学导论12.3.2关系与函数 复合函数设f是从集合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的函数，对

16、于yY，都分派一个惟一的xX和它对应，使得f(x)=y 。f的反函数记作：f 1: YX，即f 1(y)=x。31计算机科学导论12.4代数结构12.4.1代数结构概述u 1.运算的定义及性质 （以二元运算为例）设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)，则称运算 在S上满足结合律。32计算机科学导论12.4.1代数结构概述 (3) 设 S上的二元运算，如

17、果对于任意的xS有x x=x则称运算 在S上满足幂等律。 (4) 设 和*为S上两个二元运算，如果对于任意的x,y,zS，有x*(y z) (x*y) (x*z)(左分配律)(右分配律)(y z)*x (y*x) (z*x)则称运算*对运算满足分配律。 (5) 设 和*为S上两个可交换的二元运算，如果对于任意的x,yS，都有x *(x y)xx (x *y)x 则称运算和*满足吸收律。33计算机科学导论u 2运算中的特殊元素集合中有些元素在运算过程中具有特殊的性质，它们 是集合运算中的特殊元素。 (1)元。设*为S上的二元运算，如果元素eS且对任意元素xS，有x*e=e*x=x则称e为S上关于

18、*运算的元，且唯一。 (2)零元。设*为S上的二元运算，如果元素OS且对任 意元素xS，有x*O=O*x=O则称O为S上关于*运算的零元，且唯一。 (3)逆元。设*为S上的二元运算，eS为运算*的 对于元素xS，且对任意元素yS，有元。x*y=y*x=e则称y为x的逆元。34计算机科学导论12.4.1代数结构概述u 3.代数结构的定义代数结构通常指由以下三个部分组成的数学结构：一个非空集合S，称为代数结构的载体。S上的若干运算。一组刻画载体S上各运算所满足性质的公理。通常，代数结构用一个多元序组来表示，其中，S是载体， ，*，为各种运算。有时，S中地位比较特殊的元素(如也会被列入这个多元组的末

19、尾。元、零元、逆元)例如，以自然数集N为载体，“+”运算可以作为二元运算组成一个代数结构，记为。35计算机科学导论12.4.2格与布尔代数u 1.格 (1)格的定义：有序集称为格(lattice)，如果A的任何两个元素的子集都有上确界和下确界。通常，用ab表示a,b的上确界，用ab表示a,b的下确界。(b)(a) 格36计算机科学导论12.4.2格与布尔代数 (2)分配格称格为分配格，如果它满足分配律，即对任意a,b,cA,a(bc)=(ab) (ac)a(bc)=(ab) (ac)37计算机科学导论12.4.2格与布尔代数 (3)有界格格称为有界格，如果A中既有上确界1，又有下确界0。则，0

20、和1称为A的界。对于A中的一个元素a，如果有 ab =1，ab=0则称b为a 的补补。记为a。如果A中的每个元素都有补元，则有界格称为有补格。38计算机科学导论12.4.2格与布尔代数u 2.布尔代数的定义定义：代数系统称为布尔代数，如果 B满足以下条件： 运算，满换律。 运算对运算满足分配律，运算对运算也满足分配律。 B有运算元1和运算零元0、运算元0和运算零元1。 对B中的每一个元素a，均存在元素a，使aa=1， aa=039计算机科学导论12.5图论12.5.1图的基本概念u 1图的由来 哥七桥问题40计算机科学导论12.5.1图的基本概念u 2.图的基本概念(1) 图的定义图(grap

21、h)G由三个部分所组成： 非空集合V(G)，称为图G的节点集，其成员称为节点或顶点(nodes or vertices)。 集合 E(G)，称为图G的，其成员称为边(edges)。 函数(G):E(G)(V(G)，V(G)，称为边与顶点的关联(associatve mapping)。41计算机科学导论12.5.1图的基本概念u (2) 关于图的概念设图G为 当V和E为有限集时，称G为有限图，否则称G为无限图。在此只讨论有限图。 当G为，称G为；当G为非，称G为重图，又称满足(e1) = (e2)的不同边e1、e2为重边，或平行边。 当(e)(v,v)(或)时，称e为环(loops)。无环。当G

22、为有限简和重边的无向称为简时，也常用(n,m)表示图G，其中n = V，m = E 。42计算机科学导论12.5.1图的基本概念 在G中，(e)(u,v)(或)时，也用(u,v)(或)表示边e，这时称u,v邻接e, u,v是e的端点(或称u为e的起点，v为e的终点)；也称e关联结点u,v 。不是任何边的端点的节点称为孤立结点，仅由孤立结点构 成的图(E = )称为零图。43计算机科学导论12.5.1图的基本概念u (3) 结点的度 定义：在无，结点v的度(degree)d(v)是v作为边的端点的数目。在有，结点v的出度d +(v)(out-degree)是以v作为有向边起点的数目，v的入度d

23、-(v)(in-degree)是v 作为有向边终点的数目。结点的度是v的出度与入度之和。44计算机科学导论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 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,

24、 , l-1 )各不相同时，该拟路径称为路径(walk)，又当v i(i = 1,2, ,l)各不相同时(除v1与v1)，则称此路径为通路(Path)。v1v1 的路径称为闭路径(closed walk)；v1= v1的通路称为回路(circuit)。45计算机科学导论12.5.2 定义：称无路径、回路及连通性G是连通的(Connected)，如果G的任何两个顶点都是相互可达的。 定义：称有G是强连通的，如果G的任何两个G是单向连通的，顶点都是相互可达的；称有如果G的任何两个顶点中，至少从一个顶点到另一G是弱连通的，如果G是连通的。个顶点是可达的；称有的有向边被看作无(a) 强连通图(b) 单

25、向连通图(c)弱连通图46计算机科学导论12.5.3图的矩阵表示 (1)关联矩阵47计算机科学导论12.5.3图的矩阵表示 (2) 邻接矩阵48计算机科学导论12.6离散概率概率(Probability)在推理过程中具有非常重要的作用，它通常用来衡量发生的可能性的大小，或者说用来衡量人们期待的占总体的比例u 离散概率(Discrete Probability)的一些基本知识： 定义：概率试验通常指人们对随机现象的结果进行的过程，通常记为E。观察、 定义：样本空间指的是概率试验的所有结果的集合，通常记为S。样本空间中的每个元素分别称为样本点。如果样本空间含有有限个或可数的离散的样本点， 该样本空间就是离散样本空间。 同一个概率试验可以有不同的样本空间。49计算机科学导论12.6离散概率 定义：离散样本空间S的任意子集，称为S