離散數學

遵循 ^[1]  適應性、科學性、系統性、發展性等基本原則，進行內容組織與佈局。力求選材精練、闡述準確、行文優美、條理清晰、核心突出。本教材不僅是教和學的藍本，更是創新教學內容、改革教學方法、主導教學方向的體現，是人才培養過程中傳授知識、訓練技能和發展智力的重要工具之一。 （1）體系結構，靈活合理全書採用模塊化結構分為五篇，各篇信息量大致均衡，且各篇之間既可相互獨立、自成體系，又可彼此聯繫、融會貫通。便於教師根據不同專業、不同學時、不同基礎的學生進行選講。方便學生很快入門，同時又為基礎好的學生設置足夠的拓展和提升空間。 （2）內容組織，深入淺出由命題邏輯的擴展潛移默化地導出謂詞邏輯；從一種特殊集合引出關係，又從一種特殊關係導出函數，再從一種特殊函數引出運算；從一種特殊偏序集導出格等等。在討論集合時，將其限於合適定義範圍內，採用經典集合論的原始描述，既不會導致悖論，且所得結論和公理化集合論中的結論完全一致，又避免展示公理化集合論的過於複雜性。在討論計數問題時，從基本的計數技術向高級計數技術慢慢推進，且反覆嘗試用不同的方法解同一個問題，從中展示不同計數技術解題的一般思路和方法，使學生不僅懂得了其深奧的道理，而且掌握了普遍的方法，對所學知識能廣泛遷移，隨機通達。大大降低了學習難度，節約了教學學時。 （3）重視學生能力培養，授人以漁強調命題翻譯和謂詞翻譯的技巧，強調邏輯推理，反覆訓練學生的形式思維和邏輯思維能力，是本書的一大亮點。巧妙導出關係是客觀事物間聯繫的一種數學抽象，而圖是客觀事物間聯繫的另一種數學抽象；強調不同代數結構間的相互聯繫；展示不同計數技術的數學模型，不斷訓練學生的抽象思維能力，是本書的另一特色。 （4）理論與應用有機結合由n元關係與關係數據庫的淵源，由等價關係的等價類來求解許多應用問題，將哈斯圖作為一種最基本的操作系統模型等角度，延伸關係的廣泛應用；用較大的篇幅闡述主合取範式與主析取範式、羣、環、域、獨立集、匹配、着色、最短路問題、歐拉圖、哈密頓圖、樹、平面圖等的廣泛應用，且這些應用都真真切切地來自社會實踐，使學生自然而然地理解離散數學與其它學科之間千絲萬縷的聯繫，促進學生在充分體會理論與應用的結合點時，培養自己的探索興趣與應用能力，培養以後研究中運用離散數學理論知識的敏鋭性。 （6）廣泛的課堂教學實踐不是為編教材而編教材，更不是臨時拼湊，而是十幾年課堂教學實踐所得。每個概念都闡述清晰、每個定理都證明透徹、每道例題和習題都精心設計、且書末附有詳細習題解答。同時，本教材還及時補充了哈斯圖的生成算法、超立方體的Laplace譜、生成排列的翻轉算法、生成組合的插入算法等新內容。 ^[2] 

前言

符號註釋

第1篇數 理 邏 輯

第1章命題邏輯2

11命題2

12命題聯結詞4

13命題公式及其真值表7

14邏輯等價10

15藴含與對偶14

16聯結詞的全功能集合17

17命題公式的範式21

18命題邏輯的推理理論30

第2章謂詞邏輯35

21個體與謂詞35

22命題函數與量詞36

23謂詞公式與約束變元39

24謂詞演算的等價式與藴含式44

25謂詞演算的推理理論49

第2篇集合論

第3章集合與關係57

31集合的概念57

32集合的運算59

33序偶與笛卡兒積65

34關係及其表示68

35關係的性質71

36等價關係與劃分75

37相容關係與覆蓋80

38偏序關係83

39複合關係與逆關係89

310關係的閉包運算97

第4章函數105

41函數的基本概念105

42複合函數與逆函數108

43置換112

44可數集與不可數集120

第3篇抽 象 代 數

第5章羣128

51運算及其性質128

52幺元、零元和逆元131

53羣的基本概念135

54子羣140

55子羣的陪集143

56同態與同構149

57阿貝爾羣與循環羣155

58置換羣161

第6章環與格168

61環168

62理想與特徵174

63格179

64分配格與有補格185

65布爾代數190

第4篇圖論

第7章圖的基本概念197

71圖的概念197

72路與連通205

73圖的矩陣表示212

74最短路問題218

75匹配225

第8章樹和平面圖236

81歐拉（Euler）圖與哈密頓（Hamilton）

圖236

82樹243

83生成樹249

84平面圖257

85圖的着色263

86超立方體的拉普拉斯（Laplace）譜268

第5篇組 合 數 學

第9章基本計數問題274

91基本計數原則274

92重集的計數280

93排列的生成算法285

94組合的生成算法293

95二項式係數299

96鴿巢原理306

第10章高級計數問題310

101生成函數310

102生成函數的應用316

103指數生成函數325

104遞歸的建立333

105常係數線性齊次遞推關係339

106常係數線性非齊次遞推關係344

107斐波那契（Fibonacci）數與卡特蘭

（Catalan）數347

108差分序列和斯特林（Stirling）數353

109容斥原理364

1010有禁區的排列與車多項式371

部分習題解答376

參考文獻446