[理学]第二章 关系ppt课件

1、第二章 关系 本章将研究集合内元素之间的关联以及集合之间元素的关联，这就是“关系 “关系是很重要的根本数学概念，它在各数学领域中均有很大的作用，并且对研究计算机科学中许多问题都是很好的数学工具2.1 关系的根本概念 定义2.1 从集合A到集合B的一个关系关系R是A与B的笛卡尔积AB的一个子集 关系R中有序偶第一个客体所允许选取对象的集合称为关系R的定义域，记以DR，第二个客体所允许选取对象集合称为关系R的值域，记以CR 在特殊情况下，当DR=CR=M时，M为一集合，此时称为关系为M上的关系 例：实数集R上的“关系可以定义为： = x,y | xR, yR,且xy2.1 关系的根本概念 假如从X

2、到Y不存在某种关系R，那么称这种关系为空关系空关系，假如从X的每个元素到Y的每个元素之间均具有某种关系，那么称此关系为全关系全关系. 从X到Y的全关系即XY. 定义2.2 由集合X1、X2、Xn所确定的的n元关系元关系是X1X2Xn的一个子集2.1 关系的根本概念 大型的计算机构造中或一个大型软件构造中所谓的内部逻辑关系复杂，所指的“逻辑关系就是这里的“关系，只要把这些构造内的关系搞清，那么任何构造的“正确性“可靠性就迎刃而解了.2.1 关系的根本概念 关系的图的表示法 一个集合X=x1,x2,xn上的关系可用一关系图表示之.集合X中元素可用图中结点表示；关系R的有序偶xi,xj可用图中从结点

3、xi到xj的有向边表示。 例：010000000001100100000010010000000000RM2.2 关系的运算 关系的交、并、补、差 关系是特殊的集合 有关集合的交、并、补、差在关系中也适用，有关集合运算的一些公式在关系中也适用2.2 关系的运算 复合运算 定义2.3 设R是一个从X到Y的关系，S是一个从Y到Z的关系，那么R与S的复合关系：RoS=x,z | xX,zZ,至少存在一个yY有x,yR且y,zS计算方法：1从定义入手2有向图法3布尔矩阵R SRsMMM2.2 关系的运算 定理复合运算满足结合律： 设R、S、T分别表示从X到Y、Y到Z、Z到U的关系，那么有RoS oT

4、= RoSoT = RoSoT 定义2.4设有一个集合X上的关系R，那么Rn可定义如下：1R1=R2Rn+1=RnoR故，RmoRn=Rm+n Rmn=Rmn2.2 关系的运算 例：设R和S是集合X=0,1,2,3上的关系，有R=x,y | j=i+1 或 j=i/2S=x,y | i=j+2求 RoS，SoR 解：R=0,1,1,2,2,3,0,0,2,1S=2,0,3,1RoS=1,0,2,1SoR=2,1,2,0,3,22.2 关系的运算 例：设有X上的关系R1,R2,R3，试证：如R1R2，那么R1oR3R2oR3 证明：对任意a,cR1oR3，存在bX，使得a,bR1且b,cR3由于

5、R1R2，所以存在bX，使得a,bR2且b,cR3，于是a,c R2oR3因此R1oR3R2oR32.2 关系的运算 逆运算是一种一元运算，其结果组成的关系，称关系的逆关系. 定义2.5 设R是一个从X到Y的关系，即R=x,y | xX,yY，那么从Y到X的关系称为R的逆关系. 例：R=1,a,2,b,3,cRR( , ) ( , )Ry xx yR=(a,1),(b,1),(c,1)2.2 关系的运算 定理 设R，S分别是从X到Y及Y到Z的关系，那么有12345R=R(R S)=S RRS=RSRS=RSRS=S R2.3 关系的重要性质 自反性 反自反性 对称性 反对称性 传递性2.3 关

6、系的重要性质 定义2.6 在集合X上的关系R，如对任意xX，有x,xR,那么R是自反自反的 定义2.7 在集合X上的关系R，如对任意xX，有x,x R,那么R是反自反反自反的例：在整数集Z上的关系，“是自反的，不是反自反的；“是反自反的，不是自反的。在集合X=1,2,3,4上的关系R：R=1,1,2,1,3,4,4,2既不是自反的也不是反自反的2.3 关系的重要性质 一个关系的自反性在图形表示法中相当于一个关系图中的每个结点均有环出现 而一个关系的反自反性相当于一个关系图中的每个结点均无环出现2.3 关系的重要性质 定义2.8 在集合X上的关系R，假如有x,yR,必有y,xR，那么称R是对称对

7、称的 定义2.9 在集合X上的关系R，假如有x,y R且xy,必有y,x R，那么称R是反对称反对称的 例例：有一些人的集合中“同事关系是对称的，“父子关系那么是反对称的。 在集合X=1,2,3,4上的关系R：R=1,2,2,1,3,4,4,2既不是对称的也不是反对称的2.3 关系的重要性质 关系的对称性在图形表示中相当于关系图中两个结点间如有有向边相连，那么一定有方向相反的两条有向边连接 一个关系的反对称性相当于关系图中两个结点间如有有向边相连那么一定只有一条边2.3 关系的重要性质 定义2.10 在集合X上的关系R，假如有x,yR且y,zR，那么必有x,zR,那么称R是传递传递的 例： 在

8、一些人的集合上，“同事关系是传递的，但“父子关系不是传递的 整数集Z上的“、“都是传递的 一些城市所组成的集合上，“线路的连通关系是传递的2.3 关系的重要性质 注意： 一个关系可以 既不是自反的，又不是反自反的； 即是对称的，又是反对称的； 根据定义，一个有序偶的第一元素和第二元素假如可以交换且存在反对称关系的话，那么第一和第二元素应该一样 但是传递与非传递不能同时存在 传递意为假如有a,b,b,c就应该有a,c,假如没有a,c就是非传递，一个关系要么是传递的要么是非传递的，两者只能居其一，而假如没有a,bb,c出现的情况也归为满足传递性。2.3 关系的重要性质 一个集合X上的关系可能具有上

9、述5个性质中的假设干性质. 全关系是自反的、对称的，传递的 空关系是反自反的、对称的、反对称的，传递的 例：设集合A=a,b,c,d，断定以下关系具有什么性质1R1=a,a,b,a2R2=c,d3R3=a,a,b,b,c,c 例：集合A=1,2,10的关系R=x,y x+y=10且x,yA，那么R具有什么性质？ 解：R=1,9,2,8,3,7,4,6,5,5,6,4,7,3,8,2,9,1 R是对称的反对称的，传递的反自反的，反对称的，传递的自反的，对称的，反对称的，传递的2.3 关系的重要性质 例：试判断图中关系的性质 a b c 解: a R是对称的，非传递的b R是反自反的，对称的，非传

10、递的c R是自反的，反对称的，非传递的abcabcabc2.3 关系的重要性质定义定义集合集合关系图关系图关系矩阵关系矩阵自反的自反的任取aA有a,aRIA R图中每个结点都有自回路主对角线上全为1反自反的反自反的任取aA有a,a RRIA=图中每个结点都无自回路主对角线上全为0对称的对称的假设a,bR,那么a,bRR=R-1任意两个不同的结点要么没有弧，要么有方向相反的一对弧对称阵反对称的反对称的假设a,b R, a,b R,那么a=b RR-1IA任意两结点间至多有一条弧反对称阵传递的传递的假设a,b R, b,cR,那么a,cRRoRR假设a到b有弧,b到c有弧,那么a到c有弧-2.4

11、关系上的闭包运算 定义2.11 设R是集合X上的一个关系，那么R的自反对称、传递闭包闭包是一个满足以下条件的关系R：1R是自反的对称的、传递的 ；2RR；3设R是自反的对称的、传递的且RR，那么必有RR.通常用 rR表示R的自反闭包sR表示R的对称闭包tR表示R的传递闭包2.4 关系上的闭包运算 例： 整数集Z上的“关系的自反闭包是“关系；对称闭包是“关系；传递闭包是它本身。 定理： 设R是集合X上的关系，那么rR=RUQ，其中Q=x,x | xXsR=RUtR= =RUR2UR3U设X是有限集，并设X有n个元素，那么tR=R1Rii1Rnii2.4 关系上的闭包运算 例例：设集合A=a,b,

12、c,d，定义R=a,b,b,a,b,c,c,d，求rR，sR，tR 解：rR=RUQ=a,a,b,b,c,c,a,b,b,a,b,c,c,dsR=RU =a,b,b,a,b,c,c,b,c,d,d,ctR=RUR2UR3UR4=a,b,b,a,b,c,c,d U a,a,a,c,b,b,b,d U a,b,a,d,b,a,b,c U a,a,a,c,b,b,b,d =a,a,b,b,a,b,a,c,a,d,b,a,b,c,b,d,c,d R2.4 关系上的闭包运算 例：设有X上的关系R1,R2, 且R1R2,试证 1 rR1rR2 2 sR1sR2 3 tR1tR2 证明：1 因为R1R2,

13、所以R1ER2E, 即rR1=rR2 2 因为R1R2, 所以 所以 , 即sR1=sR2 3 对任意的nN, 根据数学归纳法可知： 又因为tR=RUR2UR3U, 所以tR1tR212RR1122RRRR1122RRRRnn2.4 关系上的闭包运算 集合A上的二元关系R的闭包运算可以复合，例如tsR=tsR表示R的对称闭包的传递闭包，可以简称为R的对称传递闭包。tsrR那么表示R的自反对称传递闭包。 定理：设R是集合A的二元关系，那么有1 假如R是自反的，那么sR和tR也是自反的；2 假如R是对称的，那么rR和tR也是对称的；3 假如R是传递的，那么rR也是传递的4 rsR=stR5 rtR

14、=trR6 tsRstR2.5 次序关系 定义2.12 集合X上的关系R假如是自反的、反对称的、传递的，那么称R在X上是偏序偏序的或称R是集合X上的偏序关系。而称集合X为R的偏序集偏序集用X,R表示. 一般用符号“表示偏序有时我们用xy表示xy,且xy 例： 由集合A所组成的幂集A上的关系“是自反的、反对称的，又是传递的，所以它是偏序的2.5 次序关系 可比：在偏序集合A,中，元素x,yA，假如xy或yx，x与y是可比的，否那么称它们是不可比的. 盖住：在偏序集合A,中，元素x,yA，xy且没有其他元素zA满足xzy，称y盖住X. A, 上的盖住集CovA定义为CovA=x,y x,yA，y盖

15、住x 例例：集合A=a,b,c，偏序集合A, 中，判断A的以下子集是否盖住a? 1 2 b,c 3 a,b 4 a,b,c2.5 次序关系 定义2.13 集合X上的关系R假如是反自反的、传递的，那么称R在X上是拟序的或称R是集合X上的拟序关系拟序关系. 一般用符号“表示拟序 例： 由集合A所组成的幂集A上的关系“是拟序的2.5 次序关系 定理： 假如集合X上的关系R是拟序的，那么其必是反对称的 偏序是拟序的扩大而拟序是偏序的缩减 定理： 设R是集合X上的关系1假如R是一个拟序关系，那么rR=RUQ是一个片序关系2假如R是一个偏序关系，那么R-Q是一个拟序关系2.5 次序关系 定义2.14 设R

16、是集合X上的偏序，假如对每个x,yX必有xy或yx，那么称R是线性次序的也可以叫全序的或称R是集合X上的线性次序关系. 例： 集合X=a,b,c上的关系R=a,b,b,c,a,c,a,a,b,b,c,c是线性次序的. 集合A=a,b的幂集A=,a,b,a,b上的“关系不是线性次序的.2.5 次序关系 字典次序 设有一些抽象字母所组成的集合，这个集合是有限的，成为字母表。在此集合上可建立一个线性次序关系“，由的字母所组成的字母串叫上的字，所有这些字包括空字组成一个集合*，需要在*上建立一个字典次序.2.5 次序关系 定义2.15设是一个有限字母表，上的偏序关系是一个线性次序集，建立*上的字典次序

17、关系L：设x= x1,x2,xn, y=y1,y2,ym ,其中x,y* ; x1,x2,xn, y1,y2,ym .1 x1y1且如x1y1,那么说xLy;如y1x1,那么说yLx;2 如存在一个最大的k且kminn,m,使得x1=y1 ,x2=y2,xk=yk ,而xk+1yk+1,假如xk+1yk+1 ,那么说xLy;如yk+1xk+!,那么说yLx;3 假如存在一个最大的k=minn,m,使得x1=y1 ,x2=y2,xk=yk ，此时如nm,那么说xLy;如mn那么说yLx.2.5 次序关系 定义2.16设集合X有一个偏序关系“且设Y是X的一个子集，那么1 假如存在一个元素yY对每个

18、y Y均有yy，那么称y是Y的最大元素最大元；假如均有yy，那么称y是Y的最小元素最小元;2 假如存在一个元素yY且在Y中不存在元素y有yy且yy，那么称y是Y的极大元素极大元；假如Y中不存在元素y有yy且yy，那么称y是Y的极小元素;2.5 次序关系3 假如存在一个元素xX，对每个yY均有y x，那么称x是Y的上界；假如均有xy，那么称x是Y的下界.4 假如xX是Y的上界且对每一个Y的上界x均有xx，那么称x是Y的上确界；假如xX是Y的下界且对每一个Y的下界x均有xx，那么称x是Y的下确界.2.5 次序关系 定理：设集合X上有一个偏序关系“且设Y是X的一个子集，那么1 假如y是Y的最大小元素

19、，那么它亦必是Y的极大小元素；2假如y是Y的最大小元素，那么它亦必是Y的上下确界；3 假如x是Y的上下确界，且xY，那么x必是Y的最大小元素.2.5 次序关系 哈斯Hasse图： 对一个X上的偏序关系，对其X中的每个元素可用结点表示. 如x,yX，且x y，那么在图中将结点x画于结点y的下面，如x与y间不存在另一个z有x z，z y x,yCovX，那么在x与y间用一线连接，由此所得到的图即为哈斯图。 哈斯图对寻找最大小元素、极大小元素、上下界、上下确界有明显的作用。 极大元: 12, 20, 25 极小元: 2, 5122042105252.5 次序关系 Hasse图也可在原偏序的关系图上通

20、过以下步骤得到：1 先画出偏序关系图，并要求所有箭头朝上;2 移去所有自回路;3 删除所有可以由传递性导出的边;4 删除所有箭头 例：设A=a,b，画出偏序集合A, 的哈斯图a,baba,bab2.5 次序关系 例：A=1,2,12, 为A上的整除关系, 请画出A, 的哈斯图，求B=2,4,6, C=4,6,9, D=1,2,5,10的特殊元素.151081269411372极小元极大元最小元最大元上界下界上确界下确界B=2,4,624,62-121,2122C=4,6,94,6,94,6,9-1-1D=1,2,5,101101101011012.6 相容关系 定义2.17 一个在X上的关系R

21、，假如它是自反的、对称的，那么称此关系为相容关系. 相容关系一般用“表示相容关系的关系矩阵是对称的且对角线上诸元素均为1，因此仅给出矩阵的下部三角形部分就够了相容关系的有向图中的边均是双边的且均有环出现，可以简化为一根无方向的线。2.6 相容关系 定义2.18设有集合X上的相容关系，设A是X的子集，如A中任何元素都互为相容，且X-A中的任何元素没有一个与A中的所有元素相容，那么称A是X中的极大相容性分块.从图上看，就是“最大完全多边形 定义2.19设有X上的相容关系，它的极大相容性分块的集合称为X的完全覆盖. 定理：X上的每个相容关系，唯一的定义一个完全覆盖2.6 相容关系 例：设A=a,b,

22、c,d，A上的二元关系为R=a,a,a,b,b,a,a,d,d,a,b,b,c,c,d,d, 写出R的关系矩阵，断定R是否是A上的相容关系，假如是，请写出A上的完全覆盖. 解：R的关系矩阵为：根据MR的主对角线元素全为1，知R是自反的；又根据其余的1与主对角线有对称性，知R是对称的，故R是A上的相容关系.A上的完全覆盖是：a,b,a,d,c1101110000101001RM2.7 等价关系 定义2.20一个在X上的关系R假如它是自反的、对称的、传递的，那么称此关系为等价关系. 定义2.21设S是一个集合， A1,A2,Am是它的子集，假如他们满足以下条件：1 所有Ai间均是别离的，亦即对所有的i,j i=1,2,m; j=1,2,m，如ij，那么Ai Aj = 2 A1A2Am=S那么集合A=A1,A2,Am称为S的一个划分，而A1,A2,An称为这个划分的块.2.