第1 章命題邏輯1
1.1 命題和聯(lián)結(jié)詞1
1.1.1 命題1
1.1.2 命題聯(lián)結(jié)詞.2
1.1.3 命題表達式.5
1.1.4 真值表的構(gòu)造6
1.1.5 命題符號化.7
1.2 重言式8
1.2.1 命題公式分類8
1.2.2 重言式.9
1.2.3 邏輯等價.9
1.2.4 代入規(guī)則與替換規(guī)則11
1.2.5 對偶原理.13
1.3 公式中的范式.14
1.3.1 析取范式和合取范式14
1.3.2 主析取范式16
1.3.3 主合取范式20
1.4 命題聯(lián)結(jié)詞的擴充與歸約23
1.4.1 命題聯(lián)結(jié)詞的擴充23
1.4.2 命題聯(lián)結(jié)詞的歸約24
1.5 基于命題的推理25
1.5.1 基于真值表的推理26
1.5.2 基于推理規(guī)則的推理27
1.5.3 舉例.27
1.6 習題30
第2 章謂詞邏輯33
2.1 謂詞公式33
2.1.1 個體詞.33
2.1.2 謂詞.33
2.1.3 量詞.34
2.1.4 命題符號化34
2.1.5 謂詞公式.35
2.2 約束35
￠ IV ￠ 目錄
2.2.1 約束部分.36
2.2.2 換名規(guī)則和代替規(guī)則36
2.2.3 公式的解釋37
2.3 謂詞公式中的永真式.37
2.3.1 謂詞公式的等價37
2.3.2 謂詞公式的類型38
2.4 謂詞公式中的范式39
2.5 謂詞推理39
2.5.1 推理規(guī)則.39
2.5.2 舉例.40
2.6 習題41
第3 章集合論43
3.1 基本概念43
3.2 集合間的關(guān)系.45
3.3 集合的運算47
3.3.1 集合的基本運算47
3.3.2 集合的運算律49
3.3.3 例題.51
3.4 包含排斥原理.52
3.5 冪集合與笛卡兒積55
3.5.1 冪集合.55
3.5.2 笛卡兒積.56
3.6 集合運算與基數(shù)概念的擴展58
3.6.1 并集、交集的擴展.58
3.6.2 基數(shù)概念的擴展59
3.7 習題60
第4 章二元關(guān)系63
4.1 基本概念63
4.1.1 二元關(guān)系的定義63
4.1.2 關(guān)系的表示65
4.2 關(guān)系的運算65
4.2.1 關(guān)系的并、交、補、差、對稱差運算65
4.2.2 關(guān)系的復合運算66
4.2.3 關(guān)系的逆運算68
4.3 關(guān)系的性質(zhì)69
4.3.1 關(guān)系性質(zhì)的概念69
4.3.2 關(guān)系性質(zhì)舉例70
4.3.3 關(guān)系性質(zhì)在關(guān)系圖及關(guān)系矩陣中的特征71
目錄￠ V ￠
4.4 關(guān)系的閉包71
4.4.1 閉包的定義71
4.4.2 關(guān)系R 的閉包求法72
4.4.3 傳遞閉包的Warshall 算法74
4.4.4 閉包的復合75
4.5 集合的劃分和覆蓋77
4.6 序關(guān)系78
4.6.1 偏序關(guān)系與偏序集的概念78
4.6.2 偏序集的哈斯圖79
4.6.3 偏序集中的特殊元79
4.7 等價關(guān)系與等價類81
4.8 函數(shù)84
4.8.1 函數(shù)的概念84
4.8.2 逆函數(shù)與復合函數(shù)86
4.9 習題88
第5 章圖論93
5.1 若干圖論經(jīng)典問題93
5.2 圖的基本概念及矩陣表示96
5.2.1 圖的基本概念96
5.2.2 圖的矩陣表示方法100
5.3 路與連通度102
5.4 歐拉圖與哈密頓圖108
5.5 二部圖與匹配.110
5.6 平面圖.112
5.6.1 平面圖及其性質(zhì)112
5.6.2 平面圖著色114
5.7 樹.116
5.7.1 樹及其性質(zhì)116
5.7.2 最小生成樹118
5.7.3 有向樹120
5.8 習題124
第6 章初等數(shù)論128
6.1 整數(shù)和除法128
6.2 整數(shù)128
6.3 素數(shù)130
6.4 最大公約數(shù)和最小公倍數(shù).133
6.4.1 最大公約數(shù)和最小公倍數(shù)的定義133
6.4.2 最大公約數(shù)和最小公倍數(shù)的求法133
￠ VI ￠ 目錄
6.5 同余135
6.6 剩余系.136
6.6.1 完全剩余系136
6.6.2 既約剩余系、歐拉函數(shù)和歐拉定理137
6.7 歐拉函數(shù)的計算139
6.8 一次同余方程.142
6.8.1 一次同余方程的概念142
6.8.2 一次同余方程的解142
6.9 剩余定理144
6.9.1 一次同余方程組144
6.9.2 剩余定理的計算機大整數(shù)加法.146
6.10 原根147
6.10.1 原根的定義147
6.10.2 具有原根的正整數(shù)的分布.151
6.11 指數(shù)的算術(shù)161
6.12 原根在密碼學中的應用163
6.12.1 公鑰密碼學的背景知識163
6.12.2 模重復平方計算方法165
6.12.3 離散對數(shù)公鑰加密方案167
6.12.4 離散對數(shù)公鑰簽名方案168
6.13 習題170
第7 章代數(shù)系統(tǒng)174
7.1 二元運算及其性質(zhì)174
7.1.1 二元運算的定義174
7.1.2 二元運算的性質(zhì)175
7.2 代數(shù)系統(tǒng)179
7.2.1 代數(shù)系統(tǒng)的定義與實例179
7.2.2 代數(shù)系統(tǒng)的同構(gòu)與同態(tài)180
7.3 半群184
7.3.1 半群.184
7.3.2 單位元和逆元186
7.4 群.189
7.4.1 群的定義189
7.4.2 群的同態(tài)192
7.4.3 循環(huán)群195
7.4.4 變換群199
7.4.5 置換群201
7.4.6 子群.205
目錄￠ VII ￠
7.4.7 子群的陪集209
7.4.8 不變子群和商群212
7.5 群在密碼學中的應用213
7.5.1 兩個特殊的群Zn 和Z¤
n 213
7.5.2 Z¤
n 和歐拉定理215
7.5.3 基于Z¤
n 的公鑰密碼系統(tǒng)RSA 216
7.6 環(huán).217
7.6.1 環(huán)的定義218
7.6.2 子環(huán).220
7.6.3 理想子環(huán)220
7.7 域.222
7.7.1 域的定義222
7.7.2 子域.223
7.7.3 域的特征223
7.7.4 域上的多項式環(huán)224
7.7.5 域上多項式的帶余除法225
7.7.6 最高公因式和最低公倍式227
7.7.7 不可約多項式227
7.7.8 多項式的重因式229
7.7.9 多項式的根230
7.7.10 多項式環(huán)的理想與商環(huán)230
7.8 環(huán)與域在編碼糾錯理論中的應用236
7.8.1 通信系統(tǒng)的基本模型236
7.8.2 編碼理論的基本知識237
7.8.3 線性分組碼的編碼與譯碼方案.245
7.8.4 線性分組碼的譯碼效率253
7.8.5 循環(huán)碼的編碼與譯碼方案254
7.8.6 循環(huán)碼的譯碼效率263
7.9 習題266
參考文獻271