离散数学 - 推理规则

---

---

为了从我们已知真值的语句中推导出新的语句，使用**推理规则**。

推理规则的用途是什么？

数学逻辑常用于逻辑证明。证明是有效的论证，用于确定数学语句的真值。

一个论证是一系列语句。最后一个语句是结论，所有其前面的语句称为前提（或假设）。符号“$\therefore$”（读作因此）放在结论之前。一个有效的论证是指结论遵循前提真值的论证。

推理规则为从我们已有的语句构建有效论证提供了模板或指南。

推理规则表

加法

如果 P 是一个前提，我们可以使用加法规则推导出 $ P \lor Q $。

$$\begin{matrix} P \\ \hline \therefore P \lor Q \end{matrix}$$

例子

令 P 为命题，“他学习非常努力”为真

因此 - “要么他学习非常努力，要么他是一个非常差的学生。” 这里 Q 是命题“他是一个非常差的学生”。

合取

如果 P 和 Q 是两个前提，我们可以使用合取规则推导出 $ P \land Q $。

$$\begin{matrix} P \\ Q \\ \hline \therefore P \land Q \end{matrix}$$

例子

令 P - “他学习非常努力”

令 Q - “他是班上最好的男孩”

因此 - “他学习非常努力，并且他是班上最好的男孩”

简化

如果 $P \land Q$ 是一个前提，我们可以使用简化规则推导出 P。

$$\begin{matrix} P \land Q\\ \hline \therefore P \end{matrix}$$

例子

"他学习非常努力，并且他是班上最好的男孩"，$P \land Q$

因此 - “他学习非常努力”

肯定前件

如果 P 和 $P \rightarrow Q$ 是两个前提，我们可以使用肯定前件推导出 Q。

$$\begin{matrix} P \rightarrow Q \\ P \\ \hline \therefore Q \end{matrix}$$

例子

"如果你有密码，那么你可以登录 Facebook"，$P \rightarrow Q$

"你有密码"，P

因此 - “你可以登录 Facebook”

否定后件

如果 $P \rightarrow Q$ 和 $\lnot Q$ 是两个前提，我们可以使用否定后件推导出 $\lnot P$。

$$\begin{matrix} P \rightarrow Q \\ \lnot Q \\ \hline \therefore \lnot P \end{matrix}$$

例子

"如果你有密码，那么你可以登录 Facebook"，$P \rightarrow Q$

"你无法登录 Facebook"，$\lnot Q$

因此 - “你没有密码”

析取三段论

如果 $\lnot P$ 和 $P \lor Q$ 是两个前提，我们可以使用析取三段论推导出 Q。

$$\begin{matrix} \lnot P \\ P \lor Q \\ \hline \therefore Q \end{matrix}$$

例子

"冰淇淋不是香草味的"，$\lnot P$

"冰淇淋要么是香草味的，要么是巧克力味的"，$P \lor Q$

因此 - “冰淇淋是巧克力味的”

假言三段论

如果 $P \rightarrow Q$ 和 $Q \rightarrow R$ 是两个前提，我们可以使用假言三段论推导出 $P \rightarrow R$

$$\begin{matrix} P \rightarrow Q \\ Q \rightarrow R \\ \hline \therefore P \rightarrow R \end{matrix}$$

例子

"如果下雨，我就不去上学"，$P \rightarrow Q$

"如果我不去上学，我就不用做作业"，$Q \rightarrow R$

因此 - “如果下雨，我就不用做作业”

构造性二难推理

如果 $( P \rightarrow Q ) \land (R \rightarrow S)$ 和 $P \lor R$ 是两个前提，我们可以使用构造性二难推理推导出 $Q \lor S$。

$$\begin{matrix} ( P \rightarrow Q ) \land (R \rightarrow S) \\ P \lor R \\ \hline \therefore Q \lor S \end{matrix}$$

例子

“如果下雨，我会请假”，$( P \rightarrow Q )$

“如果外面很热，我会去冲凉”，$(R \rightarrow S)$

“要么下雨，要么外面很热”，$P \lor R$

因此 - “我会请假，或者我会去冲凉”

破坏性二难推理

如果 $(P \rightarrow Q) \land (R \rightarrow S)$ 和 $ \lnot Q \lor \lnot S $ 是两个前提，我们可以使用破坏性二难推理推导出 $\lnot P \lor \lnot R$。

$$\begin{matrix} (P \rightarrow Q) \land (R \rightarrow S) \\ \lnot Q \lor \lnot S \\ \hline \therefore \lnot P \lor \lnot R \end{matrix}$$

例子

“如果下雨，我会请假”，$(P \rightarrow Q )$

“如果外面很热，我会去冲凉”，$(R \rightarrow S)$

“要么我不会请假，要么我不会去冲凉”，$\lnot Q \lor \lnot S$

因此 - “要么不下雨，要么外面不热”