目 錄

第1章 命題邏輯 1
1.1 命題 1
思考與練習1.1 3
1.2 邏輯聯結詞 3
1.2.1 基本聯結詞 3
1.2.2 其他聯結詞 6
思考與練習1.2 6
1.3 命題公式與真值表 7
1.3.1 命題公式 7
1.3.2 真值表 8
思考與練習1.3 9
1.4 命題翻譯 9
1.4.1 合取命題 9
1.4.2 可兼與不可兼析取命題 10
1.4.3 條件命題 10
1.4.4 多聯結詞命題 11
思考與練習1.4 13
1.5 命題公式的值與等價 14
1.5.1 命題公式的分類 14
1.5.2 命題公式的等價 14
1.5.3 聯結詞的功能完備集 17
1.5.4 由德?摩根律到對偶原理 17
思考與練習1.5 18
1.6 范式 19
1.6.1 簡單的范式 19
1.6.2 小項與大項 20
1.6.3 主析取范式與主合取范式 21
思考與練習1.6 23
1.7 推理理論 24
1.7.1 蘊含與論證 24
1.7.2 自然推理系統 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 量詞量化的命題 39
思考與練習2.2 42
2.3 量詞約束與謂詞公式的解釋 42
2.3.1 量詞對個體詞變元的作用 42
2.3.2 謂詞公式的解釋與求值 43
2.3.3 量詞與聯結詞的搭配 44
思考與練習2.3 45
2.4 謂詞邏輯中的基本等價和蘊含
關系 46
2.4.1 基本等價與蘊含關系 46
2.4.2 利用等價關系計算前束范式 49
思考與練習2.4 50
2.5 謂詞演算的推理理論 50
思考與練習2.5 56
第3章 集合論基礎 58
3.1 集合的概念與表示方法 58
3.1.1 集合描述 58
3.1.2 集合的包含與相等 59
3.1.3 空集與全集 60
3.1.4 集合的冪集 62
思考與練習3.1 63
3.2 集合運算 64
3.2.1 基本運算 64
3.2.2 多集合的交與并 66
思考與練習3.2 68
3.3 集合運算的性質與證明方法 69
3.3.1 集合運算的性質與演算證明 69
3.3.2 基于定義的集合運算證明
方法 70
思考與練習3.3 73
3.4 序偶與笛卡爾積 73
3.4.1 序偶與元組 74
3.4.2 笛卡爾積 74
思考與練習3.4 77
第4章 關系 78
4.1 二元關系的含義與表示 78
4.1.1 二元關系 78
4.1.2 關系的矩陣和圖表示法 80
思考與練習4.1 81
4.2 關系運算 81
4.2.1 關系求逆與復合 82
4.2.2 關系運算的性質 83
4.2.3 利用關系圖與關系矩陣實現
關系運算 85
4.2.4 多關系的復合 87
思考與練習4.2 89
4.3 關系的主要性質 89
4.3.1 自反與反自反關系 89
4.3.2 對稱與反對稱關系 90
4.3.3 傳遞關系 92
4.3.4 特殊關系的判定 92
思考與練習4.3 94
4.4 關系的閉包 95
4.4.1 閉包的概念 95
4.4.2 閉包計算 96
思考與練習4.4 99
4.5 相容關系與等價關系 100
4.5.1 集合的覆蓋與劃分 100
4.5.2 相容與等價 101
4.5.3 相容關系產生的完全覆蓋 102
4.5.4 等價關系產生的劃分 103
4.5.5 由覆蓋、劃分生成相容關系
和等價關系 105
思考與練習4.5 106
4.6 序關系 107
4.6.1 體現部分次序的偏序關系 107
4.6.2 哈斯圖 107
4.6.3 偏序集的特殊元素 110
思考與練習4.6 112
第5章 函數 114
5.1 從關系到函數 114
5.1.1 函數的概念 114
5.1.2 函數集 115
5.1.3 特殊函數 116
思考與練習5.1 118
5.2 函數的逆與復合 119
5.2.1 雙射的反函數 119
5.2.2 函數的復合 119
5.2.3 函數運算的性質 121
思考與練習5.2 122
5.3 集合的基數 123
5.3.1 集合等勢 123
5.3.2 有限集與無限集 124
5.3.3 可數集與不可數集 124
5.3.4 基數比較 126
思考與練習5.3 127
第6章 運算與代數系統 129
6.1 運算及其性質 129
6.1.1 n元運算 129
6.1.2 二元運算的主要性質 130
思考與練習6.1 132
6.2 二元運算中的特殊元素 132
6.2.1 幺元 132
6.2.2 零元 133
6.2.3 逆元 134
思考與練習6.2 135
6.3 代數系統 135
6.3.1 代數與子代數 135
6.3.2 同態與同構 136
思考與練習6.3 138
6.4 半群與獨異點 138
思考與練習6.4 140
6.5 群與子群 140
6.5.1 群的概念 140
6.5.2 群的性質 141
6.5.3 子群 142
思考與練習6.5 144
6.6 循環群與置換群 145
6.6.1 循環群 145
6.6.2 置換群 146
思考與練習6.6 148
6.7 群的陪集分解 149
6.7.1 陪集 149
6.7.2 拉格朗日定理 150
思考與練習6.7 151
第7章 環、域、格和布爾代數 152
7.1 環和域 152
7.1.1 環 152
7.1.2 域 153
思考與練習7.1 154
7.2 格 155
7.2.1 格與其誘導的代數系統 155
7.2.2 子格 157
7.2.3 特殊格 157
思考與練習7.2 160
7.3 布爾代數 161
7.3.1 布爾格誘導的布爾代數 161
7.3.2 典型的布爾代數 162
思考與練習7.3 164
第8章 圖 165
8.1 圖的基本概念 165
8.1.1 圖的認知 165
8.1.2 結點的度與握手定理 166
8.1.3 完全圖與正則圖 168
8.1.4 子圖、補圖與圖同構 169
思考與練習8.1 170
8.2 圖的連通性 171
8.2.1 路與回路 171
8.2.2 無向圖的連通性 172
8.2.3 有向圖的連通性 173
思考與練習8.2 174
8.3 圖的矩陣表示 174
8.3.1 鄰接矩陣 174
8.3.2 關聯矩陣 176
思考與練習8.3 177
8.4 二部圖、歐拉圖與漢密爾頓圖 177
8.4.1 二部圖 177
8.4.2 歐拉圖 179
8.4.3 漢密爾頓圖 181
思考與練習8.4 183
8.5 平面圖 183
8.5.1 平面圖與歐拉定理 183
8.5.2 平面圖的對偶圖 186
8.5.3 平面圖的著色 187
思考與練習8.5 188
8.6 樹 188
8.6.1 無向樹 188
8.6.2 生成樹 190
8.6.3 根樹 192
思考與練習8.6 195
附錄A 符號索引 197
參考文獻 199