2022年碩士研究生入學(xué)考試自命題科目考試大綱

科目代碼：F0205 科目名稱：離散數(shù)學(xué)

一. 考試要求

主要考察學(xué)生對離散數(shù)學(xué)中集合、關(guān)系、函數(shù)、圖論、命題邏輯、一階謂詞邏輯、推理系統(tǒng)、布爾代數(shù)等計算機數(shù)學(xué)的基本概念、計算和證明方法的理解與掌握情況，以及應(yīng)用上述概念和方法進行應(yīng)用問題離散建模、計算求解和邏輯推理的能力。注重概念的深入理解、知識的綜合運用，以及現(xiàn)實問題分析和解決。

二、考試內(nèi)容

1. 邏輯和證明基礎(chǔ)

命題、邏輯聯(lián)接詞、真值表、位操作和位串、命題符號化及應(yīng)用、邏輯等價和蘊含、命題可滿足性及應(yīng)用、謂詞、量詞、量詞表達式等價及否定、嵌套量詞、謂詞邏輯符號化、推理規(guī)則、歸結(jié)、邏輯證明、證明方法、證明策略、邏輯語義。要求熟練掌握命題邏輯和謂詞邏輯的基本概念，掌握邏輯等價和蘊含分析方法，掌握邏輯推理方法和證明方法，能夠熟練運用命題邏輯和謂詞邏輯求解邏輯問題，了解可滿足性問題。

2. 基本結(jié)構(gòu)：集合、函數(shù)、序列、求和

集合基本概念、集合描述方法、常見集合、集合相等、屬于、子集、空集、冪集、集合的基數(shù)、n元組、笛卡爾乘積、集合運算(交、并、差、補)、集合恒等式、廣義交、廣義并、集合的計算機表示、(全)函數(shù)、函數(shù)算術(shù)、1對1函數(shù)、1-1對應(yīng)、內(nèi)射、滿射、雙射、函數(shù)運算(逆函數(shù)、函數(shù)的合成)、若干重要函數(shù)、部分函數(shù)、序列、算術(shù)級數(shù)、幾何級數(shù)、遞推關(guān)系、一些特殊序列、累加、基數(shù)比較關(guān)系(=，³，£，<, >)、可數(shù)集、不可數(shù)集、基數(shù)關(guān)系證明。要求熟練掌握集合的基本概念、集合的運算;熟練掌握函數(shù)、函數(shù)的運算及其證明;熟練掌握級數(shù)、累加;掌握基數(shù)比較和函數(shù)的關(guān)系、可數(shù)集。

3. 歸納和遞歸

數(shù)學(xué)歸納法原理、數(shù)學(xué)歸納法運用、強歸納法原理、強歸納法運用、良序性質(zhì)、遞歸定義函數(shù)、歸納定義法、遞歸定義的集合和結(jié)構(gòu)、結(jié)構(gòu)歸納法、結(jié)構(gòu)歸納法的運用、廣義歸納法、遞歸算法、遞歸算法正確性證明、遞歸和迭代。要求熟練掌握數(shù)學(xué)歸納法、強歸納法和結(jié)構(gòu)歸納法，能夠熟練運用歸納定義法;掌握遞歸和遞歸算法的基本概念，能夠較熟練編寫遞歸算法;了解遞歸算法正確性證明。

4. 關(guān)系

二元關(guān)系基本概念、關(guān)系與函數(shù)、二元關(guān)系的性質(zhì)(自反、對稱、反對稱、傳遞)及其證明、關(guān)系的運算、n-元關(guān)系基本概念、n-元關(guān)系的運算、關(guān)系與數(shù)據(jù)庫、關(guān)系的表示(關(guān)系矩陣、關(guān)系圖)、關(guān)系的閉包、等價關(guān)系、等價類、劃分、偏序、全序、良序歸納原理、哈斯圖、最大(小)元、極大(小)元、上(下)界、上(下)確界、格、拓撲排序。要求熟悉集合、關(guān)系和函數(shù)的關(guān)聯(lián)關(guān)系;掌握關(guān)系的性質(zhì)判定和運算;熟悉關(guān)系與關(guān)系數(shù)據(jù)庫的關(guān)系;掌握等價關(guān)系、序關(guān)系，能夠證明相關(guān)性質(zhì);了解格和拓撲排序。

5. 圖

圖的基本概念、圖模型、圖的基本術(shù)語和特殊類型圖、二部圖和匹配、圖的應(yīng)用、圖的運算、圖的表示、圖同構(gòu)、路徑和連通性、歐拉路徑和哈密頓路徑及其應(yīng)用、最短路徑算法、平面圖及其應(yīng)用、歐拉公式、庫拉托瓦斯基定理、圖的著色問題。要求熟悉圖的基本概念和術(shù)語;掌握最短路徑算法;熟悉路徑和連通性;較熟練掌握圖的性質(zhì)證明;較好掌握二部圖和平面圖。

6. 樹

樹的基本概念和術(shù)語、樹建模、樹的性質(zhì)及其證明、樹的應(yīng)用、二叉樹、樹的遍歷算法、樹的編碼、生成樹、最小生成樹、回溯。要求熟悉樹的基本概念;掌握樹的算法和性質(zhì)證明;能夠使用樹進行建模和應(yīng)用;掌握各種樹的遍歷算法;掌握回溯法。

7. 布爾代數(shù)

布爾函數(shù)、布爾表達式、布爾代數(shù)恒等式、對偶、布爾代數(shù)定義、范式展開、邏輯門、電路、電路極小化。要求掌握布爾表達式變換方法;熟悉布爾代數(shù)與電路的關(guān)聯(lián)關(guān)系;了解布爾代數(shù)。

三、考試形式

考試形式為閉卷、筆試，考試時間為1.5-2.0小時，滿分100分。

題型包括：計算題、證明題、分析題、推理題等。

四、參考書目

1.Discrete Mathematics and Its Applications (7th edition), Kenneth H. Rosen, ISBN:978-0-07-338309-5, McGraw-Hill, 2012.

2.《離散數(shù)學(xué)》，王兵山、張強、毛曉光主編，國防科技大學(xué)出版社，2001.