目 錄
第 1 章 命題邏輯 ····································································································.1
1.1 命題與聯(lián)結(jié)詞 ·····························································································.1
1.2 命題公式及其賦值 ······················································································.5
1.3 等值式 ·······································································································.8
1.4 析取范式與合取范式 ·················································································.10
1.4.1 范式的基本概念 ··············································································.10
1.4.2 主范式及其表示 ··············································································.12
1.4.3 主范式的求解 ··················································································.13
1.4.4 主范式的數(shù)量 ··················································································.15
1.5 聯(lián)結(jié)詞的完備集 ························································································.16
1.5.1 真值函數(shù) ·························································································.16
1.5.2 聯(lián)結(jié)詞完備集 ··················································································.17
1.6 命題邏輯的推理理論 ·················································································.18
1.6.1 推理的基本概念 ··············································································.18
1.6.2 推理定律和推理規(guī)則 ·······································································.19
1.6.3 命題邏輯的推理方法 ·······································································.19
1.7 命題邏輯的應(yīng)用 ························································································.23
1.7.1 命題公式在計(jì)算機(jī)中的表示 ·····························································.23
1.7.2 程序優(yōu)化 ·························································································.24
1.7.3 資源分配 ·························································································.24
1.7.4 計(jì)算機(jī)硬件電路設(shè)計(jì) ·······································································.25
1.8 命題邏輯實(shí)驗(yàn) ····························································································.25
習(xí)題 1 ···············································································································.27
第 2 章 一階邏輯 ···································································································.30
2.1 一階邏輯的基本概念 ·················································································.30
2.2 一階邏輯公式及其解釋 ··············································································.33
2.2.1 一階邏輯公式的符號(hào) ·······································································.33
2.2.2 一階邏輯公式的結(jié)構(gòu) ·······································································.34
2.2.3 量詞的轄域 ·····················································································.34
2.2.4 公式的解釋 ·····················································································.35
2.3 一階邏輯等值式及演算 ··············································································.37
2.4 一階邏輯前束范式 ·····················································································.38
2.5 一階邏輯的推理理論 ·················································································.39
2.6 一階邏輯實(shí)驗(yàn) ····························································································.43
習(xí)題 2 ···············································································································.43
第 3 章 集合論 ·······································································································.47
3.1 集合的基本概念 ························································································.47
3.2 集合的基本運(yùn)算 ························································································.50
3.3 有限集的計(jì)數(shù) ····························································································.54
3.4 集合論實(shí)驗(yàn) ·······························································································.55
習(xí)題 3 ···············································································································.57
第 4 章 二元關(guān)系 ···································································································.60
4.1 有序?qū)εc笛卡兒積 ·····················································································.60
4.2 二元關(guān)系的定義 ························································································.62
4.3 關(guān)系的運(yùn)算 ·······························································································.63
4.4 關(guān)系的性質(zhì) ·······························································································.67
4.4.1 性質(zhì)的定義 ·····················································································.67
4.4.2 性質(zhì)的判定 ·····················································································.70
4.5 關(guān)系的閉包 ·······························································································.72
4.5.1 閉包的基本概念 ··············································································.72
4.5.2 閉包的性質(zhì) ·····················································································.74
4.5.3 用 WarShall 算法求傳遞閉包 ····························································.74
4.6 等價(jià)關(guān)系 ···································································································.76
4.6.1 等價(jià)關(guān)系的概念 ··············································································.76
4.6.2 等價(jià)類 ····························································································.76
4.6.3 商集與劃分 ·····················································································.77
4.7 偏序關(guān)系 ···································································································.79
4.7.1 偏序關(guān)系的概念 ··············································································.79
4.7.2 哈斯圖 ····························································································.79
4.7.3 偏序集中的特殊元素 ·······································································.80
4.7.4 偏序關(guān)系的應(yīng)用 ··············································································.81
4.8 二元關(guān)系實(shí)驗(yàn) ····························································································.83
習(xí)題 4 ···············································································································.84
第 5 章 函數(shù) ··········································································································.86
5.1 函數(shù)的定義與性質(zhì) ·····················································································.86
5.1.1 函數(shù)的定義 ·····················································································.86
5.1.2 函數(shù)的性質(zhì) ·····················································································.88
5.2 函數(shù)的復(fù)合與反函數(shù) ·················································································.90
5.2.1 函數(shù)的復(fù)合 ·····················································································.90
5.2.2 反函數(shù) ····························································································.91
5.3 函數(shù)實(shí)驗(yàn) ···································································································.92
習(xí)題 5 ···············································································································.92
第 6 章 代數(shù)結(jié)構(gòu) ···································································································.94
6.1 運(yùn)算及其性質(zhì) ····························································································.94
6.1.1 代數(shù)的構(gòu)成 ·····················································································.94
6.1.2 二元運(yùn)算的性質(zhì) ··············································································.97
6.2 代數(shù)系統(tǒng) ···································································································.99
6.3 半群與群 ·································································································.102
6.4 子群 ········································································································.104
6.5 代數(shù)結(jié)構(gòu)實(shí)驗(yàn) ··························································································.107
習(xí)題 6 ·············································································································.108
第 7 章 特殊代數(shù)系統(tǒng) ··························································································.111
7.1 環(huán)與域 ····································································································.111
7.2 格的定義與性質(zhì) ······················································································.113
7.2.1 格的定義 ·······················································································.113
7.2.2 格的性質(zhì) ·······················································································.114
7.2.3 特殊的格 ·······················································································.115
7.3 布爾代數(shù) ·································································································.116
7.4 布爾代數(shù)的應(yīng)用 ······················································································.118
7.4.1 邏輯門電路 ···················································································.118
7.4.2 電路的極小化 ················································································.118
7.5 特殊代數(shù)系統(tǒng)實(shí)驗(yàn) ···················································································.119
習(xí)題 7 ·············································································································.120
第 8 章 圖 ············································································································.123
8.1 圖的基本概念 ··························································································.123
8.1.1 圖的概念 ·······················································································.123
8.1.2 握手定理 ·······················································································.125
8.1.3 圖的同構(gòu) ·······················································································.127
8.1.4 圖的運(yùn)算 ·······················································································.128
8.1.5 子圖與補(bǔ)圖 ···················································································.128
8.2 通路與回路 ·····························································································.129
8.3 圖的連通性 ·····························································································.130
8.3.1 無(wú)向圖的連通性 ············································································.130
8.3.2 有向圖的連通性 ············································································.132
8.4 圖的矩陣表示 ··························································································.133
8.5 圖的實(shí)驗(yàn) ·································································································.135
習(xí)題 8 ·············································································································.137
第 9 章 特殊圖及其應(yīng)用 ·······················································································.139
9.1 歐拉圖 ····································································································.139
9.1.1 歐拉圖的概念 ················································································.139
9.1.2 歐拉圖的判別法 ············································································.140
9.2 漢密爾頓圖 ·····························································································.141
9.3 平面圖 ····································································································.143
9.3.1 平面圖的基本定義 ·········································································.143
9.3.2 歐拉公式 ·······················································································.145
9.3.3 歐拉公式的推廣 ············································································.146
9.3.4 平面圖的判斷 ················································································.147
9.4 圖的應(yīng)用 ·································································································.148
9.4.1 最短路徑問(wèn)題 ················································································.148
9.4.2 中國(guó)郵遞員問(wèn)題 ············································································.150
9.5 特殊圖實(shí)驗(yàn) ·····························································································.152
習(xí)題 9 ·············································································································.153
第 10 章 樹(shù) ··········································································································.155
10.1 無(wú)向樹(shù) ··································································································.155
10.2 生成樹(shù)及應(yīng)用 ························································································.157
10.2.1 生成樹(shù)的基本概念 ·······································································.157
10.2.2 最小生成樹(shù) ··················································································.158
10.3 根樹(shù)及應(yīng)用 ···························································································.161
10.3.1 根樹(shù)的相關(guān)概念 ················································································.161
10.3.2 最優(yōu)二叉樹(shù) ······················································································.162
10.3.3 樹(shù)的遍歷 ·························································································.165
10.4 樹(shù)的實(shí)驗(yàn) ·······························································································.166
習(xí)題 10 ···········································································································.167
模擬卷 A ················································································································.169
模擬卷 B ················································································································.172
參考文獻(xiàn) ···············································································································.176