離散數學 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繼續(xù)計算求解，會得出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)作業(yè)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}，，{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必是原劃分的加細。作業(yè)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