【文章內(nèi)容簡(jiǎn)介】 {(a,b),(a,c)}（ √） R3={(a,a),(c,b),(b,c),(c,a)}（ ） 數(shù)的大于關(guān)系、小于關(guān)系（ √） 朋友關(guān)系，父子關(guān)系（ ） 空關(guān)系 ?、全域關(guān)系 EA 、相等關(guān)系 IA （ √） ? 傳遞性特點(diǎn)： R具有傳遞性的 ? R2 ?R。 R有傳遞性，當(dāng)且僅當(dāng)對(duì)于 R的關(guān)系圖中的任意三點(diǎn) a,b,c，不存在這樣的情形：有 a到 b的有向弧， b到 c的有向弧，但無(wú) a到 c的有向弧。 如果 M(R)2中某元素 sij=1，那么M(R)相應(yīng)位置元素 rij也一定為 1，則 R具有傳遞性。 定理 ?集合 A上的關(guān)系 R具有傳遞性的充要條件是 R2 ?R。 ?證明：必要性。 若 R具有傳遞性，任取 (x,y)?R2，于是存在 z?A，使得 xRz， zRy，因?yàn)?R是傳遞的，所以有 xRy，即 (x,y) ?R,故 R2? R。 充分性。 如果 xRy， yRz，則 xR2z。 因?yàn)?R2? R，故 xRz。所以 R具有傳遞性。 ？思考 A上關(guān)系 R是傳遞的 當(dāng)且僅當(dāng) 對(duì)所有 n ?N+ ，都有 Rn ?R。 提示：充分性易證； 采用 數(shù)學(xué)歸納法 證明必要性，即當(dāng) R是傳遞的時(shí)，對(duì) n ?N+ 進(jìn)行歸納，證明 Rn ?R。 ?關(guān)系的性質(zhì)總結(jié) 自反的 反自反的 對(duì)稱的 反對(duì)稱的 傳遞的 定義 任取 a?A有(a,a)?R 任取 a?A有(a,a)?R 若 (a,b)?R,則 (b,a)?R 若 (a,b)?R, (b,a)?R, 則 a=b 若 (a,b)?R且 (b,c)?R, 則(a,c)?R 集合 IA?R IA∩ R=? R1=R R∩ R1?IA R2 ?R 關(guān)系圖 圖中每個(gè)結(jié)點(diǎn)都有自回路 圖中每個(gè)結(jié)點(diǎn)都無(wú)自回路 任意兩個(gè)不同結(jié)點(diǎn)間要么沒(méi)有弧 ,要么有一對(duì)方向相反的弧 任意兩個(gè)不同結(jié)點(diǎn)間至多有一條弧 若 a到 b有弧 ,b到 c有弧 ,則 a到 c有弧 關(guān)系矩陣 主對(duì)角線上全為 1 主對(duì)角線上全為 0 對(duì)稱矩陣 以主對(duì)角線為對(duì)稱的元素不同時(shí)為 1 MR2中某元素為 1， MR中相應(yīng)位置元素也一定為 1 1． 討論以下幾種關(guān)系的自反性、反自反性、對(duì)稱性、反對(duì)稱性和傳遞性： (1)空集上的空關(guān)系 216。 (2)非空集合上的空關(guān)系 216。 (3)恒等關(guān)系 IA (|A|0) (4)全域關(guān)系 EA(|A|1) (5)正整數(shù)集合上的整除關(guān)系 (6)整數(shù)集合上的整除關(guān)系 (7)有理數(shù)集合上的 =、 、 ≤關(guān)系。 問(wèn)題討論 （自反、 傳遞） （ 反自反、對(duì)稱、反對(duì)稱、傳遞） （自反、 對(duì)稱、 傳遞 ） （自反、反自反、對(duì)稱、反對(duì)稱、傳遞） （自反、 對(duì)稱、反對(duì)稱、傳遞 ） （自反、 反對(duì)稱、傳遞） ① =關(guān)系 （自反、 對(duì)稱、反對(duì)稱、傳遞） ② 關(guān)系 （ 反自反、 反對(duì)稱、傳遞） ③ ≤關(guān)系 （自反、 反對(duì)稱、傳遞） (8)給定人群中的父子關(guān)系、婚姻關(guān)系、親戚關(guān)系、同姓關(guān)系、同齡關(guān)系 (9)整數(shù)的同余關(guān)系，幾何圖形的面積相等關(guān)系 (10)集合間的包含關(guān)系、真包含關(guān)系。 五、閉包運(yùn)算 一般來(lái)說(shuō)， A上的關(guān)系不一定具有上面討論過(guò)的某些性質(zhì)，所以想到在給定的關(guān)系 R的基礎(chǔ)上，擴(kuò)充一些序偶得一新關(guān)系 R’，使新關(guān)系具有所要求的性質(zhì)，但又希望它不太大。因此，討論最小的包含 R的 R’，使它具有所要求的性質(zhì)，這就是關(guān)系的閉包 。 關(guān)系的閉包 (closure) ?設(shè) A是 非空 集合， R是 A上的二元關(guān)系。稱 R? 是 R的自反閉包 (對(duì)稱閉包，傳遞閉包 )，如果 R?滿足： （ 1） R?是自反的 (對(duì)稱的，傳遞的 )； （ 2） R?R?； （ 3）對(duì) A上任意關(guān)系 R??， 若 R? R??，且R??是 自反的 (對(duì)稱的，傳遞的 )，必有R??R??。 R 的自反閉包、對(duì)稱閉包和傳遞閉包分別記為 r(R)， s(R)， t(R) ， 也稱 r，s， t為 閉包運(yùn)算 ， 它們作用于關(guān)系 R后，產(chǎn)生包含 R的最小的自反、對(duì)稱、傳遞的關(guān)系。 如何計(jì)算？ → 定理 ?設(shè) R是集合 A上的關(guān)系，那么， (1) r(R)=IA∪ R； (2) s(R)=R∪ R1； (3) t(R)= ={(x, y)|x?A,y?A, 且存在 n0，使得 xRny} =R+ ??? 1iiR（ 1）證明 r(R)=IA∪ R ① 因?yàn)?IA ? IA∪ R，所以 IA∪ R具有自反性； ② 顯然， R ? IA∪ R ③ 對(duì) A上任意關(guān)系 R??， 若 R? R??，且 R??是 自反的，往證 IA∪ R ?R??。 因?yàn)?R??是 自反的，所以 IA ?R?? ，又 R ? R??，所以 IA∪ R ? R??。 （ 2）證明 s(R)=R∪ R1 ① 往證 R∪ R1是對(duì)稱的，任取 (x,y)? R∪ R1 ，則 (x,y)? R或 (x,y)?R1 ， 若 (x,y)?R,則有 (y,x)?R1,所以 (y,x)?R∪ R1； 若 (x,y)?R1,則有 (y,x)?R,所以 (y,x)?R∪ R1 。 因此， R∪ R1具有對(duì)稱性。 ② 顯然， R ? R∪ R1 ③ 對(duì) A上任意關(guān)系 R??， 若 R? R??，且 R??是 對(duì)稱的，往證 R∪ R1 ?R??。 任取 (x,y)?R∪ R1 ，則 (x,y)?R或 (x,y)?R1 ， 若 (x,y)?R，因?yàn)?R? R??， 則 (x,y)?R?? ； 若 (x,y)?R1 ，則有 (y,x)?R，由 R? R??知，(y,x)?R??， 因?yàn)?R??是 對(duì)稱的 ，所以 (x,y)?R?? 。 因此， R∪ R1 ?R??。 （ 3）證明 t(R)= ???1iiR① 對(duì)于任意 x,y,z?A，若 (x,y)? ， (y,z)? , 則存在自然數(shù) j, k，使得(x,y)? Rj， (y,z)? Rk ，故 (x,z)? Rj ?Rk = Rj+k， 從而 (x， z)? ，所以， 具有傳遞性； ② 顯然， R ? ???1iiR???1iiR???1iiR ???1iiR???1iiR③ 對(duì) A上任意關(guān)系 R??， 若 R? R??，且 R??是傳遞的，往證 ?R??。 為此只要證對(duì)任意正整數(shù) n， Rn? R?? 。對(duì) n采用歸納法，n=1時(shí)，顯然有 R1? R?? 。假設(shè) n=k時(shí)有Rk? R?? ，任取 (x, y)?Rk+1，那么有 z使(x,z)?Rk， (z,y)?R。根據(jù)歸納假設(shè)及題設(shè)，有 (x,z)?R?? ， (z,y)?R??。又 R??是傳遞的 ，故 (x,y)?R?? ，所以 Rk+1? R??； 因此， ?R??。 證畢。 ???1iiR???1iiR 例 . 設(shè) A={a,b,c}， R={(a,b),(b,c),(c,a)} 則 自反閉包 r(R)=IA∪ R ={(a,b),(b,c),(c,a),(a,a),(b,b),(c,c)} 對(duì)稱閉包 s(R)=R∪ R1={(a,b),(b,c),(c,a),(b,a),(c,b),(a,c)} 傳遞閉包 t(R)= = R∪ R２ ∪ R３ =EA ???1iiR 等價(jià)關(guān)系 (equivalence relation) ?定義 設(shè) A是一個(gè) 非空 集合， R是 A上二元關(guān)系。如果 R具有自反性，對(duì)稱性，傳遞性，則稱 R是一個(gè)等價(jià)關(guān)系。 通常，用“ ? ”表示 等價(jià)關(guān)系。 ?例：整數(shù)的模 n同余關(guān)系 {(x,y)|x,y∈ Z，x,y除以 n余數(shù)相同 }， 幾何圖形的面積相等關(guān)系，人群中的同姓關(guān)系、 同齡關(guān)系等。 例： 設(shè) A為某班學(xué)生的集合，討論下列關(guān)系中，哪些是等價(jià)關(guān)系： (1) R1={(x, y)|x, y∈ A而且 x與 y同年生 }； (2) R2={(x, y)|x, y∈ A而且 x的年齡不比 y小 }； (3) R3={(x, y)|x, y∈ A而且 x與 y選修同一門課程 }； (4) R4={(x, y)|x, y∈ A而且 x的體重比 y重 }. 等價(jià)類 (equivalence class) 設(shè) A是一個(gè) 非空 集合， R是 A上的 等價(jià)關(guān)系 。A的一個(gè) 非空子集 M叫做關(guān)于 R的一個(gè)等價(jià)類，如果 1）若 a?M， b?M，則 a R b。 2）若 a?M， b?M，則 a R b；或者 , 若 a?M， a R b，則 b?M。 定理 設(shè) ?是非空集合 A上的等價(jià)關(guān)系，于是等價(jià)類是存在的。 ?證明 : 任取 a?A，令 M＝ ?x|x?A并且 x?a?， (1)顯然， M非空， a?M。 (2)任取 x1?M， x2?M，根據(jù) M的定義，則有 x1?a，x2?a，而 ?具有對(duì)稱性，傳遞性，所以 x1?x2。 (3)任取 x1?M，則 x1?a，任取 y∈ A，若 x1?y，而 ?具有對(duì)稱性，傳遞性，所以 y?a，故 y?M。 因此， M是一個(gè)等價(jià)類。 ?通常，用 [a]R表示包含元素 a的等價(jià)類，則 [a]R={x|x∈ A且 (x,a)?R} ,a稱為該 等價(jià)類的 代表元 。 例： ?設(shè)集合 A={1,2,3,?,10}， R是 模 3同余 (除以 3之后，余數(shù)相同 )關(guān)系 = {(x,y)|x,y∈ A，x,y除以 3余數(shù)相同 } ，則[3]R=[6]R=[9]R={3,6,9}, [1]R= [4]R= [7]R= [10]R={1,4,7,10} , [2]R= [5]R= [8]R= {2, 5, 8}都是等價(jià)類。 ?設(shè) A是本教室中的所有人集合， 在同姓關(guān)系下，則 本教室中 所有姓 “ 張 ” 的人構(gòu)成的集合是一個(gè) 等價(jià)類， 所有姓 “ 王 ” 的人構(gòu)成的集合是一個(gè) 等價(jià)類 , …… 。 定理 ?設(shè) ?是集合 A上的等價(jià)關(guān)系， M1, M2 , … ，是 A中關(guān)于 ?的 所有等價(jià)類。于是 A＝ M1∪ M2∪ … 并且 Mi∩ Mj=?(i?j)， 亦即，集合 A上的等價(jià)關(guān)系把 A分成了互不相交的等價(jià)類。 證明： ?任取 Mi， Mj， i?j。假設(shè) Mi∩ Mj ? ?，則必存在x?Mi∩ Mj，則任取 a?Mi， b ?Mj，都有