《離散數學基礎》是清華大學出版社於2021年出版的書籍。
基本介紹
- 書名：離散數學基礎
- 作者：周曉聰、喬海燕
- 出版社：清華大學出版社
- 出版時間：2021年5月1日
- ISBN：9787302576679
內容簡介,圖書目錄,
內容簡介
本書面向“新工科”建設背景下普通高等學校的計算機類和軟體工程專業類的本科生，以培養學生離散建模基礎能力為目標，論述邏輯、證明、集合、函式、關係、算法、整數與同餘、組合計數、圖論以及代數系統相關基礎知識，覆蓋Computer Science Curricula 2013離散結構知識體的所有知識單元。與傳統離散數學教材相比，
圖書目錄
第1 章 基礎知識 1
1.1 邏輯語言 1
1.2 集合語言 5
1.3 圖論語言 9
1.4 代數語言 13
1.5 算法語言 14
1.6 本章小結 20
1.7 習題 21
第2 章 命題邏輯 24
2.1 命題邏輯的基本概念 24
2.1.1 命題與真值 24
2.1.2 原子命題與複合命題 25
2.2 命題邏輯公式的語法 25
2.2.1 命題邏輯公式的定義 26
2.2.2 命題邏輯公式的語法性質 28
2.2.3 命題邏輯公式的簡寫 31
2.3 命題邏輯公式的語義 32
2.3.1 命題邏輯公式的真值定義 32
2.3.2 命題邏輯公式的真值表 35
2.3.3 命題邏輯公式的分類 37
2.4 命題邏輯的等值演算 40
2.4.1 命題邏輯公式的邏輯等值 40
2.4.2 基本邏輯等值式 41
2.4.3 命題邏輯公式的範式 44
2.5 命題邏輯的推理理論 48
2.5.1 推理的有效性 49
2.5.2 命題邏輯的自然推理系統 50
2.5.3 構造驗證推理有效性的論證 54
2.6 命題邏輯的套用 60
2.6.1 自然語言命題的符號化 60
2.6.2 普通邏輯問題的符號化分析 67
2.6.3 算法性質的邏輯分析 73
2.7 本章小結 75
2.8 習題 75
第3 章 一階邏輯 81
3.1 一階邏輯的基本概念 81
3.2 一階邏輯公式的語法 83
3.2.1 一階邏輯公式的符號 83
3.2.2 一階邏輯公式的定義 84
3.2.3 自由變數和約束變數 86
3.3 一階邏輯公式的語義 89
3.3.1 一階邏輯公式的解釋 89
3.3.2 一階邏輯公式的真值 91
3.3.3 一階邏輯公式的分類 97
3.4 一階邏輯的等值演算 100
3.4.1 一階邏輯公式的邏輯等值 100
3.4.2 量詞公式的基本等值式 103
3.4.3 一階邏輯的前束範式 106
3.5 一階邏輯的推理理論 110
3.5.1 一階邏輯推理的有效性 110
3.5.2 量詞公式的推理規則 112
3.5.3 一階邏輯的自然推理舉例 116
3.6 一階邏輯的套用 121
3.6.1 自然語言命題的符號化 122
3.6.2 自然語言推理有效性的驗證 128
3.6.3 算法性質的邏輯分析 130
3.7 本章小結 133
3.8 習題 134
第4 章 證明方法 139
4.1 數學證明導引 139
4.2 基本證明方法與策略 141
4.2.1 直接證明與間接證明 142
4.2.2 分情況證明 146
4.2.3 存在性證明 149
4.2.4 基本證明策略 152
4.3 歸納定義與歸納證明 154
4.3.1 數學歸納法與良序原理 154
4.3.2 歸納定義與結構歸納法 161
4.3.3 遞歸算法與歸納證明 168
4.4 本章小結 172
4.5 習題 173
第5 章 集合 179
5.1 集合的基本概念 179
5.1.1 集合的基本術語 179
5.1.2 定義集合的基本方法 181
5.1.3 文氏圖與成員關係表 184
5.2 集合運算 186
5.2.1 集合交 187
5.2.2 集合併 190
5.2.3 集合差與補 192
5.2.4 集合的冪集 194
5.2.5 集合運算的算法 195
5.3 集合等式 197
5.3.1 基於定義證明集合等式 197
5.3.2 集合等式演算 200
5.3.3 子集關係與集合等式 202
5.4 本章小結 206
5.5 習題 206
第6 章 關係 210
6.1 關係的基本概念 210
6.1.1 集合的笛卡兒積 210
6.1.2 關係的定義 212
6.1.3 關係的表示 214
6.1.4 關係的運算 216
6.2 關係的性質 222
6.2.1 關係的自反性與反自反性 223
6.2.2 關係的對稱性與反對稱性 225
6.2.3 關係的傳遞性 228
6.2.4 關係性質與關係運算 230
6.3 關係的閉包 233
6.3.1 關係閉包的定義 233
6.3.2 關係閉包的計算 235
6.3.3 Warshall 算法 240
6.4 特殊關係舉例 242
6.4.1 等價關係 242
6.4.2 偏序關係 247
6.5 本章小結 252
6.6 習題 253
第7 章 函式 259
7.1 函式的基礎知識 259
7.1.1 函式的基本概念 259
7.1.2 函式的性質 263
7.1.3 函式運算與函式的性質 266
7.2 集合基數的基礎知識 270
7.2.1 集合等勢 270
7.2.2 有窮集與無窮集 272
7.2.3 可數集與不可數集 276
7.3 函式的增長與算法效率分析 280
7.3.1 函式的增長 281
7.3.2 算法效率分析基礎 287
7.3.3 算法複雜度基礎知識 293
7.4 本章小結 295
7.5 習題 296
第8 章 計數與組合 301
8.1 組合計數的基本原理 301
8.1.1 加法原理和乘法原理 301
8.1.2 容斥原理 307
8.1.3 鴿籠原理 312
8.2 排列與組合 316
8.2.1 排列與組合的基本定義 316
8.2.2 二項式定理與組合等式 323
8.2.3 允許重複的排列與組合 328
8.2.4 再論容斥原理及其套用 333
8.2.5 排列與組合的生成算法 338
8.3 遞推關係式 342
8.3.1 計數問題的遞推關係式建模 342
8.3.2 線性遞推關係式求解 347
8.3.3 分治算法與遞推關係式 352
8.4 本章小結 355
8.5 習題 356
第9 章 圖與樹 362
9.1 圖的基礎知識 362
9.1.1 圖的基本概念 362
9.1.2 圖的連通性 368
9.1.3 圖的表示與存儲 373
9.1.4 無向圖的遍歷 377
9.2 樹的基礎知識 382
9.2.1 無向樹的定義 382
9.2.2 根樹的定義 384
9.2.3 樹的遍歷 386
9.3 帶權圖及其套用 390
9.3.1 帶權圖的最短距離 390
9.3.2 帶權圖的最小生成樹 395
9.3.3 哈夫曼樹 398
9.4 一些特殊的圖 402
9.4.1 平面圖 403
9.4.2 歐拉圖 406
9.4.3 哈密頓圖 407
9.5 本章小結 409
9.6 習題 410
第10章 代數系統 419
10.1 運算及其性質 419
10.1.1 運算的定義 419
10.1.2 運算的性質 422
10.1.3 運算性質的判定 427
10.2 代數及同態 430
10.2.1 代數與子代數 430
10.2.2 同餘關係與商代數 432
10.2.3 代數同態與同構 436
10.3 群的基礎知識 441
10.3.1 群的定義 442
10.3.2 群元素的階 445
10.3.3 子群與陪集 446
10.3.4 正規子群與商群 452
10.3.5 群同態 453
10.4 格與布爾代數 455
10.4.1 格的偏序定義與代數定義 455
10.4.2 分配格與有界格 458
10.4.3 布爾代數 460
10.5 本章小結 462
10.6 習題 463
第11章 結束語 468
參考文獻 471
