課堂演示2013dm集合的積集

1、第七章 關(guān)系7.1 集合的笛卡爾積集 7.2 二元關(guān)系的基本概念 7.3 二元關(guān)系的性質(zhì)7.4 二元關(guān)系的閉包運(yùn)算7.5 等價(jià)關(guān)系和集合的劃分 7.6 偏序關(guān)系和格 7.7 鏈與反鏈 等價(jià)關(guān)系定義1 A是一個(gè)非空集, R是A上的一個(gè)二元關(guān)系， 若R有自反性、 對(duì)稱性、 傳遞性， 則說R是A上的等價(jià)關(guān)系。等價(jià)類、代表元 若R是A上的等價(jià)關(guān)系， a是A中任意一個(gè)元素，集合 xA(x,a) R 稱為集合A關(guān)于關(guān)系R的一個(gè)等價(jià)類，記 aR= xA(x,a) R, 其中a叫代表元。例1A=1,2,3,R=(1,1), (2,2), (3,3), (1,2), (2,1) 則R是A上一個(gè)等價(jià)關(guān)系。 顯然

2、1R1,2 2R1,2 3R3 1 2 3例 試畫出關(guān)系圖 A=1,2,3,4,5,6,7,8 R=(x,y) x,y A, xy(mod 3)其中xy(mod 3)的含義就是x-y可以被3整除.14736258例2 (p83)設(shè)A是計(jì)算機(jī)系的學(xué)生的集合， R是A上一個(gè)二元關(guān)系，使得 (a, b) R當(dāng)且僅當(dāng)a和b住在同一宿舍里。還可以引入A上的其它等價(jià)關(guān)系如下：R是A上一個(gè)二元關(guān)系，使得(a, b) R當(dāng)且僅當(dāng)a和b是學(xué)習(xí)相同的專業(yè)R是A上一個(gè)二元關(guān)系，使得(a, b) R當(dāng)且僅當(dāng)a和b同齡不難驗(yàn)證， R是A上一個(gè)等價(jià)關(guān)系。例3 (p83) Z是整數(shù)集，在Z上定義一個(gè)二元關(guān)系R：對(duì)于任意的

3、x,yZ, (x,y) R當(dāng)且僅當(dāng)x與y被5除余數(shù)相同。R是Z上的等價(jià)關(guān)系。顯然, x與y被5除同余的充要條件是5|(x-y), 這里符號(hào)a|b表示a整除b，a與b是兩個(gè)整數(shù)。對(duì)于 xZ，有5|(x-x), 即(x,x) R，亦即R有自反性。對(duì)于 x,yZ，若(x,y) R, 即5|(x-y)， 也即5|(y-x), 所以(y,x) R， 亦即R有對(duì)稱性。對(duì)于 x,y,zZ，若(x,y) R, 且(y,z) R， 即5|(x-y)，且5|(z-y)，則 5|(x-y)+(y-z)， 亦即5|(x-z)，所以(x,z) R，亦即R有傳遞性。故R是A上的等價(jià)關(guān)系。例設(shè)A=1,2,3,并設(shè)是AA上的

4、關(guān)系，其定義為：若ad=bc， 則(a,b) (c,d)。證明 是一個(gè)等價(jià)關(guān)系。 證： (1) 自反性 對(duì)于(a,b)AA, 因?yàn)閍b=ba， 則有(a,b) (a,b) 。 (2) 對(duì)稱性 如果(a,b) (c,d)，即有 ad=bc， 即有 cb=da， 故有(c,d) (a,b)。 (3) 傳遞性 如果(a,b) (c,d)，(c,d) (e,f)， 即有 ad=bc, cf=de, 于是有 adcf=bcde 即 af=be, 故有 (a,b)(e,f)商集合 定義2 A是一個(gè)非空集合，R是A上的一個(gè)等價(jià)關(guān)系，集合xRxA 叫集合A的商集合，記為 A/R= xRxA 例 A=1,2,3

5、, 顯然 A/R= 1R , 3R = 1,2 , 3 1 2 3例 Z是整數(shù)集，在Z上定義一個(gè)二元關(guān)系R： 對(duì)于任意的 x,yZ, (x,y) R 當(dāng)且僅當(dāng)x與y被5除余數(shù)相同。 則 Z/R= 0R, 1R, 2R, 3R, 4R 這里 0R=xZnZ, x=5n1R=xZnZ, x=5n+12R=xZnZ, x=5n+23R=xZnZ, x=5n+34R=xZnZ, x=5n+4定理1 A是一個(gè)非空集合，R是A上的一個(gè)等價(jià)關(guān)系，則有(1) xR=A，(2) 對(duì)于任意的x,yA， 若xRyR，則xR=yR。xA證明(1) 顯然，對(duì)于任意的xA，有xRA， 所以 xR A. 反之，對(duì)于任意的x

6、 A，則x x， 即 x xR ， 所以 A xR xAxAxA定理1 證明 若xRyR，則xR=yR 證明(2): 對(duì)于任意的x,y A，若xRyR， 則存在axRyR。 由axR，得(a,x)R； 再由R的對(duì)稱性，有(x,a) R。 由ayR, 有(a,y) R。 利用R的傳遞性，得(x,y)R。 下面開始證明xR=yR。 對(duì)于任意的z xR，有(z,x) R, 又因?yàn)閯偛乓训玫?x,y) R， 由R的傳遞性，得到(z,y) R, 所以有z yR。從而證得 xRyR。 同理可證yRxR。 所以最后得到xR=yR。定理1 A是一個(gè)非空集合，R是A上的一個(gè)等價(jià)關(guān)系，則有(1) xR=A，(2)

7、 對(duì)于任意的x,yA，若xRyR， 則xR=yR。(3) xR, 且xRA.(4) 若xRy, 則xR=yR.(5) 若xRy, 則xRyR=xA集合的劃分定義3 A是一個(gè)非空集合，一個(gè)集合 = AB， A，且AA 稱做集合A的一個(gè)劃分，若 A=A 對(duì)于任意的,B，若AA，則 A=A，其中B是下標(biāo)集。B例 商集合 A/R 是集合A上的一個(gè)劃分。例考慮集合A=a,b,c,d的下列子集族: a, b,c, d a,b,c,d a,b,c,a,d , a,b, c,d a, b,c試判斷這些子集是不是一個(gè)劃分.集合的劃分等價(jià)關(guān)系若給定集合A上的一個(gè)劃分，可以在A上定義一個(gè)二元關(guān)系R，使得R成為A上的

8、一個(gè)等價(jià)關(guān)系，且有 A/R 定理2 (p84)A是一個(gè)非空集合，是A上的一個(gè)劃分， = AB，AA在A上定義一個(gè)二元關(guān)系R： 對(duì)于任意的x,yA， (x,y) R當(dāng)且僅當(dāng)存在B，x,yA. 則 R是A上一個(gè)等價(jià)關(guān)系，而且 A/R定理2 先證 R是A上的等價(jià)關(guān)系對(duì)于任意的xA，存在B，xA， 即有x, xA, 所以有(x,x)R， 故R是自反的。對(duì)于任意的x,yA，若(x,y) R， 則存在B, x,yA, 即有y,xA, 所以有(y,x) R, 故R是對(duì)稱的。對(duì)于任意x,y,zA，若(x,y) R 且(y,z) R， 則存在B，x,yA， 而且又存在B，y,zA。 因?yàn)?yAA，所以AA， 則

9、A=A，即xA，所以(x,z) R， 故R是傳遞的。所以 R是A上的等價(jià)關(guān)系。定理2 證明 A/R= 首先證明 A/R 。 對(duì)于任意的xRA/R ， 因?yàn)閤A，故存在B，XA， 可以證明xR=A。 所以 A/R。再證明A/R。 對(duì)于任意的A， 因?yàn)锳 ，故存在xA， 可以證明有xR=A，即A=xR A/R。 所以 A/R。定理2 證明 A/R 對(duì)于任意的xRA/R ，因?yàn)閤A，所以存在B，XA。 要證明xR=A。 對(duì)于任意的aA，有(a,x) R，則axR， 即有AxR； 反之, 對(duì)于任意的a xR，所以(a,x) R， 即存在B，a,xA。 因?yàn)閤AA，所以AA，所以A=A， 從而有aA，所

10、以xRA。故xR=A。所以 A/R。例考慮集合A=a,b,c,d的一個(gè)劃分: a, b,c, d 求該劃分所對(duì)應(yīng)的等價(jià)關(guān)系.解: R=(a,a), (b,b), (c,c), (b,c),(c,b),(d,d)例 設(shè)A=1,2,3,求出A上所有的等價(jià)關(guān)系.213213213213213 1 2 3 4 5R1=(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)R2=(1,1),(2,2),(2,3),(3,2),(3,3)R3=(1,1),(1,3),(3,1),(3,3),(2,2)R4=(1,1),(1,2),(2,1),(2,2),

11、(3,3)R5=(1,1),(2,2),(3,3)劃分加細(xì)定義4 A是一個(gè)非空集合。1與2 是集合A上的兩個(gè)劃分，其中 1= AB，AA, 2= AB，AA, 若對(duì)于任意的B， 存在B，使得AA ， 則稱1 是2 的加細(xì)。劃分加細(xì)定理3 A是一個(gè)非空集合， 1與2 是A上的兩個(gè)劃分: 1= AB，AA, 2= AB，AA， 它們相應(yīng)的等價(jià)關(guān)系分別為R1和R2 。 則 R1R2 當(dāng)且僅當(dāng) 是 1 是2 的加細(xì)。定理3的證明：“”若R1R2 則 1 是2 的加細(xì)對(duì)于任意的B，A1，存在 aA，A=aR1。對(duì)于任意的x aR1=A，所以有(x,a) R1。根據(jù)假設(shè)R1R2，得到(x,a) R2，所以

12、有x aR2。因?yàn)閍R2A/R2=2 ，所以存在 B，aR2=A 2，所以得到xA，從而得到AA。所以1 是2 的加細(xì)。定理3的證明“”若1 是2 的加細(xì)，則R1R2。 對(duì)于任意的x,yA，若(x,y) R1，即x yR1，又因?yàn)锳/R1=1，所以存在B，yR1=A根據(jù)假設(shè)1是2的加細(xì)，則存在B，AA于是yR1=AA，yA，且xA故(x,y) R2.所以R1R2得證。例設(shè)A是南京理工大學(xué)的學(xué)生組成的集合。學(xué)生們分別屬于不同的分院，按學(xué)院劃分R1是A的一個(gè)劃分。學(xué)生們也分別屬于不同的系，按系劃分R2也是 A的一個(gè)劃分。顯然， R1與R2都是等價(jià)關(guān)系，而且 R2R1所以，R2是R1的加細(xì)。例 (2

13、006年碩士研究生試題)已知R是A上的等價(jià)關(guān)系, 證明R2也是A上的等價(jià)關(guān)系。證: (1) 自反性 對(duì)于aA, 因?yàn)镽是自反的，即有 (a,a) R，故由定義知 (a,a) R2。 (2) 對(duì)稱性 對(duì)于(a,b) R2, 由定義知: 存在c,使得(a,c) R，且 (c,b) R.由于R是對(duì)稱的，有(c,a) R，且 (b,c) R.由R2定義知有 (b,a) R2。 (3) 傳遞性 對(duì)于(a,b) R2, (b,c) R2, 存在x,y,有：(a,x) R，且 (x,b) R.(b,y) R，且 (y,c) R.由于R具有傳遞性，則有 (x,c) R進(jìn)而，由定義知，(a,c) R2.例 (2004年碩士研究生試題)已知R是集合A上自反的、對(duì)稱的二元關(guān)系, 證明t(R)是A上的等價(jià)關(guān)系。證明： 因?yàn)閠(R)= Ri是傳遞閉包，即滿足傳遞性，即要證明自反性與對(duì)稱性。顯然，只需要證明Ri具有自反性與對(duì)稱