离散数学ppt课件第三章集合与关系.ppt

《离散数学ppt课件第三章集合与关系.ppt》由会员分享，可在线阅读，更多相关《离散数学ppt课件第三章集合与关系.ppt（82页珍藏版）》请在三一办公上搜索。

1、3-7 复合关系和逆关系,二元关系是以序偶为元素的集合，所以可以对它进行集合运算。此外还有一种新的运算：关系的复合定义3-7.1 设R是从集合A到集合B上的二元关系，S是从集合B到集合C上的二元关系，则RS称为R和S的复合关系，表示为 RS=xAzC y(yBRS),复合关系举例,例：A=1，2，3，4，B=3，5，7，C=1，2，3R=，S=，则 RS=，如图所示：,复合关系的结合律,定理：设R1 A1 A2,R2 A2 A3,R3 A3 A4,则(R1R2)R3=R1(R2R3)。,例：设A=1,2,3,4,5 A上的二元关系R=,S=,则 RS=,SR=,RS(RS)R=R(SR)=,复

2、合关系的矩阵表示（自学）,两个关系的复合可通过相应矩阵相乘获得。,复合关系练习,练习：R是A上的二元关系，试证R是传递的充要条件是RRR,证：RR 必y使得 R，R R是传递的 R RRR：R,R 必有R R R RR R 由x,y,z任意性知 xyz(RRR)R是传递的,逆关系,定义3-7.2 设R是A到B的二元关系，则R的逆是B到A的二元关系，记为Rc，其中Rc=|R。注：（1）xRyyRcx（2）互换R的关系矩阵的行和列，即得Rc的关系矩阵。即 MRcMRT（3）颠倒R的关系图中每条弧线的箭头方向，即得Rc的关系图。,逆关系举例,例1 整数集上的 关系 集合族上的 关系的逆是 空关系的逆

3、是空关系 AB的全域关系的逆是BA的全域关系例2 A=0,1,2,3，R=,则 Rc=,定理,定理：设R,R2,R1是A到B的关系，则a）(Rc)c=Rb）(R1R2)c=R1cR2cc）(R1R2)c=R1cR2d）(R)c=(Rc),R=AB-R 即R的补的逆等于逆的补e）(R1-R2)c=R1c-R2cf)(AB)c=BA,定理,定理3-7.2 设R、S分别是A到B、B到C的关系，则(RS)c=Sc Rc,证：设 是(RS)c 的任一元素，则(RS)c RS b(RS)b(c,bScRc)Sc Rc,定理,定理3-7.3 R是A上的二元关系(a)R是对称的 R=Rc(b)R是反对称的 R

4、RcIA,证：(a)：任取R，因为R是对称的，所以RRR c：任取R，则Rc R=Rc R R是对称的(b)略,3-8 关系的闭包运算,设R是A上的关系，我们希望R具有某些有用的性质，比如说自反性。如果R不具有自反性，我们通过在R中添加一部分有序对来改造R，得到新的关系R，使得R具有自反性。但又不希望R与R相差太多，换句话说，添加的有序对要尽可能的少。满足这些要求的R就称为R的自反闭包。通过添加有序对来构造的闭包除自反闭包外还有对称闭包和传递闭包。,各种闭包的定义,定义3-8.1 设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R，使得R满足以下条件：（1）R是自反的（对称的或

5、传递的）（2）R R（3）对A上任何包含R的自反（对称或传递）关系R”，有 R R”。一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。,注：R的自反闭包记为r(R),若R是自反的，则R=r(R),反之也成立。R的对称闭包记为s(R),若R是对称的，则R=s(R),反之也成立。R的传递闭包记为t(R),若R是传递的，则R=t(R),反之也成立。,构造闭包的方法,下面的定理给出了构造闭包的方法：自反闭包 r(R)=RIA 对称闭包 s(R)=RRc 传递闭包 t(R)=RR2R3,证明 r(R)=RIA,证：设R=RIA xA,R R具有自反性 RR 设R”是自反的，且

6、RR”R是自反的，IAR”又RR”R=IARR”综上所述，R满足自反闭包定义的三个条件，r(R)=R=RIA,证明 s(R)=RRc,证明：设 R=RRc Rc=(RRc)c=Rc(Rc)c=RcR=R，所以R是对称的 R=RRcR 设R”是对称的，且RR”，要证 RR”任取RRcRRc R”R R”R”R”R”R”R=RRcR”综上所述，由定义知道，R即RRc为R的对称闭包。,证 t(R)=RR2R3(R为A上的二元关系）,证：(1)证 t(R)：先用归纳法证，对n0,Rn t(R)a)由定义 R t(R)b)设Rn t(R)成立，要证Rn+1 t(R)任取Rn+1=RnR，存在cA,使Rn

7、,R 由归纳假设和基础步骤知 t(R)，t(R）t(R)是传递的，t(R)即 Rn+1 t(R)对一切n，Rn t(R),根据的结论，证 t(R)：任取 存在一个n，使Rn t(R)t(R)t(R),(2)证 t(R)设,是 的任意元素 必s,t,使得Rs,Rt RtRs=Rt+s 是传递的 t(R)是包含R的最小传递关系 t(R)由（1），（2）得 t(R)=,闭包运算举例,题：设A=a,b,c,R是A上的二元关系，且给定R=,求r(R),s(R),t(R)。解：r(R)=R IA=,s(R)=R Rc=,t(R)=RR2R3=RR2R3（因为R4=R,R5=R2,R6=R3,)=,定理3-

8、8.5 设R为X上二元关系，X=n，那么，存在一个正整数kn，使得 t()=R R2 R3.Rk例：P123例题2,求R+的算法Warshall算法,例：P124例题3,P125例题4,设有一字母表V=A,B,C,D,e,d,f并给定下面六条规则：A-Af,B-Dde,C-e,A-B,B-De,D-Bf R为定义在V上的二元关系且xiRxj，即是从xi出发用一条规则推出一串字符，使其第一个字符恰为xj。说明每个字母连续应用上述规则可能推出的头字符。,闭包运算的性质,设R为集合X上的任一二元关系，那么 a)rs(R)=sr(R)自反对称闭包等于对称自反闭包 b)tr(R)=rt(R)传递自反闭包

9、等于自反传递闭包 c)ts(R)st(R)传递对称闭包包含对称传递闭包,证明 rs(R)=sr(R),证：rs(R)=r(s(R)=r(RRc)=IxRRc=IxRRcIx=(IxR)(RcIxc)=(IxR)(RIx)c=s(IxR)=sr(R),证明 rt(R)=tr(R),证：rt(R)=r(RR2)=IXRR2 tr(R)=t(RIX)=IXR(IXR)2(IXR)n=IXRR2Rn rt(R)=tr(R),注：以上证明引用了公式：（证明略）(RIX)n=IXRR2Rn,证明st(R)ts(R),证：先证R对称t(R)对称t(R)-1=(RR2R3)-1=R-1(R2)-1(R3)-1

10、=R-1(R-1)2(R-1)3(FG)-1=G-1F-1，定理3-7.2)=R R2 R3=t(R)t(R)对称.因为 R s(R),故 st(R)st(s(R)而st(s(R)=sts(R)=s(ts(R)=ts(R)st(R)ts(R).,注：st(R)ts(R)未必成立。反例：设R=,则s(R)=,t(s(R)=,s(t(R)=s,=,t(s(R),注意：先做传递，再做对称，有可能破坏传递性。,3-9 集合的划分和覆盖,除了把两个集合相互比较外，还常把一个集合分成若干子集讨论。定义3-9.1 设A为非空集，S=S1Sm,SiA，Si(i=1m)且S1S2.Sm=A，称S是A的覆盖.若再

11、加SiSj=(i,j=1m,ij)则称S是A的划分,m称为划分的秩。,集合的划分和覆盖举例,例1 设A=1,2,3,4,5，下面哪些是覆盖，哪些是划分：(1)X=1,2,3,4,5(2)Y=1,2,2,3,4,5(3)Z=1,2,3,4(4)U=1,2,3,4,5(5)V=1,2,3,4,5 U称为A的最小划分，V称为A的最大划分。,交叉划分,定义3-9.2 若S1=A1Am,S2=B1Bn是A的二个划分,则 S=AiBj|AiS1BjS2 称为A的交叉划分。定理3-9.1 设 A1,A2,Am与B1,B2,Bn为同一集合A的两个划分。则其交叉划分AiBj亦是原集合的一种划分。,交叉划分举例,

12、例：设B是所有生物的集合,可划分成A,P,其中A表示所有动物Animal的集合,P表示所有植物Plant的集合。B也可划分成 F,L,其中F表示史前First生物,L表示史后Last生物。它们的交叉划分为:D=AF,AL,PF,PL,其中AF是史前动物,AL是史后动物,PF是史前植物,PL是史后植物。,加细,定义3-9.3 设S,S是集合A的二个划分，若S的每一块均是S中某块的子集，S是S的加细。例:A=正整数集 S=1,3,5,7,2,4,6 S=1,5,9,3,7，11,2,4,6则 S是S的细分定理3-9.2 任何两种划分的交叉划分，都是原来各划分的一种加细。,练习：3-9（2）,证明：

13、1.aA，a与a在同一分块中，故必有aRa。故R是自反的。2.若a与b在同一分块中，b与a也必在同一分块中，即 aRb bRa，故R是对称的。3.若a与b在同一分块中，b与c在同一分块中，根据划分的定义，b属于且仅属于一个分块，故a与c必在同一分块中。即 aRb bRc aRc，故R是传递的。,3-10 等价关系与等价类,等价关系是一类重要的二元关系。定义3-10.1 若集合A上的二元关系R是自反的，对称的和传递的，称R是等价关系。若R是等价关系，aRb，可读为“a等价于b”。例如，数中的相等关系，是等价关系 集合中的相等关系，是等价关系 命题演算中关系，是等价关系 全域关系是等价关系，空集上

14、任何关系是等价关系。,等价关系举例,例：设A=1,2,8，如下定义A上的关系R：R=|x，yAxy(mod 3)其中xy(mod 3)叫做模3同余，即x除以3的余数与y除以3的余数相等。不难验证R为A上的等价关系，因为 xA，有xx(mod 3)，x，yA，若xy(mod 3)，则有yx(mod 3)，x，y，zA，若xy(mod 3)，yz(mod 3)，则有xz(mod 3)。该关系的关系图如下：,等价关系举例（续）,不难看出，上述关系图被分为三个互不相连通的部分。每部分中的数两两都有关系，不同部分中的数则没有关系。每一部分中的所有的顶点构成一个等价类。,等价类,定义3-10.2 设R是A

15、上的等价关系，对aA，集合aR=x|xRa称为a关于R的等价类，简记为a，a 称为等价类aR的表示元素。从以上定义可以知道，a的等价类是A中所有与a等价的元素构成的集合。上例中的等价类是：1=4=7=1,4,72=5=8=2,5,83=6=3,6,例：设I是整数集，R是模3同余关系，即R=|xIyIxy(mod3)不难验证R是等价关系，其等价类为 0R=-6,-3,0,3,6 1R=-2,1,4 2R=-4,-1,2,5 等价类的每一元素均可作本等价类的表示元素。,定理3-10.1 设给定集合A上的等价关系R，对于a,b A 有 aRb iff aR=bR 证：aaR=bR 根据等价类定义 a

16、Rb aRb xaR xRa xRb xbR 由x的任意性知，aR=bR,商集,定义3-10.3 集合A上的等价关系R，其等价类集合aR|a A，称为A关于R的商集，记为A/R。例1：A=1,2,8，R=|x，yAxy(mod 3)则A/R=1,4,7,2,5,8,3,6 例2：A为正整数集合，R是模3同余关系，则A/R=0R,1R,2R，其中 0R=-6,-3,0,3,6 1R=-2,1,4 2R=-4,-1,2,5,显然：商集是集合的集合。商集的每个元素是等价关系的一个等价类。等价类中的每个元素都是集合A上的元素。同一等价类中的任意两个元素都具有关系R。,商集举例,例：设集合S=a,b,c

17、,d,e,f,g，S上的等价关系R如下表所示，求商集S/R。,S/R=a,b,c,d,e,f,g,思考：R=?,根据等价类对集合进行划分,定理3-10.2 集合A上的等价关系R决定了A的一个划分，即为商集A/R。,证明 A/R=aR|aA（1）根据等价类定义，aA，aR A aR A aA，aRa aaR A aR aR=A A/R是一个覆盖,根据等价类对集合进行划分,（2）证：需证 a,bA，若aRbR，则 aRbR=。反证法：若aRbR 则caRbR cRa 且 cRb R是对称、传递的 aRb 则 aR=bR，这与前提矛盾。由（1），（2）得A/R是一个划分。,定理3-10.3 集合A的

18、任一划分S确定了A的一个等价关系R。,证明 设S=S1，S2，Sm（构造性证明）定义关系R:aRb当且仅当a,b在S的同一块中，现证R是等价关系。(1)aA，a与a在同一块中 aRa，自反性成立。(2)a,bA，若aRb，则a与b在同一块中，则b与a也在同一块 bRa，即 aRbbRa 对称性成立,(3)a,b,cA，若aRb，bRc，则a与b在同一块，b与c在同一块 SiSj=(ij)a与c在同一块，即aRbbRcaRc 传递性成立综上所述，R是A的一个等价关系，且A/R=S,定理3-10.3举例,例：A=a,b,c,d,e，S=a,b,c,d,e，求由S确定的等价关系。解：设 R1=a,b

19、a,b=,R2=cc=R3=d,ed,e=,则 R=R1R2R3是由S确定的等价关系。若S=a,b,c,d,e，则由S确定的等价关系是什么？,定理3-10.4 设R1，R2是非空集合A上的等价关系，则R1=R2 A/R1=A/R2。,证明：若R1=R2 A/R1=aR1|aA，A/R2=aR2|aA 则 xaR1 R1 R2 xaR2，aR1 aR2 同理可证，aR2 aR1 aR1=aR2 A/R1=A/R2,：aA，aR1 A/R1 A/R1=A/R2 必 cR2A/R2，使 aR1=cR2 a,bA R1 aaR1baR1 acR2bcR2 R2 R1 R2 同理可证：R2R1 R1=R

20、2综上所述，R1=R2 A/R1=A/R2,例：设和是非空集A的划分,R、R是分别由、确定的等价关系，试证 细分 R R,证：R 则a、b在的同一块中，细分 a、b在的同一块 R R R：设 Si aSi，则 Si=aR=x|xRa xSi xRaxRaxaR aRaR 由 Si的任意性，知 细分 细分 R R,加细（细分）图解,3-11 相容关系,定义3-11.1 设R是集合A上的二元关系，若R是自反的和对称的，称R是相容关系。例：所有等价关系是相容关系；在一群人的集合中,朋友关系也是相容关系。,相容关系的表示方法,因为相容关系是自反和对称的,其关系矩阵是对称的且主对角线元素全为1,因此我们

21、可仅用下三角矩阵T来表示和存储就够了,即关系矩阵可以简化为“阶梯形”。相容关系的关系图可简记为：用无向边代替二有向边 自回路省略,相容关系的表示方法(P135例题),x1,x6,x4,x3,x2,x5,相容关系r的矩阵及图形表示,定义3-11.2 设R是集合A上的相容关系,若CA,若任意a,bC,有aRb,则称C是由R产生的相容类。例：上例相容关系r产生的相容类。,最大相容类,定义3-11.3 设R为定义在集合A上的相容关系，如果不能真包含在任何其他相容类中的相容类，称作最大相容类，记为CR。例：P137例题1,相容关系的确定,利用相容关系的关系图来确定相容类和最大相容类是方便的。极大完全子图

22、的顶点集合就是最大相容类。所谓极大完全子图是指每对顶点都有边相连的多边形,而最大相容类外的任何顶点不可能与类内的所有顶点相连。另外孤立顶点,以及不在极大完全子图两个顶点及其连线,也是最大相容类。,例 设给定的相容关系图表示成下图,写出所有的最大相容类。,解 最大相容类：h,a,b,d,e,f,b,c,d,f,g。,完全覆盖,定义3-11.4 设R为定义在集合A上的相容关系，其最大相容类的集合称作集合A的完全覆盖，记为CR(A)。例1：,A的完全覆盖是：1，2，3，4，5，6，5，2，6，3,3-12 序关系,定义3-12.1 若集合A上的二元关系R是自反的、反对称的和传递的，则称R是A的偏序关

23、系，记作。设 为偏序关系，如果，则记作x y，读作“小于或等于”。序偶称为偏序集合。注意这里的“小于或等于”不是指数的大小，而是在偏序关系中的顺序性。x“小于或等于”y的含义是：依照这个序，x排在y的前边或者x就是y。根据不同偏序的定义，对序有着不同的解释。例如整除关系是偏序关系，3 6的含义是3整除6。大于或等于关系也是偏序关系，针对这个关系写5 4是说大于或等于4,关系中5排在4的前边，也就是5比4大。,盖住,定义3-12.2 在偏序集中，如果x,yA，x y，x y，且没有其他元素z满足x z、z y，则称元素y盖住元素x。并且把所有具备盖住性质的续偶集合记作COV A，COV A=|y

24、盖住x例：A为正整数m12的因子的集合，并设 为整除关系，求COV A。(P140),哈斯图（偏序集合图）,对于给定的偏序集，它的盖住关系是唯一的，所以可以用哈斯图表示偏序集合图。哈斯图作图规则：用小圆圈代表元素。如果 x y，且x y，则将代表y的小圆圈画在代表x的小圆圈之上。如果 COV A,则在x与y之间用直线连接。,哈斯图举例,例：画出偏序集的哈斯图。,哈斯图举例（续）,例：A=a,b,c，画出 的哈斯图。,哈斯图举例（续）,例：已知偏序集的哈斯图如图所示，试求出集合A和关系R的表达式。,解：A=a,b,c,d,e,f,g,h R=,IA,偏序集中的特殊元素,定义3-12.5,3-12

25、.6 设为偏序集，B是A的子集，yB。若 x(xBy x)成立，则称y为B的最小元。若 x(xBx y)成立，则称y为B的最大元。若bB,且B中不存在任何元素x,使bx且b x 称b是B的极大元。若bB,且B中不存在任何元素x,使bx且x b 称b是B的极小元。,例：设偏序集如图所示，求A的极小元，最小元，极大元，最大元。,解:极小元：a,b,c,g。极大元：a,f,h。没有最小元与最大元。由这个例子可以知道，哈斯图中的孤立顶点既是极小元也是极大元。,解：A不存在最大、最小元；极大元素为d,e,极小元素为a,b；B的最大元素为c，没有最小元素；极大元素为c,极小元素为a,b。,例：设A=a,b

26、,c,d,e、B=a,b,c，则各自的最大最小元素、极大极小元素是哪些？,最小元是B中最小的元素，它与B中其它元素都可比；而极小元不一定与B中元素可比，只要没有比它小的元素，它就是极小元。对于有穷集B，极小元一定存在，但最小元不一定存在。最小元如果存在，一定是唯一的，但极小元可能有多个。如果B中只有一个极小元，则它一定是B的最小元。如果B中存在最小元，则它一定是B的唯一极小元。类似的，极大元与最大元也有这种区别。,定理3-12.1 设是一偏序集合，且BA，若B有最大（最小）元，则是唯一的。证：设a,b都是B的最大元素，那么a b,b a，从偏序关系的反对称性，得a=b。最小元证明情况与此类似。

27、,上界、下界,定义3-12.7，3-12.8 设为偏序集，BA，yA。（1）若 x(xBx y)成立，则称y为B的上界。（2）若 x(xBy x)成立，则称y为B的下界。（3）令Cy|y为B的上界，则称C的最小元为B的最小上界或上确界。（4）令Dy|y为B的下界，则称D的最大元为B的最大下界或下确界。,设为有序集，BA。的哈斯图如下所示。A=a，b，c，d，e，f，g，h，i，j，k,B=a，b，c，d，e，f，g B=h，i，j，k,B,由定义可知，B的最小元一定是B的下界，同时也是B的最大下界。同样的，B的最大元一定是B的上界，同时也是B的最小上界。但反过来不一定正确，B的下界不一定是B的

28、最小元，因为它可能不是B中的元素。同样的，B的上界也不一定是B的最大元。,序关系（注意）,（1）B的最大（小）元素和极大（小）元素必须是子集B的元素，而B的上界（下界）和最小上界（最大下界）可以是也可以不是B的元素。（2）上界和下界可以存在也可以不存在，可以唯一也可以不唯一。（3）极大元素和极小元素可以唯一也可以不唯一。（4）最大元素、最小元素可以存在也可以不存在，但若存在则唯一。（5）对于非空有限偏序集合，其极大元素和极小元素总是存在。,序关系（说明）,1、设是偏序集合，B是A的子集，（a）如果b是B的最大元素，那么b是B的极大元素，且极大元素唯一。（b）如果b是B的最大元素，那么b是B的最

29、小上界。（c）如果b是B的上界且bB,则b是B的最大元素。（对最小元素、极小元素和最大下界也存在类似的关系）2、对来说，它的逆也是一个偏序集合，偏序 的P中的最大元素、极大元素、上界、最小上界，是 P中的最小元素、极小元素、下界、最大下界，反之亦然。,拟序,定义：若集合A上的二元关系R是反自反的、传递的，则称R是A的拟序关系，序偶称为拟序集合。,全序关系,在偏序集合中，BA，若每一a、bB，都有a b或b a,称B为链（即B中任意两元素都有关系）；若B中任意两元素都是无关的，则称是反链。定义3-12.4 在偏序集中，若是链，则称为全序(线序)集合，称为全序(线序)关系。,全序（线序）举例,例：

30、是一全序集合；不是一个全序集合；P=,a,a,b,a,b,c上的包含关系，是全序集。其哈斯图如下：注：全序集合的哈斯图是一竖立的结点序列，每相邻的结点用一条弧连接。,良序,定义3-12.9 任一偏序集合，假如它的每个非空子集，都有最小元素，则这种偏序集合是良序集合。例：n=1,2,3,n,对于小于等于关系来说是良序集合。但不是良序集合。,定理3-12.2 每一个良序集合，一定是全序集合。证明：设是良序集，那么对任意两个元素x,y A可构成子集x,y，必存在最小元素，这个最小元素不是x就是y，因此一定有x y或 y x。,定理3-12.3 每一个有限的全序集合，一定是良序集合。证明：设A=a1,a2,an，令是全序集，现假定不是良序集合，那么必存在一个非空集合B A，在B中不存在最小元素，由于B是一个有限集合，故一定可以找到两个元素x与y是无关的，由于 是全序集，x,yA，所以x,y必有关系，得出矛盾。故是良序集合。上述结论对于无限的全序集合不一定成立。,