摘要
数据库论文中有许多数学表达式和离散数学概念，本文以蚂蚁老师 2021Spring 的离散数学为大纲，总结了常用的离散数学基础知识，以供参考。
离散数学概论
三个公理系统：逻辑、集合论、抽象代数（群论）。
逻辑
逻辑是研究推理和证明的一门学科，其中一个基本问题是确定何种推理是正确和合法的。
正确性
如果前提集合 \(\set{\alpha, \beta, \gamma, ...}\) 中的每个命题都为真，则结论 \(\tau\) 也为真。符号表示为：
\[ \set{\alpha, \beta, \gamma, ...} \models \tau \]
证明
就是一系列根据推理规则将公式不断变形的步骤。符号表示为：
\[ \set{\alpha, \beta, \gamma, ...} \vdash \tau \]
或者
\[ \frac{\alpha \beta \gamma}{\tau} \]
集合论
关系
$$ \[\begin{align*} 自反性: & \forall a \in X. (a, a) \in R \quad \\ 对称性: & \forall a, b \in X. ((a, b) \in R \rightarrow (b, a) \in R) \quad \\ 反对称性: & \forall a, b \in X. ((a, b) \in R \land (b, a) \in R \rightarrow a = b) \quad \\ 传递性: & \forall a, b, c \in X. ((a, b) \in R \land (b, c) \in R \rightarrow (a, c) \in R) \quad \\ 连接性: & \forall a, b \in X. ((a, b) \in R \lor (b, a) \in R) \quad \\ \text{自反性} + \text{反对称性} = & \text{相容关系} \\ \text{自反性} + \text{反对称性} + \text{传递性} = & \text{偏序关系} \\ \text{自反性} + \text{对称性} + \text{传递性} = & \text{偏序关系} \\ \text{自反性} + \text{反对称性} + \text{传递性} + \text{连接性} = & \text{全序关系} \end{align*}\] $$
图论
若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。求双连通分量可用 Tarjan 算法。
