離散數學教案

《離散數學教案》由會員分享，可在線閱讀，更多相關《離散數學教案（97頁珍藏版）》請在裝配圖網上搜索。

滁州學院計算機與信息工程學院 課程教案 課程名稱： 離散數學 授課教師： 趙歡歡 授課對象： 11級網絡工程專業(yè)3、4班 授課時間： 2012年9月-2012年12月 滁州學院計算機科學與信息工程學院 2012年8月 《離散數學》教學大綱 （Discrete Mathematic） 課程代碼： 學時：48 學分：3 一、課程簡介 本大綱根據2009版應用型人才培養(yǎng)方案制訂。 （一）教學對象：網絡工程、計算機科學與技術專業(yè)本科學生 （二）開課學期：第三學期 （三）課程類別：專業(yè)基礎課 （四）考核方式：考試 （五）參考教材：《離散數學》第2版 鄧輝文 清華大學出版社 2010. 主要參考書目： [1]邵學才,葉秀明. 離散數學[M].北京電子工業(yè)出版社，2009. [2]邵志清,虞慧群. 離散數學[M].北京電子工業(yè)出版社，2003. [3]屈婉玲. 離散數學習題解析[M].北京大學出版社，2008. 本課程的先修課程是高等數學、線性代數，后續(xù)課程包含數據結構、數據庫原理及應用、操作系統(tǒng)、數字邏輯、人工智能、算法分析與設計等。 二、教學基本要求與內容安排 （一）教學目的與要求 離散數學是研究離散量的結構及其相互關系的學科,它在各學科領域特別在計算機科學領域有著廣泛的應用，同時離散數學也是計算機專業(yè)的許多專業(yè)課程必不可少的先行課程。 本課程的教學目的旨在通過對離散數學的教學，讓學生不但可以掌握處理如集合、代數結構和圖等離散結構的描述工具和方法，為后續(xù)課程的學習創(chuàng)造條件，而且為學生今后提高專業(yè)理論水平，從事計算機行業(yè)的實際工作提供必備的抽象思維和嚴格的邏輯推理能力，為將來參與創(chuàng)新性的研究和開發(fā)工作打下堅實的基礎。 （二）教學內容安排 教學內容 教學要求 教學 方法 重點 (☆) 難點 (Δ) 學時分配 備注 講課 實驗 上機 其他 第一部分 數理邏輯 講授 15.5 1命題邏輯的基本概念 2 1.1命題與聯(lián)接詞 B ☆ 1 1.2命題公式及其賦值 A ☆ Δ 1 2命題邏輯等值演算 3.5 2.1等值式 B ☆ 1 2.2析取范式與合取范式 A ☆ Δ 1 2.3聯(lián)接詞的完備集 C 0.5 2.4可滿足性與消解法 B 1 3命題邏輯的推理理論 2 3.1 推理的形式結構 A ☆ 1 3.2 自然推理系統(tǒng)P B Δ 1 4一階邏輯基本概念 2 4.1一階邏輯命題符號化 A ☆ 1 4.2 一階邏輯公式及解釋 A ☆ Δ 1 5一階邏輯等值演算與推理 3 5.1 一階邏輯等值式與置換規(guī)則 A ☆ 1 5.2 一階邏輯前束范式 A ☆ 1 5.3 一階邏輯的推理理論 A ☆ Δ 1 6數理邏輯在計算機中的應用 3 第二部分 集合論 講授 13 1集合代數 2 1.1 集合的基本概念 B 0.5 1.2 集合的運算 A ☆ 0.5 1.3 有窮集的計數 C 0.5 1.4 集合恒等式 A ☆ 0.5 2二元關系 6 2.1 有序對與笛卡爾積 A ☆ 1 2.2 二元關系 A ☆ 1 2.3 關系的運算 A ☆ 1 2.4 關系的性質 A ☆ Δ 1 2.5 關系的閉包 A ☆ 1 2.6 等價關系與劃分 A ☆ Δ 1 3函數 3 3.1 函數的定義與性質 A ☆ 0.5 3.2函數的復合與反函數 A ☆ 0.5 3.3雙射函數與集合的基數 C Δ 1 3.4 一個電話系統(tǒng)的描述實例 C Δ 1 4集合論在計算機中的應用 2 第三部分 代數結構 講授 6 1.5 1代數系統(tǒng) 3 1.1 二元運算及其性質 A ☆ 1 1.2 代數系統(tǒng) A ☆ 1 1.3 代數系統(tǒng)的同態(tài) 與同構 B Δ 1 2群與環(huán) 3 2.1 群的定義及其性質 A ☆ 1 2.2 循環(huán)群與置換群 A ☆ Δ 2 第四部分 圖論 講授 12 1圖的基本概念 2.5 1.1 圖 A ☆ 0.5 1.2 連通與回路 A ☆ 0.5 1.3 圖的連通性 A ☆ 0.5 1.4 圖的矩陣表示 A ☆ 0.5 1.5 圖的運算 A ☆ Δ 0.5 2歐拉圖與哈密頓圖 2 2.1 歐拉圖 A ☆ 0.5 2.2 哈密頓圖 A ☆ 0.5 2.3 最短路問題與貨郎擔問題 C Δ 1 3樹 1.5 3.1 無向樹及其性質 A ☆ 0.5 3.2 生成樹 A ☆ 0.5 3.3 根樹及其應用 B 0.5 4平面圖 3 4.1 平面圖的基本概念 B 0.5 4.2 歐拉公式 B ☆ 0.5 4.3 平面圖的判斷 B 1 4.4 平面圖的對偶圖 C 1 5 圖論在計算機中的應用 3 （教學要求：A—熟練掌握；B—掌握；C—了解） 三、實驗內容 本課程無實驗 制訂人（簽字）： 審核人（簽字）： 教 學 進 度 表 2012～2013學年第1學期 周 數 16 周 計劃學時 48學時 講 課 48 學時 課堂討論 0 學時 實驗課 0 學時 習題課 0 學時 其他環(huán)節(jié) 0 學時 授課教師姓名 趙歡歡 職稱 助教 授課專業(yè) 網絡工程 班級 2011級 課程名稱 離散數學 教材名稱 離散數學 出版社 清華大學出版社 周次 日期 周學時 其中 教學內容摘要 （章節(jié)名稱、講述的內容提要、實驗的名稱、課堂討論的題目等） 講課 實驗課 習題課 課堂討論 其他環(huán)節(jié) 第一周 9月3日至9月9日 4 4 第一講 集合、映射與運算（一） 1.1 集合的基本概念 理論：集合、子集、冪集、n元組、笛卡爾積 第二講 集合、映射與運算（二） 1.2 映射的有關概念 理論：映射的定義、映射的性質、逆映射、復合映射 第二周 9月10日至9月16日 2 2 第三講 集合、映射與運算（三） 1.3運算的定義和性質 理論：運算的定義、運算的性質 第三周 9月17日至9月23日 4 4 第四講 集合、映射與運算（四） 1.4 集合的運算 1.5 集合的劃分 1.6 集合的對等 理論：集合的并、交、差、補、對稱差等基本運算，集合的劃分與覆蓋、集合對等、可數集合、不可數集合 第五講 關系（一） 2.1 關系的概念 理論：n元關系的定義、2元關系、關系的定義域和值域、關系的表示、函數的關系定義 第四周 9月24日至9月30日 2 2 第六講 關系（二） 2.1 關系的運算 理論：關系的集合運算、逆運算、復合運算、關系的其他運算 第五周 10月1日至10月7日 4 4 國慶放假 第七講 關系（三） 2.3 關系的性質 2.4 關系的閉包 理論：關系的性質：自反性、反自反性、對稱性、反對稱性、傳遞性；自反閉包r(R)、對稱閉包s(R)、傳遞閉包t(R) 第六周 10月8日至10月14日 2 2 第八講 關系（四） 2.5 等價關系 2.6相容關系 2.7偏序關系 理論：等價關系的定義、等價類；相容關系的定義；偏序關系的定義、哈斯圖的、偏序集中的特殊元素 第七周 10月15日至10月21日 4 4 第九講 命題邏輯（一） 3.1 命題的有關概念 3.2 邏輯聯(lián)接詞 理論：命題的定義與真值、原子命題和復合命題、各種邏輯連接詞的含義，真假的判斷 第十講 命題邏輯（二） 3.3 命題公式及其真值表 理論：命題公式的定義、命題的符號化、命題公式的真值表、命題公式的類型 第八周 10月22日至10月28日 2 2 第十一講 命題邏輯（三） 3.4 邏輯等值的命題公式 理論：邏輯等值的定義、基本等值式、等值演算法、對偶原理 第九周 10月29日至11月4日 4 4 第十二講 命題邏輯（四） 3.5 命題公式的范式 理論：命題公式的析取范式和合取范式的定義域求法 命題公式的主析取范式及主合取范式的定義和求法 第十三講 命題邏輯（五） 3.7 命題邏輯中的推理 理論：推理形式有效性的定義；基本推理規(guī)則；命題邏輯的自然推理系統(tǒng) 第十周 11月5日至11月11日 2 2 第十四講 謂詞邏輯（一） 4.1 個體、謂詞、量詞和函詞 理論：謂詞邏輯概念，謂詞的概念與表示，量詞的概念與表示，個體域，轄域，約束變元和自由變元的含義 第十一周 11月12日至11月18日 4 4 第十五講 謂詞邏輯（二） 4.2謂詞公式及命題的符號化 4.3 謂詞公式的解釋及類型 理論：謂詞公式的定義，將命題用用符號（個體，量詞，謂詞）來表示，消去量詞的邏輯等值式，永真式，科滿足式，永假式及中性式的概念 第十六講 謂詞邏輯（三） 4.4邏輯等值的謂詞公式 4.5謂詞公式的前束范式 理論：謂詞公式等值的定義，基本等值式，前束范式 第十二周 11月19日至11月25日 2 2 第十七講 圖論（一） 6.1 圖的基本概念 6.2 節(jié)點的度數6.3 子圖，圖的運算和圖同構 理論：圖的定義，鄰接，關聯(lián)，簡單圖，節(jié)點的度數，子圖 第十三周 11月26日至12月2日 4 4 第十八講 圖論（二） 6.4 路與回路 6.5圖的連通性 理論內容：路，回路，無向圖的連通性，無向連通圖的點連通度與邊連通度，有向圖的連通性 第十九講 圖論（三） 6.6 圖的矩陣表示 6.7 賦權圖及最短路徑 理論內容：圖的鄰接矩陣，可達矩陣，關聯(lián)矩陣，賦權圖，最短路徑 第十四周 12月3日至12月9日 2 2 第二十講 圖論（四） 7.1 歐拉圖 理論內容：歐拉圖的有關概念，歐拉定理，中國郵遞員問題、Hamilton 圖 第十五周 12月8日至12月16日 4 4 第二十一講 圖論（五） 7.2 無向樹 7.3 有向樹 理論內容：樹的基本概念，最小生成樹，二叉樹的遍歷與表達式的計算 第二十二講 代數結構（一） 5.1 代數結構簡介 理論內容：代數結構的定義，半群及獨異點，子代數，代數結構的同態(tài)與同構 第十六周 12月17日至12月23日 2 2 第二十三講 代數結構（二） 5.2 群的定義及性質 理論內容：群的有關概念，子群，群的同態(tài) 第十七周 12月24日至12月30日 2 2 第二十四講 總復習 系主任簽名： 院長簽名： 年 月 日 年 月 日 說明：1．本教學進度表由主講教師負責填寫，于每學期開學第一周內送交教師所在系，經領導審定、簽字后備查。 2．此表一式三份，其中，任課教師一份，教師所在系一份，教務處一份。 第一講：集合、映射和運算（一） 一、教學目標 1. 掌握集合的概念與表示 2. 理解子集、冪集、 n元組與笛卡兒積的概念 3.掌握子集，冪集，笛卡爾積的求法 二、重點與難點分析 1.重點：集合的概念，子集，冪集，笛卡爾積的概念及求法 2.難點：冪集 三、 教學內容與教學過程 1.進行自我介紹（5分鐘） 姓名，聯(lián)系方式，專業(yè)方向。建議學生用電子郵件方式聯(lián)系。 2.進行課程簡介（10分鐘） 離散數學是研究離散量的結構及相互之間關系的學科 是一門專業(yè)基礎課，是數據結構、操作系統(tǒng)、計算機組成原理、數據庫原理等課程的數學基礎。 特點：知識點集中，概念，定理多；方法性強；學數學就要做數學 成績評定：平時成績(到課情況，書面作業(yè)，平時測驗)占30%,期末考試占70% 3.進入主題，開始第一講 (1) 集合的有關概念(20分鐘) ①集合 定義：集合是具有某種特定性質的對象匯集成的一個整體，通常用大寫字母A,B,C,D表示。 例如：滁州學院全體學生 計算機與信息工程學院所有女生 常見的數的集合：N,N+,Z,Q,R,C ②元素 集合中的每一個對象稱為該集合的元素，通常用小寫字母a,b,c,d,x,等表示 例如：滁州學院的每個學生 計算機與信息工程學院的每個女生 N：0、1、2、3… ③集合的表示方法 列舉法：Z={…,-2,-1,0,1,2,…} 描述法：{x|x是自然數且x小于10} 遞歸法 文氏圖： 特殊集合：全集U,空集 ④元素與集合 x∈A或 |A|表示集合A中的元素個數 注意：集合中的元素可以是集合，如A={a,{a,b},b,c},|A|=4,{a,b}∈A 注：集合中的元素無順序；集合中無重復元素 例：指出下列哪些是集合，哪些不是集合？ 中國人的集合； 百貨商店里好看的花布的集合； 1000以內的素數的集合； 26個英文字母組成的集合； 這個班里高個子學生的集合； 直線y＝2x-5上的點的集合。 (2)集合之間的關系 ①子集（15分鐘） 定義：若A中的任意元素都屬于B，則A是B的子集，稱A包含于B或B包含A，，包括的兩層含義：包含與真包含（A≠B），，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個元素構成的子集 計數的基本原理： 加法原理：圖示 乘法原理：圖示 定理1-4：若|X|=n,|P(X)|=2n 證明： 加法原理：二項式定理： 乘法原理： 注：每個元素的參與與否構成不同的子集 ③n元組（5分鐘） 定義：論域U中選取的n個元素按照一定的順序排列，得到n元有序組，稱n元組，記為：(x1,x2,x3,…,xn)或 例：平面直角坐標系中點的坐標是2元組；空間直角坐標系中點的坐標是3元組；n元組在數據結構中是一個表 有序對，序偶：2元組 注：(x,y)≠(y,x) ④笛卡爾積（10分鐘） 定義：設是集合，稱為A1,A2,…An的笛卡爾積（直積，叉積），記為： 例：A={a,b},B={1,2}， 例1-4 注： 一般來說， 定理1-5：若|A|=m,|B|=n,則||=mn 4. 教學小結（5分鐘） 本講首先介紹了集合的概念與表示方法，接著介紹了集合之間的關系——子集與冪集，n元組，笛卡爾積的概念及相關定理。 四、 作業(yè)與實驗（5分鐘） 1. 書面作業(yè)：習題1.1 1、2、3、7、10 2. 上機作業(yè)：無 第二講：集合、映射和運算（二） 一、教學目標 1. 掌握映射的概念與表示 2. 理解映射的三種性質：單射、滿射、雙射，會判斷某個具體映射是否具有這些性質 3.掌握逆映射的含義，復合映射的定義及性質 二、重點與難點分析 1.重點：理解和判斷映射的三種性質，逆映射，復合映射 2.難點：映射三種性質的判斷，復合映射的性質 三、教學內容與教學過程 1.習題講解（10分鐘） 2.上講內容回顧（3分鐘） 集合的概念：集合、元素、集合的表示方法 集合間的關系：子集、冪集、n元組、笛卡爾積 (1)映射的定義（15分鐘） 定義：對于A,B,若存在對應法則f，對于，唯一的與它對應，稱f是A到B的一個映射或一個函數。記為：f:A→B （圖示） 例：Ceiling function Floor function 取整函數 定義域：自變量x的取值范圍 值域：函數值y的取值范圍 像：為X在映射f下的像 原像：為Y在映射f下的原像 注：全函數即=A；為x在映射f下的像 ：A到B的所有映射組成的集合 定理1-6：|A|=m,|B|=n,則（證明） (2)映射的性質 ①單射(一對一映射)（10分鐘） 定義：，可推出x1=x2 或 ，若x1≠x2，可得出 例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)逆映射（逆函數，反函數）（10分鐘） 定義：f:A→B，將f的方向逆轉后，得到的集合B到集合A的映射 定理1-7：f的逆映射存在的充要條件是f是雙射 （加以說明解釋） 注：若f是雙射，則也是雙射，且 例1-11：判斷所給出的映射是否有逆射，若有，求出其逆映射 ① ② 解：①∵f(2)=f(-2)=4, ∴根據單射定義知f不是單射，進而其不是雙射，根據定理1-7知其不存在逆映射 ②顯然g是雙射，其逆映射為 (4)復合映射（20分鐘） 定義:設對于，令，則h是A到C的映射，h為f和g的復合映射或復合函數，記為（圖示） 注： 條件: 例1-12 例1-13 注：一般來說即使和都有意義，也不能保證成立 恒等映射(IA)： 定理1-9：若是雙射，則 若是雙射，則 定理1-10： 若f和g是單射，則是單射（證明） 若f和g是滿射，則是滿射（證明） 若f和g是雙射，則是雙射且 定理1-11：設 若是單射，則f是單射，但g不一定（證明） 若是滿射，則g是滿射，而f不一定（證明） 定理1-12 設，則 4. 教學小結（5分鐘） 本講首先介紹了映射（函數）的定義及定義域、值域、像、原像等相關概念；接著介紹了映射的三種性質：單射，滿射，雙射；最后介紹了逆映射的定義及復合映射的定義及其具有的相關性質。 四、 作業(yè)與實驗（2分鐘） 1. 書面作業(yè)：習題1.2 1、2、6、11、14. 2. 上機作業(yè)：無 第三講：集合、映射和運算（三） 一、教學目標 1. 理解運算的定義 2. 掌握運算的表示及常用運算 3. 理解運算的性質并能判斷具體運算是否具有某些性質 二、重點與難點分析 1.重點：運算的定義，運算的性質 2.難點：運算性質的判定 三、教學內容與教學過程 　 1.習題講解（5分鐘） 2.上講內容回顧（5分鐘） 映射的定義 映射的性質：單射，滿射，雙射 逆映射 復合映射 3.進入主題，開始第二講。 本講知識點概括 (1)運算的定義（25分鐘） ①定義:設和B是集合，若，稱f為到B的n元運算。 A到B的n元運算，或A上的n元運算： A上的n元封閉運算（代數運算）： ，有 例：判定取絕對值運算||、加法運算+、取大運算max是否是自然數集合N(Z)上的代數運算。 解： 例：判定減法運算-,取小運算min是否是自然數集合N上的代數運算。 解： 例：判斷數的加法運算是否是集合A={2n |n∈N}上的代數運算？ 解： 例：將十進制數273轉換成八進制 解： 273=, , ②模運算 定義：，是使成立的整數r,即x除以m的余數。 例：16(mod 3)、-8(mod 5)、9(mod 2) 模m加法，模m乘法 例：m=5, ③最大公約數，最小公倍數 若d|m且d|n,則d是m,n的公約數，用gcd(m,n)表示m,n的最大公約數 若m|d且n|d，則d是m,n的公倍數，用lcm(m,n)表示m,n的最小公倍數。 注：Gcd與lcm分別記為[,]和（，） gcd(m , n)= gcd(|m| ,| n|)且lcm(m, n)=lcm(|m|, |n|) 素因數分解：（對于大于1的正整數n都可以分解成一些素數乘積） Euclid算法 例1-19 若gcd(m,n)=1,稱m和n互素。 歐拉函數：表示小于等于n且與n互素的正整數的個數 ④運算表 給定集合A，則集合A上的1元或2元運算可以用運算表來表示 例：A={a,b,c},* * a b c a b c a b a b c c b c a 思考：A上的封閉的1元，2元，3元運算的個數是多少？ 33 39 327 (2)運算的性質 ①對合性（5分鐘） 定義：設*是A上的一元代數運算， 例： ？ ②冪等性（5分鐘） 冪等元： 定義：A中的每個元素對于*都是冪等元 例： * 1 2 3 1 1 2 3 2 2 3 2 3 3 1 3 例： ③交換性（5分鐘） 定義：對于A上的二元運算*,,均有 例：R上的+具有交換性 R上的-，映射的復合運算? ④結合性（5分鐘） 定義： 例:映射的復合運算具有結合性 R上的+具有結合性 R上的- ？ ⑤單位元素（幺元素）（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 定義：，使得： 例：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分鐘） 定義：是A上的一元運算，是A上的兩個二元運算，對于 4. 教學小結（3分鐘） 本講首先介紹了運算的定義并介紹了幾種常用的運算，接著介紹了運算的性質：對合性、冪等性、交換性、結合性、單位元素、零元素、逆元素、消去性、分配性、吸收性、德摩根律，并結合之前所學知識講解運算的性質。 四、 作業(yè)與實驗（2分鐘） 1. 書面作業(yè)：習題1.3：1、3、5、6、8 2. 上機作業(yè)：無 第四講：集合、映射和運算（四） 一、教學目標 1.掌握集合的各種運算 2.理解各種集合運算所滿足的性質 3.掌握集合的劃分與覆蓋的概念 4.了解集合的對等，集合的基數，可數集合等概念 二、重點與難點分析 1.重點：集合的運算——并、交、補、差、對稱差 集合運算性質 2.難點：集合運算等值式的證明，集合的對等、基數 三、 教學內容與教學過程 1.上講內容回顧（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：交運算滿足的性質： （冪等律） （交換律） （結合律） （是運算的零元素） （U是運算的單位元素） 例： 定理1-20：并運算與交運算之間滿足的性質： 例1-41： 證： ③補運算（10分鐘） 定義： 例1-42：（A的補集依賴于全集U的選?。? A={a,b,c} U={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在內）既不能被5和6整 除數有多少個？ 解： |S| = 1000 |A|=1000/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 集合的基數：無限集合A 若集合A和B對等, 則稱這兩個集合的基數相同.例： 可數集合：能與自然數集合N對等的集合 3. 教學小結（2分鐘） 本講首先介紹了集合的各種運算（并，交，補，差，對稱差）及其滿足的性質，接著介紹了集合的劃分與覆蓋的概念；最后介紹了集合對等、集合的基數及可數集合。 四、 作業(yè)與實驗（1分鐘） 1. 書面作業(yè)： 習題1.4 5、8、10、13. 習題1.5：1、7 2. 上機作業(yè)：無 第五講：關系（一） 一、教學目標 1. 掌握關系的概念尤其是二元關系的概念 2. 掌握關系的定義域和值域 3. 掌握關系的三種表示方法 4. 理解函數的關系定義 二、重點與難點分析 1.重點：二元關系概念、關系的三種表示方式、函數的關系定義 2.難點：關系的概念 三、 教學內容與教學過程 1.習題講解（15分鐘） 2.上章內容回顧（5分鐘） 集合的有關概念 映射的有關概念 運算的定義與性質 集合的運算、集合的劃分與覆蓋、集合的對等 3.進入主題，開始第五講 本講知識點介紹 (1)關系的定義 ①關系的概念（15分鐘） 引例：A = {張三, 李四, 王五}; B = {英語, C語言, 離散數學, 數據結構, 匯編語言}; C = {優(yōu), 良, 合格, 不合格}. A與B之間的關系R = {(張三, 離散數學), (張三, 數據結構), (張三, 英語), (李四, 數據結構), (王五, C語言), (王五, 匯編語言)} A B. A, B與C之間的關系S = {(張三, 離散數學, 優(yōu)), (張三, 數據結構, 良), (張三, 英語, 優(yōu)), (李四, 數據結構, 優(yōu)), (王五, C語言, 合格), (王五, 匯編語言, 良)} 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={（張三，輔導員），（張三，教師），（李四，教師），（王五，導師），（王五，教師）} 例2-1： 例：A={a,b},R是P(A)上的包含關系，R={(x,y)|x,y∈P(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) ,則可記為 例：實數集合R上的大于“>”關系： 例：整數集Z上的整除關系“|” 整除性質： 例：模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分鐘） ①集合表示法 列舉法：把關系內部的元素全部列舉出來 描述法：把關系內部成員的性質描述出來（同集合） ②關系圖表示法 情形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)函數的關系定義（5分鐘） ①函數到關系的轉換 例：A = {a, b, c}, B = {1, 2, 3}, f: A B, f(a) = 2, f(b) = 3, f(c) = 3. ②關系能夠轉換成函數的條件 例：，不能轉換成函數。 例2-16 4. 教學小結（3分鐘） 本講首先講解關系的概念與表示，特別介紹了二元關系，同時描述了三種特殊的關系：空關系、全關系、恒等關系，然后講解了關系的三種表示方式：集合表示法、關系圖表示法、關系矩陣表示法，接著講解了關系與函數的區(qū)別與聯(lián)系及它們間的轉換。 四、 作業(yè)與實驗（2分鐘） 1. 書面作業(yè)：習題2.1： 2、4(2)(4)(5)、13、14. 2. 上機作業(yè)：無 第六講：關系（二） 一、教學目標 1. 掌握關系的集合運算 2. 掌握關系的逆運算，逆關系的關系矩陣、關系圖及逆關系的定理 3. 掌握復合關系、復合關系相關定理 4. 了解函數的復合運算 二、重點與難點分析 1.重點：復合關系、逆關系的概念及相關性質 2.難點：復合關系、逆關系的性質 三、 教學內容與教學過程 1.習題講解（10分鐘） 2.上講內容回顧（5分鐘） N元關系的定義 2元關系 關系的定義域與值域 關系的表示 函數的關系定義 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, 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/2} S ={(x, y)| x,yA, x = y +2} ≠ 定理2-4： 證明思路： 定理2-5： 定理2-6： 證明： 注：本性質與矩陣的有關運算性質類似, 請注意順序 定理2-7： ③冪運算（10分鐘） 冪的表示方式： 例2-23： 設A={a,b,c},集合A上的關系R={(a,b),(b,c),(c,a)},試計算 冪運算的性質： ④函數的復合運算（5分鐘） 設f: A B, g: B C,函數f與函數g的復合記為f?g: 若f (x) = y且g(y) = z, 則(f?g)(x) = g(f(x)) = z. 由于f A B, g B C, 關系f與關系g的復合記為f?g: 若(x, y) f且(y, z) g, 則(x, z) f?g. 注：函數f與函數g的復合f?g與將其看作關系時關系f與關系g的復合是一致的 4. 教學小結（3分鐘） 本講分別介紹了關系的集合運算、逆運算，復合運算，并且對復合關系、逆關系的定義、表示方式、相應的關系矩陣進行了講解，還介紹了它們之間滿足的相關性質，最后介紹了函數的復合運算。 四、 作業(yè)與實驗（2分鐘） 1. 書面作業(yè)：習題2.2 1、3、6、8、12(選). 2. 上機作業(yè)：無 第七講：關系（三） 一、教學目標 1. 理解關系的各種性質 2. 掌握滿足各種性質的關系的關系矩陣和關系圖 3. 理解閉包的含義 4. 掌握閉包的幾個關鍵 5. 掌握閉包的構造 二、重點與難點分析 1.重點： 自反性、反自反性、對稱性、反對稱性、傳遞性概念的理解，閉包的理解與構造 2.難點：同上 三、教學內容與教學過程 1.上講內容回顧（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反自反 注：空關系是空集上的反自反關系. 關系矩陣：對角線元素全為0 關系圖：結點沒有環(huán) 思考：A上的自反關系與反自反關系的區(qū)別與聯(lián)系? ③ 對稱性（10分鐘） 定義：設R A A, 對于任意x, y A,若(x, y) R, 則(y, x) R, 則稱R是A上的對稱關系, 或稱R是對稱的, 或稱R具有對稱性 例2-28： A = {a, b, c, d}, R = {(b, a), (a, b), (b, b), (d, c), (c, d)}? 注：Z上的整除關系|不是對稱的; P(X)上的包含關系(一般來說)不是對稱的; R上的小于等于關系不是對稱的; R上的小于關系<不是對稱的; 三角形之間的相似關系~是對稱的; Z上的模k同余關系k是對稱的. 定理2-11：R對稱 R = R-1 關系矩陣：關于對角線對稱圖 關系圖：要么有雙向環(huán)、要么沒有 ④ 反對稱性（10分鐘） 定義：設R A A, 對于任意x, y A,若(x, y) R且(y, x) R, 一定有x = y, 則稱R是A上的反對稱關系, 或稱R具有反對稱性. 例2-29： A = {a, b, c, d}, R = {(a, a), (a, b), (b, b), (b, c), (d, c)}? 注：Z上的整除關系|不是反對稱的,因為2|-2且-2|2; P(X)上的包含關系是反對稱的; R上的小于等于關系是反對稱的; R上的小于關系<是反對稱的. 定理2-12：R反對稱 關系矩陣:關于主對角線對稱的元素不能同時為1 關系圖:兩點之間要么無邊，要么只有一條邊 思考：反對稱性與對稱性之間的區(qū)別與聯(lián)系 ⑤ 傳遞性（10分鐘） 定義：設R A A, 對于任意x, y, z A,若(x, y) R且(y, z) R,均有(x, z) R, 則稱R是A上的傳遞關系, 或稱R具有傳遞性. 例2-31： A = {a, b, c, d}, R = (a, a), (a, b), (b, b), (b, c), (a, c), (c, a)}? 注：Z上的整除關系|是傳遞的; P(X)上的包含關系是傳遞的; R上的小于等于關系是傳遞的; R上的小于關系<是傳遞的. 定理2-13：R傳遞 R?R R. 證明: ()設(x, z) R?R, 則存在y A, 使得(x, y) R, (y, z) R. 因為R傳遞, 所以(x, z) R. ()對于任意x, y, z A,若(x, y) R且(y, z) R, 則(x, z) R?R R, (x, z) R. 例2-33: A = {a, b, c, d}, R1 = {(a, b), (a, c)}傳遞, R2 = {(a, b)}也傳遞? , 傳遞性的關系圖: 定理2-13:R傳遞 R?R R. (2)關系的閉包 ①自反閉包r(R)（10分鐘） 定義：設R A A, 稱最小的包含R的自反關系為R的自反閉包, 記為r(R). 滿足3個條件:包含R；自反性；最小性. 例2-38： 設A = {a, b, c}, R = {(a, a), (b, a), (b, c), (c, a), (a, c)}, 求出R的自反閉包. 解：r(R)= R {(b, b), (c, c)} 定理2-14: 生成自反閉包關系圖的變化：R中不含環(huán)的添加環(huán) 生成自反閉包關系矩陣的變化：把對角線上是0的元素全部改成1 ②對稱閉包s(R)（10分鐘） 定義：設R A A, 稱最小的包含R的對稱關系為R的對稱閉包, 記為s(R). 滿足3個條件:包含R；對稱性；最小性. 例2-15： 解： 定理2-15： 生成對稱閉包關系圖的變化：只有一邊的添加一邊 生成對稱閉包關系矩陣的變化