《离散数学》学习指导与习题解答【2025|PDF下载-Epub版本|mobi电子书|kindle百度云盘下载】

《离散数学》学习指导与习题解答PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 集合1

1.1 概述1

1.2 集合、元素与子集1

1.2.1 集合的表示1

1.2.2 子集2

1.2.3 全集与空集3

1.2.4 不相交集3

1.3 维恩图3

1.3.1 维恩图与证明4

1.4 集合运算4

1.4.1 并集与交集5

1.4.2 补、差与对称差6

1.4.3 基本积7

1.5 集合的代数运算与对偶性8

1.5.1 代数运算规律8

1.5.2 对偶性8

1.6 有限集与计数原理9

1.6.1 计算有限集中的元素数量9

1.6.2 容斥原理10

1.7 集族、幂集与划分11

1.7.1 幂集11

1.7.2 划分12

1.7.3 集合运算的推广12

1.8 数学归纳法13

1.8.1 数学归纳法Ⅰ13

1.8.2 数学归纳法Ⅱ13

本章习题14

补充题22

补充题答案26

第2章 关系29

2.1 概述29

2.2 积集29

2.3 关系30

2.3.1 定义30

2.3.2 逆关系31

2.4 关系的图形表示31

2.4.1 实数R上的关系31

2.4.2 集合上关系的有向图32

2.4.3 有限集上关系的图示32

2.5 关系的合成33

2.5.1 关系合成33

2.5.2 关系的合成与关系矩阵34

2.6 关系的类型34

2.6.1 自反关系34

2.6.2 对称关系与反对称关系35

2.6.3 传递关系36

2.7 闭包性质36

2.7.1 P-闭包36

2.7.2 自反闭包与对称闭包37

2.7.3 传递闭包37

2.8 等价关系38

2.8.1 等价关系的定义38

2.8.2 等价关系与划分39

2.9 偏序关系40

2.10 n-元关系40

本章习题41

补充题48

补充题答案50

第3章 函数与算法52

3.1 概述52

3.2 函数52

3.2.1 作为关系的函数53

3.2.2 复合函数54

3.3 单射函数、满射函数与可逆函数55

3.3.1 单射函数与满射函数的几何特征56

3.3.2 排列57

3.4 数学函数、指数函数与对数函数57

3.4.1 下限函数与上限函数57

3.4.2 整数值函数与绝对值函数57

3.4.3 余项函数与模运算58

3.4.4 指数函数58

3.4.5 对数函数59

3.4.6 指数函数与对数函数之间的关系60

3.5 序列与集合的索引类60

3.5.1 序列61

3.5.2 求和符号与求和61

3.5.3 集合的索引类62

3.6 递归定义函数63

3.6.1 阶乘函数63

3.6.2 层号64

3.6.3 斐波纳契序列64

3.6.4 阿克曼函数65

3.7 基数／集合的容量65

3.7.1 基数65

3.7.2 不等式与基数66

3.8 算法与函数67

3.9 算法的复杂度68

3.9.1 线性查找69

3.9.2 增长率与大O记号70

3.9.3 著名算法的复杂度71

本章习题71

补充题82

补充题答案84

第4章 逻辑与命题演算86

4.1 引言86

4.2 命题与复命题86

4.2.1 命题86

4.2.2 复合命题86

4.3 基本逻辑运算87

4.3.1 合取87

4.3.2 析取88

4.3.3 否定88

4.4 命题与真值表89

4.4.1 命题与真值表89

4.4.2 构造真值表的另一方法90

4.5 永真式与永假式90

4.6 逻辑等价91

4.7 命题代数92

4.8 条件语句与双条件语句92

4.9 论证93

4.10 命题函数与量词95

4.10.1 命题函数95

4.10.2 全称量词95

4.10.3 存在量词96

4.11 量化命题的否定96

4.11.1 反例98

4.11.2 多变量命题函数98

4.11.3 多变量量化命题的否定99

本章习题99

补充题105

补充题答案106

第5章 计数技术108

5.1 概述108

5.2 基本计数原理108

5.3 数学函数109

5.3.1 阶乘函数109

5.3.2 二项式系数109

5.3.3 二项式系数与杨辉三角形110

5.4 排列111

5.4.1 一般排列111

5.4.2 可重复排列112

5.4.3 有序抽样113

5.5 组合113

5.6 鸽巢原理114

5.6.1 鸽巢原理114

5.6.2 一般鸽巢原理115

5.7 容斥原理115

5.8 树形图116

本章习题117

补充题126

补充题答案131

第6章 高级计数技术与递推134

6.1 概述134

6.2 有重组合134

6.3 有序划分与无序划分135

6.3.1 有序划分135

6.3.2 无序划分135

6.4 再现容斥原理136

6.4.1 满射函数的数量136

6.4.2 错位排列137

6.5 再现鸽巢原理138

6.6 递推关系139

6.7 具有常系数的线性递推关系141

6.8 二阶齐次线性递推关系的解142

6.8.1 通解142

6.8.2 特征多项式具有相等根时的解144

6.9 一般齐次线性递推关系的解145

本章习题146

补充题151

补充题答案153

第7章 概率论155

7.1 概述155

7.2 样本与事件155

7.3 有限概率空间158

7.3.1 有限概率空间的定义158

7.3.2 等概率空间158

7.3.3 有限概率空间相关定理159

7.4 条件概率160

7.4.1 条件概率定义160

7.4.2 条件概率的乘法定理161

7.5 独立事件162

7.6 独立重复试验与二项分布163

7.6.1 独立重复试验163

7.6.2 具有两个结果的重复试验、伯努利试验与二项试验164

7.7 随机变量165

7.7.1 随机变量定义165

7.7.2 随机变量的和与积及其记号165

7.7.3 随机变量的概率分布166

7.7.4 随机变量的期望值167

7.7.5 随机变量的方差与标准差167

7.7.6 二项分布168

7.8 切比雪夫不等式与大数定律169

7.8.1 切比雪夫不等式169

7.8.2 样本均值与大数定律170

本章习题170

补充题188

补充题答案193

第8章 图论195

8.1 概述与数据结构195

8.1.1 概述195

8.1.2 链表与指针195

8.1.3 堆栈、队列与优先队列197

8.2 图与多重图198

8.2.1 图198

8.2.2 多重图198

8.2.3 顶点的度（次数）199

8.2.4 有限图与平凡图199

8.3 子图、同构图与同胚图200

8.3.1 子图200

8.3.2 同构图200

8.3.3 同胚图200

8.4 路径与连通性201

8.4.1 路径201

8.4.2 连通性与连通分支202

8.4.3 距离与直径202

8.4.4 割点与桥203

8.5 可遍历图、欧拉图与柯尼斯堡桥203

8.5.1 可遍历图203

8.5.2 哈密顿图204

8.6 标号图与加权图204

8.7 完全图、正则图与二部图205

8.7.1 完全图205

8.7.2 正则图206

8.7.3 二部图206

8.8 树图207

8.8.1 树207

8.8.2 生成树208

8.8.3 最小生成树208

8.9 平面图209

8.9.1 地图与区域210

8.9.2 欧拉公式211

8.9.3 非平面图与库拉托夫斯基定理211

8.10 图的着色212

8.10.1 着色212

8.10.2 对偶地图与四色定理214

8.11 图在计算机存储器中的表示215

8.11.1 邻接矩阵215

8.11.2 图G的链接表示216

8.12 图算法218

8.12.1 深度优先搜索218

8.12.2 广度优先搜索220

8.13 旅行推销员问题221

8.13.1 问题定义221

8.13.2 最近邻算法222

本章习题223

补充题240

补充题答案246

第9章 有向图251

9.1 概述251

9.2 有向图251

9.2.1 有向图定义251

9.2.2 子图252

9.3 基本定义253

9.3.1 顶点度253

9.3.2 路径253

9.3.3 连通性254

9.4 有根树255

9.4.1 有根树定义255

9.4.2 有序根树256

9.5 有向图的序列表示257

9.5.1 序列表示的定义257

9.5.2 有向图与关系、邻接矩阵257

9.5.3 路径矩阵259

9.5.4 传递闭包与路径矩阵260

9.6 沃舍尔算法与最短路径260

9.6.1 沃舍尔算法260

9.6.2 最短路径算法262

9.7 有向图的链接表示263

9.8 图的算法：深度优先与广度优先查找265

9.8.1 深度优先查找266

9.8.2 广度优先查找267

9.9 有向无回路图与拓扑排序269

9.9.1 有向无回路图269

9.9.2 拓扑排序269

9.10 最短路径的修剪算法271

9.10.1 问题引出271

9.10.2 修剪算法272

本章习题274

补充题283

补充题答案289

第10章 二叉树293

10.1 概述293

10.2 二叉树293

10.2.1 二叉树的图示293

10.2.2 相似二叉树294

10.2.3 相关术语294

10.3 完全二叉树与扩充（展）二叉树295

10.3.1 完全二叉树295

10.3.2 扩充（展）二叉树：2-树296

10.3.3 代数式与波兰表示法296

10.4 二叉树在存储器中的表示297

10.4.1 二叉树的链接表示297

10.4.2 二叉树的序列表示298

10.5 遍历二叉树299

10.6 二叉查找树301

10.6.1 二叉查找树中的查找与插入302

10.6.2 二叉查找树中的删除303

10.6.3 二叉查找树算法的复杂性304

10.7 优先队列与堆304

10.7.1 堆的定义304

10.7.2 向堆中插入节点305

10.7.3 从堆中删除根节点307

10.7.4 堆算法的复杂性308

10.8 路径长度与哈夫曼算法308

10.8.1 加权路径长度309

10.8.2 哈夫曼算法309

10.8.3 哈夫曼算法的计算机实现311

10.8.4 编码中的应用312

10.9 一般（有序有根）树的回顾312

10.9.1 一般树的定义312

10.9.2 森林314

10.9.3 一般树与二叉树314

本章习题314

补充题323

补充题答案327

第11章 整数的性质329

11.1 概述329

11.2 次序、不等式与绝对值330

11.2.1 次序330

11.2.2 绝对值331

11.3 数学归纳法331

11.3.1 数学归纳法原理331

11.3.2 良序原理332

11.4 带余除法333

11.4.1 带余除法定理333

11.4.2 应用计算器的带余除法333

11.5 整除与质数334

11.5.1 整除334

11.5.2 质数335

11.6 最大公约数与欧几里德算法336

11.6.1 最大公约数336

11.6.2 欧几里德算法337

11.6.3 最小公倍数338

11.7 算术基本定理338

11.7.1 互质339

11.7.2 算术基本定理339

11.8 同余关系340

11.8.1 同余关系340

11.8.2 剩余类341

11.8.3 同余运算342

11.8.4 剩余类的计算342

11.8.5 模m整数343

11.8.6 同余的消去律343

11.8.7 简化剩余系与欧拉φ函数344

11.9 同余方程345

11.9.1 同余方程345

11.9.2 线性同余方程：ax≡1（mod m）346

11.9.3 线性同余方程：ax≡b（mod m）346

11.9.4 孙子（中国）剩余定理348

本章习题350

补充题374

补充题答案379

第12章 语言、自动机与语法381

12.1 概述381

12.2 字母表、字与自由半群381

12.2.1 字与字母表381

12.2.2 连接381

12.2.3 子字与初始段382

12.2.4 自由半群与自由类群382

12.3 语言382

12.3.1 语言的定义382

12.3.2 语言上的运算383

12.4 正则表达式与正则语言384

12.4.1 正则表达式384

12.4.2 语言与正则语言384

12.5 有限状态自动机385

12.5.1 有限状态自动机的定义385

12.5.2 自动机的状态图386

12.5.3 自动机确定的语言387

12.5.4 泵作用引理388

12.6 语法389

12.6.1 语法的定义389

12.6.2 语法G的语言L（G）390

12.6.3 语法的类型391

12.6.4 上下文无关语法的推导树392

12.6.5 巴克斯-诺尔形式393

12.6.6 自动机与语法393

本章习题394

补充题401

补充题答案404

第13章 有限状态机与图灵机406

13.1 概述406

13.2 有限状态机406

13.2.1 有限状态机的定义406

13.2.2 有限状态机的状态表与状态图407

13.2.3 输入带与输出带407

13.2.4 二进制加法408

13.3 哥德尔数409

13.4 图灵机410

13.4.1 基本定义410

13.4.2 采用图灵机计算412

13.4.3 具有输入的图灵机413

13.4.4 语言与图灵机413

13.5 可计算函数414

13.5.1 定义414

13.5.2 多元函数415

本章习题416

补充题420

补充题答案422

第14章 有序集与格424

14.1 概述424

14.2 有序集424

14.2.1 偏序424

14.2.2 对偶序425

14.2.3 有序子集425

14.2.4 拟序425

14.2.5 可比较性与线性有序集425

14.2.6 积集与积序426

14.2.7 克林闭包与次序426

14.3 偏序集的哈塞图427

14.3.1 哈塞图定义427

14.3.2 极小元素、极大元素、首元素（最小元素）、末元素（最大元素）428

14.4 相容枚举429

14.5 上确界与下确界430

14.6 同构有序集（相似有序集）432

14.7 良序集432

14.7.1 良序集定义432

14.7.2 超限归纳法433

14.7.3 选择公理与良序定理434

14.8 格434

14.8.1 格的定义公理435

14.8.2 对偶性与幂等律435

14.8.3 格与次序435

14.8.4 子格与同构格436

14.9 有界格437

14.10 分配格437

14.10.1 分配格定义437

14.10.2 并不可约元与原子438

14.11 补元与有补格439

14.11.1 补元439

14.11.2 有补格439

本章习题440

补充题451

补充题答案457

第15章 布尔代数461

15.1 概述461

15.2 基本定义461

15.2.1 布尔代数461

15.2.2 子代数、同构布尔代数462

15.3 对偶性463

15.4 基本定理463

15.5 布尔代数作为格464

15.6 表示定理464

15.7 集合的积和形式465

15.8 布尔代数的积和形式466

15.8.1 积和形式的定义466

15.8.2 求积和形式的算法467

15.8.3 完全积和形式468

15.9 极小布尔表达式与素项469

15.9.1 极小积和469

15.9.2 素项469

15.9.3 基本积的一致470

15.9.4 一致法求素项470

15.9.5 求极小积和形式471

15.10 逻辑门与逻辑电路472

15.10.1 逻辑门472

15.10.2 逻辑电路474

15.10.3 逻辑电路作为布尔代数474

15.10.4 与或电路474

15.10.5 与非门和或非门475

15.11 真值表与布尔函数476

15.11.1 真值表476

15.11.2 布尔函数478

15.12 卡诺图479

15.12.1 卡诺图定义479

15.12.2 二元情形480

15.12.3 三元情形481

15.12.4 四元情形483

本章习题485

补充题503

补充题答案507

附录A 向量与矩阵510

A.1 概述510

A.2 向量510

A.2.1 向量定义510

A.2.2 向量运算510

A.2.3 列向量511

A.3 矩阵511

A.4 矩阵的加法与标量乘法512

A.5 矩阵乘法514

A.5.1 矩阵乘法的定义514

A.5.2 矩阵乘法与线性方程组515

A.6 转置矩阵516

A.7 方阵516

A.7.1 方阵定义516

A.7.2 方阵的代数运算517

A.8 可逆（非奇异）矩阵和逆矩阵518

A.9 行列式519

A.9.1 行列式的定义519

A.9.2 行列式的一般定义520

A.9.3 行列式与2×2矩阵的逆矩阵520

A.10 初等行变换与高斯消去法521

A.10.1 初等行变换521

A.10.2 阶梯矩阵521

A.10.3 矩阵形式中的高斯消去法522

A.10.4 线性方程组的矩阵解法524

A.10.5 n×n矩阵的逆矩阵525

A.11 布尔（0-1）矩阵526

本章习题527

补充题538

补充题答案542

附录B 代数系统543

B.1 概述543

B.2 运算543

B.2.1 定义543

B.2.2 运算性质544

B.3 半群546

B.3.1 半群的定义546

B.3.2 自由半群与自由么半群547

B.3.3 子半群547

B.3.4 同余关系与商结构547

B.3.5 半群的同态548

B.3.6 半群同态基本定理549

B.3.7 半群积550

B.4 群550

B.4.1 群的定义550

B.4.2 对称群Sn551

B.4.3 MAP（A）、PERM（A）与AUT（A）552

B.5 子群、正规子群与同态552

B.5.1 子群552

B.5.2 陪集553

B.5.3 正规子群553

B.5.4 模m整数554

B.5.5 循环子群554

B.5.6 生成集和生成元555

B.5.7 同态555

B.6 环、整环（整域）与域556

B.6.1 环与子环的定义556

B.6.2 特殊的环：整环与域557

B.6.3 理想558

B.6.4 环同态559

B.6.5 整环上的整除性559

B.7 域上的多项式559

B.7.1 基本定义560

B.7.2 欧几里德算法与多项式的根561

B.7.3 K［t］作为PID（主理想域）与UFD（唯一析因整环）562

B.7.4 代数基本定理563

本章习题564

补充题581

补充题答案587