《離散數學及其套用》是2007年清華大學出版社出版的圖書，作者是周忠榮。本書系統闡述了離散數學的經典內容，包括命題邏輯、謂詞邏輯、集合、關係、代數系統、圖論等方面的基本知識。
基本介紹
- 書名：離散數學及其套用
- 作者：周忠榮
- ISBN：9787302165743
- 定價：30元
圖書信息,圖書簡介,目錄,
圖書信息
出版日期：2007-12-1
出版社：清華大學出版社
圖書簡介
本書根據計算機科學各專業的需要選擇內容、把握尺度，儘可能將離散數學知識和計算機科學中的實際問題相結合。本書編排新穎，每章通過定義、定理、實例、例等形式將內容有機結合、融會貫通，達到學練兼顧的目的。本書加入了機上實現內容，滿足了普通高校理工類本科生的實際需求。
本書書末還提供了離散數學常用符號、中英文名詞術語對照表、英中文名詞術語對照表以及習題答案與提示，能很好地幫助讀者理解和學習。
本書既可作為套用型本科和高職高專院校計算機科學各專業的教材，也可作為工程技術人員的參考書。
目錄
第1章 基礎知識1
1.1 集合的初步知識1
1.2 數學歸納法1
1.3 整數的基本性質2
1.3.1 整除2
1.3.2 素數3
1.3.3 帶餘除法4
1.3.4 最大公約數5
1.3.5 最低公倍數7
1.3.6 模運算8
1.3.7 同餘的套用10
1.4 序列的基本知識11
1.4.1 序列11
1.4.2 典型的整數序列12
1.4.3 序列求和13
1.5 計數15
1.5.1 加法原理和乘法原理15
1.5.2 排列與組合17
1.5.3 二項式定理21
1.5.4 鴿巢原理22
1.6 矩陣的初步知識23
1.6.1 矩陣的概念23
1.6.2 矩陣的加法和數乘25
1.6.3 矩陣的乘法26
1.6.4 轉置矩陣和逆矩陣27
1.7 本章小結28
1.8 習題28
第2章 命題邏輯31
2.1 命題與聯結詞31
2.1.1 命題31
2.1.2 邏輯聯結詞33
2.1.3 聯結詞的優先權37
2.1.4 命題符號化37
2.1.5 邏輯運算在計算機中的直接運用39
2.2 命題公式與等價演算41
2.2.1 命題公式及其層次41
2.2.2 命題公式的賦值42
2.2.3 等價式與等價演算45
2.2.4 等價演算的實際套用48
2.3 聯結詞的擴充與聯結詞完備集49
2.3.1 聯結詞的擴充49
2.3.2 與非、或非、異或的性質51
2.3.3 聯結詞完備集52
2.4 範式53
2.4.1 析取範式與合取範式53
2.4.2 主析取範式與主合取範式57
2.4.3 主範式的作用62
2.4.4 用主範式解答實際問題63
2.5 命題邏輯推理66
2.5.1 推理的形式結構66
2.5.2 推理的證明方法68
2.5.3 命題邏輯推理的實際套用71
2.6 本章小結72
2.7 習題73
第3章 謂詞邏輯76
3.1 謂詞邏輯的基本概念76
3.1.1 個體和謂詞76
3.1.2 量詞78
3.1.3 特性謂詞80
3.1.4 謂詞邏輯符號化81
3.2 謂詞公式與翻譯82
3.2.1 謂詞公式82
3.2.2 謂詞邏輯的翻譯83
3.3 變元的約束86
3.3.1 約束變元和自由變元86
3.3.2 約束變元的換名規則87
3.3.3 自由變元的代替規則88
3.4 謂詞公式的解釋與分類89
3.4.1 謂詞公式的解釋89
3.4.2 謂詞公式的分類90
3.5 謂詞邏輯的等價式和前束範式91
3.5.1 謂詞邏輯等價式91
3.5.2 前束範式94
3.6 謂詞邏輯推理95
3.6.1 推理定律95
3.6.2 推理規則97
3.6.3 謂詞邏輯推理例題98
3.7 程式正確性證明100
3.8 本章小結102
3.9 習題102
第4章 集合106
4.1 集合的基本概念106
4.1.1 集合及其表示方法106
4.1.2 集合間的關係108
4.1.3 特殊集合109
4.1.4 有限冪集元素的編碼表示110
4.2 集合的基本運算111
4.3 集合恆等式113
4.4 集合的劃分與覆蓋115
4.5 有窮集合的計數117
4.6 本章小結118
4.7 習題119
第5章 關係121
5.1 關係的概念與表示121
5.1.1 笛卡兒積121
5.1.2 二元關係的概念123
5.1.3 關係矩陣和關係圖125
5.2 複合關係和逆關係127
5.2.1 複合關係127
5.2.2 逆關係130
5.3 關係的性質131
5.4 關係的閉包135
5.5 等價關係和偏序關係136
5.5.1 等價關係136
5.5.2 偏序關係138
5.5.3 字典排序和拓撲排序141
5.6 函式143
5.6.1 函式的基本概念143
5.6.2 複合函式和逆函式145
5.6.3 幾個重要的函式147
5.7 二元關係的套用148
5.7.1 等價關係的套用149
5.7.2 函式的套用149
5.8 多元關係及其套用149
5.8.1 多元關係149
5.8.2 關係資料庫151
5.9 本章小結153
5.10 習題153
第6章 代數系統155
6.1 二元運算及其性質155
6.1.1 二元運算與一元運算155
6.1.2 二元運算的性質與特殊元素157
6.1.3 代數系統簡介162
6.1.4 典型例題分析163
6.2 半群與群164
6.2.1 半群、獨異點與群164
6.2.2 冪167
6.2.3 群的性質168
6.2.4 典型例題分析170
6.3 子群、循環群與置換群170
6.3.1 元素的周期170
6.3.2 子群171
6.3.3 循環群173
6.3.4 置換群176
6.4 陪集和正規子群178
6.4.1 陪集178
6.4.2 正規子群180
6.4.3 典型例題分析181
6.5 群的同態與同構182
6.5.1 基本概念182
6.5.2 基本性質183
6.6 環和域184
6.6.1 環184
6.6.2 域187
6.7 格187
6.7.1 格的定義187
6.7.2 格的性質189
6.7.3 幾種特殊的格191
6.8 布爾代數193
6.8.1 布爾代數及其性質193
6.8.2 布爾函式與布爾表達式196
6.9 套用實例196
6.9.1 門電路196
6.9.2 邏輯電路設計197
6.10 本章小結199
6.11 習題200
第7章 圖論204
7.1 圖的基本概念204
7.1.1 圖的定義204
7.1.2 特殊的圖207
7.1.3 子圖208
7.1.4 結點的度209
7.2 圖的連通性211
7.2.1 路徑和迴路211
7.2.2 無向圖的連通性212
7.2.3 有向圖的連通性212
7.2.4 歐拉圖213
7.2.5 哈密頓圖217
7.2.6 帶權圖的最短路217
7.3 圖的矩陣表示219
7.3.1 無向圖的關聯矩陣219
7.3.2 有向圖的關聯矩陣220
7.3.3 有向圖的鄰接矩陣220
7.3.4 無向圖的鄰接矩陣221
7.4 樹222
7.4.1 無向樹與生成樹222
7.4.2 有向樹224
7.4.3 最優二元樹226
7.4.4 前綴碼228
7.4.5 樹的遍歷230
7.5 本章小結231
7.6 習題232
第8章 算法與偽代碼234
8.1 算法概述234
8.2 判斷素數算法236
8.3 求最大數算法236
8.4 求最大公約數的歐幾里得算法237
8.5 求拓撲排序的算法237
8.6 求歐拉路的Fleury算法239
8.7 求最短路徑的Dijkstra算法240
8.8 求最小生成樹的Prim算法241
8.9 求最優二元樹的Huffman算法243
附錄A 離散數學常用符號245
附錄B 中英文名詞術語對照表250
附錄C 英中文名詞術語對照表263
附錄D 習題答案與提示275
參考文獻286
