離散數學

“離散數學”不僅是現代數學的一個重要分支，更是計算機類專業課程體系中極其重要的專業基礎課。它以研究離散量的結構及其相互關係為目標，充分描述了計算機科學的離散性特點。 ^[1] 

該課程是“數據結構”“操作系統”“計算機網絡”“算法設計與分析”“軟件工程”“人工智能”等計算機本科階段核心課程的基礎，也是“組合數學”“遺傳算法”“數據挖掘”等相關專業碩士研究生階段課程的基礎，意義不言而喻。本書共分12章，涉及離散數學基礎、數理邏輯、集合論、關係和函數、圖論、代數系統及其羣、環、域、布爾代數等內容，最後就書中涉及的人和事件等相關知識及其歷史背景做了簡要介紹，不僅可讀性強，也使讀者對離散數學的發展思想及其衍化脈落有了更進一步的瞭解。本書可作為普通高等院校計算機等相關專業的本科生教材，也可作為信息類相關專業本科生、研究生的參考資料。 ^[1] 

第1章離散數學基礎

1.1算法

1.1.1算法的定義

1.1.2算法的基本特徵

1.1.3算法設計方法

1.1.4算法表示

1.1.5算法的複雜度分析

1.2可計算性問題*

1.3模和同餘

1.4遞歸 ^[1] 

1.5密碼學初步*

1.6計數

小結

習題

第2章命題邏輯

2.1命題與聯結詞

2.1.1命題及其表示

2.1.2聯結詞

2.1.3最小功能完備集*

2.2命題公式與重言式

2.2.1命題公式

2.2.2指派與真值表

2.2.3重言式

2.3範式

2.3.1對偶原理

2.3.2範式

2.3.3主析取範式

2.3.4主合取範式

2.4基於命題的推理

2.4.1推理理論

2.4.2CP規則

2.4.3歸謬法

小結

習題

第3章謂詞邏輯

3.1謂詞

3.2量詞

3.2.1全稱量詞

3.2.2存在量詞

3.2.3量詞分析

3.3謂詞公式

3.4謂詞演算

3.5謂詞演算中的推理規則

3.5.1推理規則

3.5.2含有量詞的永真式

3.6三元謂詞向二元謂詞的轉換*

3.7基於謂詞的知識表示*

3.8基於謂詞演算的程序正確性證明*

小結

習題

第4章集合論

4.1集合的基本概念

4.1.1集合及其表示

4.1.2子集

4.1.3基數

4.1.4冪集

4.1.5悖論*

4.2集合的運算

4.2.1集合的並與交

4.2.2集合的差與補

4.2.3環和與環積*

4.2.4集合的笛卡兒積

4.3集合運算定律

4.4集合計數

4.5可列集與無限集*

4.6集合的計算機表示*

4.7自然數集合與數學歸納法*

小結

習題

第5章關係

5.1關係的基本概念

5.2二元關係

5.3二元關係的表示

5.3.1集合表示法

5.3.2關係圖

5.3.3關係矩陣

5.3.4表格法

5.4關係的基本性質

5.4.1自反性

5.4.2反自反性

5.4.3對稱性

5.4.4反對稱性

5.4.5傳遞性

5.5等價關係與集合劃分

5.5.1等價關係

5.5.2等價類

5.5.3集合的劃分

5.6相容關係與集合覆蓋

5.6.1相容關係

5.6.2相容類

5.6.3覆蓋

5.7偏序關係與哈斯圖

5.7.1哈斯圖與偏序集

5.7.2偏序集中的特殊元素

5.8關係運算

5.8.1複合關係和逆關係

5.8.2逆關係

5.8.3限制與閉包

小結

習題

第6章函數

6.1函數的定義

6.2特殊函數

6.3函數的運算

6.3.1函數合成

6.3.2逆函數

小結

習題

第7章圖論

7.1圖的基本概念

7.1.1圖的基本概念

7.1.2度

7.1.3正則圖與完全圖

7.1.4子圖與補圖

7.1.5賦權圖

7.1.6同構圖

7.2圖的存儲

7.2.1鄰接矩陣

7.2.2邊表示法

7.2.3鄰接編目法

7.2.4多重鏈表

7.2.5十字鏈表

7.3連通與迴路

7.3.1可達與連通

7.3.2歐拉圖

7.3.3漢密爾頓圖

7.4平面圖與對偶圖

7.4.1平面圖

7.4.2對偶圖

7.5二部圖與匹配

7.6網絡規劃*

7.6.1規劃圖

7.6.2結構與優化

7.6.3規劃圖的繪製

7.6.4規劃圖參數

7.6.5規劃圖的優化分析

7.7最短路徑模型

7.8圖的着色*

7.9自補圖*

小結

習題

第8章樹

8.1無向樹

8.2生成樹

8.3有向樹

8.4二叉樹

8.5二叉樹的遍歷

8.6代數表達式的波蘭表示*

8.7前綴碼與哈夫曼樹

8.8決策樹*

8.8.1決策樹實例分析

8.8.2不確定事件的決策分析

8.8.3逆推技術

8.8.4臨界值分析

8.9樹的存儲

小結

習題

第9章代數結構

9.1代數運算

9.1.1代數運算的基本概念

9.1.2代數運算的表示

9.1.3代數運算的性質

9.2代數系統

9.2.1代數系統的基本概念和表示

9.2.2代數系統中的特殊元素

9.3同構

小結

習題

第10章羣與環*

10.1羣

10.1.1半羣

10.1.2羣

10.1.3子羣

10.1.4元素的階數

10.1.5若干特殊羣

10.2環和域

10.2.1環

10.2.2域

小結

習題

第11章格與布爾代數

11.1格*

11.2布爾函數*

11.2.1布爾函數運算

11.2.2布爾表達式

11.2.3布爾代數中的恆等式

11.2.4對偶性

11.2.5布爾代數的研究意義

11.3布爾函數的表示和構造*

11.3.1積之和展開式

11.3.2函數的完備性

11.4邏輯門電路設計

11.5卡諾圖

11.5.1卡諾圖概述

11.5.2三變元卡諾圖

11.5.3四變元卡諾圖

11.5.4奎因·莫可拉斯基方法

小結

習題

第12章附註*

12.1國外人物簡介

12.1.1歐幾里得

12.1.2斐波那契

12.1.3笛卡兒

12.1.4費馬

12.1.5歐拉

12.1.6高斯

12.1.7巴貝奇

12.1.8漢密頓

12.1.9黎曼

12.1.10康托爾

12.1.11希爾伯特

12.1.12羅素

12.1.13圖靈

12.1.14迪卡斯特拉

12.1.15Ike Nassi

12.1.16哈夫曼

12.1.17劉維爾

12.1.18香農

12.1.19泊松

12.1.20阿貝爾

12.1.21拉格朗日

12.1.22伽羅華

12.1.23卡諾

12.2國內人物簡介

12.2.1華羅庚

12.2.2閔嗣鶴

12.2.3柯召

12.2.4王元

12.2.5陳景潤

12.2.6潘承洞

12.2.7管梅谷

12.3名詞解釋

12.3.1圖靈機

12.3.2圖靈試驗

12.3.3圖靈獎

12.3.4希爾伯特的23個問題

12.3.5哈斯圖

參考文獻 ^[1]