“離散數(shù)學(xué)”是計算機(jī)和信息類專業(yè)重要的核心學(xué)科基礎(chǔ)課程之一。本書內(nèi)容主要包括集合論（集合、二元關(guān)系與函數(shù)）、組合數(shù)學(xué)初步、圖論、數(shù)理邏輯（命題邏輯、謂詞邏輯）、代數(shù)系統(tǒng)簡介五部分。在涵蓋離散數(shù)學(xué)各方面內(nèi)容的同時，本書有層次地精選了豐富的例題和多種解題思路與方法，各章配有適量的習(xí)題，幫助讀者鞏固和掌握所學(xué)知識，提高解題能力及技巧。本書結(jié)構(gòu)清晰，概念準(zhǔn)確，敘述嚴(yán)謹(jǐn)，力圖做到“宜教易學(xué)”。本版新增了微課，掃描書中二維碼即可觀看；本書提供電子課件和習(xí)題答案，登錄華信教育資源網(wǎng)可免費(fèi)下載。本書可作為高等學(xué)校計算機(jī)和信息類等專業(yè)的教材，也適合作為考研復(fù)習(xí)的輔助資料。
張婷 ，北京工業(yè)大學(xué)計算機(jī)學(xué)院副教授，主要研究方向：計算機(jī)科學(xué)、模式識別與信息處理；在研課題：數(shù)字幾何處理的理論和應(yīng)用問題的研究、網(wǎng)絡(luò)傳輸自相似性研究；科研成果：四元數(shù)射影空間上的一類等參超曲面，關(guān)于謂詞邏輯教學(xué)中的一些探索等。
目 錄
第1章 集合1
1.1 集合的基本概念1
1.1.1 集合的表示方法1
1.1.2 子集2
1.1.3 全集和補(bǔ)集3
1.1.4 冪集3
1.2 集合的基本運(yùn)算4
1.2.1 并和交4
1.2.2 差和對稱差7
習(xí)題19
第2章 二元關(guān)系與函數(shù)12
2.1 二元關(guān)系的基本概念12
2.1.1 引言12
2.1.2 笛卡兒乘積和二元關(guān)系的定義12
2.1.3 二元關(guān)系的三種表示方法13
2.1.4 二元關(guān)系的基本類型16
2.2 等價關(guān)系和偏序關(guān)系19
2.2.1 等價關(guān)系與劃分19
2.2.2 偏序關(guān)系25
2.3 關(guān)系的特殊運(yùn)算28
2.3.1 復(fù)合關(guān)系28
2.3.2 逆關(guān)系32
2.3.3 閉包運(yùn)算33
2.4 函數(shù)36
2.4.1 函數(shù)的基本概念36
2.4.2 特殊函數(shù)38
2.4.3 復(fù)合函數(shù)和逆函數(shù)40
習(xí)題243
第3章 組合數(shù)學(xué)初步47
3.1 計數(shù)的基本原則與鴿巢原理47
3.1.1 乘積法則與求和法則47
3.1.2 減法法則（容斥原理）48
3.1.3 除法法則49
3.1.4 樹形圖50
3.1.5 鴿巢原理50
3.1.6 鴿巢原理的應(yīng)用52
3.2 排列與組合及其推廣53
3.2.1 基本計數(shù)原理53
3.2.2 排列：順序重要、不放回54
3.2.3 組合：順序不重要、不放回54
3.2.4 允許重復(fù)的排列（有放回）55
3.2.5 多重集的排列（元素不可區(qū)分）55
3.2.6 允許重復(fù)的組合（多重集的組合）56
3.2.7 分配模型與等價轉(zhuǎn)換57
3.3 二項式與經(jīng)典恒等式57
3.3.1 二項式定理58
3.3.2 組合恒等式的推導(dǎo)59
3.3.3 帕斯卡恒等式60
3.3.4 范德蒙德卷積61
3.3.5 上指標(biāo)求和與其他恒等式62
3.3.6 應(yīng)用舉例62
3.4 生成排列與組合63
3.4.1 生成排列63
3.4.2 生成組合65
3.5 遞推模型與分治思想67
3.5.1 遞推關(guān)系及應(yīng)用67
3.5.2 動態(tài)規(guī)劃與遞推關(guān)系68
3.5.3 分治算法與遞推關(guān)系69
3.5.4 分治遞推關(guān)系估計算法復(fù)雜度71
3.6 線性遞推關(guān)系的求解73
3.6.1 線性齊次遞推關(guān)系求解73
3.6.2 常系數(shù)線性齊次遞推關(guān)系求解73
3.6.3 常系數(shù)線性非齊次遞推關(guān)系求解75
3.7 生成函數(shù)76
3.7.1 生成函數(shù)的定義和定理76
3.7.2 生成函數(shù)的應(yīng)用77
習(xí)題378
第4章 圖論81
4.1 圖的基本概念81
4.1.1 幾個問題81
4.1.2 圖的基本術(shù)語82
4.1.3 圖的矩陣表示85
4.1.4 子圖與圖的同構(gòu)87
4.1.5 完全圖與補(bǔ)圖89
4.2 通路與賦權(quán)圖的最短通路91
4.2.1 通路與回路91
4.2.2 圖的連通性92
4.2.3 賦權(quán)圖的最短通路96
4.3 樹102
4.3.1 無向樹102
4.3.2 有向樹106
4.3.3 前綴碼與最優(yōu)樹108
4.4 歐拉圖和哈密頓圖114
4.4.1 歐拉圖114
4.4.2 哈密頓圖118
4.5 二部圖和平面圖122
4.5.1 二部圖123
4.5.2 平面圖127
習(xí)題4135
第5章 命題邏輯140
5.1 命題邏輯的基本概念140
5.1.1 命題140
5.1.2 命題聯(lián)結(jié)詞141
5.1.3 命題公式143
5.1.4 命題公式的真值表145
5.1.5 永真式、永假式和可滿足式145
5.2 邏輯等價147
5.2.1 邏輯等價147
5.2.2 代換規(guī)則148
5.2.3 對偶原理150
5.2.4 聯(lián)結(jié)詞的完備集150
5.2.5 奎因法151
5.3 范式和主范式152
5.3.1 析取范式和合取范式152
5.3.2 主析取范式和主合取范式153
5.4 邏輯蘊(yùn)涵160
5.4.1 邏輯蘊(yùn)涵的定義160
5.4.2 邏輯蘊(yùn)涵的性質(zhì)161
5.5 推理理論164
5.5.1 前提和有效結(jié)論164
5.5.2 直接證明法165
5.5.3 間接證明法166
習(xí)題5170
第6章 謂詞邏輯174
6.1 謂詞邏輯的基本概念174
6.1.1 個體詞、謂詞和命題函數(shù)174
6.1.2 量詞176
6.1.3 謂詞公式181
6.1.4 約束變元和自由變元182
6.1.5 解釋184
6.2 邏輯等價與邏輯蘊(yùn)含186
6.2.1 永真式、永假式和可滿足式186
6.2.2 邏輯等價式和邏輯蘊(yùn)含式186
6.2.3 前束范式191
6.3 謂詞演算的推理理論192
習(xí)題6196
第7章 代數(shù)系統(tǒng)簡介198
7.1 代數(shù)系統(tǒng)的基本概念198
7.1.1 代數(shù)系統(tǒng)的定義198
7.1.2 特殊運(yùn)算與特殊元素201
7.1.3 同構(gòu)206
7.2 半群和獨異點207
7.2.1 半群和子半群207
7.2.2 獨異點和子獨異點211
7.3 群212
7.3.1 群的定義和性質(zhì)212
7.3.2 子群218
7.3.3 循環(huán)群223
7.3.4 陪集和拉格朗日定理225
7.3.5 群碼229
7.4 環(huán)和域232
7.4.1 環(huán)232
7.4.2 域235
7.5 格237
7.5.1 格的定義237
7.5.2 格和偏序集239
7.5.3 特殊格241
習(xí)題7246
參考文獻(xiàn)251
書單推薦
