離散數(shù)學(xué)教案

《離散數(shù)學(xué)教案》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)教案（97頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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