离散数学概念

命题演算

? 命题（真值确定但不一定要知道真假，比如“存在外星人”是一个命题，它的真值确定，即使我们不知道真值）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

原始命题/原子命题 复合命题 逻辑连接词 否定/┐ 合取/∧ 析取/∨

条件/→（┐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) 同构 重数 子图

本文来源：https://www.bwwdw.com/article/vjht.html