1.5 命题逻辑的推理

1.5.1 推理理论

数理逻辑是用数学方法研究推理的形式结构和推理规律的数学学科。推理是从前提出发推出结论的思维过程，其中前提是已知的命题公式，结论是从前提出发应用推理规则推出的命题公式。关于从前提 A 推出结论 B 的定义如下。

定义1.5.1 设 A 和 B 是两个命题公式，当且仅当命题 A → B 是重言式时（即 A → B ⇔1时），称 从 A 推出 B 是有效的 ，或 A 蕴涵 B ，或 B 是前提 A 的结论 ，可以表示成 A ⇒ B 。

一般地，推理的前提可以是多个命题公式 A ₁ ， A ₂ ，…， A _n ，若（ A ₁ ∧ A ₂ ∧…∧ A _n ）→ B 是重言式，则称由前提 A ₁ ， A ₂ ，…， A _n 推出结论 B 是有效的，可表示为（ A ₁ ∧ A ₂ ∧…∧ A _n ）⇒ B 。

注意，⇒不是逻辑联结词，因而 A ⇒ B 不是公式，称 A ⇒ B 为 蕴涵关系式 。

例1.5.1 判断下列推理是否正确。

1） p ∧（ p → q ）⇒ q

2）（ p → q ）∧ q ⇒ p

解 写出 p ∧（ p → q ）→ q 和（ p → q ）∧ q → p 的真值表。

由真值表1.5.1可知， p ∧（ p → q ）→ q 是重言式，所以蕴涵关系式 p ∧（ p → q ）⇒ q 成立。而（ p → q ）∧ q → p 不是重言式，所以蕴涵关系式（ p → q ）∧ q ⇒ p 不成立。

在由前提推出结论时，如果所有前提为真，则结论为真。但是，推理的有效性并不保证推出的结论是真的，因为有效推理并没有要求所有前提的真值必须为真，当前提中包含假命题时，有效推理可能推出真值为假的结论。

例1.5.2 证明“如果牛吃草，则马会飞；马不会飞，所以牛不吃草”是正确的推理。

证明 设 p 表示“牛吃草”， q 表示“马会飞”。

上述推理问题的前提符号化为 p → q 、 ，结论符号化为 。因此，只需证明 是 p → q 和 的结论。

而

所以， 是 p → q 和 的结论，即蕴涵关系式 成立。尽管结论“牛不吃草”真值为假，这仍然是正确的推理，这个结论是有效的，得出这个真值为假的结论的原因是前提条件中的 p → q 的真值为假。

◀

有一些重要的蕴涵关系式，称为 推理定律 。这些蕴涵式如下。

定理1.5.1 对任意公式 A ₁ ， A ₂ ，…， A _n ， B ， C ，由 A ₁ ， A ₂ ，…， A _n 推出 B → C 是有效的，当且仅当由 A ₁ ， A ₂ ，…， A _n 和 B 推出 C 是有效的。

证明 根据定义1.5.1，有（ A ₁ ∧ A ₂ ∧…∧ A _n ）→（ B → C ）⇔1。

因为

所以（ A ₁ ∧ A ₂ ∧…∧ A _n ）→（ B → C ）是永真式，当且仅当（ A ₁ ∧ A ₂ ∧…∧ A _n ∧ B ）→ C 是永真式，即 A ₁ ， A ₂ ，…， A _n 和 B 推出 C 是有效的。

◀

该定理在证明推理问题时十分有用。根据该定理，如果需要推出结论的形式为 B → C ，则可以把 B 放在前提中，设法推出 C 即可。这是一条命题推理规则，称为 CP规则 。

1.5.2 推理证明方法

根据定义1.5.1，判断由前提 A 推出结论 B 的方法就是判断 A → B 是重言式的方法，可以采用不同的证明方法，下面是常用的证明方法，其中，真值表法、等价运算法是基本的方法。

通过写出真值表判断 A → B 的类型，若 A → B 是重言式，则由前提 A 可以推出结论 B 。

1.真值表法

例1.5.3 证明前提 p ∨ q 和 可以推出结论 q ∨ r 。

证明 根据定义1.5.1，只需证明 是重言式。

其真值表如表1.5.2所示。

由真值表可知， 是重言式，所以前提 p ∨ q 和 可以推出结论 q ∨ r 。

◀

2.等价演算法

利用命题的等值演算判断 A → B 的类型，若 A → B 是重言式，则由前提 A 可以推出结论 B 。

例1.5.4 证明 q 是 和 p ∨ q 的结论。

证明

当命题公式所含命题变元较多时，上述证明方法较为不便，因而常用演绎法证明推理的有效性。

◀

3.演绎法

演绎法从前提（假设）出发，依据公认的推理规则和推理定律推导出一个结论。在证明过程中，将前提和推理定律匹配，推出结论。判断推出的结论是否为需要证明的结论，如果是，则结束；如果不是，则把推出的结论加入前提集合中，构成一组新的前提，重复上述过程，直到推出需要证明的结论为止。演绎法证明推理问题就是用命题公式序列描述推理过程，其中的每个公式或者是前提，或者是由某些前提得出的结论。在这样的证明中需要引入下面的推理规则。

1）前提引入规则。在推导的过程中，可随时引入前提集合中的任意一个前提。

2）结论引入规则。在推导的过程中，所得到的结论都可作为后续推导的前提。

3）置换规则。在推导的过程中，命题公式的子公式都可以用等值的公式置换。

4）CP规则（附加前提规则）。如果推出的结论形为 P → Q ，则可以把 P 放到前提中去，设法推出 Q 即可。

这些规则与1.5.1节的推理定律和1.3.1节的基本等价公式作为推理和演绎的基础，可以构造一个完整的命题演算推理系统，证明命题逻辑的推理。

例1.5.5 证明（ p ∨ q ）∧（ p ↔ r ）∧（ q → s ）⇒ s ∨ r 。

证明

例1.5.6 证明，由前提“今天下午有课且今天比昨天冷；只有今天下午没有课，我们才去游泳；如果我们不去游泳，我们就去打篮球；如果我们打篮球，我们就会感到精力充沛”推出结论“我们感到精力充沛”是正确的。

证明 设 p 表示“今天下午有课”， q 表示“今天比昨天冷”， r 表示“我们去游泳”， s 表示“我们去打篮球”， h 表示“我们感到精力充沛”。

则前提为 p ∧ q ， ，结论是 h 。

例1.5.7 证明 是 p →（ q → r ）和 p ∧ q 的结论。

证明

4.附加前提证明法

根据CP规则，如果推出的结论形为 P → Q ，则可以把 P 放到前提中去，设法推出 Q 即可。

例1.5.8 证明 r → s 是 p →（ q → s ）、 、 q 的结论。

证明 根据CP规则，只需证明 s 是 r 、 p →（ q → s ）、 、 q 的结论。

以上证明方法又称 直接证明法 。在推理问题的构造证明中，有时采用间接证明的方法（又称归谬法）。

5.间接推演法（归谬法）

间接推演法就是把要推出的结论否定后与原来的前提一起使用推出矛盾结论的证明方法。

定义1.5.2 设 H ₁ ， H ₂ ，…， H _r 是 r 个命题公式。若 H ₁ ∧ H ₂ ∧…∧ H _r 是矛盾式，则称 H ₁ ， H ₂ ，…， H _r 是 不相容 的，否则称 H ₁ ， H ₂ ，…， H _r 是 相容 的。

如果公式 B 是由前提 H ₁ ， H ₂ ，…， H _r 推出的，则 是重言式，因此 是矛盾式，即 H ₁ ， H ₂ ，…， H _r ， 不相容。因而，若 H ₁ ， H ₂ ，…， H _r ， 不相容，则说明 B 是公式 H ₁ ， H ₂ ，…， H _r 的逻辑结论。这种将 B 作为附加前提推出矛盾的证明方法称为 间接推演法（归谬法） 。

例1.5.9 用间接法证明 p 是 的结论。

6.归结证明法

例1.5.10 证明 蕴涵结论 r 。

证明

在例1.5.10中利用了归结规则，称为 归结证明 。归结规则在基于逻辑规则的编程语言中扮演着重要角色。可以用归结规则构建自动定理证明系统。要使用归结规则构造命题逻辑中的证明，前提和结论必须被表示为子句，子句是变元或其否定的析取，如 p ∨ q 、 等是子句。对于非子句的公式，可以用一个或多个和它等价的子句替换它，如可以用 代替公式 p → q ；对于公式 p ∨（ q ∧ r ），因为 p ∨（ q ∧ r ）⇔（ p ∨ q ）∧（ p ∨ r ），可以用两个子句 p ∨ q 和 p ∨ r 代替 p ∨（ q ∧ r ）；可以用两个子句 和 代替 ，因为 。

例1.5.11 用归结规则证明下面的推理。

如果小张守门或小李上场，则 A 队获胜；或者 A 队未获胜，或者 A 队成为联赛第一名； A 队没有成为联赛第一名。因此小张没有守门并且小李没有上场。

证明 设 p 表示“小张守门”， q 表示“小李上场”， r 表示“ A 队获胜”， s 表示“ A 队成为联赛第一名”。

前提： 。

结论： 。

前提中的 ，用两个子句 和 代替（ p ∨ q ）→ r ，前提中的 和 是子句。结论 可以用两个子句 和 代替。 kqJAZseVy/UPIUWNUR5T19yg6e3roudN5KxjfBWlCnlWXOARm1BsyNUrIA31Jxeh