【導(dǎo)讀】滁州學(xué)院計(jì)算機(jī)與信息工程學(xué)院?！峨x散數(shù)學(xué)》教學(xué)大綱。課程代碼：學(xué)時(shí)：48學(xué)分：3. 本大綱根據(jù)2020版應(yīng)用型人才培養(yǎng)方案制訂。（一）教學(xué)對(duì)象：網(wǎng)絡(luò)工程、計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科學(xué)生。（五）參考教材：《離散數(shù)學(xué)》第2版鄧輝文清華大學(xué)出版社2020.[1]邵學(xué)才,葉秀明.離散數(shù)學(xué)[M].北京電子工業(yè)出版社，2020.及應(yīng)用、操作系統(tǒng)、數(shù)字邏輯、人工智能、算法分析與設(shè)計(jì)等。離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的學(xué)科,它在各學(xué)科領(lǐng)域特別在。計(jì)算機(jī)科學(xué)領(lǐng)域有著廣泛的應(yīng)用，同時(shí)離散數(shù)學(xué)也是計(jì)算機(jī)專業(yè)的許多專業(yè)課程。必不可少的先行課程。本課程的教學(xué)目的旨在通過(guò)對(duì)離散數(shù)學(xué)的教學(xué)，讓學(xué)生不但可以掌握處理如。而且為學(xué)生今后提高專業(yè)理論水平，從事計(jì)算機(jī)行業(yè)的實(shí)際工作提供必備的抽象。思維和嚴(yán)格的邏輯推理能力，為將來(lái)參與創(chuàng)新性的研究和開(kāi)發(fā)工作打下堅(jiān)實(shí)的基。講課實(shí)驗(yàn)上機(jī)其他。2命題邏輯等值演算。第二部分集合論講授13. 最短路問(wèn)題與貨郎擔(dān)

　　

【正文】 ????????? (3)函數(shù)的關(guān)系定義 （ 5分鐘） ① 函數(shù) 到 關(guān)系 的轉(zhuǎn)換 例： A = {a, b, c}, B = {1, 2, 3}, f: A ? B, f(a) = 2, f(b) = 3, f(c) = 3. ( ) ( , ){ ( , 2 ) , ( , 3 ) , ( , 3 ) }f x y x y ff a b c? ? ??? ② 關(guān)系能夠轉(zhuǎn)換成函數(shù)的條件 1 2 1 2( , ) , ( , )d o m f Ax y f x y f y y?? ? ? ? ? 例： { , , } , { 1 , 2 , 3 , 4 } , { ( , 1 ) , ( , 2 ) , ( , 4 ) , ( , 3 ) }A x y z B R x y z y? ? ?，不能轉(zhuǎn)換成函數(shù)。 例 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)換。 四、 作業(yè)與實(shí)驗(yàn) （ 2 分鐘） 1. 書(shū)面作業(yè)： 習(xí)題 ： 4(2)(4)(5)、 1 14. 2. 上機(jī)作業(yè)：無(wú) 29 第 六 講：關(guān)系（二） 一、教學(xué)目標(biāo) 1. 掌握 關(guān)系的集合運(yùn)算 2. 掌握 關(guān)系的逆運(yùn)算， 逆關(guān)系的關(guān)系矩陣、關(guān)系圖 及逆關(guān)系的定理 3. 掌握復(fù)合關(guān)系、 復(fù)合關(guān)系相關(guān) 定理 4. 了解函數(shù)的復(fù)合運(yùn)算 二、重點(diǎn)與難點(diǎn)分析 ：復(fù)合關(guān)系、逆關(guān)系 的概念 及相關(guān)性質(zhì) ：復(fù)合關(guān)系、逆關(guān)系的性質(zhì) 三、 教學(xué)內(nèi)容與教學(xué)過(guò)程 （ 10 分鐘） （ 5 分鐘） N元關(guān)系的定義 2元關(guān)系 關(guān)系的定義域與值域 關(guān)系的表示 函數(shù)的關(guān)系定義 ，開(kāi)始第 六 講。 (1)關(guān)系的集合運(yùn)算 （ 15 分鐘） 關(guān)系 的幾種 常見(jià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,。( 2) ( ) 。( 3 ) ( ) ( ) 。m n m nm n m nmmR A A m nR R RRRRR????????設(shè) ， 對(duì) 于 非 負(fù) 整 數(shù) ， 有(1) ④函數(shù)的復(fù)合運(yùn)算 （ 5分鐘） 設(shè) f: A ? B, g: B ? C,函數(shù) f 與函數(shù) g的復(fù)合記為 f?g: 若 f (x) = y 且 g(y) = z, 則 (f?g)(x) = g(f(x)) = z. 由于 f ? A ? B, g ? B ? C, 關(guān)系 f 與關(guān)系 g的復(fù)合記為 f?g: 若 (x, y) ? f且 (y, z) ? g, 則 (x, z) ? f?g. 注： 函數(shù) f與函數(shù) g的復(fù)合 f?g與將其看作關(guān)系時(shí)關(guān)系 f與關(guān)系 g的復(fù)合是一致的 4. 教學(xué)小結(jié) （ 3 分鐘） 本講分別介紹了關(guān)系 的集合運(yùn)算、逆運(yùn)算 ， 復(fù)合運(yùn)算， 并且對(duì)復(fù)合關(guān)系、逆關(guān)系的定義、表示方式、相應(yīng)的關(guān)系矩陣進(jìn)行了講解， 還介紹了它們之間 滿足的相關(guān)性質(zhì) ，最后介紹了 函數(shù)的復(fù)合運(yùn)算 。 四、 作業(yè)與實(shí)驗(yàn) （ 2 分鐘） 1. 書(shū)面作業(yè)： 習(xí)題 12(選 ). 2. 上機(jī)作業(yè)：無(wú) 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é)過(guò)程 （ 5 分鐘） 關(guān)系的集合運(yùn)算 關(guān)系的逆運(yùn)算 關(guān)系的復(fù)合運(yùn)算 ，開(kāi)始第 七 講 本講知識(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)系 |是自反的 。 P(X)上的包含關(guān)系 ? 是自反的 。 R 上的小于等于關(guān)系 ?是自反的 。 R