目錄
第1章命題邏輯1
1．1命題及聯結詞1
1．1．1命題1
1．1．2命題聯結詞2
1．2命題公式及其分類5
1．2．1命題公式6
1．2．2命題公式的解釋與真值表7
1．2．3命題公式的分類8
1．2．4命題公式的基本等價關繫10
1．3命題公式的範式13
1．3．1析取範式和合取範式14
1．3．2主析取範式和主合取範式14
1．4命題邏輯推理與證明技術18
1．4．1形式推理18
1．4．2推理規則18
1．4．3判定有效性的方法19
1．5其他聯結詞21
1．6命題邏輯的應用22
習題126
第2章謂詞邏輯28
2．1謂詞邏輯的基本概念28
2．1．1個體詞與謂詞28
2．1．2量詞30
2．1．3謂詞的翻譯31
2．2謂詞公式與解釋32
2．2．1謂詞的合式公式32
2．2．2和33
2．2．3謂詞公式的解釋34
2．2．4謂詞公式的分類35
2．2．5謂詞公式的基本等值式35
2．3謂詞公式的範式37
2．3．1謂詞公式的前束範式37
2．3．2Skolem標準型38
2．4謂詞邏輯推理38
2．4．1謂詞邏輯的推理38
2．4．2謂詞邏輯推理方法39
2．5謂詞邏輯的應用41
習題245
第3章集合與關繫48
3．1集合的基本概念48
3．1．1素48
3．1．2集合間的關繫49
3．2集合的運算50
3．3容斥原理51
3．4序偶與笛卡兒積53
3．4．1序偶53
3．4．2笛卡兒積54
3．5關繫及其表示56
3．5．1關繫的定義56
3．5．2關繫的表示57
3．5．3幾種特殊的關繫58
3．6關繫的性質及其判定方法59
3．6．1關繫的性質59
3．6．2關繫性質的判定60
3．7復合關繫和逆關繫62
3．7．1復合關繫62
3．7．2復合關繫的矩陣表示及圖形表示64
3．7．3逆關繫66
3．8關繫的閉包運算68
3．9等價關繫與相容關繫71
3．9．1集合的劃分和覆蓋71
3．9．2等價關繫與等價類72
3．9．3相容關繫75
3．10偏序關繫77
3．10．1偏序關繫的定義77
3．10．2偏序關繫的哈斯圖77
3．10．3偏序集素79
3．10．4兩種特殊的偏序集81
3．11集合和關繫的應用81
3．11．1關繫在關繫數據庫中的應用81
3．11．2等價關繫的應用84
3．11．3同餘關繫和偏序關繫的應用85
習題387
第4章函數89
4．1函數的概念89
4．2特殊函數92
4．3復合函數和反函數94
4．3．1復合函數94
4．3．2反函數96
4．4置換98
4．5基數99
4．5．1限集合99
4．5．2基數的概念100
4．5．3可數集與不可數集101
4．6 函數的應用104
4．6．1一些有趣的雙射函數104
4．6．2哈希函數105
習題4110
第5章圖的基本理論112
5．1圖的定義及相關概念112
5．1．1圖的定義及其表示113
5．1．2圖的同構114
5．1．3子圖115
5．1．4圖的運算116
5．2通路、回路與連通性117
5．2．1通路、回路117
5．2．2向圖的連通性118
5．2．3有向圖的連通性119
5．3圖的矩陣表示120
5．3．1圖的關聯矩陣120
5．3．2圖的鄰接矩陣121
5．3．3可達矩陣123
5．4圖中通路的應用124
習題5125
第6章特殊圖128
6．1樹128
6．1．1向樹及其性質128
6．1．2生成樹與最小生成樹130
6．1．3根樹的基本概念133
6．1．4最優樹134
6．1．5二叉樹的遍歷135
6．2歐拉圖135
6．3哈密頓圖138
6．4二部圖141
6．4．1二部圖定義及其判定定理141
6．4．2二部圖中的匹配141
6．5平面圖143
6．5．1平面圖的基本概念143
6．5．2歐拉公式144
6．5．3平面圖的判斷定理145
6．5．4平面圖的對偶圖146
6．6特殊圖的應用147
6．6．1根樹的應用147
6．6．2歐拉圖的應用150
6．6．3哈密頓圖的應用152
6．6．4二部圖的應用154
習題6155
第7章代數繫統基礎158
7．1代數運算158
7．1．1什麼是運算158
7．1．2運算的定義159
7．2代數繫統及運算的性質161
7．2．1代數繫統161
7．2．運算的性質161
7．3代數繫統中及子代數繫統163
7．3．1代數繫統中163
7．3．2子代數繫統166
7．4代數繫統的同態與同構166
7．5常用的代數繫統分類169
習題7171
第8章幾個典型的代數繫統174
8．1半群與幺半群174
8．1．1半群和循環半群174
8．1．2幺半群與循環幺半群175
8．2群176
8．2．1群的定義及性質177
8．2．2子群及同態181
8．2．3特殊群183
8．2．4陪集與拉格朗日定理185
8．3環與域188
8．3．1環與域的定義188
8．3．2環與域的性質189
8．3．3子環及環同態190
8．4格與布爾代數191
8．4．1格的概念與性質192
8．4．2子格及格同態195
8．4．3幾種特殊格197
8．4．4布爾代數200
8．4．5布爾表達式203
8．5典型代數繫統的應用204
8．5．1半群的應用——有窮(限)自動機204
8．5．2群論的應用——糾錯碼208
8．5．3布爾代數的應用——全加器的電路設計216
習題8219
