第 1 章 命题逻辑
1.1 命题............................................................... 1
1.1.1 命题与真值............................................1
1.1.2 原子命题与复合命题............................3
1.2 逻辑联结词................................................... 3
1.2.1 否定联结词............................................3
1.2.2 合取联结词............................................3
1.2.3 析取联结词............................................4
1.2.4 蕴含联结词............................................4
1.2.5 等价联结词............................................5
1.3 命题公式....................................................... 5
1.3.1 命题公式的概念....................................5
1.3.2 命题符号化............................................6
1.3.3 命题公式真值表....................................7
1.3.4 命题公式的类型....................................8
1.3.5 重言式的性质........................................9
1.4 命题逻辑的等价关系.................................... 9
1.4.1 等价........................................................9
1.4.2 基本等价式......................................... 10
1.4.3 置换规则............................................. 10
1.5 命题公式的标准化...................................... 13
1.5.1 析取范式与合取范式......................... 13
1.5.2 主析取范式与主合取范式................. 14
1.5.3 主范式的应用..................................... 16
1.6 命题逻辑的蕴含关系.................................. 17
1.6.1 蕴含..................................................... 17
1.6.2 证明蕴含关系的方法......................... 17
1.6.3 基本蕴含式......................................... 17
1.7 命题逻辑的推理理论................................... 18
1.7.1 论证的有效性......................................18
1.7.2 有效论证的判断方法.........................18
1.7.3 自然推理系统......................................19
1.7.4 自然推理系统中构造有效论证的
方法......................................................20
习题...................................................................... 23
第 2 章 谓词逻辑
2.1 谓词逻辑命题符号化................................... 25
2.1.1 命题逻辑的局限性.............................25
2.1.2 谓词逻辑三要素.................................26
2.1.3 谓词逻辑命题符号化.........................27
2.2 谓词公式..................................................... 28
2.2.1 谓词逻辑的合式公式.........................28
2.2.2 闭式......................................................29
2.2.3 谓词公式的解释.................................29
2.2.4 谓词逻辑的公式类型.........................30
2.3 谓词逻辑的等价关系................................... 31
2.3.1 等价关系..............................................31
2.3.2 基本等价式..........................................31
2.4 谓词公式的标准化...................................... 32
2.5 谓词逻辑的蕴含关系................................... 33
2.5.1 蕴含关系..............................................33
2.5.2 基本蕴含式..........................................33
2.6 谓词逻辑的推理理论................................... 33
习题...................................................................... 36
离散数学 （第 3 版）（微课版）
< 2 >
第 3 章 集 合
3.1 集合的概念与表示......................................37
3.1.1 集合的定义......................................... 37
3.1.2 集合的表示方法................................. 38
3.2 集合之间的重要关系...................................39
3.2.1 集合之间的重要关系......................... 39
3.2.2 特殊集合............................................. 39
3.3 集合的运算..................................................40
3.3.1 集合的基本运算................................. 40
3.3.2 集合关系的证明方法......................... 41
3.3.3 笛卡儿积............................................. 42
习题......................................................................42
第 4 章 关 系
4.1 关系的概念及表示......................................44
4.1.1 关系的概念......................................... 44
4.1.2 关系的表示方法................................. 45
4.2 关系的性质..................................................46
4.2.1 自反性与反自反性............................. 46
4.2.2 对称性与反对称性............................. 47
4.2.3 传递性................................................. 48
4.3 关系的运算..................................................49
4.3.1 关系的复合运算................................. 49
4.3.2 关系的逆运算..................................... 52
4.3.3 关系的闭包运算................................. 53
4.4 等价关系与划分..........................................55
4.4.1 等价关系的概念................................. 55
4.4.2 等价类................................................. 55
4.4.3 划分..................................................... 56
4.5 次序关系.....................................................57
4.5.1 偏序关系............................................. 57
4.5.2 其他次序关系..................................... 59
习题......................................................................60
第 5 章 函 数
5.1 函数的概念与性质.......................................62
5.1.1 函数的概念 .........................................62
5.1.2 函数的性质 .........................................64
5.2 函数的运算..................................................64
5.2.1 函数的复合运算.................................64
5.2.2 函数的逆运算.....................................65
5.3 基数.............................................................65
5.3.1 基数的概念 .........................................65
5.3.2 基数的比较 .........................................66
习题......................................................................68
第 6 章 代数结构
6.1 代数系统的概念..........................................69
6.2 代数系统的运算及其性质...........................70
6.2.1 二元运算的性质.................................71
6.2.2 小结......................................................74
6.3 半群与含幺半群..........................................74
6.3.1 半群和子半群.....................................74
6.3.1 含幺半群和子含幺半群.....................75
6.4 群与子群......................................................77
6.4.1 群..........................................................77
6.4.2 子群......................................................80
6.5 交换群、循环群与置换群...........................81
6.5.1 交换群..................................................81
6.5.2 循环群..................................................82
6.5.3 置换群..................................................84
6.6 陪集与拉格朗日定理...................................85
6.6.1 陪集......................................................85
6.6.2 拉格朗日定理.....................................87
6.6.3 正规子群..............................................87
6.7 同态与同构..................................................88
6.7.1 同态......................................................88
6.7.2 同构..................................................... 89
6.7.3 同余关系............................................. 91
6.8 环与域......................................................... 92
6.8.1 环......................................................... 93
6.8.2 域......................................................... 94
习题 ..................................................................... 96
第 7 章 格与布尔代数
7.1 格.............................................................. 100
7.1.1 格的概念........................................... 100
7.1.2 格的性质........................................... 102
2.2 分配格....................................................... 105
7.3 有补格....................................................... 106
7.4 布尔代数................................................... 108
7.5 布尔代数的应用........................................ 110
7.5.1 布尔函数........................................... 110
7.5.2 布尔函数的表示............................... 113
7.5.3 逻辑门电路....................................... 115
习题 ................................................................... 121
第 8 章 图论及其应用
8.1 图的基本概念............................................ 124
8.1.1 图....................................................... 124
8.1.2 结点的度........................................... 125
8.1.3 图的同构........................................... 126
8.1.4 子图和补图....................................... 127
8.2 图的连通性............................................... 128
8.2.1 路径与回路....................................... 128
8.2.2 连通图............................................... 128
8.3 图的矩阵表示............................................130
8.3.1 图的邻接矩阵....................................130
8.3.2 图的可达矩阵....................................132
8.4 特殊图.......................................................133
8.4.1 欧拉图................................................133
8.4.2 哈密顿图............................................135
8.4.3 二部图................................................137
8.4.4 平面图................................................138
8.5 图的应用...................................................141
8.5.1 图的应用示例....................................141
8.5.2 特殊图的应用....................................142
习题....................................................................144
第 9 章 树
9.1 无向树.......................................................148
9.1.1 基本概念............................................148
9.1.2 最小生成树及其应用.......................150
9.2 有向树.......................................................152
9.2.1 基本概念............................................152
9.2.2 有序树................................................153
9.2.3 m 叉树...............................................154
9.3 二叉树.......................................................155
9.3.1 基本概念............................................155
9.3.2 二叉树的遍历....................................157
9.3.3 最优树................................................158
习题....................................................................160
附录 数据库的维护