离散数学速通

集合论

• 集合的三大特征
  • 互异性
  • 确定性
  • 无序性
• 子集, 真子集, 包含, 真包含
• 基数 / 势, 有限集, 无限集
  • 可数集, 不可数集, 等势
• 子集总数, 幂集
• 并集, 交集, 差集, 补集, 对称差

集合运算律 1

集合运算律 2

计数问题

• 加法原理, 乘法原理
• 排列问题, 组合问题
  • 圆排列
• 容斥原理, 鸽笼原理
• 离散概率, 概率函数
• 递归关系

命题逻辑

• 命题
  • 原子命题 / 简单命题, 复合命题
• 命题联结词
  • 否定
  • 合取
  • 析取
  • 蕴含
  • 双条件 / 等价

联结词真值表

• 命题公式, 命题变量
• 解释, 真值表
• 永真公式 / 重言式, 永假公式 / 矛盾式, 可满足公式
• 公式等价 : 任意解释下真值相同 永真

基本等价公式 1

基本等价公式 2

基本等价公式 3

• 代入定理, 替换定理
• 范式
  • 文字: 命题变元及否定
  • 子句: 有限个文字的析取式
  • 短语: 有限个文字的合取式
  • 互补对:
  • 析取范式, 合取范式: 外层是析取 / 合取
  • 主析取范式, 主合取范式
    • 极小项(合取), 极大项(析取)
    • 永真公式主合取范式为空, 永假公式主析取范式为空
• 推理
  • 前提, 结论
  • 判定定理
  • 推理规则
    • P 规则: 前提引用
    • T 规则: 逻辑结果引用
    • CP 规则: 附加前提规则, 从前提集合 和 推出 , 则从前提集合推出
  • 间接证明 (反证)

推理定律 1

推理定律 2

谓词逻辑

• 个体词, 谓词, 命题函数
• 个体常量, 个体变量, 个体域
• 全称量词, 存在量词, 作用变量
• 谓词公式
  • 常量符号, 变量符号, 函数符号, 谓词符号
  • 项, 原子谓词公式, 合式公式
  • 自由变元, 约束变元, 闭式
  • 解释
  • 有效公式, 矛盾公式, 可满足公式
    • 有效公式是可满足公式
  • 代入示例: 谓词公式代入命题公式

谓词演算的有效公式 1

谓词演算的有效公式 2

谓词演算的有效公式 3

• 范式
  • 前束范式: 所有量词都在最前端
  • Skolem 标准型: 消去前束范式的量词

谓词推理规律 1

谓词推理规律 2

谓词推理规律 3

• 谓词推理规则
  • US: , 所选用取代 的变元 在公式中必须是自由的
  • ES: 若还有其它自由变元时，则必须用关于自由变元的函数符号来取代常量符号.
  • UG: 所使用的变元符号不能与辖域内的变元符号相同.
  • EG: , 所使用的变元符号不能与辖域内的变元符号相同.

证明技术

• 直接证明 , 通过证明 永真
• 间接证明 , 通过证明 永真
• 空证明 , 证明 为假
• 平凡证明 , 证明 为真
• 归谬证明 , 找到矛盾式 使得 为真
• 分类讨论 , 证明
• 等价证明 , 证明
• 存在性证明, 唯一性证明
• 数学归纳法
  1. 归纳基础: 为真
  2. 对于任意 :
     • 归纳假设: 若 为真
     • 归纳结论: 为真
  3. 对所有整数 , 有 为真
• 强形式数学归纳法
  1. 归纳基础: 为真
  2. 对于任意 :
     • 强归纳假设: 若任意 为真
     • 归纳结论: 为真
  3. 对所有整数 , 有 为真

二元关系

• 序偶, 笛卡尔积, 重有序组
• 二元关系, 空关系, 全关系
  • 集合表示法, 关系图法, 关系矩阵
• 关系的复合运算, 逆运算
  • 

    关系运算律
• 关系的幂运算
• 关系的性质
  • 自反性:
  • 反自反性:
  • 对称性:
  • 反对称性:
  • 传递性:

我直接粘 PPT

我直接粘 PPT

• 闭包: 增加最少元素，使其具备所需性质的扩充.
  • 自反闭包, 对称闭包, 传递闭包

特殊关系

• 利用等价关系划分集合, 商集
• 偏序关系可绘制哈斯图
  • 自反性: 省去自环
  • 反对称性: 省去箭头, 小的画在下方
  • 传递性: 省去三角边
• 偏序集上: 最大元, 最小元, 极大元, 极小元
• 偏序集的子集: 上界, 下界, 上确界(最小上界), 下确界(最大下界)
• 全序 / 线序: , 哈斯图是一条链
• 良序: 任意非空子集都有最小元素
  • 有限全序集一定是良序集

函数

• 满射: 中的像在填满了集合 , 即 中每个元在 中都有原象.
• 单射: 中不同元的像不同.
• 双射 (1-1 映射): 既是单射又是满射.
• 单射 左可逆映射
• 满射 右可逆映射
• 双射 可逆映射
• 常用函数
  • 恒等函数
  • 常值函数
  • 特征函数
  • 上取整函数
  • 下取整函数
  • 布尔函数
• 复合, 逆运算
• 置换函数 (有限集合上的双射函数)

许可协议

本文采用 署名-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章