本节对应原书 PDF 第 64–75 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

推理是数理逻辑的重要内容，它是对数学证明以及在各种各样领域中的推理思维的高度抽象。

2.4.1 推理的形式结构

定义 2.19 设 A_1,A_2,\cdots,A_k,B 都是命题公式，若对于 A_1,A_2,\cdots,A_k,B 中出现的命题变项的任意一组赋值，或者 A_1\wedge A_2\wedge\cdots\wedge A_k 为假，或者当 A_1\wedge A_2\wedge\cdots\wedge A_k 为真时，B 也为真，则称由前提 A_1,A_2,\cdots,A_k 推出 B 的推理是有效的或正确的，并称 B 是有效的结论。

由定义 2.19 容易证明下面定理。

定理 2.8 命题公式 A_1,A_2,\cdots,A_k 推出 B 的推理正确当且仅当蕴涵式

(A_1\wedge A_2\wedge\cdots\wedge A_k)\rightarrow B

为重言式。

由定理 2.8 给出下面定义。

定义 2.20 称

(A_1\wedge A_2\wedge\cdots\wedge A_k)\rightarrow B\tag{2.7}

为由前提 A_1,A_2,\cdots,A_k 推结论 B 的推理的形式结构。

当式(2.7)为重言式(即推理正确)时，记为

(A_1\wedge A_2\wedge\cdots\wedge A_k)\Rightarrow B\tag{2.8}

其中 \Rightarrow 同 \Leftrightarrow 一样是一种元语言符号，用来表示蕴涵式为重言式。

解读：判断一个推理是否正确，唯一标准是它的形式结构是否为重言式——与前提、结论在现实中是真是假无关。所以"推理正确"（形式有效）和"结论为真"是两件事：前提全假时，推理照样可以正确。

推理的形式结构还有另外的表达方式，比如将前提与结论分开写。

\begin{gathered} \text{前提：}\;A_1,A_2,\cdots,A_k.\\ \text{结论：}\;B. \end{gathered}\tag{2.9}

对于实际中给出的推理，应首先将推理中的简单命题符号化，然后写出前提和结论，使其成为式(2.9)的形式。通过判断推理的形式结构(2.7)是否重言式，就可以确定推理是否有

效.判断(2.7)是否是重言式的方法很多，例如，

(1) 真值表法；

(2) 等值演算法；

(3) 主析取范式法；

(4) 观察法，若能观察出式(2.7)的成假赋值，则断言推理一定不正确.

例 2.24 判断下面推理是否正确.

(1) 若 a 是偶数，则 a 能被 2 整除.a 是偶数.所以，a 能被 2 整除.

(2) 若 a 是偶数，则 a 能被 2 整除.a 能被 2 整除.所以，a 是偶数.

(3) 下午马芳或去看电影或去游泳.她没去看电影.所以，她去游泳了.

(4) 若下午气温超过 30℃，则王小燕必去游泳.若她去游泳，她就不去看电影了.所以，若王小燕没去看电影，下午气温必超过了 30℃.

解 先将简单命题符号化，然后写出前提、结论，即推理形式结构式(2.9)的形式，同时写出形式结构式(2.7)的形式，用式(2.7)的形式判断推理是否正确.

(1) 设

p：a 是偶数.

q：a 能被 2 整除.

前提：p\rightarrow q,p.

结论：q.

推理的形式结构：

(p\rightarrow q)\wedge p\rightarrow q\qquad(2.10)

用真值表法判断此推理.由表 2.14 可知，(2.10)是重言式，因而推理正确，式(2.10)可以写成 (p\rightarrow q)\wedge p\Rightarrow q.

表 2.14

pqp\rightarrow q(p\rightarrow q)\wedge p(p\rightarrow q)\wedge p\rightarrow q
00101
01101
10001
11111

(2) 设 p,q 的含义同(1).

前提：p\rightarrow q,q.

结论：p.

推理的形式结构：(p\rightarrow q)\wedge q\rightarrow p. (2.11)

容易看出，01 是式(2.11)的成假赋值，所以(2)中推理不正确.

(3) 设

p：马芳下午去看电影.

q：马芳下午去游泳.

前提：p\vee q,\neg p.

结论：q.

推理的形式结构：((p\vee q)\wedge\neg p)\rightarrow q. (2.12)

用等值演算法来判断式(2.12)是否为重言式.演算过程如下.

\begin{aligned} &((p\vee q)\wedge\neg p)\rightarrow q\\ &\Leftrightarrow\neg((p\vee q)\wedge\neg p)\vee q\\ &\Leftrightarrow((\neg p\wedge\neg q)\vee p)\vee q\\ &\Leftrightarrow((\neg p\vee p)\wedge(\neg q\vee p))\vee q \end{aligned}
\begin{aligned} &\Leftrightarrow\neg q\vee p\vee q\\ &\Leftrightarrow 1 \end{aligned}

这说明式(2.12)为重言式，所以推理正确.因而可将式(2.12)记为

((p\vee q)\wedge\neg p)\Rightarrow q

(4) 设

p：下午气温超过 30℃.

q：王小燕去游泳.

r：王小燕去看电影.

前提：p\rightarrow q,q\rightarrow\neg r.

结论：\neg r\rightarrow p.

推理的形式结构：((p\rightarrow q)\wedge(q\rightarrow\neg r))\rightarrow(\neg r\rightarrow p). (2.13)

用主析取范式法判断式(2.13)是否为重言式.

\begin{aligned} &((p\rightarrow q)\wedge(q\rightarrow\neg r))\rightarrow(\neg r\rightarrow p)\\ &\Leftrightarrow\neg((\neg p\vee q)\wedge(\neg q\vee\neg r))\vee(r\vee p)\\ &\Leftrightarrow((p\wedge\neg q)\vee(q\wedge r))\vee r\vee p\\ &\Leftrightarrow p\vee r & &(用两次吸收律)\\ &\Leftrightarrow(p\wedge\neg q\wedge\neg r)\vee(p\wedge\neg q\wedge r)\vee(p\wedge q\wedge\neg r)\vee(p\wedge q\wedge r)\vee(\neg p\wedge\neg q\wedge r)\\ &\quad\vee(\neg p\wedge q\wedge r)\vee(p\wedge\neg q\wedge r)\vee(p\wedge q\wedge r)\\ &\Leftrightarrow m_1\vee m_3\vee m_4\vee m_5\vee m_6\vee m_7 & &(重新排序) \end{aligned}

可见式(2.13)不是重言式(主析取范式中少两个极小项 m_0,m_2)，所以推理不正确.

2.4.2 推理的证明

2.4.1 节是从命题公式的真值和命题演算的角度讨论如何判断推理的正确性.在实际应用中，证明推理正确和进行有效推理的基本方法是构造推理的证明，即构造一个从前提道结论的公式序列，序列中的每一个公式都是前提的有效结论.本节介绍如何构造这样的序列.

若蕴涵式 A\rightarrow B 是重言式，即 A\Rightarrow B，则以前件 A 为前提，后件 B 为结论的推理是正确的.例如，由 p\Rightarrow p\vee q，可知由前提 p 推出结论 p\vee q 是正确的.因为这个缘故，称永真的蕴涵式为推理定律.下面给出 9 条常用的推理定律，它们都不难验证.

(1) A\Rightarrow(A\vee B). 附加律

(2) (A\wedge B)\Rightarrow A. 化简律

(3) (A\rightarrow B)\wedge A\Rightarrow B. 假言推理

(4) (A\rightarrow B)\wedge\neg B\Rightarrow\neg A. 拒取式

(5) (A\vee B)\wedge\neg B\Rightarrow A. 析取三段论

(6) (A\rightarrow B)\wedge(B\rightarrow C)\Rightarrow(A\rightarrow C). 假言三段论

(7) (A\rightarrow B)\wedge(C\rightarrow D)\wedge(A\vee C)\Rightarrow(B\vee D)； 构造性二难

(A\rightarrow B)\wedge(\neg A\rightarrow B)\Rightarrow B. 构造性二难(特殊形式)

(8) (A\rightarrow B)\wedge(C\rightarrow D)\wedge(\neg B\vee\neg D)\Rightarrow(\neg A\vee\neg C). 破坏性二难

此外，每一个等值式可以派生出两条推理定律：由 A\Leftrightarrow B，可以得到 A\Rightarrow B 和 B\Rightarrow A.

解读：等值式比推理定律"强"：A\Leftrightarrow B 双向成立，所以它同时给出 A\Rightarrow B 与 B\Rightarrow A 两条推理定律；反之，A\Rightarrow B 只是单向的，不能反推。这就是 24 个等值式在证明中格外好用的原因。

就是说，可以把一个公式换成任何与它等值的公式，称作等值置换，简称置换.特别地，可以利用 2.2.1 节中的 24 个等值式进行这种置换.

定义 2.21 设前提 A_1,A_2,\cdots,A_k，结论 B，如果一个公式序列的最后是 B 并且序列中的每一个公式或者是某个 A_i(1\leqslant i\leqslant k)，或者是前面公式的有效结论，则称这个序列是由前提 A_1,A_2,\cdots,A_k 推出结论 B 的证明.

显然，如果存在由前提 A_1,A_2,\cdots,A_k 推出结论 B 的证明，则这个推理是有效的.实际上，证明的本身就是一个有效推理的过程.为了构造证明，引入下述推理规则：

(1) 前提引入规则：在证明的每一步都可以引入前提.

(2) 结论引入规则：在证明的每一步都可以引入由前面的公式得到的有效结论.

由前面给出的 8 条推理定律和等值置换，应用结论引入规则可以导出以下各条推理规则.

(3) 置换规则：在证明的每一步可以引入前面公式的等值置换.

(4) 假言推理规则(或称分离规则)：若证明的公式序列中已出现过 A\rightarrow B 和 A，则由假言推理定律 ((A\rightarrow B)\wedge A\Rightarrow B) 可知，B 是 A\rightarrow B 和 A 的有效结论，由结论引入规则可知，可将 B 引入到命题序列中来.用图式表示为如下形式

\frac{\begin{aligned}A&\rightarrow B\\ A&\end{aligned}}{B}

以下各条推理定律直接以图式给出，不再加以说明.

(5) 附加规则：

\frac{A}{A\vee B}

(6) 化简规则：

\frac{A\wedge B}{A}

(7) 拒取式规则：

\frac{\begin{aligned}A&\rightarrow B\\ \neg B&\end{aligned}}{\neg A}

(8) 假言三段论规则：

\frac{\begin{aligned}A&\rightarrow B\\ B&\rightarrow C\end{aligned}}{A\rightarrow C}

(9) 析取三段论规则：

\frac{\begin{aligned}A&\vee B\\ \neg B&\end{aligned}}{A}

(10) 构造性二难推理规则：

\frac{\begin{aligned}A&\rightarrow B\\ C&\rightarrow D\\ A&\vee C\end{aligned}}{B\vee D}

(11) 破坏性二难推理规则：

\frac{\begin{aligned}A&\rightarrow B\\ C&\rightarrow D\\ \neg B&\vee\neg D\end{aligned}}{\neg A\vee\neg C}

(12) 合取引入规则：

\frac{\begin{aligned}A&\\ B&\end{aligned}}{A\wedge B}

本条规则说明，若证明的公式序列中已出现 A 和 B，则可将 A\wedge B 引入序列中.它显然是合理的.

构造从前提 A_1,A_2,\cdots,A_k 推结论 B 的证明时，推理的形式结构采用式(2.9)的形式.

前提：A_1,A_2,\cdots,A_k.

结论：B.

对于正确的推理，人们能从前提出发，严格地按着推理规则构造命题序列，序列的最后一条是结论 B.还应该指出，对于任意的赋值，若 A_1,A_2,\cdots,A_k 均为真，则构造出的命题序列的每一条也均为真，从而结论 B 为真.

例 2.25 构造下面推理的证明.

(1) 前提：p\vee q,q\rightarrow r,p\rightarrow s,\neg s.

结论：r\wedge(p\vee q).

(2) 前提：\neg p\vee q,r\vee\neg q,r\rightarrow s.

结论：p\rightarrow s.

解 (1) 证明：

① p\rightarrow s 前提引入

② \neg s 前提引入

③ \neg p ①②拒取式

④ p\vee q 前提引入

⑤ q ③④析取三段论

⑥ q\rightarrow r 前提引入

⑦ r ⑤⑥假言推理

⑧ r\wedge(p\vee q) ⑦④合取

此证明的序列长为 8，最后一步为推理的结论，所以推理正确，r\wedge(p\vee q) 是有效的结论.

(2) 证明：

① \neg p\vee q 前提引入

② p\rightarrow q ①置换

③ r\vee\neg q 前提引入

④ q\rightarrow r ③置换

⑤ p\rightarrow r ②④假言三段论

⑥ r\rightarrow s 前提引入

⑦ p\rightarrow s ⑤⑥假言三段论

得证推理正确，p\rightarrow s 是有效结论.

例 2.26 构造下面推理的证明.

若数 a 是实数，则它不是有理数就是无理数.若 a 不能表示成分数，则它不是有理数.a 是实数且它不能表示成分数.所以，a 是无理数.

解 首先将简单命题符号化.

p：a 是实数.

q：a 是有理数.

r：a 是无理数.

s：a 能表示成分数.

前提：p\rightarrow(q\vee r),\neg s\rightarrow\neg q,p\wedge\neg s.

结论：r.

证明：

① p\wedge\neg s 前提引入

② p ①化简

③ \neg s ①化简

④ p\rightarrow(q\vee r) 前提引入

⑤ q\vee r ②④假言推理

⑥ \neg s\rightarrow\neg q 前提引入

⑦ \neg q ③⑥假言推理

⑧ r ⑤⑦析取三段论

例 2.27 构造下面推理的证明.

如果王小红努力学习，她一定取得好成绩.若王小红贪玩或不按时完成作业，她就不能取得好成绩.所以，如果王小红努力学习，她就不贪玩并且按时完成作业.

解 将简单命题符号化.

p：王小红努力学习.

q：王小红取得好成绩.

r：王小红贪玩.

s：王小红按时完成作业.

前提：p\rightarrow q,(r\vee\neg s)\rightarrow\neg q.

结论：p\rightarrow(\neg r\wedge s).

证明：

① p\rightarrow q 前提引入

② (r\vee\neg s)\rightarrow\neg q 前提引入

③ q\rightarrow\neg(r\vee\neg s) ②置换

④ p\rightarrow\neg(r\vee\neg s) ①③假言三段论

⑤ p\rightarrow(\neg r\wedge s) ④置换

下面介绍两种证明方法.

(1) 附加前提证明法

有时推理的形式结构具有如下形式

(A_1\wedge A_2\wedge\cdots\wedge A_k)\rightarrow(A\rightarrow B)\tag{2.14}

式(2.14)中结论也为蕴涵式.因为

\begin{aligned} &(A_1\wedge A_2\wedge\cdots\wedge A_k)\rightarrow(A\rightarrow B)\\ &\Leftrightarrow\neg(A_1\wedge A_2\wedge\cdots\wedge A_k)\vee(\neg A\vee B)\\ &\Leftrightarrow(\neg(A_1\wedge A_2\wedge\cdots\wedge A_k)\vee\neg A)\vee B\\ &\Leftrightarrow\neg(A_1\wedge A_2\wedge\cdots\wedge A_k\wedge A)\vee B\\ &\Leftrightarrow(A_1\wedge A_2\wedge\cdots\wedge A_k\wedge A)\rightarrow B \end{aligned} \tag{2.15}

所以可以通过证明推理(2.15)来证明推理(2.14)，即当推理的结论为蕴涵式 A\rightarrow B 时，把 A 加入推理的前提，把 B 作为推理的结论.称此证明方法为附加前提证明法，并称 A 为附加前提.

解读：结论是蕴涵式 A\rightarrow B 时，与其直接证整个蕴涵式，不如把前件 A 搬进前提、只证后件 B——由式(2.15)两者等价。这样证明显著变短，代价是要在证明里注明 A 是"附加前提引入"而不是原前提。

用附加前提证明法，重新证明例 2.27 中的推理.

证明：

① p 附加前提引入

② p\rightarrow q 前提引入

③ q ①②假言推理

④ (r\vee\neg s)\rightarrow\neg q 前提引入

⑤ \neg(r\vee\neg s) ③④拒取式

⑥ \neg r\wedge s ⑤置换

(2) 归谬法

归谬法(反证法)在第 1 章 1.3 节中已经介绍过，它是把结论的否定加入前提，而要推出矛盾，即以 0 为结论.也就是说，把证明推理

(A_1\wedge A_2\wedge\cdots\wedge A_k)\rightarrow B

转换成证明推理

(A_1\wedge A_2\wedge\cdots\wedge A_k\wedge\neg B)\rightarrow 0

解读：归谬法的逻辑支点是"\neg X\vee 0\Leftrightarrow\neg X"——把 B 换成 \neg B 塞进前提，只需推出矛盾（即 0）即可。使用时要记住：最后一步必须真的推出 q\wedge\neg q 或 0，否则归谬法并没有完成证明。

其理由如下：

\begin{aligned} &(A_1\wedge A_2\wedge\cdots\wedge A_k)\rightarrow B\\ &\Leftrightarrow\neg(A_1\wedge A_2\wedge\cdots\wedge A_k)\vee B\\ &\Leftrightarrow\neg(A_1\wedge A_2\wedge\cdots\wedge A_k\wedge\neg B)\\ &\Leftrightarrow\neg(A_1\wedge A_2\wedge\cdots\wedge A_k\wedge\neg B)\vee 0\\ &\Leftrightarrow(A_1\wedge A_2\wedge\cdots\wedge A_k\wedge\neg B)\rightarrow 0 \end{aligned}

例 2.28 构造下面推理的证明.

如果小张守第一垒并且小李向 B 队投球，则 A 队将取胜.或者 A 队未取胜，或者 A 队成为联赛第一名.A 队没有成为联赛的第一名.小张守第一垒.因此，小李没向 B 队投球.

解 先将简单命题符号化.

p：小张守第一垒.

q：小李向 B 队投球.

r：A 队取胜.

s：A 队成为联赛第一名.

前提：(p\wedge q)\rightarrow r,\neg r\vee s,\neg s,p.

结论：\neg q.

证明：用归谬法证.

① q 结论的否定引入

② \neg r\vee s 前提引入

③ \neg s 前提引入

④ \neg r ②③析取三段论

⑤ (p\wedge q)\rightarrow r 前提引入

⑥ \neg(p\wedge q) ④⑤拒取式

⑦ \neg p\vee\neg q ⑥置换

⑧ p 前提引入

⑨ \neg q ⑦⑧析取三段论

⑩ q\wedge\neg q ①⑨合取

所以推理正确.请读者不用归谬法证明之.

例 2.29 民警侦查一起盗窃案，掌握了下述事实：

(1) 甲或乙偷了一台计算机.

(2) 若甲偷了这台计算机，则作案时间不可能发生在午夜之前.

(3) 若乙说的是真话，则午夜时屋里的灯是亮着的.

(4) 若乙说的是谎话，则作案时间在午夜之前.

(5) 午夜时屋里的灯灭了.

问：是谁偷了这台计算机？

解 设 p：甲偷了这台计算机；

q：乙偷了这台计算机；

r：作案时间发生在午夜前；

s：乙说的是真话；

t：午夜时屋里的灯是亮着的.

根据掌握的事实，有下述前提.

前提：p\vee q,p\rightarrow\neg r,s\rightarrow t,\neg s\rightarrow r,\neg t

推理如下：

① s\rightarrow t 前提引入

② \neg t 前提引入

③ \neg s ①②拒取式

④ \neg s\rightarrow r 前提引入

⑤ r ③④假言推理

⑥ p\rightarrow\neg r 前提引入

⑦ \neg p ⑤⑥拒取式

⑧ p\vee q 前提引入

⑨ q ⑦⑧析取三段论

可以得出结论：乙偷了这台计算机.

2.4.3 归结证明法

2.4.2 节在构造推理证明时使用很多条推理规则，这不利于在计算机上的实现.归结证明法除前提引入规则外，只使用一条归结规则，因而便于在计算机上的实现，在人工智能中有广泛的应用.归结证明法又称消解法.

解读：归结证明法的全部技巧只有一句"找到一对互补文字（L 与 \neg L）把它消掉"，其余都是机械操作，因此特别适合程序实现。代价是必须先做准备工作：把结论取反、把所有公式都化成合取范式，每个简单析取式当作一条前提。

归结规则

显然有

(L\vee C_1)\wedge(\neg L\vee C_2)\Rightarrow C_1\vee C_2\tag{2.16}

其中，L 是一个变元，C_1 和 C_2 是简单析取式.事实上，只有当 C_1 和 C_2 都为 0 时，右端才为 0，而此时左端也为 0，因此这是一个重言式.称(2.16)为归结定律.根据归结定律，应用结论引入规则得到下述归结规则.

\frac{\begin{aligned}L&\vee C_1\\ \neg L&\vee C_2\end{aligned}}{C_1\vee C_2}

其中，L 是一个变元，C_1 和 C_2 是简单析取式.特别地，当 C_1 和 C_2 为空简单析取式(即不含任何文字的简单析取式)时，由 L 和 \neg L 推出空简单析取式，而空简单析取式是矛盾式——它没有一个文字的值是 1.也就是说，L 和 \neg L 推出 0.实际上，\neg L\wedge L\Leftrightarrow 0.今后把空简单析取式记作 0.当 C_1 或 C_2 为空简单析取式时也用 0 代替.例如，由 p 和 \neg p\vee q 推出 q，这里 L=p,C_1=0,C_2=q.

应用归结规则由两个含有相同变元(一个含变元，另一个含它的否定式)的简单析取式推出一个新的不含这个变元的简单析取式，对这个新的简单析取式又可以继续应用归结规则.

归结证明法的基本思想是采用归谬法，把结论的否定引入前提.如果推出空简单析取式，即推出 0，则证明推理正确.其证明步骤如下：

(1) 把结论的否定引入前提.

(2) 把所有前提，包括结论的否定在内，化成合取范式，并把得到的合取范式中的所有简单析取式作为前提.

(3) 应用归结规则进行推理.

(4) 如果推出空简单析取式，即推出 0，则证明推理正确.

实际上可以证明，如果推理正确，则一定可以推出空简单析取式.

(1)和(2)是构造推理证明的准备工作.设推理形式为

前提：A_1,A_2,\cdots,A_k.

结论：B

求出 A_1,A_2,\cdots,A_k 和 \neg B 的合取范式，设

\begin{aligned} A_1&\Leftrightarrow C_{11}\wedge C_{12}\wedge\cdots\wedge C_{1n_1}\\ A_2&\Leftrightarrow C_{21}\wedge C_{22}\wedge\cdots\wedge C_{2n_2}\\ &\vdots \end{aligned}
\begin{aligned} A_k&\Leftrightarrow C_{k1}\wedge C_{k2}\wedge\cdots\wedge C_{kn_k}\\ \neg B&\Leftrightarrow D_1\wedge D_2\wedge\cdots\wedge D_m \end{aligned}

于是，经过(1)和(2)把推理的形式转化为下述等价的形式

\begin{aligned} 前提：&C_{11},C_{12},\cdots,C_{1n_1},C_{21},C_{22},\cdots,C_{2n_2},\cdots,\\ &C_{k1},C_{k2},\cdots,C_{kn_k},D_1,D_2,\cdots,D_m\\ 结论：&0 \end{aligned} \tag{2.17}

当然，若在(2.17)的前提中有重复出现的简单析取式，应该删去.

例 2.30 用归结法证明下面推理.

前提：p\vee q,\neg p\vee r,\neg r\vee s.

结论：q\vee s.

解 先把推理形式改写成(2.17)的形式，这里前提中的公式都已经是简单析取式，而 \neg(q\vee s)\Leftrightarrow\neg q\wedge\neg s.因此有

前提：p\vee q,\neg p\vee r,\neg r\vee s,\neg q,\neg s.

结论：0

证明：① p\vee q 前提引入

② \neg p\vee r 前提引入

③ q\vee r ①②归结

④ \neg r\vee s 前提引入

⑤ q\vee s ③④归结

⑥ \neg q 前提引入

⑦ s ⑤⑥归结

⑧ \neg s 前提引入

⑨ 0 ⑦⑧归结

注意：在推理中，有些简单析取式是一个文字，如 \neg q,s 与 \neg s.用归结规则时，将它们分别看成 \neg q\vee 0,s\vee 0 与 \neg s\vee 0.

例 2.31 用归结法构造下面推理的证明.

前提：p,p\rightarrow q,\neg q\vee r.

结论：r.

解 先将此推理化成式(2.17)形式.

前提：p,\neg p\vee q,\neg q\vee r,\neg r.

结论：0.

证明：① p 前提引入

② \neg p\vee q 前提引入

③ q ①②归结

④ \neg q\vee r 前提引入

⑤ r ③④归结

⑥ \neg r 前提引入

⑦ 0 ⑤⑥归结

例 2.32 用归结法证明下面推理.

前提：\neg p\vee q\vee r,\neg q,\neg r.

结论：\neg p.

解 先将推理形式改写成下述形式

前提：\neg p\vee q\vee r,\neg q,\neg r,p.

结论：0.

证明：① \neg p\vee q\vee r 前提引入

② \neg q 前提引入

③ \neg p\vee r ①②归结

④ \neg r 前提引入

⑤ \neg p ③④归结

⑥ p 前提引入

⑦ 0 ⑤⑥归结

例 2.33 用归结法证明下面推理.

前提：p\rightarrow r,\neg r\vee q,p.

结论：q.

解 首先将推理形式化成(2.17)的形式.

前提：\neg p\vee r,\neg r\vee q,p,\neg q.

结论：0.

证明：① \neg p\vee r 前提引入

② p 前提引入

③ r ①②归结

④ \neg r\vee q 前提引入

⑤ q ③④归结

⑥ \neg q 前提引入

⑦ 0 ⑤⑥归结

例 2.34 用归结证明法证明下面推理.

前提：q\rightarrow p,q\leftrightarrow s,s\rightarrow t,t\wedge r.

结论：p\wedge q\wedge s.

解 先将推理形式化成(2.17)的形式.

前提：\neg q\vee p,\neg q\vee s,\neg s\vee q,\neg s\vee t,\neg t\vee s,t,r,\neg p\vee\neg q\vee\neg s.

结论：0.

这里注意，q\leftrightarrow s\Leftrightarrow(\neg q\vee s)\wedge(\neg s\vee q) 有两个简单析取式 \neg q\vee s 和 \neg s\vee q，同样地，s\leftrightarrow t 和 t\wedge r 也有两个简单析取式，而 \neg(p\wedge q\wedge s)\Leftrightarrow\neg p\vee\neg q\vee\neg s 是一个简单析取式.

证明：① \neg t\vee s 前提引入

② t 前提引入

③ s ①②归结

④ \neg s\vee q 前提引入

⑤ q ③④归结

⑥ \neg q\vee p　　　　前提引入

⑦ p　　　　　　　⑤⑥归结

⑧ \neg p\vee\neg q\vee\neg s　　前提引入

⑨ \neg q\vee\neg s　　　⑦⑧归结

⑩ \neg s　　　　　⑤⑨归结

⑪ 0　　　　　　　③⑩归结

2.4.4 对证明方法的补充说明

现在回过头来用命题逻辑对 1.3 节中介绍的证明方法做进一步的说明.

设待证明的命题为 A\rightarrow B,由于只有当 A 为真、B 为假时,A\rightarrow B 为假,故只需证明当 A 为真时 B 为真. 特别地,若证明了 A 为矛盾式,则 A\rightarrow B 必为真. 这就是前提假证明法. 若证明了 B 为永真式,则不管 A 如何,A\rightarrow B 也必为真. 这就是结论真证明法.

关于间接证明法,因为 A\rightarrow B\Leftrightarrow \neg B\rightarrow \neg A,所以可以通过证明 \neg B\rightarrow \neg A 为真来证明 A\rightarrow B 为真.

关于归谬法在 2.4.2 节中已作说明.

解读：这一小节把中学数学里常用的证明方法逐一翻译成了命题逻辑的等值式——前提假、结论真、逆否、反证、分情况，本质上都是 A\rightarrow B 的不同等值变形。认出所用方法对应哪条等值式，就知道该证的式子长什么样。

关于分情况证明法,因为

\begin{aligned} &(A_1\vee A_2\vee\cdots\vee A_k)\rightarrow B\\ \Leftrightarrow &\neg(A_1\vee A_2\vee\cdots\vee A_k)\vee B\\ \Leftrightarrow &(\neg A_1\wedge \neg A_2\wedge\cdots\wedge \neg A_k)\vee B\\ \Leftrightarrow &(\neg A_1\vee B)\wedge(\neg A_2\vee B)\wedge\cdots\wedge(\neg A_k\vee B)\\ \Leftrightarrow &(A_1\rightarrow B)\wedge(A_2\rightarrow B)\wedge\cdots\wedge(A_k\rightarrow B) \end{aligned}

所以,可以用证明所有的 A_1\rightarrow B,A_2\rightarrow B,\cdots,A_k\rightarrow B 都为真来证明 (A_1\vee A_2\vee\cdots\vee A_k)\rightarrow B 为真.