这幅思维导图基于我上课复习的重点而作,并不全面,如有纰漏请指出。

离散数学 Discrete Mathematics.JPG

二元关系

序偶

笛卡尔积

  • 前域
  • 后域
  • 定义域
  • 值域

二元关系

  • 定义
  • 重要关系

    • 空关系
    • 全关系
    • 恒等关系

二元关系的数量

关系的表示

  • 集合表示法
  • 关系图表示法
  • 关系矩阵表示法

    • 布尔矩阵的并交运算
    • 布尔矩阵的积运算

关系的运算

  • 基本运算

  • 复合运算
  • 逆运算
  • 幂运算

关系的性质

  • 自反性
  • 反自反性
  • 对称性
  • 反对称性
  • 传递性

关系的闭包运算

  • 自反闭包(r(R))
  • 对称闭包(s(R))
  • 传递闭包(t(R))

集合论

特殊的集合

  • 空集(∅)
  • 全集(U)
  • 有限集、无限集
  • 幂集
  • 自然数集合(N)
  • 整数集(Z)
  • 有理数集合(Q)
  • 复数集(C)

集合的表示方法

  • 枚举法
  • 隐式法
  • 归纳法
  • 递归指定
  • 文氏图法

集合与元素的关系

  • 明确
  • 互异
  • 无序

集合间的关系

  • 相等
  • 包含

    • 真包含

集合的运算

  • 对称差

集合的运算定律

  • 幂等率
  • .......
  • 德摩根率

可数集合与不可数集合

  • 等势

特殊关系

等价关系

  • 性质

    • 自反
    • 对称
    • 传递
  • 等价类

    • 特点

      • 不空
      • 不重
      • 不丢
  • 商集
  • 划分

次序关系

  • 拟序关系

    • 性质

      • 反自反
      • 传递
  • 偏序关系

    • 性质

      • 自反
      • 反对称
      • 传递
  • 哈斯图

    • 画法
    • 最大元、最小元

      (在一个集合中)大于等于(小于等于)所有

    • 极大元、极小元

      (在一个集合中)没有比其大(小)的元素

    • 上界、下界

      (在全集中)大于等于(小于等于)全部集合中的元素

    • 上确界、下确界

      最小上界,最大下界

函数

函数的定义

函数的类型

  • 单射
  • 满射
  • 双射
  • 变换

函数的运算

  • 复合运算

特殊图

欧拉图

  • 欧拉通路(回路)
  • 判定定理

    • 有向欧拉图
    • 无向欧拉图
  • Fleury算法

哈密顿图

  • 哈密顿通路(回路)
  • 判定方法

    • 必要条件
    • 充分条件
    • 其它方法

偶图

  • 判定方法

    • 必要条件
    • 充分条件
  • 匹配

    • 判定条件

      • 相异性条件
      • t条件
      • 必要条件

平面图

    • 无限面
    • 有限面
  • 次数
  • 欧拉公式
  • 同胚
  • 收缩
  • 库拉托夫斯基定理

无向树

  • 定义

    • 分支点
    • 森林
    • 平凡树
  • 性质

    • 无回路
    • 连通
    • 平凡树至少有2片叶
  • 生成树

    • 算法

      • 破圈法
      • 避圈法
      • 广度优先法
    • 最小生成树

      • 算法

        • Kruskal
        • Prim

有向树

  • 定义

    • 根树
    • 外向树
    • 内点
    • 分支点
    • 层数
    • 根树的高
    • 关系

      • 祖先
      • 后代
      • 父亲
      • 儿子
      • 兄弟
  • 有序树、k元树
  • 遍历

    • 先根
    • 后根
    • 中根
  • 最优树

    • 定义

      • 前缀
      • 前缀码
      • 二元前缀码
      • 赋权二元树

    • 算法

      • 哈夫曼算法

定义

  • 序偶

    • 有序<u,v>
    • 无序(u,v)

表示

  • 集合
  • 图形
  • 矩阵

分类

  • 按边的方向

    • 有向图
    • 无向图
    • 混合图
  • 按重边

    • 多重图
    • 线图
    • 简单图
  • 按权值

    • 有权
    • 无权
  • 特殊图

    • 零图
    • 平凡图

子图

  • 真子图
  • 导出子图
  • 生成子图

完全图

补图

    • 握手定理

      • 推论
    • 分类(有向图)

      • 入度
      • 出度
  • 悬挂点
  • 邻接点
  • 割点

  • 邻接边
  • 割边(桥)

同构

  • 定义
  • 必要条件

通路、回路

  • 简单(复杂)通路、简单(复杂)回路
  • 基本通路、基本回路

可达性与最短路

  • 可达性判定
  • 可达性矩阵

连通性

  • 无向图

    • 连通分支
    • 点割集
    • 边割集
  • 有向图

    • 分类

      • 弱连通图
      • 单向连通图
      • 强连通图
      • 非连通图
    • 连通分支

      • 若连通分支
      • 单连通分支
      • 强连通分支

谓词逻辑

个体词

  • 个体常量
  • 个体变量
  • 个体域

量词

  • 全称量词
  • 特称量词
  • 量词辖域

谓词

  • 逻辑符号化
  • 谓词合成公式

    • 原子公式
    • 合成公式
    • 自由变元与约束变元

      • 改名规则
      • 带入规则
      • 闭式
    • 公式的解释
    • 分类

      • 有效公式
      • 矛盾公式
      • 可满足公式
    • 基本等价关系
    • 范式

      • 前束范式
      • Skolem标准型

谓词综合推理

  • 推理规律
  • 推理规则

    • US
    • UG
    • ES
    • EG

命题逻辑

命题

  • 命题连接词

    • 否定
    • 合取
    • 析取
    • 蕴含
    • 等价
  • 命题公式

    • 分类

      • 永真公式(重言式)
      • 永假公式(矛盾式)
      • 可满足式
    • 公式的等价

      • 基本等价公式

范式

  • 文字
  • 简单析取式(子句)

    • 合取范式
  • 简单合取式(短语)

    • 析取范式
  • 互补对
  • 主范式

    • 极小项、极大项
    • 求解

      • 公式法
      • 真值表技术

命题蕴含公式

  • 基本蕴含关系

    • 简化规则
    • ......
    • 二难推论

演绎法推理

  • 推理规则

    • P
    • T
    • CP
Last modification:June 22, 2020
博客维护不易,如果你觉得我的文章有用,请随意赞赏