工科離散數(shù)學

目 錄

第1章 命題邏輯1
1.1 命題1
思考與練習1.13
1.2 邏輯聯(lián)結詞3
1.2.1 基本聯(lián)結詞3
1.2.2 其他聯(lián)結詞6
思考與練習1.26
1.3 命題公式與真值表7
1.3.1 命題公式7
1.3.2 真值表8
思考與練習1.39
1.4 命題翻譯9
1.4.1 合取命題9
1.4.2 可兼與不可兼析取命題10
1.4.3 條件命題10
1.4.4 多聯(lián)結詞命題11
思考與練習1.413
1.5 命題公式的值與等價14
1.5.1 命題公式的分類14
1.5.2 命題公式的等價14
1.5.3 聯(lián)結詞的功能完備集17
1.5.4 由德摩根律到對偶原理17
思考與練習1.518
1.6 范式19
1.6.1 簡單的范式19
1.6.2 小項與大項20
1.6.3 主析取范式與主合取范式21
思考與練習1.623
1.7 推理理論24
1.7.1 蘊含與論證24
1.7.2 自然推理系統(tǒng)26
思考與練習1.733
第2章 謂詞邏輯34
2.1 謂詞、個體詞與量詞34
2.1.1 個體詞與謂詞34
2.1.2 量詞與量化36
思考與練習2.137
2.2 謂詞邏輯中的命題翻譯38
2.2.1 特殊化個體詞的命題38
2.2.2 量詞量化的命題39
思考與練習2.242
2.3 量詞約束與謂詞公式的解釋42
2.3.1 量詞對個體詞變元的作用42
2.3.2 謂詞公式的解釋與求值43
2.3.3 量詞與聯(lián)結詞的搭配44
思考與練習2.345
2.4 謂詞邏輯中的基本等價和蘊含
關系46
2.4.1 基本等價與蘊含關系46
2.4.2 利用等價關系計算前束范式49
思考與練習2.450
2.5 謂詞演算的推理理論50
思考與練習2.556
第3章 集合論基礎58
3.1 集合的概念與表示方法58
3.1.1 集合描述58
3.1.2 集合的包含與相等59
3.1.3 空集與全集60
3.1.4 集合的冪集62
思考與練習3.163
3.2 集合運算64
3.2.1 基本運算64
3.2.2 多集合的交與并66
思考與練習3.268
3.3 集合運算的性質(zhì)與證明方法69
3.3.1 集合運算的性質(zhì)與演算證明69
3.3.2 基于定義的集合運算證明
方法70
思考與練習3.373
3.4 序偶與笛卡爾積73
3.4.1 序偶與元組74
3.4.2 笛卡爾積74
思考與練習3.477
第4章 關系78
4.1 二元關系的含義與表示78
4.1.1 二元關系78
4.1.2 關系的矩陣和圖表示法80
思考與練習4.181
4.2 關系運算81
4.2.1 關系求逆與復合82
4.2.2 關系運算的性質(zhì)83
4.2.3 利用關系圖與關系矩陣實現(xiàn)
關系運算85
4.2.4 多關系的復合87
思考與練習4.289
4.3 關系的主要性質(zhì)89
4.3.1 自反與反自反關系89
4.3.2 對稱與反對稱關系90
4.3.3 傳遞關系92
4.3.4 特殊關系的判定92
思考與練習4.394
4.4 關系的閉包95
4.4.1 閉包的概念95
4.4.2 閉包計算96
思考與練習4.499
4.5 相容關系與等價關系100
4.5.1 集合的覆蓋與劃分100
4.5.2 相容與等價101
4.5.3 相容關系產(chǎn)生的完全覆蓋102
4.5.4 等價關系產(chǎn)生的劃分103
4.5.5 由覆蓋、劃分生成相容關系
和等價關系105
思考與練習4.5106
4.6 序關系107
4.6.1 體現(xiàn)部分次序的偏序關系107
4.6.2 哈斯圖107
4.6.3 偏序集的特殊元素110
思考與練習4.6112
第5章 函數(shù)114
5.1 從關系到函數(shù)114
5.1.1 函數(shù)的概念114
5.1.2 函數(shù)集115
5.1.3 特殊函數(shù)116
思考與練習5.1118
5.2 函數(shù)的逆與復合119
5.2.1 雙射的反函數(shù)119
5.2.2 函數(shù)的復合119
5.2.3 函數(shù)運算的性質(zhì)121
思考與練習5.2122
5.3 集合的基數(shù)123
5.3.1 集合等勢123
5.3.2 有限集與無限集124
5.3.3 可數(shù)集與不可數(shù)集124
5.3.4 基數(shù)比較126
思考與練習5.3127
第6章 運算與代數(shù)系統(tǒng)129
6.1 運算及其性質(zhì)129
6.1.1 n元運算129
6.1.2 二元運算的主要性質(zhì)130
思考與練習6.1132
6.2 二元運算中的特殊元素132
6.2.1 幺元132
6.2.2 零元133
6.2.3 逆元134
思考與練習6.2135
6.3 代數(shù)系統(tǒng)135
6.3.1 代數(shù)與子代數(shù)135
6.3.2 同態(tài)與同構136
思考與練習6.3138
6.4 半群與獨異點138
思考與練習6.4140
6.5 群與子群140
6.5.1 群的概念140
6.5.2 群的性質(zhì)141
6.5.3 子群142
思考與練習6.5144
6.6 循環(huán)群與置換群145
6.6.1 循環(huán)群145
6.6.2 置換群146
思考與練習6.6148
6.7 群的陪集分解149
6.7.1 陪集149
6.7.2 拉格朗日定理150
思考與練習6.7151
第7章 環(huán)、域、格和布爾代數(shù)152
7.1 環(huán)和域152
7.1.1 環(huán)152
7.1.2 域153
思考與練習7.1154
7.2 格155
7.2.1 格與其誘導的代數(shù)系統(tǒng)155
7.2.2 子格157
7.2.3 特殊格157
思考與練習7.2160
7.3 布爾代數(shù)161
7.3.1 布爾格誘導的布爾代數(shù)161
7.3.2 典型的布爾代數(shù)162
思考與練習7.3164
第8章 圖165
8.1 圖的基本概念165
8.1.1 圖的認知165
8.1.2 結點的度與握手定理166
8.1.3 完全圖與正則圖168
8.1.4 子圖、補圖與圖同構169
思考與練習8.1170
8.2 圖的連通性171
8.2.1 路與回路171
8.2.2 無向圖的連通性172
8.2.3 有向圖的連通性173
思考與練習8.2174
8.3 圖的矩陣表示174
8.3.1 鄰接矩陣174
8.3.2 關聯(lián)矩陣176
思考與練習8.3177
8.4 二部圖、歐拉圖與漢密爾頓圖177
8.4.1 二部圖177
8.4.2 歐拉圖179
8.4.3 漢密爾頓圖181
思考與練習8.4183
8.5 平面圖183
8.5.1 平面圖與歐拉定理183
8.5.2 平面圖的對偶圖186
8.5.3 平面圖的著色187
思考與練習8.5188
8.6 樹188
8.6.1 無向樹188
8.6.2 生成樹190
8.6.3 根樹192
思考與練習8.6195
附錄A 符號索引197
參考文獻199