五邑大學2021年碩士研究生招生考試專業科目考試大綱

一、考試科目：離散數學

二、基本要求

離散數學的基本概念、基本理論和基本算法。主要內容包括命題邏輯、謂詞邏輯、集合與關系、函數、圖論等知識。在內容的組織上，力求提供培養學生抽象思維、慎密概括和嚴密的邏輯推理能力知識的同時，注重展現離散數學在計算機科學及信息科學中的應用。

三、考試范圍

1、命題邏輯的基本概念、理論及方法

（1）理解命題的概念，掌握常用的命題聯結詞。

（2） 理解命題的合式公式概念，會用真值表來判別公式的真假。

（3） 知道公式的等價關系和蘊含關系,會利用真值表和常用的基本等值式作等值演算。

（4）會用真值表法及等值演算求合式公式的主析取范式和主合取范式。

（5）知道命題演算的推理理論，掌握直接證明、條件證明、反證法，能進行一些簡單推理。

2、謂詞邏輯的基本概念、理論及方法

（1）熟悉一階謂詞邏輯的謂詞、量詞等概念。知道謂詞公式的概念。

（2） 知道謂詞演算中關于量詞的等值式。

（3） 熟悉常見謂詞演算的基本規則；掌握謂詞演算的推理理論。。

3、集合論的基本概念、理論及方法。

（1）理解集合的概念，掌握集合和元素間的關系。

（2） 熟悉集合與集合之間的關系（相等、包含）。

（3）熟練掌握集合之間的運算及基本運算規律。

（4）掌握冪集及笛卡爾積的計算。

4、關系與函數的基本概念、理論及方法。

（1）理解關系的基本概念，掌握關系的圖及其矩陣表示方法。

（2）掌握關系的運算，理解關系的幾種特性。

（3）掌握關系的閉包運算。

（4）了解函數的基本概念，掌握復合函數、逆函數的計算。

（5）了解基數、無限集合的理解和區分

（6）理解等價關系、等價類、商集、會根據等價關系求等價類,理解并掌握等價關系與集合劃分之間的重要關系會求出等價關系所產生的一個集合的劃分。

（7）偏序關系的概念，會用哈斯圖表示偏序關系

5、圖的基本理論

（1）理解圖的基本概念；

（2）理解圖同構。

（3）掌握通路和回路的概念。

（4）掌握圖的矩陣表示法（鄰接矩陣、關聯矩陣）。

（5） 理解圖的連通性，掌握連通性的判別方法，對簡單有向圖會判斷強連通、單向連通還是弱連通。能熟練地求圖的點割集、邊割集，割點、割邊。

（6）了解權圖中的最短路問題及一些算法。

6、特殊圖基本概念、理論及方法。

（1）理解歐拉圖、歐拉通路、歐拉回路的概念

（2）知道哈密頓圖的概念及哈密頓圖與歐拉圖的區別，掌握相關的重要結論，會判斷一個圖是否是歐拉圖或哈密頓圖。

（3）理解二分圖的概念,會求最大匹配.

（4）了解平面圖的基本概念，掌握歐拉公式，了解相關的重要結論。

（5）了解平面圖的點著色, 了解四色定理。

（6） 理解有向樹、生成樹、最小生成樹的概念，會由連通圖來尋找生成樹,掌握最小生成樹的構造方法。

（7）理解帶權樹、二元樹等概念，掌握Huffman算法，熟悉前綴碼及其應用。

三、參考書目

（1）吳明芬，張先勇，朱鐵丹等，離散數學，人民郵電出版社，2014，9787115365439

（2）屈婉玲，耿素云，張立昂，離散數學，高等教育出版社，2008，9787040231250