1.6. 推理规则

所谓 论证(argument)，是指一连串的命题并以结论为最后的命题。所谓有效性(valid)，是指结论或论证的最后一个命题必须根据论证过程前面的命题或前提(premise)的真实性推出。也就是说，一个论证是有效的当且仅当不可能出现所有前提为真而结论为假的情况。

命题逻辑的有效论证

$$\begin{array}{ll} & p \to q \\ & p \\ \hline \therefore & q \end{array}$$

语句$((p \to q) \land p) \to q$是一个永真式。当$p \to q$和$p$都为真时，我们知道$q$肯定是真。 我们说语句的这种论证形式是有效的。

定义1

命题逻辑中的一个论证是一连串的命题。除了论证中左后一个命题外都叫做前提，最后那个命题叫做结论。一个论证是有效的，如果它的所有前提为真，蕴含着结论为真。
命题逻辑中的[论证形式]是一连串设计命题变元的复合命题。无论用什么特定命题来替换其中的命题变元，如果前提均真时结论为真，则称该论证形式是有效的。

从有效论证形式的定义可知，当$(p_1 \land p_2 \land \dots\land p_n) \to q$是永真式时，带有前提$p_1 , p_2 , \dots , p_n$以及结论$q$的论证形式是有效的。

证明命题逻辑中论证有效性的关键是要证明它的论证形式的有效性。

命题逻辑的推理规则

我们可以先建立一些相对简单的论证形式（称为推理规则）的有效性。这些瑰丽规则可以作为基本构件用来构造更多复杂的有效论证形式。

永真式$((p \to q) \land p) \to q$是称为假言推理（modus ponens）或分离规则（law of detachment）的推理规则的基础。这个永真式导出了下面的有效论证形式，

$$\begin{array}{ll} & p \to q \\ & p \\ \hline \therefore & q \end{array}$$

例2

确定如下给定的论证是否有效，并且确定有论证的有效性是否可以推出它的结论一定为真。

$$\text{如果}\sqrt{2} > \frac{3}{2}\text{，那么}(\sqrt{2})^2 > \Big(\frac{3}{2}\Big)^2. \text{我们知道}\sqrt{2} > \frac{3}{2}\text{，因此}(\sqrt{2})^2 = 2 > \Big(\frac{3}{2}\Big)^2 = \frac{9}{4}$$

解 令$p$为命题$\displaystyle \sqrt{2} > \frac{3}{2}$，令$q$为命题$\displaystyle (\sqrt{2})^2 > \Big(\frac{3}{2}\Big)^2$。论证的前提为$p \to q$和$p$，而$q$是结论。这个论证是有效的，因为可以通过假言推理这个有效论证形式来构造。然而其中的前提$p$为假，所以我们不能得出结论为真。

这里要注意论证有效和结论为真，不能混为一谈。论证有效，是保证结论为真的一个前提条件，只有论证有效且所有前提为真才能推出结论为真。

推理规则	永真式	名称
$\begin{array}{ll} &p \\ &p \to q \\ \hline \therefore & q \end{array}$	$(p\land (p \to q) \to q)$	假言推理
$\begin{array}{ll} &\lnot q \\ &p \to q \\ \hline \therefore & \lnot p \end{array}$	$(\lnot q\land (p \to q) \to \lnot p)$	取拒式
$\begin{array}{ll} &p \to q \\ &q \to r \\ \hline \therefore & p \to r \end{array}$	$(p \to q)\land (q \to r) \to (p \to r)$	假言三段论
$\begin{array}{ll} &p \lor q \\ &\lnot p \\ \hline \therefore & q \end{array}$	$((p\lor q)\land\lnot p) \to q$	析取三段论
$\begin{array}{ll} &p \\ \hline \therefore & p \lor q \end{array}$	$p \to (p \lor q)$	附加率
$\begin{array}{ll} &p\land q \\ \hline \therefore & p\end{array}$	$p \land q \to p$	化简率
$\begin{array}{ll} &p \\ &q \\ \hline \therefore & p \land q\end{array}$	$((p) \land (q)) \to (p \land q)$	合取律
$\begin{array}{ll} &p\lor q \\ &\lnot p \lor r \\ \hline \therefore & q \land r\end{array}$	$((p\lor q)\land(\lnot p \lor r)) \to (q \lor r)$	消解律

使用推理规则建立论证

例6

证明前提“今天下午不是晴天并且比昨天冷”，“只有今天下午是晴天，我们才去游泳”，“如果我们不去游泳，则我们将乘独木舟游览”，以及“我们乘独木舟游览，则我们将在黄昏前回家”，推导出结论“我们将在黄昏前回家”。

• $p$: 今天下午是晴天
• $q$：今天比昨天冷
• $r$：我们将去游泳
• $s$：我们将乘独木舟游览
• $t$： 我们将在黄昏前回家

那么这些前提可以表示为$\lnot p \land q, r \to p, \lnot r \to s , s \to t$

question

只有今天下午是晴天，我们才去游泳，晴天不一定去游泳，但是去游泳了一定是晴天所以表示成$r \to p$，而不是$p \to r$

$$\begin{array}{llll} 1.& \lnot p \land q && \text{前提引入} \\ 2.& \lnot p && \text{化简率} \\ 3.& r \to p && \text{前提引入} \\ 4.& \lnot r && \text{取拒式} \\ 5.& \lnot r \to s && \text{前提引入} \\ 6.& s && \text{假言推理} \\ 7.& s \to t && \text{前提引入} \\ 8.& t && \text{假言推理} \\ \end{array}$$ $$\begin{array}{llll} &\lnot p \land q \\ \hline \therefore & \lnot p \\ & r \to p \\ \hline \therefore & \lnot r \\ & \lnot r \to s \\ \hline \therefore & s \\ & s \to t \\ \hline \therefore & t \\ \end{array}$$

---

消解律

消解律永真式$((p\lor q)\land(\lnot p\lor r)) \to (q\lor r)$

证明假设$(p \land q)\lor r$和$r \to s$蕴含结论$p\lor s$

$$\begin{array}{lll} & ((p \land q)\lor r)\land(r \to s) \\ = & ((p\lor r)\land(q\lor r))\land (\lnot r \lor s) & \text{分配率和条件命题逻辑等价式}\\ = & (q\lor r)\land((r\lor p) \land (\lnot r \lor s)) & \text{交换律和结合律} \\ = & (q \lor r) \land (p \lor s) & \text{消解律} \end{array}$$

question

为什么证明的结论中多了$(q \lor r)$

谬误

谬误看上去像是推理规则，但是它们是基于可满足式而不是永真式。

DEFINITION 肯定结论的谬误

命题$((p \to q)\land q) \to p$不是永真式，因为当$p$为假而$q$为真时，它为假。这类不正确的推理称为肯定结论的谬误（fallacy of affirming the conclusion）

例10
如果你做过本书的每一道练习，则你就学习离散数学。你学过离散数学。因此，你做过本书的每一道练习

• $p$：你做过本书的每一道练习
• $q$：你学过离散数学

命题可表述为：$((p \to q) \land q) \to p$，事实上你可以通过其他途径学习离散数学，而不仅是本书。

DEFINITION 否定假设的谬误

命题$((p \to q)\land \lnot p) \to \lnot p$不是永真式，因为当$p$为假而$q$为真时，它为假。这类不正确的推理称为否定假设的谬误（fallacy of denying the hypothesis）

例11
设$p$和$q$同例10一样。如果你没有做过本书里的每一道习题，你就没有学过离散数学。
$((p \to q) \land\lnot q) \to \lnot p$

量化命题的推理规则

DEFINITION 全称实例

全称实例（universal instantiation）是从给定前提$\forall x P(x)$得出$P(c)$为真的推理规则，其中$c$是论域里的一个特定的成员。

从命题“所有女人都是聪明的”得出“Lisa是聪明的”

DEFINITION 全称引入

全称引入（universal generalization）是从对论域里所有元素$c$都有$P(c)$为真的前提推出$\forall x P(x)$为真的推理规则。

我们可以通过从论域中的任意取一个元素$c$并证明$P(c)$为真来证明$\forall x P(x)$为真时，这就使用全称引入规则。元素$c$必须是论域里的一个任意的元素，而不是特定的元素。

DEFINITION 存在实例

存在实例（existential instantiation）是允许从“如果我们知道$\exist xP(x)$为真，得出在论域中存在一个元素$c$是的$P(c)$为真”的推理规则。

这里不能选择一个任意的$c$，而必须是使得$P(c)$为真的那个$c$

DEFINITION 存在引入

存在引入（existential geralization）是用来从“一直有一特定的$c$使$P(c)$为真时得出$\exist x P(x)$为真”的推理规则。

即如果我们知道论域里一个元素$c$使得$P(c)$为真，则我们就知道$\exist x P(x)$为真。

推理规则	名称
$\begin{array}{ll} & \forall xP(x) \\ \hline \therefore & P(c) \end{array}$	全称实例
$\begin{array}{ll} & P(c),\text{任意}c \\ \hline \therefore & \forall xP(x) \end{array}$	全称引入
$\begin{array}{ll} & \exist xP(x) \\ \hline \therefore & P(c)\text{，对某个元素c} \end{array}$	存在实例
$\begin{array}{ll} & P(c)\text{，对某个元素c} \\ \hline \therefore & \exist xP(x) \end{array}$	存在引入

例12 证明前提“在这个离散数学班上的每个人都学过一门计算机课程”和“Marla是这个班上的一名学生”蕴含结论“Marla学过一名计算机课程”。

备注

设$D(x)$表示“$x$在这个离散数学班上”，并且$C(x)$表示“$x$学过一门计算机课程”，则前提是$\forall x(D(x) \to C(x))$和$D(Marla)$，结论是$C(Marla)$

$$\begin{array}{lll} 1.& \forall x(D(x) \to C(x)) & \text{前提引入} \\ 2.& D(Marla) \to C(Marla)) & \text{前提引入} \\ 3.&D(Marla) & \text{前提引入} \\ 4.& C(Marla) & \text{假言推理}(2)\land(3) \end{array}$$

命题和量化命题推理规则的组合使用

由于全称实例和假言推理在一起使用时如此广泛，所以这种规则的组合有时称为全称假言推理（universal modus ponens）。这个规则告诉我们：如果$\forall x (P(x) \to Q(x))$为真，并且如果$P(a)$在对全称量词论域中的一个特定元素$a$为真，那么$Q(a)$也肯定为真。

$$\begin{array}{ll} & \forall x (P(x) \to Q(x)) \\ & P(a), \text{其中} a \text{是论域中的一个特定的元素} \\ \hline \therefore & Q(a) \end{array}$$

另外一个重要的命题逻辑推理规则和量化命题推理规则的组合是全称取拒式（universal modus tollens）。全称取拒式将全称和取拒式组合在一起

$$\begin{array}{ll} & \forall x (P(x) \to Q(x)) \\ & \lnot P(a), \text{其中} a \text{是论域中的一个特定的元素} \\ \hline \therefore & \lnot Q(a) \end{array}$$