本書從應用的角度介紹離散數(shù)學。
全書共分6章,分別是命題邏輯、謂詞邏輯、集合與關系、代數(shù)結構、圖和有向圖。全書體系嚴謹,內容講解深入淺出,并配有大量與計算機科學相關的有實際背景的例題和習題。在每章后增加了上機作業(yè),可增強學生對課堂教學內容的理解和掌握,提高學生的學習興趣和動手能力。全書以二維碼的形式提供了教學視頻,有利于教師進行線上線下混合式教學,幫助學生更好地學習、理解和應用離散數(shù)學理論。
本書可作為普通高等學校計算機科學與技術或相關專業(yè)的本科生教材。
1.本書為浙江省普通高校十三五新形態(tài)教材。
2.本書配有微課視頻,易教利學。
3.本書例題、習題豐富,有上機作業(yè),配套課件、習題答案;
4.本書課件中有機融入了課程思政元素。
方景龍,博士,教師,博士生導師,現(xiàn)任杭州電子科技大學計算機學院副院長。第3屆中國電子裝備技術協(xié)會理事,第5屆全高校實驗室工作研究會理事。
第 1章 命題邏輯1
1.1 命題和邏輯連接詞 2
1.1.1 命題 2
1.1.2 邏輯連接詞與命題符號化 4
習題1.1 7
1.2 命題公式及其真值表 8
1.2.1 命題公式 8
1.2.2 真值表 9
習題1.2 11
1.3 命題公式的等價演算 12
習題1.3 15
1.4 命題公式的范式 15
1.4.1 析取范式與合取范式 15
1.4.2 標準析取范式和標準合取范式 18
1.4.3 利用真值表求解標準范式 20
1.4.4 標準析取范式和標準合取范式的關系 22
習題1.4 24
1.5 命題公式的推理演算 25
1.5.1 基本概念 25
1.5.2 演繹推理方法 27
1.5.3 附加前提法 29
習題1.5 31
1.6 邏輯門電路 32
1.6.1 門電路 32
1.6.2 邏輯電路設計 34
習題1.6 36
1.7 本章小結……………………………………………………………………………… 36
第 1章上機練習 37
第 2章 謂詞邏輯 38
2.1 個體詞、謂詞與量詞 38
2.1.1 個體詞與謂詞 38
2.1.2 量詞 39
習題2.1 42
2.2 謂詞公式及其解釋 43
2.2.1 謂詞公式 43
2.2.2 謂詞公式的解釋 45
習題2.2 48
2.3 謂詞公式的等價演算 49
習題2.3 52
2.4 謂詞公式的推理演算 52
2.4.1 基本概念 51
2.4.2 演繹推理方法 53
習題2.4 57
2.5 本章小結……………………………………………………………………………… 59
第 2章上機練習 59
第3章 集合與關系 60
3.1 集合及其運算 61
3.1.1 基本概念 61
3.1.2 集合的運算 63
3.1.3 集合的計算機表示 66
習題3.1 66
3.2 二元關系及其運算 68
3.2.1 笛卡兒積 68
3.2.2 二元關系及其表示 69
3.2.3 二元關系的運算 71
習題3.2 74
3.3 二元關系的性質與閉包 75
3.3.1 二元關系的性質 75
3.3.2 二元關系的閉包 77
習題3.3 80
3.4 等價關系與劃分 81
習題3.4 84
3.5 偏序關系與拓撲排序 85
3.5.1 偏序關系 85
3.5.2 偏序集中的特殊元 87
3.5.3 拓撲排序 89
習題3.5 90
3.6 函數(shù) 92
3.6.1 基本概念 92
3.6.2 復合函數(shù) 94
3.6.3 逆函數(shù) 95
3.6.4 幾個重要的函數(shù)………………………………………………………………. 96
習題3.6 96
3.7 集合的等勢與基數(shù) 98
習題3.7 99
3.8 多元關系及其應用 99
3.8.1 多元關系 99
3.8.2 關系數(shù)據(jù)庫 100
3.8.3 數(shù)據(jù)庫的檢索 101
3.8.4 插入、刪除與修改 102
習題3.8 104
3.9本章小結………………………………………………………………………………..104
第3章上機練習 104
第4章 代數(shù)結構 106
4.1 代數(shù)運算 106
4.1.1 基本概念 106
4.1.2 二元運算的性質 107
4.1.3 二元運算中的特殊元 108
習題4.1 110
4.2 代數(shù)系統(tǒng) 111
習題4.2 114
4.3 群 115
4.3.1 基本概念 115
4.3.2 冪運算 116
4.3.3 群的性質 118
習題4.3 121
4.4 循環(huán)群、置換群 122
4.4.1 循環(huán)群 122
4.4.2 置換群 123
習題4.4 126
4.5 子群與陪集 127
4.5.1 子群 127
4.5.2 陪集 128
4.5.3 正規(guī)子群與商群 131
4.5.4 群同態(tài)與同構 132
習題4.5 133
4.6 環(huán)與域 134
4.6.1 環(huán) 135
4.6.2 整環(huán)與域 136
習題4.6 137
4.7 格與布爾代數(shù) 138
4.7.1 格 138
4.7.1 幾種特殊的格 139
4.7.2 布爾代數(shù) 141
習題4.7 142
4.8本章小結 142
第4章上機練習 143
第5章 圖 145
5.1 基本概念 145
5.1.1 圖的定義 145
5.1.2 頂點的度 147
習題5.1 149
5.2 圖的連通性 149
5.2.1 通路 149
5.2.2 連通圖 151
習題5.2 154
5.3 樹 155
5.3.1 基本概念 155
5.3.2 生成樹 157
習題5.3 159
5.4 圖的遍歷 159
5.4.1 圖的矩陣表示 159
5.4.2 廣度優(yōu)先搜索 163
5.4.3 深度優(yōu)先搜索 166
5.4.4 小生成樹…………………………………………………………………....169
習題5.4 172
5.5 歐拉圖與哈密爾頓圖 174
5.5.1 歐拉圖 174
5.5.2 哈密爾頓圖 177
5.5.3 旅行商問題 180
習題5.5 180
5.6 平面圖及圖的著色 181
5.6.1 平面圖 181
5.6.2 圖的點著色 185
習題5.6 187
5.7 本章小結 188
第5章上機練習 189
第6章 有向圖 190
6.1有向圖概述 190
6.1.1 基本概念 190
6.1.2 有向圖的連通性 191
6.1.3 有向圖的矩陣表示 193
習題6.1 195
6.2 短路徑 196
6.2.1 Dijkstra算法 196
6.2.2 Floyd算法 199
6.2.3 中國郵遞員問題 199
習題6.2 200
6.3 根樹 201
6.3.1 基本概念 201
6.3.2 二叉搜索樹 203
6.3.3 二叉樹 205
習題6.3 209
6.4 網(wǎng)絡流 210
6.4.1 基本概念 210
6.4.2 流算法 212
6.4.3 流小割定理 218
習題6.4 219
6.5 匹配 220
習題6.5 223
6.6 本章小結……………………………………………………………………………...224
第6章上機練習 224
參考文獻 226