目錄
前言
第一章 命題邏輯 1
1.1 命題和聯(lián)結(jié)詞 1
1.1.1 命題 1
1.1.2 命題聯(lián)結(jié)詞 2
1.1.3 命題表達(dá)式 5
1.1.4 真值表的構(gòu)造 6
1.1.5 命題符號(hào)化 7
1.2 重言式 8
1.2.1 命題公式分類 8
1.2.2 重言式 9
1.2.3 邏輯等價(jià) 9
1.2.4 代入規(guī)則與替換規(guī)則 11
1.2.5 對(duì)偶原理 13
1.3 公式中的范式 15
1.3.1 析取范式和合取范式 15
1.3.2 主析取范式 17
1.3.3 主合取范式 21
1.4 命題聯(lián)結(jié)詞的擴(kuò)充與歸約 23
1.4.1 命題聯(lián)結(jié)詞的擴(kuò)充 24
1.4.2 命題聯(lián)結(jié)詞的歸約 25
1.5 基于命題的推理 26
1.5.1 基于真值表的推理 26
1.5.2 基于推理規(guī)則的推理 27
1.5.3 應(yīng)用實(shí)例 28
1.6 習(xí)題 31
第二章 謂詞邏輯 34
2.1 謂詞公式 34
2.1.1 個(gè)體詞 34
2.1.2 謂詞 34
2.1.3 量詞 35
2.1.4 命題符號(hào)化 35
2.1.5 謂詞公式 36？
2.2 約束 36
2.2.1 約束部分 36
2.2.2 換名規(guī)則和代替規(guī)則 37
2.2.3 公式的解釋 37
2.3 謂詞公式中的永真式 38
2.3.1 謂詞公式的等價(jià) 38
2.3.2 謂詞公式的類型 39
2.4 謂詞公式中的范式 40
2.5 謂詞推理 40
2.5.1 推理規(guī)則 41
2.5.2 舉例 41
2.6 習(xí)題 42
第三章 集合論 44
3.1 基本概念 44
3.1.1 集合的概念 44
3.1.2 集合的表示方法 44
3.1.3 元素與集合 45
3.2 集合間的關(guān)系 46
3.3 集合的運(yùn)算 48
3.3.1 集合的基本運(yùn)算 48
3.3.2 集合的運(yùn)算律 50
3.3.3 例題 52
3.4 包含排斥原理 53
3.5 冪集合與笛卡兒積 56
3.5.1 冪集合 56
3.5.2 笛卡兒積 57
3.6 集合運(yùn)算與基數(shù)概念的擴(kuò)展 59
3.6.1 并集、交集的擴(kuò)展 59
3.6.2 基數(shù)概念的擴(kuò)展 60
3.7 習(xí)題 61
第四章 二元關(guān)系 64
4.1 基本概念 64
4.1.1 二元關(guān)系的定義 64
4.1.2 關(guān)系的表示 66
4.2 關(guān)系的運(yùn)算 66
4.2.1 關(guān)系的并、交、補(bǔ)、差、對(duì)稱差運(yùn)算 66
4.2.2 關(guān)系的復(fù)合運(yùn)算 67
4.2.3 關(guān)系的逆運(yùn)算 69？
4.3 關(guān)系的性質(zhì) 70
4.3.1 關(guān)系性質(zhì)的概念 70
4.3.2 關(guān)系性質(zhì)舉例 71
4.3.3 關(guān)系性質(zhì)在關(guān)系圖及關(guān)系矩陣中的特征 71
4.4 關(guān)系的閉包 72
4.4.1 閉包的定義 72
4.4.2 關(guān)系R的閉包求法 72
4.4.3 傳遞閉包的Warshall算法 74
4.4.4 閉包的復(fù)合 76
4.5 集合的劃分和覆蓋 77
4.6 序關(guān)系 78
4.6.1 偏序關(guān)系與偏序集的概念 78
4.6.2 偏序集的哈斯圖 79
4.6.3 偏序集中的特殊元 80
4.6.4 全序集與良序集 81
4.7 等價(jià)關(guān)系與等價(jià)類 81
4.8 函數(shù) 84
4.8.1 函數(shù)的概念 84
4.8.2 逆函數(shù)與復(fù)合函數(shù) 86
4.9 習(xí)題 89
第五章 圖論 93
5.1 若干圖論經(jīng)典問題 93
5.1.1 哥尼斯堡七橋問題 93
5.1.2 四色問題和哈密頓環(huán)游世界問題 94
5.1.3 平面圖和印刷電路板的設(shè)計(jì) 94
5.1.4 運(yùn)輸網(wǎng)絡(luò) 95
5.1.5 通訊網(wǎng)絡(luò) 95
5.1.6 二叉樹的應(yīng)用 96
5.1.7 最短路問題 96
5.2 圖的基本概念及矩陣表示方法 96
5.2.1 圖的基本概念 96
5.2.2 圖的矩陣表示方法 100
5.3 路與連通度 102
5.4 歐拉圖與哈密頓圖 108
5.5 二部圖與匹配 110
5.6 平面圖 112
5.6.1 平面圖及其性質(zhì) 112
5.6.2 平面圖著色 115？
5.7 樹 116
5.7.1 樹及其性質(zhì) 116
5.7.2 最小生成樹 118
5.7.3 有向樹 120
5.8 習(xí)題 124
第六章 初等數(shù)論 128
6.1 整數(shù)和除法 128
6.2 整數(shù) 128
6.3 素?cái)?shù) 130
6.4 最大公約數(shù)和最小公倍數(shù) 133
6.5 同余 135
6.6 一次同余方程 137
6.7 中國剩余定理 138
6.8 歐拉定理和費(fèi)馬小定理 139
6.9 習(xí)題 140
第七章 代數(shù)系統(tǒng) 143
7.1 二元運(yùn)算及性質(zhì) 143
7.1.1 二元運(yùn)算的定義 143
7.1.2 二元運(yùn)算的性質(zhì) 144
7.2 代數(shù)系統(tǒng) 148
7.2.1 代數(shù)系統(tǒng)的定義與實(shí)例 148
7.2.2 代數(shù)系統(tǒng)的同構(gòu)與同態(tài) 149
7.3 半群 153
7.3.1 半群 153
7.3.2 單位元和逆元 155
7.4 群 158
7.4.1 群的定義 158
7.4.2 群的同態(tài) 162
7.4.3 循環(huán)群 164
7.4.4 變換群 168
7.4.5 置換群 170
7.4.6 子群 174
7.4.7 子群的陪集 178
7.4.8 正規(guī)子群和商群 181
7.5 環(huán)和域簡介 182
7.5.1 環(huán) 183
7.5.2 域 185
7.6 習(xí)題 186
參考文獻(xiàn) 190