離散數學

目錄

緒論離散數學與電腦1

第一部分集合論

第1章集合7

1.1集合的概念與表示7

1.1.1集合的概念7

1.1.2集合的元素8

1.1.3集合的表示方法8

1.1.4集合之間的關系10

習題1.111

1.2集合的運算12

1.2.1交運算12

1.2.2並運算12

1.2.3補運算13

1.2.4差運算14

1.2.5對稱差運算14

習題1.215

1.3集合的劃分與覆蓋16

1.3.1集合的劃分16

1.3.2集合的覆蓋17

習題1.317

1.4容斥原理18

習題1.421

1.5集合的思維導圖22

1.6集合的算法思想23

1.6.1求任意一個集合的冪集23

1.6.2求任意兩個集合的交集、並集、差集23

1.7本章小結23〖1〗〖2〗離散數學目錄〖2〗〖2〗第2章關系24

2.1有序n元組24

習題2.125

2.2笛卡兒積25

2.2.1笛卡兒積的定義25

2.2.2笛卡兒積的性質27

習題2.229

2.3二元關系30

2.3.1二元關系的概念30

2.3.2二元關系的表示32

習題2.333

2.4關系的運算34

2.4.1關系的集合運算34

2.4.2關系的復合運算35

2.4.3關系的逆運算37

習題2.437

2.5關系的性質38

2.5.1自反性39

2.5.2反自反性40

2.5.3對稱性42

2.5.4反對稱性43

2.5.5傳遞性44

習題2.549

2.6關系的閉包50

2.6.1自反閉包r(R)50

2.6.2對稱閉包s(R)51

2.6.3傳遞閉包t(R)52

2.6.4閉包之間的關系54

習題2.655

2.7等價關系和等價類56

2.7.1等價關系56

2.7.2等價類57

習題2.760

2.8相容關系和相容類61

2.8.1相容關系61

2.8.2相容類62

習題2.864

2.9偏序關系64

2.9.1偏序關系的定義64

2.9.2哈斯圖及特殊元素65

2.9.3全序關系70

2.9.4良序關系71

2.9.5擬序關系71

習題2.971

2.10關系的思維導圖73

2.11關系的算法思想74

2.11.1求任意個元素的全排列74

2.11.2求笛卡兒積74

2.11.3判斷關系性質及類型算法74

2.11.4求等價類75

2.11.5求極大相容類75

2.11.6求關系的閉包75

2.12本章小結76

第3章映射77

3.1映射的基本概念77

習題3.179

3.2映射的性質80

3.2.1單射80

3.2.2滿射80

3.2.3雙射81

習題3.282

3.3映射的復合運算82

習題3.384

3.4映射的逆運算85

習題3.486

3.5映射的思維導圖87

3.6映射的算法思想87

3.6.1映射的判定87

3.6.2求滿射88

3.7本章小結88

第二部分數 理 邏 輯

第4章命題邏輯91

4.1命題91

習題4.193

4.2聯結詞94

4.2.1否定聯結詞瘙綈94

4.2.2合取聯結詞∧（與）95

4.2.3析取聯結詞∨（或）95

4.2.4不可兼析取聯結詞∨（異或）96

4.2.5條件聯結詞→97

4.2.6雙條件聯結詞98

4.2.7與非聯結詞↑98

4.2.8或非聯結詞↓98

4.2.9條件否定聯結詞n99

4.2.10聯結詞與集合運算之間的關系99

習題4.2101

4.3命題公式101

4.3.1命題公式的定義101

4.3.2命題公式的符號化102

4.3.3命題公式的解釋104

4.3.4命題公式的真值表105

4.3.5命題公式的類型106

習題4.3106

4.4命題公式的邏輯等值107

4.4.1命題公式邏輯等值的定義107

4.4.2命題公式基本的邏輯等值式108

4.4.3命題公式的等值演算110

4.4.4命題公式的對偶定理113

習題4.4113

4.5範式114

4.5.1析取範式與合取範式114

4.5.2主析取範式與主合取範式116

4.5.3主範式的應用122

習題4.5124

4.6命題公式的邏輯蘊涵125

4.6.1邏輯蘊涵的定義125

4.6.2蘊涵式的證明方法126

4.6.3基本的邏輯蘊涵式128

習題4.6129

4.7全功能聯結詞與極小聯結詞組129

習題4.7130

4.8命題邏輯推理131

4.8.1命題邏輯推理理論131

4.8.2推理規則131

4.8.3判斷有效結論的常用方法133

習題4.8137

4.9命題邏輯的思維導圖138

4.10命題邏輯的算法思想——求任意一個命題公式的真值表139

4.11本章小結140

第5章謂詞邏輯141

5.1謂詞邏輯的相關概念141

5.1.1個體詞與謂詞141

5.1.2量詞143

習題5.1144

5.2謂詞公式145

5.2.1謂詞公式的定義145

5.2.2謂詞公式的符號化146

5.2.3謂詞的約束與替換148

5.2.4謂詞公式的解釋151

5.2.5謂詞公式的類型152

習題5.2153

5.3謂詞公式的邏輯等值154

5.3.1謂詞公式邏輯等值的定義154

5.3.2謂詞公式基本的邏輯等值式155

習題5.3158

5.4謂詞公式的前束範式158

5.4.1謂詞公式前束範式的定義158

5.4.2謂詞公式前束範式的計算159

習題5.4160

5.5謂詞公式的邏輯蘊涵160

習題5.5163

5.6謂詞邏輯的推理164

5.6.1謂詞邏輯中的邏輯蘊涵式164

5.6.2謂詞邏輯的推理規則164

5.6.3謂詞邏輯的自然推理系統165

習題5.6168

5.7謂詞邏輯的思維導圖169

5.8本章小結170

第三部分圖論

第6章圖173

6.1圖的基本概念173

6.1.1圖174

6.1.2子圖176

6.1.3通路與迴路177

6.1.4圖的同構179

習題6.1180

6.2結點的度181

6.2.1結點的度的概念181

6.2.2握手定理及其推論181

習題6.2182

6.3圖的連通性183

6.3.1無向圖的連通性183

6.3.2有向圖的連通性186

習題6.3188

6.4圖的矩陣表示189

6.4.1鄰接矩陣189

6.4.2可達矩陣190

6.4.3關聯矩陣193

習題6.4195

6.5圖的應用196

6.5.1加權圖的最短通路196

6.5.2加權圖的關鍵路徑200

習題6.5202

6.6圖的思維導圖203

6.7圖的算法思想204

6.7.1圖的可達矩陣算法204

6.7.2有向圖的所有強分支算法204

6.7.3有向圖的所有單向分支算法204

6.7.4圖的所有割點算法205

6.7.5圖的所有割邊算法205

6.7.6發點到其他各點的所有最短通路算法206

6.7.7求兩點間最短通路的WarshallFloyd算法207

6.7.8圖的所有關鍵路徑算法207

6.8本章小結208

第7章歐拉圖與哈密爾頓圖209

7.1歐拉圖209

7.1.1歐拉圖的定義209

7.1.2歐拉圖的判定210

7.1.3歐拉圖的應用212

習題7.1215

7.2哈密爾頓圖216

7.2.1哈密爾頓圖的定義216

7.2.2哈密爾頓圖的判定217

7.2.3哈密爾頓圖的應用220

習題7.2221

7.3歐拉圖和哈密爾頓圖的思維導圖223

7.4歐拉圖和哈密爾頓圖的算法思想224

7.4.1求歐拉迴路的算法224

7.4.2判斷一個圖是否為哈密爾頓圖224

7.5本章小結225

第8章特殊圖226

8.1樹226

8.1.1無向樹226

8.1.2生成樹與最小生成樹228

8.1.3有向樹與根樹232

8.1.4k叉樹與有序樹233

習題8.1238

8.2二部圖239

8.2.1二部圖的概念239

8.2.2二部圖的匹配241

習題8.2243

8.3平面圖244

8.3.1平面圖的概念244

8.3.2歐拉公式245

8.3.3平面圖的判定247

8.3.4平面圖的著色248

習題8.3253

8.4特殊圖的思維導圖254

8.5特殊圖的算法思想255

8.5.1求Huffman樹255

8.5.2求無（有）向圖的生成樹的算法256

8.5.3求最小生成樹的兩種算法: Kruskal算法、Prim算法256

8.5.4廣度優先搜索算法257

8.5.5深度優先搜索算法257

8.5.6二叉樹的遍歷258

8.5.7二部圖的所有完備匹配算法259

8.5.8圖的著色算法259

8.6本章小結259

第四部分代 數 系 統

第9章代數結構263

9.1代數系統的定義263

9.1.1代數運算263

9.1.2代數系統266

習題9.1267

9.2代數系統的性質267

9.2.1交換律267

9.2.2結合律268

9.2.3分配律268

9.2.4吸收律268

9.2.5冪等律269

9.2.6單位元（幺元）269

9.2.7零元270

9.2.8逆元270

9.2.9消去律272

習題9.2274

9.3代數系統的同態與同構275

習題9.3278

9.4半群與獨異點279

9.4.1半群279

9.4.2獨異點280

習題9.4282

9.5群283

9.5.1群的定義283

9.5.2群的性質285

習題9.5286

9.6子群287

9.6.1子群的定義287

9.6.2子群的判定287

習題9.6289

9.7特殊的群289

9.7.1阿貝爾群289

9.7.2循環群291

9.7.3置換群293

習題9.7296

9.8群的同態與同構297

習題9.8299

9.9代數系統的思維導圖300

9.10代數系統的算法思想301

9.11本章小結301

第10章環與域302

10.1環302

10.1.1環的概念302

10.1.2子環與理想305

10.1.3環的同態與同構306

習題10.1307

10.2域307

10.2.1域的概念307

10.2.2有限域309

10.2.3域的同態與同構309

習題10.2310

10.3環與域的思維導圖311

10.4本章小結312

第11章格與布爾代數313

11.1格的定義和性質313

11.1.1格的定義313

11.1.2格的對偶原理314

11.1.3格的性質315

習題11.1316

11.2子格與格同態317

11.2.1子格317

11.2.2格同態與格同構317

習題11.2318

11.3幾種特殊的格319

11.3.1分配格319

11.3.2模格321

11.3.3有界格321

11.3.4有補格322

習題11.3323

11.4布爾代數324

11.4.1布爾代數的定義324

11.4.2布爾代數的性質325

11.4.3布爾代數的同態與同構326

習題11.4328

11.5格與布爾代數的思維導圖329

11.6本章小結330

附錄1符號索引331

附錄2相關數學概念336