00 考試大綱

離散數學與組合數學彙總

文章目錄

• • 一 命題邏輯的等值演算與推理演算
  • 二 謂詞邏輯的等值演算和推理演算
  • 三 集合與關系
  • 四 圖論的基本概念、路與回路
  • 五 樹、平面圖與圖的着色
  • 六 代數結構
  • 七 排列與組合
  • 八 母函數與遞推關系
  • 九 容斥原理和鴿巢原理
  • 十 Polya定理

高款數學與組合數學是現代數學的重要分支,是計算機科學的基能理論課程。

數理邏輯、集合論、圖論與代數結構是離散數學的重要組成部分。

要求考生對它們的基本概念有較深入的了解,能夠系統地掌握命題演算、請詞演算及樸素集合論的經典内容,掌握演繹推理的基本方法。掌據居論的基本定理和應用,熟悉代數系統的基本概念及定理。

組合數學部分要求考生掌握各種基本的計數方法,線性常系數遞卷關系的解法, Burnside引理和Polya定理的應用,容斥原理和鴿巢原理的應用等。

主要内容包括:

一 命題邏輯的等值演算與推理演算

1. 命題邏輯的基本概念、命題邏輯聯結詞與真值表,重言式
2. 簡單命題的形式化(簡單自然語句的形式化)
3. 等值定理、基本等值公式以及等值演算
4. 命題公式與真值表的關系、聯結詞的完備集
5. 析取範式、合取範式、主析取範式和主合取範式
6. 命題邏輯的推理規則與推理演算,歸結推理證明方法
7. 命題邏輯公理系統的概念,公理系統的基本結構

二 謂詞邏輯的等值演算和推理演算

1. 謂詞、量詞的基本概念及表示法
2. 複雜自然語句的形式化
3. 否定型等值式、景詞配置設定等值式
4. 範式、前東範式,Skolem标準形5,基本推理公式及其證明方法
5. 謂詞邏輯的推理規則與推理演算,歸結推理法

三 集合與關系

1. 集合的概念、性質和基本運算,集合同的關系和特殊集合
2. 有限集合的基數,包含排斥原理
3. 集合論公理系統,無窮公理和自然數集合
4. 二進制關系的概念、關系矩陣和關系圖
5. 關系的逆、合成,關系的基本性質,關系的閉包
6. 等價關系和劃分,偏序關系與哈斯圖
7. 任意集合上的函數定義與性質、特殊函數,滿射、單射與雙射8,集合的勢、無限集合的基數

四 圖論的基本概念、路與回路

1. 圖的基本概念與性質
2. 圖的代數表示
3. 途徑、路、回路、迹的定義
4. 歐拉環遊(歐拉閉迹)與歐拉迹
5. 漢密爾頓路與回路
6. 最短路徑
7. 連通性
8. 有向圖

五 樹、平面圖與圖的着色

1. 樹的定義及等價條件
2. 支撐樹的計數
3. 森林
4. 最短樹
5. 平面圖與極大平面圖
6. 對偶圖
7. 色數與色多項式

六 代數結構

1. 代數系統的概念
2. 同構與同态
3. 群的基本知識
4. 循環群、群的同構
5. 變換群和置換群、Caylay定理
6. 陪集和群的陪集分解、Lagrange定理
7. 正規子群與商群
8. 同态、同态基本定理
9. 環和域的概念

七 排列與組合

1. 加法法則與乘法法則
2. 排列與組合
3. Stirling近似公式
4. 排列的生成算法
5. 組合的生成算法
6. 可重組合
7. 若幹等式及其組合意義

八 母函數與遞推關系

1. 母函數
2. 遞推關系
3. Fibonacci 效列
4. 線性常系數遞推關系
5. 整數的拆分和Ferrers 圖像
6. 指數型母函數
7. 母函數和遞推關系應用舉例
8. 錯排問題
9. Stirling數
10. Catalan數

九 容斥原理和鴿巢原理

1. 容斥原理
2. 棋盤多項式與有限制排列
3. 一般公式
4. 二項式反演與Mobius反演
5. 鴿巢原理
6. Ramsey問題和Ramsey數

十 Polya定理

1. Burnside引理
2. Polya定理
3. 母函數型的Polya定理
4. 圖的計數