目 錄

第1章 命題邏輯 1
1.1 命題 1
思考與練習(xí)1.1 3
1.2 邏輯聯(lián)結(jié)詞 3
1.2.1 基本聯(lián)結(jié)詞 3
1.2.2 其他聯(lián)結(jié)詞 6
思考與練習(xí)1.2 6
1.3 命題公式與真值表 7
1.3.1 命題公式 7
1.3.2 真值表 8
思考與練習(xí)1.3 8
1.4 命題翻譯 9
1.4.1 命題的合取 9
1.4.2 命題的析取 9
1.4.3 條件句復(fù)合命題 10
1.4.4 多聯(lián)結(jié)詞構(gòu)成的復(fù)合命題 11
思考與練習(xí)1.4 12
1.5 命題公式的分類與邏輯等價 13
1.5.1 命題公式的分類 13
1.5.2 命題公式等價 14
1.5.3 聯(lián)結(jié)詞的功能完備集 16
1.5.4 對偶原理 17
思考與練習(xí)1.5 18
1.6 范式 18
1.6.1 簡單的范式 18
1.6.2 小項(xiàng)與大項(xiàng) 19
1.6.3 主析取范式與主合取范式 20
思考與練習(xí)1.6 23
1.7 推 理 理 論 24
1.7.1 蘊(yùn)含與論證 24
1.7.2 自然推理系統(tǒng) 26
思考與練習(xí)1.7 33
第2章 謂詞邏輯 34
2.1 謂詞、個體詞與量詞 34
2.1.1 個體詞和謂詞 34
2.1.2 量詞與量化 36
思考與練習(xí)2.1 37
2.2 謂詞邏輯的命題翻譯 38
2.2.1 特殊化個體詞的命題 38
2.2.2 量詞量化的命題 38
思考與練習(xí)2.2 41
2.3 量詞約束與謂詞公式的解釋 42
2.3.1 量詞對個體詞變元的作用 42
2.3.2 謂詞公式的解釋與求值 42
2.3.3 量詞與聯(lián)結(jié)詞的搭配 44
思考與練習(xí)2.3 44
2.4 謂詞公式的等價和蘊(yùn)含 45
2.4.1 基本等價與蘊(yùn)含關(guān)系 45
2.4.2 利用等價關(guān)系計算前束范式 48
思考與練習(xí)2.4 49
2.5 謂詞邏輯的推理理論 50
2.5.1 推理定律 50
2.5.2 量詞的消除與產(chǎn)生規(guī)則 50
2.5.3 謂詞邏輯的自然推理示例 52
思考與練習(xí)2.5 55
2.6 *數(shù)學(xué)證明初步 56
2.6.1 數(shù)學(xué)論題的描述 56
2.6.2 證明方法 56
2.6.3 證明策略 58
思考與練習(xí)2.6 59
第3章 集合論基礎(chǔ) 61
3.1 集合的概念和表示方法 61
3.1.1 集合描述 61
3.1.2 集合的包含與相等 62
3.1.3 空集和全集 63
3.1.4 集合的冪集 65
思考與練習(xí)3.1 66
3.2 集合運(yùn)算 66
3.2.1 基本運(yùn)算 66
3.2.2 多集合的交與并 68
思考與練習(xí)3.2 70
3.3 集合運(yùn)算的性質(zhì) 71
3.3.1 集合算律與恒等變換 71
3.3.2 基于定義的運(yùn)算性質(zhì)驗(yàn)證 72
思考與練習(xí)3.3 74
3.4 集合劃分和計數(shù) 74
3.4.1 集合的劃分與覆蓋 75
3.4.2 *集合計數(shù)的容斥原理 76
思考與練習(xí)3.4 77
3.5 序偶與笛卡兒積 78
3.5.1 序偶和元組 78
3.5.2 笛卡兒積 79
思考與練習(xí)3.5 81
第4章 關(guān)系 82
4.1 二元關(guān)系的含義與表示 82
4.1.1 二元關(guān)系 82
4.1.2 關(guān)系的矩陣和圖表示法 84
思考與練習(xí)4.1 85
4.2 關(guān)系運(yùn)算 86
4.2.1 關(guān)系的逆與復(fù)合 86
4.2.2 關(guān)系運(yùn)算的性質(zhì) 87
4.2.3 關(guān)系運(yùn)算的圖和矩陣實(shí)現(xiàn) 88
4.2.4 關(guān)系的冪 90
思考與練習(xí)4.2 92
4.3 關(guān)系的性質(zhì) 93
4.3.1 自反與反自反關(guān)系 93
4.3.2 對稱與反對稱關(guān)系 94
4.3.3 傳遞關(guān)系 95
4.3.4 關(guān)系性質(zhì)的等價描述與判定 95
思考與練習(xí)4.3 97
4.4 關(guān)系的閉包 98
4.4.1 閉包的概念 98
4.4.2 閉包計算 99
思考與練習(xí)4.4 102
4.5 等價關(guān)系 102
4.5.1 等價與相容 102
4.5.2 等價類 103
4.5.3 劃分與等價關(guān)系的對應(yīng) 104
思考與練習(xí)4.5 106
4.6 序關(guān)系 107
4.6.1 體現(xiàn)部分序的偏序關(guān)系 107
4.6.2 哈斯圖 108
4.6.3 鏈與全序關(guān)系 109
4.6.4 偏序集的特殊元素 111
思考與練習(xí)4.6 112
第5章 函數(shù) 114
5.1 從關(guān)系到函數(shù) 114
5.1.1 函數(shù)的概念 114
5.1.2 函數(shù)集 115
5.1.3 函數(shù)的性質(zhì)與特殊函數(shù) 116
思考與練習(xí)5.1 118
5.2 函數(shù)的逆與復(fù)合 119
5.2.1 雙射的反函數(shù) 119
5.2.2 函數(shù)復(fù)合 119
5.2.3 函數(shù)運(yùn)算的性質(zhì) 121
思考與練習(xí)5.2 122
5.3 集合的基數(shù) 122
5.3.1 集合等勢 122
5.3.2 有限集與無限集 123
5.3.3 可數(shù)集與不可數(shù)集 123
5.3.4 基數(shù)比較 125
思考與練習(xí)5.3 126
第6章 運(yùn)算與代數(shù)系統(tǒng) 127
6.1 運(yùn)算及其性質(zhì) 127
6.1.1 運(yùn)算的概念 127
6.1.2 二元運(yùn)算的性質(zhì) 128
思考與練習(xí)6.1 129
6.2 二元運(yùn)算中的特殊元素 130
6.2.1 幺元 130
6.2.2 零元 131
6.2.3 逆元 132
思考與練習(xí)6.2 133
6.3 代數(shù)系統(tǒng) 133
6.3.1 代數(shù)與子代數(shù) 133
6.3.2 同態(tài)與同構(gòu) 134
思考與練習(xí)6.3 135
6.4 半群與獨(dú)異點(diǎn) 136
思考與練習(xí)6.4 137
6.5 群與子群 138
6.5.1 群的概念 138
6.5.2 群的性質(zhì) 139
6.5.3 子群 140
思考與練習(xí)6.5 141
6.6 循環(huán)群與置換群 142
6.6.1 循環(huán)群 142
6.6.2 置換群 143
思考與練習(xí)6.6 145
6.7 群的陪集分解 145
6.7.1 陪集 146
6.7.2 拉格朗日定理 147
思考與練習(xí)6.7 148
6.8 環(huán)和域 148
6.8.1 環(huán)與整環(huán) 148
6.8.2 域 150
思考與練習(xí)6.8 150
6.9 格 151
6.9.1 格與其誘導(dǎo)的代數(shù)系統(tǒng) 151
6.9.2 子格 153
6.9.3 幾種特殊格 153
思考與練習(xí)6.9 155
6.10 布爾代數(shù) 156
6.10.1 布爾代數(shù)的定義 156
6.10.2 二值布爾代數(shù) 157
思考與練習(xí)6.10 159
第7章 圖 160
7.1 圖的基本概念 160
7.1.1 圖及其組成 160
7.1.2 結(jié)點(diǎn)的度與握手定理 161
7.1.3 完全圖與正則圖 163
7.1.4 子圖、補(bǔ)圖與圖同構(gòu) 163
思考與練習(xí)7.1 165
7.2 圖的連通性 165
7.2.1 路與回路 165
7.2.2 無向圖的連通性 166
7.2.3 有向圖的連通性 167
思考與練習(xí)7.2 168




7.3 圖的矩陣表示 168
7.3.1 鄰接矩陣 168
7.3.2 關(guān)聯(lián)矩陣 170
思考與練習(xí)7.3 170
7.4 幾種特殊的圖 171
7.4.1 二部圖 171
7.4.2 歐拉圖 173
7.4.3 漢密爾頓圖 175
思考與練習(xí)7.4 176
7.5 平面圖 177
7.5.1 平面圖與歐拉定理 177
7.5.2 平面圖著色 179
思考與練習(xí)7.5 180
7.6 樹 180
7.6.1 無向樹 180
7.6.2 生成樹 182
7.6.3 *單源最短路徑 184
7.6.4 根樹 186
思考與練習(xí)7.6 189
第8章 初等數(shù)論基礎(chǔ) 190
8.1 整數(shù)除法與素數(shù) 190
8.1.1 整數(shù)除法與整除 190
8.1.2 素數(shù)與合數(shù) 191
8.1.3 最大公約數(shù)與最小公倍數(shù) 193
思考與練習(xí)8.1 196
8.2 同余與同余方程 196
8.2.1 模算術(shù)與同余 196
8.2.2 一次同余方程及方程組 198
思考與練習(xí)8.2 200
8.3 費(fèi)馬小定理與歐拉定理 201
8.3.1 費(fèi)馬小定理 201
8.3.2 *歐拉函數(shù)與歐拉定理 202
8.3.3 *RSA密碼系統(tǒng)原理 202
思考與練習(xí)8.3 204
附錄 符號索引 205
參考文獻(xiàn) 207