目 錄

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




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