集论与逻辑 面向计算机科学PDF电子书下载

第一篇 基础集论 3

第一章 集合的基本关系与运算 3

1.1 集合的表示：内涵与外延 3

1.2 集合的运算、构集公理 4

第二章 关系与函数 12

2.1 基本概念、关系的运算 12

2.2 分划、等价关系与映射 23

2.3 偏序与树 32

2.4 Cantor的对角线论证法、从二元关系的矩阵表示及理发师悖论谈起 41

2.5 多元关系、关系数据库的一个实例 44

第三章 有限集与无限集 49

3.1 无穷公理与自然数、归纳与递归 49

3.2 归纳与递归Revisited 60

3.3 超限序数、超限归纳与递归 70

3.4 无限基数、可数无限与不可数无限、选择公理 74

3.5 集合悖论、公理方法与若干历史的注记 89

第四章 引论 95

第二篇 经典逻辑 95

第五章 命题逻辑(PL) 99

5.1 PL的句(语)法 99

5.2 语义学——PL公式之语义、PL模型 102

5.3 命题逻辑与布尔集代数 114

5.4 命题算子与布尔函数、PL的表达能力的探讨与应用 119

5.5 Hilbert公理系简介、What is a Proof？ 129

5.6 PL的Tableau推理系统 134

5.7 Tableau系统的可靠性与完备性及其应用 141

第六章 一阶逻辑(FO) 148

6.1 自然引入 148

6.2 一阶语言与一阶公式 150

6.3 逻辑结构与模型、Tarski语义 156

6.4 一阶逻辑的Tableau证明系统 177

6.5 一阶Tableau推理系统的可靠性与完备性及若干应用 185

6.6 一阶逻辑的Hilbert公理系统 193

6.7 一阶逻辑的局限性与扩充 195