离散数学简明教程PDF电子书下载

第一章 集合 1

1．1 集合的概念 1

1．2 集合的运算 3

1．2．1 集合的运算 3

1．2．2 包含排斥原理 5

第二章 关系与函数 7

2．1 关系及表示法 7

2．1．1 笛卡尔积 7

2．1．2 关系的概念 8

2．1．3 二元关系的矩阵和图形表示 9

2．2 关系的一些性质 10

2．3 复合关系与逆关系 12

2．4 关系的闭包 16

2．5 等价关系与划分 20

2．6 半序关系 22

2．6．1 半序关系的定义 23

2．6．2 最大元和最小元 24

2．7 映射 26

2．7．1 映射的概念 26

2．7．2 复合映射和逆映射 27

第三章 命题逻辑 30

3．1 命题与命题连接词 30

3．1．1 命题 30

3．1．2 联结词和复合命题 31

3．2．1 合式公式的概念 33

3．2 合式公式与解释 33

3．2．2 命题公式的解释 34

3．2．3 公式的等价 35

3．2．4 对偶原理 37

3．3 析取范式和合取范式 39

3．3．1 范式 39

3．3．2 主范式及其唯一性 41

3．4 命题逻辑的推理 43

3．4．1 逻辑蕴涵 43

3．4．2 推理的形式结构 44

3．4．3 证明的方法 46

4．1 谓词与量词 49

第四章 一阶逻辑 49

4．2 谓词公式与解释 51

4．2．1 谓词公式 51

4．2．2 公式的解释 54

4．3 公式的等价与蕴涵 57

4．4 一阶逻辑的推理 59

第五章 群和环 64

5．1 代数系统 64

5．1．1 代数系统的概念 64

5．1．2 子代数系统 65

5．2 二元运算和特殊元素 66

5．2．1 运算的性质 66

5．2．2 特殊元素 68

5．3．1 同构 70

5．3 同态与同构 70

5．3．2 同态 72

5．4 群的概念 73

5．4．1 半群和群的定义 73

5．4．2 群元素的阶数 75

5．4．3 置换群 75

5．5 子群和循环群 78

5．5．1 子群 78

5．5．2 循环群 79

5．6 正规子群与商群 80

5．6．1 陪集 80

5．6．2 正规子群 83

5．7．1 群同构 84

5．7 群同态与同构 84

5．7．2 群同态 85

5．8 环和域 87

5．8．1 环 87

5．8．2 域的概念 89

第六章 格与布尔代数 91

6．1 格的概念 91

6．1．1 格的概念 91

6．1．2 子格 94

6．2 几种特殊的格 95

6．2．1 有界格 95

6．2．2 有补格 96

6．2．3 分配格 96

6．3 布尔代数 98

6．3．1 布尔代数定义 99

6．3．2 有限布尔代数的结构 100

第七章 图论 106

7．1 基本概念 106

7．1．1 图的定义 106

7．1．2 顶点的度数 108

7．1．3 图的运算 109

7．2 路和连通性 111

7．2．1 路 111

7．2．2 最短路径 112

7．2．3 图的矩阵表示 115

7．3．1 树的概念 117

7．3 树 117

7．3．2 有向树 120

7．4 二部图与线匹配 124

7．4．1 二部图的概念 124

7．4．2 二部图的线匹配 126

7．5 欧拉迹与哈密圈 128

7．5．1 欧拉迹与欧拉图 128

7．5．2 哈密顿路和圈 130

7．6 可平面性 133

7．6．1 图曲面嵌入的概念 133

7．6．2 平面图的性质 134

7．6．3 图平面嵌入的算法 136

7．7 图的着色 139

参考文献 142