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

离散数学DiscreteMathematics山东科技大学信息科学与工程学院3-8关系的闭包关系的自反闭包关系的对称闭包关系的传递闭包一、关系的闭包定义定义3-8.1：设R是X上的二元关系，如果另外有一个关系R’满足：(1)R’是自反的(对称的，传递的)；(2)R’R；(3)对于任何自反的(对称的，传递的)关系R’’，如果有R’’R，就有R’’R’。则称关系R’为R的自反(对称，传递)闭包。记作r(R)，(s(R)，t(R))例：设集合X={x，y，z}，X上的关系R={x，x，x，y，y，z}，则:自反闭包r(R)={x，x，x，y，y，z，y，y，z，z}对称闭包s(R)={x，x，x，y，y，z，y，x，z，y}传递闭包t(R)={x，x，x，y，y，z，x，z}由闭包的定义可以知道，构造关系R的闭包方法就是向R中加入必要的有序对，使其具有所希望的性质。下面定理体现了这一点。二、关系的性质与闭包的关系1、定理3-8.1：设R是X上的二元关系，则(1)R是自反的，当且仅当r(R)=R(2)R是对称的，当且仅当s(R)=R(3)R是传递的，当且仅当t(R)=R证明只证明①①必要性:令R为自反.由于RR,并取右方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是传递的，当且仅当t(R)=R2、定理3-8.2：设R是集合X上的二元关系，则r(R)=Rx证明：RRx，Rx是自反的，定义的前两条满足了。设R”满足RR”，R”是自反的，x，yRx，则x，yR或x，yx。如果x，yR则由RR”，x，yR”。如果x，yx则必有x=y，即x，xx，由R”的自反性，则x，yR”，总之均有x，yR”，所以RXR”，满足定义第三条。得r(R)=Rx。对关系矩阵而言，r(R)的关系矩阵只要将MR的对角元置1即可。3、定理3-8.3：设R是集合X上的二元关系，则s(R)=RRc。证明：RRRc满足定义第一条。x，yRRcx，yRx，yRcy，xRcy，xRy，xRRc，所以RRc是对称的，满足定义的第二条。如果RR”，且R”是对称的，x，yRRc，则x，yR或x，yRc，如x，yR，由RR”，则x，yR”，如x，yRc则y，xR则y，xR”，又因R”对称，所以x，yR”，所以RRcR”，满足定义第三条。得s(R)=RRc。4、定理3-8.4：设R是集合X上的二元关系，则t(R)=R(i)=RR(2)R(3)…证明首先证明Rt(R).用归纳法证明如下:基础步:根据传递闭包定义,Rt(R);归纳步:假设n≥1时Rnt(R),欲证Rn+1t(R)令x,yX,则:xRn+1yxRn*Ry(z)(xRnz∧zRy)xRnz∧zRyxt(R)z∧zt(R)yxt(R)y因此,Rnt(R).于是,Rit(R).U1iU1iU1i次证t(R)Ri,由于包含R的传递关系都包含t(R)，且RRi,因此只需证明Ri是传递即可.令x,y,zX,则x(Ri)y∧y(Ri)z(j)(xRjy)∧(k)(yRkz)xRjy∧yRkzxRjy*yRkzxRj+kzx(Ri)z因此,Ri是传递的.综上可知,t(R)=Ri.U1iU1iU1iU1iU1iU1iU1iU1i例题1：设A={a，b，c}，R是A上的二元关系，且给定R={a，b，b，c，c，a}，求r(R)，s(R)，t(R)。解：r(R)={a，b，b，c，c，a，a，a，b，b，c，c}s(R)={a，b，b，a，b，c，c，b，c，a，a，c}为了求t(R)，先写出010MR=001100010010001MR2=001001=100100100010001010010MR3=100001=001010100100继续计算求解，会得出R4=R=R3n+1,R5=R2=R3n+2,R6=R3=R3n+3所以t(R)=RR2R35、定理3-8.5：设X含有n个元素的集合，R是X上的二元关系，则存在一个正整数k≤n，使得t(R)=RR(2)R(3)…R(K)例：A={a，b，c，d}，R={a，b，a，c，b，c，b，d}，求t(R)。解：R(2)={a，c，a，d}，R(3)=R(4)=所以t(R)=RR(2)R(3)R(4)={a，b，a，c，b，c，b，d，a，d}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)如果i≤n，则转到步骤(3)，否则停止。举例•P124例3•Warshall算法的C语言实现7、求闭包的关系图作法：(1)r(R)在R的基础上添加自回路，使得每点均有自回路。(2)s(R)在R中两结点间只有一条弧时，再添一条反向弧，使两结点间或是0条弧，或是两条弧，原来两点间没有弧不能添加。(3)t(R)在R中如结点x通过有向路能通到z，则添加一条从x到z的有向弧，其中包括如x能达到自身，则必须添从x到x的自回路。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中每个元素至少属于一个分块，那么这些分块的全体构成的集合叫做A的一个覆盖。如果A中每个元素属于且仅属于一个分块，那么这些分块的全体构成的集合叫做A的一个划分(或分划)。一、集合的划分和覆盖定义3-9.1：令A为非空集合，S={S1，S2，···，Sm}，其中①Si，②SiA，③Si=A，集合S称作集合A的覆盖。如果除以上条件外，另有Si∩Sj=(ij)，则称S是A的划分(或分划)。1mi例如，A={a，b，c}，考虑下列子集：S={{a，b}，{b，c}}，Q={{a}，{a，b}，{a，c}}D={{a}，{b，c}}，G={{a，b，c}}E={{a}，{b}，{c}}，F={{a}，{a，c}}则：D、E、G、S、Q是A的覆盖D、E、G是A的划分F既不是划分也不是覆盖。•若是划分则必是覆盖，其逆不成立。•任何一个集合的最小划分，就是由这个集合的全部元素组成的一个分块的集合。如G是A的最小划分。•任何一个集合的最大划分，就是由每个元素构成一个单元素分块的集合。如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={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，···，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彼此等价。例如，平面上三角形集合中，三角形的相似关系是等价关系。鉴于空集合中的二元关系是等价关系，是一种平凡情形，因此，一般讨论非空集合上的等价关系。例题1：设集合T={1，2，3，4}，R={1，1，1，4，4，1，4，4，2，2，2，3，3，2，3，3}。验证R是T上的等价关系。解：画出R的关系图每个结点都有自回路，说明R是自反的。任意两个结点间或没有弧线连接，或有成对弧出现，故R是对称的。从序偶表示式中，可以看出，R是传递的。故R是T上的等价关系。模m等价是I（整数集合）或其子集上的等价关系，并且是一类重要的等价关系。定义：设m为一正整数，而a，bI。若存在k，使a-b=km，则称a与b是模m等价，记为ab(modm)。如1与4是模3等价，1与7是模3等价，4与7是模3等价，4与1是模3等价，7与1是模3等价，1与1是模3等价，……例题2：设I是整数集，R={(a，b)|ab(modk)，a，bI}，证明R是等价关系。证明：设任意a，b，cI(1)因为a-a=k0，所以a，aR，R是自反的。(2)若a，bR，ab(modk)，a-b=kt(t为整数)，则b-a=-kt，所以ba(modk)，b，aR，R是对(3)若a，bR，b，cR，ab(modk)，bc(modk)，则a-b=kt，b-c=ks(t，s为整数)，a-c=k(t+s)，所以ac(modk)，a，cR，R是传递的。因此R是等价关系。二、等价类1、定义3-10.2：设R为集合A上的等价关系，对任何aA，集合[a]R={x|xA，aRx}称为元素a形成的R等价类。显然，等价类[a]R非空，因为a[a]R。例题3：设I是整数集，R是模3关系，即R={(x，y)|xy(mod3)，x，yI}，确定由I的元素所产生的等价类。解：由I的元素所产生的等价类是[0]R={…，-6，-3，0，3，6，…}[1]R={…，-5，-2，1，4，7，…}[2]R={…，-4，-1，2，5，8，…}例：A={52张扑克牌}，R1={a，b｜a与b同花，a，b是扑克}，R2={a，b｜a与b同点，a，b是扑克}，即R1是同花关系，R2是同点关系，R1和R2都是等价关系。R1把A分为四类同花类，R2把A分为13类同点类。例：A={0，1，2，3，4，5}，R={0，0，1，1，2，2，3，3，1，2，1，3，2，1，2，3，3，1，3，2，4，4，4，5，5，4，5，5}，R把A分成了三个等价类：{0}，{1，2，3}，{4，5}。2、定理3-10.1：设给定集合A上的等价关系R，对于a，bA有aRbiff[a]R=[b]R。证明：假定[a]R=[b]R，因为a[a]R，故a[b]R，即aRb。反之，若aRb，则bRa，设c[a]RaRcbRcc[b]R即[a]R[b]R同理，若aRb，设c[b]RbRcaRcc[a]R即[b]R[a]R由此证得若