在计算机科学与数学领域，严谨的逻辑推理是构建一切理论的基石。CS70作为离散数学与概率论的入门课程，其核心便是教会我们如何确立命题的真伪。本文将记录初学者如何在这一过程中，掌握命题逻辑、经典证明方法以及强大的数学归纳法。

---

证明方法的基石

确立一个普遍性命题（例如“对所有x，如果p(x)成立，那么q(x)也成立”）的真实性，不能仅仅依靠列举有限的例子，而需要依赖一套通用且可靠的证明体系。

一、命题与逻辑：证明的基础

理解命题是所有逻辑推理的起点。一个命题是一个可以判断真假的陈述句，其真值非真即假，不存在模糊的中间状态。这正是**排中律（Law of Excluded Middle）**的核心思想。

1.1 命题的形式与逻辑联结词

• 原子命题（Atomic Proposition）：最简单的命题，无法再分解。例如：“2>1”。

• 复合命题（Compound Proposition）：由原子命题通过**逻辑联结词（Logical Connectives）**组合而成。这些联结词定义了命题间的逻辑关系：

  • 否定 (¬)：非 p (not p)

  • 合取 (∧)：p 且 q (p AND q)

  • 析取 (∨)：p 或 q (p OR q)

  • 蕴含 (→)**：如果 p 那么 q (if p THEN q)

  • 等价 (↔)**：p 当且仅当 q (p IF AND ONLY IF q)

说明：逻辑联结词具有明确的优先级：圆括号 () > 非 (¬) > 合取 (∧) > 析取 (∨) > 蕴含 (→) > 等价 (↔)。

通过命题变元（Propositional Variable）和联结词，我们可以形成合式公式（Well-formed Formula）。根据其在各种赋值下的真值表现，合式公式可被分类：

• **重言式（Tautology）或永真式：在所有赋值下均为真。
• **矛盾式（Contradiction）或永假式：在所有赋值下均为假。
• **可满足式（Satisfiable）：至少在一种赋值下为真。

1.2 确立真命题的基本证明方法

当面对形如 ∀x,P(x)→Q(x) 的普遍性陈述时，通常采用以下几种证明方法。

• 直接证明（Direct Proof） 这是最直观的证明策略。为证明 p 蕴含 q，我们从假设 p 为真出发，通过一系列逻辑推导和已知事实，直接导出 q 为真。此方法具备传递性：若 p 蕴含 q 且 q 蕴含 r，则 p 蕴含 r。

• 间接证明（Indirect Proof / Proof by Contrapositive） 当直接证明复杂时，可利用逻辑等价关系：p 蕴含 q 等价于其逆否命题 非 q 蕴含 非 p (p→q≡¬q→¬p)。通过证明逆否命题的真伪来间接证明原命题。

• 反证法（Proof by Contradiction） 反证法是一种强大的技巧。其核心在于：为证明命题 p 为真，我们首先假设 p 为假（即 非 p 成立）。若从此假设出发，最终推导出一个矛盾（Contradiction），则表明最初的假设 非 p 是错误的，从而证明了 p 必然为真。

  经典案例：证明存在无限个质数 假设质数是有限的，可列举为 p1​,p2​,…,pn​。构造新数 N=(p1​×p2​×⋯×pn​)+1。 根据算术基本定理，N要么是质数，要么可被某质数整除。

  • 若N是质数，它不在有限列表内，与假设矛盾。
  • 若N是合数，它能被某个 pi​ 整除。但 N 除以任何 pi​ 都余1，无法被整除，这同样与假设矛盾。 无论哪种情况都导致矛盾，因此最初假设“质数是有限的”是错误的，从而证明了质数是无限的。

1.3 公理 (Axiom)

在数学体系中，公理（Axiom）是被我们无需质疑而直接接受为真的陈述。它们是构建整个理论大厦的基石，不需通过其他命题来证明。例如，欧几里得几何中的“两点之间只有一条直线”即为公理。公理的存在，使得我们能够从确定的起点出发，通过逻辑推理构建更复杂的知识体系。

---

二、无限的跳跃：数学归纳法

**数学归纳法（Mathematical Induction）是离散数学中一种优雅而强大的证明技术，尤其适用于证明关于所有自然数（或从某个起始点开始的整数）都成立的命题。其核心思想类似于推倒多米诺骨牌：

1. 基础步骤：推倒第一块骨牌。
2. 归纳步骤：确保每一块骨牌倒下时，都能推倒紧接着的下一块骨牌。 若满足这两点，则所有骨牌都将倒下。

2.1 数学归纳法的标准流程

为证明关于自然数 n 的叙述 P(n) 对所有 n≥n0​（通常 n0​=0 或 n0​=1）都成立，遵循以下步骤：

1. 基础步骤（Base Case）：验证 P(n0​) 成立。
2. 归纳假设（Inductive Hypothesis）：假设对于某个任意但固定的 k≥n0​，叙述 P(k) 成立。
3. 归纳步骤（Inductive Step）：在 P(k) 成立的假设下，证明 P(k+1) 也成立。

说明：若归纳步骤成功，则根据数学归纳法原理，叙述 P(n) 对所有 n≥n0​ 都成立。

经典案例：证明 1+2+⋯+n=2n(n+1)​ 对所有正整数 n 成立。

• 基础步骤 (n0​=1)：当 n=1 时，左边 = 1，右边 = 21(1+1)​=1。等式成立。
• 归纳假设：假设对于某个 k≥1，等式 1+2+⋯+k=2k(k+1)​ 成立。
• 归纳步骤：目标是证明 1+2+⋯+k+(k+1)=2(k+1)((k+1)+1)​。 左边 = (1+2+⋯+k)+(k+1) 根据归纳假设 = 2k(k+1)​+(k+1) 提取公因子 (k+1) = (k+1)(2k​+1)=(k+1)(2k+2​)=2(k+1)(k+2)​。 这正是 P(k+1) 的形式。因此，原命题得证。

2.2 归纳法的正确性：良序原理

数学归纳法的有效性源于其与**良序原理（Well-Ordering Principle）**的等价性。良序原理指出：任何非空的自然数集都必然有一个最小元素。

若 P(n) 不对所有 n≥n0​ 成立，则存在一个使 P(n) 不成立的最小元素 m≥n0​。然而：

• m 不可能是 n0​，因 P(n0​) 在基础步骤中已证明成立。
• 若 m>n0​，则 P(m−1) 必成立。但归纳步骤表明，若 P(m−1) 成立，则 P(m) 也应成立。 这导致了矛盾，说明不存在这样的最小反例，故 P(n) 必然对所有 n≥n0​ 成立。

2.3 归纳与递归的紧密关联

在计算机科学中，归纳证明与**递归定义（Recursive Definition）**的概念紧密相连。许多递归算法或数据结构（如树、链表）的性质都可以通过归纳法来证明其正确性。

案例：证明高度为 h 的完全二叉树有 2h+1−1 个节点（定义空树高度为-1）。

• 基础步骤 (h=0)：高度为0的树（仅含根节点），节点数 1=20+1−1，成立。
• 归纳假设：假设所有高度为 k 的完全二叉树有 2k+1−1 个节点。
• 归纳步骤：考虑一棵高度为 k+1 的完全二叉树。它由一个根节点和两棵高度为 k 的完全二叉子树组成。 总节点数 = 1 (根) + 2× (高度为 k 的子树节点数) = 1+2×(2k+1−1) (根据归纳假设) = 1+2k+2−2 = 2k+2−1。 这正是高度为 k+1 时所需证明的表达式。因此得证。

---

三、归纳法的进阶应用

除了标准数学归纳法，更强大的变体能处理更复杂的证明场景。

3.1 强归纳法（Strong Induction / Complete Induction）

强归纳法与普通归纳法的核心区别在于其归纳假设更“强”：

• 普通归纳：假设 P(k) 成立，证明 P(k+1)。
• 强归纳：假设所有小于 k+1 的命题 P(n)（即 P(n0​),P(n0​+1),…,P(k)）都成立，在此基础上证明 P(k+1) 成立。

适用场景：当 P(k+1) 的证明不仅依赖于紧邻的前一项 P(k)，而是依赖于多个或所有之前项时（如斐波那契数列的性质证明），强归纳法尤为适用。

案例：证明任何正整数 n≥2 都可以分解为质数的乘积。（算术基本定理的归纳证明）

• 基础步骤 (n0​=2)：当 n=2 时，2是质数，成立。

• 归纳假设：假设对于所有 m，其中 2≤m≤k，都满足 m 可以分解为质数的乘积。

• 归纳步骤：考虑 k+1。

  • 若 k+1 是质数，则得证。
  • 若 k+1 是合数，则可分解为 k+1=a×b，其中 2≤a<k+1 且 2≤b<k+1。根据归纳假设（因 a,b 都小于 k+1），a 和 b 均可分解为质数乘积。因此，k+1 亦可分解为这些质数的乘积。得证。

3.2 双重归纳（Double Induction）

当命题涉及到两个或更多个变量时（例如 P(m,n)），我们需要使用双重归纳，这可以类比为在二维网格上进行推导。

双重归纳的核心步骤： 假设目标是证明：对于所有 m≥m0​ 和 n≥n0​，命题 P(m,n) 成立。

1. 基础步骤（Base Cases）

   • 步骤一：证明在基本点 (m0​,n0​)，P(m0​,n0​) 成立。
   • 步骤二：证明在 m=m0​ 且所有 n≥n0​ 时，P(m0​,n) 成立。这通常通过对 n 进行标准归纳来完成。
   • 步骤三（可选但常见）：证明在 n=n0​ 且所有 m≥m0​ 时，P(m,n0​) 成立。这通常通过对 m 进行标准归纳来完成。

2. 归纳步骤（Inductive Step） 为证明 P(m,n) 成立，假设对于所有 m′≤m,n′≤n 但并非 (m,n) 自身的情况，命题 P(m′,n′) 均成立（或至少 P(m−1,n) 和 P(m,n−1) 成立）。 这通常意味着需要从“左边”或“上边”的已验证点推导当前点。常见的策略是：

   • 假设 P(m−1,n) 成立（沿 m 轴方向的归纳），且
   • 假设 P(m,n−1) 成立（沿 n 轴方向的归纳），
   • 在此基础上推导出 P(m,n) 也成立。

说明：双重归纳确保你可以从已知的点扩展到二维网格上的下一个点，从而覆盖所有情况。一个典型的例子可能是证明某种二维排列或矩阵性质。

---

四、经典算法与离散数学应用：稳定婚姻问题

离散数学的理论不仅停留在抽象层面，它与实际世界的算法设计和问题解决紧密相连。稳定婚姻问题（Stable Marriage Problem）就是一个绝佳的例子，它旨在为两组数量相等的个体（如男性和女性）进行配对，以消除“不稳定对”——即两人都更倾向于彼此而非自己的当前伴侣。Gale-Shapley算法**是解决此问题的经典方法。

4.1 算法基本原理

1. 输入：两组数量相等的个体（如 n 男 n 女），每人持有一份对异性成员的偏好排序列表。
2. 目标：找到一个稳定匹配，即不存在任何一对未匹配的男女，他们都比现有伴侣更偏好对方。
3. 策略：算法采用“男性主动求婚，女性被动选择”的迭代过程，逐步形成稳定匹配。

4.2 算法步骤

1. 初始化：
   • 所有男性和女性初始状态均为单身。
   • 每个男性维护一个尚未向其求婚过的女性偏好列表。
2. 迭代过程：
   • 男性行动：每个单身男性向其偏好列表中尚未求婚的最高位女性发出求婚。
   • 女性决策：女性在收到求婚后，会比较当前伴侣（若已订婚）与新求婚者：
     • 若更喜欢新求婚者，则会拒绝当前伴侣，并与新求婚者订婚。
     • 否则，拒绝新求婚者，维持当前关系。
3. 终止条件：当所有男性均已成功订婚时，算法终止。

4.3 关键性质与证明

Gale-Shapley算法的有效性基于其几个关键性质：

1. 终止性：算法保证在有限步内终止。每个男性最多向每位女性求婚一次，因此求婚次数最多为 O(n2)。
2. 稳定性：算法的最终匹配必然是稳定的。
   • 证明思路：采用反证法。假设最终匹配存在不稳定对（男A和女B彼此更偏好对方而非当前伴侣）。
   • 若男A更偏好女B（而非他最终匹配的伴侣），那么男A一定在某个时刻向女B求婚过。
   • 此时，若女B接受了男A，则他们会配对。若女B拒绝了男A，则说明她当时已经有了一个比男A更优的伴侣，或者后来遇到了更优的伴侣。在此之后，女B的伴侣只会变得更好或保持不变。
   • 这意味着，男A不可能在最终匹配中与女B构成不稳定对（因为女B不可能最终与一个比男A差的人配对，同时男A又更偏好女B），这与假设矛盾。因此，最终匹配必然稳定。
3. 最优性：
   • 男性最优（Male-Optimal）：算法产生的稳定匹配对所有男性而言是最优的。这意味着在所有可能的稳定匹配中，每个男性都得到了他在任何稳定匹配中能得到的最好伴侣。
   • 女性最劣（Female-Pessimal）：相应地，算法产生的稳定匹配对所有女性而言是最劣的。在所有可能的稳定匹配中，每个女性都得到了她在任何稳定匹配中能得到的最差伴侣。

4.4 复杂度分析

• 时间复杂度：O(n2)。这是因为在最坏情况下，每个男性可能需要向 n 位女性求婚，而每位女性可能被拒绝 n 次。
• 空间复杂度：O(n2)。主要用于存储每个个体（n 男 n 女）的偏好列表。

4.5 示例与流程演示

假设两男两女：

• 男性偏好：
  • 男1: [女2, 女1]
  • 男2: [女1, 女2]
• 女性偏好：
  • 女1: [男1, 男2]
  • 女2: [男1, 男2]

流程：

1. 第一轮：
   • 男1向女2求婚。女2目前单身，接受男1。配对: (男1, 女2)。
   • 男2向女1求婚。女1目前单身，接受男2。配对: (男2, 女1)。
2. 检查终止条件：所有男性均已订婚。算法结束。

最终稳定匹配：(男1, 女2), (男2, 女1)。
让我们通过一个稍微复杂点的例子来演示流程

• 男性偏好：
  • 男1: [女1, 女2]
  • 男2: [女1, 女2]
• 女性偏好：
  • 女1: [男2, 男1]
  • 女2: [男1, 男2]

流程

1. 第一轮：
   • 男1向女1求婚。女1目前单身，接受男1。配对: (男1, 女1)。
   • 男2向女1求婚。女1收到男2求婚，比较男1和男2。女1偏好男2 ([男2, 男1])，因此拒绝男1，接受男2。配对: (男2, 女1)。男1恢复单身。
2. 第二轮：
   • 男1（单身）向其偏好列表中的下一位（女2）求婚。女2目前单身，接受男1。配对: (男1, 女2)。
3. 检查终止条件：所有男性均已订婚。算法结束。

最终稳定匹配：(男1, 女2), (男2, 女1)。

4.6 应用场景

Gale-Shapley算法及其变体在实际中有着广泛的应用：

• 大学招生：匹配学生与大学，考虑到双方的偏好。
• 医院实习分配：医学生与医院的匹配，确保稳定且公平。
• 公共资源分配：如将有限的网络服务器与用户的请求进行优化匹配，以达到最大化效率和满意度。

---

总结

本次CS70的学习实践，让我系统性地理解了命题证明的各个层面。从基本的直接证明、间接证明、反证法，到处理无限情况的数学归纳法及其变体（强归纳法和双重归纳），这些工具共同构成了我们验证和理解复杂数学及计算机科学概念的逻辑框架。

此外，通过对稳定婚姻问题及Gale-Shapley算法的探讨，我们看到了离散数学理论如何在实际问题中发挥作用，为复杂匹配问题提供了稳定且高效的解决方案。

尤其值得注意的是，任何证明过程中的一个细微错误都可能导致整个证明链条的断裂。这种对精确性与严谨性的追求，是CS领域学习者不可或缺的核心素养。