第1章 导论 1
1.1 学习动机 1
1.2 教材内容 1
1.3 组织结构 2
第2章 数 5
2.1 自然数 5
2.2 Peano算术 7
2.3 其他类型的数 8
2.4 附加练习 8
2.5 练习解答 8
第3章 命题逻辑 11
3.1 原子命题 11
3.2 真值 11
3.3 否定运算符 12
3.4 合取运算符 13
3.5 析取运算符 14
3.6 蕴含运算符 16
3.7 等值运算符 17
3.8 运算的优先级 18
3.9 重言式、矛盾式和不定式 18
3.10 真值表 19
3.11 等值推理 20
3.12 自然演绎 21
3.13 附加练习 24
3.14 练习解答 25
第4章 集合论 33
4.1 集合 33
4.2 单集 34
4.3 空集 34
4.4 集合成员 34
4.5 子集 35
4.6 超集 37
4.7 集合的并集 38
4.8 集合的交集 39
4.9 集合的差集 40
4.10 有关集合的推理 41
4.11 集合的势 42
4.12 有穷集合和无穷集合 42
4.13 集合的幂集 43
4.14 集合的广义运算 44
4.15 附加练习 45
4.16 练习解答 46
第5章 布尔代数 51
5.1 简介 51
5.2 命题逻辑回顾 51
5.3 集合论回顾 51
5.4 布尔代数基础 52
5.5 简写规定 54
5.6 优先级 54
5.7 集合的布尔代数 54
5.8 命题的布尔代数 54
5.9 布尔代数的同构 54
5.10 对偶性 55
5.11 附加练习 55
5.12 练习解答 56
第6章 类型集合论 61
6.1 类型的需要 61
6.2 再论空集 63
6.3 集合描述 64
6.4 特征组 65
6.5 缩写 66
6.6 笛卡儿积 66
6.7 公理定义 70
6.8 附加练习 71
6.9 练习解答 72
第7章 谓词逻辑 77
7.1 量词的需要 77
7.2 全称量词 77
7.3 存在量词 78
7.4 可满足性和有效性 80
7.5 量词的否定 80
7.6 自由变元和约束变元 81
7.7 替换 82
7.8 限制 84
7.9 唯一存在量词 86
7.10 等值推理 87
7.11 自然演绎 89
7.12 one-point规则 91
7.13 附加练习 92
7.14 练习解答 93
第8章 关系 101
8.1 二元关系 101
8.2 关系的推理 102
8.3 定义域和值域 102
8.4 关系的逆 103
8.5 关系上的运算 104
8.6 关系的合成 107
8.7 同类关系和异类关系 109
8.8 关系的性质 109
8.8.1 自反性 109
8.8.2 传递性 110
8.8.3 对称性 111
8.8.4 非对称性 112
8.8.5 反对称性 112
8.8.6 完全性 113
8.9 顺序与等价 113
8.9.1 偏序 113
8.9.2 全序 114
8.9.3 等价关系 114
8.10 闭包 114
8.10.1 自反闭包 114
8.10.2 传递闭包 115
8.10.3 自反传递闭包 116
8.10.4 对称闭包 116
8.11 n元关系 117
8.12 附加练习 117
8.13 练习解答 119
第9章 函数 127
9.1 一种特殊的关系 127
9.2 全函数 128
9.3 函数的作用 129
9.4 覆盖 130
9.5 函数的性质 131
9.5.1 单射 131
9.5.2 满射 132
9.5.3 双射 133
9.6 递归函数 133
9.7 附加练习 135
9.8 练习解答 136
第10章 序列 141
10.1 元包 141
10.2 顺序的需要 142
10.3 建模序列 142
10.4 空序列 143
10.5 长度 143
10.6 连接 144
10.7 头和尾 144
10.8 限制 145
10.9 逆置 147
10.10 单射序列 148
10.11 再论递归函数 148
10.12 附加练习 149
10.13 练习解答 151
第11章 归纳法 155
11.1 数学归纳法 155
11.2 结构归纳法 157
11.3 附加练习 158
11.4 练习解答 158
第12章 图论 163
12.1 图 163
12.2 图的集合和元包表示 167
12.3 图的矩阵表示 168
12.4 图的同构 170
12.5 路径 171
12.6 循环 173
12.7 树 174
12.8 带权图 175
12.9 有向图 177
12.10 二叉树 178
12.11 附加练习 180
12.12 练习解答 181
第13章 组合数学 187
13.1 阶乘函数 187
13.2 二项式系数 188
13.3 计数 190
13.4 排列 190
13.5 组合 192
13.6 树形图 193
13.7 取样 193
13.8 附加练习 195
13.9 练习解答 195
第14章 应用实例 203
14.1 程序变量的建模 203
14.2 元搜索引擎 204
14.2.1 使用集合建模 204
14.2.2 使用序列建模 205
14.2.3 使用关系建模 205
14.2.4 继续讨论 206
14.3 用于栈和队列的序列 208
14.4 数字电路 210
14.5 学校数据库 212
14.6 知识库系统 214
14.7 练习解答 216
参考文献 227