f(Program,Poet)=Programet

上图论之前，离散老师（很经典的一个人，见这里）问全班：觉不觉得离散数学概念很多？

全班（异口同声）：多……

老师：确实，我们离散数学前面几章的逻辑、集合的概念是很多的。不过，图论里面……

全班同学舒了口气……

老师：图论里面的概念……比前面的会更多。

………………………………

离散数学是计算机的基础吧，显然“计院”里的是要学的。打听了一下，现在大约只有计算机、数学、电子等专业可能要必修离散数学。我个人认为，其实离散数学还是很有意思的，只是那些概念很讨厌——经常是很多修饰词排列组合串在一起就成了一个概念（那些图灵们倒还真把离散组合数学用到这地方来了）。

快期考了，归纳一下吧。

学校的课本来自“华南理工大学出版社”，从印刷上来看，应该很烂（反正老师说不用老翻课本的，因为现在的书都是“编”多“著”少）。话说其实里面的内容还不错，很深入浅出，就是内容覆盖面小了一些。

鉴于这个学期考试只考数理逻辑、集合论（除无限集外的部分）和图论，于是我就只归纳这么多了。欢迎观摩、复习、怀念。

（如果你觉得下表很离散，那感觉就对了……）

概念名词列表（括号内的为一些细节说明）

命题演算

• 命题（真值确定但不一定要知道真假，比如“存在外星人”是一个命题，它的真值确定，即使我们不知道真值）
• 原始命题/原子命题
• 复合命题
• 逻辑连接词
• 否定/┐
• 合取/∧
• 析取/∨
• 条件/→（┐P∨Q）
• 双条件（不好意思，双向箭头字符未找到，(P∧Q)∨(┐P∧┐Q)）
• 真值表
• 命题公式/公式
• 命题变元
• 命题演算
• 等价（自反性、对称性、传递性，等价变换法俗称“少林派”）
• 结合律
• 交换律
• 分配律
• 德·摩根律/反演律
• 双重否定率
• 代换
• 蕴含（自反性、反对称性、传递性，蕴含推理法俗称“武当派”，传递法俗称“隔山打牛”）
• 对偶法则
• 对偶
• 不可兼析取（析取符上加一横，异或）
• 逆条件（条件符上加字母c）
• 与非/↑
• 或非/↓
• 结合力（ ⑴┐⑵∧⑶∨、不可兼析取、↑、↓⑷→、逆条件⑸双条件 ）
• 析取范式
• 合取范式
• 主析取范式（∑=m∨…）
• 主合取范式（∏=M∧…）
• 直接推演
• P规则
• T规则
• CP规则（俗称“北冥神功”）
• 间接推演/间接证明/反证法

谓词演算

• 谓词
• 个体
• 量词
• 全称量词（倒A，以下简写为V）
• 存在量词（倒E，以下简写为E）
• 自由变元
• 约束变元
• 作用域/辖域
• 改名
• 量词分配律（(Ex)[A(x)∨B(x)]<=>(Ex)A(x)∨(Ex)B(x)，(Vx)[A(x)∧B(x)]<=>(Vx)A(x)∧(Vx)B(x)）
• 量词转换率（┐(Ex)A(x)<=>(Vx)┐A(x)）
• 量词辖域扩张和收缩率
• 前束范式
• 全称指定规则/US
• 全称推广规则/UG
• 存在指定规则/ES
• 存在推广规则/EG

集合

• 集合
• 属于/∈
• 相等/=
• 包含（自反性、反对称性、传递性）
• 真包含/（
• 有限集
• 无限集
• 空集
• 全集
• 并/∪
• 交/∩
• 补
• 运算法则（对应命题逻辑运算法则）
• 差/-（A-B=A∩补B）
• 对称差（+外面加一个圈）
• 幂集/р(A)/2^A
• 包含排斥原理
• 直积/笛卡尔乘积
• 有序偶
• 有序n元组

关系

• 关系
• 前域/定义域/D()
• 后域/值域/R()
• 全域关系
• 空关系
• 表格表示法
• 矩阵表示法
• 关系图
• 交关系
• 并关系
• 关系的补
• 复合关系
• 逆关系
• 自反性
• 反自反性
• 对称性
• 反对称性
• 传递性
• 闭包
• 自反闭包/r(R)
• 对称闭包/s(R)
• 传递闭包/t(R)
• 集合的覆盖
• 集合的划分
• 等价关系（自反、对称、传递）
• 等价类/[x]
• 商集/“S/R={[x],[y],…}”
• 相容关系（自反、对称）
• 最大相容类
• 偏序关系（自反、反对称、传递）
• 偏序集
• 全序关系
• 全序集
• 哈斯图/偏序集图（不唯一）
• 极大元
• 极小元
• 最大元
• 最小元
• 上界
• 下界
• 上确界/最小上界
• 下确界/最大下界
• 良序集（有限全序集）

图论

• 图/G(V,E)
• 有序偶/弧
• 有向图
• 无序偶/边
• 无向图
• 顶点/结点
• 顶点集/V
• 弧/有向线
• 弧集/E
• 环
• 孤立点
• 邻接
• 边/线
• 边集
• 度数/d(v)
• 同构
• 重数
• 子图
• 生成子图
• 边导出子图/G(E’)
• 删除运算
• 收缩运算
• 图的并
• 图的交
• 图的环合
• 空图（V为空）
• 不相交（G1∩G2=空图）
• 零图（E为空）
• 边不相交（G1∩G2=零图）
• 完全图
• r-正侧图
• 二分图
• 二划分
• 完全二分图
• 多重图
• 多重集合
• 平行边
• 多重边
• 简单图（不含环、平行边）
• 带权图
• 边序/通道
• 边序起点
• 边序终点
• 边序长度
• 距离
• 迹
• 路
• 闭迹
• 闭路
• 开迹
• 开路
• 回路（至少包含一条边的闭路）
• 偶回路
• 奇回路
• 连通
• 连通图
• 可达
• 单向连通
• 强连通
• 弱连通
• 欧拉图
• 欧拉闭迹/欧拉迹
• 半欧拉图
• 欧拉开迹
• 奇顶点
• 偶顶点
• 欧拉有向图
• 入度
• 出度
• 哈密顿图
• 哈密顿回路
• 半哈密顿图
• 货郎担问题
• 树
• 树叶/悬挂点
• 分支点/内点
• 森林
• 生成树
• 树枝/枝
• 弦
• 余树
• 秩/枝数（顶点数-分支数）
• 边割
• 割集（最小边割）
• 桥
• 基本回路
• 基本回路组
• 基本割集
• 基本割集组
• 最小生成树
• 克鲁斯克尔算法/Kruskal
• 有向树
• 根树
• 儿子
• 父亲
• 兄弟
• 子孙
• 祖辈
• 以u为根的子树
• 有序树
• 先根次序
• 中根次序
• 后根次序
• 二叉树
• m叉树
• 完全m叉树
• 正则m叉树
• 关联矩阵/A(G)（v*e）
• 基本关联矩阵
• 参考点
• 回路矩阵/B(G)（g*e）
• 割集矩阵/C(G)（m*e）
• 邻接矩阵/X(G)（v*v）
• 矩阵乘法
• 平面图
• 欧拉公式/欧拉定理
• 库拉托斯基定理
• 彼得森图
• 着色
• 四色定理
• n色图
• 面
• 对偶图/G*
• 韦尔奇·鲍威尔法/Welch Powell
• 二分图
• 互补顶点子集
• 奇回路
• 偶回路

本文由 最后的叶子 创作，转载或引用前请联系我们。

2009年12月14日 星期一