第1 章命題邏輯1
1.1 命題和聯(lián)結(jié)詞1
1.1.1 命題1
1.1.2 命題聯(lián)結(jié)詞.2
1.1.3 命題表達(dá)式.5
1.1.4 真值表的構(gòu)造6
1.1.5 命題符號(hào)化.7
1.2 重言式8
1.2.1 命題公式分類8
1.2.2 重言式.9
1.2.3 邏輯等價(jià).9
1.2.4 代入規(guī)則與替換規(guī)則11
1.2.5 對(duì)偶原理.13
1.3 公式中的范式.14
1.3.1 析取范式和合取范式14
1.3.2 主析取范式16
1.3.3 主合取范式20
1.4 命題聯(lián)結(jié)詞的擴(kuò)充與歸約23
1.4.1 命題聯(lián)結(jié)詞的擴(kuò)充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 習(xí)題30
第2 章謂詞邏輯33
2.1 謂詞公式33
2.1.1 個(gè)體詞.33
2.1.2 謂詞.33
2.1.3 量詞.34
2.1.4 命題符號(hào)化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 謂詞公式的等價(jià)37
2.3.2 謂詞公式的類型38
2.4 謂詞公式中的范式39
2.5 謂詞推理39
2.5.1 推理規(guī)則.39
2.5.2 舉例.40
2.6 習(xí)題41
第3 章集合論43
3.1 基本概念43
3.2 集合間的關(guān)系.45
3.3 集合的運(yùn)算47
3.3.1 集合的基本運(yùn)算47
3.3.2 集合的運(yùn)算律49
3.3.3 例題.51
3.4 包含排斥原理.52
3.5 冪集合與笛卡兒積55
3.5.1 冪集合.55
3.5.2 笛卡兒積.56
3.6 集合運(yùn)算與基數(shù)概念的擴(kuò)展58
3.6.1 并集、交集的擴(kuò)展.58
3.6.2 基數(shù)概念的擴(kuò)展59
3.7 習(xí)題60
第4 章二元關(guān)系63
4.1 基本概念63
4.1.1 二元關(guān)系的定義63
4.1.2 關(guān)系的表示65
4.2 關(guān)系的運(yùn)算65
4.2.1 關(guān)系的并、交、補(bǔ)、差、對(duì)稱差運(yùn)算65
4.2.2 關(guān)系的復(fù)合運(yùn)算66
4.2.3 關(guān)系的逆運(yù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 閉包的復(fù)合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 等價(jià)關(guān)系與等價(jià)類81
4.8 函數(shù)84
4.8.1 函數(shù)的概念84
4.8.2 逆函數(shù)與復(fù)合函數(shù)86
4.9 習(xí)題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 習(xí)題124
第6 章初等數(shù)論128
6.1 整數(shù)和除法128
6.2 整數(shù)128
6.3 素?cái)?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ù)的計(jì)算139
6.8 一次同余方程.142
6.8.1 一次同余方程的概念142
6.8.2 一次同余方程的解142
6.9 剩余定理144
6.9.1 一次同余方程組144
6.9.2 剩余定理的計(jì)算機(jī)大整數(shù)加法.146
6.10 原根147
6.10.1 原根的定義147
6.10.2 具有原根的正整數(shù)的分布.151
6.11 指數(shù)的算術(shù)161
6.12 原根在密碼學(xué)中的應(yīng)用163
6.12.1 公鑰密碼學(xué)的背景知識(shí)163
6.12.2 模重復(fù)平方計(jì)算方法165
6.12.3 離散對(duì)數(shù)公鑰加密方案167
6.12.4 離散對(duì)數(shù)公鑰簽名方案168
6.13 習(xí)題170
第7 章代數(shù)系統(tǒng)174
7.1 二元運(yùn)算及其性質(zhì)174
7.1.1 二元運(yùn)算的定義174
7.1.2 二元運(yùn)算的性質(zhì)175
7.2 代數(shù)系統(tǒng)179
7.2.1 代數(shù)系統(tǒng)的定義與實(shí)例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 群在密碼學(xué)中的應(yīng)用213
7.5.1 兩個(gè)特殊的群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 域上的多項(xiàng)式環(huán)224
7.7.5 域上多項(xiàng)式的帶余除法225
7.7.6 最高公因式和最低公倍式227
7.7.7 不可約多項(xiàng)式227
7.7.8 多項(xiàng)式的重因式229
7.7.9 多項(xiàng)式的根230
7.7.10 多項(xiàng)式環(huán)的理想與商環(huán)230
7.8 環(huán)與域在編碼糾錯(cuò)理論中的應(yīng)用236
7.8.1 通信系統(tǒng)的基本模型236
7.8.2 編碼理論的基本知識(shí)237
7.8.3 線性分組碼的編碼與譯碼方案.245
7.8.4 線性分組碼的譯碼效率253
7.8.5 循環(huán)碼的編碼與譯碼方案254
7.8.6 循環(huán)碼的譯碼效率263
7.9 習(xí)題266
參考文獻(xiàn)271