第 1章 命題邏輯1
1.1 命題和邏輯連接詞 2
1.1.1 命題 2
1.1.2 邏輯連接詞與命題符號化 4
習(xí)題1.1 7
1.2 命題公式及其真值表 8
1.2.1 命題公式 8
1.2.2 真值表 9
習(xí)題1.2 11
1.3 命題公式的等價(jià)演算 12
習(xí)題1.3 15
1.4 命題公式的范式 15
1.4.1 析取范式與合取范式 15
1.4.2 標(biāo)準(zhǔn)析取范式和標(biāo)準(zhǔn)合取范式 18
1.4.3 利用真值表求解標(biāo)準(zhǔn)范式 20
1.4.4 標(biāo)準(zhǔn)析取范式和標(biāo)準(zhǔn)合取范式的關(guān)系 22
習(xí)題1.4 24
1.5 命題公式的推理演算 25
1.5.1 基本概念 25
1.5.2 演繹推理方法 27
1.5.3 附加前提法 29
習(xí)題1.5 31
1.6 邏輯門電路 32
1.6.1 門電路 32
1.6.2 邏輯電路設(shè)計(jì) 34
習(xí)題1.6 36
1.7 本章小結(jié)……………………………………………………………………………… 36
第 1章上機(jī)練習(xí) 37
第 2章 謂詞邏輯 38
2.1 個(gè)體詞、謂詞與量詞 38
2.1.1 個(gè)體詞與謂詞 38
2.1.2 量詞 39
習(xí)題2.1 42
2.2 謂詞公式及其解釋 43
2.2.1 謂詞公式 43
2.2.2 謂詞公式的解釋 45
習(xí)題2.2 48
2.3 謂詞公式的等價(jià)演算 49
習(xí)題2.3 52
2.4 謂詞公式的推理演算 52
2.4.1 基本概念 51
2.4.2 演繹推理方法 53
習(xí)題2.4 57
2.5 本章小結(jié)……………………………………………………………………………… 59
第 2章上機(jī)練習(xí) 59
第3章 集合與關(guān)系 60
3.1 集合及其運(yùn)算 61
3.1.1 基本概念 61
3.1.2 集合的運(yùn)算 63
3.1.3 集合的計(jì)算機(jī)表示 66
習(xí)題3.1 66
3.2 二元關(guān)系及其運(yùn)算 68
3.2.1 笛卡兒積 68
3.2.2 二元關(guān)系及其表示 69
3.2.3 二元關(guān)系的運(yùn)算 71
習(xí)題3.2 74
3.3 二元關(guān)系的性質(zhì)與閉包 75
3.3.1 二元關(guān)系的性質(zhì) 75
3.3.2 二元關(guān)系的閉包 77
習(xí)題3.3 80
3.4 等價(jià)關(guān)系與劃分 81
習(xí)題3.4 84
3.5 偏序關(guān)系與拓?fù)渑判?85
3.5.1 偏序關(guān)系 85
3.5.2 偏序集中的特殊元 87
3.5.3 拓?fù)渑判?89
習(xí)題3.5 90
3.6 函數(shù) 92
3.6.1 基本概念 92
3.6.2 復(fù)合函數(shù) 94
3.6.3 逆函數(shù) 95
3.6.4 幾個(gè)重要的函數(shù)………………………………………………………………. 96
習(xí)題3.6 96
3.7 集合的等勢與基數(shù) 98
習(xí)題3.7 99
3.8 多元關(guān)系及其應(yīng)用 99
3.8.1 多元關(guān)系 99
3.8.2 關(guān)系數(shù)據(jù)庫 100
3.8.3 數(shù)據(jù)庫的檢索 101
3.8.4 插入、刪除與修改 102
習(xí)題3.8 104
3.9本章小結(jié)………………………………………………………………………………..104
第3章上機(jī)練習(xí) 104
第4章 代數(shù)結(jié)構(gòu) 106
4.1 代數(shù)運(yùn)算 106
4.1.1 基本概念 106
4.1.2 二元運(yùn)算的性質(zhì) 107
4.1.3 二元運(yùn)算中的特殊元 108
習(xí)題4.1 110
4.2 代數(shù)系統(tǒng) 111
習(xí)題4.2 114
4.3 群 115
4.3.1 基本概念 115
4.3.2 冪運(yùn)算 116
4.3.3 群的性質(zhì) 118
習(xí)題4.3 121
4.4 循環(huán)群、置換群 122
4.4.1 循環(huán)群 122
4.4.2 置換群 123
習(xí)題4.4 126
4.5 子群與陪集 127
4.5.1 子群 127
4.5.2 陪集 128
4.5.3 正規(guī)子群與商群 131
4.5.4 群同態(tài)與同構(gòu) 132
習(xí)題4.5 133
4.6 環(huán)與域 134
4.6.1 環(huán) 135
4.6.2 整環(huán)與域 136
習(xí)題4.6 137
4.7 格與布爾代數(shù) 138
4.7.1 格 138
4.7.1 幾種特殊的格 139
4.7.2 布爾代數(shù) 141
習(xí)題4.7 142
4.8本章小結(jié) 142
第4章上機(jī)練習(xí) 143
第5章 圖 145
5.1 基本概念 145
5.1.1 圖的定義 145
5.1.2 頂點(diǎn)的度 147
習(xí)題5.1 149
5.2 圖的連通性 149
5.2.1 通路 149
5.2.2 連通圖 151
習(xí)題5.2 154
5.3 樹 155
5.3.1 基本概念 155
5.3.2 生成樹 157
習(xí)題5.3 159
5.4 圖的遍歷 159
5.4.1 圖的矩陣表示 159
5.4.2 廣度優(yōu)先搜索 163
5.4.3 深度優(yōu)先搜索 166
5.4.4 小生成樹…………………………………………………………………....169
習(xí)題5.4 172
5.5 歐拉圖與哈密爾頓圖 174
5.5.1 歐拉圖 174
5.5.2 哈密爾頓圖 177
5.5.3 旅行商問題 180
習(xí)題5.5 180
5.6 平面圖及圖的著色 181
5.6.1 平面圖 181
5.6.2 圖的點(diǎn)著色 185
習(xí)題5.6 187
5.7 本章小結(jié) 188
第5章上機(jī)練習(xí) 189
第6章 有向圖 190
6.1有向圖概述 190
6.1.1 基本概念 190
6.1.2 有向圖的連通性 191
6.1.3 有向圖的矩陣表示 193
習(xí)題6.1 195
6.2 短路徑 196
6.2.1 Dijkstra算法 196
6.2.2 Floyd算法 199
6.2.3 中國郵遞員問題 199
習(xí)題6.2 200
6.3 根樹 201
6.3.1 基本概念 201
6.3.2 二叉搜索樹 203
6.3.3 二叉樹 205
習(xí)題6.3 209
6.4 網(wǎng)絡(luò)流 210
6.4.1 基本概念 210
6.4.2 流算法 212
6.4.3 流小割定理 218
習(xí)題6.4 219
6.5 匹配 220
習(xí)題6.5 223
6.6 本章小結(jié)……………………………………………………………………………...224
第6章上機(jī)練習(xí) 224
參考文獻(xiàn) 226