离散数学

这是一份功利性的复习资料，具体的学习内容不会在这里记录。

0. 集合论

集合构成的集合称为集合族。

用叉乘表示笛卡尔积。

幂集 $\mathcal P(X)$ 是集合 $X$ 所有子集构成的集合族，记作 $2^X$。

集合 $A,B$ 的对称差记作 $A\operatorname{\triangle}B=(A\operatorname{\backslash}B)\cup (B\operatorname{\backslash}A)$。

0.1 关系

从 $X$ 到 $Y$ 的一个（有序）关系是指一个 $R\subset X\times Y$。

$A$ 上有一些特殊的关系：

• 自反：$(x,x)\in R$。
• 反自反：$(x,x)\not\in R$。
• 对称：$(x,y)\in R\Rightarrow (y,x)\in R$。
• 反对称：$\forall x\ne y$，$(x,y)\in R,(y,x)\in R$ 不同时成立。
• 传递。

以及空关系 $\varnothing$，全域关系 $A\times A$，恒等关系 $I_a=\{(x,x)\mid x\in A\}$。

$\overline{R} = (A\times B)-R$。

关系的逆是 $R^{-1}$，本质上是转置矩阵，但显然不是逆矩阵。而关系的复合是矩阵乘法，所以满足矩阵的运算律。

关系的闭包是指在关系里提娜佳边使得它获得某种性质：

• 自反闭包 $r(R)=R\cup I_A$。
• 对称闭包 $s(R)=R\cup R^{-1}$。
• 传递闭包 $t(R)=\displaystyle\cup_{i=1}^n R^i$。

若 $R$ 满足自反，对称，传递，则是等价关系，通常记作 $\sim$。形如若干个完全子图（团）。

每个团都是一个等价类，对于其中一个元素 $x$ 的等价类，记作 $[x]_R$ 或者 $\bar x$ 或者 $x/R$。

集合 $A$ 的划分记作 $\Pi$。给定等价关系后可以确定商集 $A/\!\sim \; =\{[x]\mid x\in A\}$。

若 $R$ 满足自反，反对称，传递，则是偏序关系，通常记作 $\preccurlyeq$ 或者 $\le$。

若 $R$ 满足反自反，传递（此时自动反对称，采用反证法），则是拟序关系。

0.3 势

对于集合 $A,B$，如果存在一个从 $A$ 到 $B$ 的一一映射，则称集合 $A$ 和 $B$ 对等，记作 $A\sim B$，称 $A$ 和 $B$ 有相同的势（基数）。

设 $\mathbb N$ 的基数是 $\aleph_0$（阿列夫零），如果一个集合 $A$ 的势是 $\aleph_0$，那么 $A$ 是可数集。

1. 古典数理逻辑

1.1 命题逻辑

蕴含关系 $p\rightarrow q$ 等价于 $\neg p\lor q$，套了一层德摩根。

联结词的完备集：能用该集合中的联结词表达任何真值函数（任何命题公式）。

主析取范式（Principal Disjunctive Normal Form）：标准与或式。
主合取范式（Principal Conjunctive Normal Form）：标准或与式。

1.2 谓词逻辑

谓词逻辑使得逻辑的表达能力得到了巨大提升。

• 个体词
  • 个体常元：指某个具体的对象，比如我可能可以用 $s$ 表示苏格拉底。
  • 个体变元：泛指不确定的对象，比如用 $x$ 表示某个人。
• 谓词：描述变元的性质
  • 可以有 $n$ 元，比如说我可以定义 $L(s,p)$ 表示苏格拉底是个哲学家。
  • 本身不是命题，只有所有变元都被常元替换或被量词（诸如 $\forall x$）约束后，才变成命题。

根据这个逻辑，“所有人都会死”可以翻译成 $\forall x(Man(x)\rightarrow Mortal(x))$。

• 项是“可以指代一个对象”的东西。定义是递归的：个体词是项，函数作用在项上还是项。
• 若 $P$ 是 $n$ 元谓词符号，$t_1,\cdots,t_n$ 是项，则 $P(t_1,\cdots,t_n)$ 是原子公式。原子公式是最小的公式单元，不能拆开。
• 所有的原子公式都是合式公式（well-formed formula），逻辑运算和谓词也可以得到合式公式。量词后面的最短合式公式就是它的作用范围，所以注意加括号。

在谓词后面出现的变元称为约束出现，而不是约束出现的称为自由出现，这是一个自由变元，有自由变元的公式不是命题。

同种量词可以交换。

现阶段只研究一阶逻辑，它的量词只能作用于个体变元。也就是说，不允许量词作用于谓词。高阶逻辑没有一个完备的公理系统^[1]。

范式的目的是将任意谓词公式写成“量词在前，内核在后”的标准形态。

首先是前束范式（Prenex Normal Form），形如：

$$Q_1 x_1 \, Q_2 x_2 \, \dots \, Q_n x_n \; M$$

其中每个 $Q_i$ 是 $\forall$ 或 $\exists$，母式 $M$ 中不含量词。

首先要消除 $\rightarrow$ 和 $\leftrightarrow$，然后将所有的否定移到原子公式前面，最后不断前移量词即可。

Skolem 范式在前束范式基础上，消去所有存在量词，只保留全称量词，但引入新函数/常量来“模拟”存在性。

Skolem 化后的公式与原公式不逻辑等价，但保持一个关键性质：原公式可满足 当且仅当 Skolem 范式可满足（等可满足性）。

给定前束范式 $Q_1 x_1 \dots Q_n x_n M$。
从左到右扫描量词前缀，遇到 $\exists x_i$ 就执行：

• 情况A：$\exists x_i$ 前面没有全称量词（即它是最左端或前面都是 $\exists$），则用一个新的常量符号 $c$（Skolem 常量，在原语言中未出现）替换母体 $M$ 中所有 $x_i$ 的出现，并删除该 $\exists x_i$。
• 情况B：$\exists x_i$ 前面有 $m$ 个全称量词 $\forall y_1, \dots, \forall y_m$（即这些 $\forall$ 在该 $\exists$ 的左侧），则用一个新的 $m$ 元函数符号 $f(y_1,\dots, y_m)$（Skolem 函数，新符号）替换母体中所有 $x_i$，并删除该 $\exists x_i$。

保留所有 $\forall$ 量词和替换后的母式。

比如 $\exists x_1 \exists x_2 \forall x_3 \forall x_4 \exists x_5 \forall x_6 \exist x_7 P(x_1, x_2, x_3, x_4, x_5, x_6,x_7)$ 化 Skolem 范式就是 $\forall x_3 \forall x_4 \forall x_6 P\big(a, b, x_3, x_4, f(x_3, x_4), x_6, g(x_3, x_4, x_6)\big)$。

2. 图论

Dijkstra 按照 $O(n^2)$ 的方式求解，列表格 $S,|V| -S,d(i)$。

设图 $G$ 有哈密顿回路，则对任意顶点自己 $S\sub V$，都有 $\omega(G\backslash S)\le |S|$，其中 $\omega$ 代表该图的连通块数，判定时 $|S|\ge 1$。若存在哈密顿通路，则 $\omega(G\backslash S)\le |S|+1$。

3. 初等数论

模 $m$ 的同于关系是一个等价关系，每一个等价类是一个同余类（剩余类）。

从 $m$ 个同余类中各选区一个代表元，得到完全剩余系。

在试卷上书写 5 行表格来实现扩展欧几里得算法。始终有 $r_i=aS_i+bT_i$。开始时假设 $a\ge b$。当 $r_{k+1}=0$ 时，最终得到 $aS_k+bT_k=r_k=\gcd(a,b)$。

其中 $q,r$ 正在执行辗转相除，因此 $q_k=r_{k-2} \div r_{k-1}$，$r_k=r_{k-2}-q_k r_{k-1}$。非常巧妙的是 $S,T$ 的递推公式和 $r$ 长得一摸一样。

逆元存在的充要条件是 $\gcd(a,m)=1$。

CRT：$\sum b_iM_it_i$，其中 $M_i=\frac M {m_i}$，$M_i t_i\equiv 1\pmod m_i$。

将 $n$ 质因数分解，$\varphi(n)=n\prod \left(1-\frac 1 {p_i}\right)$。

欧拉定理：若 $\gcd(a,m)=1$，则 $a^{\varphi(m)}\equiv 1\pmod m$。