简明离散数学PDF电子书下载

前言 1

第一章 集合论 1

引言 1

1—1 集合的概念 1

一 集合的概念 1

二 集合的表示法 3

三 集合的基数与分类 4

四 集合的图解 5

五 集合的相等与包含关系 5

六 全集 9

习题 1—1 10

1—2 集合的运算 12

一 集合的运算 12

二 集合的运算律 15

习题 1—2 19

1—3 集合成员表 20

一 集合成员表的构造 21

二 集合成员表的应用 23

习题 1—3 25

1—4 幂集与划分 25

一 幂集 26

二 集合的划分 29

习题 1—4 32

集合论知识结构表 35

引言 36

第二章 关系 36

2—1 关系的基本概念 37

一 二元关系 37

二 二元关系的几何意义 38

三 几个特殊的二元关系 40

四 n 元关系 41

习题 2—1 43

2—2 关系的基本性质、关系图和关系矩阵 45

一 关系的基本性质 45

二 关系图 49

三 关系矩阵 52

习题 2—2 54

2—3 关系的运算 57

一 关系的交、并、差、补运算 57

二 逆关系 58

三 复合关系与关系的复合运算 60

四 复合关系的矩阵 64

五 复合关系的逆运算 66

习题 2—3 68

2—4 关系的闭包运算 71

一 关系的闭包概念 71

二 求闭包的方法 72

习题 2—4 77

2—5 等价关系 79

一 等价关系的概念 79

二 等价类 83

习题 2—5 86

一 相容关系的概念 87

2—6 相容关系 87

二 最大相容类 90

三 相容关系与覆盖的联系 92

习题 2—6 94

2—7 序关系 95

一 偏序的概念 96

二 偏序的哈斯图 97

三 偏序集中具有特殊位置的元素 101

四 全序 104

五 几个特殊的偏序 105

习题 2—7 106

关系的知识结构表 109

第三章 函数 110

引言 110

3—1 函数的基本概念 110

一 函数的概念 111

二 在笛卡尔积 A×B 的子集中有多少个不同的函数? 113

三 函数的相等与缩小 114

四 几种常见的特殊函数 115

习题3—1 119

3—2 复合函数 121

一 复合函数的概念 121

二 函数的复合运算律 124

三 几个复合函数的特性 125

习题3—2 127

一 逆函数的概念 128

3—3 逆函数 128

二 逆函数的性质 131

习题3—3 134

3—4 无限集的基数 136

一 “一一对应关系”是求集合基数的理论基础 136

二 可数集及其性质 138

三 不可数集及集合基数的比较 144

习题3—4 147

函数知识结构表 149

引言 150

第四章 代数系统 150

4—1 集合中的代数运算 152

一 代数运算的概念 152

二 二元代数运算 154

三 与集合 A 的二元代数运算有关的 A 的特异元素 155

习题4—1 158

4—2 代数系统的基本概念和性质 164

一 代数系统的概念 164

二 代数运算的性质 165

三 利用运算表判断代数运算的性质 169

习题4—2 170

4—3 同构与同态 174

一 同构的概念和性质 174

二 同态的概念和性质 179

习题4—3 181

4—4 群 183

一 群的基本概念 184

二 群的基本性质 190

三 子群 192

四 几种典型的群 194

习题4—4 198

4—5 环和域 202

一 环的概念 202

二 环的性质 205

三 子环 206

四 几种重要的环 207

五 域 208

习题4—5 210

4—6 格 213

一 格的概念 213

二 格的性质 216

三 格——代数系统 221

四 子格 223

五 格的积代数、同态和同构 224

六 几种特殊格 227

习题4—6 230

代数系统知识结构表 234

第五章 图论 235

引言 235

5—1 图的基本概念 236

一 图论的起源 236

二 图的概念 237

三 图 G 的结点与边之间的关系的概念 240

四 图 G 的分类 241

习题5—1 243

5—2 图的运算和结点的次数 245

一 图的运算 245

二 结点次数及其计算 248

三 子图和同构图 250

习题5—2 253

5—3 路径、回路和连通性 256

一 路径和回路的概念 257

三 结点间的可达性和距离 259

二 路径的长度 259

四 简单有向图的连通性 261

五 无向图中的路径、回路和连通性 263

习题5—3 264

5—4 图的矩阵表示 267

一 邻接矩阵 268

二 可达性矩阵 273

习题5—4 277

一 最优路径的概念 280

5—5 最优路径和关键路径 280

二 怎样找到从初始结点到终端结点的最优路径? 282

三 最优路径在工程技术中的应用 284

习题5—5 288

5—6 欧拉图与哈密尔顿图 292

一 欧拉图 292

二 哈密尔顿图 299

习题5—6 309

5—7 树 312

一 无向树 313

二 无向图的生成树和最小树 314

三 有向树 318

四 二元树 320

五 最优树 323

习题5—7 325

5—8 平面图 328

一 平面图的概念 329

二 平面图的面 330

三 平面图的判定 332

四 平面图的应用 336

习题5—8 340

图论知识结构表 345

第六章 命题逻辑 346

引言 346

6—1 命题与命题联结词 347

一 命题的概念 347

三 命题的分类 349

二 命题的标识符 349

四 命题联结词 351

习题6—1 356

6—2 命题公式、真值表和翻译 358

一 命题公式 358

二 真值表 360

三 命题的翻译 363

习题6—2 365

6—3 永真式、永假式和互为等价的公式 367

一 永真式和永假式 367

二 命题公式间的等价关系及其性质 369

三 基本等价公式——命题定律 371

四 代入规则和置换规则 373

五 求证两个公式等价的方法 375

习题6—3 376

6—4 公式的对偶式和公式间的蕴涵关系 378

一 公式的对偶式 378

二 命题公式间的蕴涵关系及其性质 381

三 怎样判断两个命题公式间是否存在永真蕴涵关系? 382

四 基本永真蕴涵式 383

五 蕴涵式、等价式和永真式有关的相互关系 384

习题6—4 386

6—5 命题联结词的扩充与最小联结词组 388

一 命题联结词的扩充 388

二 联结词“与非”和“或非”的性质 389

三 联结词“异或”的性质 391

四 最小联结词组 393

习题6—5 394

6—6 公式的范式 396

一 基本积与基本和 396

二 合取范式与析取范式 397

三 利用析取范式与合取范式进行公式的判定 398

四 公式的析取范式与合取范式的不唯一性 400

习题6—6 401

一 主析取范式 402

6—7 公式的主范式 402

二 主合取范式 406

三 主范式的应用 409

习题6—7 411

6—8 命题演算的推理理论 412

一 推理的基本概念和规则 412

二 判断有效结论的方法 414

习题6—8 420

命题逻辑知识结构表 423

引言 424

第七章 谓词逻辑 424

7—1 谓词逻辑的基本概念 425

一 客体、谓词和命题的谓词表达式 425

二 命题函数 427

三 量词 429

四 自然语言中，哪些词是客体?谓词?量词? 432

习题7—1 433

一 谓词公式 434

7—2 谓词公式与翻译 434

二 约束变元和自由变元 436

三 谓词逻辑的翻译 440

习题7—2 443

7—3 谓词公式的永真式、永假式和蕴涵式 445

一 谓词公式的永真式、永假式和蕴涵式的概念 445

二 判定方法和基本公式 446

习题7—3 451

7—4 谓词公式的范式 452

一 谓词公式的多重量化 452

二 前束范式 454

三 斯柯林范式 456

习题7—4 457

7—5 谓词逻辑的推理理论 458

一 四个与量词有关的推理规则 459

二 谓词逻辑中推理的论证 460

三 谓词逻辑演算中常见的错误 465

习题7—5 468

谓词逻辑知识结构表 470

第八章 组合数学初步 471

引言 471

8—1 两个基本原理 472

一 加法原理及其特性 472

二 乘法原理及其特性 473

习题8—1 474

8—2 排列 475

一 排列 476

二 比较复杂的排列应用题常用基本解法 477

三 受限排列问题的解法 480

习题8—2 481

8—3 圆排列和重复排列 483

一 圆排列 483

二 重复排列 485

三 对按属性分组的 n 个事物的排列数的计算 486

习题8—3 488

8—4 组合 490

一 组合 490

二 组合的性质 492

三 比较复杂的组合问题常用基本解法 494

习题8—4 495

8—5 解排列组合问题的基本思路 498

一 排列组合混合问题的求解 498

二 解排列组合问题的基本思路 499

习题8—5 502

8—6 鸽巢原理 505

一 鸽巢原理 505

二 应用鸽巢原理解题举例 506

三 鸽巢原理的一般形式 509

习题8—6 510

组合数学知识结构表 512

符号表 513

习题解答与提示 518