離散數學：面向計算機科學專業（簡體書）

本書由計算機和數學領域的三位教授聯合撰寫，是為計算機專業量身定制的離散數學教材。針對初入學的本科生不理解為何要學習高深的數學，授課教師苦於向毫無編程經驗的學生講授繁雜的算法程序的問題，本書打破了傳統的課程順序和教學方法，明確“為何學”和“有何用”，不僅清晰呈現了計算機專業學生必需的數學知識，而且通過實踐和應用啟發學生對後續課程的學習興趣。主要內容涵蓋計數、密碼學與數論、邏輯與證明、歸納法、遞歸、概率以及圖論等。本書推導嚴謹、代碼清晰、練習豐富，可作為高等學校計算機相關專業的離散數學課程的教材，也可供計算機技術人員學習與參考。

從計算機科學專業需求出發，全面介紹離散數學知識

譯者序
前言
第1章 計數 1
1.1 基本計數 1
1.1.1 加法原理 1
1.1.2 抽象化 2
1.1.3 連續整數求和 3
1.1.4 乘法原理 3
1.1.5 二元子集 5
重要概念、公式和定理 5
習題 6
1.2 序列、排列和子集 7
1.2.1 使用加法和乘法原理 7
1.2.2 序列和函數 9
1.2.3 雙射原理 10
1.2.4 集合的 k 元素排列 11
1.2.5 集合子集的計數 12
重要概念、公式和定理 14
習題 15
1.3 二項式係數 16
1.3.1 帕斯卡三角形 16
1.3.2 使用加法原理的證明 18
1.3.3 二項式定理 19
1.3.4 標記與三項式係數 21
重要概念、公式和定理 22
習題 22
1.4 關係 24
1.4.1 什麼是關係 24
1.4.2 函數關係 24
1.4.3 關係的性質 25
1.4.4 等價關係 27
1.4.5 偏序和全序 29
重要概念、公式和定理 30
習題 31
1.5 在計數中運用等價關係 32
1.5.1 對稱原理 32
1.5.2 等價關係 34
1.5.3 商原理 34
1.5.4 等價類計數 35
1.5.5 多重集 36
1.5.6 書櫃安排問題 37
1.5.7 n 元集合的 k 元多重集的數目 38
1.5.8 使用商原理解釋商 39
重要概念、公式和定理 39
習題 40
第2章 密碼編碼學與數論 43
2.1 密碼編碼學和模算法 43
2.1.1 密碼編碼學導論 43
2.1.2 私鑰密碼 43
2.1.3 公鑰密碼體制 46
2.1.4 模 n 算術 47
2.1.5 使用模 n 加法的密碼編碼 49
2.1.6 使用模 n 乘法的密碼編碼 50
重要概念、公式和定理 51
習題 52
2.2 逆元和最大公因子 54
2.2.1 方程的解和模 n 的逆元 54
2.2.2 模 n 的逆元 55
2.2.3 將模方程轉化為普通方程 57
2.2.4 最大公因子 58
2.2.5 歐幾裡得除法定理 59
2.2.6 歐幾裡得最大公因子算法 61
2.2.7 廣義最大公因子算法 62
2.2.8 計算逆元 64
重要概念、公式和定理 65
習題 66
2.3 RSA 密碼體制 67
2.3.1 模 n 的指數運算 67
2.3.2 指數運算的規則 68
2.3.3 費馬小定理 70
2.3.4 RSA 密碼體制 71
2.3.5 中國剩餘定理 74
重要概念、公式和定理 75
習題 76
2.4 RSA 加密體制的細節 78
2.4.1 模 n 指數運算的實用性 78
2.4.2 使用 RSA 算法會花費多長時間 79
2.4.3 因式分解有多難 80
2.4.4 找大素數 80
重要概念、公式和定理 83
習題 83
第3章 關於邏輯與證明的思考 85
3.1 等價和蘊含 85
3.1.1 語句的等價 85
3.1.2 真值表 87
3.1.3 德摩根律 89
3.1.4 蘊含 90
3.1.5 當且僅當 91
重要概念、公式和定理 93
習題 94
3.2 變元和量詞 95
3.2.1 變元和論域 95
3.2.2 量詞