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

一般公理系统的结构

通常而言，一个公理系统一般包括如下几部分：

  1. 初始符号：公理所允许出现的全体符号的集合。

  2. 形成规则：由出事符号可以组成各种符号序列。

  3. 公理：选出几个最基本的重言式作为推演其他所有重言式的依据。

  4. 变形规则：变形规则就是公理系统所规定的推理规则。

  5. 建立定理：这是公理系统内做演算的主要内容，应该包括所有的重言式和对它们的证明。

罗素系统

初始符号

  • $A,B,C……$，大写英文字母（表示命题）

  • $\neg , \lor$表示联结词

  • （ ），表示圆括号

  • $\vdash$，写在一个公式之前表示其为重言式

形成规则

符号形成规则的符号序列成为合式公式。

  1. 符号$\pi$是合式公式（$\pi$取值为$A,B……$）

  2. 如果$A,B$是合式公式，那么$A\lor B$也是合式公式

  3. 如果$A$是合式公式，那么$\neg A$也是合式公式

  4. 只有符合1,2,3的符号序列才是合适公式

定义

除了由形成规则构成的合式公式之外，还可以通过定义来引入新的合式公式，这样引入的合式公式有着缩写和简化表达的作用。

  • 定义1 $A\rightarrow B$定义为$\neg A\lor B$

  • 定义2 $A\land B$定义为$\neg(\neg A\lor\neg B)$

  • 定义3 $A\leftrightarrow B$定义为$(A\rightarrow B)\land(B\rightarrow A)$

或者换句话说，罗素公理系统中只有“非”和“或”两种逻辑，其余逻辑都要求用“非”和“或”来表示。并且注意，上述定义中的顺序关系是严格的。

公理⭐️

  • 公理1 $\vdash (P\lor P)\rightarrow P$

  • 公理2 $\vdash P\rightarrow (P\lor Q)$

  • 公理3 $\vdash (P\lor Q)\rightarrow (Q\lor P)$

  • 公理4 $\vdash (Q\rightarrow R)\rightarrow((P\lor Q)\rightarrow (P\lor R))$

注意，只有这些公理才能够直接运用在罗素公理系统的推导过程中！我们其余所知道的所有公式定理都不能够直接在罗素公理系统中用，包括交换律、结合律、互反律、摩根律等等等等。

变形规则⭐️

  1. 代入规则：将合式公式$A$中出现的某一个符号$\pi$到处都带一某一个合适的公式$B$，从而得到合式公式$A\frac{\pi}{B}$叫代入。带入规则说，如果$\vdash A$,则$\vdash A\frac{\pi}{B}$

  2. 分离规则：如果$\vdash A , \vdash A\rightarrow B$,那么$\vdash B$

  3. 置换规则：定义的左右两方可以互相替换。设公式$A$，替换后为公式$B$。置换规则说，如果$\vdash A$则$\vdash B$

定理的推演

定理1：$\vdash (Q\rightarrow R)\rightarrow((P\rightarrow Q)\rightarrow(P\rightarrow R))$

证明：$\\(1)\vdash(Q\rightarrow R)\rightarrow((P\lor Q)\rightarrow(P\lor R)) (公理4)\\(2)\vdash(Q\rightarrow R)\rightarrow((\neg P\lor Q)\rightarrow(\neg P\lor R)) (1.带入\frac{P}{\neg P})\\(3)\vdash (Q\rightarrow R)\rightarrow((P\rightarrow Q)\rightarrow(P\rightarrow R)) (2.用定义1)$

定理2：$\vdash P\rightarrow P$

证明:$\\(1)\vdash P\rightarrow P\lor Q (公理2)\\(2)\vdash P\rightarrow P\lor P (1.带入\frac{Q}{P})\\(3)\vdash P\lor P\rightarrow P (公理1)\\(4)\vdash (Q\rightarrow R)\rightarrow((P\rightarrow Q)\rightarrow(P\rightarrow R)) (定理1)\\(5)\vdash (P\lor P\rightarrow P)\rightarrow((P\rightarrow P\lor P)\rightarrow(P\rightarrow P))(4.带入\frac{Q}{P\lor P},\frac{R}{P})\\(6)\vdash (P\rightarrow P\lor P)\rightarrow(P\rightarrow P)(3.5.分离)\\(7)\vdash P\rightarrow P(2.6.分离)$

定理3：$\vdash \neg P\lor P$

证明：$\\(1)\vdash P\rightarrow P(定理2)\\(2)\vdash\neg P\lor P(1.用定义1)$

定理4：$\vdash P\lor\neg P$

证明：$\\(1)\vdash P\lor Q\rightarrow Q\lor P(公理3)\\(2)\vdash \neg P\lor P\rightarrow P\lor \neg P(1.带入\frac{P}{\neg P},\frac{Q}{P})\\(3)\vdash \neg P\lor P(定理3)\\(4)\vdash P\lor \neg P(2.3.分离)$

定理5：$\vdash P\rightarrow \neg\neg P$

证明：$\\(1)\vdash P\lor\neg P(定理4)\\(2)\vdash\neg P\lor \neg\neg P(1.带入\frac{P}{\neg P})\\(3)\vdash P\rightarrow \neg\neg P(2.用定义1)$

定理6：$\vdash \neg\neg P\rightarrow P$

证明：$\\(1)\vdash P\rightarrow \neg\neg P(定理5)\\(2)\vdash \neg P\rightarrow \neg\neg\neg P(1.带入\frac{P}{\neg P})\\(3)\vdash(Q\rightarrow R)\rightarrow((P\lor Q)\rightarrow (P\lor R))(公理4)\\(4)\vdash(\neg P\rightarrow \neg\neg\neg P)\rightarrow((P\lor \neg P)\rightarrow (P\lor \neg\neg\neg P))(3.带入\frac{Q}{\neg P},\frac{R}{\neg\neg\neg P})\\(5)\vdash(P\lor \neg P)\rightarrow (P\lor \neg\neg\neg P)(2.4.分离)\\(6)\vdash P\lor \neg P(定理4)\\(7)\vdash P\lor \neg\neg\neg P(5.6.分离)\\(8)\vdash (P\lor Q)\rightarrow (Q\lor P)(公理3)\\(9)\vdash (P\lor \neg\neg\neg P)\rightarrow (\neg\neg\neg P\lor P)(8.带入\frac{Q}{\neg\neg\neg P})\\(10)\vdash \neg\neg\neg P\lor P(7.9.分离)\\(11)\vdash\neg\neg P\rightarrow P(10.用定义1)$

定理7：$\vdash (P\rightarrow Q)\rightarrow (\neg Q\rightarrow \neg P)$

证明：$\\(1)\vdash P\rightarrow \neg\neg P(定理5)\\(2)\vdash Q\rightarrow \neg\neg Q(1.带入\frac{P}{Q})\\(3)\vdash (Q\rightarrow R)\rightarrow((P\lor Q)\rightarrow (P\lor R))(公理4)\\(4)\vdash (Q\rightarrow \neg\neg Q)\rightarrow((\neg P\lor Q)\rightarrow (\neg P\lor \neg\neg Q))(3.带入\frac{R}{\neg\neg Q},\frac{P}{\neg P})\\(5)\vdash (\neg P\lor Q)\rightarrow (\neg P\lor \neg\neg Q)(2.4.分离)\\(6)\vdash (P\lor Q)\rightarrow (Q\lor P)(公理3)\\(7)\vdash (\neg P\lor \neg\neg Q)\rightarrow (\neg\neg Q\lor \neg P)(6.带入\frac{P}{\neg P},\frac{Q}{\neg\neg Q})\\(8)\vdash (Q\rightarrow R)\rightarrow((P\rightarrow Q)\rightarrow(P\rightarrow R))(定理1)\\(9)\vdash (\neg P\lor \neg\neg Q\rightarrow \neg\neg Q\lor \neg P)\rightarrow((\neg P\lor Q\rightarrow \neg P\lor \neg\neg Q)\rightarrow(\neg P\lor Q\rightarrow \neg\neg Q\lor \neg P))(8.带入\frac{P}{\neg P\lor Q},\frac{Q}{\neg P\lor \neg\neg Q},\frac{R}{\neg\neg Q\lor \neg P})\\(10)\vdash (\neg P\lor Q\rightarrow \neg P\lor \neg\neg Q)\rightarrow(\neg P\lor Q\rightarrow \neg\neg Q\lor \neg P)(7.9.分离)\\(11)\vdash \neg P\lor Q\rightarrow \neg\neg Q\lor \neg P(5.10.分离)\\(12)\vdash (P\rightarrow Q)\rightarrow (\neg Q\rightarrow \neg P)(11.用定义1)$

常见做题套路

三段论的实现:$\\(1)\vdash A\rightarrow B(前提)\\(2)\vdash B\rightarrow C(前提)\\(3)\vdash (Q\rightarrow R)\rightarrow((P\rightarrow Q)\rightarrow(P\rightarrow R))(定理1)\\(4)\vdash (B\rightarrow C)\rightarrow((A\rightarrow B)\rightarrow(A\rightarrow C))(3.带入\frac{P}{A},\frac{Q}{B},\frac{R}{C})\\(5)\vdash (A\rightarrow B)\rightarrow(A\rightarrow C)(2.4.分离)\\(6)\vdash A\rightarrow C(1.5.分离)$