离散数学

王庆先，顾小丰，王丽杰

目录

  • 1 集合论
    • 1.1 集合的基本概念
      • 1.1.1 集合的表示
      • 1.1.2 集合与集合的关系
      • 1.1.3 几个特殊的集合
    • 1.2 集合的运算
    • 1.3 无限集
      • 1.3.1 可数集合
      • 1.3.2 不可数集合
    • 1.4 与集合相关的应用
      • 1.4.1 集合的计算机表示
      • 1.4.2 计数问题
  • 2 命题逻辑
    • 2.1 命题与命题联结词
      • 2.1.1 命题
      • 2.1.2 命题联结词
      • 2.1.3 自然语言的命题符号化
    • 2.2 命题公式、解释与真值表
      • 2.2.1 命题公式
      • 2.2.2 命题公式的解释与真值表
      • 2.2.3 命题公式的基本等价定律
    • 2.3 公式的标准型——范式
      • 2.3.1 命题联结词的完备集
      • 2.3.2 析取范式和合取范式
      • 2.3.3 主合取范式和主析取范式
    • 2.4 命题逻辑的推理理论
      • 2.4.1 推理的基本概念
      • 2.4.2 推理有效性的判别方法
    • 2.5 命题逻辑的应用
      • 2.5.1 命题联结词的应用
      • 2.5.2 命题公式的应用
      • 2.5.3 范式的应用
      • 2.5.4 命题逻辑推理的应用
  • 3 谓词逻辑
    • 3.1 自然语言的谓词符号化
      • 3.1.1 谓词
      • 3.1.2 量词
    • 3.2 谓词公式与解释
      • 3.2.1 谓词公式
      • 3.2.2 自由变元和约束变元
      • 3.2.3 谓词公式的解释
      • 3.2.4 谓词公式的基本等价定律
    • 3.3 谓词公式的标准型——前束范式*
      • 3.3.1 前束范式
      • 3.3.2 Skolem范式
    • 3.4 谓词逻辑的推理理论
      • 3.4.1 推理规则与推理定律
      • 3.4.2 推理有效性的判别方法
    • 3.5 谓词逻辑的应用
  • 4 二元关系
    • 4.1 二元关系及其表示
      • 4.1.1 序偶和笛卡儿积
      • 4.1.2 关系的定义
      • 4.1.3 关系的表示法
    • 4.2 关系的运算
      • 4.2.1 关系的复合运算
      • 4.2.2 关系的逆运算
      • 4.2.3 关系的幂运算
    • 4.3 关系的性质
      • 4.3.1 关系性质的定义
      • 4.3.2 关系性质的判定定理
      • 4.3.3 关系性质的保守性
    • 4.4 关系的闭包
    • 4.5 关系的应用
      • 4.5.1 二元关系及表示的应用
      • 4.5.2 关系运算的应用
  • 5 特殊关系
    • 5.1 相容关系
      • 5.1.1 相容关系的定义
      • 5.1.2 集合的覆盖
    • 5.2 等价关系
      • 5.2.1 等价关系的定义
      • 5.2.2 集合的划分
      • 5.2.3 等价类与商集
      • 5.2.4 等价关系与划分
    • 5.3 次序关系
      • 5.3.1 拟序关系
      • 5.3.2 偏序关系
      • 5.3.3 全序关系
      • 5.3.4 良序关系
    • 5.4 函数
      • 5.4.1 函数的基本概念
      • 5.4.2 函数的运算
      • 5.4.3 置换函数
    • 5.5 特殊关系的应用
      • 5.5.1 等价关系的应用
      • 5.5.2 次序关系的应用
      • 5.5.3 函数的应用
      • 5.5.4 置换函数的应用
  • 6 图
    • 6.1 图的基本概念
      • 6.1.1 图的定义
      • 6.1.2 图的表示
      • 6.1.3 图的操作
      • 6.1.4 邻接点与邻接边
      • 6.1.5 图的分类
      • 6.1.6 子图与补图
    • 6.2 握手定理
    • 6.3 图的同构
    • 6.4 通路与回路
      • 6.4.1 通路与回路的概念
      • 6.4.2 通路与回路的计算
      • 6.4.3 可达与距离
      • 6.4.4 无向赋权图的最短通路
    • 6.5 图的连通性
      • 6.5.1 无向图的连通性
      • 6.5.2 有向图的连通性
    • 6.6 图的应用
      • 6.6.1 网络的结构
      • 6.6.2 渡河问题
      • 6.6.3 均分问题
  • 7 特殊图
    • 7.1 树
      • 7.1.1 树的基本概念及性质
      • 7.1.2 生成树及算法
    • 7.2 根树
      • 7.2.1 根树的定义与分类
      • 7.2.2 根树的遍历
      • 7.2.3 最优树与哈夫曼算法
    • 7.3 欧拉图
      • 7.3.1 欧拉图的引入与定义
      • 7.3.2 欧拉图的判定
    • 7.4 哈密顿图
      • 7.4.1 哈密顿图的引入与定义
      • 7.4.2 哈密顿图的判定
    • 7.5 偶图
      • 7.5.1 偶图的定义
      • 7.5.2 偶图的判定
      • 7.5.3 匹配
    • 7.6 平面图
      • 7.6.1 平面图的定义
      • 7.6.2 平面图的简单判定方法——观察法
      • 7.6.3 欧拉公式
      • 7.6.4 库拉托夫斯基定理
    • 7.7 特殊图的应用
      • 7.7.1 无向树的应用
      • 7.7.2 根树的应用
      • 7.7.3 欧拉图的应用
      • 7.7.4 哈密顿图的应用
      • 7.7.5 偶图的应用
      • 7.7.6 平面图的应用
  • 8 代数系统
    • 8.1 代数系统
      • 8.1.1 代数运算
      • 8.1.2 代数系统与子代数
    • 8.2 代数系统的基本运算性质
      • 8.2.1 二元运算律
      • 8.2.2 二元运算的特殊元
    • 8.3 同态与同构
      • 8.3.1 同态与同构的定义
      • 8.3.2 同态的性质
    • 8.4 代数系统的应用
      • 8.4.1 代数系统的计算机表示
      • 8.4.2 数据库与关系代数
  • 9 群环域
    • 9.1 群的基本概念
      • 9.1.1 群的定义及基本性质
      • 9.1.2 元素的阶
      • 9.1.3 子群
      • 9.1.4 群的同态和同构
    • 9.2 特殊群
      • 9.2.1 循环群
      • 9.2.2 置换群
    • 9.3 陪集与拉格朗日定理
      • 9.3.1 陪集
      • 9.3.2 拉格朗日定理
    • 9.4 正规子群与商群
      • 9.4.1 正规子群
      • 9.4.2 商群
    • 9.5 环和域
      • 9.5.1 环和域的定义
      • 9.5.2 子环、理想和商环
      • 9.5.3 环的同态和同构
    • 9.6 与群环域相关的应用
      • 9.6.1 计数问题
      • 9.6.2 多项式编码
  • 10 格与布尔代数
    • 10.1 格的定义和性质
      • 10.1.1 格的定义
      • 10.1.2 格的性质
    • 10.2 子格与格同态
      • 10.2.1 子格和理想
      • 10.2.2 格同态
    • 10.3 特殊格
      • 10.3.1 分配格与模格
      • 10.3.2 有界格与有补格
    • 10.4 布尔代数
    • 10.5 格与布尔代数的应用
      • 10.5.1 格与树形图结构
      • 10.5.2 布尔函数及其表示
图的基本概念