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

基本的推理公式

  • $(\forall x)P(x)\lor(\forall x)Q(x)\Rightarrow(\forall x)(P(x)\lor Q(x))$⭐️

  • $(\exists x)(P(x)\land Q(x))\Rightarrow (\exists x)P(x)\land (\exists x)Q(x)$⭐️

  • $(\forall x)(P(x)\rightarrow Q(x))\Rightarrow (\forall x)P(x)\rightarrow (\forall x)Q(x)$

  • $(\forall x)(P(x)\rightarrow Q(x))\Rightarrow (\exists x)P(x)\rightarrow (\exists x)Q(x)$

  • $(\forall x)(P(x)\leftrightarrow Q(x))\Rightarrow (\forall x)P(x)\leftrightarrow (\forall x)Q(x)$

  • $(\forall x)(P(x)\leftrightarrow Q(x))\Rightarrow (\exists x)P(x)\leftrightarrow (\exists x)Q(x)$

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

  • $(\forall x)(P(x)\rightarrow Q(x))\land P(a)\Rightarrow Q(a)$⭐

  • $(\forall x)(\forall y)P(x,y)\Rightarrow (\exists x)(\forall y)P(x,y)$

  • $(\exists x)(\forall y)P(x,y)\Rightarrow (\forall y)(\exists x)P(x,y)$

这些推理公式的逆一般是不成立的，所以记住和理解顺序很重要。

推理演算

注意，本节按照老师上课讲义的符号和规则来描述，不同的规定和不同的讲述方式可能导致本节内容在一定程度上不是普适性的。本节适配内容为T大软件学院离散数学（1）的课程及考试内容。

全称量词消去规则（$\forall E$规则）

在谓词逻辑验算中，可做替换

$$\frac{(\forall x)P(x)}{P(t)}$$

其中，$t$是任意项，可以是常项、变项或者是函数项

替换的时候要注意“变元捕获”，即不能够让$P$中的约束变元的符号带入替换。

可以这样理解：如果$(\forall x)P(x)$成立，也即对于任何的$x$，$P(x)$都成立，那么带入任意的项$t$，$P(t)$成立。

全称量词引入规则（$\forall I$规则）

在谓词逻辑验算中，可做替换

$$\frac{P(x)}{(\forall x)P(x)}$$

其中，$x$不在任何前提中以自由变元的形式出现。

可以这样理解：如果对于某个$P(x)$，它对于任意的、不受约束的任何$x$都成立，那么$(\forall x)P(x)$成立。

存在量词引入规则（$\exists I$规则）

在谓词逻辑验算中，可做替换

$$\frac{P(t)}{(\exists x)P(x)}$$

其中，$t$是任意项，可以是常项、变项或者是函数项。另外仍需注意变元捕获。

可以这样理解：我们已经知道了$P(t)$成立，那么说明存在一个$t$能够让$P(t)$成立，也即$(\exists x)P(x)$成立

存在量词消去规则（$\exists E$规则）

在谓词逻辑验算中，可做替换

$$\frac{(\exists x)P(x),[P(c)]\vdash Q}{Q}$$

其中，$c$是不能够在任何前提中出现的新符号。第二个前提表示由假设$P(c)$通过一段子证明推出$Q$。

可以这样理解：若知道存在$x$满足$P$，但不知道具体哪个个体，我们可以临时给这个个体起个名字$c$，假设$P(c)$成立，如果据此能推出一个不依赖于具体$c$的结论$Q$，那么$Q$就可以从$(\exists x)P(x)$得到。

示例

例1：证明$(\exist x)(P(x)\land Q(x))\Rightarrow (\exists)P(x)$

证明：$\\(1)(\exists x)(P(x)\land Q(x)) (前提)\\(2)|P(a)\land Q(a)(引入假设)\\(3)|P(a)(\land,2)\\(4)|(\exists x)P(x)(\exists I,3)\\(5)(\exists x)P(x)(\exists E,1,2-4)$

例2：证明$(\forall x)(H(x)\rightarrow M(x))\land H(s)\Rightarrow (\exists x)M(x)$

证明：$\\(1)(\forall x)(H(x)\rightarrow M(x))(条件引入)\\(2)H(s)\rightarrow M(s)(\forall E,1)\\(3)H(s)(条件引入)\\(4)M(s)(2,3)\\(5)(\exists x)M(x)(\exists I,4)$

例3：前提为$\neg(\exists x)(F(x)\land H(x)),(\forall x)(G(x)\rightarrow H(x))$，证明$(\forall x)(G(x)\rightarrow \neg F(x))$

证明：$\\(1)\neg(\exists x)(F(x)\land H(x))(前提引入)\\(2)(\exists x)(\neg F(x)\lor\neg H(x))(1.置换)\\(3)(\exists x)(H(x)\rightarrow \neg F(x))(2.置换)\\(4)H(x)\rightarrow \neg F(x)(\forall E,3)\\(5)(\forall x)(G(x)\rightarrow H(x))(前提引入)\\(6)G(x)\rightarrow H(x)(\forall E,5)\\(7)G(x)\rightarrow\neg F(x)(4,6分离)\\(8)(\forall x)(G(x)\rightarrow\neg F(x))(\forall I,7)$

例4：前提为：$\\(\exists x)(P(x)\land(\forall y)(D(y)\rightarrow L(x,y))),\\(\forall x)(P(x)\rightarrow (\forall y)(Q(y)\rightarrow \neg L(x,y)))\\$证明：$ \\ (\forall x)(D(x)\rightarrow \neg Q(x))$

证明：$\\(1)(\exists x)(P(x)\land(\forall y)(D(y)\rightarrow L(x,y)))(前提引入)\\(2)|P(c)\land(\forall y)(D(y)\rightarrow L(c,y))(假设引入)\\(3)|(\forall x)(P(x)\rightarrow (\forall y)(Q(y)\rightarrow \neg L(x,y)))(前提引入)\\(4)|P(c)\rightarrow (\forall y)(Q(y)\rightarrow \neg L(c,y))(\forall E，3)\\(5)|P(c)(\land,2)\\(6)|(\forall y)(Q(y)\rightarrow \neg L(c,y))(4,5分离)\\(7)|Q(y)\rightarrow \neg L(c,y)(\forall E,6)\\(8)|L(c,y)\rightarrow \neg Q(y)(7置换)\\(9)|(\forall y)(D(y)\rightarrow L(c,y))(\land ,2)\\(10)|D(y)\rightarrow L(c,y)(\forall E,10)\\(11)|D(y)\rightarrow \neg Q(y)(8,10分离)\\(12)| (\forall y)(D(y)\rightarrow \neg Q(y))(\forall I，11)\\(13)|(\forall x)(D(x)\rightarrow \neg Q(x))(12更名)\\(14)(\forall x)(D(x)\rightarrow \neg Q(x))(\exists E,1,2-23)$

归结法

基本上和命题逻辑的归结法类似。只不过一些细节和步骤上有所区别。

为了证明$A\Rightarrow B$，只需证$ A\land\neg B$是不可满足式。

  1. 建立子句集$S$。设$G=A\land\neg B$将。把$G$化成$Skolem$标准型$G^* $，然后把$G^* $中的全称量词省略.最后，把这里面的$\land$改成逗号，这样构成子句集合。
  2. 对$S$做归结。归结的意思通过例子来展现比较直观：如果$S$中有两个子句$A=P(x)\lor Q(x),B=\neg P(a)\lor R(y)$，那么对$A,B$做归结，得到归结式$Q(a)\lor R(y)$，并将这个归结式放入$S$中。注意！归结后不互反的文字变成了$Q(a)$，这是因为$\forall E$。
  3. 重复2，直至出现了矛盾式$\Box$。

例：用归结法证明$(\forall x)(P(x)\rightarrow Q(x))\land(\forall x)(Q(x)\rightarrow R(x))\Rightarrow (\forall x)(P(x)\rightarrow R(x))$

证明：$\\$首先得写出公式$G=(\forall x)(P(x)\rightarrow Q(x))\land(\forall x)(Q(x)\rightarrow R(x))\land\neg (\forall x)(P(x)\rightarrow R(x))$，$\\$然后对这个大的合取式的每个子式求出子句集。$\\$ $(\forall x)(P(x)\rightarrow Q(x))$的子句集为$\{\neg P(x)\lor Q(x)\}$ $\\$ $(\forall x)(Q(x)\rightarrow R(x))$的子句集为$\{\neg Q(x)\lor R(x)\}$ $\\$ $\neg (\forall x)(P(x)\rightarrow R(x))=(\exists x)(P(x)\land\neg R(x))$,$Skolem$化后子句集为$\{P(a),\neg R(a)\}$,$\\$这样得到了完整的子句集$S=\{\neg P(x)\lor Q(x),\neg Q(x)\lor R(x),P(a),\neg R(a)\}\\$然后开始归结过程：$\\(1)\neg P(x)\lor Q(x)\\(2)\neg Q(x)\lor R(x)\\(3)P(a)\\(4)\neg R(a)\\(5)Q(a)(1,3归结)\\(6)\neg Q(a)(2,4归结)\\(7)\Box$

到这里，所有有关“逻辑”的部分已经结束了，本科一年级就学到“一阶谓词逻辑”为止，后续同一知识树的一阶形式理论以及演算逻辑系统在这门课程中暂不涉及。

后续的内容是集合论。