離散數學

本書由六部分組成，首先將離散數學的體系結構分為以下五個主要部分：數理邏輯、集合與關係、數論與組合論、圖論、代數結構，第六部分介紹離散數學在計算機科學中的一些典型應用。 本書在每章後面配備了相當數量的難易程度不同的練習題，並在附錄中給出了幾套模擬試題，供讀者進行自測。 本書內容豐富，條理清晰，層次分明，邏輯性強，闡述深入淺出，適合作為高等院校計算機和軟件工程專業及相關專業離散數學課程的本科生教材，也可供計算機科學工作者和科技人員閲讀與參考。

“離散數學”是現代數學的一個重要分支，也是計算機科學與技術、電子信息技術、生物技術等專業的理論基礎。封底無防偽標均為盜版 版權所有，侵權必究 本書法律顧問　北京市展達律師事務所 ^[1] 

前言

第一部分　數理邏輯

第1章　命題邏輯3

1.1　命題與邏輯聯結詞3

1.2　命題公式及其賦值7

1.3　命題公式的等價9

1.4　聯結詞的完備集12

1.5　命題公式的範式表示13

1.6　命題公式的藴涵19

1.7　命題邏輯的推理方法21

習題一23

第2章　一階謂詞邏輯27

2.1　量詞化邏輯27

2.2　謂詞公式及其賦值30

2.3　謂詞公式的等價與範式表示33

2.4　謂詞公式的藴涵37

2.5　謂詞邏輯的推理方法39

習題二42

第二部分　集合與關係

第3章　集合代數47

3.1　集合的基本概念47

3.2　集合的運算49

3.3　冪集和笛卡兒集51

習題三53

第4章　二元關係55

4.1　二元關係及其表示55

4.2　關係的性質57

4.3　關係的運算59

4.4　關係的閉包61

習題四65

第5章　特殊關係67

5.1　等價關係67

5.2　偏序關係69

5.3　全序集與良序集71

習題五73

第6章　函數75

6.1　函數的定義與性質75

6.2　單射、滿射和雙射77

6.3　函數的複合與逆函數78

6.4　集合的基數、可數集和不可數集…81

習題六85

第三部分　數論與組合論

第7章　初等數論89

7.1　整數集合89

7.2　商和餘數90

7.3　整除和素因子分解92

7.4　最大公因子93

7.5　數學歸納法95

習題七97

第8章　基本計數方法99

8.1　排列計數99

8.2　組合計數101

8.3　組合恆等式104

8.4　容斥原理106

8.5　鴿巢原理108

習題八110

第9章　生成函數和遞推關係112

9.1　序列與生成函數112

9.2　組合問題的生成函數115

9.3　遞推關係式及其解118

9.4　遞推關係式的生成函數求解123

習題九126

第四部分　圖論

第10章　圖的基本概念131

10.1　圖131

10.2　通路與迴路136

10.3　圖的連通性138

10.4　圖的矩陣表示141

習題十146

第11章　樹及其應用148

11.1　無向樹及其性質148

11.2　生成樹149

11.3　根樹及其應用151

習題十一155

第12章　平面圖及其應用157

12.1　平面圖的基本概念157

12.2　歐拉公式158

12.3　平面圖的判斷159

12.4　平面圖的對偶圖160

12.5　平面的點着色與圖的着色161

習題十二163

第13章　歐拉圖與哈密頓圖164

13.1　歐拉圖與中國郵遞員問題164

13.2　哈密頓圖與推銷商問題168

習題十三173

第五部分　代數結構

第14章　代數系統177

14.1　二元運算及其性質177

14.2　代數系統的定義與特異元178

習題十四179

第15章　半羣與羣181

15.1　半羣181

15.2　羣和子羣183

15.3　交換羣和循環羣186

15.4　陪集與拉格朗日定理187

15.5　正規子羣與商羣189

15.6　羣的同態與同構190

習題十五193

第16章　環與域195

16.1　環的定義及其性質195

16.2　整環與域197

習題十六198

第17章　格與布爾代數199

17.1　格的定義與性質199

17.2　子格與格同態201

17.3　分配格與有補格204

17.4　布爾代數206

17.5　布爾表達式209

習題十七214

第六部分　應用

第18章　典型應用218

18.1　數字邏輯電路設計218

18.2　形式語言220

18.3　有限狀態自動機229

18.4　關係數據庫管理系統235

18.5　網絡236

18.6　羣碼242

習題十八244

附錄　離散數學模擬試題248