《离散数学结构及其在计算机科学中的应用》求取 ⇩

目录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.411

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

§1.2.6条件和双条件15

练习1.2.617

§1.2.7合式的公式18

§1.2.8重言式19

练习1.2.820

§1.2.9公式的等价21

§1.2.10对偶性定律23

§1.2.11重言的蕴含25

练习1.2.1127

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

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

练习1.2.1329

§1.2.14其他的联结词29

练习1.2.1431

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

练习1.237

练习1.2.1537

§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.545

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

练习1.3.649

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

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

练习1.4.151

§1.4.2推理规则51

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

§1.4.4自动定理证明56

练习1.460

§1.5谓词演算60

§1.5.1谓词61

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

§1.5.3谓词公式65

§1.5.4自由与约束变量66

§1.5.5论域67

练习1.568

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

§1.6.1有效公式和等价性69

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

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

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

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

练习1.677

本章参考文献79

第二章 集合论80

引言80

§2.1集合论的基本概念80

§2.1.1表示法80

§2.1.2集合的包含和相等82

§2.1.3幂集83

练习2.1.385

§2.1.4几种集合运算85

练习2.1.488

§2.1.5文氏（Venn）图88

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

练习2.1.590

§2.1.7区分原则93

§2.1.9笛卡儿积94

练习2.195

§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.2113

§2.3关系和次序114

§2.3.1关系114

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

练习2.3.1118

练习2.3.2119

§2.3.3关系矩阵和关系图120

§2.3.4集合的划分和覆盖124

练习2.3.4126

§2.3.5等价关系127

§2.3.6兼容性关系130

练习2.3.6135

§2.3.7二元关系的复合136

练习2.3.7140

§2.3.8偏序140

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

练习2.3.9146

§2.4.1定义和引言147

§2.4函数147

练习2.4.1150

§2.4.2函数的复合150

练习2.4.3155

§2.4.4二元和n元运算156

§2.4.3逆函数158

练习2.4.4159

§2.4.5集合的特征函数159

§2.4.6散列函数161

练习2.4.6166

练习2.4167

§2.5自然数167

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

§2.5.2基数170

练习2.5175

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

§2.6递归176

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

练习2.6.1183

练习2.6.2196

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

练习2.7204

本章参考文献204

第三章 代数结构205

引言205

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

§3.1.1定义及例子205

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

§3.2半群和独异点213

§3.2.1定义及例子213

练习3.1213

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

§3.2.3子半群和子独异点221

练习3.2222

§3.3文法和语言223

§3.3.1文法的讨论223

§3.3.2语言的形式定义226

§3.3.3语法分析的概念229

练习3.3233

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

§3.4.1波兰记号234

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

练习3.4241

§3.5群242

§3.5.1定义及例子242

练习3.5.1248

§3.5.2子群与同态249

练习3.5.2252

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

§3.5.4正规子群254

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

练习3.5.5260

练习3.5260

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

§3.6.1数制介绍261

§3.6.2剩余算术264

练习3.6271

§3.7群码272

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

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

§3.7.3群码中错误的恢复282

练习3.7284

本章参考文献285

第四章 格和布尔代数286

引言286

§4.1格作为半序集286

§4.1.1定义和举例286

练习4.1.1288

§4.1.2格的一些性质288

练习4.1.2290

§4.1.3格作为代数系统290

§4.1.4子格，直积和同态292

练习4.1.4294

§4.1.5一些特殊的格295

§4.2布尔代数298

练习4.1.5298

§4.2.1定义和举例299

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

练习4.2304

§4.3布尔函数305

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

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

练习4.3312

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

§4.4.1布尔函数的表示法313

§4.4.2布尔函数的极小化317

练习4.4324

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

练习4.5337

§4.6有穷自动机338

§4.6.1时序电路简介339

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

练习4.6347

本章参考文献348

第五章 图论349

引言349

§5.1图论的基本概念349

§5.1.1基本定义349

练习5.1.1353

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

练习5.1.2359

§5.1.3图的矩阵表示360

练习5.1.3366

§5.1.4树367

练习5.1.4371

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

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

§5.2.2表结构和图377

练习5.2381

§5.3简单优先文法382

§5.3.1语法术语382

§5.3.2语法分析梗概385

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

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

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

练习5.3393

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

§5.4.2故障探测的概念395

§5.4.1组合电路中的故障395

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

§5.4.4故障探测的过程404

练习5.4406

§5.5PERT与有关技术406

练习5.5410

本章参考文献410

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

引言411

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

练习6.1417

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

练习6.2431

本章参考文献431

附录对算法记号的说明433