离散数学PDF电子书下载

第1章集合论 1

1.1集合的概念与运算 1

1.1.1集合的概念 2

1.1.2集合之间的关系 2

1.1.3集合的运算 2

1.1.4集合的运算性质 3

1.1.5序偶与笛卡儿积 5

1.2二元关系 6

1.2.1二元关系及其表示 6

1.2.2二元关系的运算 7

1.3关系的性质 10

1.4关系的闭包运算 12

1.5序关系 15

1.6等价关系 18

1.7映射 20

1.8数学归纳法 22

1.9计数 24

1.9.1帕斯卡三角形和二项式定理 25

1.9.2鸽巢原理 26

1.9.3乘法法则和加法法则 28

1.9.4排列和组合 29

1.10排列组合生成算法 31

1.11离散概率简介 34

习题1 37

第2章命题逻辑 41

2.1命题与联结词 41

2.1.1命题与真值 41

2.1.2命题联结词 42

2.2命题公式、指派及真值表 46

2.2.1命题公式 46

2.2.2命题的符号化 47

2.2.3公式的指派（赋值）及真值表 48

2.3命题公式的等值式，蕴含关系式 50

2.3.1命题公式的等值式 50

2.3.2代入规则与替换规则 51

2.3.3对偶式 53

2.3.4蕴含关系式 54

2.4主析取范式和主合取范式 56

2.4.1合取范式与析取范式 57

2.4.2主范式 58

2.5联结词完备集 61

2.6可满足性问题与消解法 63

2.7推理的形式结构 68

2.8自然推理系统N中的形式证明 70

习题2 76

第3章谓词逻辑 79

3.1基本概念 79

3.1.1个体词、谓词 79

3.1.2量词 80

3.2一阶逻辑公式及解释 83

3.3一阶逻辑等值式 87

3.4前束范式与斯科林范式 90

3.4.1前束范式 90

3.4.2斯科林范式 92

3.5谓词演算的推理理论 93

3.6数理逻辑在计算机科学中的应用 99

3.6.1“钥匙在点火开关中”报警蜂鸣器 100

3.6.2构造自锁控制安全带的电路 103

3.6.3构造一个拿子游戏装置 105

3.6.4构造电路：专用装置和程序化计算机 108

5.6.2邻接矩阵 159

5.6.3可达矩阵 164

5.6.4图的运算 165

5.7平面图与图的着色 166

5.7.1平面图 166

5.7.2对偶图与图着色 169

习题5 171

第6章代数系统 175

6.1二元运算与代数系统 175

6.1.1二元运算 175

6.1.2代数系统 179

6.2群和半群 180

6.2.1群和半群的定义 180

6.2.2关于逆元的性质 182

6.2.3群的几个等价性质 182

6.3子群和元素的阶 183

6.3.1子群 183

6.3.2元素的阶 184

6.4循环群和生成群、群的同构 185

6.4.1循环群和生成群 185

6.4.2群的同构 186

6.4.3循环群的性质 186

6.5变换群和置换群、凯莱定理 187

6.5.1置换群 188

6.5.2凯莱定理 190

6.6子群的陪集和拉格朗日定理 192

6.6.1子群的陪集 192

6.6.2子群的指数和拉格朗日定理 193

6.7正规子群和商群 195

6.7.1正规子群的概念 195

6.7.2正规子群的性质 195

6.7.3商群 196

6.8共轭元和共轭子群 198

6.8.1中心和中心化子 198