本文及其系列文章用于离散数学（1）科目的期末考试复习

推理形式

我们将用自然语句描述的推理关系引入符号，抽象化并以条件式表现出来，就得到了一种推理形式。

比如：

如果$P$，则$Q$。非$Q$，所以非$P$

形式化之后就得到了 ：

$((P\rightarrow Q)\land\neg Q)\rightarrow \neg P$

当然，也有一些推理形式是错误的，比如$((P\rightarrow Q)\land\neg P)\rightarrow \neg Q$。这种推理形式我们不太关心。我们关心的是那些前提真则结论必真的推理形式，我们叫它正确的推理形式。

即，给定两个命题公式$A,B$，如果$A$取值为真，那么$B$取值也必为真，那么说$A\rightarrow B$就是一个正确的推理形式。这时候，我们称$A$重言蕴含$B$，或者称$B$为$A$的逻辑推论，并用符号$A\Rightarrow B$表示。

$\Rightarrow$可以理解为我们之前在初高中常见的“推导出”的符号。

基本的推理公式

常用公式

  • $P\land(P\rightarrow Q)\Rightarrow Q$⭐️⭐️

假言推理，或者说叫分离规则，最常用的公式

  • $(P\rightarrow Q)\land(Q\rightarrow R) \Rightarrow P\rightarrow R$⭐️⭐️

三段论

  • $P\land Q\Rightarrow P$⭐️

最基础的公式，常用于分离合取的不同公式

  • $P\Rightarrow P\lor Q$⭐️

常用于增加条件，方便三段论规范性

其余常见公式

这里的公式都可以由常用公式推导出。

  • $\neg(P\rightarrow Q)\Rightarrow P$

  • $\neg(P\rightarrow Q)\Rightarrow \neg Q$

  • $\neg P\Rightarrow P\rightarrow Q$

  • $Q\Rightarrow P\rightarrow Q$

  • $\neg P\land(P \lor Q)\Rightarrow Q$

  • $\neg Q\land(P\rightarrow Q)\Rightarrow\neg P$

  • $(P\leftrightarrow Q)\land(Q\leftrightarrow R)\Rightarrow P\leftrightarrow R$

  • $(P\rightarrow R)\land(Q\rightarrow R)\land(P\lor Q)\Rightarrow R$

  • $(P\rightarrow Q)\land(R\rightarrow S)\land(P\lor Q)\Rightarrow Q\lor S$

  • $(P\rightarrow Q)\land(R\rightarrow S)\land(\neg Q\lor \neg S)\Rightarrow \neg P\lor\neg R$

  • $(Q\rightarrow R)\Rightarrow((P\lor Q)\rightarrow(P\lor R))$

  • $(Q\rightarrow R)\Rightarrow((P\rightarrow Q)\rightarrow(P\rightarrow R))$

证明推理公式的一般方法

如果想证明$A\Rightarrow B$，一般方法有两种.一种就是证明$A\rightarrow B$为重言式，另外一种是证明$A\land\neg B$是矛盾式。当然，还有一种更加直观的解释法，直接对公式本身进行解释分析（前提如果为真，如何如何），不过如果考试不要求则一般不用。

另外，如果我们于考场上做题的话，我们一般倾向于分离合取式，然后对于析取式我们把它转化为蕴含式。例如，我们更喜欢看到$\neg A\rightarrow B$而不是$A\lor B$。因为蕴含式可以更加符合我们直观上推导的形式，也更加方便实用假言推理和三段论。事实上，我们做这样类型的题目基本上都是通过前提引入、假言推理、置换、三段论来做的。

推理演算

推理演算规则

一般而言，如果用形式化语言表述的话我们有如下几条规则：

  1. 前提引入规则：在推理过程中，可以随时引入前提
  2. 结论引用规则：在推理过程中所得到的中间结论，可以用作后续推理的前提
  3. 代入规则：在推理的过程中，对重言式中的命题变项可以使用代入规则。
  4. 置换规则：在推理过程中，命题公式的任何部分公式都可以用与之等值的命题公式来替换
  5. 分离规则（假言推理）：如果已知命题公式$A\rightarrow B$和$A$，则有命题公式$B$

例子

推理演算一般作为考试的一个重点，也是后续学习内容的重要基石。做题技巧比知识点本身更加重要。

例1：证明$(P\rightarrow (Q\rightarrow S))\land(\neg R\lor P)\land Q\Rightarrow R\rightarrow S$

证明：$\\ (1) \neg R\lor P (前提引入)\\ (2)\neg R\rightarrow P (1置换)\\ (3)R(附加前提引入)\\(4)P(2,3分离)\\(5)P\rightarrow (Q\rightarrow S)(前提引入)\\(6)Q\rightarrow S(4,5分离)\\(7)Q(前提引入)\\(8)S(6,7分离)\\(9)R\rightarrow S(条件证明规则)$

上面是一个比较典型的直接推导证明$A\rightarrow B$为重言式的过程。下面是一个尝试证明$A\land\neg B$是矛盾式的题目解法。

例2:证明$(\neg (P\rightarrow Q)\rightarrow \neg (R\lor S))\land((Q\rightarrow P)\lor\neg R)\land R\Rightarrow (P\leftrightarrow Q)$

证明:$\\(1)\neg (P\leftrightarrow Q) (附加前提引入，即要证否的公式引入)\\(2)\neg((P\rightarrow Q)\land(Q\rightarrow P))(1置换)\\(3)\neg(P\rightarrow Q)\lor\neg(Q\rightarrow P)(2置换)\\(4)(Q\rightarrow P)\rightarrow\neg(P\rightarrow Q) (3置换)\\(5)\neg(P\rightarrow Q)\rightarrow\neg(R\lor S)(前提引入)\\(6)(Q\rightarrow P)\rightarrow \neg(R\lor S)(4,5三段论)\\(7)(Q\rightarrow P)\lor\neg R(前提引入)\\(8)R\rightarrow(Q\rightarrow P)(7置换)\\(9)R\rightarrow \neg(R\lor S)(6,8三段论)\\(10)R(前提引入)\\(11)\neg(R\lor S)(9,10分离)\\(12)\neg R\land\neg S(11置换)\\(13)\neg R(12推导)\\(14)R\land\neg R(10,13推导)\\(15)矛盾(14推导)$

归结推理法

归结推理法的精髓就是,如果想要证明$A\Rightarrow B$，那么可以尝试证明$A\land\neg B$是矛盾式。

一般而言，归结推理法有以下几个大致不变的步骤。

  1. 建立子句集$S$。将$A\land\neg B$化成合取范式，然后把所有的子句放进$S$，构成子句集合。
  2. 对$S$做归结。归结的意思通过例子来展现比较直观：如果$S$中有两个子句$A=P\lor X,B=\neg P\lor Y$，那么对$A,B$做归结，得到归结式$X\lor Y$，并将这个归结式放入$S$中。
  3. 重复2，直至出现了矛盾式$\Box$。

给出例子可能更加好理解也更加直观。

例：证明$((P\rightarrow Q)\land(Q\rightarrow R))\Rightarrow (P\rightarrow R)$

证明：$\\$子句集为$S=\{\neg P\lor Q,\neg Q\lor R,P,\neg R\}\\$归结过程为：$\\(1)\neg P\lor Q\\(2)\neg Q\lor R\\(3)\neg P\lor R(1,2归结)\\(4)P\\(5)R(3,4归结)\\(6)\neg R\\(7)\Box(5,6归结)$