離散數(shù)學(xué)第三章第四節(jié)

1、1,第3-4講 等價(jià)關(guān)系,1. 集合覆蓋與劃分2. 等價(jià)關(guān)系3. 等價(jià)類4. 商集5. 等價(jià)關(guān)系、商集 及劃分之間的關(guān)系6. 第3-4講 作業(yè),,,,,2,1、集合覆蓋與劃分（1）,在集合研究中，有時(shí)要將集合分為若干子集來討論。如下左圖所示集合A就被分成三個(gè)非空子集B1、B2、B3。A中的所有元素至少屬于其中的某個(gè)分塊（子集），這些分塊（子集）的全體構(gòu)成的集合{B1，B2，B3}叫做A的一個(gè)覆蓋。當(dāng)A中的所有元素屬于且僅屬于

2、其中的某個(gè)分塊（子集）時(shí)，這些分塊（子集）的全體構(gòu)成的集合叫做A的一個(gè)劃分（如下右圖所示）。,,,,,B2?B3??,Ai ? Aj=?(i?j),3,1、集合覆蓋與劃分（2）,定義1 給定非空集合A，令?={Ai|1?i?m} Ai??， Ai?A， A1?A2?...? Am=A，則稱集合?為A的一個(gè)覆蓋。如果Ai?Aj=?(i?j)，則稱集合?為A的一個(gè)劃分， Ai稱為劃分?的塊。,,,,,例如 設(shè)A={a,b,c}，令

3、 ?1={{a,b},{b,c}}， ?2={{a},{a,b},{a,c}}， ?3={{a},{b,c}}， ?4={{a,b,c}}， ?5={{a},,{c}}，?6={{a},{a,b}} 則?1、 ?2、 ?3、?4、 ?5都是A的一個(gè)覆蓋；其中?3、?4、 ?5是A的劃分。 ?6既不是覆蓋，更不是劃分。,常以劃分具有塊的多少來衡量劃分的“大小”，因此，任一集合的最小劃分就是

4、由該集合全部元素構(gòu)成的唯一分塊組成的集合，如上例中的?4就是A的最小劃分， 而?5就是A的最大劃分。,4,1、集合覆蓋與劃分（3）,,,,,例如,設(shè)A={a,b,c},?1={{a,b},{c}},?2={{a},,{c}}， 則?2是?1的加細(xì)或?2細(xì)分?1。,定義3 若{A1, A2,…, Ar}與{B1, B2,…, Bs}是同一集合的兩種劃分，則所有Ai?Bj??組成的集合稱為原來兩種劃分的交叉劃分。,定義2

5、 若?1={A1, A2,…, Ar}與?2={B1, B2,…, Bs}是同一集合的兩種劃分，且對(duì)所有Bj均有Ai，使得Bj?Ai，則稱?2是?1的加細(xì)，或?2細(xì)分?1。,例如，設(shè)S是某年級(jí)全體學(xué)生的集合，令?1={A1,A2,A3}，其中A1、A2、A3分別表示一班、二班和三班學(xué)生的集合；?2={B1, B2}，其中B1、B2分別表示本年級(jí)全體 男、女生的集合。則交叉劃分 ?={A1?B1,A1?B2,A2?B1,A2?

6、B2,A3?B1,A3?B2}中的各元素分別表示各班男生和女生的集合。,5,1、集合覆蓋與劃分（4）,,,,,定理1 若?1={A1, A2,…, Ar}與?2={B1, B2,…, Bs}是同一集合X的兩種劃分，則?1、 ?2的交叉劃分 ?={Ai ? Bj|1?i?r, 1?j?s} 也是集合X的一種劃分。,證明：1、在?中任取兩個(gè)元素Ai?Bh 、Aj?Bk,證明它們的交集為空。分三種情況討論：當(dāng)i?j,

7、h=k時(shí)， ( Ai?Bh )?(Aj?Bk)=( Ai?Aj)?(Bh?Bk) =?? Bh=?當(dāng)i?j,h?k時(shí)， ( Ai?Bh )?(Aj?Bk)=( Ai?Aj)?(Bh?Bk) =?? ? =?當(dāng)i=j,h?k時(shí)， 與第一種情況類同。2、證明?中所有元素的并集合等于X。,6,1、集合覆蓋與劃分（5）,,,,,定理2 同一集合X的任何兩種劃分的交叉劃分 是原來各劃分的加細(xì)。,證明：若?1={A1, A2,…, Ar

8、}與?2={B1, B2,…, Bs}是同一集合X的兩種劃分，?1、 ?2的交叉劃分為 ?={Ai ? Bj|1?i?r, 1?j?s}則對(duì)?中任意元素Ai?Bj 均有Ai?Bj? Ai，Ai?Bj ? Bj。故?是原來各劃分的加細(xì)。,7,2、等價(jià)關(guān)系（1）,定義4 設(shè)R為非空集合A上的二元關(guān)系，如果R是自反的、對(duì)稱的和傳遞的，則稱R為上的等價(jià)關(guān)系。,,,,,等價(jià)關(guān)系是一類重要的二元關(guān)系。,例如，幾何中的全等關(guān)系、相似

9、關(guān)系，數(shù)中的相等關(guān)系，命題邏輯中等價(jià)關(guān)系都是等價(jià)關(guān)系。,8,2、等價(jià)關(guān)系（2）,例1 設(shè)A＝{1,2,3,4,5,6,7}，Z為整數(shù)集合，A上的關(guān)系R定義為： R={|x,y?A?(x-y)/3?Z}說明R是等價(jià)關(guān)系。,,,,,解： R={,,,,,, ,,,,,,, ,,} 顯然R是自反的、對(duì)稱的和傳遞的，因此R是等價(jià)關(guān)系。R的關(guān)系圖如下：,9,2、等價(jià)關(guān)系（3）,設(shè)Z為整數(shù)集合，R為Z上的關(guān)系，K為正整數(shù)，令

10、 R={|x,y?Z?(x-y)/K?Z}稱R為模K同余關(guān)系。一般記作 R={|x,y?Z?x≡y(modK)}并稱x與y模K相等。容易證明，R是等價(jià)關(guān)系。,證：設(shè)任意a、b、c?Z， 因(a-a)/K=0，故?R，說明R是自反的。 若?R,即a≡b(modK),可令a-b=Kt,其中t為整數(shù)，所以b-a=-Kt,故?R。 若?R，?R，則可令a-b=Kt, b-c=Ks,其中t、s為整數(shù)，

11、那么 a-c=(a-b)+(b-c)=K(t+s)，即a≡c(modK)故?R。 綜上所述，R是等價(jià)關(guān)系。,,,,,10,3、等價(jià)類（1）,定義5 設(shè)R為非空集合A上的等價(jià)關(guān)系，?a?A，令 [a]R={ x |x?A?aRx }稱[a]R為a關(guān)于R的等價(jià)類。簡(jiǎn)稱為a的等價(jià)類，簡(jiǎn)記為[a]。,從例1看出，集合A上的等價(jià)關(guān)系R將A進(jìn)行了一種劃分，每一劃分塊中的元素之間（包括自身“之間”）都具有關(guān)系R，而不在一

12、個(gè)劃分塊中的元素之間則不具有關(guān)系R。,例如，設(shè)A={a,b,c},求等價(jià)關(guān)系R={,,,,}的所有等價(jià)類。 解：[a]={a}, [b]=[c]={b,c}。,,,,,11,3、等價(jià)類（2）,定理3 設(shè)R為非空集合A上的等價(jià)關(guān)系，?a,b ?A, aRb當(dāng)且僅當(dāng)[a]R=[b]R。,證明：若aRb，任取c?[a]R , c?[a]R?aRc?cRa?cRb?bRc?c?[b]R , 故[a]R?

13、[b]R。 同理可證[b]R?[a]R。 故[a]R=[b]R 。反之,若[a]R=[b]R ,則 a?[a]R ? a?[b]R ? bRa ? aRb,,,,,12,4、商集,定義6 設(shè)R為非空集合A上的等價(jià)關(guān)系，集合{[x]R|x?A}稱為A關(guān)于R的商集，記作A/R。,集合A上的等價(jià)關(guān)系R將A劃分為等價(jià)類，以等價(jià)類作元素，得到新的集合，稱為A關(guān)于R的商集。,例如，設(shè)A={a,b,c},R為等價(jià)關(guān)系： R={

14、,,,,}則A關(guān)于R的商集： A/R={[a]，[b]，[c]} ={{a},{b,c}},,,,,13,5、等價(jià)關(guān)系、商集及劃分之間的關(guān)系（1）,定理4 集合A上的等價(jià)關(guān)系R確定A的一個(gè)劃分，這個(gè)劃分就是商集A／R。,,,,,證：1、A/R={[a]R|a?A},顯然,2、對(duì)?a?A，有a?[a]R，所以A中的每個(gè)元素都屬于某個(gè)分塊。 3、下面證明A中的任一個(gè)元素僅屬于某一個(gè)分塊。 設(shè)?a?A ，a?[

15、b]R且a?[c]R，那么，bRa，cRa 。因R對(duì)稱，所以aRc。又因R是傳遞的,所以bRc。按定理3, [b]R=[c]R 。 綜上所述，A/R是A關(guān)于R的一個(gè)劃分。,14,5、等價(jià)關(guān)系、商集及劃分之間的關(guān)系（2）,定理5 A的一個(gè)劃分π={A1，A2，…，Ak}，確定A上的一個(gè)等價(jià)關(guān)系： R={ |x,y?A ? x與y在π的同一劃分塊中} = A1?A1 ? A2?A2 ?…? Ak?Ak。,,,

16、,,證：對(duì)任意a?A，因?yàn)閍與a屬于同一分塊，所以?R，故R是自反的。 若?R，則a與b屬于同一分塊，當(dāng)然b與a也屬于同一分塊，所以?R。這說明R是對(duì)稱的。 若?R，?R，可設(shè)a、b屬于同一分塊Ai，b、c屬于同一分塊Aj。按劃分的定義，當(dāng)i?j時(shí)，Ai?Aj=?，但b只能屬于一個(gè)分塊，所以Ai=Aj。于是a、c屬于同一分塊，那么?R，故R是傳遞的。 綜合上述，R是A上的等價(jià)關(guān)系。,15,5、等價(jià)關(guān)系、商集及劃分之間

17、的關(guān)系（3）,,,,,例2：設(shè)A={a,b,c,d,e}，A的一個(gè)劃分π={{a,b},{c},{d,e}}，試寫出劃分π所確定的A上的等價(jià)關(guān)系。,解：R1={a,b}?{a,b}={,,,} R2={c}?{c}={} R3={d,e}?{d,e}={,,,} R= R1?R2?R3 ={,,,,, ,,,},16,5、等價(jià)關(guān)系、商集及劃分之間的關(guān)系（4）,,,

18、,,例3：給出A={1，2，3}上的所有等價(jià)關(guān)系。,解：因A的所有劃分如下圖所示:,A上的所有等價(jià)關(guān)系就是π1 、π2 、π3 、π4 、π5對(duì)應(yīng)的等價(jià)關(guān)系，它們依次為EA，R2，R3，R4，IA，其中EA=A ? A為全域關(guān)系， IA= { , , }， R2={,}? IA R3={,}? IA R4={,}? IA,17,5、等價(jià)關(guān)系、商集及劃分之間的關(guān)系（5）,定理6 設(shè)R1

19、和R2是非空集合A上的兩個(gè)等價(jià)關(guān)系，R1=R2當(dāng)且僅當(dāng)A/R1= A/R2 。,,,,,證：若 R1=R2，因A/R1={[a]R1|a?A}，A/R2={[a]R2|a?A}。對(duì)任意a?A，[a]R1={x|x?A,aR1x}={x|x?A,aR2x}=[a]R2所以A/R1和 A/R2 中的元素相同，即A/R1= A/R2 。 反之，若A/R1= A/R2 ，則對(duì)任意[a]R1?A/R1，必有[c]R2?A/R2，使得[a