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

1、滁州學(xué)院計(jì)算機(jī)與信息工程學(xué)院課程教案課程名稱： 離散數(shù)學(xué) 授課教師：授課對(duì)象：授課時(shí)間：離散數(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ù)專業(yè)本科學(xué)生（二）開課學(xué)期：第三學(xué)期（三）課程類別：專業(yè)基礎(chǔ)課（四）考核方式：考試（五）參考教材：離散數(shù)學(xué)第2版 鄧輝文 清華大學(xué)出版社 2010.主要參考書目：1邵學(xué)才,葉秀明. 離散數(shù)學(xué)m.北京電子工業(yè)出版社，2009.2邵志清,虞慧群. 離散數(shù)學(xué)m.北京電子工業(yè)出版社，2003.3屈婉玲. 離散數(shù)學(xué)習(xí)題解析m.北京

2、大學(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ī)專業(yè)的許多專業(yè)課程必不可少的先行課程。本課程的教學(xué)目的旨在通過(guò)對(duì)離散數(shù)學(xué)的教學(xué)，讓學(xué)生不但可以掌握處理如集合、代數(shù)結(jié)構(gòu)和圖等離散結(jié)構(gòu)的描述工具和方法，為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件，而且為學(xué)生今后提高專業(yè)理論水平，從事計(jì)算機(jī)行業(yè)的實(shí)際工作提供必備的抽象思維和嚴(yán)格的邏輯推理能力，為將來(lái)參與創(chuàng)新性

3、的研究和開發(fā)工作打下堅(jiān)實(shí)的基礎(chǔ)。（二）教學(xué)內(nèi)容安排教學(xué)內(nèi)容教學(xué)要求教學(xué)方法重點(diǎn)()難點(diǎn)()學(xué)時(shí)分配備注講課實(shí)驗(yàn)上機(jī)其他第一部分 數(shù)理邏輯講授15.51命題邏輯的基本概念21.1命題與聯(lián)接詞b11.2命題公式及其賦值a12命題邏輯等值演算3.52.1等值式b12.2析取范式與合取范式a12.3聯(lián)接詞的完備集c0.52.4可滿足性與消解法b13命題邏輯的推理理論2 3.1 推理的形式結(jié)構(gòu)a13.2 自然推理系統(tǒng)pb14一階邏輯基本概念24.1一階邏輯命題符號(hào)化a14.2 一階邏輯公式及解釋a15一階邏輯等值演算與推理35.1 一階邏輯等值式與置換規(guī)則a15.2 一階邏輯前束范式a15.3 一階邏輯

4、的推理理論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)系a12.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ù)c13.4 一個(gè)電話系統(tǒng)的描述實(shí)例c14集合論在計(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

5、代數(shù)系統(tǒng)的同態(tài) 與同構(gòu)b12群與環(huán)32.1 群的定義及其性質(zhì)a12.2 循環(huán)群與置換群a2第四部分 圖論講授121圖的基本概念2.51.1 圖a0.51.2 連通與回路a0.51.3 圖的連通性a0.51.4 圖的矩陣表示a0.51.5 圖的運(yùn)算a0.52歐拉圖與哈密頓圖22.1 歐拉圖a0.52.2 哈密頓圖a0.52.3 最短路問(wèn)題與貨郎擔(dān)問(wèn)題c13樹1.53.1 無(wú)向樹及其性質(zhì)a0.53.2 生成樹a0.53.3 根樹及其應(yīng)用b0.54平面圖34.1 平面圖的基本概念b0.54.2 歐拉公式b0.54.3 平面圖的判斷b14.4 平面圖的對(duì)偶圖c15 圖論在計(jì)算機(jī)中的應(yīng)用3（教學(xué)要求：a

6、熟練掌握；b掌握；c了解）三、實(shí)驗(yàn)內(nèi)容本課程無(wú)實(shí)驗(yàn)制訂人（簽字）： 審核人（簽字）： 教 學(xué) 進(jìn) 度 表 20122013學(xué)年第1學(xué)期周 數(shù) 16 周 計(jì)劃學(xué)時(shí) 48學(xué)時(shí)講 課 48 學(xué)時(shí) 課堂討論 0 學(xué)時(shí)實(shí)驗(yàn)課 0 學(xué)時(shí) 習(xí)題課 0 學(xué)時(shí) 其他環(huán)節(jié) 0 學(xué)時(shí)授課教師姓名 趙歡歡 職稱 助教 授課專業(yè) 網(wǎng)絡(luò)工程 班級(jí) 2011級(jí) 課程名稱 離散數(shù)學(xué) 教材名稱 離散數(shù)學(xué) 出版社 清華大學(xué)出版社 周次日期周學(xué)時(shí)其中教學(xué)內(nèi)容摘要（章節(jié)名稱、講述的內(nèi)容提要、實(shí)驗(yàn)的名稱、課堂討論的題目等）講課實(shí)驗(yàn)課習(xí)題課課堂討論其他環(huán)節(jié)第一周9月3日至9月9日44第一講 集合、映射與運(yùn)算（一）1.1 集合的基本概念

7、理論：集合、子集、冪集、n元組、笛卡爾積第二講 集合、映射與運(yùn)算（二）1.2 映射的有關(guān)概念 理論：映射的定義、映射的性質(zhì)、逆映射、復(fù)合映射第二周9月10日至9月16日22第三講 集合、映射與運(yùn)算（三）1.3運(yùn)算的定義和性質(zhì) 理論：運(yùn)算的定義、運(yùn)算的性質(zhì)第三周9月17日至9月23日44第四講 集合、映射與運(yùn)算（四）1.4 集合的運(yùn)算 1.5 集合的劃分 1.6 集合的對(duì)等理論：集合的并、交、差、補(bǔ)、對(duì)稱差等基本運(yùn)算，集合的劃分與覆蓋、集合對(duì)等、可數(shù)集合、不可數(shù)集合第五講 關(guān)系（一）2.1 關(guān)系的概念理論：n元關(guān)系的定義、2元關(guān)系、關(guān)系的定義域和值域、關(guān)系的表示、函數(shù)的關(guān)系定義第四周9月24日至

8、9月30日22第六講 關(guān)系（二）2.1 關(guān)系的運(yùn)算 理論：關(guān)系的集合運(yùn)算、逆運(yùn)算、復(fù)合運(yùn)算、關(guān)系的其他運(yùn)算第五周10月1日至10月7日 4 4國(guó)慶放假第七講 關(guān)系（三）2.3 關(guān)系的性質(zhì) 2.4 關(guān)系的閉包理論：關(guān)系的性質(zhì)：自反性、反自反性、對(duì)稱性、反對(duì)稱性、傳遞性；自反閉包r(r)、對(duì)稱閉包s(r)、傳遞閉包t(r)第六周10月8日至10月14日22第八講 關(guān)系（四）2.5 等價(jià)關(guān)系 2.6相容關(guān)系 2.7偏序關(guān)系理論：等價(jià)關(guān)系的定義、等價(jià)類；相容關(guān)系的定義；偏序關(guān)系的定義、哈斯圖的、偏序集中的特殊元素第七周10月15日至10月21日44第九講 命題邏輯（一）3.1 命題的有關(guān)概念 3.2

9、邏輯聯(lián)接詞理論：命題的定義與真值、原子命題和復(fù)合命題、各種邏輯連接詞的含義，真假的判斷第十講 命題邏輯（二）3.3 命題公式及其真值表理論：命題公式的定義、命題的符號(hào)化、命題公式的真值表、命題公式的類型第八周10月22日至10月28日22第十一講 命題邏輯（三）3.4 邏輯等值的命題公式理論：邏輯等值的定義、基本等值式、等值演算法、對(duì)偶原理第九周10月29日至11月4日 44第十二講 命題邏輯（四）3.5 命題公式的范式理論：命題公式的析取范式和合取范式的定義域求法命題公式的主析取范式及主合取范式的定義和求法第十三講 命題邏輯（五）3.7 命題邏輯中的推理理論：推理形式有效性的定義；基本推理規(guī)

10、則；命題邏輯的自然推理系統(tǒng)第十周11月5日至11月11日22第十四講 謂詞邏輯（一）4.1 個(gè)體、謂詞、量詞和函詞理論：謂詞邏輯概念，謂詞的概念與表示，量詞的概念與表示，個(gè)體域，轄域，約束變?cè)妥杂勺冊(cè)暮x第十一周 11月12日至11月18日44第十五講 謂詞邏輯（二）4.2謂詞公式及命題的符號(hào)化 4.3 謂詞公式的解釋及類型理論：謂詞公式的定義，將命題用用符號(hào)（個(gè)體，量詞，謂詞）來(lái)表示，消去量詞的邏輯等值式，永真式，科滿足式，永假式及中性式的概念第十六講 謂詞邏輯（三）4.4邏輯等值的謂詞公式 4.5謂詞公式的前束范式 理論：謂詞公式等值的定義，基本等值式，前束范式第十二周11月19日至1

11、1月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日至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)題、hamilton 圖第十

12、五周12月8日至12月16日44第二十一講 圖論（五）7.2 無(wú)向樹 7.3 有向樹理論內(nèi)容：樹的基本概念，最小生成樹，二叉樹的遍歷與表達(dá)式的計(jì)算第二十二講 代數(shù)結(jié)構(gòu)（一）5.1 代數(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í)系主任簽名： 院長(zhǎng)簽名： 年 月 日 年 月 日說(shuō)明：1本教學(xué)進(jìn)度表由主講教師負(fù)責(zé)填寫，于每學(xué)期開學(xué)第一周內(nèi)送交教師所在系，經(jīng)領(lǐng)導(dǎo)審定、簽字后備查。2此表一式三

13、份，其中，任課教師一份，教師所在系一份，教務(wù)處一份。第一講：集合、映射和運(yùn)算（一）一、教學(xué)目標(biāo)1. 掌握集合的概念與表示2. 理解子集、冪集、 n元組與笛卡兒積的概念3.掌握子集，冪集，笛卡爾積的求法 二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：集合的概念，子集，冪集，笛卡爾積的概念及求法2.難點(diǎn)：冪集三、 教學(xué)內(nèi)容與教學(xué)過(guò)程1.進(jìn)行自我介紹（5分鐘）姓名，聯(lián)系方式，專業(yè)方向。建議學(xué)生用電子郵件方式聯(lián)系。2.進(jìn)行課程簡(jiǎn)介（10分鐘） 離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及相互之間關(guān)系的學(xué)科 是一門專業(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é)

14、數(shù)學(xué)就要做數(shù)學(xué) 成績(jī)?cè)u(píng)定：平時(shí)成績(jī)(到課情況，書面作業(yè)，平時(shí)測(cè)驗(yàn))占30%,期末考試占70%3.進(jìn)入主題，開始第一講(1) 集合的有關(guān)概念(20分鐘)集合 定義：集合是具有某種特定性質(zhì)的對(duì)象匯集成的一個(gè)整體，通常用大寫字母a,b,c,d表示。例如：滁州學(xué)院全體學(xué)生 計(jì)算機(jī)與信息工程學(xué)院所有女生 常見的數(shù)的集合：n,n+,z,q,r,c元素集合中的每一個(gè)對(duì)象稱為該集合的元素，通常用小寫字母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 遞歸法文氏圖：

15、特殊集合：全集u,空集元素與集合 xa或 |a|表示集合a中的元素個(gè)數(shù) 注意：集合中的元素可以是集合，如a=a,a,b,b,c,|a|=4,a,ba注：集合中的元素?zé)o順序；集合中無(wú)重復(fù)元素例：指出下列哪些是集合，哪些不是集合？ 中國(guó)人的集合； 百貨商店里好看的花布的集合； 1000以內(nèi)的素?cái)?shù)的集合； 26個(gè)英文字母組成的集合； 這個(gè)班里高個(gè)子學(xué)生的集合； 直線y2x-5上的點(diǎn)的集合。(2)集合之間的關(guān)系子集（15分鐘）定義：若a中的任意元素都屬于b，則a是b的子集，稱a包含于b或b包含a，包括的兩層含義：包含與真包含（ab），a是b的真子集注意：屬于（元素與集合的關(guān)系）與包含于（集合與集合的關(guān)

16、系）的區(qū)別例：a=1,2,3,4，b=2,4 或定理1-1：a定理1-2：（自反性）則a=b則（傳遞性） 用定義進(jìn)行證明定理1-3：a=b的充要條件是注：該定理是證明兩個(gè)集合相等的基本方法 該定理與定理1-2中的(2)的區(qū)別 例1-2注：a中有一個(gè)元素不屬于c，則，反證法是一種很好的方法冪集（15分鐘）定義：由x的所有子集組成的集合， 例：x=1,2 ，y=a,b,c 例1-3 注：若|x|=n,p(x)的元素有：；由一個(gè)元素構(gòu)成的子集；由兩個(gè)元素構(gòu)成的子集；由n個(gè)元素構(gòu)成的子集計(jì)數(shù)的基本原理：加法原理：圖示乘法原理：圖示定理1-4：若|x|=n,|p(x)|=2n證明：加法原理：二項(xiàng)式定理：

17、 乘法原理：注：每個(gè)元素的參與與否構(gòu)成不同的子集n元組（5分鐘） 定義：論域u中選取的n個(gè)元素按照一定的順序排列，得到n元有序組，稱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,an的笛卡爾積（直積，叉積），記為：例：a=a,b,b=1,2，例1-4注： 一般來(lái)說(shuō)，定理1-5：若|a|=m,|b|=n,則|=mn4. 教學(xué)小結(jié)（5分鐘）本講首先介紹了集合的概念與表示方法，接著介紹了集合之間的關(guān)系子集

18、與冪集，n元組，笛卡爾積的概念及相關(guān)定理。 四、 作業(yè)與實(shí)驗(yàn)（5分鐘）1. 書面作業(yè)：習(xí)題1.1 1、2、3、7、102. 上機(jī)作業(yè)：無(wú)第二講：集合、映射和運(yùn)算（二）一、教學(xué)目標(biāo)1. 掌握映射的概念與表示2. 理解映射的三種性質(zhì)：?jiǎn)紊?、滿射、雙射，會(huì)判斷某個(gè)具體映射是否具有這些性質(zhì)3.掌握逆映射的含義，復(fù)合映射的定義及性質(zhì)二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：理解和判斷映射的三種性質(zhì)，逆映射，復(fù)合映射2.難點(diǎn)：映射三種性質(zhì)的判斷，復(fù)合映射的性質(zhì)三、教學(xué)內(nèi)容與教學(xué)過(guò)程1.習(xí)題講解（10分鐘）2.上講內(nèi)容回顧（3分鐘） 集合的概念：集合、元素、集合的表示方法集合間的關(guān)系：子集、冪集、n元組、笛卡爾積(1)映

19、射的定義（15分鐘） 定義：對(duì)于a,b,若存在對(duì)應(yīng)法則f，對(duì)于，唯一的與它對(duì)應(yīng)，稱f是a到b的一個(gè)映射或一個(gè)函數(shù)。記為：f:ab （圖示） 例：ceiling function floor function 取整函數(shù) 定義域：自變量x的取值范圍 值域：函數(shù)值y的取值范圍 像：為x在映射f下的像原像：為y在映射f下的原像注：全函數(shù)即=a；為x在映射f下的像：a到b的所有映射組成的集合定理1-6：|a|=m,|b|=n,則（證明）(2)映射的性質(zhì)單射(一對(duì)一映射)（10分鐘） 定義：，可推出x1=x2 或 ，若x1x2，可得出 例1-6：設(shè)則f是n到n的單射，試證明之。 證：對(duì)于，由得出，進(jìn)而x1

20、=x2 (使用定義證明)滿射（10分鐘）定義：對(duì)于，使得y=f(x) 充要條件：=b 例1-7：設(shè)，則f是z到n的滿射，試證明之。 證：對(duì)于取,顯然有 （使用定義證明）雙射（一一對(duì)應(yīng)）（5分鐘）定義:既單射又滿射例1-8例1-9：建立一個(gè)（0,1）到r的一一對(duì)應(yīng)解： 置換：a到a的雙射(3)逆映射（逆函數(shù)，反函數(shù)）（10分鐘）定義：f:ab，將f的方向逆轉(zhuǎn)后，得到的集合b到集合a的映射定理1-7：f的逆映射存在的充要條件是f是雙射（加以說(shuō)明解釋） 注：若f是雙射，則也是雙射，且 例1-11：判斷所給出的映射是否有逆射，若有，求出其逆映射 解：f(2)=f(-2)=4, 根據(jù)單射定義知f不是單射

21、，進(jìn)而其不是雙射，根據(jù)定理1-7知其不存在逆映射 顯然g是雙射，其逆映射為(4)復(fù)合映射（20分鐘） 定義:設(shè)對(duì)于，令，則h是a到c的映射，h為f和g的復(fù)合映射或復(fù)合函數(shù)，記為（圖示） 注： 條件: 例1-12 例1-13 注：一般來(lái)說(shuō)即使和都有意義，也不能保證成立 恒等映射(ia)： 定理1-9：若是雙射，則 若是雙射，則定理1-10： 若f和g是單射，則是單射（證明） 若f和g是滿射，則是滿射（證明） 若f和g是雙射，則是雙射且 定理1-11：設(shè) 若是單射，則f是單射，但g不一定（證明） 若是滿射，則g是滿射，而f不一定（證明） 定理1-12 設(shè)，則4. 教學(xué)小結(jié)（5分鐘）本講首先介紹了映

22、射（函數(shù)）的定義及定義域、值域、像、原像等相關(guān)概念；接著介紹了映射的三種性質(zhì)：?jiǎn)紊?，滿射，雙射；最后介紹了逆映射的定義及復(fù)合映射的定義及其具有的相關(guān)性質(zhì)。四、 作業(yè)與實(shí)驗(yàn)（2分鐘）1. 書面作業(yè)：習(xí)題1.2 1、2、6、11、14.2. 上機(jī)作業(yè)：無(wú)第三講：集合、映射和運(yùn)算（三）一、教學(xué)目標(biāo) 1. 理解運(yùn)算的定義2. 掌握運(yùn)算的表示及常用運(yùn)算3. 理解運(yùn)算的性質(zhì)并能判斷具體運(yùn)算是否具有某些性質(zhì)二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：運(yùn)算的定義，運(yùn)算的性質(zhì)2.難點(diǎn)：運(yùn)算性質(zhì)的判定 三、教學(xué)內(nèi)容與教學(xué)過(guò)程 1.習(xí)題講解（5分鐘）2.上講內(nèi)容回顧（5分鐘） 映射的定義 映射的性質(zhì)：?jiǎn)紊?，滿射，雙射 逆映射 復(fù)合

23、映射3.進(jìn)入主題，開始第二講。本講知識(shí)點(diǎn)概括(1)運(yùn)算的定義（25分鐘） 定義:設(shè)和b是集合，若，稱f為到b的n元運(yùn)算。 a到b的n元運(yùn)算，或a上的n元運(yùn)算： a上的n元封閉運(yùn)算（代數(shù)運(yùn)算）： ，有例：判定取絕對(duì)值運(yùn)算|、加法運(yùn)算+、取大運(yùn)算max是否是自然數(shù)集合n(z)上的代數(shù)運(yùn)算。解： 例：判定減法運(yùn)算-,取小運(yùn)算min是否是自然數(shù)集合n上的代數(shù)運(yùn)算。解： 例：判斷數(shù)的加法運(yùn)算是否是集合a=2n |nn上的代數(shù)運(yùn)算？解： 例：將十進(jìn)制數(shù)273轉(zhuǎn)換成八進(jìn)制解： 273=, , 模運(yùn)算定義：，是使成立的整數(shù)r,即x除以m的余數(shù)。例：16(mod 3)、-8(mod 5)、9(mod 2)模m加

24、法，模m乘法 例：m=5, 最大公約數(shù)，最小公倍數(shù)若d|m且d|n,則d是m,n的公約數(shù)，用gcd(m,n)表示m,n的最大公約數(shù)若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ù)分解：（對(duì)于大于1的正整數(shù)n都可以分解成一些素?cái)?shù)乘積） euclid算法 例1-19若gcd(m,n)=1,稱m和n互素。歐拉函數(shù)：表示小于等于n且與n互素的正整數(shù)的個(gè)數(shù)運(yùn)算表給定集合a，則集合a上的1元或2元運(yùn)算可以用運(yùn)算表來(lái)表示例：a=a,b

25、,c,*abcabcababccbca思考：a上的封閉的1元，2元，3元運(yùn)算的個(gè)數(shù)是多少？33 39 327 (2)運(yùn)算的性質(zhì) 對(duì)合性（5分鐘） 定義：設(shè)*是a上的一元代數(shù)運(yùn)算， 例： ？?jī)绲刃裕?分鐘） 冪等元：定義：a中的每個(gè)元素對(duì)于*都是冪等元例：*123112322323313例：交換性（5分鐘） 定義：對(duì)于a上的二元運(yùn)算*,均有 例：r上的+具有交換性 r上的-，映射的復(fù)合運(yùn)算?結(jié)合性（5分鐘） 定義： 例:映射的復(fù)合運(yùn)算具有結(jié)合性 r上的+具有結(jié)合性 r上的- ？單位元素（幺元素）（5分鐘） 定義：對(duì)于a上的二元運(yùn)算*，使得對(duì)于 例：r關(guān)于加法運(yùn)算+的單位元素是0 r關(guān)于乘法運(yùn)算的

26、單位元素是1 r關(guān)于減法運(yùn)算-的單位元素是？定理1-3：若a關(guān)于* 有單位元素，則單位元素是唯一的證明：設(shè)e1,e2是a關(guān)于*的單位元素，則e1=e1*e2=e2零元素（5分鐘） 定義：對(duì)于a上的二元運(yùn)算*，使得對(duì)于 例:r關(guān)于乘法運(yùn)算的零元素是0 r關(guān)于減法運(yùn)算-的零元素是？ r關(guān)于加法運(yùn)算的零元素是？定理1-4：若a關(guān)于* 有零元素，則零元素是唯一的證明：設(shè)e1,e2是a關(guān)于*的零元素，則e1=e1*e2=e2逆元素（5分鐘）前提：a關(guān)于二元運(yùn)算*有單位元素e定義：，使得：例：r上的加法運(yùn)算+：x+(-x)=0=(-x)+x r上的乘法運(yùn)算： 注：逆元不一定存在，存在不一定唯一，參見表1-

27、5定理1-5：若a關(guān)于*運(yùn)算有單位元素為e且*運(yùn)算滿足結(jié)合律，若對(duì)于a中的x有左逆元y與右逆元z，則y=z,此逆元唯一證明：y*x=e,x*z=e y=y*e=y*(x*z)=(y*x)*z=e*z=z消去性（分鐘） 定義：若a關(guān)于*有零元，則記為，對(duì)于，若 例1-31 z上的加法運(yùn)算+和乘法運(yùn)算均滿足消去律.分配性（5分鐘） 定義：是a上的兩個(gè)二元運(yùn)算，對(duì)于 則稱*關(guān)于是可分配的吸收性（2分鐘） 定義：是a上的兩個(gè)二元運(yùn)算，對(duì)于則稱*關(guān)于是可吸收的德摩根律（3分鐘） 定義：是a上的一元運(yùn)算，是a上的兩個(gè)二元運(yùn)算，對(duì)于4. 教學(xué)小結(jié)（3分鐘）本講首先介紹了運(yùn)算的定義并介紹了幾種常用的運(yùn)算，接著

28、介紹了運(yùn)算的性質(zhì)：對(duì)合性、冪等性、交換性、結(jié)合性、單位元素、零元素、逆元素、消去性、分配性、吸收性、德摩根律，并結(jié)合之前所學(xué)知識(shí)講解運(yùn)算的性質(zhì)。 四、 作業(yè)與實(shí)驗(yàn)（2分鐘）1. 書面作業(yè)：習(xí)題1.3：1、3、5、6、8 2. 上機(jī)作業(yè)：無(wú)第四講：集合、映射和運(yùn)算（四）一、教學(xué)目標(biāo)1.掌握集合的各種運(yùn)算2.理解各種集合運(yùn)算所滿足的性質(zhì)3.掌握集合的劃分與覆蓋的概念4.了解集合的對(duì)等，集合的基數(shù)，可數(shù)集合等概念 二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：集合的運(yùn)算并、交、補(bǔ)、差、對(duì)稱差 集合運(yùn)算性質(zhì) 2.難點(diǎn)：集合運(yùn)算等值式的證明，集合的對(duì)等、基數(shù)三、 教學(xué)內(nèi)容與教學(xué)過(guò)程1.上講內(nèi)容回顧（5分鐘）運(yùn)算的定義運(yùn)算

29、的性質(zhì)：對(duì)合性、冪等性、交換性、結(jié)合性、單位元素、零元素、逆元素、消去性、分配性、吸收性、德摩根律2.進(jìn)入主題、開始第四講本講知識(shí)點(diǎn)概括(1)集合的運(yùn)算并運(yùn)算（15分鐘） 定義： 定理1-16：是包含a和b的最小集合 定理1-17：并運(yùn)算滿足的性質(zhì)： （交換律） （結(jié)合律） （冪等律）（是運(yùn)算的單位元素）（是運(yùn)算的零元素）例1-38:設(shè)f : a b, x, y a, 則證明：證明： 交運(yùn)算（15分鐘） 定義： 定理1-18：是包含在a和b的最大集合定理1-19：交運(yùn)算滿足的性質(zhì)： （冪等律） （交換律） （結(jié)合律） （是運(yùn)算的零元素）（u是運(yùn)算的單位元素） 例：定理1-20：并運(yùn)算與交運(yùn)算之

30、間滿足的性質(zhì)： 例1-41：證：補(bǔ)運(yùn)算（10分鐘） 定義：例1-42：（a的補(bǔ)集依賴于全集u的選?。゛=a,b,cu=a,b,c,d 定理1-21：定理1-22：德摩根律：p25： 差運(yùn)算（10分鐘）定義：例1-43：定理1-23：證明：例1-45：證明： 證：例1-46：例1-47： 對(duì)稱差運(yùn)算（10分鐘）定義：例定理1-24：容斥原理形式： 或： 例：求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除數(shù)有多少個(gè)？ 解： |s| = 1000 |a|=1000/5=200, |b|=1000/6=166 |ab| = 1000/lcm(5,6) = 1000/33 = 33 （2）

31、集合的劃分與覆蓋（12分鐘） 劃分定義：其中：例1-53： 設(shè)a = a, b, c, 則a的所有不同的劃分分別為: 覆蓋設(shè)a是集合, 由a的若干非空子集構(gòu)成的集合稱為a的覆蓋, 如果這些非空子集的并等于a.（3）集合的對(duì)等（10分鐘）定義：a b 存在雙射f : a b.例：(0, 1) r 集合的基數(shù)：無(wú)限集合a 若集合a和b對(duì)等, 則稱這兩個(gè)集合的基數(shù)相同.例：可數(shù)集合：能與自然數(shù)集合n對(duì)等的集合3. 教學(xué)小結(jié)（2分鐘）本講首先介紹了集合的各種運(yùn)算（并，交，補(bǔ)，差，對(duì)稱差）及其滿足的性質(zhì)，接著介紹了集合的劃分與覆蓋的概念；最后介紹了集合對(duì)等、集合的基數(shù)及可數(shù)集合。四、 作業(yè)與實(shí)驗(yàn)（1分鐘

32、）1. 書面作業(yè)： 習(xí)題1.4 5、8、10、13. 習(xí)題1.5：1、7 2. 上機(jī)作業(yè)：無(wú)第五講：關(guān)系（一）一、教學(xué)目標(biāo)1. 掌握關(guān)系的概念尤其是二元關(guān)系的概念2. 掌握關(guān)系的定義域和值域3. 掌握關(guān)系的三種表示方法4. 理解函數(shù)的關(guān)系定義二、重點(diǎn)與難點(diǎn)分析1.重點(diǎn)：二元關(guān)系概念、關(guān)系的三種表示方式、函數(shù)的關(guān)系定義2.難點(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ì)等3.進(jìn)入主題，開始第五講本講知識(shí)點(diǎn)介紹(1)關(guān)系的定義關(guān)系的概念（15分鐘）引例：a = 張三, 李四

33、, 王五;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ǔ)言, 良) a b c.定義：是集合， ，則r為間的n元關(guān)系特別的 為a上的n元關(guān)系注（兩層含義）：集合、關(guān)系例：a=王，李，張，黃，

34、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)系稱為二元關(guān)系 a到b的關(guān)系： a上的關(guān)系：例：a=甲，乙，丙 r=(乙，甲)，（乙，丙），（甲，丙） 注：(x,y)表示x勝y例：a=張三，李四，王五，b=教師，輔導(dǎo)員，導(dǎo)師 r=（張三，輔導(dǎo)員），（張三，教師），（李四，教師），（王五，導(dǎo)師），（王五，教師）例2-1： 例：a=a,b,r是p(a)上的包含關(guān)系，r=(x,y)|x,yp(a)且p(a)= 注意：關(guān)系的次序定理2

35、-1：若，則a到b的關(guān)系有 若，則a上的關(guān)系有注：a到b的關(guān)系是ab的子集三種特殊的關(guān)系（5分鐘）空關(guān)系：a到b的空關(guān)系 a上的空關(guān)系全關(guān)系：a到b的全關(guān)系 a上的全關(guān)系恒等關(guān)系： 例：a=0,1,2 =(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2) ia=(0,0),(1,1),(2,2)關(guān)系符號(hào)（10分鐘）定義：若(x,y) ,則可記為 例：實(shí)數(shù)集合r上的大于“”關(guān)系： 例：整數(shù)集z上的整除關(guān)系“|” 整除性質(zhì)：例：模m同余關(guān)系 性質(zhì)：關(guān)系的定義域和值域（5分鐘）定義域:設(shè),即r中所有有序?qū)χ械谝晃恢迷亟M成的集合, 它顯然是a的

36、子集.值域：設(shè)r ab, ran r = y|yb, 存在xa, 使得(x, y) r, 即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 = 1, 2, 3, 4. (2) 關(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 = a, b, c, d, b = 1, 2, 3, r =

37、(a, 2), (a, 3), (c, 2), (d, 2).情形2 r是a上的關(guān)系a = a, b, c, d， 注：有向邊關(guān)系矩陣表示法定義：例2-13: a = a, b, c, d, b = 1, 2, 3, r = (a, 2), (a, 3), (c, 2), (d, 2).例：a=a,b,c,(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.關(guān)系能夠轉(zhuǎn)換成函數(shù)的條件 例：，不能轉(zhuǎn)換成函數(shù)。 例2-164. 教學(xué)小結(jié)（3分鐘）本講首先講解關(guān)系的概念與表示，特

38、別介紹了二元關(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)換。四、 作業(yè)與實(shí)驗(yàn)（2分鐘）1. 書面作業(yè)：習(xí)題2.1： 2、4(2)(4)(5)、13、14.2. 上機(jī)作業(yè)：無(wú)第六講：關(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)分析1.重點(diǎn)：復(fù)合關(guān)系、逆關(guān)系的概念及相關(guān)性質(zhì)2.難點(diǎn)：復(fù)合關(guān)系、逆關(guān)系的性質(zhì)三、 教學(xué)內(nèi)容與教學(xué)過(guò)程1

39、.習(xí)題講解（10分鐘）2.上講內(nèi)容回顧（5分鐘）n元關(guān)系的定義2元關(guān)系關(guān)系的定義域與值域關(guān)系的表示函數(shù)的關(guān)系定義3.進(jìn)入主題，開始第六講。 (1)關(guān)系的集合運(yùn)算（15分鐘） 關(guān)系的幾種常見集合運(yùn)算: 注： 解：例2-17(2)關(guān)系的逆運(yùn)算（20分鐘） 為何考慮關(guān)系的逆運(yùn)算? 若x是y的老師,則y是x的學(xué)生, 定義：注：就是將所有r中的有序?qū)χ械膬蓚€(gè)元素交換次序，例2-18：a = a, b, c, d, b = 1, 2, 3, r = (a, 3), (c, 2), (a, 2), (b, 2). 則逆關(guān)系的關(guān)系圖 有向線條反向（圖示例2-18）逆關(guān)系的關(guān)系矩陣 原關(guān)系的關(guān)系矩陣的轉(zhuǎn)置（示例

40、2-18） 逆運(yùn)算的性質(zhì)：定理2-2：（對(duì)合律）定理2-3：逆運(yùn)算與關(guān)系的集合運(yùn)算并, 交, 補(bǔ)的關(guān)系 證明：（）：(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分鐘）例：，則：例2-19：借助關(guān)系圖理解復(fù)合運(yùn)算： 關(guān)系矩陣：復(fù)合關(guān)系的性質(zhì)（10分鐘）r s s r.例：r =(x,y)|x,ya, y = x+1或y = x/2s =(x, y)| x,ya, x = y +2定理2-4： 證明思路： 定理2-5： 定理2-6： 證明： 注：本性質(zhì)與矩陣的有關(guān)運(yùn)算性質(zhì)類似, 請(qǐng)注意順序定理2-7：冪

41、運(yùn)算（10分鐘） 冪的表示方式：例2-23： 設(shè)a=a,b,c,集合a上的關(guān)系r=(a,b),(b,c),(c,a),試計(jì)算冪運(yùn)算的性質(zhì)：函數(shù)的復(fù)合運(yùn)算（5分鐘）設(shè)f: a b, g: b c,函數(shù)f與函數(shù)g的復(fù)合記為fg: 若f (x) = y且g(y) = z, 則(fg)(x) = g(f(x) = z. 由于f a b, g b c, 關(guān)系f與關(guān)系g的復(fù)合記為fg: 若(x, y) f且(y, z) g, 則(x, z) fg.注：函數(shù)f與函數(shù)g的復(fù)合fg與將其看作關(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)系、

42、逆關(guān)系的定義、表示方式、相應(yīng)的關(guān)系矩陣進(jìn)行了講解，還介紹了它們之間滿足的相關(guān)性質(zhì)，最后介紹了函數(shù)的復(fù)合運(yùn)算。四、 作業(yè)與實(shí)驗(yàn)（2分鐘）1. 書面作業(yè)：習(xí)題2.2 1、3、6、8、12(選).2. 上機(jī)作業(yè)：無(wú)第七講：關(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)分析1.重點(diǎn)： 自反性、反自反性、對(duì)稱性、反對(duì)稱性、傳遞性概念的理解，閉包的理解與構(gòu)造2.難點(diǎn)：同上三、教學(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)入主題，開始第七講本

43、講知識(shí)點(diǎn)概括 (1)關(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自反 注：空關(guān)系是空集上的自反關(guān)系. 關(guān)系矩陣：對(duì)角線元素都為1關(guān)系圖：結(jié)點(diǎn)含有環(huán) 反自反性（10分鐘）定義：設(shè)r a a, 若對(duì)于任意x a, 均有(x, x) r, 則稱r是a上的反自反關(guān)系, 或稱r具有反自反性.例2-26： a = a, b, c, d, r = (b, a), (a, b), (b, c), (c, d), (c, a)?注：z上的整除關(guān)系|不是反自反的; p(x)上的包含關(guān)系不是反自反的; r上的小于等于關(guān)系不是反自反的;r上的小于關(guān)系是反自反的.定理：r反自反 注：空關(guān)系是空集上的反自反關(guān)系.關(guān)系矩陣：對(duì)角線元素全為0關(guān)系圖：結(jié)點(diǎn)沒(méi)有環(huán)思考：a上的自反關(guān)系與反自反關(guān)系的區(qū)別與聯(lián)系? 對(duì)稱性（10分鐘）定義：設(shè)r a a, 對(duì)于任意x, y a,若(x, y