離散數學（第4版）(2022年清華大學出版社出版的圖書)

《離散數學（第4版）》是清華大學出版社於2022年出版的圖書，作者是屈婉玲、劉田、耿素雲、張立昂

基本介紹

• 中文名：離散數學（第4版）
• 作者：屈婉玲、劉田、耿素雲、張立昂
• 出版時間：2022年9月1日
• 出版社：清華大學出版社
• ISBN：9787302613961
• 定價：66 元

內容簡介

《離散數學（第4版）》參照美國ACM和IEEE CS**推出的Computing Curricula，根據教育部高等學校計算機科學與技術教學指導委員會**編制的“高等學校計算機科學與技術專業規範”中關於離散數學的知識結構和體系撰寫. 全書共14章，內容包含證明技巧、數理邏輯、集合與關係、函式、組合計數、圖和樹、初等數論、離散機率、代數系統等. 體系嚴謹，文字精練，內容翔實，例題豐富，注重與計算機科學技術的實際問題相結合，並選配了大量難度適當的習題，適合教學. 另外，本書有配套的習題解答與學習指導等教學輔導用書，以及用於課堂教學的PPT演示文稿和線上數字資源等，以滿足教學需要. 本書適合作為高等學校計算機及相關專業本科生“離散數學”課程的教材，也可以作為對離散數學感興趣的人員的入門參考書.

圖書目錄

目錄CONTENTS

第1章數學語言與證明方法1

1.1常用的數學符號1

1.1.1集合符號1

1.1.2運算符號2

1.1.3邏輯符號2

1.2集合及其運算3

1.2.1集合及其表示法3

1.2.2集合之間的包含與相等4

1.2.3集合的冪集5

1.2.4集合的運算6

1.2.5基本集合恆等式及其套用8

1.3證明方法概述11

1.3.1直接證明法和歸謬法12

1.3.2分情況證明法和構造性證明法13

1.3.3數學歸納法14

1.4遞歸定義16

習題17

第2章命題邏輯22

2.1命題邏輯基本概念22

2.1.1命題與聯結詞22

2.1.2命題公式及其分類28

2.2命題邏輯等值演算33

2.2.1等值式與等值演算33

2.2.2聯結詞完備集37

2.3範式39

2.3.1析取範式與合取範式39

2.3.2主析取範式與主合取範式42

2.4推理49

2.4.1推理的形式結構49

2.4.2推理的證明51

2.4.3歸結證明法57

2.4.4對證明方法的補充說明60

習題60

目錄離散數學（第4版）第3章一階邏輯66

3.1一階邏輯基本概念66

3.1.1命題邏輯的局限性66

3.1.2個體詞、謂詞與量詞66

3.1.3一階邏輯命題符號化68

3.1.4一階邏輯公式與分類71

3.2一階邏輯等值演算76

3.2.1一階邏輯等值式與置換規則76

3.2.2一階邏輯前束範式79

習題81

第4章關係86

4.1關係的定義及其表示86

4.1.1有序對與笛卡兒積86

4.1.2二元關係的定義87

4.1.3二元關係的表示89

4.2關係的運算90

4.2.1關係的基本運算 90

4.2.2關係的冪運算93

4.3關係的性質96

4.3.1關係性質的定義和判別96

4.3.2關係的閉包100

4.4等價關係與偏序關係104

4.4.1等價關係104

4.4.2等價類和商集104

4.4.3集合的劃分106

4.4.4偏序關係107

4.4.5偏序集與哈斯圖 108

習題112

第5章函式117

5.1函式的定義及其性質117

5.1.1函式的定義117

5.1.2函式的像與完全原像 119

5.1.3函式的性質 120

5.2函式的複合與反函式123

5.2.1函式的複合123

5.2.2反函式125

習題129

第6章圖133

6.1圖的基本概念133

6.1.1無向圖與有向圖133

6.1.2頂點的度數與握手定理135

6.1.3簡單圖、完全圖、正則圖、圈圖、輪圖、方體圖137

6.1.4子圖、補圖139

6.1.5圖的同構140

6.2圖的連通性142

6.2.1通路與迴路142

6.2.2無向圖的連通性與連通度142

6.2.3有向圖的連通性及其分類145

6.3圖的矩陣表示145

6.3.1無向圖的關聯矩陣145

6.3.2有向無環圖的關聯矩陣146

6.3.3有向圖的鄰接矩陣147

6.3.4有向圖的可達矩陣148

6.4幾種特殊的圖150

6.4.1二部圖150

6.4.2歐拉圖153

6.4.3哈密頓圖154

6.4.4平面圖158

習題167

第7章樹及其套用174

7.1無向樹174

7.1.1無向樹的定義及其性質174

7.1.2生成樹177

7.2根樹及其套用178

7.2.1根樹及其分類178

7.2.2最優樹與哈夫曼算法179

7.2.3最佳前綴碼180

7.2.4根樹的週遊及其套用182

習題183

第8章組合計數基礎186

8.1基本計數規則187

8.1.1加法法則187

8.1.2乘法法則187

8.1.3分類處理與分步處理188

8.2排列與組合188

8.2.1集合的排列與組合189

8.2.2多重集的排列與組合192

8.3二項式定理與組合恆等式194

8.3.1二項式定理194

8.3.2組合恆等式195

8.3.3非降路徑問題200

8.4多項式定理與多項式係數202

8.4.1多項式定理202

8.4.2多項式係數203

習題204

第9章容斥原理207

9.1容斥原理及其套用207

9.1.1容斥原理的基本形式207

9.1.2容斥原理的套用208

9.2對稱篩公式及其套用211

9.2.1對稱篩公式211

9.2.2棋盤多項式與有限制條件的排列213

習題216

第10章遞推方程與生成函式218

10.1遞推方程及其套用218

10.1.1遞推方程的定義及實例218

10.1.2常係數線性齊次遞推方程的求解220

10.1.3常係數線性非齊次遞推方程的求解223

10.1.4遞推方程的其他解法225

10.1.5遞推方程與遞歸算法229

10.2生成函式及其套用234

10.2.1牛頓二項式定理與牛頓二項式係數234

10.2.2生成函式的定義及其性質235

10.2.3生成函式的套用237

10.3指數生成函式及其套用242

10.4Catalan數與Stirling數244

習題249

第11章初等數論252

11.1素數252

11.2最大公約數與最低公倍數255

11.3同餘258

11.4一次同餘方程與中國剩餘定理260

11.4.1一次同餘方程260

11.4.2中國剩餘定理262

11.4.3大整數算術運算263

11.5歐拉定理和費馬小定理264

習題265

第12章離散機率269

12.1隨機事件與機率、事件的運算269

12.1.1隨機事件與機率269

12.1.2事件的運算271

12.2條件機率與獨立性272

12.2.1條件機率272

12.2.2獨立性274

12.2.3伯努利概型與二項機率公式274

12.3離散型隨機變數275

12.3.1離散型隨機變數及其分布律275

12.3.2常用分布276

12.3.3數學期望278

12.3.4方差279

12.4機率母函式281

習題283

第13章初等數論和離散機率的套用287

13.1密碼學287

13.1.1凱撒密碼287

13.1.2RSA公鑰密碼288

13.2產生偽隨機數的方法290

13.2.1產生均勻偽隨機數的方法290

13.2.2產生離散型偽隨機數的方法291

13.3算法的平均複雜度分析293

13.3.1排序算法293

13.3.2散列表的檢索和插入296

13.4隨機算法299

13.4.1隨機快速排序算法299

13.4.2多項式恆零測試300

13.4.3素數測試302

13.4.4蒙特卡羅法和拉斯維加斯法303

習題304

第14章代數系統307

14.1二元運算及其性質307

14.1.1二元運算與一元運算的定義307

14.1.2二元運算的性質309

14.2代數系統312

14.2.1代數系統的定義與實例312

14.2.2代數系統的分類313

14.2.3子代數系統與積代數系統314

14.2.4代數系統的同態與同構315

14.3幾個典型的代數系統316

14.3.1半群與獨異點316

14.3.2群318

14.3.3環與域324

14.3.4格與布爾代數327

14.4皮亞諾系統332

習題334

參考文獻338