命题逻辑推理理论

一、推理的基本概念

1.1 推理的定义

定义：设A和B是两个命题公式，当蕴含式 $A \to B$ 为重言式时，称由A可以推出B，或称B是前提A的有效结论，记作 $A \Rightarrow B$。

要点：

• 推理是由给定的前提推出想要的结论
• 推理过程中需要用到推理规则
• 前提可以有多个：$A_1, A_2, \cdots, A_n \Rightarrow B$

1.2 证明推理有效性的方法

证明B是A的有效结论有三种方法：

二、演绎

2.1 演绎的定义

定义：设S是一个命题公式的集合（前提集合）。从S推出公式G的一个演绎是公式的一个有限序列：$G_1, G_2, \cdots, G_k$。其中，$G_i$ 或者属于S，或者是某些 $G_j$（$j < i$）的逻辑结果。并且 $G_k$ 就是G。我们称公式G为此演绎的逻辑结果，或称从S演绎出G，记作 $S \Rightarrow G$。

示例：设 $S = \{P \lor Q, Q \to R, P \to M, \neg M\}$，则下面的公式序列：
$\neg M, P \to M, \neg P, P \lor Q, Q, Q \to R, R$
就是从S推出R的一个演绎。

2.2 基本蕴涵式

必须熟记以下基本蕴涵式：

推理中常用的蕴含式：

2.3 形式演绎法

定义：根据基本等价式和基本蕴涵式，从前提集合S出发，演绎出结论G。

三条基本规则：

P规则（前提引入规则）

在演绎过程中可以随便使用前提集合中任一公式。

说明：前提可以在证明的任何步骤中引入使用。

T规则（逻辑结果引入规则）

在演绎过程中可以随便使用前面演绎出的某些公式的逻辑结果。

说明：如果前面已经推出了 $A$ 和 $A \to B$，则可以推出 $B$。

CP规则（附加前提规则）

如果需要演绎出的公式是 $P \to Q$ 的形式，则可以将P作为附加前提使用，设法演绎出Q。

说明：当结论是蕴含式时，将前件作为附加前提，证明后件成立。

2.4 证明的三种方法

三、基本推理规则

3.1 十大推理规则

必须熟记以下推理规则的公式和名称：

规则1：化简规则（化简律）

$P \land Q \vdash P$

说明：有前提P∧Q，可以推出P成立（也可以推出Q成立）。

规则2：附加规则

$P \vdash P \lor Q$

说明：有前提P，可以推出P∨Q成立。

规则3：假言推理

$P,\ P \to Q \vdash Q$

说明：P成立，且"如果P则Q"成立，那么Q成立。这是最常用的推理规则。

规则4：拒取式

$P \to Q,\ \neg Q \vdash \neg P$

说明：如果P则Q，现在Q不成立，那么P一定不成立。

规则5：析取三段论

$P \lor Q,\ \neg P \vdash Q$

说明：P或Q成立，现在P不成立，那么Q一定成立。

规则6：合取式

$P,\ Q \vdash P \land Q$

说明：P成立且Q成立，那么P∧Q成立。

规则7：假言三段论

$P \to Q,\ Q \to R \vdash P \to R$

说明：如果P则Q，如果Q则R，那么如果P则R。

规则8：等价三段论

$P \leftrightarrow Q,\ Q \leftrightarrow R \vdash P \leftrightarrow R$

说明：P当且仅当Q，Q当且仅当R，那么P当且仅当R。

规则9：构造性二难

$P \to Q,\ R \to S,\ P \lor R \vdash Q \lor S$

说明：如果P则Q，如果R则S，现在P或R成立，那么Q或S成立。

规则10：归谬解释（破坏性二难）

$P \lor Q,\ \neg P \lor R \vdash Q \lor R$

说明：既有P又有¬P，P肯定不成立，所以Q或R成立。

3.2 推理规则速查表

四、证明方法

4.1 直接证明法

思路：由前提直接推导结论。

步骤：

1. 列出所有前提
2. 利用推理规则逐步推导
3. 最终得到结论

形式证明的格式：

每一步包含三部分：

• 步骤号：序号
• 公式：当前步骤的命题公式
• 理由：前提引入 / 置换规则 / 某推理规则（由第X步…得到）

4.2 归谬法（反证法）

思路：将结论的否定作为附加前提，推出矛盾。

步骤：

1. 将结论的否定作为附加前提引入
2. 利用推理规则推导
3. 得到矛盾（如 $S \land \neg S$）
4. 说明原结论成立

4.3 附加前提证明法

适用条件：当要证明的结论是蕴含式 $S \to R$ 时使用。

思路：将结论的前件S作为附加前提，证明后件R成立。

步骤：

1. 将结论的前件S作为附加前提引入
2. 利用推理规则推导
3. 证明后件R成立

五、形式证明示例

5.1 例题一：直接证明法

题目：已知前提 $P \lor Q$、$P \leftrightarrow R$、$Q \to S$，证明 $S \lor R$。

分析：

• $P \lor Q \Leftrightarrow \neg P \to Q$
• 由 $\neg P \to Q$ 和 $Q \to S$，用假言三段论得 $\neg P \to S$
• $P \leftrightarrow R \Rightarrow P \to R$
• $\neg P \to S \Leftrightarrow \neg S \to P$
• 由 $\neg S \to P$ 和 $P \to R$，用假言三段论得 $\neg S \to R \Leftrightarrow S \lor R$

证明：

5.2 例题二：自然语言翻译 + 直接证明

题目：如果马会飞或羊吃草，则母鸡就会变飞鸟；如果母鸡变飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。所以羊儿不吃草。

翻译：

• 令P：马会飞
• 令Q：羊吃草
• 令R：母鸡变飞鸟
• 令S：烤熟的鸭子会跑

前提：$(P \lor Q) \to R$，$R \to S$，$\neg S$

结论：$\neg Q$

证明：

5.3 例题三：归谬法（反证法）

题目：同例题二，用归谬法证明。

证明：

5.4 例题四：附加前提证明法

题目：如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。

翻译：

• 令P：小张去看电影
• 令Q：小王去看电影
• 令R：小李去看电影
• 令S：小赵去看电影

前提：$(P \land Q) \to R$，$\neg S \lor P$，$Q$

结论：$S \to R$

证明（附加前提证明法）：

结论：$S \to R$ 成立。

六、证明技巧总结

6.1 翻译步骤

对于自然语言推理问题：

1. 找出所有原子命题
2. 用符号表示每个原子命题
3. 逐句翻译为命题公式
4. 明确前提和结论

6.2 证明策略

分析阶段（草稿纸）：

• 观察前提的形式
• 思考如何利用推理规则连接前提和结论
• 可以用等值式先做变换

正式证明：

• 每一步都要写清楚：步骤号、公式、理由
• 理由要写明：由第几步、利用什么规则
• 注意区分"前提引入"和"附加前提引入"

6.3 常用等值变换

在推理过程中，常需要先做等值变换：

• $P \lor Q \Leftrightarrow \neg P \to Q$（析取变蕴含）
• $P \to Q \Leftrightarrow \neg P \lor Q$（蕴含变析取）
• $P \leftrightarrow Q \Leftrightarrow (P \to Q) \land (Q \to P)$（等价变合取）
• $\neg(P \lor Q) \Leftrightarrow \neg P \land \neg Q$（德摩根律）

本节小结

• 推理的定义：当 $A \to B$ 为重言式时，B是A的有效结论
• 演绎的定义：从前提集合S推出公式G的有限公式序列
• 基本蕴涵式：必须熟记常用蕴含式
• 三大规则：P规则（前提引入）、T规则（逻辑结果引入）、CP规则（附加前提）
• 三大证明方法：直接证明法、归谬法（反证法）、附加前提证明法
• 十大推理规则：化简规则、附加规则、假言推理、拒取式、析取三段论、合取式、假言三段论、等价三段论、构造性二难、归谬解释
• 形式证明格式：每步写明公式和理由
• 翻译技巧：先找原子命题，再逐句翻译
• 附加前提证明法：适用于结论为蕴含式的情况

练习题

练习1：自然语言推理（直接证明法）

题目：如果交通阻塞迟到了，那么小张迟到了；如果小张迟到了，那么他就不能评优；小张没有评优是不对的（即小张评优了）。所以交通没有阻塞且小张没有迟到。

翻译：设 $P$：交通阻塞，$Q$：小张迟到，$R$：小张评优。

前提：$P \to Q$，$Q \to \neg R$，$R$

结论：$\neg P \wedge \neg Q$

证明：

练习2：自然语言推理（归谬法）

题目：同练习1，用归谬法证明。

证明：

练习3：附加前提证明法

题目：前提：$\neg S \vee P$，$Q$，$(P \wedge Q) \to R$。结论：$S \to R$。

证明（CP规则）：

结论：$S \to R$ 成立。

练习4：综合推理

题目：前提：$P \vee Q$，$P \to R$，$Q \to S$。结论：$R \vee S$。

证明：

关键术语速查