一、推理

1. 推理的形式结构

• 记前提为 $A_1, A_2, \cdots, A_k$，结论为 $B$，推理的形式结构即为：

  $$ A_1 \wedge A_2 \wedge \cdots \wedge A_k \to B $$

  • 当 $A \to B$ 为永真式，记为 $A \Rightarrow B$，称这个推理是正确的（有效的），称 $B$ 为 $A$ 的有效结论。

2. 重要的推理定律

下面的证明方式都是证明永真式，即看真值表。

• 附加律：$A \Rightarrow A \vee B$

• 化简律：$A \wedge B \Rightarrow A$，$A \wedge B \Rightarrow B$

• 假言推理：$(A \rightarrow B) \wedge A \Rightarrow B$

  • 就是「小三段论」。

• 拒取式：$(A \rightarrow B) \wedge \neg B \Rightarrow \neg A$

  • 一种反证法。「你没变强，说明你没充钱」。

• 析取三段论：$(A \vee B) \wedge \neg A \Rightarrow B$，$(A \vee B) \wedge \neg B \Rightarrow A$

  • A 与 B 起码有一个是真的，里面又有一个是假的，剩下一个只能是真的。

• 假言三段论：$(A \rightarrow B) \wedge (B \rightarrow C) \Rightarrow A \rightarrow C$

• 等价三段论：$(A \leftrightarrow B) \wedge (B \leftrightarrow C) \Rightarrow A \leftrightarrow C$

• 消解律：$(A \vee B) \wedge (\neg A \vee C) \Rightarrow B \vee C$

  证明

  • A 与 B 起码有一个是真的；非 A 与 C 起码有一个是真的。
  • A=0 时 B 一定为真；A=1 时 C 一定为真；A 要么是 0，要么是 1（排中律）。
  • 所以 B 和 C 起码有一个是真的。

  • 消解律非常重要，其可以推出其他很多式子。
    • 代入 $B=C$，有 $(A \vee B) \wedge (\neg A \vee B) \Rightarrow B$。
    • 代入 $C = 0$，有 $(A \vee B) \wedge \neg A \Rightarrow B$，

• 构造性两难：$(A \rightarrow B) \wedge (C \rightarrow D) \wedge (A \vee C) \Rightarrow B \vee D$

3. 判断推理是否正确

方法一：求解推理的形式结构是一个永真式。

方法二：从前提经过推理定律推演出结论。

例一

比如有这样一个推理，前提为：$p\to(q \to r), p, q$，结论为 $r$，请证明推理是正确的。

方法一：证明 $(p\to(q \to r)) \wedge p \wedge q \to r$ 是一个永真式。

方法二：通过推理定律进行推演

例二

前提： $p \rightarrow q \vee r, \ \ \neg s \rightarrow \neg q, \ \ p \wedge \neg s$ 三个永真式。

结论：$r$

证明：

① $p \wedge \neg s$ 引入前提

② $p$ ①化简

③ $\neg s$ ①化简

④ $\neg s \rightarrow \neg q$ 引入前提

⑤ $\neg q$ ④③假言推理

⑥ $p \rightarrow q \vee r$ 引入前提

⑦ $q \vee r$ ⑥②假言推理

⑧ $r$ ⑦⑤ 析取三段论