离散数学基础知识

摘要

数据库论文中有许多数学表达式和离散数学概念，本文以蚂蚁老师 2021Spring 的离散数学为大纲，总结了常用的离散数学基础知识，以供参考。

离散数学概论

三个公理系统：逻辑、集合论、抽象代数（群论）。

逻辑是研究推理和证明的一门学科，其中一个基本问题是确定何种推理是正确和合法的。

如果前提集合 ${α, β, γ, . . .}$ 中的每个命题都为真，则结论 $τ$ 也为真。符号表示为：

{α, β, γ, . . .} ⊨ τ

就是一系列根据推理规则将公式不断变形的步骤。符号表示为：

{α, β, γ, . . .} ⊢ τ

或者

\frac{α β γ}{τ}

\begin{aligned} 自 反 性 : & \forall a \in X . (a, a) \in R \\ 对 称 性 : & \forall a, b \in X . ((a, b) \in R \to (b, a) \in R) \\ 反 对 称 性 : & \forall a, b \in X . ((a, b) \in R \land (b, a) \in R \to a = b) \\ 传 递 性 : & \forall a, b, c \in X . ((a, b) \in R \land (b, c) \in R \to (a, c) \in R) \\ 连 接 性 : & \forall a, b \in X . ((a, b) \in R \lor (b, a) \in R) \\ 自反性 + 反对称性 = & 相容关系 \\ 自反性 + 反对称性 + 传递性 = & 偏序关系 \\ 自反性 + 对称性 + 传递性 = & 偏序关系 \\ 自反性 + 反对称性 + 传递性 + 连接性 = & 全序关系 \end{aligned}

若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。求双连通分量可用 Tarjan 算法。