命题逻辑：主范式与推理演算

本节导读

这一节讲命题逻辑单元的后三条：范式与主范式、推理规则与推理演算（含归结推理）、公理系统的概念。主范式是判断公式类型、判断两个公式是否等值的「标准答案」；推理演算则是证明推导题的主体——给出前提和结论，要求一步一步写出推理过程。

学完你应该能用真值表或等值演算求出一个公式的主析取范式和主合取范式，能按「编号—公式—依据」的格式写出构造性证明，并能用归结法完成同样的证明。

析取范式与合取范式

命题变元或它的否定叫文字。几个文字的析取叫简单析取式，几个文字的合取叫简单合取式。由简单合取式组成的析取式叫析取范式，由简单析取式组成的合取式叫合取范式。任何公式都有与它等值的析取范式和合取范式，但写法不唯一。

求范式分三步：一，用蕴涵等值式、等价等值式消去 $\to$→ 和 $\leftrightarrow$↔；二，用德摩根律和双重否定律把否定号移到变元前；三，用分配律展开——要析取范式就把 $\land$∧ 分配到 $\lor$∨ 上，要合取范式就把 $\lor$∨ 分配到 $\land$∧ 上。

极小项、极大项与主范式

在含 n 个变元的简单合取式里，如果每个变元或它的否定恰好出现一次，就叫极小项；简单析取式里每个变元恰好出现一次，就叫极大项。n 个变元各有 $2^n$2n 个极小项和极大项，按下标编码：极小项 $m_i$mi​ 只在二进制为 i 的那组赋值下为真，变元取 1 的写原形、取 0 的写否定；极大项 $M_i$Mi​ 只在那组赋值下为假，变元取 0 的写原形、取 1 的写否定。两个变元时：

赋值（p q）	极小项	极大项
0 0	$m_0 = \neg p \land \neg q$m0​=¬p∧¬q	$M_0 = p \lor q$M0​=p∨q
0 1	$m_1 = \neg p \land q$m1​=¬p∧q	$M_1 = p \lor \neg q$M1​=p∨¬q
1 0	$m_2 = p \land \neg q$m2​=p∧¬q	$M_2 = \neg p \lor q$M2​=¬p∨q
1 1	$m_3 = p \land q$m3​=p∧q	$M_3 = \neg p \lor \neg q$M3​=¬p∨¬q

全由极小项组成的析取范式叫主析取范式，它就是公式所有成真赋值对应的极小项之析取；全由极大项组成的合取范式叫主合取范式，它是所有成假赋值对应的极大项之合取。所以同一个公式的两种主范式，下标正好互补；而且 $\neg m_i \Leftrightarrow M_i$¬mi​⇔Mi​。主范式是唯一的，这正是它有用的地方：

• 公式是重言式，当且仅当主析取范式含全部 $2^n$2n 个极小项（主合取范式不含极大项，记为 1）；
• 公式是矛盾式，当且仅当主析取范式不含极小项（记为 0）；
• 两个公式等值，当且仅当它们的主范式相同。

求法有两种。真值表法：列表找出成真、成假赋值，直接写出下标。例如 $(p \lor q) \to r$(p∨q)→r 只在 p∨q 为 1 而 r 为 0 时为假，成假赋值是 010、100、110，所以主合取范式是 $M_2 \land M_4 \land M_6$M2​∧M4​∧M6​，主析取范式是 $m_0 \lor m_1 \lor m_3 \lor m_5 \lor m_7$m0​∨m1​∨m3​∨m5​∨m7​。等值演算法：先化成析取范式，某个合取式缺变元 q 时，乘上 $(q \lor \neg q)$(q∨¬q) 再展开，最后合并相同的项；求主合取范式时缺变元就析取上 $(q \land \neg q)$(q∧¬q)。

推理规则

从前提 $A_1, A_2, \ldots, A_k$A1​,A2​,…,Ak​ 推出结论 B 的推理正确，当且仅当 $(A_1 \land A_2 \land \cdots \land A_k) \to B$(A1​∧A2​∧⋯∧Ak​)→B 是重言式，记作 $A_1, \ldots, A_k \Rightarrow B$A1​,…,Ak​⇒B。判断的办法有真值表法、主范式法和构造证明法，考试的证明推导题一般要求最后一种。构造证明用到的推理定律如下：

名称	形式
附加	$A \Rightarrow A \lor B$A⇒A∨B
化简	$A \land B \Rightarrow A$A∧B⇒A
假言推理（分离规则）	$A \to B, A \Rightarrow B$A→B,A⇒B
拒取式	$A \to B, \neg B \Rightarrow \neg A$A→B,¬B⇒¬A
析取三段论	$A \lor B, \neg B \Rightarrow A$A∨B,¬B⇒A
假言三段论	$A \to B, B \to C \Rightarrow A \to C$A→B,B→C⇒A→C
构造性二难	$A \to B, C \to D, A \lor C \Rightarrow B \lor D$A→B,C→D,A∨C⇒B∨D
合取引入	$A, B \Rightarrow A \land B$A,B⇒A∧B

另外还有三条结构性的规则：前提引入（任何时候都可以写下一个前提）、结论引入（已推出的公式可以作为后面的依据）、置换（任何一步都可以换成与它等值的公式，依据写所用的等值式）。

三种证明方法

直接证明：从前提出发，一行一行推出结论，每行写「编号、公式、依据」。

附加前提证明法：结论是 $C \to B$C→B 的形式时，可以把 C 当作附加前提，改为证明 B。依据是输出律：$(A \land C) \to B \Leftrightarrow A \to (C \to B)$(A∧C)→B⇔A→(C→B)。结论是蕴涵式时，先想这种方法。

归谬法（反证法）：把结论的否定 $\neg B$¬B 加入前提，推出一个矛盾 $R \land \neg R$R∧¬R，就证明了原推理。结论是单个文字、正面推不出来时，可以试归谬。

归结推理

归结规则只有一条：两个子句里有一对互补文字 L 和 $\neg L$¬L，就可以把它们消去，剩下的部分析取起来，得到的新子句叫归结式。比如 $p \lor q$p∨q 与 $\neg p \lor r$¬p∨r 归结得 $q \lor r$q∨r。

用归结法证明 $A_1, \ldots, A_k \Rightarrow B$A1​,…,Ak​⇒B 的步骤：一，把每个前提和结论的否定 $\neg B$¬B 都化成合取范式；二，把所有简单析取式拆开，组成子句集 S；三，对 S 中的子句反复归结，一旦得到空子句 $\square$□（由一对 L、$\neg L$¬L 归结而来），就说明 S 不可满足，推理得证。例如前提 $p \lor q$p∨q、$p \to r$p→r、$q \to r$q→r，结论 r：子句集是 $\{p \lor q, \neg p \lor r, \neg q \lor r, \neg r\}${p∨q,¬p∨r,¬q∨r,¬r}；前两个归结得 $q \lor r$q∨r，再与 $\neg q \lor r$¬q∨r 归结得 r，与 $\neg r$¬r 归结得 $\square$□。归结法步骤机械，是人工智能里机器定理证明的基础。

命题逻辑公理系统

公理系统是一种形式系统：给出符号表和公式的形成规则，选定少数重言式作为公理，再规定推理规则（常用的只有分离规则），从公理出发按规则推出的公式叫定理。不同教材选用的公理不同，一种常见的选法是三条：$A \to (B \to A)$A→(B→A)；$(A \to (B \to C)) \to ((A \to B) \to (A \to C))$(A→(B→C))→((A→B)→(A→C))；$(\neg A \to \neg B) \to (B \to A)$(¬A→¬B)→(B→A)。

对公理系统要知道两个概念：可靠性（定理都是重言式）和完备性（重言式都是定理）。命题逻辑的常见公理系统两条性质都具备，所以「是定理」和「是重言式」说的是同一批公式，只是一个靠推导、一个靠真值。

易错提醒

• ❌ 极大项 $M_i$Mi​ 也按「1 写原形、0 写否定」来写。✅ 极大项正好相反：0 写原形、1 写否定。因为 $M_i$Mi​ 要在第 i 组赋值下为假。

• ❌ 主合取范式取成真赋值的下标。✅ 主合取范式取成假赋值的下标，与主析取范式互补。因为极大项为假的那一行，正是公式为假的那一行。

• ❌ 用「肯定后件」推理：由 $p \to q$p→q 和 q 推出 p。✅ 这不是有效推理。因为 p 为 0、q 为 1 时前提都真，结论却假。

• ❌ 归结时一次消去两对互补文字。✅ 一次只消一对。因为同时消两对得到的子句不是原子句集的逻辑推论。

• ❌ 证明过程只写公式，不写依据。✅ 每一行写明「前提引入」「假言推理（2）（3）」这类依据。因为证明推导题按步骤和依据给分。

例题精讲

例题 1（求主范式）

用等值演算求 $(p \to q) \land r$(p→q)∧r 的主析取范式，并写出主合取范式。

答题要点示范：

$(p \to q) \land r \Leftrightarrow (\neg p \lor q) \land r \Leftrightarrow (\neg p \land r) \lor (q \land r)$(p→q)∧r⇔(¬p∨q)∧r⇔(¬p∧r)∨(q∧r)

第一个合取式缺 q，第二个缺 p，分别补上：$(\neg p \land q \land r) \lor (\neg p \land \neg q \land r) \lor (p \land q \land r) \lor (\neg p \land q \land r)$(¬p∧q∧r)∨(¬p∧¬q∧r)∨(p∧q∧r)∨(¬p∧q∧r)，合并相同的项，得到主析取范式 $m_1 \lor m_3 \lor m_7$m1​∨m3​∨m7​；下标互补，主合取范式是 $M_0 \land M_2 \land M_4 \land M_5 \land M_6$M0​∧M2​∧M4​∧M5​∧M6​。

点评：补变元后一定要检查有没有重复的极小项，$m_3$m3​ 在这里出现了两次。

例题 2（证明推导：附加前提法）

前提：$p \to (q \to r)$p→(q→r)，$s \to p$s→p，q。结论：$s \to r$s→r。

答题要点示范：

(1) s                附加前提引入
(2) s → p            前提引入
(3) p                (1)(2) 假言推理
(4) p → (q → r)      前提引入
(5) q → r            (3)(4) 假言推理
(6) q                前提引入
(7) r                (5)(6) 假言推理

由附加前提证明法，推出 $s \to r$s→r。

点评：结论是蕴涵式，用附加前提法最直接；每一行的依据都要写出用到的行号。

例题 3（归结推理）

用归结法证明：$\neg p \lor q$¬p∨q，$\neg q \lor r$¬q∨r，p $\Rightarrow$⇒ r。

答题要点示范：子句集 $S = \{\neg p \lor q, \neg q \lor r, p, \neg r\}$S={¬p∨q,¬q∨r,p,¬r}。$\neg p \lor q$¬p∨q 与 $\neg q \lor r$¬q∨r 归结得 $\neg p \lor r$¬p∨r；它与 p 归结得 r；r 与 $\neg r$¬r 归结得 $\square$□。所以推理成立。

点评：别忘了把结论的否定 $\neg r$¬r 放进子句集，这是归结法最常漏的一步。

本节小结

• 范式不唯一，主范式唯一；n 个变元有 $2^n$2n 个极小项和极大项。
• 主析取范式取成真赋值，主合取范式取成假赋值，下标互补；全部极小项都在就是重言式。
• 推理正确等于「前提合取蕴涵结论」是重言式；构造证明每行写编号、公式、依据。
• 结论是蕴涵式用附加前提法；正面难证用归谬法。
• 归结法：前提与结论的否定化成子句集，反复归结直到空子句。
• 公理系统由公理和推理规则组成，命题逻辑的常见公理系统既可靠又完备。