離散數(shù)學(xué)教案全案設(shè)計(jì)--教案.學(xué)案

1、 滁州學(xué)院計(jì)算機(jī)與信息工程學(xué)院課程教案課程名稱(chēng)： 離散數(shù)學(xué)授課教師： 趙歡歡授課對(duì)象：11級(jí)網(wǎng)絡(luò)工程專(zhuān)業(yè) 3、4班授課時(shí)間：2012年9月-2012年12月滁州學(xué)院計(jì)算機(jī)科學(xué)與信息工程學(xué)院2012年8月離散數(shù)學(xué) 教學(xué)大綱（ Discrete Mathematic）課程代碼： 學(xué)時(shí)： 48 學(xué)分： 3一、課程簡(jiǎn)介本大綱根據(jù) 2009 版應(yīng)用型人才培養(yǎng)方案制訂。（一）教學(xué)對(duì)象：網(wǎng)絡(luò)工程、計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)本科學(xué)生（二）開(kāi)課學(xué)期：第三學(xué)期（三）課程類(lèi)別：專(zhuān)業(yè)基礎(chǔ)課（四）考核方式：考試（五）參考教材：離散數(shù)學(xué)第 2 版 鄧輝文 清華大學(xué)出版社 2010. 主要參考書(shū)目：邵學(xué)才，葉秀明離散數(shù)學(xué)M.北京

2、電子工業(yè)出版社，2009.邵志清，虞慧群.離散數(shù)學(xué)M.北京電子工業(yè)出版社，2003.屈婉玲.離散數(shù)學(xué)習(xí)題解析M.北京大學(xué)出版社，2008.本課程的先修課程是高等數(shù)學(xué)、線性代數(shù)，后續(xù)課程包含數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)原理 及應(yīng)用、操作系統(tǒng)、數(shù)字邏輯、人工智能、算法分析與設(shè)計(jì)等。二、教學(xué)基本要求與內(nèi)容安排（一）教學(xué)目的與要求離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的學(xué)科 ,它在各學(xué)科領(lǐng)域特別在計(jì) 算機(jī)科學(xué)領(lǐng)域有著廣泛的應(yīng)用，同時(shí)離散數(shù)學(xué)也是計(jì)算機(jī)專(zhuān)業(yè)的許多專(zhuān)業(yè)課程必 不可少的先行課程。本課程的教學(xué)目的旨在通過(guò)對(duì)離散數(shù)學(xué)的教學(xué)，讓學(xué)生不但可以掌握處理如 集合、代數(shù)結(jié)構(gòu)和圖等離散結(jié)構(gòu)的描述工具和方法，為后續(xù)課程的

3、學(xué)習(xí)創(chuàng)造條件， 而且為學(xué)生今后提高專(zhuān)業(yè)理論水平，從事計(jì)算機(jī)行業(yè)的實(shí)際工作提供必備的抽象 思維和嚴(yán)格的邏輯推理能力，為將來(lái)參與創(chuàng)新性的研究和開(kāi)發(fā)工作打下堅(jiān)實(shí)的基 礎(chǔ)。（二）教學(xué)內(nèi)容安排教學(xué)內(nèi)容教學(xué)教學(xué)重點(diǎn)難點(diǎn)學(xué)時(shí)分配備注要求方法()()講課實(shí) 驗(yàn)上 機(jī)苴丿、他第一部分?jǐn)?shù)理邏輯講授15.51命題邏輯的基本概念21.1命題與聯(lián)接詞B11.2命題公式及其賦值A(chǔ)12命題邏輯等值演算3.52.1等值式B122析取范式與合取范式A12.3聯(lián)接詞的完備集C0.52.4可滿(mǎn)足性與消解法B13命題邏輯的推理理論23.1推理的形式結(jié)構(gòu)A13.2自然推理系統(tǒng)PB14一階邏輯基本概念24.1 一階邏輯命題符號(hào)化A14.

4、2 一階邏輯公式及解釋A15 一階邏輯等值演算與推 理35.1一階邏輯等值式與置換規(guī)則A15.2 一階邏輯前束范式A15.3 一階邏輯的推理理論A16數(shù)理邏輯在計(jì)算機(jī)中的 應(yīng)用3第二部分集合論講授131集合代數(shù)21.1集合的基本概念B0.51.2集合的運(yùn)算A0.51.3有窮集的計(jì)數(shù)C0.51.4集合恒等式A0.52二兀關(guān)系62.1有序?qū)εc笛卡爾積A12.2二兀關(guān)系A(chǔ)12.3關(guān)系的運(yùn)算A12.4關(guān)系的性質(zhì)A12.5關(guān)系的閉包A12.6等價(jià)關(guān)系與劃分A13函數(shù)33.1函數(shù)的定義與性質(zhì)A0.53.2函數(shù)的復(fù)合與反函數(shù)A0.53.3雙射函數(shù)與集合的基 數(shù)CA13.4 個(gè)電話系統(tǒng)的描述 實(shí)例CA14集合

5、論在計(jì)算機(jī)中的應(yīng) 用2第三部分代數(shù)結(jié)構(gòu)講授61.51代數(shù)系統(tǒng)31.1二元運(yùn)算及其性質(zhì)A11.2代數(shù)系統(tǒng)A11.3代數(shù)系統(tǒng)的同態(tài)與同 構(gòu)BA12群與環(huán)32.1群的定義及其性質(zhì)A12.2循環(huán)群與置換群AA2第四部分圖論講授121圖的基本概念2.51.1圖A0.51.2連通與回路A0.51.3圖的連通性A0.51.4圖的矩陣表示A0.51.5圖的運(yùn)算AA0.52歐拉圖與哈密頓圖22.1歐拉圖A0.52.2哈密頓圖A0.52.3最短路問(wèn)題與貨郎擔(dān) 問(wèn)題CA13樹(shù)1.53.1無(wú)向樹(shù)及其性質(zhì)A0.53.2生成樹(shù)A0.53.3根樹(shù)及其應(yīng)用B0.54平面圖34.1平面圖的基本概念B0.54.2歐拉公式B0.5

6、4.3平面圖的判斷B14.4平面圖的對(duì)偶圖C15圖論在計(jì)算機(jī)中的應(yīng)用3（教學(xué)要求：A熟練掌握；B掌握；C了解）三、實(shí)驗(yàn)內(nèi)容本課程無(wú)實(shí)驗(yàn)制訂人（簽字）：學(xué)進(jìn)審核人（簽字）：教度表20122013學(xué)年第1學(xué)期授課教師姓名趙歡歡職稱(chēng)助教周數(shù) 16周計(jì)劃學(xué)時(shí)48學(xué)時(shí)授課專(zhuān)業(yè)網(wǎng)絡(luò)工程班級(jí)2011 級(jí)講課48學(xué)時(shí)課堂討論0學(xué)時(shí)課程名稱(chēng)離散數(shù)學(xué)實(shí)驗(yàn)課 0 學(xué)時(shí)習(xí)題課 0學(xué)時(shí)教材名稱(chēng)離散數(shù)學(xué)其他環(huán)節(jié)0學(xué)時(shí)出版社清華大學(xué)出版社-周學(xué)時(shí)中 其要稱(chēng) 名摘的驗(yàn)容實(shí)內(nèi)趴等要學(xué)綢容教仙 的 述 講 名 節(jié) 章 z(周次 日期講課實(shí)驗(yàn)課習(xí)題課課堂討論其他環(huán)節(jié)日周3 9一9M一44rT 只 映 耳R合 L 復(fù) 刪元！I L

7、映 n映、 、 二二 合 合用 集隼集加 講念幕5念卿 第S第哉 基、有的 厶口合集射映 集：映： 1論 2論 1理仁理日16510月日 第鋼22-集伽 講質(zhì)才 三性4 第和曲日2344關(guān) 劃 、 妁 或 等合 值 OM集 煒 合第 義 叩集運(yùn) 定 (B5本合 的 算力基集 系 等數(shù)-)關(guān) 郃笛補(bǔ)垛講 2 集集茫htx .5差可第兒系 呻亠處w扯佞 第算車(chē)伽念系數(shù) 運(yùn)的集概朕函 的合、的元、 合集蓋系門(mén)赤 集：覆關(guān)表 4論與 1論的 1理分 2理系日30 周24月日 四月9 第9至22算 運(yùn) 二合 (-復(fù) 系、 關(guān)算運(yùn) 講逆 六第氯 1 2理日7 周1月 五月10日 第10至44的XI 稱(chēng)低

8、)對(duì)S 三、包 z( 三可 系包反加 關(guān)閉自押 的反區(qū) 講系、八 七關(guān)性低 第4反r 2自包 質(zhì)恍 性的自 的系E; 假系關(guān)酬 燦關(guān) 萬(wàn) 3 7 國(guó) 2理日14 周8月 六月O日 第鋼22四骨“ 士糸 Z/IX分闿-一介一匸 系7 ;殊 關(guān)2類(lèi)特價(jià)的 講系等中 八關(guān)集 第W-厶庫(kù)系圖 系關(guān)斯 仆杯哈 等：兒 5論定 2理的日21訕150M日第1OM144一司3二命 Z/IX、. Z/IX 輯祇瀝輯低 邏單命 邏 號(hào) 題塑再題符 命遇命矽 講33、講#0 九值斷十表、 第真判第值義 念與的真定 概義假 其的 關(guān)定真及式型 有的,式公類(lèi) 的題義公題的 題命含題命式 命：的命公 1論詞 3論題 3理

9、接 3理命系主任簽名：院長(zhǎng)簽名：第八周10月22日 至10月28日22第一講 命題邏輯（三）3.4邏輯等值的命題公式理論：邏輯等值的定義、基本等值式、等值演算法、對(duì)偶原 理第九周 10月29日 至11月4日44第十二講命題邏輯（四）3.5命題公式的范式 理論：命題公式的析取范式和合取范式的定義域求法 命題公式的主析取范式及主合取范式的定義和求法 第十三講命題邏輯（五）3.7命題邏輯中的推理理論：推理形式有效性的定義；基本推理規(guī)則；命題邏輯的自然推理系統(tǒng)第十周11月5日 至11月11日22第十四講謂詞邏輯（一）4.1個(gè)體、謂詞、量詞和函詞理論：謂詞邏輯概念，謂詞的概念與表示，量詞的概念與表示，

10、個(gè)體域，轄域，約束變?cè)妥杂勺冊(cè)暮x%144第十五講謂詞邏輯（二）4.2謂詞公式及命題的符號(hào)化4.3謂詞公式的解釋及類(lèi)型理論：謂詞公式的定義，將命題用用符號(hào)（個(gè)體，量詞，謂詞） 來(lái)表示，消去量詞的邏輯等值式，永真式，科滿(mǎn)足式，永假式及中性式的概念第十六講謂詞邏輯（三）4.4邏輯等值的謂詞公式4.5謂詞公式的前束范式理論：謂詞公式等值的定義，基本等值式，前束范式第十11 日至18 日一周 月12 11月第十二周11月19日 至11月25日22第十七講圖論（一）6.1圖的基本概念 6.2節(jié)點(diǎn)的度數(shù)6.3子圖，圖的運(yùn)算和圖 同構(gòu)理論：圖的定義，鄰接，關(guān)聯(lián)，簡(jiǎn)單圖，節(jié)點(diǎn)的度數(shù)，子圖第十三周11月26

11、日 至12月2 日44第十八講圖論（二）6.4路與回路6.5圖的連通性理論內(nèi)容：路，回路，無(wú)向圖的連通性，無(wú)向連通圖的點(diǎn)連通 度與邊連通度，有向圖的連通性第十九講圖論（三）6.6圖的矩陣表示 6.7賦權(quán)圖及最短路徑 理論內(nèi)容：圖的鄰接矩陣，可達(dá)矩陣，關(guān)聯(lián)矩陣，賦權(quán)圖，最 短路徑第十四周12月3日 至12月9日22第二十講圖論（四）7.1歐拉圖理論內(nèi)容：歐拉圖的有關(guān)概念，歐拉定理，中國(guó)郵遞員問(wèn)題、Hamilt on 圖第十五周 12月8日 至12月16日44第二十一講圖論（五）7.2無(wú)向樹(shù) 7.3有向樹(shù)理論內(nèi)容：樹(shù)的基本概念，最小生成樹(shù)，二叉樹(shù)的遍歷與表 達(dá)式的計(jì)算第二十二講代數(shù)結(jié)構(gòu)（一）5.1

12、代數(shù)結(jié)構(gòu)簡(jiǎn)介理論內(nèi)容：代數(shù)結(jié)構(gòu)的定義，半群及獨(dú)異點(diǎn)，子代數(shù)，代數(shù)結(jié) 構(gòu)的同態(tài)與同構(gòu)第十六周12月17日 至12月23日22第二十三講代數(shù)結(jié)構(gòu)（二） 5.2群的定義及性質(zhì)理論內(nèi)容：群的有關(guān)概念，子群，群的冋態(tài)第十七周12月24日 至12月30日22第二十四講 總復(fù)習(xí)說(shuō)明： 1本教學(xué)進(jìn)度表由主講教師負(fù)責(zé)填寫(xiě)， 于每學(xué)期開(kāi)學(xué)第一周內(nèi)送交教師所在系， 經(jīng)領(lǐng)導(dǎo)審定、 簽字后備查2此表一式三份，其中，任課教師一份，教師所在系一份，教務(wù)處一份。第一講：集合、映射和運(yùn)算（一）一、教學(xué)目標(biāo)掌握集合的概念與表示理解子集、冪集、 n 元組與笛卡兒積的概念掌握子集，冪集，笛卡爾積的求法二、重點(diǎn)與難點(diǎn)分析重點(diǎn)：集合的概

13、念，子集，冪集，笛卡爾積的概念及求法難點(diǎn)：冪集三、教學(xué)內(nèi)容與教學(xué)過(guò)程進(jìn)行自我介紹（ 5 分鐘） 姓名，聯(lián)系方式，專(zhuān)業(yè)方向。建議學(xué)生用電子郵件方式聯(lián)系。進(jìn)行課程簡(jiǎn)介（ 10 分鐘） 離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及相互之間關(guān)系的學(xué)科 是一門(mén)專(zhuān)業(yè)基礎(chǔ)課，是數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計(jì)算機(jī)組成原理、數(shù)據(jù)庫(kù)原理 等課程的數(shù)學(xué)基礎(chǔ)。特點(diǎn)：知識(shí)點(diǎn)集中，概念，定理多；方法性強(qiáng)；學(xué)數(shù)學(xué)就要做數(shù)學(xué) 成績(jī)?cè)u(píng)定：平時(shí)成績(jī) （ 到課情況，書(shū)面作業(yè)，平時(shí)測(cè)驗(yàn) ）占 30%,期末考試占 70%進(jìn)入主題，開(kāi)始第一講（1）集合的有關(guān)概念 （20 分鐘 ）集合 定義：集合是具有某種特定性質(zhì)的對(duì)象匯集成的一個(gè)整體，通常用大寫(xiě)字 母 A,B

14、,C,D 表示。例如：滁州學(xué)院全體學(xué)生 計(jì)算機(jī)與信息工程學(xué)院所有女生 常見(jiàn)的數(shù)的集合： N,N+,Z,Q,R,C元素集合中的每一個(gè)對(duì)象稱(chēng)為該集合的元素，通常用小寫(xiě)字母a,b,c,d,x,等表示例如：滁州學(xué)院的每個(gè)學(xué)生計(jì)算機(jī)與信息工程學(xué)院的每個(gè)女生N: 0、1、2、3 集合的表示方法列舉法：Z=,-2,-1,0,1,2,描述法：x|x是自然數(shù)且x小于10 遞歸法文氏圖： 特殊集合：全集U,空集._ 元素與集合x(chóng) A 或 X A|A|表示集合A中的元素個(gè)數(shù)注意：集合中的元素可以是集合，如A=a,a,b,b,c,|A|=4,a,b A注：集合中的元素?zé)o順序；集合中無(wú)重復(fù)元素例：指出下列哪些是集合，哪

15、些不是集合？中國(guó)人的集合；百貨商店里好看的花布的集合；1000以?xún)?nèi)的素?cái)?shù)的集合；26個(gè)英文字母組成的集合；這個(gè)班里高個(gè)子學(xué)生的集合；直線y= 2x-5上的點(diǎn)的集合。（2）集合之間的關(guān)系子集（15分鐘）定義：若A中的任意元素都屬于B,則A是B的子集，稱(chēng)A包含于B或B包 含A, AGB ,包括的兩層含義：包含與真包含（ 心B）, Au B , A是B的真子集注意：屬于（元素與集合的關(guān)系）與包含于（集合與集合的關(guān)系）的區(qū)別例：A=1,2,3,4 , B=2,4B工A或A = B定理1-1 ：、 A定理1-2 : （1）A5 A;（自反性）（2）A - B, B - A,則 A=B（3）A B,B C

16、,則 A C （傳遞性）用定義進(jìn)行證明定理1-3 : A=B的充要條件是A B,B A注：該定理是證明兩個(gè)集合相等的基本方法 該定理與定理1-2中的（2）的區(qū)別例1-2注：A中有一個(gè)元素不屬于C,則A二C ,反證法是一種很好的方法 幕集(15分鐘)定義：由X的所有子集組成的集合，P(X)二A|A X例：x=1,2P(X) =._ ,1,2, 1,2，Y=a,b,cP(X)珂、,a, b, c, a, b, a,c, b,c, a,b,c例1-3注：若|X|=n,P(x)的元素有：-；由一個(gè)元素構(gòu)成的子集；由兩個(gè)元素構(gòu) 成的子集；由n個(gè)元素構(gòu)成的子集計(jì)數(shù)的基本原理： 加法原理：圖示乘法原理：圖示

17、定理 1-4：若 |X|=n,|P(X)|=2n證明：n加法原理：二項(xiàng)式定理：(x y)n = 7 C；xryn 1 C1 C2 . C： C性(1 1)n =2n乘法原理：a2 2 . 2 = 2n.注：每個(gè)元素的參與與否構(gòu)成不同的子集n元組(5分鐘)定義：論域U中選取的n個(gè)元素按照一定的順序排列，得到 n元有序組，稱(chēng) n 元組，記為：(x1,x2,x3,xn)或例：平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)是2元組；空間直角坐標(biāo)系中點(diǎn)的坐標(biāo)是3元組；n元組在數(shù)據(jù)結(jié)構(gòu)中是一個(gè)表有序?qū)?，序偶?元組注：(x,y)工(y,x)笛卡爾積(10分鐘)定義：設(shè)A1，A2，.A.是集合，稱(chēng)(x1,x2，xn)|xAii

18、=1,2,n為A1,A2,An的笛卡爾積(直積，叉積)，記為：A1 A2，An例：A=a,b,B=1,2，例1-4注：A 一 - 一 A =：一一般來(lái)說(shuō)，A B = B A定理 1-5：若 |A|=m,|B|=n,則 |A B|=mX n教學(xué)小結(jié)(5分鐘)本講首先介紹了集合的概念與表示方法，接著介紹了集合之間的關(guān)系一一子集與冪集， n 元組，笛卡爾積的概念及相關(guān)定理四、作業(yè)與實(shí)驗(yàn)（ 5 分鐘）書(shū)面作業(yè)：習(xí)題 1.1 1 、 2、 3、 7、 10上機(jī)作業(yè)：無(wú)第二講：集合、映射和運(yùn)算（二）一、教學(xué)目標(biāo)掌握映射的概念與表示理解映射的三種性質(zhì)：?jiǎn)紊洹M(mǎn)射、雙射，會(huì)判斷某個(gè)具體映射是否具有 這些性質(zhì)掌

19、握逆映射的含義，復(fù)合映射的定義及性質(zhì)二、重點(diǎn)與難點(diǎn)分析重點(diǎn)：理解和判斷映射的三種性質(zhì)，逆映射，復(fù)合映射難點(diǎn)：映射三種性質(zhì)的判斷，復(fù)合映射的性質(zhì)三、教學(xué)內(nèi)容與教學(xué)過(guò)程習(xí)題講解（10分鐘）2上講內(nèi)容回顧（3分鐘）集合的概念：集合、元素、集合的表示方法集合間的關(guān)系：子集、幕集、n元組、笛卡爾積（1）映射的定義（15分鐘）定義：對(duì)于A,B,若存在對(duì)應(yīng)法則f,對(duì)于A，唯一的r B與它對(duì)應(yīng), 稱(chēng)f是A到B的一個(gè)映射或一個(gè)函數(shù)。記為：f:A f B （圖示）例: Ceiling functionf ： g = g Q fFloor functionx取整函數(shù)xl定義域：自變量x的取值范圍domf值域：函數(shù)值

20、y的取值范圍ranf像：f （X）二f （x）X X為x在映射f下的像1 _原像：f （X）二x| f（x）丫為丫在映射f下的原像注：全函數(shù)即domf =A y= f（x）為x在映射f下的像AB =f I f :A B : A到B的所有映射組成的集合定理 1-6 : |A|=m,|B|=n,貝U BA = nm （證明）映射的性質(zhì)單射（一對(duì)一映射）（10分鐘）定義：-x1,x2 A，f（x1） = f（x2）可推出 x仁 x2或一x1,x2 A，若 x1 工x2，可得出 f（x1）=f（x2）例1-6 :設(shè)f :N N, f （x2x,則f是N到N的單射，試證明之。 證：對(duì)于_x1，x N，由

21、f（x1）=f（x2）得出2昭=厶2，進(jìn)而x仁x2（使用定義證明）滿(mǎn)射（10分鐘）定義：對(duì)于y B，A，使得y=f（x）充要條件：ranf =B例1-7 :設(shè)f :Zt N, f (x) =|x，則f是Z到N的滿(mǎn)射，試證明之。 證：對(duì)于- y三N,取x = y三Z，顯然有y = f (x)(使用定義證明)雙射(一一對(duì)應(yīng))(5分鐘)定義:既單射又滿(mǎn)射例1-8例1-9 :建立一個(gè)(0,1 )到R的對(duì)應(yīng)解：f : (0,1) R, f(x)二 tan(x 一 1/2)二置換：A到A的雙射逆映射(逆函數(shù)，反函數(shù))(10分鐘)定義：f:A -B,將f的方向逆轉(zhuǎn)后，得到的集合 B到集合A的映射f J 定理

22、1-7 : f的逆映射存在的充要條件是f是雙射(加以說(shuō)明解釋)注：若f是雙射，則f也是雙射，且(f二f例1-11 :判斷所給出的映射是否有逆射，若有，求出其逆映射f : R R, f (x x2g : R R, f(x) =x3解： f(2)=f(-2)=4,根據(jù)單射定義知f不是單射，進(jìn)而其不是雙射，根據(jù)定理1-7知其不存在逆映射顯然g是雙射，其逆映射為g:R R,g(y) = 3y復(fù)合映射(20分鐘)定義:設(shè) f :A B,g： B C,對(duì)于一 x A，令 h(x)二 g(f(x)，則 h 是 A 到C的映射，h為f和g的復(fù)合映射或復(fù)合函數(shù)，記為f g (圖示) 注：(f ：g)(x)二 g

23、(f (x)條件：f(A)dom(g)例 1-12例 1-13注：一般來(lái)說(shuō)即使f g和g f都有意義，也不能保證f g = g f成立恒等映射(I a) : f ： A A, f (xx定理1-9 :若f ： A * B是雙射，則f0fl：f7f B若 f ： at A是雙射，則 f 0 f = f f = Ia定理 1-10 : f : A B,g： B C若f和g是單射，則f?g是單射（證明） 若f和g是滿(mǎn)射，則f?g是滿(mǎn)射（證明）若f和g是雙射，則 仁9是雙射且（f g）二gOf定理 1-11 :設(shè) f : A B,g： B C若f ?g是單射，則f是單射，但g不一定（證明）若fJg是滿(mǎn)

24、射，則g是滿(mǎn)射，而f不一定（證明）ABc定理 1-12 設(shè) f：AT B,g:BTC,h:CT D，貝(f(3g)0h=fC(g0h)教學(xué)小結(jié)（5分鐘）本講首先介紹了映射（函數(shù)）的定義及定義域、值域、像、原像等相關(guān)概念; 接著介紹了映射的三種性質(zhì)：?jiǎn)紊洌瑵M(mǎn)射，雙射；最后介紹了逆映射的定義及復(fù) 合映射的定義及其具有的相關(guān)性質(zhì)。四、作業(yè)與實(shí)驗(yàn)（2分鐘）書(shū)面作業(yè)：習(xí)題1.2 1、2、6、11、14.上機(jī)作業(yè)：無(wú)第三講：集合、映射和運(yùn)算（三）一、教學(xué)目標(biāo)理解運(yùn)算的定義掌握運(yùn)算的表示及常用運(yùn)算理解運(yùn)算的性質(zhì)并能判斷具體運(yùn)算是否具有某些性質(zhì)二、重點(diǎn)與難點(diǎn)分析重點(diǎn)：運(yùn)算的定義，運(yùn)算的性質(zhì)難點(diǎn)：運(yùn)算性質(zhì)的判定

25、三、教學(xué)內(nèi)容與教學(xué)過(guò)程1習(xí)題講解（5分鐘）2上講內(nèi)容回顧（5分鐘）映射的定義映射的性質(zhì)：?jiǎn)紊?，滿(mǎn)射，雙射逆映射復(fù)合映射3進(jìn)入主題，開(kāi)始第二講。本講知識(shí)點(diǎn)概括運(yùn)算的定義（25分鐘）定義：設(shè)A1，A2，.，An和B是集合，若f:A1 A2 . AnB，稱(chēng)f為 A1，A2,., An 到 b 的 n 元運(yùn)算。nA至U B的n元運(yùn)算，或 A上的n元運(yùn)算:a匯A.At bA上的n元封閉運(yùn)算（代數(shù)運(yùn)算）：nf：AA 漢 At A，V x1,x2,.x n A,有 f（x1,x2,.,x n） = y A例：判定取絕對(duì)值運(yùn)算|、加法運(yùn)算+、取大運(yùn)算max是否是自然數(shù)集合N（Z） 上的代數(shù)運(yùn)算。解：-x N

26、- 斗=x N- x, y N = x y NVx1, x 2 , .x n 4 m ax （ x1, 2x,n. N例：判定減法運(yùn)算-,取小運(yùn)算min是否是自然數(shù)集合N上的代數(shù)運(yùn)算。解：例：判斷數(shù)的加法運(yùn)算是否是集合 A=2n |n N上的代數(shù)運(yùn)算？解：21 - 22 =6Jn例：將十進(jìn)制數(shù)273轉(zhuǎn)換成八進(jìn)制解：273=34 8 1,34 =4 8 2 ,=2 73= 3 4 8 1 （4 8）2） 81= 48+2 工8 +1273 =(421)8模運(yùn)算定義. f : Z t N, f (x) = x(mod m) x(mod m)是使 x = qm+r,0 蘭 r cm 成立 的整數(shù)r,

27、即x除以m的余數(shù)。例：16(mod 3)、-8(mod 5)、9(mod 2)模m加法，模m乘法x my 彳 x y( m o dm )x *m y =( x * y( m o dm )例：m=5, 3 5(-5) =3,3 5(-5) =0最大公約數(shù)，最小公倍數(shù)_m, 乙若d|m且d|n,貝U d是m,n的公約數(shù)，用gcd(m,n)表示m,n的最 大公約數(shù)_m, 乙若m|d且n|d，則d是m,n的公倍數(shù)，用lcm(m,n)表示m,n的最 小公倍數(shù)。注：Gcd與lcm分別記為,和(，) gcd(m , n)= gcd(|m|n|)且 lcm(m, n)=lcm(|m|, |n|) 素因數(shù)分解：

28、(對(duì)于大于1的正整數(shù)n都可以分解成一些素?cái)?shù)乘積) r1 r2rk一 出s, s2s _ -Hm = p/p；P/ Z ,n 二 p；P22piZ(Pk為素?cái)?shù)，rk, sk為非負(fù)整數(shù)) gcd(m,n) = p,min( )p；in( r2，s2)pJn(rk，Sk) lcm(m,n)二卩罟心卩異心2).Euclid算法m 二q,nr,0:r,： n, n二 q?*咕0：r?：r,：n，r“ 二 qkiR一1 二qkrk = gcd(m, n) = mx ny例 1-19若 gcd(m,n)=1,稱(chēng) m 和n互素。歐拉函數(shù)：(n)：表示小于等于n且與n互素的正整數(shù)的個(gè)數(shù)運(yùn)算表給定集合A，則集合A

29、上的1元或2元運(yùn)算可以用運(yùn)算表來(lái)表示 例：A=a,b,c,*abcabcababccbca思考：A上的封閉的1元，2元，3元運(yùn)算的個(gè)數(shù)是多少?33 39327運(yùn)算的性質(zhì)對(duì)合性（5分鐘）定義：設(shè)*是A上的一元代數(shù)運(yùn)算，“（“x）=x,A.例：-x R: _（-x） = x（A）二二 A,（AT）T = AI x| = x ？幕等性（5分鐘）幕等元：x* x = x,x A定義：A中的每個(gè)元素對(duì)于*都是幕等元例：*123112322323313例：R, *?交換性（5分鐘）定義：對(duì)于A上的二元運(yùn)算*, -x, y A,均有x” y = y ” X, 例：R上的+具有交換性R上的-，映射的復(fù)合運(yùn)算f

30、jg?結(jié)合性（5分鐘）定義：-x, y, z A: （x y） z = x （y z）.例:映射的復(fù)合運(yùn)算（f g）Qh二f （g h）具有結(jié)合性R上的+具有結(jié)合性R上的-?單位元素（幺元素）（5分鐘）定義：對(duì)于A上的二元運(yùn)算*， e，使得對(duì)于-xx e 二 x.e x 二 x.例：R關(guān)于加法運(yùn)算+的單位元素是0R關(guān)于乘法運(yùn)算的勺單位元素是1R關(guān)于減法運(yùn)算-的單位元素是？定理1-3：若A關(guān)于*有單位元素，則單位元素是唯一的 證明：設(shè)e1,e2是A關(guān)于*的單位元素，則e仁e1*e2=e2零元素（5分鐘）定義：對(duì)于A上的二元運(yùn)算*，二，使得對(duì)于x日*x=T x*日=0例:R關(guān)于乘法運(yùn)算的零兀素是0

31、R關(guān)于減法運(yùn)算-的零兀素是？R關(guān)于加法運(yùn)算的零兀素是？定理1-4:若A關(guān)于*有零元素，則零元素是唯一的證明：設(shè)e1,e2是A關(guān)于*的零元素，貝U e仁e1*e2=e2逆元素(5分鐘)前提：A關(guān)于二元運(yùn)算*有單位元素e定義：x A, y A，使得：x y = e. y x = e.例：R上的加法運(yùn)算+: x+(-x)=O=(-x)+x TOC o 1-5 h z 一 11R上的乘法運(yùn)算: x = 0, x1xxx注：逆元不一定存在，存在不一定唯一，參見(jiàn)表 1-5 定理1-5：若A關(guān)于*運(yùn)算有單位元素為e且*運(yùn)算滿(mǎn)足結(jié)合律，若對(duì)于 A 中的x有左逆元 y與右逆元 z,貝U y=z,此逆元唯一證明：

32、y*x=e,x*z=ey=y*e=y*(x*z)=(y*x)*z=e*z=z消去性(分鐘)定義：若A關(guān)于*有零元，則記為v，對(duì)于-x, y, A，若x -x y = x z= y = z. y x 二 z x 二 y = z.例1-31 Z上的加法運(yùn)算+和乘法運(yùn)算均滿(mǎn)足消去律.分配性(5分鐘)定義：*,】是A上的兩個(gè)二元運(yùn)算，對(duì)于 x, y, z Ax (y z) = (x y) (x z). (y z) x = (y x) (z x). 則稱(chēng)*關(guān)于是可分配的吸收性(2分鐘)定義：*,是A上的兩個(gè)二元運(yùn)算，對(duì)于-x,y, Ax (x y)二 x. (y x) x = x.則稱(chēng)*關(guān)于是可吸收的德

33、摩根律(3分鐘)定義：是A上的一元運(yùn)算，是A上的兩個(gè)二元運(yùn)算，對(duì)于x,y,z A(x y) =(% (y).*(x y)=(嘆)(y).教學(xué)小結(jié)(3分鐘)本講首先介紹了運(yùn)算的定義并介紹了幾種常用的運(yùn)算，接著介紹了運(yùn)算的性 質(zhì)：對(duì)合性、幕等性、交換性、結(jié)合性、單位元素、零元素、逆元素、消去性、 分配性、吸收性、德摩根律，并結(jié)合之前所學(xué)知識(shí)講解運(yùn)算的性質(zhì)。四、作業(yè)與實(shí)驗(yàn)（ 2 分鐘）書(shū)面作業(yè)：習(xí)題 1.3： 1、3、5、6、8上機(jī)作業(yè)：無(wú)第四講：集合、映射和運(yùn)算（四）一、教學(xué)目標(biāo)掌握集合的各種運(yùn)算理解各種集合運(yùn)算所滿(mǎn)足的性質(zhì)掌握集合的劃分與覆蓋的概念了解集合的對(duì)等，集合的基數(shù)，可數(shù)集合等概念二、重

34、點(diǎn)與難點(diǎn)分析重點(diǎn)：集合的運(yùn)算一一并、交、補(bǔ)、差、對(duì)稱(chēng)差集合運(yùn)算性質(zhì)難點(diǎn)：集合運(yùn)算等值式的證明，集合的對(duì)等、基數(shù)三、教學(xué)內(nèi)容與教學(xué)過(guò)程1上講內(nèi)容回顧（5分鐘）運(yùn)算的定義運(yùn)算的性質(zhì)：對(duì)合性、幕等性、交換性、結(jié)合性、單位元素、零元 素、逆元素、消去性、分配性、吸收性、德摩根律2進(jìn)入主題、開(kāi)始第四講本講知識(shí)點(diǎn)概括（1）集合的運(yùn)算并運(yùn)算（15分鐘）定義：A-B=x|x A或 x B.定理1-16 : A _ B是包含A和B的最小集合WC A,C：Bn C：AuB定理1-17 :并運(yùn)算滿(mǎn)足的性質(zhì)：A _ B 二 B _ A （交換律）（A - B） - C = A - （B - C）（結(jié)合律）A. A二A

35、 （幕等律）A - 一 一 - A = A （.一是u運(yùn)算的單位元素）A-U=U-A=U （ U是U運(yùn)算的零元素）例 1-38:設(shè) f : A B, X, Y A,則證明：f（X Y）二 f（X） 一. f（Y）:X X _ Y= f(X) f (X _ Y)證明：Y X 一 丫二 f (Y) f (X 一 Y) .f(X)_.f(Y) f(X 一 丫)-b f(X 一 Y)= a (X 一 Y): b = f (a) a X 二 b 二 f(a) f (X)a Y二 b = f (a) f (Y).b f(X) 一 f(Y)f(X Y) f(Xh，f(Y)交運(yùn)算(15分鐘)定義：A B 二x

36、|x A且x BcuM c 廳=4 * E = AB定理1-18 : A、B是包含在A和B的最大集合.一 C 三 A,C - B = C - A 一 B定理1-19 :交運(yùn)算滿(mǎn)足的性質(zhì)：AA二A （幕等律）A r B二B r A （交換律）（A B） C=A （B C）（結(jié)合律）A* （、是運(yùn)算的零元素）A - U二U二A （ U是運(yùn)算的單位元素）例：定理1-20 :并運(yùn)算與交運(yùn)算之間滿(mǎn)足的性質(zhì)：A _ （A - B） =A（一.對(duì) 可吸收）A、（A_. B） 對(duì)一可吸收）A 一（B 一 C） =（A_. B廠（A_. C）（_.對(duì)-可分配）A 一（B 一 C）二（A 一 B） 一 （A 一

37、C）（-對(duì)一.可分配）例 1-41 : A - B ：= AB 二 A ：= A B 二 B 證：A 二 B ：= A B = BB A 一 Bx A - B,x A,由于 A-B= x B補(bǔ)運(yùn)算（10分鐘）定義：A 二 Cu（A）U例1-42 : （A的補(bǔ)集依賴(lài)于全集U的選?。〢=a,b,cU=a,b,c,d二 A 二dU =a,b,c,d,a,b,b,c, c二 A=d,a,b, b,c, c定理1-21 :定理1-22 :德摩根律:P25: 一廠，運(yùn)算的重要性質(zhì)差運(yùn)算（10分鐘）定義：A-B=x|x A且x- E例 1-43 :a,b,c -b,c,d,e f二a b,c,d,e, f

38、-a,b,c =d,e, f定理 1-23 : A -B 二 A B證明：x A-B= x A,x - B二 x A,x B = x AB 例 1-45 :證明：（A -B） -C =A-（B C）例 1-46 :A B 二 A - B 二一例 1-47 :（A -B） _ （A -C） =（AB） _ （AC）=A（B 一 C） =ABC =A -（BC）A ；= B C（A _B） -C =（AB） -C =（AB廠 C證：=A 一 （BC） =A-（B - C）對(duì)稱(chēng)差運(yùn)算（10分鐘）定義：A _ B =（A_B） 一（B A）A B =例a,b,c - b,c,d,e, f =a,d,e

39、, fA_ BB i A（交換律）定理1-24 :=0徑A=A（0是的單位元素）（A輕B）C=A （ B過(guò)C）（結(jié)合律）A : A= .容斥原理形式：| Au B | =| A| + |B | -1 AC B |. 或：AcB =|U A B +|AcB例：求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整 除數(shù)有多少個(gè)？解：|S| = 1000|A|=I11000/5 =200, |B|= H.1000/6 =166|A B| = Il1000/lcm（5,6）= I11000/33 = 33Ac B =1000 -200 -166 +33 =667集合的劃分與覆蓋(12分鐘)劃分定

40、義：兀=A | A匸A,i乏1A，一 i I其中：AAj一，一jA = Ai日例1-53 :設(shè)A = a, b, c, 則A的所有不同的劃分分別為：1 二a,b,c,二 a,b, c,3 二a,c, b, ：；4 b, c, a,二5 - a,b,c.覆蓋設(shè)A是集合，由A的若干非空子集構(gòu)成的集合稱(chēng)為A的覆蓋,如果這些非空子集的并等于A.（3）集合的對(duì)等（10分鐘）定義：AB =存在雙射f : AB.例：（0, 1）R集合的基數(shù)|A :無(wú)限集合A若集合A和B對(duì)等,則稱(chēng)這兩個(gè)集合的基數(shù)相同.例：|（0,1）可數(shù)集合：能與自然數(shù)集合 N對(duì)等的集合教學(xué)小結(jié)（2分鐘）本講首先介紹了集合的各種運(yùn)算（并，交

41、，補(bǔ)，差，對(duì)稱(chēng)差）及其滿(mǎn)足的性 質(zhì)，接著介紹了集合的劃分與覆蓋的概念；最后介紹了集合對(duì)等、集合的基數(shù)及 可數(shù)集合。四、作業(yè)與實(shí)驗(yàn)（1分鐘）書(shū)面作業(yè)： 習(xí)題1.4 5、8、10、13.習(xí)題 1.5: 1、7上機(jī)作業(yè)：無(wú)第五講：關(guān)系（一）一、教學(xué)目標(biāo)掌握關(guān)系的概念尤其是二元關(guān)系的概念掌握關(guān)系的定義域和值域掌握關(guān)系的三種表示方法理解函數(shù)的關(guān)系定義二、重點(diǎn)與難點(diǎn)分析重點(diǎn)：二元關(guān)系概念、關(guān)系的三種表示方式、函數(shù)的關(guān)系定義難點(diǎn)：關(guān)系的概念三、教學(xué)內(nèi)容與教學(xué)過(guò)程1習(xí)題講解（15分鐘）2上章內(nèi)容回顧（5分鐘）集合的有關(guān)概念映射的有關(guān)概念運(yùn)算的定義與性質(zhì)集合的運(yùn)算、集合的劃分與覆蓋、集合的對(duì)等進(jìn)入主題，開(kāi)始第五

42、講本講知識(shí)點(diǎn)介紹（1）關(guān)系的定義關(guān)系的概念（15分鐘）引例：A = 張三,李四,王五；B = 英語(yǔ),C語(yǔ)言,離散數(shù)學(xué),數(shù)據(jù)結(jié)構(gòu),匯編語(yǔ)言；C = 優(yōu),良,合格,不合格.A與B之間的關(guān)系R = （張三,離散數(shù)學(xué)）,（張三,數(shù)據(jù)結(jié)構(gòu)）,（張 三，英語(yǔ)）,（李四，數(shù)據(jù)結(jié)構(gòu)）,（王五，C語(yǔ)言）,（王五，匯編語(yǔ)言）A B.A, B與C之間的關(guān)系S = （張三,離散數(shù)學(xué),優(yōu)）,（張三,數(shù)據(jù)結(jié) 構(gòu)，良），（張三，英語(yǔ)，優(yōu)）,（李四，數(shù)據(jù)結(jié)構(gòu)，優(yōu)）,（王五，C語(yǔ) 言,合格）,（王五,匯編語(yǔ)言,良） ABC.定義：A,A2,.An是集合，jR A匯人2乞腫代，貝U R為A,A2,.An間的n元關(guān)系特別的R A

43、A . A為A上的n元關(guān)系注（兩層含義）：集合、關(guān)系例：A=王，李，張，黃 , B=100米，400米，鉛球，跳遠(yuǎn) , C=第 一名，第二名，第三名，優(yōu)秀獎(jiǎng)R=(王，100米，第二名)，(李，鉛球，優(yōu)秀獎(jiǎng))，(張，100米，第 一名)，(黃，跳遠(yuǎn)，第二名)二元關(guān)系的定義：兩個(gè)集合 A和B (可以相同)之間的關(guān)系稱(chēng)為二元關(guān)系A(chǔ) 到B的關(guān)系：R A BA 上的關(guān)系：R A A例：A=甲，乙，丙R=(乙，甲)，(乙，丙)，(甲，丙)注：(x,y)表示x勝y例：A=張三，李四，王五，B=教師，輔導(dǎo)員，導(dǎo)師R=(張三，輔導(dǎo)員)，(張三，教師)，(李四，教師)，(王五，導(dǎo)師)，(王五，教師)例 2-1 :

44、A 二a,b, B 二1,2,3R =( a,3),( a,2),( b,1),(b,3) A B =( a,1),(a,2),( a,3),( b,1),(b,2),( b,3)例：A=a,b,R 是 P(A)上的包含關(guān)系，R=(x,y)|x,y P(A)且 xyP(A)=f - ,a, b, AR 二(、，、),(_, a),(、， b),( - , A),( a, a),( a, A),( b, b),( b, A),(代 A) 注意：關(guān)系的次序定理2-1 :若=m, B=n，則A到B的關(guān)系有2mn若|A|=m，則A上的關(guān)系有2mm注：A到B的關(guān)系是AX B的子集三種特殊的關(guān)系(5分鐘)

45、空關(guān)系：A到B的空關(guān)系、A 上的空關(guān)系-全關(guān)系：A到B的全關(guān)系A(chǔ) BA 上的全關(guān)系A(chǔ) A恒等關(guān)系：Ia 二(x,x)|x a例：A=0,1,2A a=(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)I a=(0,0),(1,1),(2,2)關(guān)系符號(hào)(10分鐘)定義：若(x,y)R,則可記為xRy例：實(shí)數(shù)集合R上的大于“ ”關(guān)系：x(x, y)|x, R,x y.例：整數(shù)集Z上的整除關(guān)系“ I”m |n 二 n = mq ,卜( x, y) | x, y 己 Z , x| y(2,6),( -2,6),(2, -6),( -2, -6)

46、|(1)若 x|y且 y|x,則x =y 或 x = y整除性質(zhì)：(2)若x | y且y |乙則x|z(3)若x | y且x | 乙則x |my nz例：模m同余關(guān)系三mx=m y = m (x-y)3(x-y)u x除以3的余數(shù)=y除以3的余數(shù) 性質(zhì)：(1)x 三 x(mod m).I ix 三 y(mod m)= y 三 x(mod m)x 三 y(modm), y三 z(modm)二x 三 z(mod m)a 三 b(modm), c三 d(modm)=ax cy 三 bxdy(mod m)a= b(modm), c三 d(modm)二ac 三 bd (modm)a 三 b(modm)=

47、an 三 bn(mod m)a 三 b(mod m)二 f (a)三 f (b)(mod m)關(guān)系的定義域和值域(5分鐘)定義域：設(shè)R - A B,domR=x|存在y B,使(x, y) R .即 R中所有有序?qū)χ?第一位置元素組成的集合，它顯然是A的子集值域：設(shè) RA B, ran R = y| y B,存在 x A,使得(x, y)F,即 R中所有有序?qū)χ械诙恢迷亟M成的集合，它是B的子集.例2-10 : R= (1,1), (1,3), (2, 2), (2, 4), (3,1), (3, 3), (4, 2), (4, 4), 則 dom R= 1,2, 3, 4，ran R =

48、1,2, 3, 4.關(guān)系的表示(20分鐘)集合表示法列舉法：把關(guān)系內(nèi)部的元素全部列舉出來(lái)描述法：把關(guān)系內(nèi)部成員的性質(zhì)描述出來(lái)(同集合)關(guān)系圖表示法情形1 R是A到B的關(guān)系A(chǔ) = a, b, c, d, B = 1,2, 3,R = ( a, 2), ( a, 3), ( c, 2), ( d, 2).情形2 R是A上的關(guān)系A(chǔ) = a, b, c, d， R =( a,b),( a, c),( c, a),(d,c),(d,d)注：有向邊關(guān)系矩陣表示法= 1,2,，m, j1A =Xi, X2,., Xm, B = yi, y2,., Ym, R A B 定義：=M R = (mj )m n例

49、2-13:A = a,b, c,d, B = 1,2, 3,R = ( a, 2), ( a, 3), ( c, 2),(d, 2).一0111 1000M R =111011010mijR,i_ 1,(xi,yj)0,(xi, yj) R= 1,2,., n例：A=a,b,c, I A =(a, a),(b,b),(c,c)01(3)函數(shù)的關(guān)系定義(5分鐘)函數(shù)到關(guān)系的轉(zhuǎn)換例：A = a, b, c, B = 1,2, 3, f: AB, f(a) = 2, f(b) = 3, f(c) =3.-f =(a,2),(b,3),(c,3)關(guān)系能夠轉(zhuǎn)換成函數(shù)的條件domf 二 A(x, yj f

50、 ,(x, y2) f 二 力二 y2例：A =x, y, z, B 鞏1,2,3,4, R =( x,1),( y,2),( z,4),( y,3)，不能轉(zhuǎn)換成函數(shù)。例 2-16教學(xué)小結(jié)(3分鐘)本講首先講解關(guān)系的概念與表示，特別介紹了二元關(guān)系，同時(shí)描述了三 種特殊的關(guān)系：空關(guān)系、全關(guān)系、恒等關(guān)系，然后講解了關(guān)系的三種表示方式：集合表示法、關(guān)系圖表示法、關(guān)系矩陣表示法，接著講解了關(guān)系與函數(shù)的區(qū)別與聯(lián)系及它們間的轉(zhuǎn)換。13、14.四、作業(yè)與實(shí)驗(yàn)( 2 分鐘)書(shū)面作業(yè)：習(xí)題 2.1： 2 、4(2)(4)(5)上機(jī)作業(yè)：無(wú)第六講：關(guān)系（二）一、教學(xué)目標(biāo)掌握關(guān)系的集合運(yùn)算掌握關(guān)系的逆運(yùn)算，逆關(guān)系的

51、關(guān)系矩陣、關(guān)系圖及逆關(guān)系的定理掌握復(fù)合關(guān)系、復(fù)合關(guān)系相關(guān)定理了解函數(shù)的復(fù)合運(yùn)算二、重點(diǎn)與難點(diǎn)分析重點(diǎn)：復(fù)合關(guān)系、逆關(guān)系的概念及相關(guān)性質(zhì)難點(diǎn)：復(fù)合關(guān)系、逆關(guān)系的性質(zhì)三、教學(xué)內(nèi)容與教學(xué)過(guò)程1習(xí)題講解（10分鐘）2上講內(nèi)容回顧（5分鐘）N元關(guān)系的定義2元關(guān)系關(guān)系的定義域與值域關(guān)系的表示函數(shù)的關(guān)系定義3進(jìn)入主題，開(kāi)始第六講。（1）關(guān)系的集合運(yùn)算（15分鐘）關(guān)系的幾種常見(jiàn)集合運(yùn)算：R,S A B:R_. S,RS,R, R-S,R二S.、宀 RQ A汽Bn R = A漢 B R 注：_R AA=R = AA R例：設(shè) A 二123,4,若R二(x,y)|(x,y)/2 是整數(shù)，x,y A,S二(x,y)

52、|(x-y)/3 是正整數(shù)，x,y A, 求 R_ S,R - S,S-R,L R,R 二 SR=(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)L 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),

53、(4,2),(4,4),(4,1)例 2-17（2）關(guān)系的逆運(yùn)算（20分鐘）為何考慮關(guān)系的逆運(yùn)算？若x是y的老師，則y是x的學(xué)生,定義：R A B= R二(y,x) |(x,y) R B A注：R1就是將所有R中的有序?qū)χ械膬蓚€(gè)元素交換次序，例 2-18 : A = a, b, c, d, B = 1,2, 3, R = ( a, 3), ( c, 2), ( a, 2), ( b, 2).則 R=(3,a),(2,c),(2, a),(2, b)逆關(guān)系的關(guān)系圖Gri有向線條反向(圖示例2-18)逆關(guān)系的關(guān)系矩陣MR1原關(guān)系的關(guān)系矩陣的轉(zhuǎn)置(示例 2-18)逆運(yùn)算的性質(zhì)：定理2-2 : (R)

54、二R (對(duì)合律)定理2-3 :逆運(yùn)算與關(guān)系的集合運(yùn)算并，交，補(bǔ)的關(guān)系(R S)二 RJS(R - S)=R八 SJ(R)證明：(R - S) 二 RJ Sd):-(u,v) (RS) 二(v,u) R S：=(v, u) R,(v,u) S：= (u,v) R，,(u,v) S二(u,v) RJ SJ.關(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 C=二(x,z)| y B,(x,y) R,( y, z) S.例：F 二(3,3),(6,2), G 二(2,3)，貝U：F OG

55、二(6,3), G!)F 二(2,3)例 2-19 : A=a,b,c,d, B =1,2,3,4, C 二：，、,S 二(1,： ),(2, J(2,、),(3), R 二(a,1),(a,2),(b,2),(d,3),(c,4),=R S 二(a,： ),(a, J(a,、),(b, J(b,、),(d, J.借助關(guān)系圖理解復(fù)合運(yùn)算：關(guān)系矩陣:_1 100 101001 00010104*4-110001000001Mr=Mr,Mj00001010100sj00001010100.0000j10101010000.01004*4復(fù)合關(guān)系的性質(zhì)(10分鐘)R ? S - S ? R.或 y

56、= x/2 =( 0,1), (1,2), (2,3), (0,0),(2,1)例：R =(x,y)|x,y A, y = x+1S =(x, y)| x,y A, x = y +2=( 2,0), (3,1)R S =(1,0),(2,1)工 S R=(2,1),(2,0),(3,2) 定理 2-4 : (R S) T = R (S T)二 R S T.證明思路：(R 廠工R S T)(R S) T 二 R (S T)定理 2-5 : R (S T) =(R S) 一(R T).R (S T) (R Sr (R T).定理 2-6 : (R S宀 S R4.證明：- (u,v) (R S)

57、= (v,u) R Sy B:(v,y) R,(y,u) Sy B:(y,v) R,(u,y) S (u,v) S4 R.注：本性質(zhì)與矩陣的有關(guān)運(yùn)算性質(zhì)類(lèi)似，請(qǐng)注意順序(AB )4 B 4 A，,(AB )T B T A T.定理 2-7 :設(shè)R5A B,則：Ia0R二 R,R0ib 二 R幕運(yùn)算(10分鐘)R= A A: R0 =Ia, R1 =R,R2 =R：R.幕的表示方式：Rn = R：IRI：;:R, n_2.Rn41 =Rn0 R試計(jì)算Rn例 2-23 :設(shè) A=a,b,c,集合 A上的關(guān)系 R=(a,b),(b,c),(c,a),R1 =R=(a,b),(b,c),(c,a),R

58、2 二(a,c),(b,a),(c,b),3R =(a,a),(b,b),(c,c) = lA=R =R3$R 二 R,RR3CR2 二 R2=R3k =lA,R3k 1 = R,R3k 2 = R2設(shè)R二A A,對(duì)于非負(fù)整數(shù)m, n,有幕運(yùn)算的性質(zhì):RmQRn =Rm;(Rm)n =Rmn;(Rm)NR-1)”；函數(shù)的復(fù)合運(yùn)算(5分鐘)設(shè)f: A B, g: B C,函數(shù)f與函數(shù)g的復(fù)合記為f:若f (x)=y 且 g(y)=乙 則(f 匂)(x) = g(f(x)=乙由于f A B, g B C,關(guān)系f與關(guān)系g的復(fù)合記為f 若(x, y) f 且(y, z) g,則(x, z) f ?g.

59、注：函數(shù)f與函數(shù)g的復(fù)合與將其看作關(guān)系時(shí)關(guān)系f與關(guān)系g的復(fù)合是 一致的教學(xué)小結(jié)(3分鐘)本講分別介紹了關(guān)系的集合運(yùn)算、逆運(yùn)算，復(fù)合運(yùn)算，并且對(duì)復(fù)合關(guān)系、逆 關(guān)系的定義、表示方式、相應(yīng)的關(guān)系矩陣進(jìn)行了講解，還介紹了它們之間滿(mǎn)足的 相關(guān)性質(zhì)，最后介紹了函數(shù)的復(fù)合運(yùn)算。四、作業(yè)與實(shí)驗(yàn)(2分鐘)書(shū)面作業(yè)：習(xí)題 2.2 1、3、6、8、12(選).上機(jī)作業(yè)：無(wú)第七講：關(guān)系(三)一、教學(xué)目標(biāo)理解關(guān)系的各種性質(zhì)掌握滿(mǎn)足各種性質(zhì)的關(guān)系的關(guān)系矩陣和關(guān)系圖理解閉包的含義掌握閉包的幾個(gè)關(guān)鍵掌握閉包的構(gòu)造二、重點(diǎn)與難點(diǎn)分析 重點(diǎn)：自反性、反自反性、對(duì)稱(chēng)性、反對(duì)稱(chēng)性、傳遞性概念的理解，閉包 的理解與構(gòu)造難點(diǎn)：同上三、教

60、學(xué)內(nèi)容與教學(xué)過(guò)程1上講內(nèi)容回顧(5分鐘)關(guān)系的集合運(yùn)算關(guān)系的逆運(yùn)算 關(guān)系的復(fù)合運(yùn)算2進(jìn)入主題，開(kāi)始第七講本講知識(shí)點(diǎn)概括關(guān)系的性質(zhì)自反性(10分鐘)定義：對(duì)于集合A上的元素a屬于A，有(a,a)屬于R,那么R就是一個(gè)自 反關(guān)系例 2-25 : 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上的小于關(guān)系 不是自反的.定理：R自反=IA R注：空關(guān)系是空集一上的自反關(guān)系關(guān)系矩陣：對(duì)角線元素都為1關(guān)系圖：結(jié)點(diǎn)含有環(huán)反自反性