1-8 推理理论

$T$ ，并使用一些公认的规则，得到另外的命题，形成结论，这种过程就是论证。

$A$ $C$ $A \to C$ $A \implies C$ $C$ $A$ $C$ $A$ 逻辑地推出。

$n$ 个前提的情况。

$H_1, H_2, \cdots, H_n, C$ 是命题公式，当且仅当

\begin{matrix} (A) & H_{1} \land H_{2} \land \dots \land H_{n} ⟹ C \end{matrix}

$C$ $H_1, H_2, \cdots, H_n$ 的有效结论。

判别有效结论的过程就是论证过程，论证方法千变万化，但基本方法是真值表法、直接证法和间接证法。

(1) 真值表法

$P_1, P_2, \cdots, P_n$ $H_1, H_2, \cdots, H_m$ $C$ $P_1, P_2, \cdots, P_n$ $H_1, H_2, \cdots, H_m$ $C$ $(A)$ 式是否成立。

$H_1, H_2, \cdots, H_m$ $T$ $C$ $T$ $(A)$ $C$ $F$ $H_1, H_2, \cdots, H_m$ $F$ $(A)$ 式也成立。

例题1

一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。

\begin{aligned} 解 & 设 各 命 题 变 元 为 \\ P ： 统 计 表 格 的 错 误 是 由 于 材 料 不 可 靠 。 \\ Q ： 统 计 表 格 的 错 误 是 由 于 计 算 有 错 误 。 \\ 本 例 可 译 为 ： Q 是 前 提 P \lor Q ， \neg P 的 有 效 结 论 ， 即 \end{aligned} \neg P \land (P \lor Q) ⟹ Q

我们列出真值表 1-8.1 如下：

表 1-8.1

$P$	$Q$	$P \lor Q$	$\neg P$
$T$	$T$	$T$	$F$
$T$	$F$	$T$	$F$
$F$	$T$	$T$	$T$
$F$	$F$	$F$	$T$

$P \lor Q$ $\neg P$ $T$ $Q$ $T$ 。故

(P \lor Q) \land (\neg P) ⟹ Q

成立。

$Q$ $F$ $P \lor Q$ $\neg P$ $F$ $(P \lor Q) \land (\neg P) \implies Q$ 成立。

例题2

如果张老师来了，这个问题可以得到解答，如果李老师来了，这个问题也可以得到解答，总之张老师或李老师来了，这个问题就可以得到解答。

\begin{aligned} 解 若 设 & P ： 张 老 师 来 了 。 \\ Q ： 李 老 师 来 了 。 \\ R ： 这 个 问 题 可 以 得 到 解 答 。 \end{aligned}

上述语句可以翻译成下述命题关系式

(P \to R) \land (Q \to R) \land (P \lor Q) ⟹ R

列出真值表 1-8.2 如下

表 1-8.2

$P$	$Q$	$R$	$P \to R$	$Q \to R$	$P \lor Q$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$	$F$	$T$
$T$	$F$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$T$	$T$
$F$	$T$	$T$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$F$	$T$
$F$	$F$	$T$	$T$	$T$	$F$
$F$	$F$	$F$	$T$	$T$	$F$

$P \to R$ $Q \to R$ $P \lor Q$ $T$ $R$ $T$ 。故

(P \to R) \land (Q \to R) \land (P \lor Q) ⟹ R

(2) 直接证法

直接证法就是由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，扮演得到有效的结论。

$P$ 规则，前提在推导过程中的任何时候都可以引入使用。

$T$ $S$ $S$ 可以引入推导之中。

现将常用的蕴含式和等价式列入表 1-8.3 和表 1-8.4 中。

表 1-8.3

编号	公式
$I_1$	$P \land Q \implies P$
$I_2$	$P \land Q \implies Q$
$I_3$	$P \implies P \lor Q$
$I_4$	$Q \implies P \lor Q$
$I_5$	$\neg P \implies P \to Q$
$I_6$	$Q \implies P \to Q$
$I_7$	$\neg (P \to Q) \implies P$
$I_8$	$\neg (P \to Q) \implies \neg Q$
$I_9$	$P, Q \implies P \land Q$
$I_{10}$	$\neg P, P \lor Q \implies Q$
$I_{11}$	$P, P \to Q \implies Q$
$I_{12}$	$\neg Q, P \to Q \implies \neg P$
$I_{13}$	$P \to Q, Q \to R \implies P \to R$
$I_{14}$	$P \lor Q, P \to R, Q \to R \implies R$
$I_{15}$	$A \to B \implies (A \lor C) \to (B \lor C)$
$I_{16}$	$A \to B \implies (A \land C) \to (B \land C)$

表 1-8.4

编号	公式
$E_1$	$\neg \neg P \iff P$
$E_2$	$P \land Q \iff Q \land P$
$E_3$	$P \lor Q \iff Q \lor P$
$E_4$	$(P \land Q) \land $ \iff P \land (Q \land R)$
$E_5$	$(P \lor Q) \lor R \iff P \lor (Q \lor R)$
$E_6$	$P \land (Q \lor R) \iff (P \land Q) \lor (P \land R)$
$E_7$	$P \lor (Q \land R) \iff (P \lor Q) \land (P \lor R)$
$E_8$	$\neg (P \land Q) \iff \neg P \lor \neg Q$
$E_9$	$\neg (P \lor Q) \iff \neg P \land \neg Q$
$E_{10}$	$P \lor Q \iff P$
$E_{11}$	$P \land P \iff P$
$E_{12}$	$R \lor (P \land \neg P) \iff R$
$E_{13}$	$R \land (P \lor \neg P) \iff R$
$E_{14}$	$R \lor (P \lor \neg P) \iff T$
$E_{15}$	$R \land (P \land \neg P) \iff F$
$E_{16}$	$P \to Q \iff \neg P \lor Q$
$E_{17}$	$\neg (P \to Q) \iff P \land \neg Q$
$E_{18}$	$P \to Q \iff \neg Q \to \neg P$
$E_{19}$	$P \to (Q \to R) \iff (P \land Q) \to R$
$E_{20}$	$P \leftrightarrow Q \iff (P \to Q) \land (Q \to P)$
$E_{21}$	$P \leftrightarrow Q \iff (P \land Q) \lor (\neg P \land \neg Q)$
$E_{22}$	$\neg (P \leftrightarrow Q) \iff P \leftrightarrow \neg Q$

例题1

$(P \lor Q) \land (P \to R) \land (Q \to S) \implies S \lor R$

\begin{aligned} 证法1 & (1) P \lor Q & P \\ (2) \neg P \to Q & T (1) E \\ (3) Q \to S & P \\ (4) \neg P \to S & T (2), (3) I \\ (5) \neg S \to P & T (4) E \\ (6) P \to R & P \\ (7) \neg S \to R & T (5), (6) I \\ (8) S \lor R & T (7) E \\ 证法2 & (1) P \to R & P \\ (2) P \lor Q \to R \lor Q & T (1) I \\ (3) Q \to S & P \\ (4) Q \lor R \to S \lor R & T (3) I \\ (5) P \lor Q \to S \lor R & T (2), (4) I \\ (6) P \lor Q & P \\ (7) S \lor R & T (5), (6) I \end{aligned}

例题2

$(W \lor R) \to V, V \to C \lor S, S \to U, \neg C \land \neg U \implies \neg W$

\begin{aligned} 证明 & (1) \neg C \land \neg U & P \\ (2) \neg U & T (1) I \\ (3) S \to U & P \\ (4) \neg S & T (2), (3) I \\ (5) \neg C & T (1) I \\ (6) \neg C \land \neg S & T (4), (5) I \\ (7) \neg (C \lor S) & T (6) E \\ (8) \neg (W \lor R) \to V & P \\ (9) V \to (C \lor S) & P \\ (10) (W \lor R) \to (C \lor S) & T (8), (9) I \\ (11) \neg (W \lor R) & T (7), (10) I \\ (12) \neg W \land \neg R & T (11) E \\ (13) \neg W & T (12) I \end{aligned}

(3) 间接证法

$H_1, H_2, \cdots, H_m$ $P_1, P_2, \cdots, P_m$ $P_1, P_2, \cdots, P_n$ $H_1 \land H_2 \land \cdots \land H_m$ $T$ $H_1, H_2, \cdots, H_m$ $P_1, P_2, \cdots, P_n$ $H_1 \land H_2 \land \cdots \land H_m$ $F$ $H_1, H_2, \cdots, H_m$ 是不相容的。

现在可把不相容的概念应用于命题公式的证明。

$H_1, H_2, \cdots, H_m$ $C$ $H_1 \land H_2 \land \cdots \land H_m \implies C$ $S \implies C$ $\neg C \to \neg S$ $C \lor \neg S$ $\neg C \land S$ $H_1 \land H_2 \land \cdots \land H_m \implies C$ $H_1, H_2, \cdots, H_m$ $\neg C$ 是不相容的。

例题3

$A \to B, \neg (B \lor C)$ $\neg A$

\begin{aligned} 证明 & (1) A \to B & P \\ (2) A & P (附 加 前 提) \\ (3) \neg (B \lor C) & P \\ (4) \neg B \land \neg C & T (3) E \\ (5) B & T (1), (2) I \\ (6) \neg B & T (4) I \\ (7) B \land \neg B (矛 盾) & T (5), (6) I \end{aligned}

例题4

$(P \lor Q) \land (P \to R) \land (Q \to S) \implies S \lor R$

\begin{aligned} 证明 & (1) \neg (S \lor R) & P (附 加 前 提) \\ (2) \neg S \land \neg R & T (1) E \\ (3) P \lor Q & P \\ (4) \neg P \to Q & T (3) E \\ (5) Q \to S & P \\ (6) \neg P \to S & T (4), (5) I \\ (7) \neg S \to P & T (6) E \\ (8) (\neg S \land \neg R) \to (P \land \neg R) & T (7) I \\ (9) P \land \neg R & T (2), (8) I \\ (10) P \to R & P \\ (11) \neg P \lor R & T (10) E \\ (12) \neg (P \land \neg R) & T (11) E \\ (13) (P \land \neg R) \land \neg (P \land \neg R) (矛 盾) & T (11) E \end{aligned}

$H_1 \land H_2 \land \cdots \land H_m \implies (R \to C)$ $H_1 \land H_2 \land \cdots \land H_m$ $S$ $S \implies (R \to C)$ $S \implies (\neg R \lor C)$ $S \to (\neg R \lor C)$ $S \to (\neg R \lor C) \iff \neg S \lor (\neg R \lor C) \iff (\neg S \lor \neg R) \lor C \iff \neg (S \land R) \lor C \iff (S \land R) \to C$ $R$ $(S \land R) \implies C$ $S \implies (R \to C)$ $(S \land R) \implies C$ $S \implies (R \to C)$ $CP$ 规则。

例题5

$A \to (B \to C), \neg D \lor A$ $B$ $D \to C$

\begin{aligned} 证明 & (1) D & P (附 加 前 提) \\ (2) \neg D \lor A & P \\ (3) A & T (1), (2) I \\ (4) A \to (B \to C) & P \\ (5) B \to C & T (3), (4) I \\ (6) B & P \\ (7) C & T (5), (6) I \\ (8) D \to C & C P \end{aligned}

例题6

设有下列情况，结论是否有效？

(a) 或者是天晴，或者是下雨。

(b) 如果是天晴，我去看电影。

结论：如果我在看书则天在下雨。

\begin{aligned} 解 若 设 & M ： 天 晴 。 & Q ： 下 雨 。 \\ S ： 我 看 电 影 。 & R ： 我 看 书 。 \\ 故 本 题 即 证 ： M \overset{―}{\lor} Q, M \to S, S \to \neg R ， 推 出 R \to Q \\ 因 为 (M \overset{―}{\lor} Q) ⟺ \neg (M \leftrightarrow Q) \\ (1) R & P (附 加 前 提) \\ (2) S \to \neg R & P \\ (3) R \to \neg S & T (2) E \\ (4) \neg S & T (1) (3) I \\ (5) M \to S & P \\ (6) \neg M & T (4), (5) I \\ (7) \neg (M \leftrightarrow Q) & P \\ (8) M \neg \neg Q & T (7) E \\ (9) (M \to \neg Q) \land (\neg Q \to M) & T (8) E \\ (10) \neg Q \to M & T (9) I \\ (11) \neg M \to Q & T (10) E \\ (12) Q & T (6), (11) I \\ (13) R \to Q & C P \end{aligned}

$P$	$Q$	$R$	$P \to R$	$Q \to R$	$P \lor Q$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$	$F$	$T$
$T$	$F$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$T$	$T$
$F$	$T$	$T$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$F$	$T$
$F$	$F$	$T$	$T$	$T$	$F$
$F$	$F$	$F$	$T$	$T$	$F$

$P$	$Q$	$R$	$P \to R$	$Q \to R$	$P \lor Q$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$	$F$	$T$
$T$	$F$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$T$	$T$
$F$	$T$	$T$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$F$	$T$
$F$	$F$	$T$	$T$	$T$	$F$
$F$	$F$	$F$	$T$	$T$	$F$

$P$	$Q$	$R$	$P \to R$	$Q \to R$	$P \lor Q$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$	$F$	$T$
$T$	$F$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$T$	$T$
$F$	$T$	$T$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$F$	$T$
$F$	$F$	$T$	$T$	$T$	$F$
$F$	$F$	$F$	$T$	$T$	$F$