圖書信息
作者：Seymour Lipschutz著曹愛文等譯圖書詳細信息：
ISBN：9787302238508
定價：69元
印次：1-1
裝幀：平裝
印刷日期：2011-6-10
圖書簡介
隨著計算機技術的發展，重點研究有限系統的離散數學的重要地位日益鞏固。數字計算機本質上是有限結構，它的諸多性質都可以在有限數學系統的框架內進行理解與解釋。本書包括離散數學的最基本內容，既可作為離散數學課程的教材，也可作為現行課程的補充參考。本書前3章討論集合、關係、函式與算法。第4章~第7章分別討論邏輯、計數技術、機率論。第8章~第10章介紹圖論，分別討論圖、有向圖與二叉樹。第11章~第15章相對獨立，分別討論整數的性質、語言、自動機、有序集與格。附錄討論向量與矩陣、代數系統。其中，函式與算法一章中包含基數、可數集和計算複雜性的討論；圖論一章包含對平面性、可遍歷性、最小路徑、Warshall算法與哈夫曼算法。改變本書章節次序學習不會造成困難，也不影響知識的連貫性。
每章開始都是基本定義和原理的清晰敘述；所有定理都給出一系列的例子和其他幫助理解的材料。然後，章末附加習題與補充題。通過習題，可以增進理解學習內容以及證明定理，補充題是章節內容的完整複習。本書內容已遠遠超過對初步課程的要求，作為教材的話，本書具有更大的靈活性，極有價值，並且可以進一步提高讀者學習離散數學的興趣
圖書前言
譯者序由於信息技術瞬息萬變，引進教材等外國優秀成果也是中國當今相應學科發展的需要，在比較和吸收國外優秀科研、教學成果的同時，不斷改進和提高我國相應方面的狀態，這才是最終目的。但引進的材料應該具有權威性、系統性、先進性和通俗性等諸多優點，又能體現當今科技發展方向，使科技發展在已有成果的基礎上朝著更為明確的方向發展和努力。本書則恰恰具有這些特點，在保持淺顯易懂的同時又不失理論深度，選材廣泛適當，覆蓋面廣，其敘述特點則是深入淺出，推理嚴謹，且習題豐富。
在翻譯過程中，譯者深刻體會到本書中的先進教學思想和教學方法，因此，深入學習本書不僅可以提高計算機科學等方面的數學基礎，更為重要的是，可以學到良好的方法與技巧、縝密的思維與推理。本書將理論與實踐相集合，對於培養動手能力同樣大有裨益。
本書的特點是，詳細說明重要知識點，用豐富的例子，讓讀者全面透徹地理解和掌握概念。每章最後，都有大量習題和補充題，覆蓋面廣，難易適中，並給出詳盡答案，使讀者能舉一反三，靈活運用理論知識解決實際問題，並檢驗知識的掌握程度。
總之，本書是一本不可多得的好教材。
在翻譯過程中，譯者嚴格分析書中每個句子與單詞等基本信息，不敢妄自斷言，堅持尊重原書風格與思路，反覆推敲揣度，系統審視，謙虛謹慎，力爭完美。
本書主要由曹愛文翻譯，參加翻譯工作的人員還有李志雲、李曉春、陳安華、侯佳宜、許偉、戴文雅、於樊鵬、劉朋、王嘉佳、鄧衛、鄧凡平、李波、程雲建、許曉哲、朱珂、韋笑、孫宏、李騰、陳磊、魏宇、周京平、徐冬、馮哲、李緋、李強、趙東輝、周剛、張樂華、孫燕、高強、劉欣、王紅亮、周峰、謝暉、李琳、孫向陽、李元園、趙志鵬、馮佳、林彩娥、孫蕾、張百濤、趙楠等人，在此表示感謝。
由於譯者學識、水平等限制，出現錯誤和缺點在所難免，希望讀者多多包涵並不吝賜教、指正，譯者在此深表謝意。
前言
隨著計算機技術的發展，重點研究有限系統的離散數學的重要地位日益鞏固。數字計算機本質上是有限結構，它的諸多性質都可以在有限數學系統的框架內進行理解與解釋。本書包括離散數學的最基本內容，既可作為離散數學課程的教材，也可作為現行課程的補充參考。
本書前3章討論集合、關係、函式與算法。第4章~第7章分別討論邏輯、計數技術、機率論。第8章~第10章介紹圖論，分別討論圖、有向圖與二叉樹。第11章~第15章相對獨立，分別討論整數的性質、語言、自動機、有序集與格。附錄討論向量與矩陣、代數系統。其中，函式與算法一章中包含基數、可數集和計算複雜性的討論；圖論一章包含對平面性、可遍歷性、最小路徑、Warshall算法與哈夫曼算法。改變本書章節次序學習不會造成困難，也不影響知識的連貫性
圖書目錄
離散數學學習指導與習題解答(第3版)目錄目錄第1章集合1
1.1概述1
1.2集合、元素與子集1
1.2.1集合的表示1
1.2.2子集2
1.2.3全集與空集3
1.2.4不相交集3
1.3維恩圖3
1.3.1維恩圖與證明4
1.4集合運算4
1.4.1並集與交集5
1.4.2補、差與對稱差6
1.4.3基本積7
1.5集合的代數運算與對偶性8
1.5.1代數運算規律8
1.5.2對偶性8
1.6有限集與計數原理9
1.6.1計算有限集中的元素數量9
1.6.2容斥原理10
1.7集族、冪集與劃分11
1.7.1冪集11
1.7.2劃分12
1.7.3集合運算的推廣12
1.8數學歸納法13
1.8.1數學歸納法Ⅰ13
1.8.2數學歸納法Ⅱ13
本章習題14
補充題22
補充題答案26
第2章關係29
2.1概述29
2.2積集29
2.3關係30
2.3.1定義30
2.3.2逆關係31
2.4關係的圖形表示31
2.4.1實數R上的關係31
2.4.2集合上關係的有向圖32
2.4.3有限集上關係的圖示32
2.5關係的合成33
2.5.1關係合成33
2.5.2關係的合成與關係矩陣34
2.6關係的類型34
2.6.1自反關係34
2.6.2對稱關係與反對稱關係35
2.6.3傳遞關係36
2.7閉包性質36
2.7.1P-閉包36
2.7.2自反閉包與對稱閉包37
2.7.3傳遞閉包37
2.8等價關係38
2.8.1等價關係的定義38
2.8.2等價關係與劃分39
2.9偏序關係40
2.10n-元關係40
本章習題41
補充題48
補充題答案50
第3章函式與算法52
3.1概述52
3.2函式52
3.2.1作為關係的函式53
3.2.2複合函式54
3.3單射函式、滿射函式與可逆函式55
3.3.1單射函式與滿射函式的幾何特徵56
3.3.2排列57
3.4數學函式、指數函式與對數函式57
3.4.1下限函式與上限函式57
3.4.2整數值函式與絕對值函式57
3.4.3餘項函式與模運算58
3.4.4指數函式58
3.4.5對數函式59
3.4.6指數函式與對數函式之間的關係60
3.5序列與集合的索引類60
3.5.1序列61
3.5.2求和符號與求和61
3.5.3集合的索引類62
3.6遞歸定義函式63
3.6.1階乘函式63
3.6.2層號64
3.6.3斐波納契序列64
3.6.4阿克曼函式65
3.7基數/集合的容量65
3.7.1基數65
3.7.2不等式與基數66
3.8算法與函式67
3.9算法的複雜度68
3.9.1線性查找69
3.9.2增長率與大O記號70
3.9.3著名算法的複雜度71
本章習題71
補充題82
補充題答案84
第4章邏輯與命題演算86
4.1引言86
4.2命題與復命題86
4.2.1命題86
4.2.2複合命題86
4.3基本邏輯運算87
4.3.1合取87
4.3.2析取88
4.3.3否定88
4.4命題與真值表89
4.4.1命題與真值表89
4.4.2構造真值表的另一方法90
4.5永真式與永假式90
4.6邏輯等價91
4.7命題代數92
4.8條件語句與雙條件語句92
4.9論證93
4.10命題函式與量詞95
4.10.1命題函式95
4.10.2全稱量詞95
4.10.3存在量詞96
4.11量化命題的否定96
4.11.1反例98
4.11.2多變數命題函式98
4.11.3多變數量化命題的否定99
本章習題99
補充題105
補充題答案106
第5章計數技術108
5.1概述108
5.2基本計數原理108
5.3數學函式109
5.3.1階乘函式109
5.3.2二項式係數109
5.3.3二項式係數與楊輝三角形110
5.4排列111
5.4.1一般排列111
5.4.2可重複排列112
5.4.3有序抽樣113
5.5組合113
5.6鴿巢原理114
5.6.1鴿巢原理114
5.6.2一般鴿巢原理115
5.7容斥原理115
5.8樹形圖116
本章習題117
補充題126
補充題答案131
第6章高級計數技術與遞推134
6.1概述134
6.2有重組合134
6.3有序劃分與無序劃分135
6.3.1有序劃分135
6.3.2無序劃分135
6.4再現容斥原理136
6.4.1滿射函式的數量136
6.4.2錯位排列137
6.5再現鴿巢原理138
6.6遞推關係139
6.7具有常係數的線性遞推關係141
6.8二階齊次線性遞推關係的解142
6.8.1通解142
6.8.2特徵多項式具有相等根時的解144
6.9一般齊次線性遞推關係的解145
本章習題146
補充題151
補充題答案153
第7章機率論155
7.1概述155
7.2樣本與事件155
7.3有限機率空間158
7.3.1有限機率空間的定義158
7.3.2等機率空間158
7.3.3有限機率空間相關定理159
7.4條件機率160
7.4.1條件機率定義160
7.4.2條件機率的乘法定理161
7.5獨立事件162
7.6獨立重複試驗與二項分布163
7.6.1獨立重複試驗163
7.6.2具有兩個結果的重複試驗、伯努利試驗與二項試驗164
7.7隨機變數165
7.7.1隨機變數定義165
7.7.2隨機變數的和與積及其記號165
7.7.3隨機變數的機率分布166
7.7.4隨機變數的期望值167
7.7.5隨機變數的方差與標準差167
7.7.6二項分布168
7.8切比雪夫不等式與大數定律169
7.8.1切比雪夫不等式169
7.8.2樣本均值與大數定律170
本章習題170
補充題188
補充題答案193
第8章圖論195
8.1概述與數據結構195
8.1.1概述195
8.1.2鍊表與指針195
8.1.3堆疊、佇列與優先佇列197
8.2圖與多重圖198
8.2.1圖198
8.2.2多重圖198
8.2.3頂點的度(次數)199
8.2.4有限圖與平凡圖199
8.3子圖、同構圖與同胚圖200
8.3.1子圖200
8.3.2同構圖200
8.3.3同胚圖200
8.4路徑與連通性201
8.4.1路徑201
8.4.2連通性與連通分支202
8.4.3距離與直徑202
8.4.4割點與橋203
8.5可遍歷圖、歐拉圖與柯尼斯堡橋203
8.5.1可遍歷圖203
8.5.2哈密頓圖204
8.6標號圖與加權圖204
8.7完全圖、正則圖與二部圖205
8.7.1完全圖205
8.7.2正則圖206
8.7.3二部圖206
8.8樹圖207
8.8.1樹207
8.8.2生成樹208
8.8.3最小生成樹208
8.9平面圖209
8.9.1地圖與區域210
8.9.2歐拉公式211
8.9.3非平面圖與庫拉托夫斯基定理211
8.10圖的著色212
8.10.1著色212
8.10.2對偶地圖與四色定理214
8.11圖在計算機存儲器中的表示215
8.11.1鄰接矩陣215
8.11.2圖G的連結表示216
8.12圖算法218
8.12.1深度優先搜尋218
8.12.2廣度優先搜尋220
8.13旅行推銷員問題221
8.13.1問題定義221
8.13.2最近鄰算法222
本章習題223
補充題240
補充題答案246
第9章有向圖251
9.1概述251
9.2有向圖251
9.2.1有向圖定義251
9.2.2子圖252
9.3基本定義253
9.3.1頂點度253
9.3.2路徑253
9.3.3連通性254
9.4有根樹255
9.4.1有根樹定義255
9.4.2有序根樹256
9.5有向圖的序列表示257
9.5.1序列表示的定義257
9.5.2有向圖與關係、鄰接矩陣257
9.5.3路徑矩陣259
9.5.4傳遞閉包與路徑矩陣260
9.6沃舍爾算法與最短路徑260
9.6.1沃舍爾算法260
9.6.2最短路徑算法262
9.7有向圖的連結表示263
9.8圖的算法：深度優先與廣度優先查找265
9.8.1深度優先查找266
9.8.2廣度優先查找267
9.9有向無迴路圖與拓撲排序269
9.9.1有向無迴路圖269
9.9.2拓撲排序269
9.10最短路徑的修剪算法271
9.10.1問題引出271
9.10.2修剪算法272
本章習題274
補充題283
補充題答案289
第10章二叉樹293
10.1概述293
10.2二叉樹293
10.2.1二叉樹的圖示293
10.2.2相似二叉樹294
10.2.3相關術語294
10.3完全二叉樹與擴充（展）二叉樹295
10.3.1完全二叉樹295
10.3.2擴充（展）二叉樹：2-樹296
10.3.3代數式與波蘭表示法296
10.4二叉樹在存儲器中的表示297
10.4.1二叉樹的連結表示297
10.4.2二叉樹的序列表示298
10.5遍歷二叉樹299
10.6二叉查找樹301
10.6.1二叉查找樹中的查找與插入302
10.6.2二叉查找樹中的刪除303
10.6.3二叉查找樹算法的複雜性304
10.7優先佇列與堆304
10.7.1堆的定義304
10.7.2向堆中插入節點305
10.7.3從堆中刪除根節點307
10.7.4堆算法的複雜性308
10.8路徑長度與哈夫曼算法308
10.8.1加權路徑長度309
10.8.2哈夫曼算法309
10.8.3哈夫曼算法的計算機實現311
10.8.4編碼中的套用312
10.9一般（有序有根）樹的回顧312
10.9.1一般樹的定義312
10.9.2森林314
10.9.3一般樹與二叉樹314
本章習題314
補充題323
補充題答案327
第11章整數的性質329
11.1概述329
11.2次序、不等式與絕對值330
11.2.1次序330
11.2.2絕對值331
11.3數學歸納法331
11.3.1數學歸納法原理331
11.3.2良序原理332
11.4帶餘除法333
11.4.1帶餘除法定理333
11.4.2套用計算器的帶餘除法333
11.5整除與質數334
11.5.1整除334
11.5.2質數335
11.6最大公約數與歐幾里德算法336
11.6.1最大公約數336
11.6.2歐幾里德算法337
11.6.3最低公倍數338
11.7算術基本定理338
11.7.1互質339
11.7.2算術基本定理339
11.8同餘關係340
11.8.1同餘關係340
11.8.2剩餘類341
11.8.3同餘運算342
11.8.4剩餘類的計算342
11.8.5模m整數343
11.8.6同餘的消去律343
11.8.7簡化剩餘系與歐拉?函式344
11.9同餘方程345
11.9.1同餘方程345
11.9.2線性同餘方程:ax≡1(mod m)346
11.9.3線性同餘方程：ax≡b(mod m)346
11.9.4孫子（中國）剩餘定理348
本章習題350
補充題374
補充題答案379
第12章語言、自動機與語法381
12.1概述381
12.2字母表、字與自由半群381
12.2.1字與字母表381
12.2.2連線381
12.2.3子字與初始段382
12.2.4自由半群與自由類群382
12.3語言382
12.3.1語言的定義382
12.3.2語言上的運算383
12.4正則表達式與正則語言384
12.4.1正則表達式384
12.4.2語言與正則語言384
12.5有限狀態自動機385
12.5.1有限狀態自動機的定義385
12.5.2自動機的狀態圖386
12.5.3自動機確定的語言387
12.5.4泵作用引理388
12.6語法389
12.6.1語法的定義389
12.6.2語法G的語言L(G)390
12.6.3語法的類型391
12.6.4上下文無關語法的推導樹392
12.6.5巴克斯-諾爾形式393
12.6.6自動機與語法393
本章習題394
補充題401
補充題答案404
第13章有限狀態機與圖靈機406
13.1概述406
13.2有限狀態機406
13.2.1有限狀態機的定義406
13.2.2有限狀態機的狀態表與狀態圖407
13.2.3輸入帶與輸出帶407
13.2.4二進制加法408
13.3哥德爾數409
13.4圖靈機410
13.4.1基本定義410
13.4.2採用圖靈機計算412
13.4.3具有輸入的圖靈機413
13.4.4語言與圖靈機413
13.5可計算函式414
13.5.1定義414
13.5.2多元函式415
本章習題416
補充題420
補充題答案422
第14章有序集與格424
14.1概述424
14.2有序集424
14.2.1偏序424
14.2.2對偶序425
14.2.3有序子集425
14.2.4擬序425
14.2.5可比較性與線性有序集425
14.2.6積集與積序426
14.2.7克林閉包與次序426
14.3偏序集的哈塞圖427
14.3.1哈塞圖定義427
14.3.2極小元素、極大元素、首元素（最小元素）、末元素（最大元素）428
14.4相容枚舉429
14.5上確界與下確界430
14.6同構有序集（相似有序集）432
14.7良序集432
14.7.1良序集定義432
14.7.2超限歸納法433
14.7.3選擇公理與良序定理434
14.8格434
14.8.1格的定義公理435
14.8.2對偶性與冪等律435
14.8.3格與次序435
14.8.4子格與同構格436
14.9有界格437
14.10分配格437
14.10.1分配格定義437
14.10.2並不可約元與原子438
14.11補元與有補格439
14.11.1補元439
14.11.2有補格439
本章習題440
補充題451
補充題答案457
第15章布爾代數461
15.1概述461
15.2基本定義461
15.2.1布爾代數461
15.2.2子代數、同構布爾代數462
15.3對偶性463
15.4基本定理463
15.5布爾代數作為格464
15.6表示定理464
15.7集合的積和形式465
15.8布爾代數的積和形式466
15.8.1積和形式的定義466
15.8.2求積和形式的算法467
15.8.3完全積和形式468
15.9極小布爾表達式與素項469
15.9.1極小積和469
15.9.2素項469
15.9.3基本積的一致470
15.9.4一致法求素項470
15.9.5求極小積和形式471
15.10邏輯門與邏輯電路472
15.10.1邏輯門472
15.10.2邏輯電路474
15.10.3邏輯電路作為布爾代數474
15.10.4與或電路474
15.10.5與非門和或非門475
15.11真值表與布爾函式476
15.11.1真值表476
15.11.2布爾函式478
15.12卡諾圖479
15.12.1卡諾圖定義479
15.12.2二元情形480
15.12.3三元情形481
15.12.4四元情形483
本章習題485
補充題503
補充題答案507
附錄A向量與矩陣510
A.1概述510
A.2向量510
A.2.1向量定義510
A.2.2向量運算510
A.2.3列向量511
A.3矩陣511
A.4矩陣的加法與標量乘法512
A.5矩陣乘法514
A.5.1矩陣乘法的定義514
A.5.2矩陣乘法與線性方程組515
A.6轉置矩陣516
A.7方陣516
A.7.1方陣定義516
A.7.2方陣的代數運算517
A.8可逆（非奇異）矩陣和逆矩陣518
A.9行列式519
A.9.1行列式的定義519
A.9.2行列式的一般定義520
A.9.3行列式與 2×2 矩陣的逆矩陣520
A.10初等行變換與高斯消去法521
A.10.1初等行變換521
A.10.2階梯矩陣521
A.10.3矩陣形式中的高斯消去法522
A.10.4線性方程組的矩陣解法524
A.10.5n×n矩陣的逆矩陣525
A.11布爾（0-1）矩陣526
本章習題527
補充題538
補充題答案542
附錄B代數系統543
B.1概述543
B.2運算543
B.2.1定義543
B.2.2運算性質544
B.3半群546
B.3.1半群的定義546
B.3.2自由半群與自由么半群547
B.3.3子半群547
B.3.4同餘關係與商結構547
B.3.5半群的同態548
B.3.6半群同態基本定理549
B.3.7半群積550
B.4群550
B.4.1群的定義550
B.4.2對稱群Sn551
B.4.3MAP(A)、PERM(A)與 AUT(A)552
B.5子群、正規子群與同態552
B.5.1子群552
B.5.2陪集553
B.5.3正規子群553
B.5.4模m整數554
B.5.5循環子群554
B.5.6生成集和生成元555
B.5.7同態555
B.6環、整環（整域）與域556
B.6.1環與子環的定義556
B.6.2特殊的環：整環與域557
B.6.3理想558
B.6.4環同態559
B.6.5整環上的整除性559
B.7域上的多項式559
B.7.1基本定義560
B.7.2歐幾里德算法與多項式的根561
B.7.3K[t] 作為 PID（主理想域）與UFD（唯一析因整環）562
B.7.4代數基本定理563
本章習題564
補充題581
補充題答案587
第1章集合1
1.1概述1
1.2集合、元素與子集1
1.2.1集合的表示1
1.2.2子集2
1.2.3全集與空集2
1.2.4不相交集3
1.3維恩圖3
1.3.1維恩圖與證明3
1.4集合運算4
1.4.1並集與交集4
1.4.2補、差與對稱差5
1.4.3基本積6
1.5集合的代數運算與對偶性7
1.5.1代數運算規律7
1.5.2對偶性8
1.6有限集與計數原理8
1.6.1計算有限集中的元素數量8
1.6.2容斥原理9
1.7集族、冪集與劃分10
1.7.1冪集10
1.7.2劃分10
1.7.3集合運算的推廣11
1.8數學歸納法12
1.8.1數學歸納法Ⅰ12
1.8.2數學歸納法Ⅱ12
本章習題12
補充題20
補充題答案24
第2章關係26
2.1概述26
2.2積集26
2.3關係27
2.3.1定義27
2.3.2逆關係28
2.4關係的圖形表示28
2.4.1實數R上的關係28
2.4.2集合上關係的有向圖29
2.4.3有限集上關係的圖示29
2.5關係的合成29
2.5.1關係合成29
2.5.2關係的合成與關係矩陣30
2.6關係的類型31
2.6.1自反關係31
2.6.2對稱關係與反對稱關係31
2.6.3傳遞關係32
2.7閉包性質33
2.7.1P-閉包33
2.7.2自反閉包與對稱閉包33
2.7.3傳遞閉包34
2.8等價關係34
2.8.1等價關係的定義34
2.8.2等價關係與劃分35
2.9偏序關係36
2.10n-元關係36
本章習題37
補充題43
補充題答案45
第3章函式與算法47
3.1概述47
3.2函式47
3.2.1作為關係的函式48
3.2.2複合函式49
3.3單射函式、滿射函式與可逆函式50
3.3.1單射函式與滿射函式的幾何特徵51
3.3.2排列51
3.4數學函式、指數函式與對數函式52
3.4.1下限函式與上限函式52
3.4.2整數值函式與絕對值函式52
3.4.3餘項函式與模運算52
3.4.4指數函式53
3.4.5對數函式53
3.4.6指數函式與對數函式之間的關係54
3.5序列與集合的索引類55
3.5.1序列55
3.5.2求和符號與求和55
3.5.3集合的索引類56
3.6遞歸定義函式57
3.6.1階乘函式57
3.6.2層號58
3.6.3斐波納契序列58
3.6.4阿克曼函式59
3.7基數/集合的容量59
3.7.1基數59
3.7.2不等式與基數60
3.8算法與函式60
3.9算法的複雜度62
3.9.1線性查找62
3.9.2增長率與大O記號63
3.9.3著名算法的複雜度64
本章習題64
補充題74
補充題答案76
第4章邏輯與命題演算78
4.1引言78
4.2命題與復命題78
4.2.1命題78
4.2.2複合命題78
4.3基本邏輯運算79
4.3.1合取79
4.3.2析取79
4.3.3否定80
4.4命題與真值表81
4.4.1命題與真值表81
4.4.2構造真值表的另一方法81
4.5永真式與永假式82
4.6邏輯等價82
4.7命題代數83
4.8條件語句與雙條件語句83
4.9論證84
4.10命題函式與量詞86
4.10.1命題函式86
4.10.2全稱量詞86
4.10.3存在量詞87
4.11量化命題的否定87
4.11.1反例88
4.11.2多變數命題函式89
4.11.3多變數量化命題的否定89
本章習題90
補充題95
補充題答案96
第5章計數技術97
5.1概述97
5.2基本計數原理97
5.3數學函式98
5.3.1階乘函式98
5.3.2二項式係數98
5.3.3二項式係數與楊輝三角形99
5.4排列100
5.4.1一般排列100
5.4.2可重複排列101
5.4.3有序抽樣101
5.5組合102
5.6鴿巢原理103
5.6.1鴿巢原理103
5.6.2一般鴿巢原理103
5.7容斥原理103
5.8樹形圖104
本章習題105
補充題114
補充題答案118
第6章高級計數技術與遞推120
6.1概述120
6.2有重組合120
6.3有序劃分與無序劃分121
6.3.1有序劃分121
6.3.2無序劃分121
6.4再現容斥原理121
6.4.1滿射函式的數量122
6.4.2錯位排列123
6.5再現鴿巢原理124
6.6遞推關係124
6.7具有常係數的線性遞推關係126
6.8二階齊次線性遞推關係的解127
6.8.1通解127
6.8.2特徵多項式具有相等根時的解129
6.9一般齊次線性遞推關係的解130
本章習題131
補充題135
補充題答案137
第7章機率論139
7.1概述139
7.2樣本與事件139
7.3有限機率空間141
7.3.1有限機率空間的定義141
7.3.2等機率空間142
7.3.3有限機率空間相關定理142
7.4條件機率143
7.4.1條件機率定義143
7.4.2條件機率的乘法定理144
7.5獨立事件145
7.6獨立重複試驗與二項分布146
7.6.1獨立重複試驗146
7.6.2具有兩個結果的重複試驗、伯努利試驗與二項試驗147
7.7隨機變數148
7.7.1隨機變數定義148
7.7.2隨機變數的和與積及其記號148
7.7.3隨機變數的機率分布149
7.7.4隨機變數的期望值149
7.7.5隨機變數的方差與標準差150
7.7.6二項分布151
7.8切比雪夫不等式與大數定律151
7.8.1切比雪夫不等式151
7.8.2樣本均值與大數定律152
本章習題153
補充題168
補充題答案174
第8章圖論175
8.1概述與數據結構175
8.1.1概述175
8.1.2鍊表與指針175
8.1.3堆疊、佇列與優先佇列177
8.2圖與多重圖178
8.2.1圖178
8.2.2多重圖178
8.2.3頂點的度（次數）178
8.2.4有限圖與平凡圖179
8.3子圖、同構圖與同胚圖179
8.3.1子圖179
8.3.2同構圖179
8.3.3同胚圖180
8.4路徑與連通性180
8.4.1路徑180
8.4.2連通性與連通分支181
8.4.3距離與直徑181
8.4.4割點與橋182
8.5可遍歷圖、歐拉圖與柯尼斯堡橋182
8.5.1可遍歷圖182
8.5.2哈密頓圖183
8.6標號圖與加權圖183
8.7完全圖、正則圖與二部圖184
8.7.1完全圖184
8.7.2正則圖184
8.7.3二部圖185
8.8樹圖186
8.8.1樹186
8.8.2生成樹186
8.8.3最小生成樹187
8.9平面圖188
8.9.1地圖與區域188
8.9.2歐拉公式189
8.9.3非平面圖與庫拉托夫斯基定理190
8.10圖的著色191
8.10.1著色191
8.10.2對偶地圖與四色定理192
8.11圖在計算機存儲器中的表示193
8.11.1鄰接矩陣193
8.11.2圖G的連結表示194
8.12圖算法195
8.12.1深度優先搜尋196
8.12.2廣度優先搜尋198
8.13旅行推銷員問題199
8.13.1問題定義199
8.13.2最近鄰算法199
本章習題200
補充題215
補充題答案221
第9章有向圖226
9.1概述226
9.2有向圖226
9.2.1有向圖定義226
9.2.2子圖227
9.3基本定義227
9.3.1頂點度228
9.3.2路徑228
9.3.3連通性228
9.4有根樹229
9.4.1有根樹定義229
9.4.2有序根樹230
9.5有向圖的序列表示231
9.5.1序列表示的定義231
9.5.2有向圖與關係、鄰接矩陣232
9.5.3路徑矩陣233
9.5.4傳遞閉包與路徑矩陣234
9.6沃舍爾算法與最短路徑234
9.6.1沃舍爾算法234
9.6.2最短路徑算法235
9.7有向圖的連結表示237
9.8圖的算法：深度優先與廣度優先查找239
9.8.1深度優先查找239
9.8.2廣度優先查找241
9.9有向無迴路圖與拓撲排序242
9.9.1有向無迴路圖242
9.9.2拓撲排序242
9.10最短路徑的修剪算法244
9.10.1問題引出244
9.10.2修剪算法245
本章習題247
補充題255
補充題答案260
第10章二叉樹264
10.1概述264
10.2二叉樹264
10.2.1二叉樹的圖示264
10.2.2相似二叉樹265
10.2.3相關術語265
10.3完全二叉樹與擴充（展）二叉樹266
10.3.1完全二叉樹266
10.3.2擴充（展）二叉樹：2-樹266
10.3.3代數式與波蘭表示法267
10.4二叉樹在存儲器中的表示268
10.4.1二叉樹的連結表示268
10.4.2二叉樹的序列表示269
10.5遍歷二叉樹269
10.6二叉查找樹271
10.6.1二叉查找樹中的查找與插入272
10.6.2二叉查找樹中的刪除273
10.6.3二叉查找樹算法的複雜性274
10.7優先佇列與堆274
10.7.1堆的定義274
10.7.2向堆中插入節點275
10.7.3從堆中刪除根節點276
10.7.4堆算法的複雜性277
10.8路徑長度與哈夫曼算法278
10.8.1加權路徑長度278
10.8.2哈夫曼算法279
10.8.3哈夫曼算法的計算機實現280
10.8.4編碼中的套用281
10.9一般（有序有根）樹的回顧281
10.9.1一般樹的定義281
10.9.2森林282
10.9.3一般樹與二叉樹283
本章習題283
補充題291
補充題答案294
第11章整數的性質297
11.1概述297
11.2次序、不等式與絕對值297
11.2.1次序297
11.2.2絕對值298
11.3數學歸納法299
11.3.1數學歸納法原理299
11.3.2良序原理300
11.4帶餘除法300
11.4.1帶餘除法定理300
11.4.2套用計算器的帶餘除法301
11.5整除與質數301
11.5.1整除301
11.5.2質數302
11.6最大公約數與歐幾里德算法303
11.6.1最大公約數303
11.6.2歐幾里德算法304
11.6.3最低公倍數305
11.7算術基本定理305
11.7.1互質305
11.7.2算術基本定理306
11.8同餘關係307
11.8.1同餘關係307
11.8.2剩餘類308
11.8.3同餘運算308
11.8.4剩餘類的計算309
11.8.5模m整數309
11.8.6同餘的消去律310
11.8.7簡化剩餘系與歐拉?函式310
11.9同餘方程311
11.9.1同餘方程311
11.9.2線性同餘方程:ax≡1(mod m)312
11.9.3線性同餘方程：ax≡b(mod m)313
11.9.4孫子（中國）剩餘定理314
本章習題315
補充題337
補充題答案342
第12章語言、自動機與語法344
12.1概述344
12.2字母表、字與自由半群344
12.2.1字與字母表344
12.2.2連線344
12.2.3子字與初始段345
12.2.4自由半群與自由類群345
12.3語言345
12.3.1語言的定義345
12.3.2語言上的運算346
12.4正則表達式與正則語言346
12.4.1正則表達式346
12.4.2語言與正則語言347
12.5有限狀態自動機348
12.5.1有限狀態自動機的定義348
12.5.2自動機的狀態圖348
12.5.3自動機確定的語言349
12.5.4泵作用引理350
12.6語法351
12.6.1語法的定義351
12.6.2語法G的語言L（G）352
12.6.3語法的類型353
12.6.4上下文無關語法的推導樹354
12.6.5巴克斯-諾爾形式355
12.6.6自動機與語法355
本章習題355
補充題362
補充題答案364
第13章有限狀態機與圖靈機367
13.1概述367
13.2有限狀態機367
13.2.1有限狀態機的定義367
13.2.2有限狀態機的狀態表與狀態圖368
13.2.3輸入帶與輸出帶368
13.2.4二進制加法369
13.3哥德爾數370
13.4圖靈機370
13.4.1基本定義371
13.4.2採用圖靈機計算373
13.4.3具有輸入的圖靈機373
13.4.4語言與圖靈機373
13.5可計算函式374
13.5.1定義374
13.5.2多元函式375
本章習題376
補充題379
補充題答案381
第14章有序集與格383
14.1概述383
14.2有序集383
14.2.1偏序383
14.2.2對偶序384
14.2.3有序子集384
14.2.4擬序384
14.2.5可比較性與線性有序集384
14.2.6積集與積序385
14.2.7克林閉包與次序385
14.3偏序集的哈塞圖386
14.3.1哈塞圖定義386
14.3.2極小元素、極大元素、首元素（最小元素）、末元素（最大元素）387
14.4相容枚舉388
14.5上確界與下確界388
14.6同構有序集（相似有序集）390
14.7良序集390
14.7.1良序集定義390
14.7.2超限歸納法391
14.7.3選擇公理與良序定理392
14.8格392
14.8.1格的定義公理392
14.8.2對偶性與冪等律393
14.8.3格與次序393
14.8.4子格與同構格394
14.9有界格394
14.10分配格395
14.10.1分配格定義395
14.10.2並不可約元與原子395
14.11補元與有補格396
14.11.1補元396
14.11.2有補格397
本章習題397
補充題408
補充題答案413
第15章布爾代數416
15.1概述416
15.2基本定義416
15.2.1布爾代數416
15.2.2子代數、同構布爾代數417
15.3對偶性417
15.4基本定理418
15.5布爾代數作為格418
15.6表示定理419
15.7集合的積和形式420
15.8布爾代數的積和形式420
15.8.1積和形式的定義420
15.8.2求積和形式的算法421
15.8.3完全積和形式422
15.9極小布爾表達式與素項423
15.9.1極小積和423
15.9.2素項423
15.9.3基本積的一致424
15.9.4一致法求素項424
15.9.5求極小積和形式425
15.10邏輯門與邏輯電路426
15.10.1邏輯門426
15.10.2邏輯電路427
15.10.3邏輯電路作為布爾代數428
15.10.4與或電路428
15.10.5與非門和或非門429
15.11真值表與布爾函式429
15.11.1真值表429
15.11.2布爾函式431
15.12卡諾圖432
15.12.1卡諾圖定義432
15.12.2二元情形432
15.12.3三元情形434
15.12.4四元情形436
本章習題437
補充題453
補充題答案457
附錄A向量與矩陣460
A.1概述460
A.2向量460
A.2.1向量定義460
A.2.2向量運算460
A.2.3列向量461
A.3矩陣461
A.4矩陣的加法與標量乘法462
A.5矩陣乘法463
A.5.1矩陣乘法的定義463
A.5.2矩陣乘法與線性方程組465
A.6轉置矩陣465
A.7方陣466
A.7.1方陣定義466
A.7.2方陣的代數運算466
A.8可逆（非奇異）矩陣和逆矩陣467
A.9行列式468
A.9.1行列式的定義468
A.9.2行列式的一般定義469
A.9.3行列式與2×2矩陣的逆矩陣469
A.10初等行變換與高斯消去法470
A.10.1初等行變換470
A.10.2階梯矩陣470
A.10.3矩陣形式中的高斯消去法471
A.10.4線性方程組的矩陣解法473
A.10.5n×n矩陣的逆矩陣473
A.11布爾（0-1）矩陣474
本章習題475
補充題485
補充題答案488
附錄B代數系統490
B.1概述490
B.2運算490
B.2.1定義490
B.2.2運算性質491
B.3半群493
B.3.1半群的定義493
B.3.2自由半群與自由么半群493
B.3.3子半群494
B.3.4同餘關係與商結構494
B.3.5半群的同態495
B.3.6半群同態基本定理496
B.3.7半群積496
B.4群496
B.4.1群的定義496
B.4.2對稱群Sn497
B.4.3MAP(A)、PERM(A)與 AUT(A)498
B.5子群、正規子群與同態498
B.5.1子群498
B.5.2陪集499
B.5.3正規子群499
B.5.4模m整數500
B.5.5循環子群500
B.5.6生成集和生成元501
B.5.7同態501
B.6環、整環（整域）與域502
B.6.1環與子環的定義502
B.6.2特殊的環：整環與域503
B.6.3理想503
B.6.4環同態504
B.6.5整環上的整除性504
B.7域上的多項式505
B.7.1基本定義505
B.7.2歐幾里德算法與多項式的根506
B.7.3K[t] 作為 PID（主理想域）與UFD（唯一析因整環）508
B.7.4代數基本定理508
本章習題509
補充題524
補充題答案530
