离散数学概念

2023年12月20日发(作者：囊谦县中考数学试卷及答案)

命题演算

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





















































原始命题/原子命题

复合命题

逻辑连接词

否定/┐

合取/∧

析取/∨

条件/→（┐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

二分图

互补顶点子集

奇回路

偶回路