推理理论

推理的定义

定义3.1 设 $A_{1}, A_{2}, \dots, A_{k}$ 和 $B$ 为命题公式。若对于每一组赋值， $A_{1} \land A_{2} \land \dots \land A_{k}$ 为假，或当 $A_{1} \land A_{2} \land \dots \land A_{k}$ 为真时 $B$ 也为真，则称由前提 $A_{1}, A_{2}, \dots, A_{k}$ 推出结论 $B$ 的推理是有效的或正确的，并称 $B$ 是有效结论。

说明

由前提 $A_{1}, A_{2}, \dots, A_{k}$ 推出结论 $B$ 的推理是否正确，与诸前提的排列顺序无关。
设 $A_{1}, A_{2}, \dots, A_{k}, B$ 中共出现 $n$ 个命题变项，对于任一组赋值，前提和结论的取值情况有以下 4 种：
- (1) $A_{1} \land A_{2} \land \dots \land A_{k}$ 为 $0$ ， $B$ 为 $0$
- (2) $A_{1} \land A_{2} \land \dots \land A_{k}$ 为 $0$ ， $B$ 为 $1$
- (3) $A_{1} \land A_{2} \land \dots \land A_{k}$ 为 $1$ ， $B$ 为 $0$
- (4) $A_{1} \land A_{2} \land \dots \land A_{k}$ 为 $1$ ， $B$ 为 $1$ 其中 (3) 出现时推理不正确。

定理3.1 由命题公式 $A_{1}, A_{2}, \dots, A_{k}$ 推出 $B$ 的推理正确当且仅当 $(A_{1} \land A_{2} \land \dots \land A_{k}) \to B$ 为重言式。

推理的形式结构

${A_{1}, A_{2}, \dots, A_{k}} ⊢ B$ 若推理正确，记为 $A_{1}, A_{2}, \dots, A_{k} ⊢ B$ 。
$A_{1} \land A_{2} \land \dots \land A_{k} \to B$ 若推理正确，记为 $A_{1} \land A_{2} \land \dots \land A_{k} \Rightarrow B$ 。
前提： $A_{1}, A_{2}, \dots, A_{k}$ 结论： $B$

推理方法

判断推理是否正确的方法：

真值表法
等值演算法
主析取范式法
推理定律法

推理定律

附加律 $A \Rightarrow (A \lor B)$
化简律 $(A \land B) \Rightarrow A$ , $(A \land B) \Rightarrow B$
假言推理 $(A \to B) \land A \Rightarrow B$
拒取式 $(A \to B) \land \neg B \Rightarrow \neg A$
析取三段论 $(A \lor B) \land \neg A \Rightarrow B$
假言三段论 $(A \to B) \land (B \to C) \Rightarrow (A \to C)$
等价三段论 $(A \leftrightarrow B) \land (B \leftrightarrow C) \Rightarrow (A \leftrightarrow C)$
构造性二难
- $(A \to B) \land (C \to D) \land (A \lor C) \Rightarrow (B \lor D)$
- $(A \to B) \land (\neg A \to B) \Rightarrow B$ （特殊形式）
破坏性二难 $(A \to B) \land (C \to D) \land (\neg B \lor \neg D) \Rightarrow (\neg A \lor \neg C)$

每个等值式可产生两个推理定律。如由 $A \Leftrightarrow \neg\neg A$ 可产生 $A \Rightarrow \neg\neg A$ 和 $\neg\neg A \Rightarrow A$ 。

构造证明法

自然推理系统 P

定义3.2 一个形式系统 $I$ 由下面四个部分组成：

非空的字母表，记作 $A (I)$
$A (I)$ 中符号构造的合式公式集，记作 $E (I)$
$E (I)$ 中一些特殊的公式组成的公理集，记作 $A x (I)$
推理规则集，记作 $R (I)$

记 $I = ⟨ A (I), E (I), A x (I), R (I)⟩$ ，其中 $⟨ A (I), E (I)⟩$ 是 $I$ 的形式语言系统， $⟨ A x (I), R (I)⟩$ 是 $I$ 的形式演算系统。

自然推理系统：无公理集，即 $A x (I) = \emptyset$ 。 公理推理系统：有公理集，推出的结论是系统中的重言式，称作定理。

定义3.3 自然推理系统 P 定义如下：

字母表
- 命题变项符号：p, q, r, s, …
- 联结词符号： $\neg, \land, \lor, \to, \leftrightarrow$
- 括号与逗号：(, ), ，
合式公式（同定义1.6）
推理规则
- (1) 前提引入规则
- (2) 结论引入规则
- (3) 置换规则

证明的定义

设前提 $A_{1}, A_{2}, \dots, A_{k}$ ，结论 $B$ 及公式序列 $C_{1}, C_{2}, \dots, C_{l}$ 。如果每一个 $C_{i}$ （ $1 \leq i \leq l$ ）是某个 $A_{j}$ ，或者可由序列中前面的公式应用推理规则得到，并且 $C_{l} = B$ ，则称这个公式序列是由 $A_{1}, A_{2}, \dots, A_{k}$ 推出 $B$ 的证明。

直接证明法

按推理规则逐步推导出结论。

例：构造下面推理的证明：若明天是星期一或星期三，我明天就有课。若我明天有课，今天必备课。我今天没备课。所以，明天不是星期一，也不是星期三。

解：

设命题并符号化：p: 明天是星期一，q: 明天是星期三，r: 我明天有课，s: 我今天备课
前提： $(p \lor q) \to r, r \to s, \neg s$ ，结论： $\neg p \land \neg q$
证明：
- ① $r \to s$ 前提引入
- ② $\neg s$ 前提引入
- ③ $\neg r$ ①②拒取式
- ④ $(p \lor q) \to r$ 前提引入
- ⑤ $\neg (p \lor q)$ ③④拒取式
- ⑥ $\neg p \land \neg q$ ⑤置换