離散數學基礎教程

目 錄

第1章集合及其運算1

1.1集合1

1.1.1集合的概念1

1.1.2集合的表示2

1.1.3集合的分類3

1.2子集、集合的相等4

1.2.1子集4

1.2.2集合的相等5

1.2.3冪集6

1.3集合的基本運算8

1.3.1並運算8

1.3.2交運算11

1.3.3差運算13

1.3.4對稱差運算14

1.3.5求補運算、德·摩根公式15

1.4笛卡兒乘積運算17

1.4.1序對17

1.4.2笛卡兒乘積的定義18

1.4.3n元組18

1.5有窮集合的基數19

1.5.1映射20

1.5.2有窮集合的基數的定義20

1.5.3計數法則20

1.5.4容斥原理21

1.6邏輯與證明24

1.6.1數理邏輯簡介24

1.6.2公理系統25

1.6.3命題邏輯26

1.6.4謂詞邏輯27

1.6.5推理與證明29

1.7習題選解32

1.7.1建立語言的數學模型32

1.7.2證明集合相等34

1.7.3建立數學模型35

1.8本章小結37

習題38第2章映射40

2.1函數的一般概念——映射40

2.1.1函數概念的回顧40

2.1.2映射的定義41

2.1.3有窮集合間的映射42

2.2抽屜原理44

2.2.1抽屜原理的形式44

2.2.2抽屜原理的應用44

2.3映射的一般性質46

2.3.1導出映射46

2.3.2映射的一般性質及其證明46

2.4映射的合成48

2.4.1映射的合成的定義49

2.4.2合成運算的性質49

2.5逆映射50

2.5.1逆映射的存在條件及其唯一性51

2.5.2左(右)可逆映射51

2.6置換52

2.6.1置換的定義52

2.6.2置換的乘積53

2.6.3循環置換與對換53

2.6.4置換的循環置換分解54

2.6.5奇置換和偶置換55

2.7序列、矩陣與運算56

2.7.1序列56

2.7.2矩陣56

2.7.3運算57

2.7.4代數結構58

2.8集合的特征函數59

2.8.1特征函數59

2.8.2集合在計算機中的存儲60

2.9習題選解61

2.9.1再論集合相等61

2.9.2利用映射建立數學模型62

2.9.3抽屜原理的應用64

2.9.4映射的性質67

2.9.5置換69

2.10本章小結69

習題69第3章關系71

3.1關系的概念71

3.1.1關系的等價定義71

3.1.2n元關系與關系數據庫73

3.2幾種特殊的二元關系74

3.2.1自反關系、反自反關系74

3.2.2對稱關系、反對稱關系74

3.2.3傳遞關系75

3.2.4相容關系、關系的計數75

3.3關系的運算76

3.3.1關系的集合運算76

3.3.2關系的合成運算77

3.3.3關系合成運算的性質77

3.4二元關系的傳遞閉包79

3.4.1二元關系的傳遞閉包、自反傳遞閉包79

3.4.2傳遞閉包的性質79

3.4.3迷宮問題81

3.5關系矩陣與關系圖81

3.5.1關系矩陣81

3.5.2(0,1)矩陣的運算82

3.5.3Warshall算法82

3.5.4關系的圖83

3.6等價關系與集合的劃分83

3.6.1等價關系83

3.6.2等價類84

3.6.3集合的劃分85

3.6.4等價關系與集合劃分互相確定86

3.6.5從等價關系看線性代數87

3.6.6等價閉包與等價關系的合成87

3.7映射按等價關系分解88

3.7.1由映射確定的等價關系與集合劃分88

3.7.2商集、自然映射88

3.7.3映射按等價關系分解89

3.7.4與映射相容的等價關系89

3.8偏序關系與偏序集90

3.8.1偏序關系與偏序集的定義90

3.8.2Hasse圖91

3.8.3上(下)界、最大(小)元素、上(下)確界91

3.8.4鏈與反鏈93

3.9習題選解95

3.9.1利用關系建立數學模型95

3.9.2二元關系的概念97

3.9.3二元關系的閉包98

3.9.4二元關系與映射99

3.9.5等價關系和偏序關系101

3.10本章小結102

習題102第4章無窮集合及其基數104

4.1可數集104

4.1.1關於無窮104

4.1.2可數集的定義105

4.1.3可數集的性質105

4.1.4無窮集合107

4.2連續統集108

4.2.1康托對角線法108

4.2.2連續統109

4.2.3連續統的性質109

4.2.4例題111

4.3基數及其比較112

4.3.1基數的定義112

4.3.2基數的比較113

4.3.3連續統假設113

4.3.4康托定理113

4.4康托伯恩斯坦定理114

4.4.1問題114

4.4.2康托伯恩斯坦定理的定義114

4.4.3選擇公理116

4.4.4基數的算術運算116

4.5公理化集合論117

4.5.1直覺集合論中一些著名的悖論117

4.5.2一些非數學上的悖論118

4.5.3公理集合論簡介118

4.6圖靈機、可計算性與計算復雜性120

4.6.1圖靈機產生的背景120

4.6.2圖靈其人121

4.6.3圖靈機的直觀模型122

4.6.4圖靈機的形式定義123

4.6.5可計算性124

4.6.6計算復雜性126

4.7習題選解127

4.7.1可數集127

4.7.2對角線法128

4.7.3康托伯恩斯坦定理的應用129

4.7.4連續統130

4.8本章小結130

習題131第5章邏輯演算132

5.1等值演算132

5.1.1指派與解釋132

5.1.2邏輯等價135

5.1.3對偶式和內否式137

5.1.4聯結詞完備集138

5.2範式139

5.2.1析取範式與合取範式139

5.2.2主範式140

5.2.3前束範式142

5.3命題演算形式系統PC143

5.3.1PC的組成143

5.3.2PC的基本定理143

5.3.3PC的性質定理152

5.4謂詞演算形式系統FC153

5.4.1FC的組成153

5.4.2FC的基本定理153

5.4.3FC的性質定理157

5.5習題選解157

5.6本章小結161

習題161

第6章圖163

6.1利用圖模型解決問題163

6.1.1圖論史上的標誌性問題164

6.1.2遊戲類問題168

6.1.3應用類問題169

6.2基本概念169

6.2.1圖的定義169

6.2.2子圖172

6.2.3度173

6.2.4正則圖173

6.2.5圖的同構174

6.3路、圈與連通圖175

6.3.1路與圈176

6.3.2圖的連通性176

6.3.3連通圖的判定177

6.3.4有圈圖的判定179

6.4補圖與偶圖180

6.4.1補圖180

6.4.2偶圖182

6.4.3極值圖論182

6.5歐拉圖185

6.5.1歐拉圖的定義185

6.5.2歐拉定理185

6.6哈密頓圖186

6.6.1哈密頓圖及背景186

6.6.2哈密頓圖的判定186

6.6.3哈密頓圖的幾個充分條件187

6.6.4Kp的哈密頓圈分解188

6.6.5比賽圖189

6.7圖的表示190

6.7.1鄰接矩陣190

6.7.2可達矩陣192

6.7.3鄰接表192

6.7.4關聯矩陣192

6.8帶權圖194

6.8.1最短路徑問題194

6.8.2巡回售貨員(貨郎擔或旅行商)問題196

6.8.3中國郵路問題196

6.9習題選解196

6.9.1連通圖、圈196

6.9.2同構198

6.9.3哈密頓圖199

6.9.4最長路200

6.10本章小結200

習題200第7章樹和割集202

7.1樹202

7.1.1樹和森林202

7.1.2樹的性質203

7.1.3樹的中心204

7.2生成樹205

7.2.1生成樹的定義205

7.2.2生成樹計數206

7.2.3最小生成樹207

7.3有根樹與有序樹210

7.3.1有根樹210

7.3.2有序樹212

7.4割點、橋和割集213

7.4.1割點和橋213

7.4.2割點和橋的特征性質213

7.4.3割集215

7.5習題選解216

7.6本章小結218

習題218第8章連通度、匹配和覆蓋219

8.1連通度219

8.1.1連通度的定義219

8.1.2κ(G)、λ(G)、δ(G)的關系220

8.1.3n連通222

8.2門格爾定理223

8.2.1門格爾定理及推論223

8.2.2網絡流224

8.2.3割集226

8.2.4求最大流227

8.3匹配229

8.3.1匹配問題及模型230

8.3.2獨立集230

8.3.3相異代表系232

8.3.4霍爾定理233

8.3.5求最大匹配235

8.4覆蓋與支配集236

8.4.1覆蓋237

8.4.2支配集237

8.5習題選解239

8.5.1建立網絡流模型239

8.5.2連通度240

8.5.3匹配與覆蓋241

8.5.4門格爾定理242

8.6本章小結242

習題243第9章平面圖與圖的著色244

9.1平面圖及歐拉公式244

9.1.1背景244

9.1.2平面圖的定義244

9.1.3平面圖的歐拉公式245

9.1.4K5、K3,3不可平面246

9.2非哈密頓平面圖247

9.3庫拉托夫斯基定理249

9.4圖的頂點著色250

9.4.1圖的頂點著色的概念250

9.4.2色數的上下界251

9.4.3平面圖的四色定理252

9.4.4平面圖的五色定理254

9.5圖的邊著色255

9.5.1邊著色及邊色數255

9.5.2幾個主要結果255

9.6習題選解256

9.7本章小結261

習題261第10章代數系統264

10.1半群和幺半群265

10.1.1半群和幺半群的概念265

10.1.2子半群、子幺半群、理想266

10.1.3同構和同態268

10.2群272

10.2.1群的概念272

10.2.2子群、生成子群273

10.2.3變換群、同構274

10.2.4循環群275

10.2.5子群的陪集275

10.2.6正規子群、商群277

10.2.7同態基本定理279

10.2.8直積281

10.3環和域283

10.3.1環和域的概念283

10.3.2環和域的基本性質284

10.4格與布爾代數286

10.4.1格286

10.4.2布爾代數288

10.5習題選解290

10.6本章小結295

習題295參考文獻296