●第I部分數學證明
引言3
0.1參考文獻4
章什麼是證明5
1.1命題5
1.2謂詞8
1.3公理化方法8
1.4我們的公理9
1.4.1邏輯推理9
1.4.2證明的模式10
1.5證明蘊涵10
1.5.1方法#111
1.5.2方法#2：證明逆反命題12
1.6證明“當且僅當”13
1.6.1方法#1：證明兩個語句相互蘊涵13
1.6.2方法#2：構建iff鏈13
1.7案例證明法14
1.8反證法15
1.9數學證明的優秀實踐16
1.10參考文獻18
1.1節習題18
1.5節習題21
1.7節習題21
1.8節習題23
第2章良序原理26
2.1良序證明26
2.2良序證明模板27
2.2.1整數求和27
2.3質因數分解29
2.4良序集合29
2.4.1不一樣的良序集合（選學）30
2.2節習題31
2.4節習題38
第3章邏輯公式40
3.1命題的命題41
3.1.1NOT，AND和OR41
3.1.2當且僅當42
3.1.3IMPLIES42
3.2計算機程序的命題邏輯44
3.2.1真值表計算45
3.2.2符號表示46
3.3等價性和有效性47
3.3.1蘊涵和逆否47
3.3.2永真性和可滿足性48
3.4命題代數49
3.4.1命題範式49
3.4.2等價性證明50
3.5SAT問題53
3.6謂詞公式54
3.6.1量詞54
3.6.2混合量詞55
3.6.3量詞的順序56
3.6.4變量與域56
3.6.5否定量詞57
3.6.6謂詞公式的永真性57
3.7參考文獻58
3.1節習題59
3.2節習題61
3.3節習題65
3.4節習題68
3.5節習題69
3.6節習題71
第4章數學數據類型79
4.1集合79
4.1.1常用集合80
4.1.2集合的比較和組合80
4.1.3冪集81
4.1.4集合構造器標記82
4.1.5證明集合相等82
4.2序列83
4.3函數84
4.3.1域和像84
4.3.2函數復合86
4關繫86
4.4.1關繫圖87
4.4.2關繫的像89
4.5有限基數90
4.5.1有限集有多少個子集91
4.1節習題92
4.2節習題96
4.4節習題97
4.5節習題105
第5章歸納法107
5.1一般歸納法107
5.1.1一般歸納法的規則108
5.1.2舉例說明108
5.1.3歸納法證明的模板109
5.1.4一般歸納法的簡潔寫法110
5.1.5更復雜的例子111
5.1.6錯誤的歸納證明113
5.2強歸納法115
5.2.1強歸納法的規則115
5.2.2斐波那契數列116
5.2.3質數的乘積117
5.2.4找零問題118
5.2.5堆盒子遊戲119
5.3強歸納法、一般歸納法和良序法的比較120
5.1節習題121
5.2節習題131
第6章狀態機136
6.1狀態和轉移136
6.2不變性原理137
6.2.1沿對角線移動的機器人137
6.2.2不變性原理的定義139
6.2.3示例：《虎膽龍威》141
6.3偏序正確性和終止性143
6.3.1快速求冪143
6.3.2派生變量145
6.3.3基於良序集合的終止性（選學）146
6.3.4東南方向跳躍的機器人（選學）146
6.4穩定的婚姻147
6.4.1配對儀式148
6.4.2我們結婚吧150
6.4.3他們從此幸福地生活在一起150
6.4.4竟然是男性151
6.4.5應用152
6.3節習題153
6.4節習題165
第7章遞歸數據類型172
7.1遞歸定義和結構歸納法172
7.1.1結構歸納法174
7.2匹配帶括號的字符串175
7.3非負整數上的遞歸函數179
7.3.1N上的一些標準遞歸函數179
7.3.2不規範的函數定義179
7.4算術表達式181
7.4.1Aexp的替換和求值181
7.5計算機科學中的歸納185
7.1節習題185
7.2節習題193
7.3節習題201
7.4節習題202
第8章無限集206
8.1無限基數集206
8.1.1不同之處209
8.1.2可數集209
8.1.3冪集的勢嚴格大於原集合211
8.1.4對角線證明213
8.2停止問題214
8.3集合邏輯217
8.3.1羅素悖論217
8.3.2集合的ZFC公理繫統218
8.3.3避免羅素悖論220
8.4這些真的有效嗎220
8.4.1計算機科學中的無窮大221
8.1節習題221
8.2節習題228
8.3節習題233
8.4節習題236
第Ⅱ部分結構
引言241
第9章數論242
9.1整除242
9.1.1整除的性質243
9.1.2不可整除問題244
9.1.3虎膽龍威245
9.2優選公約數247
9.2.1歐幾裡得算法247
9.2.2粉碎機249
9.2.3水壺問題的通解251
9.2.4優選公約數的性質252
9.3質數的奧秘253
9.4算術基本定理255
9.4.1專享分解定理的證明256
9.5阿蘭·圖靈257
9.5.1圖靈編碼（1.0版）258
9.5.2破解圖靈編碼（1.0版）260
9.6模運算260
9.7餘運算262
9.7.1環Z_n264
9.8圖靈編碼（2.0版）265
9.9倒數與約去266
9.9.1互質267
9.9.2約去268
9.9.3解密（2.0版）268
9.9.4破解圖靈編碼（2.0版）269
9.9.5圖靈後記269
9.10歐拉定理271
9.10.1計算歐拉?函數273
9.11RSA公鑰加密274
9.12SAT與RSA有什麼關繫276
9.13參考文獻277
9.1節習題277
9.2節習題278
9.3節習題285
9.4節習題285
9.6節習題287
9.7節習題288
9.8節習題293
9.9節習題293
9.10節習題295
9.11節習題303
0章有向圖和偏序309
10.1頂點的度311
10.2路和通路311
10.2.1查找通路313
10.3鄰接矩陣314
10.3.1最短路徑315
10.4路關繫316
10.4.1復合關繫316
10.5有向無環圖＆調度317
10.5.1調度318
10.5.2並行任務調度320
10.5.3Dilworth引理322
10.6偏序323
10.6.1DAG中路關繫的性質323
10.6.2嚴格偏序324
10.6.3弱偏序325
10.7用集合包含表示偏序326
10.8線性序327
10.9乘積序327
10.10等價關繫328
10.10.1等價類328
10.11關繫性質的總結329
10.1節習題330
10.2節習題331
10.3節習題334
10.4節習題335
10.5節習題338
10.6節習題344
10.7節習題347
10.8節習題349
10.9節習題352
10.10節習題354
1章通信網絡357
11.1路由357
11.1.1接近二叉樹357
11.1.2路由問題358
11.2路由的評價指標358
11.2.1網絡直徑358
11.2.2交換機的數量359
11.2.3網絡時延359
11.2.4擁塞360
11.3網絡設計361
11.3.1二維陣列361
11.3.2蝶形網絡362
11.3.3Benes?網絡363
11.2節習題368
11.3節習題368
2章簡單圖373
12.1頂點鄰接和度373
12.2美國異性伴侶統計375
12.2.1握手引理376
12.3一些常見的圖377
12.4同構378
12.5二分圖與匹配380
12.5.1二分匹配問題380
12.5.2匹配條件381
12.6著色384
12.6.1一個考試安排問題384
12.6.2一些著色邊界386
12.6.3為什麼著色387
12.7簡單路388
12.7.1簡單圖中的路、通路和圈388
12.7.2圈作為子圖389
12.8連通性390
12.8.1連通分量390
12.8.2奇數長度的圈和2-著色性391
12.8.3k？連通圖392
12.8.4連通圖的最小邊數393
12.9森林和樹394
12.9.1葉子、父母和孩子394
12.9.2性質395
12.9.3生成樹397
12.9.4最小生成樹397
12.10參考文獻401
12.2節習題402
12.4節習題403
12.5節習題406
12.6節習題411
12.7節習題418
12.8節習題420
12.9節習題424
3章平面圖431
13.1在平面上繪制圖形431
13.2平面圖的定義433
13.2.1面434
13.2.2平面嵌入的遞歸定義436
13.2.3這個定義行嗎438
13.2.4外表面在哪裡呢438
13.3歐拉公式439
13.4平面圖中邊的數量440
13.5返回到K_5和K_3,3441
13.6平面圖的著色442
13.7多面體的分類443
13.8平面圖的另一個特征445
13.2節習題446
13.8節習題447
第Ⅲ部分計數
引言455
4章求和與漸近性457
14.1年金的值458
14.1.1錢未來的價值458
14.1.2擾動法459
14.1.3年金價值的閉型460
14.1.4無限長的等比數列460
14.1.5示例461
14.1.6等比數列求和的變化462
14.2冪和463
14.3估算求和式子465
14.4超出邊界468
14.4.1問題陳述468
14.4.2調和數471
14.4.3漸近等式473
14.5乘積474
14.5.1斯特林公式475
14.6雙倍的麻煩477
14.7漸近符號479
14.7.1小o479
14.7.2大O479
14.7.3θ481
14.7.4漸近符號的誤區482
14.7.5Ω（選學）484
14.1節習題484
14.2節習題486
14.3節習題486
14.4節習題488
14.7節習題490
5章基數法則499
15.1通過其他計數來計算當前計數499
15.1.1雙射規則499
15.2序列計數500
15.2.1乘積法則501
15.2.素集合的子集501
15.2.3加和法則502
15.2.4密碼計數502
15.3廣義乘積法則503
15.3.1有缺鈔票504
15.3.2一個像棋問題505
15.3.3排列505
15.4除法法則506
15.4.1另一個像棋問題506
15.4.2圓桌騎士507
15.5子集計數508
15.5.1子集法則509
15.5.2比特序列510
15.6重復序列510
15.6.1子集序列510
15.6.2Bookkeeper法則511
15.6.3二項式定理512
15.7計數練習：撲克手牌513
15.7.1四條相同點數的手牌514
15.7.2葫蘆手牌514
15.7.3兩個對子的手牌515
15.7.4花色齊全的手牌517
15.8鴿子洞原理517
15.8.1頭上的頭發518
15.8.2具有相同和的子集519
15.8.3魔術521
15.8.4秘密521
15.8.5真正的秘密523
15.8.6如果是4張牌呢524
15.9容斥原理525
15.9.1兩個集合的並集525
15.9.2三個集合的並集525
15.9.342序列、04序列或60序列526
15.9.4n個集合的並集527
15.9.5計算歐拉函數529
15.10組合證明530
15.10.1帕斯卡三角恆等式530
15.10.2給出組合證明531
15.10.3有趣的組合證明532
15.11參考文獻533
15.2節習題534
15.4節習題537
15.5節習題538
15.6節習題544
15.7節習題548
15.8節習題550
15.9節習題554
15.10節習題561
6章母函數566
16.1無窮級數566
16.1.1不收斂性567
16.2使用母函數計數568
16.2.1蘋果和香蕉568
16.2.2母函數的積569
16.2.3卷積法則570
16.2.4利用卷積法則數甜甜圈570
16.2.5卷積法則中的二項式定理571
16.2.6一個荒唐的計數問題572
16.3部分分式573
16.3.1帶有重根的部分分式575
16.4求解線性遞推575
16.4.1斐波那契數的母函數575
16.4.2漢諾塔576
16.4.3求解一般線性遞推580
16.5形式冪級數580
16.5.1發散母函數580
16.5.2冪級數環581
16.6參考文獻583
16.1節習題583
16.2節習題583
16.3節習題586
16.4節習題588
16.5節習題595
第Ⅳ部分概率論
引言599
7章事件和概率空間601
17.1做個交易吧601
17.1.1理清問題601
17.2四步法602
17.2.1步驟一：找到樣本空間602
17.2.2步驟二：確定目標事件605
17.2.3步驟三：確定結果的概率606
17.2.4步驟四：計算事件的概率608
17.2.5蒙特霍爾問題的另一種解釋609
17.3奇怪的骰子609
17.3.1骰子Avs.骰子B610
17.3.2骰子Avs.骰子C612
17.3.3骰子Bvs.骰子C612
17.3.4擲兩次613
17.4生日原理615
17.4.1匹配概率的確切公式615
17.5集合論和概率616
17.5.1概率空間616
17.5.2集合論的概率法則617
17.5.3均勻概率空間618
17.5.4無窮概率空間619
17.6參考文獻620
17.2節習題620
17.5節習題623
8章條件概率626
18.1蒙特霍爾困惑626
18.1.1帷幕之後627
18.2定義和標記627
18.2.1問題所在628
18.3條件概率四步法629
18.4為什麼樹狀圖有效630
18.4.1大小為k的子集的概率631
18.4.2醫學檢測632
18.4.3四步分析法633
18.4.4固有頻率634
18.4.5後驗概率634
18.4.6概率的哲學635
18.5全概率定理637
18.5.1以單一事件為條件637
18.6辛普森悖論638
18.7獨立性640
18.7.1另一個公式640
18.7.2獨立性是一種假設641
18.8相互獨立性641
18.8.1DNA檢測642
18.8.2兩兩獨立643
18.9概率vs.置信度645
18.9.1肺結核測試645
18.9.2可能性修正646
18.9.3很可能正確的事實648
18.9.4特別事件648
18.9.5下一次拋擲的置信度649
18.4節習題650
18.5節習題650
18.6節習題660
18.7節習題661
18.8節習題663
18.9節習題666
9章隨機變量667
19.1隨機變量示例667
19.1.1指示器隨機變量668
19.1.2隨機變量和事件668
19.2獨立性669
19.3分布函數670
19.3.1伯努利分布672
19.3.2均勻分布672
19.3.3數字遊戲673
19.3.4二項分布675
19.4期望677
19.4.1均勻隨機變量的期望值677
19.4.2隨機變量的倒數的期望678
19.4.3指示器隨機變量的期望值678
19.4.4期望的另一種定義678
19.4.5條件期望679
19.4.6平均故障時間680
19.4.7賭博遊戲的預期收益682
19.5期望的線性性質686
19.5.1兩枚骰子的期望687
19.5.2指示器隨機變量的和687
19.5.3二項分布的期望688
19.5.4贈券收集問題689
19.5.5無限和691
19.5.6賭博悖論691
19.5.7悖論的解答692
19.5.8乘積的期望693
19.2節習題694
19.3節習題696
19.4節習題698
19.5節習題702
第20章離差712
20.1馬爾可夫定理712
20.1.1應用馬爾可夫定理714
20.1.2有界變量的馬爾可夫定理714
20.2切比雪夫定理715
20.2.1兩個賭博遊戲的方差716
20.2.2標準差717
20.3方差的性質718
20.3.1方差公式719
20.3.2故障時間的方差719
20.3.3常數的處理720
20.3.4和的方差721
20.3.5生日匹配722
20.4隨機抽樣估計723
20.4.1選民投票723
20.4.2兩兩獨立采樣725
20.5估計的置信度726
20.6隨機變量的和728
20.6.1引例728
20.6.2切諾夫界729
20.6.3二項式尾的切諾夫界729
20.6.4彩票遊戲的切諾夫界730
20.6.5隨機負載均衡731
20.6.6切諾夫界的證明732
20.6.7邊界的比較734
20.6.8墨菲定律735
20.7大期望736
20.7.1重復你自己736
20.1節習題737
20.2節習題738
20.3節習題739
20.5節習題746
20.6節習題750
20.7節習題753
第21章隨機遊走755
21.1賭徒破產755
21.1.1避免破產的概率757
21.1.2獲勝概率遞推758
21.1.3有偏情形的簡單解釋759
21.1.4步長多長761
21.1.5贏了就退出762
21.2圖的隨機遊走763
21.2.1網頁排名初探764
21.2.2網頁圖的隨機遊走765
21.2.3平穩分布與網頁排名766
21.1節習題768
21.2節習題769
第Ⅴ部分遞推
引言779
第22章遞推780
22.1漢諾塔780
22.1.1上界陷阱781
22.1.2擴充-化簡法781
22.2歸並排序783
22.2.1尋找遞推784
22.2.2求解遞推784
22.3線性遞推786
22.3.1爬樓梯786
22.3.2求解齊次線性遞推789
22.3.3求解一般線性遞推790
22.3.4如何猜測特解792
22.4分治遞推793
22.4.1Akra-Bazzi公式794
22.4.2兩個技術問題795
22.4.3Akra-Bazzi定理796
22.4.4主定理797
22.5進一步探索797
22.4節習題799
參考文獻802
符號表806

本書原為麻省理工學院計算機科學與工程專業的數學課程講義，谷歌技術專家參與編寫，涵蓋計算機科學涉及的全部基礎數學知識，包括形式邏輯符號、數學證明、歸納、集合與關繫、圖論基礎、排列與組合、計數原理、離散概率、遞歸等，特別強調數學定義、證明及其應用方法。本書因具有繫統、完整，以及有趣、易讀等明顯優勢，現已被優選IT技術相關從業者及準從業者奉為圭臬、廣泛傳閱，在人工智能日益普及的全新信息時代，更是大放異彩。本書適合計算機相關專業學生及從業人員作為數學入門教材，亦可作為統計、機器學習、數據挖掘等課程的寶貴資料。