离散数学速通
离散数学集合论
- 集合的三大特征
- 互异性
- 确定性
- 无序性
- 子集, 真子集, 包含, 真包含
- 基数 / 势, 有限集, 无限集
- 可数集, 不可数集, 等势
- 子集总数, 幂集
- 并集, 交集, 差集, 补集, 对称差
![集合运算律 1](https://cdn.duanyll.com/img/20230221202928.png)
![集合运算律 2](https://cdn.duanyll.com/img/20230221203858.png)
计数问题
- 加法原理, 乘法原理
- 排列问题, 组合问题
- 圆排列
- 容斥原理, 鸽笼原理
- 离散概率, 概率函数
- 递归关系
命题逻辑
- 命题
- 原子命题 / 简单命题, 复合命题
- 命题联结词
- 否定
- 合取
- 析取
- 蕴含
- 双条件 / 等价
- 否定
![联结词真值表](https://cdn.duanyll.com/img/20230221210239.png)
- 命题公式, 命题变量
- 解释, 真值表
- 永真公式 / 重言式, 永假公式 / 矛盾式, 可满足公式
- 公式等价
: 任意解释下真值相同 永真
![基本等价公式 1](https://cdn.duanyll.com/img/20230221210925.png)
![基本等价公式 2](https://cdn.duanyll.com/img/20230221210952.png)
![基本等价公式 3](https://cdn.duanyll.com/img/20230221211039.png)
- 代入定理, 替换定理
- 范式
- 文字: 命题变元及否定
- 子句: 有限个文字的析取式
- 短语: 有限个文字的合取式
- 互补对:
- 析取范式, 合取范式: 外层是析取 / 合取
- 主析取范式, 主合取范式
- 极小项(合取), 极大项(析取)
- 永真公式主合取范式为空, 永假公式主析取范式为空
- 推理
- 前提, 结论
- 判定定理
- 推理规则
- P 规则: 前提引用
- T 规则: 逻辑结果引用
- CP 规则: 附加前提规则, 从前提集合
和 推出 , 则从前提集合推出
- 间接证明 (反证)
![推理定律 1](https://cdn.duanyll.com/img/20230221212235.png)
![推理定律 2](https://cdn.duanyll.com/img/20230221212255.png)
谓词逻辑
- 个体词, 谓词, 命题函数
- 个体常量, 个体变量, 个体域
- 全称量词, 存在量词, 作用变量
- 谓词公式
- 常量符号, 变量符号, 函数符号, 谓词符号
- 项, 原子谓词公式, 合式公式
- 自由变元, 约束变元, 闭式
- 解释
- 有效公式, 矛盾公式, 可满足公式
- 有效公式是可满足公式
- 代入示例: 谓词公式代入命题公式
![谓词演算的有效公式 1](https://cdn.duanyll.com/img/20230221214309.png)
![谓词演算的有效公式 2](https://cdn.duanyll.com/img/20230221214345.png)
![谓词演算的有效公式 3](https://cdn.duanyll.com/img/20230221214356.png)
- 范式
- 前束范式: 所有量词都在最前端
- Skolem 标准型: 消去前束范式的量词
![谓词推理规律 1](https://cdn.duanyll.com/img/20230221215447.png)
![谓词推理规律 2](https://cdn.duanyll.com/img/20230221215511.png)
![谓词推理规律 3](https://cdn.duanyll.com/img/20230221215924.png)
- 谓词推理规则
- US:
, 所选用取代 的变元 在公式中必须是自由的 - ES:
若还有其它自由变元时,则必须用关于自由变元的函数符号来取代常量符号. - UG:
所使用的变元符号不能与辖域内的变元符号相同. - EG:
, 所使用的变元符号不能与辖域内的变元符号相同.
- US:
证明技术
- 直接证明
, 通过证明 永真 - 间接证明
, 通过证明 永真 - 空证明
, 证明 为假 - 平凡证明
, 证明 为真 - 归谬证明
, 找到矛盾式 使得 为真 - 分类讨论
, 证明 - 等价证明
, 证明 - 存在性证明, 唯一性证明
- 数学归纳法
- 归纳基础:
为真 - 对于任意
: - 归纳假设: 若
为真 - 归纳结论:
为真
- 归纳假设: 若
- 对所有整数
, 有 为真
- 归纳基础:
- 强形式数学归纳法
- 归纳基础:
为真 - 对于任意
: - 强归纳假设: 若任意
为真 - 归纳结论:
为真
- 强归纳假设: 若任意
- 对所有整数
, 有 为真
- 归纳基础:
二元关系
- 序偶, 笛卡尔积,
重有序组 - 二元关系, 空关系, 全关系
- 集合表示法, 关系图法, 关系矩阵
- 关系的复合运算, 逆运算
- 关系的幂运算
- 关系的性质
- 自反性:
- 反自反性:
- 对称性:
- 反对称性:
- 传递性:
- 自反性:
![我直接粘 PPT](https://cdn.duanyll.com/img/20230221223003.png)
![我直接粘 PPT](https://cdn.duanyll.com/img/20230221223121.png)
- 闭包: 增加最少元素,使其具备所需性质的扩充.
- 自反闭包, 对称闭包, 传递闭包
特殊关系
关系 | 自反 | 反自反 | 对称 | 反对称 | 传递 | 例子 |
---|---|---|---|---|---|---|
等价关系 | ✔ | ✔ | ✔ | |||
偏序关系 | ✔ | ✔ | ✔ | |||
拟序关系 | ✔ | ✔ | ✔ |
- 利用等价关系划分集合, 商集
- 偏序关系可绘制哈斯图
- 自反性: 省去自环
- 反对称性: 省去箭头, 小的画在下方
- 传递性: 省去三角边
- 偏序集上: 最大元, 最小元, 极大元, 极小元
- 偏序集的子集: 上界, 下界, 上确界(最小上界), 下确界(最大下界)
- 全序 / 线序:
, 哈斯图是一条链 - 良序: 任意非空子集都有最小元素
- 有限全序集一定是良序集
函数
- 满射:
中的像在填满了集合 , 即 中每个元在 中都有原象. - 单射:
中不同元的像不同. - 双射 (1-1 映射): 既是单射又是满射.
- 单射
左可逆映射 - 满射
右可逆映射 - 双射
可逆映射 - 常用函数
- 恒等函数
- 常值函数
- 特征函数
- 上取整函数
- 下取整函数
- 布尔函数
- 复合, 逆运算
- 置换函数 (有限集合上的双射函数)