目錄
第一部分 數(shù)理邏輯
第1章 命題邏輯 3
1.1 命題及聯(lián)結(jié)詞 3
1.1.1 命題的概念 3
1.1.2 命題聯(lián)結(jié)詞 5
1.1.3 命題的符號(hào)化 9
1.2 命題公式 9
1.2.1 命題公式的定義 9
1.2.2 命題公式的賦值與真值表 11
1.2.3 命題公式的類(lèi)型 12
1.3 命題公式等值演算 13
1.3.1 等值式與等值演算 13
1.3.2 范式 17
1.3.3 主范式 19
1.4 命題邏輯的推理理論 26
1.4.1 推理的形式結(jié)構(gòu)及推理規(guī)則 26
1.4.2 證明方法和策略 30
習(xí)題1 31
拓展練習(xí)1 34
第2章 謂詞邏輯 36
2.1 謂詞邏輯命題符號(hào)化 36
2.1.1 個(gè)體詞、謂詞 36
2.1.2 量詞 37
2.2 謂詞公式及解釋 38
2.2.1 基本定義 38
2.2.2 謂詞公式的解釋 39
2.2.3 謂詞公式的類(lèi)型 41
2.3 謂詞邏輯等值演算 42
2.3.1 等值式與等值演算 42
2.3.2 前束范式 44
2.4 謂詞邏輯的推理理論 45
2.4.1 推理的形式結(jié)構(gòu)及推理規(guī)則 45
2.4.2 證明方法和策略 46
習(xí)題2 48
拓展練習(xí)2 50
第二部分 集 合 論
第3章 集合論基礎(chǔ) 53
3.1 集合的基本概念 53
3.1.1 集合的概念及特征 53
3.1.2 集合間的關(guān)系 55
3.1.3 冪集合 56
3.2 集合的運(yùn)算與恒等式 57
3.2.1 集合的運(yùn)算 57
3.2.2 集合恒等式 58
3.3 有限集合的計(jì)數(shù)問(wèn)題 61
3.3.1 兩個(gè)有限集合的計(jì)數(shù)問(wèn)題 61
3.3.2 三個(gè)有限集合的計(jì)數(shù)問(wèn)題 62
3.3.3 n個(gè)有限集合的計(jì)數(shù)問(wèn)題 63
3.4 計(jì)算機(jī)表示集合的方法 64
習(xí)題3 66
拓展練習(xí)3 68
第4章 關(guān)系 69
4.1 關(guān)系的概念 69
4.1.1 有序?qū)?69
4.1.2 笛卡兒積 70
4.1.3 關(guān)系的定義 71
4.2 關(guān)系的表示、性質(zhì)及運(yùn)算 72
4.2.1 關(guān)系的表示方法 72
4.2.2 關(guān)系的性質(zhì) 74
4.2.3 關(guān)系的運(yùn)算 75
4.3 等價(jià)關(guān)系與劃分 82
4.3.1 等價(jià)關(guān)系 82
4.3.2 等價(jià)類(lèi)及其性質(zhì) 82
4.3.3 商集和劃分 83
4.4 偏序關(guān)系 84
4.4.1 偏序關(guān)系的定義 84
4.4.2 哈斯圖 85
4.4.3 偏序集中的特殊元素 87
4.4.4 拓?fù)渑判?88
習(xí)題4 88
拓展練習(xí)4 90
第5章 函數(shù)與集合的勢(shì) 91
5.1 函數(shù) 91
5.1.1 函數(shù)的定義 91
5.1.2 函數(shù)的類(lèi)型 92
5.1.3 常用函數(shù) 94
5.2 函數(shù)的運(yùn)算 95
5.2.1 函數(shù)的復(fù)合 95
5.2.2 函數(shù)的逆運(yùn)算 96
5.3 集合的勢(shì) 97
5.3.1 集合的等勢(shì) 98
5.3.2 可數(shù)集合與不可數(shù)集合 99
5.3.3 集合的優(yōu)勢(shì) 101
習(xí)題5 102
拓展練習(xí)5 102
第三部分 代數(shù)系統(tǒng)
第6章 代數(shù)系統(tǒng)的基本概念 107
6.1 運(yùn)算 107
6.1.1 運(yùn)算的定義與表示方法 107
6.1.2 二元運(yùn)算的性質(zhì) 110
6.1.3 二元運(yùn)算的特殊元素和消去律 111
6.2 代數(shù)系統(tǒng)簡(jiǎn)介 114
6.2.1 代數(shù)系統(tǒng)的定義 114
6.2.2 代數(shù)系統(tǒng)的分類(lèi) 114
6.2.3 子代數(shù)和積代數(shù) 115
6.2.4 代數(shù)系統(tǒng)的同態(tài)與同構(gòu) 116
習(xí)題6 117
拓展練習(xí)6 119
第7章 幾個(gè)典型的代數(shù)系統(tǒng) 120
7.1 半群和群 120
7.1.1 半群與獨(dú)異點(diǎn) 120
7.1.2 群 121
7.2 環(huán)與域 126
7.2.1 環(huán) 126
7.2.2 域 127
7.3 格與布爾代數(shù) 128
7.3.1 格 128
7.3.2 布爾代數(shù) 132
習(xí)題7 132
拓展練習(xí)7 134
第四部分 圖論
第8章 圖論基礎(chǔ) 139
8.1 圖的基本概念 139
8.1.1 圖的定義 139
8.1.2 頂點(diǎn)的度與握手定理 141
8.1.3 完全圖與正則圖 145
8.1.4 圖的同構(gòu) 146
8.1.5 子圖、補(bǔ)圖與圖的運(yùn)算 147
8.2 圖的連通性 148
8.2.1 通路與回路 149
8.2.2 無(wú)向圖的連通性 151
8.2.3 有向圖的連通性 152
8.3 圖的矩陣表示 153
8.3.1 關(guān)聯(lián)矩陣 153
8.3.2 鄰接矩陣 154
8.3.3 可達(dá)矩陣 157
8.4 圖的應(yīng)用 157
8.4.1 渡河問(wèn)題 158
8.4.2 均分問(wèn)題 158
8.4.3 賦權(quán)圖的最短通路問(wèn)題 159
8.4.4 通信網(wǎng)絡(luò)問(wèn)題 160
習(xí)題8 160
拓展練習(xí)8 161
第9章 樹(shù) 163
9.1 無(wú)向樹(shù)及其應(yīng)用 163
9.1.1 無(wú)向樹(shù)的定義和性質(zhì) 163
9.1.2 生成樹(shù) 165
9.1.3 最小生成樹(shù) 167
9.2 根樹(shù)及其應(yīng)用 168
9.2.1 根樹(shù)的定義及分類(lèi) 168
9.2.2 根樹(shù)的遍歷 170
9.2.3 最優(yōu)二元樹(shù)與哈夫曼編碼 172
9.2.4 根樹(shù)的應(yīng)用 174
習(xí)題9 177
拓展練習(xí)9 178
第10章 幾種特殊的圖 180
10.1 歐拉圖 180
10.1.1 歐拉圖的定義 180
10.1.2 歐拉圖的判定及歐拉回路的求解算法 181
10.1.3 歐拉圖的應(yīng)用 182
10.2 哈密頓圖 186
10.2.1 哈密頓圖的定義 186
10.2.2 哈密頓圖的判定 187
10.2.3 哈密頓圖的應(yīng)用 188
10.3 二部圖 189
10.3.1 二部圖的定義 189
10.3.2 二部圖的判定 190
10.3.3 二部圖的匹配及其應(yīng)用 191
10.4 平面圖 193
10.4.1 平面圖的定義及性質(zhì) 193
10.4.2 平面圖的判定 195
10.4.3 平面圖的應(yīng)用——著色問(wèn)題 197
習(xí)題10 199
拓展練習(xí)10 203
參考文獻(xiàn) 204