离散数学 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为自反.由于RR,并取右方R为S,以及任何包含R的自反关系T,有ST,可见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)=Rx证明：RRx，Rx是自反的，定义的前两条满足了。设R”满足RR”，R”是自反的，<x，y>Rx，则<x，y>R或<x，y>x。如果<x，y>R则由RR”，<x，y>R”。如果<x，y>x则必有x=y，即<x，x>x，由R”的自反性，则<x，y>R”，总之均有<x，y>R”，所以RXR”，满足定义第三条。得r(R)=Rx。对关系矩阵而言，r(R)的关系矩阵只要将MR的对角元置1即可。3、定理3-8.3：设R是集合X上的二元关系，则s(R)=RRc。证明：RRRc满足定义第一条。<x，y>RRc<x，y>R<x，y>Rc<y，x>Rc<y，x>R<y，x>RRc，所以RRc是对称的，满足定义的第二条。如果RR”，且R”是对称的，<x，y>RRc，则<x，y>R或<x，y>Rc，如<x，y>R，由RR”，则<x，y>R”，如<x，y>Rc则<y，x>R则<y，x>R”，又因R”对称，所以<x，y>R”，所以RRcR”，满足定义第三条。得s(R)=RRc。4、定理3-8.4：设R是集合X上的二元关系，则

t(R)=R(i)=RR(2)R(3)…证明首先证明Rt(R).用归纳法证明如下:

基础步:根据传递闭包定义,Rt(R);

归纳步:假设n≥1时Rnt(R),欲证Rn+1t(R)令x,yX,则:xRn+1yxRn

*Ry(z)(xRnz∧zRy)

xRnz∧zRy

xt(R)z∧zt(R)yxt(R)y

因此,Rnt(R).于是,Ri

t(R).次证t(R)Ri,由于包含R的传递关系都包含t(R)，且RRi,因此只需证明Ri是传递即可.令x,y,zX,则

x(Ri)y∧y(Ri)z

(j)(xRjy)∧(k)(yRkz)

xRjy∧yRkz

xRjy

*yRkz

xRj+kz

x(Ri)z因此,Ri是传递的.综上可知,t(R)=Ri.例题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)=RR2

R35、定理3-8.5：设X含有n个元素的集合，R是X上的二元关系，则存在一个正整数k≤n，使得t(R)=RR(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)=RR(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，…，n

ajk=ajk+aik（第i行与第j行逻辑相加，记于第j行）(4)i=i+1；(5)如果i≤n，则转到步骤(3)，否则停止。举例P124例3Warshall算法的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：若RAA，则①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，②SiA，③Si=A，集合S称作集合A的覆盖。如果除以上条件外，另有Si∩Sj=(ij)，则称S是A的划分(或分划)。例如，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的两种划分，则其中所有AiBj组成的集合，称为原来两种划分的交叉划分。例如，所有生物的集合X，可分割成{P，A}，其中P表示所有植物的集合，A表示所有动物的集合，又X也可分割成{E，F}，其中E表示史前生物，F表示史后生物，则其交叉划分为Q={PE，PF，AE，AF}。定理3-9.1：设{A1，A2，···，Ar}与{B1，B2，···，Bs}是同一集合X的两种划分，则其交叉划分亦是原集合的一种划分。加细定义3-9.3：给定X的任意两个划分{A1，A2，···，Ar}与{B1，B2，···，Bs}，若对每一个Aj均有Bk使AjBk，则{A1，A2，···，Ar}称为{B1，B2，···，Bs}的加细。定理3-9.2：任何两种划分的交叉划分，都是原来各划分的一种加细。证明：设{A1，A2，···，Ar}与{B1，B2，···，Bs}的交叉划分为T，对T中任意元素AiBj必有AiBjAi，AiBjBj，故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，bI。若存在k，使a-b=km，则称a与b是模m等价，记为ab(modm)。如1与4是模3等价，1与7是模3等价，4与7是模3等价，4与1是模3等价，7与1是模3等价，1与1是模3等价，……例题2：设I是整数集，R={(a，b)|ab(modk)，a，bI}，证明R是等价关系。证明：设任意a，b，cI(1)因为a-a=k0，所以<a，a>R，R是自反的。(2)若<a，b>R，ab(modk)，a-b=kt(t为整数)，则b-a=-kt，所以ba(modk)，<b，a>R，R是对称的。(3)若<a，b>R，<b，c>R，ab(modk)，bc(modk)，则a-b=kt，b-c=ks(t，s为整数)，a-c=k(t+s)，所以ac(modk)，<a，c>R，R是传递的。因此R是等价关系。二、等价类1、定义3-10.2：设R为集合A上的等价关系，对任何aA，集合[a]R={x|xA，aRx}称为元素a形成的R等价类。显然，等价类[a]R非空，因为a[a]R。例题3：设I是整数集，R是模3关系，即R={(x，y)|xy(mod3)，x，yI}，确定由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，bA有aRb

iff[a]R=[b]R。证明：假定[a]R=[b]R，因为a[a]R，故a[b]R，即aRb。反之，若aRb，则bRa，设c[a]RaRcbRcc[b]R即[a]R[b]R同理，若aRb，设c[b]RbRcaRcc[a]R即[b]R[a]R由此证得若aRb，则[a]R=[b]R。三、商集1、定义3-10.3：集合A上的等价关系R，其等价类的集合{[a]R|aA}称为A关于R的商集，记作A/R。如例题1中商集T/R={[1]R，[2]R}，例题3中商集I/R={[0]R，[1]R，[2]R}

等价关系R把A的元素分为若干类，各类之间没有公共元素。确定的R是对集合A进行的一个划分。2、定理3-10.2：集合A上的等价关系R