【正文】 R 上的小于等于關(guān)系 ?是自反的 。 四、 作業(yè)與實(shí)驗(yàn) （ 2 分鐘） 1. 書面作業(yè)： 習(xí)題 12(選 ). 2. 上機(jī)作業(yè)：無 33 第 七 講：關(guān)系（三） 一、教學(xué)目標(biāo) 1. 理解 關(guān)系 的 各種 性質(zhì) 2. 掌握 滿足各種性質(zhì)的關(guān)系的關(guān)系矩陣和關(guān)系圖 3. 理解閉包的含義 4. 掌握閉包的幾個(gè)關(guān)鍵 5. 掌握閉包的構(gòu)造 二、重點(diǎn)與難點(diǎn)分析 ： 自反性、反自反性、對(duì)稱性、反對(duì)稱性、傳遞性概念的理解， 閉包的理解與構(gòu)造 ：同上 三、教學(xué)內(nèi)容與教學(xué)過程 （ 5 分鐘） 關(guān)系的集合運(yùn)算 關(guān)系的逆運(yùn)算 關(guān)系的復(fù)合運(yùn)算 ，開始第 七 講 本講知識(shí)點(diǎn)概括 (1)關(guān)系的性質(zhì) ① 自反性 （ 10 分鐘） 定義： 對(duì)于集合 A 上的元素 a 屬于 A，有 (a,a)屬于 R,那么 R 就是一個(gè)自反關(guān)系 例 225： A = {a, b, c, d}, R = {(a, a), (a, b), (b, b), (c, c), (c, a), (d, d)}? 注： Z 上的整除關(guān)系 |是自反的 。( 3 ) ( ) ( ) 。 (1)關(guān)系的集合運(yùn)算 （ 15 分鐘） 關(guān)系 的幾種 常見 集合運(yùn)算 : , : , , , , .R S A B R S R S R R S R S? ? ? ? ? ? 注： R A B R A B RR A A R A A R? ? ? ? ? ?? ? ? ? ? ? { 1 , 2 , 3 , 4 } , R = { ( x , y ) | ( x , y ) / 2 x , y A } , S = { ( x , y ) | ( x y ) / 3 x , y A } ,A ? ? ?? ? ?例 ： 設(shè) 若 是 整 數(shù) ， 是 正 整 數(shù) ，求 R S , R S , S R , R , R S 解：R= {( 1 ,1 ) ,( 1 ,3 ) ,( 2 ,2 ) ,( 2 ,4 ) ,( 3 ,1 ) ,( 3 ,3 ) ,( 4 ,2 ) ,( 4 ,4 ) }S = {( 4 ,1 ) }R S = {( 1 ,1 ) ,( 1 ,3 ) ,( 2 ,2 ) ,( 2 ,4 ) ,( 3 ,1 ) ,( 3 ,3 ) , ( 4 ,2 ) ,( 4 ,4 ) ,( 4 ,1 ) }R S =S R= S = {( 4 ,1 ) }R= A A R= {( 1 ,2 ) ,( 1 ,4 ) ,( 2 ,1 ) ,( 2 ,3 ) ,( 3 ,2 ) ,( 3 ,4 ) ,( 4 ,1 ) ,( 4 ,3 ) }R S = (????? R S ) ( R S ) = R S= {( 1 ,1 ) ,( 1 ,3 ) ,( 2 ,2 ) ,( 2 ,4 ) ,( 3 ,1 ) ,( 3 ,3 ) ,( 4 ,2 ) ,( 4 ,4 ) ,( 4 ,1 ) }? ? ? 例 217 (2)關(guān)系的逆運(yùn)算 （ 20 分鐘） 為何考慮關(guān)系的逆運(yùn)算 ? 若 x是 y的老師 ,則 y 是 x 的學(xué)生 , ? 30 ① 定義 ： 1 {( , ) | ( , ) }R A B R y x x y R B A?? ? ? ? ? ? ? 注： 1R? 就是將所有 R中的有序?qū)χ械膬蓚€(gè)元素交換次序， 例 218： A = {a, b, c, d}, B = {1, 2, 3}, R = {(a, 3), (c, 2), (a, 2), (b, 2)}. 則 1 {( 3 , ) , ( 2 , ) , ( 2 , ) , ( 2 , ) }R a c a b? ? ② 逆關(guān)系的關(guān)系圖1RG? 有向線條反向 （圖示例 218） ③逆關(guān)系的關(guān)系矩陣1RM? 原關(guān)系的關(guān)系矩陣的轉(zhuǎn)置 （示例 218） ④ 逆運(yùn)算的性質(zhì)： 定理 22： 11()RR??? （ 對(duì)合律 ） 定理 23： 逆運(yùn)算與關(guān)系的集合運(yùn)算并 , 交 , 補(bǔ)的關(guān)系 11111111()()()R S R SR S R SRR????????? ? ?? ? ?? 證明 ： （ 111()R S R S???? ? ?）：11111( , ) ( ) ( , )( , ) , ( , ) ( , ) , ( , )( , ) .u v R S v u R Sv u R v u S u v R u v Su v R S?????? ? ? ? ? ?? ? ? ? ? ?? ? ? (3)關(guān)系的復(fù)合運(yùn)算 （ 35 分鐘） 為何考慮關(guān)系的復(fù)合運(yùn)算 ? 若 x 是 y 的母親 , y 是 z的妻子 , 則 x 是 z 的岳母 , ? ① 關(guān)系 R 到關(guān)系 S 的復(fù)合運(yùn)算 （ 10 分鐘） ,{ ( , ) | , ( , ) , ( , ) } .R A B S B CR S x z y B x y R y z S? ? ? ?? ? ? ? ? ? 例： { ( 3 , 3 ) , (6 , 2 ) } , { ( 2 , 3 ) }FG??，則： { (6 , 3 ) } , { ( 2 , 3 ) }F G G F?? 例 219： },{},4,3,2,1{},{ ??????? CBdcbaA ) } ,3(),2(),2(),1{( ?????S ) } ,4,(),3,(),2,(),2,(),1,{( cdbaaR ? ) } .,(),(),(),(),(),{( ?????? dbbaaaSR ?? ? 借助關(guān)系圖理解復(fù)合運(yùn)算 ： 31 關(guān)系矩陣： 4 *4 4 *41 1 1,00110RsRMMM??? ??? ? ??? ? ??? ? ??? ? ??? ?? ? ? ?? ? ? ?? ??? ???? ? ??? ? ? ??? ???? ? ??? ?? ? ? ???? ? ? ?? ??? ? ??? ? ??? ? ? ??? ???? ? ??? ?? ? ? ???? ? ??? ???? ? ??? ? ??? ? ??? ?? ? ? ???? ??? ? ??? ???? ??? ???? ? ??? ???? ??? ? ??? ? ??? ???? ? ??? ???? ??1100??? ? ??? ? ??? ? ??? ???? ? ??? ?? ? ? ? ?? ? ? ? ?? ??? ???? ? ??? ? ? ??? ???? ? ??? ?? ? ? ? ? ??? ? ? ? ? ?? ??? ???? ? ??? ? ? ??? ? ??? ? ??? ?? ? ? ? ? ???? ? ??? ? ??? ? ??? ???? ? ??? ?? ? ? ? ? ②復(fù)合關(guān)系的性質(zhì) （ 10分鐘） R ? S ? S ? R. 例 ： R ={(x,y)|x,y?A, y = x+1 或 y = x/2} )}1,2(),0,0(),3,2(),2,1(),1,0{(? S ={(x, y)| x,y?A, x = y +2} )}1,3(),0,2{(? )}1,2(),0,1{(?SR ? ≠ )}2,3(),0,2(),1,2{(?RS ? 定理 24： .)()( TSRTSRTSR ?????? ?? 證明思路 ： )()( TSRTSR ???? ? )()( TSRTSR ???? ? 定理 25： ).()()( TRSRTSR ??? ??? ).()()( TRSRTSR ??? ??? 定理 26： .)( 111 ??? ? RSSR ?? 證明 ： SRuvSRvu ?? ???? ? ),()(),( 1 SuyRyvBy ????? ),(,),(: .),( ),(,),(: 1111?????? ????? RSvu SyuRvyBy ? 注： 本性質(zhì)與矩陣的有關(guān)運(yùn)算性質(zhì)類似 , 請(qǐng)注意順序 .)(,)( 111 TTT ABABABAB ?? ??? 定理 27： , BR R R I R? ? ? ?A設(shè) R A B, 則 ： I ③冪運(yùn)算 （ 10 分鐘） 冪的表示方式 ：0 1 21: , , , . . .. . . , 2 .AnnnnR A A R I R R R R RR R R R nR R R?? ? ? ? ???? 例 223： 設(shè) A={a,b,c},集合 A上的關(guān)系 R={(a,b),(b,c),(c,a)},試計(jì)算 nR 32 1234 3 5 3 2 23 3 1 3 2 2{( , ) , ( , ) , ( , ) },{( , ) , ( , ) , ( , ) },{( , ) , ( , ) , ( , ) },Ak k kAR R a b b c c aR a c b a c bR a a b b c c IR R R R R R R RR I R R R R???????? ? ? ? ?? ? ? ? 冪運(yùn)算的性質(zhì)：11,。 例 216 4. 教學(xué)小結(jié) （ 3 分鐘） 本講首先講解關(guān)系的概念與表示，特別介紹了二元關(guān)系，同時(shí)描述了三種特殊的關(guān)系：空關(guān)系、全關(guān)系、恒等關(guān)系， 然后講解了關(guān)系的三種表示方 28 式： 集合表示法、關(guān)系 圖表示法 、關(guān)系矩陣表示法，接著講解了關(guān)系與函數(shù)的區(qū)別與聯(lián)系及它們間的轉(zhuǎn)換。 B = {英語(yǔ) , C 語(yǔ)言 , 離散數(shù)學(xué) , 數(shù)據(jù)結(jié)構(gòu) , 匯編語(yǔ)言 }。摩根律： A B A BA B A B? ? ?? ? ? P25： ,?? 運(yùn) 算 的 重 要 性 質(zhì) ④ 差運(yùn)算 （ 10 分鐘） 定義 ： { | }A B x x A? ? ? ?且 xB 例 143： { , , } { , , , , } { }{ , , , , } { , , } { , , }a b c b c d e f ab c d e f a b c d e f???? 定理 123： A B A B? ? ? 證明： ,x A B x A x B x A x B x A B? ? ? ? ? ? ? ? ? ? ? ? 例 145：證明： ( ) ( )A B C A B C? ? ? ? ? 證： ( ) ( ) ( )( ) ( )A B C A B C A B CA B C A B C? ? ? ? ? ? ? ?? ? ? ? ? ? 例 146： A B A B? ? ? ? ? 例 147： ( ) ( ) ( ) ( )( ) ( )A B A C A B A CA B C A B C A B C? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? A B C? ? ? ⑤ 對(duì)稱差運(yùn)算 （ 10 分鐘） )(ACA U? 22 定義 ： ( ) ( )A B A B B A? ? ? ? ? 例 { , , } { , , , , } { , , , }a b c b c d e f a d e f?? 定理 124：()A =AA B C =A B CA A =A B B AA? ? ?? ? ? ? ? ? ?? ? ? ???交 換 律（ 是 的 單 位 元 素 ）（ ） （ ） （ 結(jié) 合 律 ） 容斥原理 形式 ： 或： A B U A B A B? ? ? ? ? ? 例： 求 1到 1000 之間（包含 1 和 1000 在內(nèi)）既不能被 5和 6整 除數(shù) 有多少個(gè)？ 解： |S| = 1000 |A|=?1000/5?=200, |B|=?1000/6?=166 |A?B| = ?1000/lcm(5,6)? = ?1000/33? = 33 1 0 0 0 2 0 0 1 6 6 3 3 6 6 7AB? ? ? ? ? ? （ 2）集合的劃分與覆蓋 （ 12分鐘） ①劃分 定義： { | , }iiA A A i I? ? ? ? 其中：,iijiiIA i IA A i jAA?? ? ? ?? ? ? ? ?? 例 153： 設(shè) A = {a, b, c}, 則 A的所有不 同的劃分分別為 : ②覆蓋