【正文】 X到 Y的關(guān)系， S是從 Y到 Z的關(guān)系，則 R和 S的復(fù)合關(guān)系記作 R?S 。 B 1 2 3 。 B a b c 。即 R R=R2， R2 R=R R2 =R3， … 一般地 R0 =IA， Rm Rn = Rm+n (Rm)n =Rmn (m,n為非負(fù)整數(shù) ) 例如 R是 A上關(guān)系，如上圖所示 ,可見(jiàn) a,c?R2,表明在 R圖上有從 a到 c有兩條邊的路徑 : a b c。 再證 R? RC， 任取 x,y?R, 因 R對(duì)稱(chēng)，所以有 y,x∈ R，則 x,y∈ RC, 所以 R?RC。記作 r(R)、 (s(R) 、 t(R)) (reflexive、 symmetric、 transitive) 1。 定理 A中關(guān)系 R,則 t(R)=R∪ R2∪ R3∪ ... 。 。 運(yùn)行該算法 求 t(R)的矩陣 ： 1。 定理 8：設(shè) R是 A上關(guān)系，則 ⑴ sr(R)=rs(R) ⑵ tr(R)=rt(R) ⑶ st(R)?ts(R) 證明： ⑴ sr(R)=r(R)∪ (r(R)c=(R∪ IA)∪ (R∪ IA)c = (R∪ IA)∪ (Rc∪ IAc) =R∪ IA∪ Rc∪ IA = (R∪ Rc)∪ IA= s(R)∪ IA=rs(R) ⑵ 的證明用前邊證明的結(jié)論： (R∪ IA)k= IA∪ R∪ R2∪ ...∪ Rk 很容易證明，這里從略。 4 3 1。 4 3 1。 例 X={1,2,3}, A1={{1,2,3}}, A2={{1},{2},{3}}, A3={{1,2},{3}}, A4={{1,2},{2,3}}, A5={{1},{3}} A1, A2 ,A3 ,A4 是覆蓋。 2。 2。 。不同的等價(jià)類(lèi)個(gè)數(shù) =獨(dú)立子圖個(gè)數(shù)。 ⑶ [a]R=[b]R 當(dāng)且 僅當(dāng) a,b∈ R。即 A/R={[a]R |a∈ A} 用刀分 } { 用 R分 生 日 日 快 快 樂(lè) 樂(lè) 生 例如 A={1,2,3,4,5,6,7} , R上模 3同余關(guān)系，則 A/R= {[1]R,[2]R,[3]R} ={{},{2,5},{3,6}} 練習(xí) X={1,2,3},X上關(guān)系 R R2 、 R3， 如上圖所示。 即任意 x,y∈ [a]R， 必有 x,y∈ R 證明： 任取 x,y∈ [a]R，由等價(jià)類(lèi)定義得， a,x∈ R, a,y∈ R ,由 R對(duì)稱(chēng)得， x,a∈ R， 又由 R傳遞得 x,y∈ R。 二 . 等價(jià)類(lèi) 我們經(jīng)常用等價(jià)關(guān)系對(duì)集合進(jìn)行劃分，得到的劃分塊 稱(chēng)之為等價(jià)類(lèi)。 2。 7。 作業(yè) ：第 130頁(yè) (1) 48 等價(jià)關(guān)系與等價(jià)類(lèi) 等價(jià)關(guān)系是很重要的關(guān)系，它是我們遇到最多的 關(guān)系，例如，數(shù)值相等關(guān)系 =、命題間的等價(jià)關(guān) 系 ? 、三角形相似 ∽ 和全等關(guān)系 ≌ ， ….. 一 .等價(jià)關(guān)系 :設(shè) R是 A上關(guān)系 ,若 R是自反的、對(duì)稱(chēng)的和 傳遞的，則稱(chēng) R是 A中的等價(jià)關(guān)系。 4 3 r(R) s(R) t(R) sr(R) rs(R) tr(R) rt(R) st(R) ts(R) 本節(jié)重點(diǎn)掌握閉包的定義、計(jì)算方法和性 質(zhì)。 4 3 1。 4 3 1。 ②假設(shè) i≤k 時(shí)結(jié)論成立，即 (R∪ IA)k= IA∪ R∪ R2∪ ...∪ Rk (R2)c=(R R)c =Rc Rc =(Rc)2 ③ 當(dāng) i=k+1時(shí) (R∪ IA)k+1=(R∪ IA)k (R∪ IA) = (IA∪ R∪ R2∪ ...∪ Rk） (IA∪ R) = (IA∪ R∪ R2∪ ...∪ Rk)∪ (R∪ R2∪ ...∪ Rk+1) = IA∪ R∪ R2∪ ...∪ Rk∪ Rk+1 所以結(jié)論成立 . t(r(R))=t(R∪ IA) = (R∪ IA)∪ (R∪ IA)2∪ (R∪ IA)3∪ ... =(IA∪ R)∪ (IA∪ R∪ R2)∪ (IA∪ R∪ R2∪ R3)∪ ... = IA∪ R∪ R2∪ R3∪ ...= IA∪ t(R) = IA∪ R (R傳遞 t(R)=R) =r(R) 所以 r(R)也傳遞。 ⑶ 對(duì)所有 j ,如果 A[j,i] =1 ,則對(duì) k=1,2,…,n A[j,k]:=A[j,k]+A[i,k]。 最后得 R’=R”，所以 t(R)=R∪ R2∪ ...∪ Rn 定理證畢。 所以 R’就是 R的自反閉包。 。 證明 ： 充分性 ，已知 RC? SC ，則任取 x,y∈ R ?y, x?RC? y, x?SC ? x,y?S ∴ R?S 必要性 ，已知 R? S，則任取 y,x∈ RC ? x,y?R?x,y?S ?y,x?SC ∴ RC?SC 6.(~R)C=~RC 證明 :任取 y,x∈ (~R)C ?x,y∈ ~R?x,y?R ?y,x?RC ?y,x∈ ~RC ∴ .(~R)C=~RC R是從 X到 Y的關(guān)系， S是 Y到 Z的關(guān)系，則 (R S)C= SC RC 。 d 1。 3。 3。 作業(yè) 第 113頁(yè) ⑴、⑶、⑷ 44 關(guān)系的復(fù)合 二元關(guān)系除了可進(jìn)行集合并、交、補(bǔ)等運(yùn)算外， 還可以進(jìn)行一些新的運(yùn)算，先介紹由兩個(gè)關(guān)系生 成一種新的關(guān)系，即關(guān)系的復(fù)合運(yùn)算。 。 2。 1。 例如 A={1,2},下面 A中關(guān)系 R是傳遞的 . 通過(guò)帶量詞的公式在論域展開(kāi)式說(shuō)明 R在 A上傳遞 ??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz) ??x?y?z((xRy?yRz)?xRz) (為了簡(jiǎn)單做些刪改 ) ? ?y?z((1Ry?yRz)?1Rz)??y?z((2Ry?yRz)?2Rz) ? (?z((1R1?1Rz)?1Rz)??z((1R2?2Rz)?1Rz) ?(?z((2R1?1Rz)?2Rz) ?(?z((2R2?2Rz)?2Rz)) ?(((1R1?1R1)?1R1)?((1R1?1R2)?1R2)) ? (((1R2?2R1)?1R1)?((1R2?2R2)?1R2)) ? (((2R1?1R1)?2R1)? ((2R1?1R2)?2R2)) ? (((2R2?2R1)?2R1)) ? ((2R2?2R2)?2R2)) ? (((F?F)?F)?((F?T)?T))?(((T?F)?F)?((T?F)?T))? (((F?F)?F)? ((F?T)?F))?(((F?F)?F))?((F?F)?F))?T 1? ?2 下邊 R R R R R8均是傳遞的關(guān)系 。 。 R 下邊 R R R R R8均是反對(duì)稱(chēng)關(guān)系。 3 3 3 3 1。 R是 A上對(duì)稱(chēng)的 ??x?y((x?A?y?A?xRy) ?yRx) 從關(guān)系有向圖看對(duì)稱(chēng)性 :在兩個(gè)不同的結(jié)點(diǎn) 之間，若有邊的話，則有方向相反的兩條邊。 1。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 可見(jiàn)這八個(gè)關(guān)系中 R R R4是自反的。 。 3 0 0 0 0 0 0 0 0 0 3 3 MΦ= MA A= Φ A A IA 五 . 關(guān)系的集合運(yùn)算 由于關(guān)系就是集合，所以集合的 ∩、 ∪ 、 、 ?和 ~運(yùn)算對(duì)關(guān)系也適用。 2 3 R4 : R3 : ： 有限集合之間的關(guān)系也可以用矩陣來(lái)表示，這種表示 法便于用計(jì)算機(jī)來(lái)處理關(guān)系。 ： 即用謂詞公式表示序偶的第一元素與第二元素間的關(guān)系。 設(shè) A,B,C是任意集合，則 ⑴ A?(B∪ C)= (A?B)∪ (A?C)； ⑵ A?(B∩C)= (A?B)∩(A?C)； ⑶ (A∪ B)?C= (A?C)∪ (B?C)； ⑷ (A∩B)?C= (A?C)∩(B?C) 證明⑴ ：任取 x,y?A?(B∪ C) ?x?A ?y?B∪ C ?x?A ?(y?B∨ y?C) ?( x?A ?y?B)∨ (x?A?y?C) ?x,y?A?B∨ x,y?A?C ?x,y?(A?B)∪ (A?C) 所以⑴式成立。設(shè) x表示 上衣 ,y表示褲子 ,(x,y)可以表示一個(gè)人的著裝。? , yn ?( x1= y1)? ( x2= y2) ?? ?( xn= yn) 二 .集合的 笛卡爾積 例如“斗獸棋”的 16顆棋子， 可看成是由兩種顏色的集合 A和 8種動(dòng)物的集合 B組成的。 二元 關(guān)系簡(jiǎn)稱(chēng)為關(guān)系。 。 。 2。 。 。 1。 。 1。 2。 。 。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 本節(jié)要求 ： 。 2。 證明 ： 必要性 : 已知 R是對(duì)稱(chēng)和傳遞的。 。 C 1 2 3 。 。 RC={y,x|x,y?R} y,x∈ RC ?x,y?R 二 . 計(jì)算方法 1. R={1,2,2,3,3,4,4,5} RC ={2,1,3,2,4,3,5,4} 2. RC的有向圖：是將 R的有向圖的所有邊的方向顛倒一下即可。 作業(yè) ：第 118頁(yè)⑴、⑵ a)b)、⑶、⑸ 46 關(guān)系的閉包運(yùn)算 關(guān)系的閉包是個(gè)很有用的概念，特別是傳遞閉 包。 。 ∴ R’?R”。 x e1 ej1 ej =ek ej+1 。 定理 6. R是 A上關(guān)系，則 ⑴ R是自反的，則 s(R)和 t(R)也自反。 2。 2。 2。如 A1 。 A={1} A={1,2} A={1,2,3} : 上邊 的模 3同余關(guān)系 R的圖： 從關(guān)系圖可看 出， R是自反、 對(duì)稱(chēng)、傳遞的 關(guān)系，所以 R是等價(jià)關(guān)系。 3 3 1。 2。 3 R2 1。 證明： A中任何元素 a,由于有 aRa,所以 a∈ [a]R ， 如果 a∈ [b]R ， 所以有 a,b∈ ⑶得 [a]R=[b]R 。 (因?yàn)橐?a,b∈ R， 要么 a,b?R。 。 3 3 R3 R4 R7 R8 思考題 ： A={1,2,3},可構(gòu)造多少個(gè) A中不同的等價(jià) 關(guān)系？可以根據(jù)等價(jià)關(guān)系有向圖的特點(diǎn)來(lái)考慮。 。 上述關(guān)系 R圖就是由三個(gè)獨(dú)立的完全圖構(gòu)成的。即每個(gè)劃分塊里 只有一個(gè)元素的劃分。 。 。 。 ⑶ R是傳遞的，則 r(R)也傳遞。 。其實(shí)則不然，請(qǐng)看下例 : A={1,2,3} A中關(guān)系 R1,R2,R3,如下： R1={1,2,3,2} R2 ={1,2,3,1} R3 ={1,2,3,3} ={1,2} = =Φ 所以 t(R1)= ∪ ∪ = R1 ={1,3,2,1,3,2} ={1,1,2,2,3,3} =IA, = R2 ... t(R2)= R2∪ ∪ ={1,3,2,3,3,3} = t(R3)= R2∪ 2 R1 3 R1 4 R1 1 R1 2 R1 3 R1 2 R2 3 R2 4 R2 3 R2 2 R2 3 R2 3 R3 2 R3 2 R3 2 R3 定理 A中關(guān)系 R,如果 A是有限集合， |A|=n 則 t(R)=R∪ R2∪ ...∪ Rn 。 2。這里要介紹關(guān)系的自反閉包、對(duì) 稱(chēng)閉包和傳遞閉包。如 三 .性質(zhì) 令 R、 S都是從 X到 Y的關(guān)系，則 1. (RC)C = R 2. (R∪ S)C = RC∪ SC 。 a b c 。 1 0 0 0 0 1 0 1 0 0 0 0