課程簡介
Course Introduction
教學大綱
Teaching Syllabus
離散數學(Discrete mathematics)是研究離散量的結構及其相互關系的數學學科，是現代數學的一個重要分支。它在各學科領域，特別在計算機科學與技術相關領域有著廣泛的應用。
教學內容以基本概念、結論、算法、推理與證明方法，以及一般應用方法的介紹為主，主要內容包括數理邏輯、集合論、與圖論等內容。
通過本課程的學習，要求學生理解離散數學的基本概念、結論、算法、應用方法及適用范圍；了解和掌握處理離散結構的描述工具和方法；提高抽象思維和嚴格的邏輯推理能力，為后續課程的學習及將來從事計算機軟硬件技術開發打好必要的理論基礎。
（一）第1章 命題邏輯
主要知識點:
1.1命題與邏輯聯結詞
1.2命題公式及公式分類
1.3等值式與等值演算
1.4范式與主范式
1.5推理理論
教學要求:通過本章學習，了解命題概念，掌握五種聯結詞與真值表的構造；理解命題公式的概念，掌握命題公式類型的判斷；理解等值式的概念，掌握命題公式的等值演算；理解析取范式與合取范式的概念，掌握主析取范式與主合取范式的求解方法；理解推理的形式結構與推理定律，掌握形式證明的方法與技巧。
重點:主析取范式與主合取范式及命題邏輯的推理理論。
難點:主析取范式與主合取范式的求解、推理理論及應用。
采用的教學方法:知識點講解、習題講解。
講授學時:8學時
講解習題:1學時
（二）第2章 謂詞邏輯
主要知識點:
2.1基本概念
2.1謂詞公式
2.3謂詞邏輯蘊含式和等值式
2.4前束范式
2.5謂詞邏輯推理理論
教學要求:通過本章學習，理解謂詞、量詞、變元、個體域等概念；掌握用謂詞、量詞、聯結詞構造謂詞邏輯公式的方法。理解一階邏輯公式的概念及其解釋，掌握簡單一階邏輯公式類型的判斷方法；理解一階邏輯置換規則、換名規則、代替規則，掌握一階邏輯基本等值式的使用；掌握一階邏輯公式前束公式的求解方法；能夠以謂詞邏輯作為工具，將命題符號化，并能用推理規則進行邏輯證明。
重點:一階邏輯的概念與表示，一階邏輯公式及其解釋，一階邏輯的等值式與置換規則，一階邏輯的推理理論。
難點:一階邏輯公式類型的判斷和一階邏輯的推理證明。
采用的教學方法:知識點講解、習題講解。
講授學時:8學時
講解習題:1學時
（三）第3章 關系
主要知識點:
3.1笛卡兒積
3.2關系的概念與表示方法
3.3關系的運算
3.4關系的性質
3.5關系的閉包
3.6關系等價與劃分
3.7偏序關系
教學要求:通過本章學習，理解笛卡兒積與二元關系的概念，掌握關系的表示、運算與性質；理解關系閉包的定義，掌握關系閉包的求解方法；理解等價關系、劃分與偏序關系的定義，掌握等價關系和偏序關系的結構。
重點:等價關系與偏序關系的結構及應用、關系的閉包與算法。
難點:關系的閉包與算法。
采用的教學方法:知識點講解、習題講解。
講授學時:8學時
講解習題:1學時
（四）第4章 函數
主要知識點:
4.1函數的概念
4.2特殊函數
4.3逆函數與復合函數
4.4幾個重要的函數
4.5函數的應用
教學要求:通過本章學習，理解函數的基本概念，掌握函數的性質；掌握逆函數和復合函數的基本概念與性質；。
重點:逆函數和復合函數的性質。
難點:逆函數和復合函數的性質。
采用的教學方法:知識點講解、習題講解。
講授學時:5學時
講解習題:1學時
（五）第5章 圖論
主要知識點:
5.1圖的定義及相關概念
5.2通路、回路與連通圖
5.3圖的矩陣表示
5.4歐拉圖與哈密頓圖
5.5最短路徑問題與貨郎擔問題
5.6平面圖和圖的著色
教學要求:通過本章學習，了解圖論的基本內容及其在計算機領域中的應用；理解圖的基本概念、子圖與補圖概念，通路與回路的概念、圖的連通性與連通度的概念、歐拉圖與漢密爾頓圖的概念、樹及最優樹的概念；掌握圖的表示方法、圖的可達性與連通性的判斷；掌握圖的通路與回路的判斷、圖的連通性的判斷；掌握歐拉圖與漢密爾頓圖的判定方法；掌握求最小生成樹的Kruskal算法、求最優樹的Huffman算法。
重點:握手定理及其推論的應用、圖中通路和回路應用、圖中的可達性和連通性的求解方法、歐拉圖判定、哈密頓圖判定、最短路徑及應用、最小生成樹。
難點:圖的連通性的有關定理、圖的同構及哈密爾頓圖的判定。
采用的教學方法:知識點講解、習題講解。
講授學時:7學時
講解習題:2學時
（六）第6章 樹
主要知識點:
6.1無向樹及性質
6.2根樹
6.3生成樹
6.4樹的應用
教學要求:通過本章學習，了解樹、生成樹、最小生成樹的基本概念，掌握求最優二叉樹的Huffman算法，以及求最小生成樹的Kruskal算法和Prim算法。
重點:二叉樹的遍歷及搜索，Huffman算法，最小生成樹以及Kruskal算法和Prim算法。
難點:Huffman算法、Kruskal算法、Prim算法。
采用的教學方法:知識點講解、習題講解。
講授學時:7學時
講解習題:2學時
在本門課程結束時，學生應該能夠:
1. 掌握析取范式與合取范式的求法，自然推理系統的推理理論；一階邏輯的推理理論，在一階邏輯中構造推理證明的方法。
2.掌握二元關系的運算、關系的性質、關系的閉包，掌握等價關系和劃分及偏序關系，掌握判斷函數單射、滿射、雙射的方法。
3. 掌握圖的矩陣表示，求最短路程與路線的方法；掌握用閉圈法求最小生成樹的方法，用算法求最優樹、最佳前綴碼的方法。
4. 提高學生的抽象思維和邏輯推理能力上有較好提高
（一）出勤
學生應積極參與課堂教學并完成相關的作業。
（二）閱讀資料
學生應認真進行課前預習，閱讀教材和指定參考書及重要的參考文獻。
（三）課堂演示
結合理論課教學內容，教師課堂內容和習題講解、同學討論。
（四）課程實驗
本課程是理論的課程，不安排課外實踐作為課程內容。
（五）小考與期末考
課程中隨機問答。期末考試形式為閉卷筆試。
（六）學術誠信
按中山大學南方學院相關規定執行。
（七）剽竊的定義以及相應的懲罰
剽竊是嚴重違反學校規章制度的行為。一經發現，將上報相關部門，并受到包括開除學籍在內的嚴厲處罰。
（一）教科書-必讀
1. 王瑞胡等主編，離散數學及其應用，清華大學出版社，2014
（二）教科書-強烈推薦
1. 耿素云，屈婉玲編著，《離散數學》北京大學出版社，2002年2. 操作系統真象還原，鄭鋼，人民郵電出版社，2016
（三）文章-必讀
近年《計算機學報》、《軟件學報》等國內、國際期刊雜志刊登的文章。
（四）文章-強烈推薦
無
（五）其他參考資料
1. Kenneth.Rosen 著，袁崇義 屈婉玲 等譯,《離散數學及其應用》（原書第6版）, 機械工業出版社 2011
（一）教學活動
1、個人預習
2、課堂講授
3、課堂問答
4、習題講解
5、案例討論
6、期中測驗
7、期末考試
（二）對預期學習成果的考察
預期學習成果 | 教學活動 | 學習成果考察內容:作業/課程實驗 |
第1章 命題邏輯 | 1,2,3,4,5,7 | 課后作業P7(1,2)，P10(1,2,3)，P15(1,8,9)， P21(7)，P29(1,2) |
第2章 謂詞邏輯 | 1,2,3,4,5,7 | 課后作業P33(1,3)， P38(1), P42(2)，P44(1)， P47(1) |
第3章 關系 | 1,2,3,4,5,7 | 課后作業P59(1,2)，P66(1,2)， P70(2)， P74(3,4)， P80(1,2)， P89(2)， P94(2) |
第4章 函數 | 1,2,3,4,5,7 | 課后作業P101(1,4)， P103(1,2)，P107(1,2) |
第5章 圖論 | 1,2,3,4,5,7 | 課后作業P158(1)，P160(3)， P166(3,4)， P171(1,2)，P175(1)，P179(1) |
第6章 樹 | 1,2,3,4,5,7 | 課后作業P188(1,2)， P196(3)， P202(2,3)， |
（一）評分體系
1、出勤率: 10%
2、課堂參與: 15%
3、課后作業: 15%
4、期末考試: 60%
（二）評分標準及要求
課堂參與度 (10%+15%) |
1）全勤 2）課前預習 3）積極回答課堂問題及參與課堂討論 |
課后作業(15%) |
1）按時按量完成課后作業內容 2）能正確完成課后作業 3）作業格式、書寫符合規范 |
期末考試 (60%) |
1）按時參加期末考試 2）正確解答試卷的問題 3）格式書寫符合規范 |
周次 | 課程要點 | 理論學時 | 討論學時 | 習題學時 |
1 | 命題與邏輯聯結詞,命題公式及公式分類 | 3 | ||
2 | 等值式與等值演算，范式與主范式 | 3 | ||
3 | 推理理論 | 2 | 1 | |
4 | 謂詞邏輯基本概念，謂詞公式 | 3 | ||
5 | 謂詞邏輯蘊含式和等值式，前束范式 | 3 | ||
6 | 謂詞邏輯推理理論 | 2 | 1 | |
7 | 笛卡兒積，關系的概念與表示方法，關系的運算， | 3 | ||
8 | 關系的性質，關系的閉包， | 3 | ||
9 | 關系等價與劃分，偏序關系 | 2 | 1 | |
10 | 函數的概念，特殊函數，逆函數與復合函數 | 3 | ||
11 | 幾個重要的函數，函數的應用 | 2 | 1 | |
12 | 圖的定義及相關概念，通路、回路與連通圖 | 3 | ||
13 | 圖的矩陣表示，歐拉圖與哈密頓圖 | 2 | 1 | |
14 | 最短路徑問題與貨郎擔問題，平面圖和圖的著色 | 2 | 1 | |
15 | 無向樹及性質，根樹 | 3 | ||
16 | 生成樹 | 2 | 1 | |
17 | 樹的應用 | 2 | 1 | |
18 | 復習、答疑 | 3 | ||
19 | ||||
20 | ||||
總學時 | ||||
