【正文】 質(zhì) ①單射 (一對一映射 )（ 10 分鐘） 定義 ： 1, 2x x A??， ( 1) ( 2)f x f x? 可推出 x1=x2 或 1, 2x x A?? ，若 x1≠ x2，可得出 ( 1) ( 2)f x f x? 例 16：設(shè) : , ( ) 2 ,f N N f x x??則 f是 N到 N的單射，試證明之。AA? （自反性） (2) , ,A B B A??則 A=B (3) , ,A B B C??則 AC? （傳遞性） 用定義進行證明 定理 13： A=B 的充要條件是 ,A B B A?? 注：該定理是證明兩個集合相等的基本方法 該定理與定理 12 中的 (2)的區(qū)別 例 12 注： A中有一個元素不屬于 C，則 AC? ， 反證法是一種很好的方法 9 ②冪集 （ 15 分鐘 ） 定義： 由 X的所有子集組成的集合 ， ( ) { | }P X A A X?? 例： x={1,2} ( ) { , {1} , { 2 } , {1, 2 } }PX ?? ， Y={a,b,c} ( ) { , { } , { } , { } , { , } , { , } , { , } , { , , } }P X a b c a b a c b c a b c?? 例 13 注：若 |X|=n,P(x)的元素有： ? ；由一個元素構(gòu)成的子集；由兩個元素構(gòu)成的子集； ? 由 n個元素構(gòu)成的子集 計數(shù)的基本原理： 加法原理： 圖示 乘法原理：圖示 定理 14：若 |X|=n,|P(X)|=2n 證明： 加法原理：二項式定理：0()nn r r n rnrx y C x y ????? 1 2 11 . . . (1 1 ) 2n n n nn n n nC C C C?? ? ? ? ? ? ? ? 乘法原理： 注： 每個元素的參與與否構(gòu)成不同的子集 ③ n 元組 （ 5 分鐘） 定義：論域 U 中選取的 n 個元素按照一定的順序排列 ，得到 n 元有序組，稱n 元組，記為： (x1,x2,x3,… ,xn)或 x1,x2,x3,… ,xn 例：平面直角坐標系中點的坐標是 2 元組；空間直角坐標系中點的坐標是 3元組； n 元組在數(shù)據(jù)結(jié)構(gòu)中是一個 表 有序?qū)Γ蚺迹?2 元組 注： (x,y)≠ (y,x) ④笛卡爾積 （ 10分鐘） 定義：設(shè) 1, 2,...,A A An是集合，稱 ,{ ( 1 , 2 , . . . , ) | 1 , 2 , . . . , }iix x x n x A i n??為A1,A2,… An 的笛卡爾積（直積，叉積） ，記為： 1 2 ,...,A A An?? 例： A={a,b},B={1,2}， 例 14 注： AA?? ??? ?? 一般來說， A B B A? ? ? 定理 15： 若 |A|=m,|B|=n,則 | AB? |=m n 4. 教學小結(jié) （ 5 分鐘） 本講首先介紹了集合 的概念與表示方法 ，接著介紹了 集合之間的關(guān)系 —— 子集 與冪集， n元組，笛卡爾積的概念及相關(guān)定理。 例如：滁州學院全體學生 計算機 與 信 息工程學院所有女生 常見的數(shù)的集合： N,N+,Z,Q,R,C ② 元素 集合中的每一個對象稱為該集合的元素 ，通常用小寫字母 a,b,c,d,x,等表示 例如： 滁州學院的每個學 生 計算機與信息工程學院的每個女生 N： 0、 3… ③集合的表示方法 列舉法： Z={… ,2,1,0,1,2,… } 描述法 ： {x|x 是自然數(shù)且 x 小于 10} 遞歸法 8 文氏圖 ： 特殊集合：全集 U,空集 ? ④ 元素與集合 x∈ A 或 xA? |A|表示集合 A 中的元素個數(shù) 注意：集合中的元素可以是集合，如 A={a,{a,b},b,c},|A|=4,{a,b}∈ A 注：集合中的元素無順序；集合中無重復元素 例：指出下列哪些是集合，哪些不是集合？ 中國人的集合； 百貨商店里好看的花布的集合； 1000 以內(nèi)的素數(shù)的集合； 26 個英文字母組成的集合； 這個班里高個子學生的集合； 直線 y＝ 2x5 上的點的集合。 （ 10 分鐘 ） 離散數(shù)學是研究離散量的結(jié)構(gòu)及相互之間關(guān)系的學科 是一門專業(yè)基礎(chǔ)課， 是數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計算機組成原理、數(shù)據(jù)庫原理等 課程的數(shù)學基礎(chǔ)。 7 第一講：集合、 映射和運算 （一） 一、 教學目標 1. 掌握 集合的概念與表示 2. 理解 子集、 冪集 、 n元組與笛卡兒積 的概念 子集，冪集，笛卡爾積的求法 二、重點與難點分析 ： 集合的概念，子集，冪集，笛卡爾積的概念 及求法 ： 冪集 三、 教學 內(nèi)容與教學過程 （ 5 分鐘） 姓名，聯(lián)系方式，專業(yè)方向。 （二）教學內(nèi)容安排 3 教學內(nèi)容 教學要求 教學 方法 重點 (☆) 難點 (Δ) 學時分配 備注 講課 實驗 上機 其他 第一部分 數(shù)理邏輯 講授 1命題邏輯的基本概念 2 B ☆ 1 A ☆ Δ 1 2命題邏輯等值演算 B ☆ 1 A ☆ Δ 1 C B 1 3命題邏輯的推理理論 2 推理的 形式結(jié)構(gòu) A ☆ 1 自然推理系統(tǒng) P B Δ 1 4一階邏輯基本概念 2 A ☆ 1 一階邏輯公式及解釋 A ☆ Δ 1 5 一階邏輯等值演算與推理 3 一階邏輯等值式與置換規(guī)則 A ☆ 1 一階邏輯前束范式 A ☆ 1 一階邏輯的推理理論 A ☆ Δ 1 6 數(shù)理邏輯在計算機中的應用 3 第二部分 集合論 講授 13 1集合代數(shù) 2 集合的基本概念 B 集合的運算 A ☆ 有窮集的計數(shù) C 集合恒等式 A ☆ 2二元關(guān)系 6 有序?qū)εc笛卡爾積 A ☆ 1 二元關(guān)系 A ☆ 1 關(guān)系的運算 A ☆ 1 關(guān)系的性質(zhì) A ☆ Δ 1 關(guān)系的閉 包 A ☆ 1 等價關(guān)系與劃分 A ☆ Δ 1 3函數(shù) 3 函數(shù)的定義與性質(zhì) A ☆ A ☆ 4 雙射函數(shù)與集合的基數(shù) C Δ 1 一個電話系統(tǒng)的描述實例 C Δ 1 4 集合論在計算機中的應用 2 第三部分 代數(shù)結(jié)構(gòu) 講授 6 1代數(shù)系統(tǒng) 3 二元運算及其性質(zhì) A ☆ 1 代數(shù)系統(tǒng) A ☆ 1 代數(shù)系統(tǒng)的同態(tài) 與同構(gòu) B Δ 1 2群與環(huán) 3 群的定義及其性質(zhì) A ☆ 1 循環(huán)群與置換群 A ☆ Δ 2 第四部分 圖論 講授 12 1圖的基本概念 圖 A ☆ 連通與回路 A ☆ 圖的連通性 A ☆ 圖的矩陣表示 A ☆ 圖的運算 A ☆ Δ 2歐拉圖與哈密頓圖 2 歐拉圖 A ☆ 哈密頓圖 A ☆ 最短路問題與貨郎擔問題 C Δ 1 3樹 無向樹及其性質(zhì) A ☆ 生成樹 A ☆ 根樹及其應用 B 4平面圖 3 平面圖的基本概念 B 歐拉公式 B ☆ 平面圖的判斷 B 1 平面圖的對偶圖 C 1 5 圖論在計算機中的應用 3 （教學要求： A— 熟練掌握； B— 掌握； C— 了解） 三、實驗內(nèi)容 本課程無實驗 制訂人（簽字）： 審核人（簽字）： 5 教 學 進 度 表 2020～ 2020 學年第 1 學期 授課教師姓名 趙歡歡 職稱 助教 授課專業(yè) 網(wǎng)絡工程 班級 2020 級 課程名稱 離散數(shù)學 教材名稱 離散數(shù)學 出版社 清華大學出版社 周次 日期 周學時 其中 教 學 內(nèi) 容 摘 要 （章節(jié)名稱、講述 的內(nèi)容提要、實驗的名稱、課堂討論的題目等） 講課 實驗課 習題課 課堂討論 其他環(huán)節(jié) 第一周 9 月 3 日至9 月 9 日 4 4 第一講 集合、映射與運算（一） 集合的基本概念 理論：集合、子集、冪集、 n元組、笛卡爾積 第二講 集合、映射與運算（二） 映射的有關(guān)概念 理論：映射的定義、映射的性質(zhì)、逆映射、復合映射 第二周 9 月 10 日至 9 月 16日 2 2 第三講 集合、映射與運算（三） 理論：運算的定義、運算的性質(zhì) 第三周 9 月 17 日至 9 月 23日 4 4 第四講 集合、映射與運算（四） 集合的運算 集合的劃分 集合的對等 理論：集合的并、交、差、補、對稱差等基本運算，集合的劃分與覆蓋、集合對等、可數(shù)集合、不可數(shù)集合 第五 講 關(guān)系（一） 關(guān)系的概念 理論： n元關(guān)系的定義、 2元關(guān)系、關(guān)系的定義域和值域、關(guān)系的表示、函數(shù)的關(guān)系定義 第四周 9 月 24 日至 9 月 30日 2 2 第六 講 關(guān)系（二） 關(guān)系的運算 理論：關(guān)系的集合運算、逆運算、復合運算、關(guān)系的其他運算 第五周 10 月 1 日至 10 月 7日 4 4 國慶放假 第七 講 關(guān)系（三） 關(guān)系的性質(zhì) 關(guān)系的閉包 理論：關(guān)系的性質(zhì)：自反性、反自反性、對稱性、反對稱性、傳遞性；自反閉包 r(R)、對稱閉包 s(R)、傳遞閉包 t(R) 第六周 10 月 8 日至 10 月 14日 2 2 第八 講 關(guān)系（四） 等價關(guān)系 理論：等價關(guān)系的定義、等價類；相容關(guān)系的定義；偏序關(guān)系的定義、哈斯圖的、偏序集中的特殊元素 第七周 10 月 15日至 10 月 21日 4 4 第九講 命題邏輯（一） 命題的有關(guān)概念 邏輯聯(lián)接詞 理論：命題的定義與真值、原子命題和復合命題、各種邏輯連接詞的含義，真假的判斷 第 十 講 命題邏輯（二） 命題公式及其真值表 理論：命題公式的定義、命題的符號化、命題公式的真值表、命題公式的類型 第八周 10 月 22日至 10 月 28日 2 2 第十一講 命題邏輯（三） 邏輯等值的命題公式 理論：邏輯等值的定義、基本等值式、等值演算法、對偶原理 周 數(shù) 16 周 計劃學時 48 學時 講 課 48 學時 課堂討論 0 學時 實驗課 0 學時 習題課 0 學時 其他環(huán)節(jié) 0 學時 6 第九周 10 月 29日至 11 月 4日 4 4