离散数学（二）

这是离散数学（二）的合并笔记。正文先整理数论与同余、组合计数和逻辑，最后汇总对应证明；原笔记中尚未展开的高级计数部分保留为提纲说明。

数论和密码学

除法和模运算

整除

定义

如果a，b是整数，且a != 0，那么如果存在一个整数c，使得b = a * c，则称a整除b，记作a | b。

性质

定理1. a b c 都是整数，且a != 0，那么有：

• 若a | b 且 a | c，那么a | (b + c)；相关证明
• 若a | b，那么a | bc对所有的整数c都成立；
• 若a | b 且 b | c，那么a | c；

除法算法

1. 定义：若a是整数，b 是正整数，则存在唯一的整数 q 和 r，使得 0≤r<b， 并且 a=bq+r。相关证明
2. 换言之，可以尝试通过将一个数字分解为除数乘以商加余数的形式来对问题进行分析。
3. 良序原理：每个非空的自然数集都有最小的元素。

同余关系

定义

如果 a 和 b 是整数，且 m 是正整数，那么当 m 整除 a−b 时，称 a 与 b 在模 m 下同余，记作 a ≡ b (mod m)。

性质

• 除数的唯一性:定理2. 设 m 为正整数。当且仅当存在一个整数 k 使得a=b+km，整数 a 和 b 在模 m 意义下同余。相关证明
• 对称性：a ≡ a (mod m)
• 自反性/反身性：若a ≡ b (mod m) 则b ≡ a (mod m)
• 传递性：若a ≡ b (mod m)且b ≡ c (mod m) ，则a ≡ c (mod m)

附注

(mod m) 和 mod m的区别：

• 前者类似表明一种性质，表示模m的意义下二者同余
• 后者表示一种运算，是一个返回余数的函数
• 定理 3:设 a 和 b 为整数，m 为正整数，则 a≡b (mod m) 当且仅当 a mod  m=b mod  m.

运算

同余式的加法和乘法运算

定理 4:设 m 为正整数。如果 a≡b (mod m) 且 c≡d (mod m)，则 a+c≡b+d (mod m) 且 ac≡bd (mod m)。相关证明 定理4推论1：将有效同余式的两边同时乘以一个整数会保持其有效性；将一个整数加到一个有效同余式的两边也会保持其有效性。 值得注意的是，将同余式两边同时除以一个整数并不总能产生有效的同余关系。 定理4推论2:设 m 为正整数，a 和 b 为整数，则 (a + b) (mod m) = ((a mod m) + (b mod m)) mod m 且 ab mod m = ((a mod m) (b mod m)) mod m 换言之，和的模等于模的和的模，积的模等于模的积的模，可以看成一种简化运算

二进制模幂算法

将非负指数写成 $n=\sum_j a_j2^j$，其中 $a_j\in\{0,1\}$。于是

连续平方得到 $b,b^2,b^4,\ldots$，每一步取模，再将指数位为 1 的因子相乘并取模。不需要先构造巨大的整数幂。

群，环，域

原笔记尚未展开这一主题。

模m算数运算

定义

给定一个$Z_m$是一个包含从0到m-1的非负整数的集合，即{0，1，…，m-1}

• 加法 $+_m$ 定义为$a+_mb=(a+b)mod m$
• 乘法 $·_m$ 定义为$a·_mb=(a·b)mod m$
• 这些运算被称为模m的算数运算

素数和最大公约数

素数

定义

对于一个大于1的正整数p，若p的正因子只有1和p本身，则称p为素数；一个大于1且非素数的正整数称之为合数。

算数基本定理

定理：每一个大于1的正整数都可以唯一的表示为一个素数，或者表示为两个或更多素数的乘积，其中素因数按照大小不减的顺序排列。即$p=a_1a_2...a_n$，其中$a_1\leq a_2...\leq a_n$ 相关证明

最大公约数

定义

设a,b为整数，且不全为0。能够同时整除a和b的最大整数d称为a和b的最大公约数，记作$gcd(a,b)$ 值得注意的是，当a,b两者中存在负数时可以将其视作绝对值，因为定义为最大整数。

最大公约数表示成一个线性组合

定理：若a和b是任意整数且不全为0，则$gcd(a,b)$是集合$\{ax+by|x,y \in Z\}$中的最小正整数元素。相关证明 推论：对于整数a和b,若d|a且d|b，则d | gcd(a,b) 贝祖定理：若a和b是正整数，则存在整数s和t使得gcd(a,b) = sa+tb.这样的s和t被称为贝祖系数。

素数测试及试除法

试除法

定理：若a是合数，则a必有小于或等于$\sqrt{a}$的因子。 推论：若a是合数，则a必有小于或等于$\sqrt{a}$的素因子。相关证明 试除法：依次将小于等于$\sqrt{a}$的素数除a来判断a是否是素数。

埃拉托斯特尼筛法

输入：正整数 n 输出：所有小于等于 n 的素数

1. 创建布尔数组 isPrime[2..n]，初始化所有值为 true
2. 从 p = 2 开始
3. 当 p² ≤ n 时： a. 如果 isPrime[p] 为 true：
   • 从 p² 开始，标记 p 的所有倍数为 false
   • 步长为 p b. p = p + 1
4. 收集所有 isPrime[i] 为 true 的 i 值
5. 返回素数列表 换言之，其实就是从前往后遍历进行排除的过程。

无穷素数

定理

素数的个数是无限的。相关证明

梅森素数

定义

形如$2^{p} - 1$的素数，其中p为素数，被称为梅森素数。 那么反过来，当n是合数时，$2^n - 1$一定是合数：$2^{ab} - 1 = (2^a - 1)(2^{a(b - 1)} + 2^{a(b - 2)} + ...+2^a + 1)$

素数的分布规律

不超过x的素数个数与$\frac{x}{ln x}$的比率随着x的增大而趋近于1. 由该定理可知：

• 不超过x的素数个数可以用$\frac{x}{ln x}$来近似；
• 随机选择一个小于n的正整数是素数的概率大约是$\frac{(\frac{n}{ln n})}{n} = \frac{1}{ln n}$.

生成素数

不能把任意整数多项式的所有取值都当作素数。实际生成大素数通常从候选整数开始并进行适当的素性测试；“没有简单函数能总产生素数”并不是可据此笼统断言的定理。

互素

定义

如果两个整数a和b的最大公约数为1，则称a和b互素。

素因子分解法找最大公约数

$a = p_1^{a_1}p_2^{a_2}...p_n^{a_n}$，$b = p_1^{b_1}p_2^{b_2}...p_n^{b_n}$， 其中每个指数都是非负整数，且两个素因数分解中出现的所有素数都包含在两者当中，那么： $gcd(a,b) = p_1^{min(a_1,b_1)}p_2^{min(a_2,b_2)}...p_n^{min(a_n,b_n)}$.

欧几里得算法/辗转相除法

理论基础：当$a \geq b,\quad c = a \bmod b$，则$gcd(a,b) = gcd(b,c)$。 相关证明

辗转相除法其实就是不断用大者除以小者，而后小者更新为大者，余数更新为小者，直到小者为0循环终止。

最小公倍数

定义

正整数 a 和 b 的最小公倍数是同时能被a和b整除的最小正整数，记作 lcm(a, b). 最小公倍数也可以通过素因数分解来计算： $lcm(a,b) = p_1^{max(a_1,b_1)}...p_n^{max(a_n,b_n)}$

求贝祖系数

贝祖定理

定义

若 a 和 b 是正整数，则使得 gcd(a, b) = sa + tb的整数 s 和 t 称为 a 和 b 的贝祖系数

两步法求贝祖系数

简言之，就是先通过欧几里得算法求出最大公约数，然后通过前述运算过程回代得到贝祖系数

扩展欧几里得算法求贝祖系数

目标：求满足$xa + yb=\gcd(a,b)$的x和y，假设$a \geq b$ 通过欧几里得算法，gcd(a,b) = gcd(b,a mod b) 设 r=a mod b，递归求得 x’b+y’r=gcd(b,r)，再将 r=a−⌊a/b⌋b 代入 这样我们就可以依次进行迭代：$x = y',\quad y = x' - y' \lfloor a/b \rfloor$ 直到得到我们需要的系数。

同余式的除法

定理：设m为正整数，a，b，c是整数，若$ac \equiv bc \pmod m$且$\gcd(c,m) = 1$，那么$a \equiv b \pmod m$ 相关证明

求解同余方程

线性同余式

定义

形如$ax \equiv b \pmod m$的同余式，其中m为正整数，a和b是整数，x是变量，称为线性同余式。 线性同余式$ax \equiv b \pmod m$的解是所有满足该同余式的整数x

逆元

若整数$\overline{a}$满足$\overline{a}a \equiv 1 \pmod m$，则称$\overline{a}$为a模m的逆元。 定理1：若 a 与 m 互素且 m>1，a 的逆元在模 m 意义下唯一，或在 0 到 m−1 中有唯一代表 相关证明

逆元求解

欧几里得算法和贝祖系数提供了一种系统求解逆元的方法 目标：求解a在模m下的逆元 方法：

• 扩展欧几里得算法求解$xa + ym = \gcd(a,m) = 1$
• 两边同时模m，可得$xa \equiv 1 \pmod m$ 前提：gcd(a,m) = 1 结果：$ax \equiv b \pmod m$，$\overline{a}a \equiv 1 mod m$， 那么$\overline{a}ax \equiv x \equiv \overline{a}b \pmod m$ 可以求解同余方程

中国剩余定理

定理2：设$m_1,m_2,...,m_n$是两两互素且大于1的正整数，$a_1,a_2,...,a_n$是任意整数，那么以下同余方程组： $x \equiv a_1 \pmod {m_1}$ $x \equiv a_2 \pmod {m_2}$ … $x \equiv a_n \pmod {m_n}$ 有唯一的解模$m = m_1m_2...m_n$ / 即存在解x，使得$0 \leq x < m$，且所有其他解与该解模m同余 求解过程：

1. 计算所有模的积$m = m_1m_2...m_n$
2. 针对每个同余方程$x \equiv a_k \pmod {m_k}$，
   1. 计算$M_k = \frac{m}{m_k}$
   2. 利用扩展欧几里得算法计算模$M_k$在模$m_k$下的逆元，记作$M_k^{-1}$
3. $x = (\sum_{i=1}^{n}a_iM_iM_i^{-1}) \mod m$ 相关证明

回代法

将每一个同余方程转化为等式，代入变量的值到另一个同余方程中，持续该过程直到解出所有同余方程 简言之，其实就是瞪眼法

Wilson定理

定理：对于整数 p>1，p 是素数当且仅当$(p-1)! \equiv -1 \pmod p$ 相关证明

欧拉函数

定义

$\phi(n)$：定义为比n小且与n互质的正整数的个数

性质

• 若p是素数，则$\phi(p) = p -1$
• 若n是合数且n=pq,其中p和q是两个不同的素数，则$\phi(n) = (p-1)(q-1)$
• 若n是合数且n = pq,其中p,q互质，那么$\phi(n) = \phi(p) \phi(q)$

欧拉定理

定理：若gcd(a,n)=1，则$a^{\phi(n)} \equiv 1 \pmod n$ 推论：若gcd(a,n)=1，则$a^x \equiv a^{x \mod {\phi(n)}} \pmod n$ 相关证明 欧拉定理在后续的密码学中还会有涉及，较为重要，应当掌握。

费马小定理

定理：如果p是一个素数且a是一个不被p整除的整数，则有$a^{p-1} \equiv 1 \pmod p$；此外，对于每个整数a，都有$a^p \equiv a \pmod p$，

• 若a与p互素，$a^p \equiv a \pmod p \leftrightarrow a^{p-1} \equiv 1 \pmod p$
• 若a与p不互素，$a^p \equiv a \equiv 0 \pmod p$

伪素数

定义

设 b 是一个正整数。如果 n 是一个合数，且 $b^{n-1} ≡ 1 \pmod n$，那么 n 被称为基数 b 的伪素数

补充

给定一个正整数n，

• 若$2^{n-1} \not\equiv 1 \pmod n$，那么n是合数
• 若$2^{n-1} \equiv 1 \pmod n$，那么n可能是素数，也可能是基数2的伪素数

原根

定义

一个素数p的原根是指$Z_p$中的一个整数r，使得$Z_p$中的每一个非零元素都是r的某个幂 换言之，其实就是对于一个数字的最小分隔集，我们要找这样的一个数字r使得这个集合内的每一个元素能够与r的某个幂次形成一一对应关系。此时我们就能够说r是素数p的一个原根。 应当注意的是，对于每一个素数p，总存在一个原根。

离散对数

定义

设 p 是一个素数，r 是模 p 的一个原根，且 a 是位于 1 到 p−1之间的整数。若 $r^e \mod p = a$，且 1 ≤ e ≤ p − 1，我们称 e 为模 p以 r 为底数的 a 的离散对数， 写作$log_r a = e$ (其中素数p是默认的). 换言之，其实就是上文中提到的那个幂次被称之为离散对数 值得注意的是，目前没有已知的多项式时间算法来计算离散对数

同余式的应用

哈希函数

定义

哈希函数 ℎ 将具有键 k 的记录分配到存储位置 ℎ(k) 不同键可能得到相同哈希值，称为碰撞；哈希映射一般不是单射。

伪随机数

确定性算法可以生成具有某些统计特征的序列。普通伪随机序列与密码学安全随机数不是同一概念；仅凭表面看起来随机不能判断安全性。

数字校验位

校验位：UPCs

在末尾添加一个额外的数字，并通过特定函数进行评估。若末尾数字不正确，则判定该字符串不正确.

校验位：ISBN-10

图书通过国际标准图书编号（ISBN-10）来识别，为10位数字代码。前9位用于标识语言、出版社和图书。第10位是校验位，通过以下关系确定： $x_{10}=\left(\sum_{i=1}^{9}i x_i\right)\bmod 11$；若值为 10，用 X 表示。这是 ISBN-10 的加权校验约定，不适用于 ISBN-13。

密码学

以下为理解模运算的教学模型，不直接作为实际系统的加密实现。

凯撒密码与仿射密码

将字母编号为 0 到 25。移位密码为 $E(p)=(p+k)\bmod26$，解密为 $D(c)=(c-k)\bmod26$。

仿射密码为 $E(p)=(ap+b)\bmod26$。只有 $\gcd(a,26)=1$ 时，$a$ 才有逆元，此时

这类单字母替换会保留可分析的统计结构，不宜用于现实保密任务。

分块与置换

原笔记中的方法是把消息按固定长度分块，再按一个置换重排块内字母位置，属于分组置换密码示例。它不等同于现代分组密码的完整设计。

密码系统的定义

密码系统可写成五元组 $(P,C,K,E,D)$，分别对应明文空间、密文空间、密钥空间、加密函数集合和解密函数集合。正确性要求对允许的明文和密钥有 $D_k(E_k(p))=p$。

RSA 教学模型

取不同素数 $p,q$，令 $n=pq$。选取满足 $\gcd(e,\phi(n))=1$ 的公开指数 $e$，求 $ed\equiv1\pmod{\phi(n)}$。

• 公钥是 $(e,n)$。
• 私钥涉及 $d$，并须保护 $p,q$ 等秘密参数。
• 对 $0\le m<n$，教学式加密为 $c=m^e\bmod n$，解密为 $m=c^d\bmod n$。

这是 textbook RSA；实际加密与签名需要各自合适的编码、填充与协议，不能把这些整数幂公式直接当作安全应用方案。

Diffie–Hellman 密钥交换

在适当选择的有限群中，双方公开群参数和生成元 $g$，分别保留秘密指数 $a,b$，交换 $g^a$、$g^b$，然后各自计算 $g^{ab}$。在模素数的教学写法中：

DH 本身做密钥协商，不是“私钥签名后公钥加密”；未经身份认证的交换还可能遭到中间人攻击，认证需要另外的协议机制。

计数

计数基础

乘法法则、加法法则和减法法则

依次完成的选择数相乘；互斥情形的选择数相加；有重叠的两类用容斥式 |A∪B|=|A|+|B|−|A∩B|，不能把相交的情形直接相加。

除法法则

若某项任务可通过 n种办法完成，且对于每一种方式 w， 正好有 d 种办法对应于该方式，那么完成这项任务的方式总数为 n/d.

树状图

我们可以通过使用树状图解决许多计数问题，其中分支代表可能的选择，叶子代表可能的结果.

鸽巢原理

定义

若k是一个正整数，将k+1个物体放入k个盒子中，则至少一个盒子包含两个或更多的物体。

推论

从一个具有 k+1 个元素的集合到一个具有 k 个元素的集合的函数 f 不是一一对应的

广义鸽巢原理

如果将N个物体放进k个盒子当中，那么至少有一个盒子包含至少$\lceil \frac{N}{k} \rceil$个物体。 相关证明

排列和组合

排列

定义

一组不同对象的排列是这些对象的有序序列。集合中 r 个元素的有序序列称为 r-排列.具有n个元素的集合的r-排列的数量记为P(n,r).

公式

定理1：:若n 是正整数，且 r 是满足 1≤r≤n 的整数，则对于一个有 n 个不同元素的集合，其 r-排列的数量为

推论1：若n和r是满足$1 \leq r \leq n$的整数，那么

组合

定义

一个集合元素的 r-组合 是从集合中无序选择 r 个元素。因此，r-组合只是一个包含 r 个元素的子集。具有 n 个不同元素的集合的 r-组合的数量记作 C(n, r)或 $\binom{r}{n}$ ，也称为二项式系数

公式

定理2：当$0 \leq r \leq n$时，具有n个元素的集合的r-组合数量为

推论2：设n和r是非负整数，且$r \leq n$，则$C(n,r) = C(n,n-r)$

组合证明

组合证明是指使用以下方法之一来进行恒等式的证明：

• 双计数证明：使用计数论证来证明恒等式两边以不同的方式计算相同的对象
• 双射证明：恒等式两边所计数的对象集合之间存在双射关系

二项式系数和恒等式

二项式定理

定理：设x和y是变量，n为非负整数，那么

换言之，其实就是选取特定数量的项的意思

有用的恒等式

定理1：当$n \geq 0$，

换言之，其实就是$(1+1)^n = 2^n$应用二项式定理得到的结果 帕斯卡恒等式：若n和k是整数，且满足$0 \leq k \leq n$，则C(n+1,k) = C(n,k-1) + C(n,k) 换言之，这个是杨辉三角的经典小推论

广义排列和组合

接下来是一些需要记忆一下的内容

带重复的排列

定理1：允许重复的情况下，从n个对象的集合中选取r个对象的排列数为$n^r$ 换言之，乘法原理，不用管

带重复的组合

定理2：当允许元素重复时，从一个包含n类元素的集合中选择r个元素的组合数是C(n+r-1,r) = C(n+r-1,n-1) 换言之，这个方法的意味是指顺序不重要下可重复选取物品的公式是物品类型+选取个数-1来C选取个数个

带有不可区分对象的排列

定理3：有n个对象，其中有$n_1$个不可区分的类型1对象，…，$n_k$个不可区分的类型k对象，不同排列的数量是

换言之，类似定序，即全排列之后进行序数的“剥离”，把不同的有序数要求的要求给削弱掉

将对象分配到盒子里

先明确物体和盒子是否可区分、盒子是否允许为空，以及是否指定每盒数量。

母函数

母函数是一种使用多项式函数来对情况进行分析的方法，其特点有：

• 使用代数运算取代逻辑推理
• 涵盖所有情况 基本思想：把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造

定义

对于序列$a_0,a_1,...,$ 函数$G(x) = a_0 + a_1x +a_2x^2 + ...$称为该序列的母函数。

整数的拆分

以下区分有序合成与无序分拆，且各部分为正整数。

• 将 $N$ 有序拆成恰好 $r$ 个正整数，有 $\binom{N-1}{r-1}$ 种（$N\ge r\ge1$）。允许零时公式不同。
• 将 $N$ 无序分拆为不同正整数的方案数，等于将它分拆为奇数部分的方案数。
• 每个部分重复次数不超过 $k$ 的分拆数，等于所有部分均不被 $k+1$ 整除的分拆数。
• 只有限制每个 2 的幂至多使用一次时，二进制分解才唯一。若允许重复，$4=4=2+2=2+1+1=1+1+1+1$，便不唯一。

若有序合成的允许部分集合为有限正整数集合 $A$，令 $F(x)=\sum_{a\in A}x^a$，则包含空合成的普通生成函数为

其中 $x^N$ 的系数给出所需数量。这里作为形式幂级数运算，不要求选取某个数值 x 后讨论收敛。

指数型母函数

定义

对于序列$a_0,a_1,...,$ 函数$G(x) = a_0 + \frac{a_1}{1!}x +\frac{a_2}{2!}x^2 + ...$称为该序列的指数型母函数。

高级计数：原笔记中的提纲

原稿目前仅列出递推关系、常系数齐次与非齐次递推、分治递推、生成函数和容斥原理，尚未形成完整推导。这里保留主题范围，不将空标题冒充已完成内容。

数理逻辑

下文采用非空论域的经典一阶逻辑。

命题逻辑

命题

定义

具有确切真值的陈述句。命题可以取一个值，称为真值。 真值只有真和假两种，用T/1和F/0表示。

分类

• 原子命题：不能再分解为更简单命题的命题。
• 复合命题：可以再分解为更简单命题的命题。

命题联结词

• 否定联结词：$\neg P$
• 合取联结词：$P \land Q$
• 析取联结词：$P \lor Q$
• 蕴含联结词：$P \rightarrow Q$

• 等价联结词：$P \leftrightarrow Q$

善意推定

在自然语言中，前件为假，不管结论真假，整个语句的意义，往往无法判断。但在数理逻辑中，当前件P为假时，不管Q的真假如何，则P→Q都为真。此时称为“善意推定”。 值得注意的是，自然语言的条件句常带有语境约束；这里的实质蕴含只按真值表定义，不要求因果联系。

命题公式、解释与真值表

命题公式

定义：当构成复合命题的原子命题是变元时，这个复合命题就可以看作原子变元的真值函数，或者称之为命题公式。

公式的解释

定义：设$P_1,P_2,...P_n$是出现在公式G中的所有命题变元，指定$P_1,P_2,...,P_n$一组真值，那么这组真值称为G的一个解释，常记为I。 一般来说有n个命题变元的命题的解释会有$2^n$个。 若公式G在解释I下是真的，则称I满足G；反之，则称I弄假G。 真值表：将公式G在其所有可能解释下的真值情况列成的表。 公式分类：

• 永真公式/重言式
• 永假公式/矛盾式
• 可满足的公式（如果该公式不是永假的） 定理：公式G、H等价的充分必要条件是公式$G \leftrightarrow H$是永真公式

代入定理

设$G(P_1,P_2,...,P_n)$是一个命题公式，其中$P_1,P_2,...,P_n$是命题变元，$G_1(P_1,P_2,...,P_n)$，$G_2(P_1,P_2,...,P_n)$，…，$G_n(P_1,P_2,...,P_n)$是任意的命题公式，分别用$G_1,G_2,...,G_n$取代原命题的$P_1,P_2,...,P_n$，得到新的命题公式

若G是永真公式/永假公式，那么G’也是永真公式/永假公式。

替换定理

设$G_1$是G的子公式（即$G_1$是G的一部分），$H_1$是任意的命题公式，在G中凡是出现$G_1$出都用$H_1$替换后得到新的命题公式H，若$G_1 = H_1$，则G=H。

范式

范式即是公式的标准型

定义

1. 命题变元或者命题变元的否定称为文字
2. 有限个文字的析取称为子句；若干短语的析取是析取范式（DNF）。
3. 有限个文字的合取称为短语；若干子句的合取是合取范式（CNF）。
4. P与$\neg P$称为互补对

• 一个短语/子句也可以是析取范式/合取范式 定理：对于任意命题公式，都存在与其等价的析取范式和合取范式

极小项和极大项

定义：在含有n个命题变元$P_1,P_2,...,P_n$的短语/子句中，若每个命题变元预期否定不同时存在，但二者之一恰好出现且仅出现依次，则称此短语/子句为关于$P_1,P_2,...,P_n$的一个极小项/极大项 性质：

• 任意两个不同极小项的合取必为假
• 任意两个不同极大项的析取必为真
• 极大项的否定是极小项
• 极小项的否定是极大项
• 所有极小项的析取为永真公式
• 所有极大项的合取是永假公式

主析取范式和主合取范式

定义：

• 在给定的析取范式中，每一个短语都是极小项，则称该范式是主析取范式；
• 在给定的合取范式中，每一个子句都是极大项，则称该范式是主合取范式；
• 若一个主析取范式不包含任何极小项，则称该主析取范式为空；
• 若一个主合取范式不包含任何极大项，则称该主合取范式为空 定理：任何一个公式都有与之等价的主析取范式和主合取范式 值得注意的是，主析取范式中能且只能包含使得公式真值为真的那些解释对应的极小项；主合取范式中能且只能包含那些使得公式真值为假的那些对应的极大项

谓词逻辑

换言之，谓词逻辑是在赋予主题性质

个体词与谓词

定义

在原子命题中，可以独立存在的客体，称为个体词，而用以刻划客体的性质或客体之间的关系就是谓词。

分类

• 表示具体某个物体的叫做个体常量
• 用以泛指的或抽象的个体词称为个体变量

个体域

个体词的取值范围称之为个体域/论域，常用D表示； 宇宙间所有个体聚集在一起所构成的个体域称为全总个体域

n元谓词

设D为非空的个体域，定义在$D^n$上取值于{0,1}上的n元函数，称之为n元命题函数/n元谓词，记作$P(x_1,x_2,...,x_n)$，此时个体变量$x_1,x_2,...,x_n$的定义域为D，$P(x_1,x_2,...,x_n)$的值域为{0,1}

量词

定义

称$\forall x$为全称量词，$\exists x$为存在量词 其中x被称为作用变量，一般将量词加在谓词之前，此时我们的谓词就被称为量词的辖域

项

定义

谓词逻辑中的项，被递归的定义：

• 任意的常量符号或任意的变量符号是项；
• 若$f(x_1,x_2,...,x_n)$是n元函数符号，$t_1,t_2,...,t_n$是项，那么$f(t_1,t_2,...,t_n)$是项
• 仅由有限次前两部推导得到的符号串才能称之为项

原子公式

若$P(x_1,x_2,...,x_n)$是n元谓词，$t_1,t_2,...,t_n$是项，那么$P(t_1,t_2,...,t_n)$被称为原子谓词公式，简称原子公式

合式公式

满足下述条件的表达式，称合式公式，简称公式：

• 原子公式是合式公式
• 若G,H是合式公式，那么否定、合取、析取、蕴含、等价运算得到的也是合式公式
• 若G是合式公式，x是个体变量，那么$(\forall x)G,(\exists x) G$也是合式公式
• 由上三步产生的表达式也是合式公式

自由变元和约束变元

字面意思 改名规则：

• 约束变元的改名规则：将量词中出现的变元以及该量词辖域中此变量的所有约束出现都用新的个体变元替换；新的变元一定要有别于改名辖域中的所有其它变量
• 自由变元的代入规则：将公式中出现该自由变元的每一处都用新的个体变元替换；新变元不允许在原公式中以任何约束形式出现

闭式

定义

设G是任意一个公式，若G中无自由出现的个体变元，则称G为封闭的合式公式，简称闭式

解释

谓词逻辑中公式G 的每一个解释I由如下四部分组成

1. 非空的个体域集合D
2. G中的每个常量符号，指定D中的某个特定的元素
3. G中的每个n元函数符号，指定$D^n$到D中的某个特定的函数
4. G中的每个n元谓词符号，指定$D^n$到{0，1}中的某个特定的谓词 换言之，解释其实就是寻找某个命题公式的为真/假时的内部元素真假的过程

谓词合式公式的分类

• 有效公式：公式G在所有的解释I下取值都为真
• 矛盾公式：公式G在所有的解释I下取值都为假
• 可满足公式：至少存在一种解释使得G取值为真

谓词逻辑的判定问题

可判定性

• 谓词逻辑是不可判定的
• 无函数符号的单子谓词逻辑片段可判定；不能仅凭“一元”就忽略语言中其他符号的影响
• 在固定且已知大小的有限论域上，可通过有限枚举检查；这不意味着一般的有限模型可满足性问题也可判定 定理：谓词逻辑的判定问题是不可解的 定义：公式G,H称为等价的，记为G=H，当且仅当$G \leftrightarrow H$是有效公式

代入实例

定义：对于某个命题公式$G(P_1,P_2,...,P_n)$，其中$P_1,P_2,...,P_n$是G中的命题变元，当我们使用任意的谓词公式$G_i(1 \leq i \leq n)$分别代入$P_i$后，得到的新谓词公式$G(G_1,G_2,...,G_n)$称为原公式的代入实例 定理：永真公式的额任意一个代入实例必为有效公式

相关有效公式

以下采用非空论域的经典一阶逻辑；移动量词时必须防止变量捕获。

• 约束变量可以改名，但新变量不能捕获原来自由出现的变量。
• $\neg\exists x\,G(x)\equiv\forall x\,\neg G(x)$。
• $\neg\forall x\,G(x)\equiv\exists x\,\neg G(x)$。
• $\forall x(G\land H)\equiv(\forall xG)\land(\forall xH)$。
• $\exists x(G\lor H)\equiv(\exists xG)\lor(\exists xH)$。
• 当 x 不在 S 中自由出现时，量词可按相应规则跨过与 S 的合取或析取。
• $(\exists xG(x))\land(\exists xH(x))\equiv\exists x\exists y(G(x)\land H(y))$，其中 y 为避免捕获而选取的新变量。

不能把量词与所有联结词随意交换。例如“每个人都喜欢某种食物”不等于“存在一种食物被所有人喜欢”。

范式

范式可以被看作是公示的一种标准形式，显然既然前文有涉及那么这里就同样会再次出现。其中，前束公式与原公式是等值的，而其他范式与原公式的关系并不强。

前束范式

定义：称公式G是一个前束范式，如果G中的一切量词都位于该公式的最前端且这些量词的辖域都延伸到公式的末端。标准形式如下：

其中$Q_i$为量词$\forall$或者$\exists$，M称作公式G的母式/基式，M中不存在量词 定理：谓词逻辑中的任一公式都可以转化为与之等价的前束范式，但其前束范式并不唯一

Skolem标准式

先将公式化为适当的前束形式，再用新常量或依赖前面全称变量的新函数项替换存在量词的变量。通常得到全称闭包的无存在量词形式；全称量词在约定下可省略书写。

Skolem 化一般保持可满足性，不保证在原语言中与原公式等价；不能解释为直接删除全部量词。

推理与证明技术

逻辑结果与命题蕴含

用 $\Gamma$ 表示前提集合。$\Gamma\models H$ 表示每个使全部前提成立的解释也使 H 成立；$G\to H$ 则是对象语言中的一个公式，两种记号不应混为一谈。

有限前提的命题推理有效，当且仅当 $(G_1\land\cdots\land G_n)\to H$ 是永真式。真值表检验只需寻找“前提全真而结论假”的反例行；存在这种行，推理就无效。

常用命题推理规则

演绎、条件证明与反证

演绎把前提、已知定理和合法规则组成有限推导序列。若在临时假设 P 下得到 S，则在解除这一假设后可推出 $P\to S$，还要遵守所用证明系统的作用域规则。

在经典逻辑中，证明 $\Gamma,\neg H$ 可推出矛盾，是证明 $\Gamma\models H$ 的常用方法。证明逆否命题和直接假设否定再推出矛盾，是有关联但不同的组织方式。

谓词逻辑的推理规则

• 全称实例化：由 $\forall xG(x)$ 得到 $G(t)$，前提是替换项 t 对 x 可自由代入，不能造成变量捕获。
• 存在引入：从某个具体实例 $G(t)$ 可推出 $\exists xG(x)$，仍需满足合法替换条件。
• 全称推广：只有对象是任取的，并且没有依赖某个特殊对象的未解除假设，才可由实例推广到全称命题。
• 存在消去：为存在命题引入新的临时见证，在不让该见证逃逸到最终结论或其他假设的条件下完成推导；不能把“有人满足”当作任意指定的人都满足。

一些有效关系

最后一个关系的逆向一般不成立：两个性质可能由不同的对象分别满足。

相关证明

数论中的证明

整除性质

命题：如果 a | b 并且 a | c, 那么 a | (b + c) 证明：假设 a | b 且 a | c ，则存在整数 s 和 t ，使得 b = as 和 c = at 。所以有 b + c = as + at = a(s + t) 。因此， a | (b + c) 。

除法算法

命题：若a是整数，b 是正整数，则存在唯一的整数 q 和 r，使得 0≤r<b， 并且 a=bq+r

存在性证明

若 a是整数，b 是正整数，则存在整数 q 和 r，使得 0≤r<b且 a=bq+r 证明：考虑集合 S = {a − bk | kε ℤ 且a − bk ≥ 0} ，以下分情况讨论：

1. 若0 ∈ S，则 b | a，从而可以令q = a/b且r = 0
2. 若0 ∉ S，我们首先证明S ≠ ∅，再分情况讨论
   1. 若a ≥ 0，则a − b * 0 ∈ S，也即S ≠ ∅
   2. 若a < 0，则a − b * a = a(1 − b) ∈ S 因此，当0 ∉ S时， S ≠ ∅。以下使用良序原理 根据良序原理，S 必然有一个最小元素，记为 r = a − bq 也即a = bq + r, r ≥ 0，接下来我们只需证明r < b 假设r ≥ b，则a − b q + 1 = a − bq − b = r − b ≥ 0，且 a − b q + 1 ∈ S，也即a − b q + 1 是比r更小的元素，与假设矛盾 因此， r < b

唯一性证明

若 a是整数，b 是正整数，则存在唯一的整数 q 和 r，使 0≤r<b且 a=bq+r 证明：假设存在两组，q 和 r，以及q‘ 和 r’ ，满足 a = bq + r a = bq’ + r‘ 则， bq + r = bq‘ + r’ 。不失一般性，假设r‘ ≥ r，则 b q − q’ = r‘ − r 因此，b|(r’ − r )。 又因为 0 ≤ r‘ − r ≤ r’ < b，必然有r‘ − r = 0 也即r‘ = r， q’ = q 证明完毕！

除数的唯一性

命题: 设 m 为正整数。当且仅当存在一个整数 k 使得a=b+km，整数 a 和 b 在模 m 意义下同余。 证明： （仅当）如果 a≡b (mod m)，则根据同余的定义，m 整 除 a−b。因此，存在一个整数 k，使得 a−b=km，即等 价于 a=b+km. （当）反过来，如果存在一个整数 k，使得 a=b+km， 那么 km=a−b。因此，m 整除 a−b，并且 a≡b (mod m).

同余式的加法和乘法运算

命题：:设 m 为正整数。如果 a≡b (mod m) 且 c≡d (mod m)，则a+c≡b+d (mod m) 且 ac≡bd (mod m) 证明：因为 a≡b (mod m) 且 c≡d (mod m)，则存在整数 s 和 t，分别使得 b=a+sm和 d=c+tm。 因此, b + d = (a + sm) + (c + tm) = (a + c) + m(s + t) b d = (a + sm) (c + tm) = ac + m(at + cs + stm). 因此, a + c ≡ b + d (mod m) and ac ≡ bd (mod m)

算数基本定理

每个大于 1 的整数都可写成素数乘积，除因子的排列顺序外唯一。

存在性可用最小反例法：若最小反例 a 不是素数，就能写为两个小于 a 且大于 1 的整数的乘积；两者都可分解，从而 a 也可分解，矛盾。

唯一性使用欧几里得引理：若素数 p 整除 ab，则 p 整除 a 或 b。若 p 不整除 a，就有 $\gcd(p,a)=1$，由贝祖等式 $up+va=1$ 两边乘 b 可知 p 整除 b。对多个因子重复使用该引理。

若一个整数有两种素因子分解，左侧任一素因子必整除右侧某个素因子，于是两者相等；约去这对因子并归纳，得到分解唯一。

最大公约数表示成一个线性组合

命题：若 a 和 b 是任意整数且不全为零，则 gcd(a, b)是集合{ax + by | x, y ∈ ℤ} 中的最小正整数元素. 证明：设 s是集合{ax+by :x, y∈ ℤ} 中的最小正整数元素。 设 q = a div s，r = a mod s；则 r = a - qs = a - q(ax+by) = a(1-qx) + b(-qy).因此 r 也是 a和b的线性组合。 由于0 ≤ r < s且s是集合{ax+by :x, y∈ ℤ} 中的最小正整数元素，因此r必然为0. 也即s|a。 同理，s|b。因此s是a和b的公约数，且gcd(a, b) ≥ s. 另一方面，由于s是a和b的线性组合， gcd (a, b) | s。因此gcd(a, b) ≤ s。 综上， gcd a, b = s，也即gcd a, b 是集合{ax+by |x, y∈ ℤ} 中的最小正整数元素

试除法

若合数 $a=bc$，其中 $1<b,c<a$，则 b、c 至少有一个不超过 $\sqrt a$；否则两者乘积会大于 a。再取这个因子的素因子，即得到 a 的一个不超过 $\sqrt a$ 的素因子。

无穷素数

假设所有素数只有 $p_1,\ldots,p_n$，取 $q=p_1\cdots p_n+1>1$。q 至少有一个素因子 t，而每个 $p_i$ 除 q 都余 1，因此 t 不在原列表中，矛盾。这里不必预先断言 q 一定是合数。

欧几里得算法

若 $a=bq+r$，a、b 的公约数恰好也是 b、r 的公约数，因此 $\gcd(a,b)=\gcd(b,r)$。

令 $r_0=a,r_1=b$，反复带余除法，直到 $r_{k+1}=0$ 而 $r_k>0$。非负余数严格递减，故必终止。逐次使用引理：

所以答案是最后一个非零余数，不能把已经等于零的余数记为最大公约数。

同余式除法

命题：设 m 为正整数，a、b 和c为整数. 若 ac ≡bc (mod m) 且 gcd(c, m) = 1, 则a ≡ b (mod m). 证明： 因为 ac ≡ bc (mod m), 则 m | (ac − bc) = c(a − b) 。 由于 gcd(c, m) = 1, 所以m|(a − b). 因此, a ≡ b (mod m)

唯一逆元

设 $m>1$ 且 $\gcd(a,m)=1$。贝祖定理给出 $sa+tm=1$，所以 $sa\equiv1\pmod m$，逆元存在。

若 $ua\equiv va\equiv1\pmod m$，则 $m\mid a(u-v)$。由 $\gcd(a,m)=1$ 可消去 a，得到 $m\mid(u-v)$，即 $u\equiv v\pmod m$。这是模 m 意义下唯一，不是整数代表只能有一个。

中国剩余定理

设各模数 $m_i>1$ 两两互素，$M=\prod_i m_i$，$M_i=M/m_i$，取 $y_iM_i\equiv1\pmod{m_i}$。

构造 $x=\sum_i a_iM_iy_i$。对固定 j，i≠j 的项被 $m_j$ 整除，而第 j 项模 $m_j$ 等于 $a_j$，所以 x 满足全部同余条件。

若 x、z 都是解，则每个 $m_i$ 都整除 x−z。利用两两互素可得 $M\mid(x-z)$，故解模 M 唯一。

Wilson定理

命题：对于整数 p>1，p 是素数当且仅当$(p-1)! \equiv -1 \pmod p$ 证明： 充分性：考虑p的真因子n，也即n|p且$1 \leq n < p$。 因此，n|(p-1)! 另一方面，由于$(p-1)! \equiv -1 \pmod p$，因此p|((p-1)! + 1)。 又因为n|p，所以n|((p-1)! + 1)。 综上所述，n|1也即n=1。 p的真因子只有1，那么p是素数。 引理：若p为素数且$x^2 \equiv 1 \pmod p$，那么$x \equiv 1 \pmod p$或者$x \equiv {-1} \pmod p$ 引理证明：$p|(x^2-1)$即p|(x+1)(x-1)。由于p是素数，那么p|(x+1)或者p|(x-1)，得证。 涉及定理：逆元唯一性 必要性：p=2或3时易证，以下考虑$p \geq 5$ 考虑集合{2,3,…,p-2}，对于其中任何一个元素a，可知$a \not\equiv 1 \pmod p$且$a \not\equiv -1 \pmod p$。根据上述引理，可知$a^2 \not\equiv 1 \pmod p$。又因为a与p互素，那么a必然存在一个模p下的逆元，且该逆元不为a本身。因此，集合{2,3,…,p-2}中可以两两配对为互为逆元的对，从而$(p-1)! = 1 \cdot (p-1) \cdot (2 \cdot 3...(p-2)) \equiv p-1 \equiv -1\pmod p$，得证

欧拉定理

设 $n>1$，$\gcd(a,n)=1$，取模 n 的一组简化剩余系 $R=\{r_1,\ldots,r_{\phi(n)}\}$。乘以 a 是这个集合上的置换：若 $ar_i\equiv ar_j\pmod n$，消去 a 得 $r_i\equiv r_j\pmod n$。

因此

每个 $r_i$ 均可逆，消去乘积，得到 $a^{\phi(n)}\equiv1\pmod n$。对于非负整数指数，再作带余除法即可得到指数按 $\phi(n)$ 约简的推论。

RSA正确性证明

取不同素数 p、q，$n=pq$，并令 $ed=1+k(p-1)(q-1)$。对任意 $0\le m<n$，分别考察模 p 和模 q。

模 p 时，若 $p\mid m$，则 $m^{ed}\equiv m\equiv0$；否则由费马小定理，$m^{p-1}\equiv1\pmod p$，所以 $m^{ed}\equiv m\pmod p$。模 q 同理。

由中国剩余定理，$m^{ed}\equiv m\pmod{pq}$。这样同时覆盖了 m 与 n 互素和不互素的情形。

计数中的证明

鸽巢原理相关

鸽巢原理： 命题：若 k 是一个正整数，将 k+1 个物体放入 k 个盒子中，则至少有一个盒子包含两个或更多的物体. 证明：我们使用反证法进行证明。假设没有一个盒子里有超过一个物体，那么所有盒子里的物体总数最多为 k。但这与我们有 k+1 个物体的假设相矛盾。因此，至少有一个盒子必须包含两个或更多的物体. 推论： 命题：从一个具有 k+1 个元素的集合到一个具有 k 个元素的集合的函数 f 不可能是单射。 证明：使用鸽巢原理. • 为 f 的值域中的每个元素 y 创建一个盒子. • 将所有使得 f(x)=y的定义域中的元素 x 放入对应的盒子中. • 因为定义域中有 k+1 个元素，而值域中只有 k 个盒子，所以至少有一个盒子里会有两个或更多的元素. 因此，函数 f 不能是一一对应的. 广义鸽巢原理： 命题：如果将 N 个物体放入 k 个盒子中，则至少 有一个盒子包含至少 $\lceil \frac{N}{k} \rceil$ 个物体 证明：我们使用反证法进行证明.假设没有任何一个盒子包含超过 ⌈N/k⌉−1个物体。这样，每个盒子最多有 ⌈N/k⌉−1个物体。由于有 k 个盒子，因此总的物体数量至多为 $k(\lceil \frac{N}{k} \rceil-1) < k((\frac{N}{k}+1)-1) = N$ 这与我们有 N 个物体的事实矛盾.

参考与整理范围

本文按主题合并数论与密码学、计数、数理逻辑及相关证明过程。高级计数原稿仅有提纲，已明确标注；证明中的符号、条件和已发现的错误已作整理，课程中的密码模型与实际协议用途也作了区分。

• MIT：Mathematics for Computer Science
• MIT：鸽巢原理与计数
• RFC 8017：RSA 加密与签名方案