第1章 命题逻辑 1
1.1 命题与命题公式 1
1.1.1 命题 1
1.1.2 命题联结词 2
1.1.3 命题公式 5
1.1.4 命题公式的真值表 7
1.2 重言式 8
1.2.1 重言式和矛盾式 8
1.2.2 等价重言式 8
1.2.3 蕴含重言式 10
1.2.4 对偶与对偶原理 12
1.3 命题演算的推理规则和证明方法 13
1.3.1 真值表的证明方法 13
1.3.2 形式推理的证明方法——直接证法 14
1.3.3 间接证法 18
1.4 命题公式的标准形式 21
1.4.1 范式 21
1.4.2 主范式 23
习题1 28
第2章 谓词逻辑 31
2.1 个体、谓词与命题函数 32
2.1.1 个体与谓词 32
2.1.2 命题函数 33
2.2 量词 33
2.2.1 全称量词 34
2.2.2 存在量词 35
2.3 谓词公式与翻译 35
2.3.1 谓词公式 35
2.3.2 命题的符号化 36
2.3.3 自由变元和约束变元 38
2.4 谓词演算的推理理论 39
2.4.1 谓词演算的等价式和蕴含式 39
2.4.2 谓词演算的推理规则 43
习题2 46
第3章 集合 50
3.1 基本概念 50
3.1.1 集合及其表示方法 50
3.1.2 集合的包含和相等 51
3.1.3 空集和全集 52
3.1.4 幂集 53
3.2 集合的运算与运算定律 54
3.2.1 集合的运算与文氏图 54
3.2.2 集合运算的定律 56
3.2.3 集合的对称差 59
3.3 集合的划分与覆盖 61
3.4 容斥原理 62
习题3 64
第4章 关系 68
4.1 序偶与笛卡儿积 68
4.1.1 序偶与有序n元组 68
4.1.2 笛卡儿积 68
4.2 关系、关系矩阵和关系图 70
4.2.1 关系的概念 70
4.2.2 关系矩阵 72
4.2.3 关系图 73
4.3 关系的运算 74
4.3.1 关系的并、交、补、差运算 74
4.3.2 关系的复合运算 74
4.3.3 关系的逆运算 77
4.4 关系的性质 78
4.4.1 定义 78
4.4.2 举例 81
4.4.3 关系性质的判定定理 82
4.5 关系的闭包运算 82
4.5.1 定义 82
4.5.2 闭包运算的性质 84
4.5.3 有限集合上关系的传递闭包 85
4.5.4 p+的关系图的画法 85
4.6 等价关系与等价类 86
4.6.1 定义 86
4.6.2 等价关系与划分 87
4.7 偏序 88
4.7.1 定义 88
4.7.2 哈斯图 89
4.7.3 偏序集中的特殊元素 90
习题4 92
第5章 函数 97
5.1 函数与特殊类型函数 97
5.1.1 函数的定义 97
5.1.2 特殊类型函数 99
5.2 函数的运算 101
5.2.1 函数的复合 101
5.2.2 逆函数 103
5.3 集合的势与可数集 105
5.3.1 集合的势 105
5.3.2 可数集 107
5.4 鸽舍原理 110
5.4.1 鸽舍原理1 110
5.4.2 鸽舍原理2 111
习题5 112
第6章 代数系统的基本理论和特殊代数系统 115
6.1 运算和代数系统 115
6.1.1 运算 115
6.1.2 运算的运算表 116
6.1.3 代数系统 117
6.2 二元运算的性质与特殊元素 118
6.2.1 二元运算的性质 118
6.2.2 二元运算的特殊元素 119
6.3 同态和同构 123
6.3.1 同构 123
6.3.2 同态 124
6.4 半群和独异点 127
6.4.1 半群 127
6.4.2 独异点 128
6.4.3 子半群和子独异点 131
6.5 群 131
6.5.1 定义 131
6.5.2 群的基本性质 134
6.6 群中元素的周期与循环群 135
6.6.1 群中元素的周期 135
6.6.2 元素周期的性质 136
6.6.3 循环群 137
6.7 子群 138
6.7.1 两个等价的定义 138
6.7.2 子群的判定定理 139
6.8 格 140
6.8.1 格的定义和性质 140
6.8.2 几种特殊的格 142
习题6 144
第7章 图论 149
7.1 图的基本概念 149
7.1.1 图 149
7.1.2 结点的度 150
7.1.3 几种常见的图 151
7.1.4 子图 151
7.1.5 图的同构 152
7.2 路与圈 153
7.2.1 路、圈和连通性 153
7.2.2 有权图的最短路径问题 155
7.3 图的矩阵表示 158
7.4 有向图和可达性矩阵 160
7.4.1 有向图 160
7.4.2 有向图的可达性 161
7.5 欧拉图与哈密尔顿图 164
7.5.1 欧拉图 164
7.5.2 哈密尔顿图 168
7.6 树 170
7.6.1 树 171
7.6.2 生成树与最小生成树 172
7.7 根树及其应用 173
7.7.1 根树、有序树、M叉树 173
7.7.2 二叉树 175
7.7.3 二叉树在计算机中的应用 177
7.8 偶图与匹配 181
7.8.1 偶图 181
7.8.2 匹配 182
7.9 平面图与欧拉公式 183
7.9.1 平面图 183
7.9.2 欧拉公式 185
习题7 187
参考文献 193