离散数学 1 第 2 章：命题等价与推理——范式与形式证明

写于 2026-11-01

这一章的考点密度是全课最高的：等值演算、范式、主范式、推理证明四块内容在考试里几乎必然同时出现。它的难点不在概念，而在没有一套统一的机械流程——同一个公式可以用十几条定律绕出结果，也可以画 8 行真值表直接读出答案。学完这一章要获得的判断力是：看到公式先估计规模，决定是"演算"还是"画表"，以及知道主范式的编号是怎么来的、为什么能唯一确定一个公式。

一、等值式：⇔ 不是联结词

设 A、B 是命题公式，若 A↔B 是重言式，称 A 与 B 等值，记作 A⇔B。注意区分两个层次：↔ 是公式内部的联结词，A↔B 仍是一个公式；⇔ 是元语言符号，说的是"A↔B 这个公式恒真"这一判断，它本身不能出现在公式里参与运算。

等值关系的三条性质使得演算可以逐步替换：自反、对称、传递。再加上一条替换规则——若 A⇔B，则任何含 A 的公式 C 中把 A 的某处出现换成 B，所得公式与 C 等值。

二、基本等价定律

类别	定律
双重否定	¬¬A ⇔ A
幂等律	A∨A ⇔ A，A∧A ⇔ A
交换律	A∨B ⇔ B∨A，A∧B ⇔ B∧A
结合律	(A∨B)∨C ⇔ A∨(B∨C)，(A∧B)∧C ⇔ A∧(B∧C)
分配律	A∨(B∧C) ⇔ (A∨B)∧(A∨C)；A∧(B∨C) ⇔ (A∧B)∨(A∧C)
德摩根律	¬(A∨B) ⇔ ¬A∧¬B；¬(A∧B) ⇔ ¬A∨¬B
吸收律	A∨(A∧B) ⇔ A；A∧(A∨B) ⇔ A
同一律	A∨0 ⇔ A，A∧1 ⇔ A
零律	A∨1 ⇔ 1，A∧0 ⇔ 0
排中律 / 矛盾律	A∨¬A ⇔ 1，A∧¬A ⇔ 0
蕴涵等值式	A→B ⇔ ¬A∨B
假言易位	A→B ⇔ ¬B→¬A
等价等值式	A↔B ⇔ (A→B)∧(B→A)
输出律	(A∧B)→C ⇔ A→(B→C)
归谬论	(A→B)∧(A→¬B) ⇔ ¬A

演算的实际套路只有三步：先用蕴涵等值式和等价等值式把 →、↔ 全部消掉；再用德摩根律和双重否定把 ¬ 压到变元上；最后用分配律、吸收律、同一律化简。 90% 的等值证明题走这条路都能通。

三、重言式、矛盾式与可满足式

三者的关系可以用一句话概括：A 是重言式当且仅当 ¬A 是矛盾式；A 可满足当且仅当 ¬A 不是重言式。判定方法有四种：真值表（2ⁿ 行，最稳但最慢）、等值演算（把公式化简成 1 或 0）、主析取范式（看是否含全部极小项）、主合取范式（看是否含全部极大项）。

四、析取范式与合取范式

析取范式是若干个合取式的析取，形如 (…∧…)∨(…∧…)；合取范式是若干个析取式的合取。它们只要求"顶层是 ∨ 或 ∧、每层内部是另一种"，对每个合取/析取支里出现哪些变元不作要求，因此不唯一。

求析取范式的流程：消去 → 与 ↔ → 否定内移 → 用 ∧ 对 ∨ 的分配律展开。求合取范式则最后一步换成用 ∨ 对 ∧ 的分配律。范式的价值在于把公式变成"标准形状"，方便判断可满足性：析取范式里只要有一个合取支不含互补对（如 p∧¬p），整体就可满足。

五、主析取范式与主合取范式

主范式在范式的基础上加了一条硬约束：每个支里，每个命题变元必须恰好出现一次（以本身或否定的形式）。这条约束让结果唯一。

极小项 mᵢ：n 个文字的合取，每个变元恰出现一次。编号规则是——按变元的固定顺序（如 p, q, r）取一个赋值，该赋值为 1 的变元写本身，为 0 的写否定，把 1/0 序列当二进制数转成十进制，就是下标。以 n=2 为例：

极小项	成真赋值	编号	极大项	成假赋值	编号
¬p∧¬q	00	m₀	p∨q	00	M₀
¬p∧q	01	m₁	p∨¬q	01	M₁
p∧¬q	10	m₂	¬p∨q	10	M₂
p∧q	11	m₃	¬p∨¬q	11	M₃

极大项 Mᵢ 是 n 个文字的析取，编号规则正好相反：赋值为 0 的变元写本身，为 1 的写否定，使该极大项在赋值为 i 时为假。两者的对偶关系是 ¬mᵢ ⇔ Mᵢ、mᵢ ⇔ ¬Mᵢ。

由此得到两条最有用的结论：主析取范式 = 所有成真赋值对应的极小项之析取（记 Σm(…)），主合取范式 = 所有成假赋值对应的极大项之合取（记 ΠM(…)）。同一公式的 Σ 下标集合与 Π 下标集合恰好互补，因为成真赋值与成假赋值合起来是全部 2ⁿ 种。

求法有两种。真值表法：画表，取值为 1 的行写极小项。等值演算法：先化成析取范式，再对缺变元的支用 A ⇔ A∧(B∨¬B) 补齐后展开合并。

例：求 (p→q)∧r 的主析取范式。

消去蕴涵：(¬p∨q)∧r
分配：⇔ (¬p∧r)∨(q∧r)
补变元：¬p∧r ⇔ ¬p∧(q∨¬q)∧r ⇔ (¬p∧q∧r)∨(¬p∧¬q∧r)，即 m₃∨m₁
第二支：q∧r ⇔ (p∨¬p)∧q∧r ⇔ (p∧q∧r)∨(¬p∧q∧r)，即 m₇∨m₃
合并去重：Σm(1,3,7)

于是主合取范式直接写出：ΠM(0,2,4,5,6)。这一步不用再算，用互补关系抄即可，是省时间的关键。

六、命题逻辑的推理理论

推理形式"由前提 A₁,…,A_k 推出结论 B"是有效的，当且仅当蕴含式 A₁∧…∧A_k → B 是重言式。注意"有效"说的是形式，与前提实际真假无关。

判定有效的三条路：真值表（检查有没有"前提全真、结论假"的行）、等值演算（把蕴含式化简为 1）、主析取范式（看蕴含式是否含全部极小项）。

形式证明则用三条规则推：

P 规则：前提随时可引入。
T 规则：由已得结论经等值式或蕴涵式推出新行，要注明用了哪几行。
CP 规则（附加前提）：要证 A→B，把 A 也当前提，推出 B 即可。
归谬法（反证）：把 ¬B 加入前提，推出 r∧¬r。

例：前提 p→q、q→r、p，证 r。

1. p            P
2. p→q          P
3. q            T, 1,2 假言推理
4. q→r          P
5. r            T, 3,4 假言推理

CP 规则的价值在结论本身是蕴含式时最明显：要证 (p∧q)→r，就把 p∧q 当作附加前提加进去，推出 r，最后一步用 CP 收口，结论还原成蕴含式。归谬法则适合结论是否定式、或前提里带"或"的情况——把结论的否定加进前提，往 r∧¬r 上撞，撞到了就说明原推理有效。

主范式的唯一性还有一个副产品：两个公式等值，当且仅当它们的主析取范式相同（极小项集合一致）。这把"等值"这种语义判断降成了"标准形比对"，也是机器定理证明里归结原理的起点。

易错点

极小项"1 写本身、0 写否定"，极大项正好相反。两者记混，整道范式题全错。
主析取范式与主合取范式的下标集合互补，不是相同。
析取范式里的合取支可以缺变元，主析取范式不行——缺了就补，用 A∧(B∨¬B)。
用 CP 规则时，最终结论必须还原成蕴含式 A→B；直接写 B 是丢分点。
归谬法推出的矛盾必须是同一公式及其否定，推出两个无关的假命题不算。

这一章在整门课里的位置

本章完全建立在第 1 章的真值表之上，没有新的联结词，只有新的组织方式。第 3、4 章的谓词逻辑会把这里的每一条定律" lifting "一遍（量词版德摩根、量词版分配律），而第 5 章集合恒等式几乎是本章定律表的逐条翻译，所以这一章练熟，后面两章能省一半力气。

本文是《离散数学 1：数理逻辑与集合论》第 2 章的知识点摘要。完整板书与例题见课程页；上一章命题联结词，下一章谓词概念。