离散数学结构及其在计算机科学中的应用PDF电子书下载

目录 1

译者的话 1

序言 1

第一章 数理逻辑 1

引言 1

§1.1语句和表示法 1

§1.2联结词 5

§1.2.1否定 6

§1.2.2合取 7

§1.2.3析取 8

§1.2.4语句公式和真假值表 8

练习1.2.4 11

§1.2.5程序语言的逻辑功能 11

§1.2.6条件和双条件 15

练习1.2.6 17

§1.2.7合式的公式 18

§1.2.8重言式 19

练习1.2.8 20

§1.2.9公式的等价 21

§1.2.10对偶性定律 23

§1.2.11重言的蕴含 25

练习1.2.11 27

§1.2.12具有不同的真假值表的公式 27

§1.2.13联结词的功能完全集 28

练习1.2.13 29

§1.2.14其他的联结词 29

练习1.2.14 31

§1.2.15二值器件与语句逻辑 31

练习1.2 37

练习1.2.15 37

§1.3范式 38

§1.3.1析取范式 38

§1.3.2合取范式 40

§1.3.3主析取范式 40

§1.3.4主合取范式 42

§1.3.5范式的次序和唯一性 43

练习1.3.5 45

§1.3.6完全括起来的中缀表示法以及波兰记法 45

练习1.3.6 49

§1.4语句运算的推理理论 49

§1.4.1用真假值表确定有效性 49

练习1.4.1 51

§1.4.2推理规则 51

§1.4.3前提的相容性以及间接证法 55

§1.4.4自动定理证明 56

练习1.4 60

§1.5谓词演算 60

§1.5.1谓词 61

§1.5.2语句函数，变量以及量词 62

§1.5.3谓词公式 65

§1.5.4自由与约束变量 66

§1.5.5论域 67

练习1.5 68

§1.6谓词演算的推理理论 69

§1.6.1有效公式和等价性 69

§1.6.2有限域上的几个有效公式 70

§1.6.3包含量词的特种有效公式 72

§1.6.4谓词演算的推理理论 73

§1.6.5包含一个以上量词的公式 76

练习1.6 77

本章参考文献 79

第二章 集合论 80

引言 80

§2.1集合论的基本概念 80

§2.1.1表示法 80

§2.1.2集合的包含和相等 82

§2.1.3幂集 83

练习2.1.3 85

§2.1.4几种集合运算 85

练习2.1.4 88

§2.1.5文氏（Venn）图 88

§2.1.6一些基本集合恒等式 90

练习2.1.5 90

§2.1.7区分原则 93

§2.1.9笛卡儿积 94

练习2.1 95

§2.2离散结构的表示 96

§2.2.1数据结构 96

§2.2.2存贮结构 98

§2.1.8有序对和n元组 99

§2.2.3顺序分配 99

§2.2.4指针和连接分配 100

§2.2.5位表示集合的应用 107

练习2.2 113

§2.3关系和次序 114

§2.3.1关系 114

§2.3.2集合中二元关系的性质 118

练习2.3.1 118

练习2.3.2 119

§2.3.3关系矩阵和关系图 120

§2.3.4集合的划分和覆盖 124

练习2.3.4 126

§2.3.5等价关系 127

§2.3.6兼容性关系 130

练习2.3.6 135

§2.3.7二元关系的复合 136

练习2.3.7 140

§2.3.8偏序 140

§2.3.9半序集：表示法和有关术语 143

练习2.3.9 146

§2.4.1定义和引言 147

§2.4函数 147

练习2.4.1 150

§2.4.2函数的复合 150

练习2.4.3 155

§2.4.4二元和n元运算 156

§2.4.3逆函数 158

练习2.4.4 159

§2.4.5集合的特征函数 159

§2.4.6散列函数 161

练习2.4.6 166

练习2.4 167

§2.5自然数 167

§2.5.1皮亚诺公理和数学归纳法 168

§2.5.2基数 170

练习2.5 175

§2.6.1递归函数，递归集合和递归谓词 176

§2.6递归 176

§2.6.2程序设计语言中的递归 183

练习2.6.1 183

练习2.6.2 196

§2.7机械定理证明中的递归 198

练习2.7 204

本章参考文献 204

第三章 代数结构 205

引言 205

§3.1代数系统：例子与一般性质 205

§3.1.1定义及例子 205

§3.1.2某些简单的代数系统及一般性质 207

§3.2半群和独异点 213

§3.2.1定义及例子 213

练习3.1 213

§3.2.2半群和独异点的同态 217

§3.2.3子半群和子独异点 221

练习3.2 222

§3.3文法和语言 223

§3.3.1文法的讨论 223

§3.3.2语言的形式定义 226

§3.3.3语法分析的概念 229

练习3.3 233

§3.4波兰表达式及其编译 234

§3.4.1波兰记号 234

§3.4.2中缀表达式到波兰记号的转换 235

练习3.4 241

§3.5群 242

§3.5.1定义及例子 242

练习3.5.1 248

§3.5.2子群与同态 249

练习3.5.2 252

§3.5.3陪集和拉格朗日定理 252

§3.5.4正规子群 254

§3.5.5具有两个二元运算的代数系统 258

练习3.5.5 260

练习3.5 260

§3.6剩余算术在计算机中的应用 261

§3.6.1数制介绍 261

§3.6.2剩余算术 264

练习3.6 271

§3.7群码 272

§3.7.1通信模型和错误校正的基本概念 272

§3.7.2利用奇偶校验生成的码 276

§3.7.3群码中错误的恢复 282

练习3.7 284

本章参考文献 285

第四章 格和布尔代数 286

引言 286

§4.1格作为半序集 286

§4.1.1定义和举例 286

练习4.1.1 288

§4.1.2格的一些性质 288

练习4.1.2 290

§4.1.3格作为代数系统 290

§4.1.4子格，直积和同态 292

练习4.1.4 294

§4.1.5一些特殊的格 295

§4.2布尔代数 298

练习4.1.5 298

§4.2.1定义和举例 299

§4.2.2子代数，直积和同态 301

练习4.2 304

§4.3布尔函数 305

§4.3.1布尔型和自由布尔代数 305

§4.3.2布尔表达式和布尔函数的值 308

练习4.3 312

§4.4布尔函数的表示法和极小化 313

§4.4.1布尔函数的表示法 313

§4.4.2布尔函数的极小化 317

练习4.4 324

§4.5应用布尔代数进行设计的例子 326

练习4.5 337

§4.6有穷自动机 338

§4.6.1时序电路简介 339

§4.6.2有穷自动机的等价性 340

练习4.6 347

本章参考文献 348

第五章 图论 349

引言 349

§5.1图论的基本概念 349

§5.1.1基本定义 349

练习5.1.1 353

§5.1.2路径，可达性与连通性 354

练习5.1.2 359

§5.1.3图的矩阵表示 360

练习5.1.3 366

§5.1.4树 367

练习5.1.4 371

§5.2图的存贮表示和处理 372

§5.2.1树：它们的表示和操作 372

§5.2.2表结构和图 377

练习5.2 381

§5.3简单优先文法 382

§5.3.1语法术语 382

§5.3.2语法分析梗概 385

§5.3.3优先关系的概念与利用 387

§5.3.4优先关系的形式定义 390

§5.3.5简单优先文法的分析算法 392

练习5.3 393

§5.4组合开关电路中的故障探测 394

§5.4.2故障探测的概念 395

§5.4.1组合电路中的故障 395

§5.4.3生成故障矩阵的算法 397

§5.4.4故障探测的过程 404

练习5.4 406

§5.5PERT与有关技术 406

练习5.5 410

本章参考文献 410

第六章 可计算性理论引论 411

引言 411

§6.1有穷状态接受机与正则文法 411

练习6.1 417

§6.2图灵机与部分递归函数 418

练习6.2 431

本章参考文献 431

附录对算法记号的说明 433