离散数学 3-9 集合的划分和覆盖3-10 等价关系与等价类

1、Discrete Mathematics山东科技大学山东科技大学信息科学与工程学院信息科学与工程学院3-8 3-8 关系的闭包关系的闭包关系的自反闭包关系的自反闭包关系的对称闭包关系的对称闭包关系的传递闭包关系的传递闭包一、关系的闭包定义一、关系的闭包定义定义定义3-8.1：设：设R是是X上的二元关系，如果另外有一上的二元关系，如果另外有一个关系个关系R满足：满足：(1)R是自反的是自反的(对称的对称的，传递的传递的)；(2)R R；(3)对于任何自反的对于任何自反的(对称的对称的，传递的传递的)关系关系R，如果，如果有有R R，就有，就有R R。则称关系。则称关系R为为R的自反的自反(对称，

2、对称，传递传递)闭包。记作闭包。记作r(R)，(s(R)，t(R)例：设集合例：设集合X=x，y，z，X上的关系上的关系R=，则，则:自反闭包自反闭包r(R)=，对称闭包对称闭包s(R)=，传递闭包传递闭包t(R)=， 由闭包的定义可以知道，构造关系由闭包的定义可以知道，构造关系R的闭包方的闭包方法就是向法就是向R中加入必要的有序对，使其具有所希望中加入必要的有序对，使其具有所希望的性质。下面定理体现了这一点。的性质。下面定理体现了这一点。二、关系的性质与闭包的关系二、关系的性质与闭包的关系1、定理、定理3-8.1：设：设R是是X上的二元关系，则上的二元关系，则(1)R是自反的，当且仅当是自反

3、的，当且仅当r(R)=R(2)R是对称的，当且仅当是对称的，当且仅当s(R)=R(3)R是传递的，当且仅当是传递的，当且仅当t(R)=R证明证明 只证明必要性必要性: 令R为自反. 由于RR, 并取右方R为S, 以及任何包含R的自反关系 T, 有S T, 可见R满足自反闭包定义, 即r(R) = R. 充分性充分性: 由自反闭包定义R是自反的.二、关系的性质与闭包的关系二、关系的性质与闭包的关系1、定理、定理3-8.1：设：设R是是X上的二元关系，则上的二元关系，则(1)R是自反的，当且仅当是自反的，当且仅当r(R)=R(2)R是对称的，当且仅当是对称的，当且仅当s(R)=R(3)R是传递的，

4、当且仅当是传递的，当且仅当t(R)=R2、定理、定理3-8.2：设：设R是集合是集合X上的二元关系，则上的二元关系，则r(R)=Rx证明：证明：R Rx，Rx是自反的，定义的前两条满足是自反的，定义的前两条满足了。设了。设R”满足满足R R”，R”是自反的，是自反的， Rx，则，则 R或或x。如果。如果 R则由则由R R”， R”。如果。如果x则必有则必有x=y，即，即x，由，由R”的自反性，的自反性，则则 R”，总之均有，总之均有 R”，所以，所以RX R”，满足定义第三条。得，满足定义第三条。得r(R)=Rx。 对关系矩阵而言，对关系矩阵而言，r(R)的关系矩阵只要将的关系矩阵只要将MR的

5、的对角元置对角元置1即可。即可。3、定理、定理3-8.3：设：设R是集合是集合X上的二元关系，则上的二元关系，则s(R)=R Rc。证明：证明：R R Rc满足定义第一条。满足定义第一条。 R Rc R Rc Rc R R Rc，所以，所以R Rc是对是对称的，满足定义的第二条。称的，满足定义的第二条。如果如果R R”，且，且R”是对称的，是对称的， R Rc，则，则 R或或 Rc，如，如 R，由，由R R”，则，则 R”，如，如 Rc则则 R则则 R”，又因又因R”对称，所以对称，所以 R”，所以，所以R Rc R”，满足，满足定义第三条。得定义第三条。得s(R)=R Rc。4、定理、定理3

6、-8.4：设：设R是集合是集合X上的二元关系，则上的二元关系，则 t(R)= R(i)=R R(2) R(3) 证明证明首先证明首先证明 R t(R). 用归纳法证明如下用归纳法证明如下: 基础步基础步: 根据传递闭包定义根据传递闭包定义, R t(R); 归纳步归纳步: 假设假设n1时时Rn t(R), 欲欲证证Rn+1 t(R)令令 x,y X, 则则: x Rn+1yx Rn * Ry ( z)(xRnzzRy) xRnzzRy xt(R)zzt(R)y xt(R)y 因此因此, Rn t(R). 于是于是, Ri t(R).U1iU1iU1i次证次证t(R) Ri, 由于包含由于包含

7、R的传递关系都包含的传递关系都包含t(R)，且且R Ri, 因此只需证明因此只需证明 Ri是传递即可是传递即可. 令令x, y, z X, 则则 x( Ri)yy( Ri)z ( j)(xRjy) ( k)(yRkz) xRjyyRkz xRjy * yRkz xRj+kz x( Ri)z因此因此, Ri是传递的是传递的. 综上可知综上可知, t(R) = Ri.U1iU1iU1iU1iU1iU1iU1iU1i例题例题1：设：设A=a，b，c，R是是A上的二元关系，且给定上的二元关系，且给定R=，求，求r(R)，s(R)，t(R)。解：解：r(R)=，s(R)=，为了求为了求t(R)，先写出，

8、先写出 0 1 0MR= 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1MR2= 0 0 1 0 0 1 = 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0MR3= 1 0 0 0 0 1 = 0 0 1 0 1 0 1 0 0 1 0 0继续计算求解，会得出继续计算求解，会得出R4=R=R3n+1, R5=R2=R3n+2 , R6=R3=R3n+3所以所以t(R)= R R2 R35、定理、定理3-8.5：设：设X含有含有n个元素的集合，个元素的集合，R是是X上的上的二元关系，则存在一个正整数二元关系，则存在一个正整数kn，使得，使得t(R)

9、=R R(2) R(3) R(K)例：例：A=a，b，c，d，R=，求，求t(R)。解：解：R(2)=，R(3)=R(4)=所以所以t(R)=R R(2) R(3) R(4) =， ，6、Warshall算法算法设设R是个元素集合是个元素集合X上的二元关系，上的二元关系，(1)A是是R的关系矩阵；的关系矩阵；(2)置置i=1；(3)对所有，如果对所有，如果aji=1，则对，则对k=1，2，najk=ajk+aik（第（第i行与第行与第j行逻辑相加，记于第行逻辑相加，记于第j行）行）(4)i=i+1；(5)如果如果in，则转到步骤，则转到步骤(3)，否则停止。，否则停止。举例 P124 例3 W

10、arshall算法的C语言实现7、求闭包的关系图作法：、求闭包的关系图作法：(1)r(R)在在R的基础上添加自回路，使得每点均有自的基础上添加自回路，使得每点均有自回路。回路。(2)s(R)在在R中两结点间只有一条弧时，再添一条反中两结点间只有一条弧时，再添一条反向弧，使两结点间或是向弧，使两结点间或是0条弧，或是两条弧，原来条弧，或是两条弧，原来两点间没有弧不能添加。两点间没有弧不能添加。(3)t(R)在在R中如结点中如结点x通过有向路能通到通过有向路能通到z，则添加，则添加一条从一条从x到到z的有向弧，其中包括如的有向弧，其中包括如x能达到自身，能达到自身，则必须添从则必须添从x到到x的自

11、回路。的自回路。8、定理、定理3-8.6：若：若R A A，则，则rs(R)=sr(R)rt(R)=tr(R)st(R) ts(R)作业 P127: (1),(2),(7):a,c3-9 集合的划分和覆盖 在集合的研究中，除了常常把两个集合在集合的研究中，除了常常把两个集合相互比较之外，有时也要把一个集合分成若相互比较之外，有时也要把一个集合分成若干子集加以讨论。干子集加以讨论。一、集合的划分和覆盖一、集合的划分和覆盖定义定义3-9.1：若把一个集合：若把一个集合A分成若干个叫做分块的分成若干个叫做分块的非空集合非空集合，使得，使得A中中每个元素至少属于一个分块每个元素至少属于一个分块，那么这

12、些分块的全体构成的集合叫做那么这些分块的全体构成的集合叫做A的一个覆盖。的一个覆盖。如果如果A中中每个元素属于且仅属于一个分块每个元素属于且仅属于一个分块，那么这，那么这些分块的全体构成的集合叫做些分块的全体构成的集合叫做A的一个划分的一个划分(或分划或分划)。一、集合的划分和覆盖一、集合的划分和覆盖定义定义3-9.1：令：令A为非空集合，为非空集合，S=S1，S2，Sm，其中其中Si，Si A， Si=A，集合，集合S称作集合称作集合A的的覆盖覆盖。如果除以上条件外，另有如果除以上条件外，另有SiSj=(i j)，则称，则称S是是A的的划分划分(或或分划分划)。1mi例如，例如，A=a，b，

13、c，考虑下列子集：，考虑下列子集：S=a，b，b，c，Q=a，a，b，a，cD=a，b，c，G=a，b，cE=a，b，c，F=a，a，c则：则：D、E、G、S、Q是是A的覆盖的覆盖D、E、G是是A的划分的划分F既不是划分也不是覆盖。既不是划分也不是覆盖。 若是划分则必是覆盖，其逆不成立。若是划分则必是覆盖，其逆不成立。任何一个集合的最小划分，就是由这个集合的全部任何一个集合的最小划分，就是由这个集合的全部元素组成的一个分块的集合。如元素组成的一个分块的集合。如G是是A的最小划分。的最小划分。任何一个集合的最大划分，就是由每个元素构成一任何一个集合的最大划分，就是由每个元素构成一个单元素分块的集

14、合。如个单元素分块的集合。如E是是A的最大划分。的最大划分。二、交叉划分二、交叉划分定义定义3-9.2：若：若A1，A2，Ar与与B1，B2，Bs是同一集合是同一集合A的两种划分，则其中所有的两种划分，则其中所有Ai Bj组成组成的集合，称为原来两种划分的交叉划分。的集合，称为原来两种划分的交叉划分。例如，所有生物的集合例如，所有生物的集合X，可分割成，可分割成P，A，其中，其中P表示所有植物的集合，表示所有植物的集合，A表示所有动物的集合，又表示所有动物的集合，又X也可分割成也可分割成E，F，其中，其中E表示史前生物，表示史前生物，F表示史表示史后生物，则其交叉划分为后生物，则其交叉划分为Q

15、=P E，P F，A E，A F。定理定理3-9.1：设：设A1，A2，Ar与与B1，B2，Bs是同一集合是同一集合X的两种划分，则其的两种划分，则其交叉划分亦是原集交叉划分亦是原集合的一种划分。合的一种划分。加细加细定义定义3-9.3：给定：给定X的任意两个划分的任意两个划分A1，A2，Ar与与B1，B2，Bs，若对每一个，若对每一个Aj均有均有Bk使使Aj Bk，则，则A1，A2，Ar称为称为B1，B2，Bs的加细的加细。定理定理3-9.2：任何两种划分的交叉划分，都是原来各划分的：任何两种划分的交叉划分，都是原来各划分的一种加细。一种加细。证明：设证明：设A1，A2，Ar与与B1，B2，

16、Bs的交叉划分为的交叉划分为T，对，对T中任意元素中任意元素Ai Bj必有必有Ai Bj Ai，Ai Bj Bj，故，故T必是必是原划分的加细。原划分的加细。作业 P130：（4）、（5）3-10 等价关系与等价类一、等价关系一、等价关系定义定义3-10.1：设：设R为集合为集合A上的二元关系，若上的二元关系，若R是自是自反的、对称的和传递的，则称反的、对称的和传递的，则称R为等价关系。为等价关系。aRb，称为，称为a等价于等价于b。由于由于R是对称的，是对称的，a等价等价b即即b等价等价a，反之亦然，反之亦然，a与与b彼此等价。彼此等价。例如，平面上三角形集合中，三角形的相似关系是例如，平面

17、上三角形集合中，三角形的相似关系是等价关系。等价关系。鉴于空集合中的二元关系是等价关系，是一种平凡鉴于空集合中的二元关系是等价关系，是一种平凡情形，因此，一般讨论非空集合上的等价关系。情形，因此，一般讨论非空集合上的等价关系。例题例题1：设集合：设集合T=1，2，3，4，R=，。验证。验证R是是T上的等价关系。上的等价关系。解：画出解：画出R的关系图的关系图每个结点都有自回路，说明每个结点都有自回路，说明R是自反的。任意两是自反的。任意两个结点间或没有弧线连接，或有成对弧出现，故个结点间或没有弧线连接，或有成对弧出现，故R是对称的。从序偶表示式中，可以看出，是对称的。从序偶表示式中，可以看出，

18、R是传是传递的。递的。故故R是是T上的等价关系。上的等价关系。模模m等价是等价是I（整数集合）或其子集上的等（整数集合）或其子集上的等价关系，并且是一类重要的等价关系。价关系，并且是一类重要的等价关系。定义：设定义：设m为一正整数，而为一正整数，而a，b I。若存。若存在在k，使，使a-b=km，则称，则称a与与b是模是模m等价，等价，记为记为a b(mod m)。如如1与与4是模是模3等价，等价， 1与与7是模是模3等价，等价， 4与与7是模是模3等价，等价，4与与1是模是模3等价，等价， 7与与1是模是模3等价，等价， 1与与1是模是模3等价，等价，例题例题2：设：设I是整数集，是整数集，

19、R=(a，b)|a b(modk)，a，b I，证明，证明R是等价关系。是等价关系。证明：设任意证明：设任意a，b，c I(1)因为因为a-a=k 0，所以，所以 R，R是是自反的。自反的。(2)若若 R，a b(modk)，a-b=kt(t为整数为整数)，则则b-a=-kt，所以，所以b a(modk)， R，R是对是对称的。称的。(3)若若 R， R，a b(modk)，b c(modk)，则，则a-b=kt，b-c=ks(t，s为整数为整数)，a-c=k(t+s)，所以，所以a c(modk)， R，R是是传递的。传递的。因此因此R是等价关系。是等价关系。二、等价类二、等价类1、定义、定

20、义3-10.2：设：设R为集合为集合A上的等价关系，对任何上的等价关系，对任何a A，集合，集合aR=x|x A，aRx称为元素称为元素a形成的形成的R等价类。等价类。显然，等价类显然，等价类aR非空，因为非空，因为a aR。例题例题3：设：设I是整数集，是整数集，R是模是模3关系，关系，即即R=(x，y)|x y(mod3)，x，y I，确定由，确定由I的元素的元素所产生的等价类。所产生的等价类。解：由解：由I的元素所产生的等价类是的元素所产生的等价类是0R=，-6，-3，0，3，6，1R=，-5，-2，1，4，7，2R=，-4，-1，2，5，8，例：例：A=52张扑克牌张扑克牌，R1=a与

21、与b同花，同花，a，b是扑克是扑克，R2=a与与b同点，同点，a，b是扑克是扑克，即即R1是同花关系，是同花关系， R2是同点关系，是同点关系，R1和和R2都是等价关系。都是等价关系。R1把把A分为四类同花类，分为四类同花类，R2把把A分为分为13类同点类。类同点类。例：例：A=0，1，2，3，4，5，R=，R把把A分成了三个等价类：分成了三个等价类：0，1，2，3，4，5。2、定理、定理3-10.1：设给定集合：设给定集合A上的等价关系上的等价关系R，对，对于于a，b A有有aRb iff aR=bR。证明：假定证明：假定aR=bR，因为，因为a aR，故，故a bR，即，即aRb。反之，若反之，若aRb，则，则bRa， 设设c aRaRcbRcc bR即即aR bR同理，若同理，若aRb，设，设c bRbRcaRcc aR即即bR aR由此证得若由此证得若aRb，则，则aR=bR。三、商集三、商集1、定义、定义3-10.3：集合：集合A上的等价关系上的等价关系R，其等价类，其等价类的集合的集合aR|a A称为称为A关于关于R的商集，记作的商集，记作A/R。如例题如例题1中商集中商集T/R=1R，2R，例题例题3中商集中商集I/R=0R，1R，2R 等价关系等价关系R把把A的元素分为若