離散數(shù)學教案

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

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

3、創(chuàng)造條件，而且為學生今后提高專業(yè)理論水平，從事計算機行業(yè)的實際工作提供必備的抽象思維和嚴格的邏輯推理能力，為將來參與創(chuàng)新性的研究和開發(fā)工作打下堅實的基礎。（二）教學內(nèi)容安排教學內(nèi)容教學要求教學方法重點()難點()學時分配備注講課實驗上機其他第一部分 數(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 推理的形式結構A13.2 自然推理系統(tǒng)PB14一階邏輯基本概念24.1一階邏輯命題符號化A14.2 一階邏

4、輯公式及解釋A15一階邏輯等值演算與推理35.1 一階邏輯等值式與置換規(guī)則A15.2 一階邏輯前束范式A15.3 一階邏輯的推理理論A16數(shù)理邏輯在計算機中的應用3第二部分 集合論講授131集合代數(shù)21.1 集合的基本概念B0.51.2 集合的運算A0.51.3 有窮集的計數(shù)C0.51.4 集合恒等式A0.52二元關系62.1 有序對與笛卡爾積A12.2 二元關系A12.3 關系的運算A12.4 關系的性質A12.5 關系的閉包A12.6 等價關系與劃分A13函數(shù)33.1 函數(shù)的定義與性質A0.53.2函數(shù)的復合與反函數(shù)A0.53.3雙射函數(shù)與集合的基數(shù)C13.4 一個電話系統(tǒng)的描述實例C14

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

6、B0.54.2 歐拉公式B0.54.3 平面圖的判斷B14.4 平面圖的對偶圖C15 圖論在計算機中的應用3（教學要求：A熟練掌握；B掌握；C了解）三、實驗內(nèi)容本課程無實驗制訂人（簽字）： 審核人（簽字）： 教 學 進 度 表 20122013學年第1學期周 數(shù) 16 周 計劃學時 48學時講 課 48 學時 課堂討論 0 學時實驗課 0 學時 習題課 0 學時 其他環(huán)節(jié) 0 學時授課教師姓名 趙歡歡 職稱 助教 授課專業(yè) 網(wǎng)絡工程 班級 2011級 課程名稱 離散數(shù)學 教材名稱 離散數(shù)學 出版社 清華大學出版社 周次日期周學時其中教學內(nèi)容摘要（章節(jié)名稱、講述的內(nèi)容提要、實驗的名稱、課堂討論的

7、題目等）講課實驗課習題課課堂討論其他環(huán)節(jié)第一周9月3日至9月9日44第一講 集合、映射與運算（一）1.1 集合的基本概念 理論：集合、子集、冪集、n元組、笛卡爾積第二講 集合、映射與運算（二）1.2 映射的有關概念 理論：映射的定義、映射的性質、逆映射、復合映射第二周9月10日至9月16日22第三講 集合、映射與運算（三）1.3運算的定義和性質 理論：運算的定義、運算的性質第三周9月17日至9月23日44第四講 集合、映射與運算（四）1.4 集合的運算 1.5 集合的劃分 1.6 集合的對等理論：集合的并、交、差、補、對稱差等基本運算，集合的劃分與覆蓋、集合對等、可數(shù)集合、不可數(shù)集合第五講 關

8、系（一）2.1 關系的概念理論：n元關系的定義、2元關系、關系的定義域和值域、關系的表示、函數(shù)的關系定義第四周9月24日至9月30日22第六講 關系（二）2.1 關系的運算 理論：關系的集合運算、逆運算、復合運算、關系的其他運算第五周10月1日至10月7日 4 4國慶放假第七講 關系（三）2.3 關系的性質 2.4 關系的閉包理論：關系的性質：自反性、反自反性、對稱性、反對稱性、傳遞性；自反閉包r(R)、對稱閉包s(R)、傳遞閉包t(R)第六周10月8日至10月14日22第八講 關系（四）2.5 等價關系 2.6相容關系 2.7偏序關系理論：等價關系的定義、等價類；相容關系的定義；偏序關系的定

9、義、哈斯圖的、偏序集中的特殊元素第七周10月15日至10月21日44第九講 命題邏輯（一）3.1 命題的有關概念 3.2 邏輯聯(lián)接詞理論：命題的定義與真值、原子命題和復合命題、各種邏輯連接詞的含義，真假的判斷第十講 命題邏輯（二）3.3 命題公式及其真值表理論：命題公式的定義、命題的符號化、命題公式的真值表、命題公式的類型第八周10月22日至10月28日22第十一講 命題邏輯（三）3.4 邏輯等值的命題公式理論：邏輯等值的定義、基本等值式、等值演算法、對偶原理第九周10月29日至11月4日 44第十二講 命題邏輯（四）3.5 命題公式的范式理論：命題公式的析取范式和合取范式的定義域求法命題公式

10、的主析取范式及主合取范式的定義和求法第十三講 命題邏輯（五）3.7 命題邏輯中的推理理論：推理形式有效性的定義；基本推理規(guī)則；命題邏輯的自然推理系統(tǒng)第十周11月5日至11月11日22第十四講 謂詞邏輯（一）4.1 個體、謂詞、量詞和函詞理論：謂詞邏輯概念，謂詞的概念與表示，量詞的概念與表示，個體域，轄域，約束變元和自由變元的含義第十一周 11月12日至11月18日44第十五講 謂詞邏輯（二）4.2謂詞公式及命題的符號化 4.3 謂詞公式的解釋及類型理論：謂詞公式的定義，將命題用用符號（個體，量詞，謂詞）來表示，消去量詞的邏輯等值式，永真式，科滿足式，永假式及中性式的概念第十六講 謂詞邏輯（三）

11、4.4邏輯等值的謂詞公式 4.5謂詞公式的前束范式 理論：謂詞公式等值的定義，基本等值式，前束范式第十二周11月19日至11月25日22第十七講 圖論（一）6.1 圖的基本概念 6.2 節(jié)點的度數(shù)6.3 子圖，圖的運算和圖同構理論：圖的定義，鄰接，關聯(lián)，簡單圖，節(jié)點的度數(shù)，子圖第十三周11月26日至12月2日44第十八講 圖論（二）6.4 路與回路 6.5圖的連通性理論內(nèi)容：路，回路，無向圖的連通性，無向連通圖的點連通度與邊連通度，有向圖的連通性第十九講 圖論（三）6.6 圖的矩陣表示 6.7 賦權圖及最短路徑理論內(nèi)容：圖的鄰接矩陣，可達矩陣，關聯(lián)矩陣，賦權圖，最短路徑第十四周12月3日至12

12、月9日22第二十講 圖論（四）7.1 歐拉圖理論內(nèi)容：歐拉圖的有關概念，歐拉定理，中國郵遞員問題、Hamilton 圖第十五周12月8日至12月16日44第二十一講 圖論（五）7.2 無向樹 7.3 有向樹理論內(nèi)容：樹的基本概念，最小生成樹，二叉樹的遍歷與表達式的計算第二十二講 代數(shù)結構（一）5.1 代數(shù)結構簡介理論內(nèi)容：代數(shù)結構的定義，半群及獨異點，子代數(shù)，代數(shù)結構的同態(tài)與同構第十六周12月17日至12月23日22第二十三講 代數(shù)結構（二）5.2 群的定義及性質理論內(nèi)容：群的有關概念，子群，群的同態(tài)第十七周12月24日至12月30日22第二十四講 總復習系主任簽名： 院長簽名： 年 月 日

13、年 月 日說明：1本教學進度表由主講教師負責填寫，于每學期開學第一周內(nèi)送交教師所在系，經(jīng)領導審定、簽字后備查。2此表一式三份，其中，任課教師一份，教師所在系一份，教務處一份。第一講：集合、映射和運算（一）一、教學目標1. 掌握集合的概念與表示2. 理解子集、冪集、 n元組與笛卡兒積的概念3.掌握子集，冪集，笛卡爾積的求法 二、重點與難點分析1.重點：集合的概念，子集，冪集，笛卡爾積的概念及求法2.難點：冪集三、 教學內(nèi)容與教學過程1.進行自我介紹（5分鐘）姓名，聯(lián)系方式，專業(yè)方向。建議學生用電子郵件方式聯(lián)系。2.進行課程簡介（10分鐘） 離散數(shù)學是研究離散量的結構及相互之間關系的學科 是一門專

14、業(yè)基礎課，是數(shù)據(jù)結構、操作系統(tǒng)、計算機組成原理、數(shù)據(jù)庫原理等課程的數(shù)學基礎。 特點：知識點集中，概念，定理多；方法性強；學數(shù)學就要做數(shù)學 成績評定：平時成績(到課情況，書面作業(yè)，平時測驗)占30%,期末考試占70%3.進入主題，開始第一講(1) 集合的有關概念(20分鐘)集合 定義：集合是具有某種特定性質的對象匯集成的一個整體，通常用大寫字母A,B,C,D表示。例如：滁州學院全體學生 計算機與信息工程學院所有女生 常見的數(shù)的集合：N,N+,Z,Q,R,C元素集合中的每一個對象稱為該集合的元素，通常用小寫字母a,b,c,d,x,等表示例如：滁州學院的每個學生 計算機與信息工程學院的每個女生 N：

15、0、1、2、3集合的表示方法 列舉法：Z=,-2,-1,0,1,2, 描述法：x|x是自然數(shù)且x小于10 遞歸法文氏圖： 特殊集合：全集U,空集元素與集合 xA或 |A|表示集合A中的元素個數(shù) 注意：集合中的元素可以是集合，如A=a,a,b,b,c,|A|=4,a,bA注：集合中的元素無順序；集合中無重復元素例：指出下列哪些是集合，哪些不是集合？ 中國人的集合； 百貨商店里好看的花布的集合； 1000以內(nèi)的素數(shù)的集合； 26個英文字母組成的集合； 這個班里高個子學生的集合； 直線y2x-5上的點的集合。(2)集合之間的關系子集（15分鐘）定義：若A中的任意元素都屬于B，則A是B的子集，稱A包含

16、于B或B包含A，包括的兩層含義：包含與真包含（AB），A是B的真子集注意：屬于（元素與集合的關系）與包含于（集合與集合的關系）的區(qū)別例：A=1,2,3,4，B=2,4 或定理1-1：A定理1-2：（自反性）則A=B則（傳遞性） 用定義進行證明定理1-3：A=B的充要條件是注：該定理是證明兩個集合相等的基本方法 該定理與定理1-2中的(2)的區(qū)別 例1-2注：A中有一個元素不屬于C，則，反證法是一種很好的方法冪集（15分鐘）定義：由X的所有子集組成的集合， 例：x=1,2 ，Y=a,b,c 例1-3 注：若|X|=n,P(x)的元素有：；由一個元素構成的子集；由兩個元素構成的子集；由n個元素構成

17、的子集計數(shù)的基本原理：加法原理：圖示乘法原理：圖示定理1-4：若|X|=n,|P(X)|=2n證明：加法原理：二項式定理： 乘法原理：注：每個元素的參與與否構成不同的子集n元組（5分鐘） 定義：論域U中選取的n個元素按照一定的順序排列，得到n元有序組，稱n元組，記為：(x1,x2,x3,xn)或 例：平面直角坐標系中點的坐標是2元組；空間直角坐標系中點的坐標是3元組；n元組在數(shù)據(jù)結構中是一個表 有序對，序偶：2元組 注：(x,y)(y,x)笛卡爾積（10分鐘） 定義：設是集合，稱為A1,A2,An的笛卡爾積（直積，叉積），記為：例：A=a,b,B=1,2，例1-4注： 一般來說，定理1-5：若

18、|A|=m,|B|=n,則|=mn4. 教學小結（5分鐘）本講首先介紹了集合的概念與表示方法，接著介紹了集合之間的關系子集與冪集，n元組，笛卡爾積的概念及相關定理。 四、 作業(yè)與實驗（5分鐘）1. 書面作業(yè)：習題1.1 1、2、3、7、102. 上機作業(yè)：無第二講：集合、映射和運算（二）一、教學目標1. 掌握映射的概念與表示2. 理解映射的三種性質：單射、滿射、雙射，會判斷某個具體映射是否具有這些性質3.掌握逆映射的含義，復合映射的定義及性質二、重點與難點分析1.重點：理解和判斷映射的三種性質，逆映射，復合映射2.難點：映射三種性質的判斷，復合映射的性質三、教學內(nèi)容與教學過程1.習題講解（10

19、分鐘）2.上講內(nèi)容回顧（3分鐘） 集合的概念：集合、元素、集合的表示方法集合間的關系：子集、冪集、n元組、笛卡爾積(1)映射的定義（15分鐘） 定義：對于A,B,若存在對應法則f，對于，唯一的與它對應，稱f是A到B的一個映射或一個函數(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)映射的性質單射(一對一映射)（10分鐘）

20、定義：，可推出x1=x2 或 ，若x1x2，可得出 例1-6：設則f是N到N的單射，試證明之。 證：對于，由得出，進而x1=x2 (使用定義證明)滿射（10分鐘）定義：對于，使得y=f(x) 充要條件：=B 例1-7：設，則f是Z到N的滿射，試證明之。 證：對于取,顯然有 （使用定義證明）雙射（一一對應）（5分鐘）定義:既單射又滿射例1-8例1-9：建立一個（0,1）到R的一一對應解： 置換：A到A的雙射(3)逆映射（逆函數(shù)，反函數(shù)）（10分鐘）定義：f:AB，將f的方向逆轉后，得到的集合B到集合A的映射定理1-7：f的逆映射存在的充要條件是f是雙射（加以說明解釋） 注：若f是雙射，則也是雙射

21、，且 例1-11：判斷所給出的映射是否有逆射，若有，求出其逆映射 解：f(2)=f(-2)=4, 根據(jù)單射定義知f不是單射，進而其不是雙射，根據(jù)定理1-7知其不存在逆映射 顯然g是雙射，其逆映射為(4)復合映射（20分鐘） 定義:設對于，令，則h是A到C的映射，h為f和g的復合映射或復合函數(shù)，記為（圖示） 注： 條件: 例1-12 例1-13 注：一般來說即使和都有意義，也不能保證成立 恒等映射(IA)： 定理1-9：若是雙射，則 若是雙射，則定理1-10： 若f和g是單射，則是單射（證明） 若f和g是滿射，則是滿射（證明） 若f和g是雙射，則是雙射且 定理1-11：設 若是單射，則f是單射，

22、但g不一定（證明） 若是滿射，則g是滿射，而f不一定（證明） 定理1-12 設，則4. 教學小結（5分鐘）本講首先介紹了映射（函數(shù)）的定義及定義域、值域、像、原像等相關概念；接著介紹了映射的三種性質：單射，滿射，雙射；最后介紹了逆映射的定義及復合映射的定義及其具有的相關性質。四、 作業(yè)與實驗（2分鐘）1. 書面作業(yè)：習題1.2 1、2、6、11、14.2. 上機作業(yè)：無第三講：集合、映射和運算（三）一、教學目標 1. 理解運算的定義2. 掌握運算的表示及常用運算3. 理解運算的性質并能判斷具體運算是否具有某些性質二、重點與難點分析1.重點：運算的定義，運算的性質2.難點：運算性質的判定 三、教

23、學內(nèi)容與教學過程 1.習題講解（5分鐘）2.上講內(nèi)容回顧（5分鐘） 映射的定義 映射的性質：單射，滿射，雙射 逆映射 復合映射3.進入主題，開始第二講。本講知識點概括(1)運算的定義（25分鐘） 定義:設和B是集合，若，稱f為到B的n元運算。 A到B的n元運算，或A上的n元運算： A上的n元封閉運算（代數(shù)運算）： ，有例：判定取絕對值運算|、加法運算+、取大運算max是否是自然數(shù)集合N(Z)上的代數(shù)運算。解： 例：判定減法運算-,取小運算min是否是自然數(shù)集合N上的代數(shù)運算。解： 例：判斷數(shù)的加法運算是否是集合A=2n |nN上的代數(shù)運算？解： 例：將十進制數(shù)273轉換成八進制解： 273=,

24、 , 模運算定義：，是使成立的整數(shù)r,即x除以m的余數(shù)。例：16(mod 3)、-8(mod 5)、9(mod 2)模m加法，模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ù)分解：（對于大于1的正整數(shù)n都可以分解成一些素數(shù)乘積） Euclid算法 例1-19若gcd(m,n)=1,稱m和n互素。歐

25、拉函數(shù)：表示小于等于n且與n互素的正整數(shù)的個數(shù)運算表給定集合A，則集合A上的1元或2元運算可以用運算表來表示例：A=a,b,c,*abcabcababccbca思考：A上的封閉的1元，2元，3元運算的個數(shù)是多少？33 39 327 (2)運算的性質 對合性（5分鐘） 定義：設*是A上的一元代數(shù)運算， 例： ？冪等性（5分鐘） 冪等元：定義：A中的每個元素對于*都是冪等元例：*123112322323313例：交換性（5分鐘） 定義：對于A上的二元運算*,均有 例：R上的+具有交換性 R上的-，映射的復合運算?結合性（5分鐘） 定義： 例:映射的復合運算具有結合性 R上的+具有結合性 R上的-

26、？單位元素（幺元素）（5分鐘） 定義：對于A上的二元運算*，使得對于 例：R關于加法運算+的單位元素是0 R關于乘法運算的單位元素是1 R關于減法運算-的單位元素是？定理1-3：若A關于* 有單位元素，則單位元素是唯一的證明：設e1,e2是A關于*的單位元素，則e1=e1*e2=e2零元素（5分鐘） 定義：對于A上的二元運算*，使得對于 例:R關于乘法運算的零元素是0 R關于減法運算-的零元素是？ R關于加法運算的零元素是？定理1-4：若A關于* 有零元素，則零元素是唯一的證明：設e1,e2是A關于*的零元素，則e1=e1*e2=e2逆元素（5分鐘）前提：A關于二元運算*有單位元素e定義：，使

27、得：例：R上的加法運算+：x+(-x)=0=(-x)+x R上的乘法運算： 注：逆元不一定存在，存在不一定唯一，參見表1-5定理1-5：若A關于*運算有單位元素為e且*運算滿足結合律，若對于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關于*有零元，則記為，對于，若 例1-31 Z上的加法運算+和乘法運算均滿足消去律.分配性（5分鐘） 定義：是A上的兩個二元運算，對于 則稱*關于是可分配的吸收性（2分鐘） 定義：是A上的兩個二元運算，對于則稱*關于是可吸收的德摩根律（3分鐘） 定義

28、：是A上的一元運算，是A上的兩個二元運算，對于4. 教學小結（3分鐘）本講首先介紹了運算的定義并介紹了幾種常用的運算，接著介紹了運算的性質：對合性、冪等性、交換性、結合性、單位元素、零元素、逆元素、消去性、分配性、吸收性、德摩根律，并結合之前所學知識講解運算的性質。 四、 作業(yè)與實驗（2分鐘）1. 書面作業(yè)：習題1.3：1、3、5、6、8 2. 上機作業(yè)：無第四講：集合、映射和運算（四）一、教學目標1.掌握集合的各種運算2.理解各種集合運算所滿足的性質3.掌握集合的劃分與覆蓋的概念4.了解集合的對等，集合的基數(shù)，可數(shù)集合等概念 二、重點與難點分析1.重點：集合的運算并、交、補、差、對稱差 集合

29、運算性質 2.難點：集合運算等值式的證明，集合的對等、基數(shù)三、 教學內(nèi)容與教學過程1.上講內(nèi)容回顧（5分鐘）運算的定義運算的性質：對合性、冪等性、交換性、結合性、單位元素、零元素、逆元素、消去性、分配性、吸收性、德摩根律2.進入主題、開始第四講本講知識點概括(1)集合的運算并運算（15分鐘） 定義： 定理1-16：是包含A和B的最小集合 定理1-17：并運算滿足的性質： （交換律） （結合律） （冪等律）（是運算的單位元素）（是運算的零元素）例1-38:設f : A B, X, Y A, 則證明：證明： 交運算（15分鐘） 定義： 定理1-18：是包含在A和B的最大集合定理1-19：交運算滿足

30、的性質： （冪等律） （交換律） （結合律） （是運算的零元素）（U是運算的單位元素） 例：定理1-20：并運算與交運算之間滿足的性質： 例1-41：證：補運算（10分鐘） 定義：例1-42：（A的補集依賴于全集U的選?。〢=a,b,cU=a,b,c,d 定理1-21：定理1-22：德摩根律：P25： 差運算（10分鐘）定義：例1-43：定理1-23：證明：例1-45：證明： 證：例1-46：例1-47： 對稱差運算（10分鐘）定義：例定理1-24：容斥原理形式： 或： 例：求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除數(shù)有多少個？ 解： |S| = 1000 |A|=1000/

31、5=200, |B|=1000/6=166 |AB| = 1000/lcm(5,6) = 1000/33 = 33 （2）集合的劃分與覆蓋（12分鐘） 劃分定義：其中：例1-53： 設A = a, b, c, 則A的所有不同的劃分分別為: 覆蓋設A是集合, 由A的若干非空子集構成的集合稱為A的覆蓋, 如果這些非空子集的并等于A.（3）集合的對等（10分鐘）定義：A B 存在雙射f : A B.例：(0, 1) R 集合的基數(shù)：無限集合A 若集合A和B對等, 則稱這兩個集合的基數(shù)相同.例：可數(shù)集合：能與自然數(shù)集合N對等的集合3. 教學小結（2分鐘）本講首先介紹了集合的各種運算（并，交，補，差，對

32、稱差）及其滿足的性質，接著介紹了集合的劃分與覆蓋的概念；最后介紹了集合對等、集合的基數(shù)及可數(shù)集合。四、 作業(yè)與實驗（1分鐘）1. 書面作業(yè)： 習題1.4 5、8、10、13. 習題1.5：1、7 2. 上機作業(yè)：無第五講：關系（一）一、教學目標1. 掌握關系的概念尤其是二元關系的概念2. 掌握關系的定義域和值域3. 掌握關系的三種表示方法4. 理解函數(shù)的關系定義二、重點與難點分析1.重點：二元關系概念、關系的三種表示方式、函數(shù)的關系定義2.難點：關系的概念三、 教學內(nèi)容與教學過程1.習題講解（15分鐘） 2.上章內(nèi)容回顧（5分鐘）集合的有關概念映射的有關概念運算的定義與性質集合的運算、集合的劃

33、分與覆蓋、集合的對等3.進入主題，開始第五講本講知識點介紹(1)關系的定義關系的概念（15分鐘）引例：A = 張三, 李四, 王五;B = 英語, C語言, 離散數(shù)學, 數(shù)據(jù)結構, 匯編語言;C = 優(yōu), 良, 合格, 不合格.A與B之間的關系R = (張三, 離散數(shù)學), (張三, 數(shù)據(jù)結構), (張三, 英語), (李四, 數(shù)據(jù)結構), (王五, C語言), (王五, 匯編語言) A B.A, B與C之間的關系S = (張三, 離散數(shù)學, 優(yōu)), (張三, 數(shù)據(jù)結構, 良), (張三, 英語, 優(yōu)), (李四, 數(shù)據(jù)結構, 優(yōu)), (王五, C語言, 合格), (王五, 匯編語言, 良)

34、A B C.定義：是集合， ，則R為間的n元關系特別的 為A上的n元關系注（兩層含義）：集合、關系例：A=王，李，張，黃，B=100米，400米，鉛球，跳遠，C=第一名，第二名，第三名，優(yōu)秀獎R=(王，100米，第二名)，（李，鉛球，優(yōu)秀獎），（張，100米，第一名），（黃，跳遠，第二名）二元關系的定義：兩個集合A和B（可以相同）之間的關系稱為二元關系 A到B的關系： A上的關系：例：A=甲，乙，丙 R=(乙，甲)，（乙，丙），（甲，丙） 注：(x,y)表示x勝y例：A=張三，李四，王五，B=教師，輔導員，導師 R=（張三，輔導員），（張三，教師），（李四，教師），（王五，導師），（王五，教師

35、）例2-1： 例：A=a,b,R是P(A)上的包含關系，R=(x,y)|x,yP(A)且P(A)= 注意：關系的次序定理2-1：若，則A到B的關系有 若，則A上的關系有注：A到B的關系是AB的子集三種特殊的關系（5分鐘）空關系：A到B的空關系 A上的空關系全關系：A到B的全關系 A上的全關系恒等關系： 例：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)關系符號（10分鐘）定義：若(x,y) ,則可記為 例：實數(shù)集合R上的大于“”關系： 例：整數(shù)集Z上的整除關系“|” 整除性質

36、：例：模m同余關系 性質：關系的定義域和值域（5分鐘）定義域:設,即R中所有有序對中第一位置元素組成的集合, 它顯然是A的子集.值域：設R AB, ran R = y|yB, 存在xA, 使得(x, y) R, 即R中所有有序對中第二位置元素組成的集合, 它是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) 關系的表示（20分鐘）集合表示法列舉法：把關系內(nèi)部的元素全部列舉出來描述法：把關系內(nèi)部成員的性

37、質描述出來（同集合）關系圖表示法情形1 R是A到B的關系A = a, b, c, d, B = 1, 2, 3, R = (a, 2), (a, 3), (c, 2), (d, 2).情形2 R是A上的關系A = a, b, c, d， 注：有向邊關系矩陣表示法定義：例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ù)的關系定義（5分鐘）函數(shù)到關系的轉換例：A = a, b, c, B = 1, 2, 3, f: A B, f(a) = 2, f(b) = 3, f(c) =

38、 3.關系能夠轉換成函數(shù)的條件 例：，不能轉換成函數(shù)。 例2-164. 教學小結（3分鐘）本講首先講解關系的概念與表示，特別介紹了二元關系，同時描述了三種特殊的關系：空關系、全關系、恒等關系，然后講解了關系的三種表示方式：集合表示法、關系圖表示法、關系矩陣表示法，接著講解了關系與函數(shù)的區(qū)別與聯(lián)系及它們間的轉換。四、 作業(yè)與實驗（2分鐘）1. 書面作業(yè)：習題2.1： 2、4(2)(4)(5)、13、14.2. 上機作業(yè)：無第六講：關系（二）一、教學目標 1. 掌握關系的集合運算2. 掌握關系的逆運算，逆關系的關系矩陣、關系圖及逆關系的定理3. 掌握復合關系、復合關系相關定理 4. 了解函數(shù)的復合

39、運算二、重點與難點分析1.重點：復合關系、逆關系的概念及相關性質2.難點：復合關系、逆關系的性質三、 教學內(nèi)容與教學過程1.習題講解（10分鐘）2.上講內(nèi)容回顧（5分鐘）N元關系的定義2元關系關系的定義域與值域關系的表示函數(shù)的關系定義3.進入主題，開始第六講。 (1)關系的集合運算（15分鐘） 關系的幾種常見集合運算: 注： 解：例2-17(2)關系的逆運算（20分鐘） 為何考慮關系的逆運算? 若x是y的老師,則y是x的學生, 定義：注：就是將所有R中的有序對中的兩個元素交換次序，例2-18：A = a, b, c, d, B = 1, 2, 3, R = (a, 3), (c, 2), (a

40、, 2), (b, 2). 則逆關系的關系圖 有向線條反向（圖示例2-18）逆關系的關系矩陣 原關系的關系矩陣的轉置（示例2-18） 逆運算的性質：定理2-2：（對合律）定理2-3：逆運算與關系的集合運算并, 交, 補的關系 證明：（）：(3)關系的復合運算（35分鐘）為何考慮關系的復合運算? 若x是y的母親, y是z的妻子, 則x是z的岳母, 關系R到關系S的復合運算（10分鐘）例：，則：例2-19：借助關系圖理解復合運算： 關系矩陣：復合關系的性質（10分鐘）R S S R.例：R =(x,y)|x,yA, y = x+1或y = x/2S =(x, y)| x,yA, x = y +2定

41、理2-4： 證明思路： 定理2-5： 定理2-6： 證明： 注：本性質與矩陣的有關運算性質類似, 請注意順序定理2-7：冪運算（10分鐘） 冪的表示方式：例2-23： 設A=a,b,c,集合A上的關系R=(a,b),(b,c),(c,a),試計算冪運算的性質：函數(shù)的復合運算（5分鐘）設f: A B, g: B C,函數(shù)f與函數(shù)g的復合記為fg: 若f (x) = y且g(y) = z, 則(fg)(x) = g(f(x) = z. 由于f A B, g B C, 關系f與關系g的復合記為fg: 若(x, y) f且(y, z) g, 則(x, z) fg.注：函數(shù)f與函數(shù)g的復合fg與將其看作

42、關系時關系f與關系g的復合是一致的4. 教學小結（3分鐘）本講分別介紹了關系的集合運算、逆運算，復合運算，并且對復合關系、逆關系的定義、表示方式、相應的關系矩陣進行了講解，還介紹了它們之間滿足的相關性質，最后介紹了函數(shù)的復合運算。四、 作業(yè)與實驗（2分鐘）1. 書面作業(yè)：習題2.2 1、3、6、8、12(選).2. 上機作業(yè)：無第七講：關系（三）一、教學目標1. 理解關系的各種性質2. 掌握滿足各種性質的關系的關系矩陣和關系圖3. 理解閉包的含義4. 掌握閉包的幾個關鍵5. 掌握閉包的構造二、重點與難點分析1.重點： 自反性、反自反性、對稱性、反對稱性、傳遞性概念的理解，閉包的理解與構造2.難

43、點：同上三、教學內(nèi)容與教學過程1.上講內(nèi)容回顧（5分鐘）關系的集合運算關系的逆運算關系的復合運算2.進入主題，開始第七講本講知識點概括 (1)關系的性質 自反性（10分鐘）定義：對于集合A上的元素a屬于A，有(a,a)屬于R,那么R就是一個自反關系例2-25： A = a, b, c, d, R = (a, a), (a, b), (b, b), (c, c), (c, a), (d, d)?注：Z上的整除關系|是自反的; P(X)上的包含關系是自反的; R上的小于等于關系是自反的; R上的小于關系不是自反的. 定理：R自反 注：空關系是空集上的自反關系. 關系矩陣：對角線元素都為1關系圖：結點含有環(huán) 反自反性（10分鐘）定義：設R A A, 若對于任意x A, 均有(x, x) R, 則稱R是A上的反自反關系, 或稱R具有反自反性.例2-26： A = a, b, c, d, R = (b, a), (a, b), (b, c), (c, d), (c, a)?注：Z上的整除關系|不是反自反的; P(X)上的包含關系不是反自反的; R上的小于等于關系不是反自反的;R上的小于關系是反自反的.定理：R反自反 注：空關系是空集上的反自反關系.關系