离散数学 Discrete MathematicsPDF电子书下载

1 数理逻辑 1

1.1 命题、联结词与公式 1

1.1.1 基本概念 1

1.1.2 命题联结词及其真值表 2

1.1.3 实例分析 4

1.1.4 公式G的种类 5

习题1.1 6

1.2 公式的等价与蕴含 7

1.2.1 公式的等价与24个基本等价式 7

1.2.2 公式的蕴含与16个基本蕴含式 9

习题1.2 10

1.3 公式的主范式 11

1.3.1 主析取范式 11

1.3.2 主合取范式 13

习题1.3 15

1.4 推理理论 15

习题1.4 18

1.5 谓词逻辑 18

1.5.1 谓词逻辑的基本概念 19

1.5.2 语句命题的谓词形式符号化 20

1.5.3 谓词公式 20

习题1.5 24

2 集合、关系和函数 26

2.1 集合和集合的运算 26

2.1.1 集合的基本概念 26

2.1.2 集合的运算 28

2.1.3 集合运算中等值式与命题公式的“等价式”一致 28

2.1.4 序偶和笛卡尔积 28

习题2.1 30

2.2 关系 31

2.2.1 二元关系R 31

2.2.2 关系R的表示与性质 31

2.2.3 关系的运算 33

2.2.4 集合A上的关系R的闭包问题——包含关系R的有用性质（自反性、对称性、传递性）的最小关系问题 36

习题2.2 37

2.3 等价关系和集合的划分 37

2.3.1 等价关系 37

2.3.2 A的划分s 38

2.3.3 A关于等价关系R的商集A/R 38

习题2.3 39

2.4 序关系和哈斯图 40

2.4.1 偏序关系及其哈斯图 40

2.4.2 其他序关系 41

习题2.4 44

2.5 函数 44

2.5.1 函数的概念 44

2.5.2 几种特殊的函数及其特点 45

2.5.3 函数的表示 46

2.5.4 复合函数与逆函数 46

习题2.5 47

3 代数结构 50

3.1 代数系统 50

3.1.1 运算及其封闭性 50

3.1.2 代数系统 51

3.1.3 子代数 55

习题3.1 57

3.2 半群和独异点 57

3.2.1 半群 57

3.2.2 独异点 58

习题3.2 59

3.3 群与子群 60

3.3.1 群的概念 60

3.3.2 群〈G;*〉的一个子群〈H;*〉 62

习题3.3 63

3.4 环与域 64

3.4.1 环 64

3.4.2 环的性质定理 65

3.4.3 几种特殊的环 65

习题3.4 67

3.5 格、子格与布尔代数 67

3.5.1 格的概念 67

3.5.2 几种特殊的格 70

3.5.3 布尔代数 73

习题3.5 74

4 图论 76

4.1 图的基本概念 76

4.1.1 图G的定义 76

4.1.2 图的种类 77

4.1.3 图的一些术语 77

4.1.4 图的性质 79

4.1.5 特殊图 79

习题4.1 82

4.2 图的连通性 83

4.2.1 无向图的连通性 83

4.2.2 有向图的连通性 84

习题4.2 88

4.3 图的矩阵表示 89

4.3.1 图G的邻接矩阵 89

4.3.2 图G的可达矩阵（又称路径矩阵） 91

习题4.3 92

4.4 树、生成树、有向树及其应用 92

4.4.1 树的基本概念 92

4.4.2 有向树的基本概念 94

习题4.4 97

4.5 欧拉图、哈密顿图、平面图 98

4.5.1 欧拉图的基本概念及其有关定理和应用 98

4.5.2 哈密顿图的基本概念及其有关定理和应用 99

4.5.3 平面图 101

习题4.5 103

参考答案 105

参考文献 126