齣版者的話
譯者序
前言
在綫資源
緻學生
作者簡介
符號錶
第1章 基礎：邏輯和證明 1
1.1 命題邏輯 1
1.1.1 引言 1
1.1.2 命題 1
1.1.3 條件語句 4
1.1.4 復閤命題的真值錶 7
1.1.5 邏輯運算符的優先級 8
1.1.6 邏輯運算和比特運算 8
練習 9
1.2 命題邏輯的應用 15
1.2.1 引言 15
1.2.2 語句翻譯 15
1.2.3 係統規範說明 16
1.2.4 布爾搜索 16
1.2.5 邏輯謎題 17
1.2.6 邏輯電路 18
練習 20
1.3 命題等價式 23
1.3.1 引言 23
1.3.2 邏輯等價式 23
1.3.3 德·摩根律的運用 25
1.3.4 構造新的邏輯等價式 26
1.3.5 可滿足性 28
1.3.6 可滿足性的應用 28
1.3.7 可滿足性問題求解 30
練習 31
1.4 謂詞和量詞 34
1.4.1 引言 34
1.4.2 謂詞 34
1.4.3 量詞 37
1.4.4 有限域上的量詞 39
1.4.5 受限域的量詞 39
1.4.6 量詞的優先級 40
1.4.7 變量綁定 40
1.4.8 涉及量詞的邏輯等價式 40
1.4.9 量化錶達式的否定 41
1.4.10 語句到邏輯錶達式的翻譯 42
1.4.11 係統規範說明中量詞的使用 43
1.4.12 選自路易斯·卡羅爾的例子 44
1.4.13 邏輯程序設計 45
練習 46
1.5 嵌套量詞 51
1.5.1 引言 51
1.5.2 理解涉及嵌套量詞的語句 51
1.5.3 量詞的順序 52
1.5.4 數學語句到嵌套量詞語句的翻譯 53
1.5.5 嵌套量詞到自然語言的翻譯 54
1.5.6 漢語語句到邏輯錶達式的翻譯 54
1.5.7 嵌套量詞的否定 55
練習 56
1.6 推理規則 62
1.6.1 引言 62
1.6.2 命題邏輯的有效論證 62
1.6.3 命題邏輯的推理規則 63
1.6.4 使用推理規則建立論證 65
1.6.5 消解律 66
1.6.6 謬誤 66
1.6.7 量化命題的推理規則 67
1.6.8 命題和量化命題推理規則的組閤使用 68
練習 69
1.7 證明導論 72
1.7.1 引言 72
1.7.2 一些專用術語 72
1.7.3 理解定理是如何陳述的 73
1.7.4 證明定理的方法 73
1.7.5 直接證明法 73
1.7.6 反證法 74
1.7.7 歸謬證明法 76
1.7.8 證明中的錯誤 78
1.7.9 良好的開端 79
練習 80
1.8 證明的方法和策略 81
1.8.1 引言 81
1.8.2 窮舉證明法和分情形證明法 81
1.8.3 存在性證明 84
1.8.4 唯一性證明 86
1.8.5 證明策略 87
1.8.6 尋找反例 89
1.8.7 證明策略實踐 90
1.8.8 拼接 90
1.8.9 開放問題的作用 92
1.8.10 其他證明方法 93
練習 94
關鍵術語和結論 96
復習題 97
補充練習 98
計算機課題 100
計算和探索 101
寫作課題 101
第2章 基本結構：集閤、函數、序列、求和與矩陣 102
2.1 集閤 102
2.1.1 引言 102
2.1.2 文氏圖 104
2.1.3 子集 105
2.1.4 集閤的大小 106
2.1.5 冪集 107
2.1.6 笛卡兒積 107
2.1.7 使用帶量詞的集閤符號 109
2.1.8 真值集和量詞 109
練習 109
2.2 集閤運算 112
2.2.1 引言 112
2.2.2 集閤恒等式 114
2.2.3 擴展的並集和交集 116
2.2.4 集閤的計算機錶示 117
2.2.5 多重集 118
練習 119
2.3 函數 123
2.3.1 引言 123
2.3.2 一對一函數和映上函數 125
2.3.3 反函數和函數閤成 128
2.3.4 函數的圖 130
2.3.5 一些重要的函數 130
2.3.6 部分函數 133
練習 133
2.4 序列與求和 138
2.4.1 引言 138
2.4.2 序列 138
2.4.3 遞推關係 139
2.4.4 特殊的整數序列 141
2.4.5 求和 144
練習 147
2.5 集閤的基數 150
2.5.1 引言 150
2.5.2 可數集閤 151
2.5.3 不可數集閤 153
練習 155
2.6 矩陣 157
2.6.1 引言 157
2.6.2 矩陣算術 158
2.6.3 矩陣的轉置和冪 159
2.6.4 0-1矩陣 160
練習 161
關鍵術語和結論 164
復習題 166
補充練習 166
計算機課題 168
計算和探索 169
寫作課題 169
第3章 算法 170
3.1 算法 170
3.1.1 引言 170
3.1.2 搜索算法 172
3.1.3 排序 174
3.1.4 字符串匹配 176
3.1.5 貪婪算法 177
3.1.6 停機問題 179
練習 180
3.2 函數的增長 183
3.2.1 引言 183
3.2.2 大O記號 184
3.2.3 一些重要函數的大O估算 187
3.2.4 函數組閤的增長 190
3.2.5 大Ω與大Θ記號 191
練習 192
3.3 算法的復雜度 196
3.3.1 引言 196
3.3.2 時間復雜度 196
3.3.3 矩陣乘法的復雜度 198
3.3.4 算法範型 199
3.3.5 理解算法的復雜度 201
練習 203
關鍵術語和結論 207
復習題 208
補充練習 209
計算機課題 211
計算和探索 211
寫作課題 212
第4章 數論和密碼學 213
4.1 整除性和模算術 213
4.1.1 引言 213
4.1.2 除法 213
4.1.3 除法算法 214
4.1.4 模算術 215
4.1.5 模m算術 217
練習 218
4.2 整數錶示和算法 220
4.2.1 引言 220
4.2.2 整數錶示 220
4.2.3 整數運算算法 223
4.2.4 模指數運算 225
練習 226
4.3 素數和最大公約數 229
4.3.1 引言 229
4.3.2 素數 229
4.3.3 試除法 230
4.3.4 埃拉托斯特尼篩法 231
4.3.5 關於素數的猜想和開放問題 235
4.3.6 最大公約數和最小公倍數 236
4.3.7 歐幾裏得算法 238
4.3.8 gcd的綫性組閤錶示 239
練習 242
4.4 求解同餘方程 245
4.4.1 引言 245
4.4.2 綫性同餘方程 245
4.4.3 中國剩餘定理 247
4.4.4 大整數的計算機算術 248
4.4.5 費馬小定理 249
4.4.6 僞素數 250
4.4.7 原根和離散對數 251
練習 252
4.5 同餘的應用 255
4.5.1 散列函數 255
4.5.2 僞隨機數 256
4.5.3 校驗碼 257
練習 259
4.6 密碼學 260
4.6.1 引言 260
4.6.2 古典密碼學 261
4.6.3 公鑰密碼學 263
4.6.4 RSA密碼係統 265
4.6.5 RSA加密 265
4.6.6 RSA解密 266
4.6.7 用RSA作為公鑰係統 266
4.6.8 密碼協議 267
4.6.9 同態加密 268
練習 269
關鍵術語和結論 271
復習題 273
補充練習 273
計算機課題 275
計算和探索 276
寫作課題 276
第5章 歸納與遞歸 278
5.1 數學歸納法 278
5.1.1 引言 278
5.1.2 數學歸納法 279
5.1.3 為什麼數學歸納法是有效的 280
5.1.4 選擇正確的基礎步驟 280
5.1.5 運用數學歸納法進行證明的原則 281
5.1.6 數學歸納法的優點與缺點 281
5.1.7 利用數學歸納法證明的例子 281
5.1.8 使用數學歸納法時犯的錯誤 290
練習 291
5.2 強歸納法與良序性 296
5.2.1 引言 296
5.2.2 強歸納法 296
5.2.3 利用強歸納法證明的例子 298
5.2.4 計算幾何學中使用強歸納法 300
5.2.5 利用良序性證明 302
練習 302
5.3 遞歸定義與結構歸納法 306
5.3.1 引言 306
5.3.2 遞歸地定義函數 307
5.3.3 遞歸地定義集閤與結構 309
5.3.4 結構歸納法 312
5.3.5 廣義歸納法 315
練習 315
5.4 遞歸算法 320
5.4.1 引言 320
5.4.2 證明遞歸算法的正確性 322
5.4.3 遞歸與迭代 323
5.4.4 歸並排序 324
練習 327
5.5 程序正確性 329
5.5.1 引言 329
5.5.2 程序驗證 329
5.5.3 推理規則 330
5.5.4 條件語句 330
5.5.5 循環不變量 332
練習 333
關鍵術語和結論 334
復習題 335
補充練習 336
計算機課題 340
計算和探索 341
寫作課題 341
第6章 計數 342
6.1 計數的基礎 342
6.1.1 引言 342
6.1.2 基本的計數原則 342
6.1.3 比較復雜的計數問題 346
6.1.4 減法法則（兩個集閤的容斥原理） 347
6.1.5 除法法則 349
6.1.6 樹圖 349
練習 350
6.2 鴿巢原理 354
6.2.1 引言 354
6.2.2 廣義鴿巢原理 355
6.2.3 鴿巢原理的幾個簡單應用 357
練習 359
6.3 排列與組閤 361
6.3.1 引言 361
6.3.2 排列 361
6.3.3 組閤 362
練習 365
6.4 二項式係數和恒等式 367
6.4.1 二項式定理 368
6.4.2 帕斯卡恒等式和三角形 370
6.4.3 其他的二項式係數
恒等式 371
練習 372
6.5 排列與組閤的推廣 375
6.5.1 引言 375
6.5.2 有重復的排列 375
6.5.3 有重復的組閤 375
6.5.4 具有不可區彆物體的集閤的排列 378
6.5.5 把物體放入盒子 379
練習 382
6.6 生成排列和組閤 385
6.6.1 引言 385
6.6.2 生成排列 385
6.6.3 生成組閤 386
練習 387
關鍵術語和結論 388
復習題 389
補充練習 390
計算機課題 393
計算和探索 394
寫作課題 394
第7章 離散概率 395
7.1 離散概率引論 395
7.1.1 引言 395
7.1.2 有限概率 395
7.1.3 事件組閤的概率 398
7.1.4 概率的推理 399
練習 399
7.2 概率論 402
7.2.1 引言 402
7.2.2 概率指派 402
7.2.3 事件的組閤 403
7.2.4 條件概率 404
7.2.5 獨立性 405
7.2.6 伯努利試驗與二項分布 406
7.2.7 隨機變量 407
7.2.8 生日問題 408
7.2.9 濛特卡羅算法 409
7.2.10 概率方法 411
練習 412
7.3 貝葉斯定理 414
7.3.1 引言 414
7.3.2 貝葉斯定理 415
7.3.3 貝葉斯垃圾郵件過濾器 417
練習 420
7.4 期望值和方差 422
7.4.1 引言 422
7.4.2 期望值 422
7.4.3 期望的綫性性質 424
7.4.4 平均情形下的計算復雜度 425
7.4.5 幾何分布 427
7.4.6 獨立隨機變量 428
7.4.7 方差 429
7.4.8 切比雪夫不等式 431
練習 433
關鍵術語和結論 435
復習題 436
補充練習 437
計算機課題 440
計算和探索 441
寫作課題 441
第8章 高級計數技術 442
8.1 遞推關係的應用 442
8.1.1 引言 442
8.1.2 用遞推關係構造模型 443
8.1.3 算法與遞推關係 447
練習 450
8.2 求解綫性遞推關係 453
8.2.1 引言 453
8.2.2 求解常係數綫性齊次遞推關係 454
8.2.3 求解常係數綫性非齊次遞推關係 458
練習 460
8.3 分治算法和遞推關係 463
8.3.1 引言 463
8.3.2 分治遞推關係 463
練習 469
8.4 生成函數 471
8.4.1 引言 471
8.4.2 關於冪級數的有用事實 471
8.4.3 計數問題與生成函數 474
8.4.4 使用生成函數求解遞推關係 477
8.4.5 使用生成函數證明恒等式 478
練習 479
8.5 容斥 484
8.5.1 引言 484
8.5.2 容斥原理 484
練習 487
8.6 容斥原理的應用 488
8.6.1 引言 488
8.6.2 容斥原理的另一種形式 488
8.6.3 埃拉托色尼篩 489
8.6.4 映上函數的個數 490
8.6.5 錯位排列 490
練習 492
關鍵術語和結論 493
復習題 494
補充練習 495
計算機課題 497
計算和探索 498
寫作課題 498
第9章 關係500 9. 1
關係及其性質 500
9.1.1 引言 500
9.1.2 函數作為關係 501
9.1.3 集閤的關係 501
9.1.4 關係的性質 502
9.1.5 關係的組閤 504
練習 506
9.2 n元關係及其應用 510
9.2.1 引言 510
9.2.2 n元關係 510
9.2.3 數據庫和關係 511
9.2.4 n元關係的運算 512
9.2.5 SQL 514
9.2.6 數據挖掘中的關聯規則 514
練習 516
9.3 關係的錶示 518
9.3.1 引言 518
9.3.2 用矩陣錶示關係 518
9.3.3 用圖錶示關係 521
練習 522
9.4 關係的閉包 524
9.4.1 引言 524
9.4.2 不同類型的閉包 524
9.4.3 有嚮圖中的路徑 525
9.4.4 傳遞閉包 526
9.4.5 沃捨爾算法 529
練習 531
9.5 等價關係 533
9.5.1 引言 533
9.5.2 等價關係 533
9.5.3 等價類 534
9.5.4 等價類與劃分 536
練習 538
9.6 偏序 542
9.6.1 引言 542
9.6.2 字典順序 544
9.6.3 哈塞圖 545
9.6.4 極大元與極小元 546
9.6.5 格 548
9.6.6 拓撲排序 550
練習 551
關鍵術語和結論 556
復習題 557
補充練習 558
計算機課題 561
計算和探索 562
寫作課題 562
第10章 圖 563
10.1 圖和圖模型 563
10.1.1 圖模型 565
練習 570
10.2 圖的術語和幾種特殊的圖 573
10.2.1 引言 573
10.2.2 基本術語 573
10.2.3 一些特殊的簡單圖 575
10.2.4 二分圖 576
10.2.5 二分圖和匹配 577
10.2.6 特殊類型圖的一些應用 580
10.2.7 從舊圖構造新圖 582
練習 584
10.3 圖的錶示和圖的同構 587
10.3.1 引言 587
10.3.2 圖的錶示 588
10.3.3 鄰接矩陣 588
10.3.4 關聯矩陣 590
10.3.5 圖的同構 590
10.3.6 判定兩個簡單圖是否同構 591
練習 593
10.4 連通性 598
10.4.1 引言 598
10.4.2 通路 598
10.4.3 無嚮圖的連通性 600
10.4.4 圖是如何連通的 601
10.4.5 有嚮圖的連通性 603
10.4.6 通路與同構 604
10.4.7 計算頂點之間的通路數 605
練習 606
10.5 歐拉通路與哈密頓通路 611
10.5.1 引言 611
10.5.2 歐拉通路與歐拉迴路 611
10.5.3 哈密頓通路與哈密頓迴路 615
10.5.4 哈密頓迴路的應用 618
練習 619
10.6 最短通路問題 623
10.6.1 引言 623
10.6.2 最短通路算法 625
10.6.3 旅行商問題 629
練習 630
10.7 平麵圖 633
10.7.1 引言 633
10.7.2 歐拉公式 634
10.7.3 庫拉圖斯基定理 637
練習 638
10.8 圖著色 640
10.8.1 引言 640
10.8.2 圖著色的應用 644
練習 645
關鍵術語和結論 648
復習題 650
補充練習 651
計算機課題 656
計算和探索 656
寫作課題 657
第11章 樹 658
11.1 樹的概述 658
11.1.1 有根樹 659
11.1.2 樹作為模型 662
11.1.3 樹的性質 663
練習 666
11.2 樹的應用 668
11.2.1 引言 668
11.2.2 二叉搜索樹 668
11.2.3 決策樹 671
11.2.4 前綴碼 672
11.2.5 博弈樹 674
練習 678
11.3 樹的遍曆 681
11.3.1 引言 681
11.3.2 通用地址係統 681
11.3.3 遍曆算法 682
11.3.4 中綴、前綴和後綴記法 688
練習 690
11.4 生成樹 693
11.4.1 引言 693
11.4.2 深度優先搜索 694
11.4.3 寬度優先搜索 696
11.4.4 迴溯的應用 698
11.4.5 有嚮圖中的深度優先搜索 700
練習 701
11.5 最小生成樹 704
11.5.1 引言 704
11.5.2 最小生成樹算法 704
練習 707
關鍵術語和結論 709
復習題 710
補充練習 711
計算機課題 714
計算和探索 714
寫作課題 715
第12章 布爾代數 716
12.1 布爾函數 716
12.1.1 引言 716
12.1.2 布爾錶達式和布爾函數 717
12.1.3 布爾代數恒等式 718
12.1.4 對偶性 720
12.1.5 布爾代數的抽象定義 720
練習 721
12.2 布爾函數的錶示 722
12.2.1 積之和展開式 723
12.2.2 函數完備性 724
練習 724
12.3 邏輯門電路 725
12.3.1 引言 725
12.3.2 門的組閤 726
12.3.3 電路的例子 726
12.3.4 加法器 728
練習 729
12.4 電路的極小化 731
12.4.1 引言 731
12.4.2 卡諾圖 732
12.4.3 無須在意的條件 737
12.4.4 奎因-莫可拉斯基方法 737
練習 741
關鍵術語和結論 743
復習題 744
補充練習 744
計算機課題 746
計算和探索 746
寫作課題 747
第13章 計算模型 748
13.1 語言和文法 748
13.1.1 引言 748
13.1.2 短語結構文法 749
13.1.3 短語結構文法的類型 751
13.1.4 派生樹 752
13.1.5 巴剋斯-諾爾範式 754
練習 755
13.2 帶輸齣的有限狀態機 758
13.2.1 引言 758
13.2.2 帶輸齣的有限狀態機 759
練習 762
13.3 不帶輸齣的有限狀態機 764
13.3.1 引言 764
13.3.2 串的集閤 764
13.3.3 有限狀態自動機 765
13.3.4 有限狀態機的語言識彆 766
13.3.5 非確定性的有限狀態自動機 771
練習 773
13.4 語言的識彆 777
13.4.1 引言 777
13.4.2 剋萊因定理 778
13.4.3 正則集閤和正則文法 781
13.4.4 一個不能由有限狀態自動機識彆的集閤 783
13.4.5 一些更強大的機器 783
練習 784
13.5 圖靈機 786
13.5.1 引言 786
13.5.2 圖靈機的定義 787
13.5.3 用圖靈機識彆集閤 789
13.5.4 用圖靈機計算函數 790
13.5.5 不同類型的圖靈機 790
13.5.6 丘奇-圖靈論題 791
13.5.7 計算復雜度、可計算性和可判定性 791
練習 794
關鍵術語和結論 796
復習題 797
補充練習 798
計算機課題 800
計算和探索 800
寫作課題 800
附錄A 實數和正整數的公理 802
附錄B 指數與對數函數 807
附錄C 僞代碼 809
推薦讀物 813
參考文獻 817
奇數編號練習答案
· · · · · · (收起)