本系列笔记仅为个人备忘记录
如有谬误、补充，还望不吝指正

数学的研究对象可以分为连续对象和离散对象两种，离散数学是研究离散对象的结构以及它们之间相互关系的科学，它是计算机科学与技术的理论基础。

数理逻辑是用数学的方法来研究形式逻辑，建立一套严格定义的符号体系来研究逻辑，故也称为符号逻辑，命题逻辑则是数理逻辑的重要部分

1 命题

1.1 什么是命题

命题是表达判断的陈述句

1.2 命题的真值

命题的真值只有两个，要么是真，要么是假

• 命题的真值为真：一个命题所表达的判断与客观情况一致，记作$T$(True)
• 命题的真值为假：一个命题所表达的判断与客观情况不一致，记作$F$(False)

1.3 判断一个句子是命题

两个判据：

• 句子是否是陈述句
• 句子是否有且仅有一个真值
  比如：
• 2是个素数
  首先这是一个陈述句，其次2要么是素数，要么不是素数，即这个句子有且仅有一个真值，所以这是个命题
• 雪是黑色的：同上
• 2030年人类将到达火星
  这个问题虽然可能还没发生，我们不知道具体的结果，但是我们知道要么人类到达了火星，要么没到达，所以它也是命题
• 如果天不下雨并且我有时间，我就去看电影
  这是个复合命题，是几个基本的命题合起来的命题
• $x+y<5$
  因为没有给出具体$x$和$y$的值，这个问题可能会有两个结果，所以它不是命题

1.4 命题的种类

• 原子命题(简单命题)：不能再分解成更简单陈述句的命题
• 复合命题(分子命题)：有若干个连结词、标点符号及原子命题符合构成的命题

1.5 命题的表示

一般用大写字母表示

1.6 逻辑连接词

前面说到我们要建立一套严格定义的符号体系来研究逻辑，简单命题可以用大写字母表示，复合命题我们就得使用逻辑连接词来连接原子命题来表示

1.6.1 否定

否定 ” $\neg$ “，表示”并非…”，”不…”等
用于对一个命题$P$的否定，写成$\neg P$，读作”非$P$“

设$P$为一命题，$P$的否定是一个新命题，记作$\neg P$，它的真值与$P$的真值相反

其真值表为：

$P$	$\neg$P
$F$	$T$
$T$	$F$

1.6.2 合取

合取 ” $\land$ “，表示”并且”、”不但…而且”等等
用于两个命题$P$，$Q$的与运算，写成$P\land Q$，读作”$P$与/且$Q$“

其真值表为：

$P$	$Q$	$P\land Q$
$F$	$F$	$F$
$F$	$T$	$F$
$T$	$F$	$F$
$T$	$T$	$T$

1.6.3 析取

析取分为可兼取的或和不可兼取的或

• 可兼取的或：析取 ” $\lor$ “

比如：$P$：小王能唱歌，$Q$：小王能跳舞，$P\lor Q$：小王能唱歌或者能跳舞

因为小王能唱歌也能跳舞这两个事情是可以同时发生的，所以我们使用析取来表达

其真值表为：

$P$	$Q$	$P\lor Q$
$F$	$F$	$F$
$T$	$F$	$T$
$F$	$T$	$T$
$T$	$T$	$T$

• 不可兼取的或：异或(排斥或) ” $\oplus$ “

异或表示“或者，但不能同时”，即两个命题中恰好有一个为真时，整个命题为真

比如：$P$：今天下雨，$Q$：今天是晴天，$P \oplus Q$：今天下雨或者是晴天，但不能同时下雨和是晴天

其真值表为：

$P$	$Q$	$P\lor Q$
$F$	$F$	$F$
$T$	$F$	$T$
$F$	$T$	$T$
$T$	$T$	$F$

1.6.4 蕴含

蕴含 ” $\to$ “，表示“如果……那么……”

用于两个命题$P$和$Q$之间的关系，写作 $P \to Q$，读作“若$P$，则$Q$”

称$P$为$P\to Q$的前件，$Q$为后件

其真值表为：

$P$	$Q$	$P \to Q$
$F$	$F$	$T$
$F$	$T$	$T$
$T$	$F$	$F$
$T$	$T$	$T$

• 当$P$为真而$Q$为假时，$P \to Q$为假
• 在其他情况下，$P \to Q$都为真。这符合逻辑中“假设前件为真时，后件必须为真”的善意规定的原则

1.6.5 等价

等价 ” $\leftrightarrow$ “，表示“当且仅当……”

用于两个命题$P$和$Q$表示它们具有相同的真值，写作 $P \leftrightarrow Q$，读作“$P$当且仅当$Q$”

其真值表为：

$P$	$Q$	$P \leftrightarrow Q$
$F$	$F$	$T$
$F$	$T$	$F$
$T$	$F$	$F$
$T$	$T$	$T$

• 当$P$与$Q$的真值相同时，$P \leftrightarrow Q$为真
• 当$P$与$Q$的真值不同时，$P \leftrightarrow Q$为假
  它和前面的异或刚好只差一个非，即

$$
P\oplus Q \leftrightarrow \neg (P\leftrightarrow Q)
$$

1.6.6 扩充连接词

• 合取非联结词：$\uparrow$
  又常称为与非，$P\uparrow Q\Leftrightarrow\neg(P\land Q)$
• 析取非联结词：$\downarrow$
  又常称为或非，$P\downarrow Q\Leftrightarrow\neg(P\lor Q)$
• 条件非联结词：$\mid\kern-0.63em\rightarrow$
  $P\mid\kern-0.63em\rightarrow Q\Leftrightarrow\neg(P\to Q)$
• 双条件非联结词：$\mid\kern-0.6em\leftrightarrow$
  就是异或，$P \mid\kern-0.6em\leftrightarrow Q\Leftrightarrow\neg(P\leftrightarrow Q)$

1.6.7 功能完全组

定义如下：称$G$为联结词功能完全组(最小联结词组)，则$G$满足下列条件：

• 由$G$中联结词构成的公式可以等价表示任意命题公式
• $G$中的任一联结词不能用其余联结词等价表示
  证明举反例即可

1.7 命题的符号化

命题符号化，就是把自然语言表达的句子用符号化的命题公式来表达，其步骤为：

1. 先将语句分解成原子命题
2. 将每个原子命题用大写字母表示。注意每个原子命题都必须是一个完整的句子
3. 用确切的逻辑联结词联结原子命题，构成给定命题的符号表达式
   例如：

$\sqrt{ 3 }$是无理数当且仅当加拿大位于亚洲

1. 这个句子有两个原子命题$P$：$\sqrt{ 3 }$是无理数，$Q$：加拿大位于亚洲
2. 所以这个命题的符号化表达为$P\leftrightarrow Q$

除非$a$能被2整除，否则$a$不能被4整除，其中a是给定正整数

1. 两个原子命题$P$：$a$能被2整除，$Q$：$a$不能被4整除
2. 所以这个命题的符号化表达为$Q \to P$

2 命题公式

2.1 数据类型

在命题公式中有三种数据类型

• 命题常项：即命题的真值
• 常值命题：即具体命题
• 命题变元：用大写字母表示的任一命题，它本身不是命题因为它没有固定真值，只有给它赋值之后才变成命题
  将一个命题常项或常值命题赋子命题变元的过程称为给命题变元赋值，也称为对命题变元作
  指派

2.2 合式公式

1. 单个命题变元、常值命题和命题常项是合式公式
2. 若$A$为合式公式，则$\neg A$为合式公式
3. 若$A$和$B$为合式公式，则$(A\land B),(A\lor B),(A\to B),(A \leftrightarrow B)$都是合式公式
4. 当且仅当有限次应用1 2 3所得到的符号串是合式公式
   下面的式子是合式公式：

$$
(P\land Q),(\neg P\to Q),(\neg P\to R),((P\land Q)\lor R)
$$

那么如果合式公式很复杂就会有很多括号，于是有了下面的约定：

• 最外层括号可省
• 不影响运算次序的括号可以省略
  运算次序：

$$
\neg ,\land,\lor,\to ,\leftrightarrow
$$

2.3 命题公式的真值表

给命题公式里的所有命题变元赋值以后它就有了唯一的真值，把所有赋值情况列成表，就是该命题公式的中值表

例如：

$(\neg P\to Q)\lor Q$	$P$	$Q$	$\neg Q$	$\neg P\to Q$
$F$	$F$	$F$	$T$	$F$
$T$	$F$	$T$	$T$	$T$
$T$	$T$	$F$	$F$	$T$
$T$	$T$	$T$	$F$	$T$

2.3.1 构建真值表的步骤

1. 由于每个命题变元都有两种赋值可能性，所以含有n个命题变元的命题公式真值表有$2^{n}$行
2. 将n个命题变元将字母次序排列
3. 将$F$记为0，$T$记为1，按照二进制数的次序赋值，赋值从 00…0 开始，然后按二进制加法依次加1，直到 11…1 为止
4. 对每个赋值，计算命题公式的真值
   例：
   构建$P\to(Q\to R)$的真值表

	$P$	$Q$	$R$	$Q\to R$	$P\to(Q\to R)$
0 0 0	$F$	$F$	$F$	$T$	$T$
0 0 1	$F$	$F$	$T$	$T$	$T$
0 1 0	$F$	$T$	$F$	$F$	$T$
0 1 1	$F$	$T$	$T$	$T$	$T$
1 0 0	$T$	$F$	$F$	$T$	$T$
1 0 1	$T$	$F$	$T$	$T$	$T$
1 1 0	$T$	$T$	$F$	$F$	$F$
1 1 1	$T$	$T$	$T$	$T$	$T$

2.4 公式分类

2.4.1 等价公式

对于下面这三个公式的真值表：

$P$	$Q$	$P\to Q$	$\neg P\lor Q$	$\neg Q\to \neg P$
$F$	$F$	$T$	$T$	$T$
$F$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$F$
$T$	$T$	$T$	$T$	$T$

可以看出，无论对P、Q作何种赋值，$P\to Q,\neg P\lor Q,\neg Q\to \neg P$的真值都相同，即

$$
P\to Q\Leftrightarrow \neg P\lor Q\Leftrightarrow \neg Q\to \neg P
$$

2.4.1.1 等价的定义

A，B是含有很多命题变元的命题公式，如果无论对它们其中的命题变元作何种赋值，A和B的赋值均相同，则称命题公式A与B等价，记作$A\leftrightarrow B$，它是个关系符号，不是个运算符号，它表明的是两个命题公式之间的关系

即若两个命题公式的真值表相同，则它们等价

2.4.1.2 等价的性质

• 自反性：对任何命题公式$A$，都有$A\Leftrightarrow A$
• 对称性：若$A\Leftrightarrow B$，则$B\Leftrightarrow A$
• 传递性：若$A\Leftrightarrow B$且$B\Leftrightarrow C$，则$A\Leftrightarrow C$

2.4.1.3 基础等价公式

1. 对合律：$\neg \neg P\Leftrightarrow P$
2. 幂等律：$P\lor P\Leftrightarrow P$， $P\land P\Leftrightarrow P$
3. 交换律：$P\lor Q\Leftrightarrow Q\lor P$，$P\land Q\Leftrightarrow Q\land P$
4. 结合律：$P\lor(Q\lor R)\Leftrightarrow(P\lor Q)\lor R$，$P\land(Q\land R)\Leftrightarrow(P\land Q)\land R$
5. 分配律：$P\lor(Q\land R)\Leftrightarrow(P\lor Q)\land(P\lor R)$，$P\land(Q\lor R)\Leftrightarrow(P\land Q)\lor(P\land R)$
6. 吸收律：$P\lor(P\land Q)\Leftrightarrow P$，$P\land(P\lor Q)\Leftrightarrow P$
7. 德摩根律：$\neg(P\lor Q)\Leftrightarrow \neg P\land \neg Q$，$\neg(P\land Q)\Leftrightarrow \neg P\lor \neg Q$
8. 同一律：$P\lor F\Leftrightarrow P$，$P\land T\Leftrightarrow P$
9. 零律：$P\lor T\Leftrightarrow T$，$P\land F\Leftrightarrow F$
10. 互补律：$P\lor \neg P\Leftrightarrow T$，$P\land \neg P\Leftrightarrow F$
11. 蕴含等价式：$P\to Q\Leftrightarrow \neg P\lor Q$
12. 等值等价式：$P\leftrightarrow Q\Leftrightarrow(P\to Q)\land(Q\to P)$

2.4.1.4 等价公式的证明方法

1. 列真值表：只适用于公式相对比较简单的情况下，公式复杂情况下命题变元很多列真值表会非常麻烦
2. 用等价公式变换：用上面的基础等价公式一步步代换变形求解

2.4.2 对偶式

在一个只含有$\neg,\lor,\land$的公式$A$中，把$\lor$换成$\land$，$\land$换成$\lor$，$T$换成$F$，$F$换成$T$，其余部分不变，得到另一个公式$A^*$，则称$A$和$A^*$互为对偶式

2.4.3 重言式与矛盾式

对于下面这两个命题公式：

$P$	$\neg P\lor P$	$\neg P\land P$
$F$	$T$	$F$
$T$	$T$	$F$

显然$\neg P\lor P$对于所有的指派，其真值都为$T$，我们称这种公式为重言式(永真式)，若公式$A\Leftrightarrow T$则称A为重言式或永真式

$\neg P\land P$对于所有指派，真值都为$F$，我们称这种公式为矛盾式(永假式)，若公式$A\Leftrightarrow F$则称A为矛盾式或永假式

2.4.4 重言蕴含式

当且仅当$A\to B$是重言式，则称$A$重言蕴含$B$，记作$A\Rightarrow B$，这个重言蕴含也是描述关系的符号，不是逻辑连接词

即若$A\to B\Leftrightarrow T$，则$A\Rightarrow B$

2.4.4.1 蕴含式的性质

• 自反性：对任意公式$A$，有$A\Rightarrow A$
• 传递性：对任意公式$A,B,C$，若$A\Rightarrow B,B\Rightarrow C$，则$A\Rightarrow C$
• 若$A\Rightarrow B,A\Rightarrow C$，则$A\Rightarrow B\land C$
• 若$A\Rightarrow C,B\Rightarrow C$，则$A\lor B\Rightarrow C$

2.4.4.2 与等价式的关系

$A\Leftrightarrow B$的充要条件是$A\Rightarrow B$且$B\Rightarrow A$

2.4.4.3 蕴含式的证明方法

• 真值表法
• 前件真推导后件真：设公式的前件$A$为真，若能推导出后件$B$也为真，即$A\to B$为永真式，$A\Rightarrow B$成立
• 前件假推导后件假：设公式的后件$B$为假，若能推导出前件$A$也为假，即$A\to B$为永真式，$A\Rightarrow B$成立
  例：

$$
\neg Q\land(P\to Q)\Rightarrow \neg P
$$

证明：

1. 前件真推导后件真：
   前件为真，$\therefore\neg Q\land(P\to Q)\Leftrightarrow T$，则$\neg Q\Leftrightarrow T,(\neg P\lor Q)\Leftrightarrow T$，所以$Q$为$F$,$P$为$F$，即后件为真
2. 后件假推导前件假：
   后件假，$\therefore\neg P\Leftrightarrow F$即$P$为$T$，分类讨论$Q$的情况
3. 若$Q$为$F$，则$(P\to Q)$为$F$，前件为假
4. 若$Q$为$T$，则$\neg Q$为$F$，前件为假

3 范式

对于给定公式的判定问题，简单的我们可以用真值表的方式解答，但变元较多的时候真值表很麻烦，为了解决这个问题，我们需要研究公式标准型问题

3.1 文字

命题变元和命题变元的否定称为文字，如果一个文字为另一个文字的否定则称他们互为相反文字

3.2 简单合取式和简单析取式

设$L_{1},L_{2},\dots,L_{k}$都是文字，其中$1\leq i\leq k$

则称$L_{1}\lor L_{2}\lor\dots \lor L_{k}$是简单析取式，并称$L_{i}$为析取项，称$L_{1}\land L_{2}\land\dots \land L_{k}$是简单析取式，并称$L_{i}$为析取项

一个命题变元或其否定既可以是简单合取式也可以是简单析取式子

显然一个简单合取式是永假式的充要条件是它含有相反文字，一个简单析取式是永真式的充要条件是它含有一对相反文字

3.3 析取范式和合取范式

设$A_{1},A_{2},\dots,A_{m}$为简单合取式，则$A_{1}\lor A_{2}\lor \dots \lor A_{m}$为析取范式，其中$1\leq m$

设$B_{1},B_{2},\dots,B_{m}$为简单析取式，则$B_{1}\land B_{2}\land \dots \land B_{m}$为合取范式，其中$1\leq n$

对于任何一个命题公式，都存在与其等价的析取范式和合取范式，并且范式具有不唯一性

3.3.1 求范式算法

1. 使用命题定律，消去公式中除了$\land,\lor,\neg$之外的公式中所有出现的连接词
2. 使用$\neg(\neg P)\Leftrightarrow P$和德摩根律，把$\neg$都移到命题变元以前
3. 利用结合律，分配律把公式化为析取范式或者合取范式
   例：
   求$(P\land(Q\to R))\to S$的析取范式和合取范式：

$$
\begin{align}
(P\land(Q\to R))\to S&\Leftrightarrow \neg (P\land(\neg Q\lor R))\lor S \\
&\Leftrightarrow (\neg P\lor(Q\land \neg R))\lor S \\
&\Leftrightarrow \neg P\lor(Q\land \neg R)\lor S \quad 析取范式 \\
&\Leftrightarrow (\neg P\lor Q\lor S)\land(\neg P\lor \neg R\lor S)\quad 合取范式
\end{align}
$$

3.3.2 范式的应用

• 公式$A$为永假式的充要条件是$A$的析取范式中每个简单合取式至少包含一对相反文字(即每个简单合取式都是永假式)
• 公式$A$为永真式的充要条件是$A$的合取范式中每个简单析取式至少包含一对相反文字(即每个简单析取式都是永真式)

3.4 主范式

3.4.1 主析取范式

3.4.1.1 小项

在含有$n$个命题变元的简单合取式中， 若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现一次， 则称该简单合取式为小项，或布尔积

$n$个命题变元构成的小项有$2^{n}$个

3.4.1.1.1 小项编码

为了简化小项的书写和表示，我们要使用小项编码，如果将命题变元按字典序排列，并且把命题变元与$1$对应， 命题变元的否定与$0$对应，则可对$2^{n}$个小项以二进制数编码， 记为$m_{i}$，其下标$i$是由二进制数转化的十进制数

比如两个命题变元$P$和$Q$的小项真值表如下

$m_{(二)}$	$m_{00}$	$m_{01}$	$m_{10}$	$m_{11}$
$P$ $Q$	$\neg P\land \neg Q$	$\neg P\land Q$	$P\land \neg Q$	$P\land Q$
0 0	1	0	0	0
0 1	0	1	0	0
1 0	0	0	1	0
1 1	0	0	0	1
$m_{(+)}$	$m_{0}$	$m_{1}$	$m_{2}$	$m_{3}$

3.4.1.1.2 小项的性质

• 没有两个小项是等价的，即是说各小项的真值表都是不同的
• 任意两个不同的小项的合取式是永假的：$m_{i}\land m_{j}\Leftrightarrow F,i\neq j$
• 所有小项之析取为永真：$\lor_{i=1}^{n}m_{i}\Leftrightarrow T$
• 每个小项只有一个成真指派，且其真值1位于主对角线上，这表明每个小项与其成真指派之间建立了一一对应关系

3.4.1.2 主析取范式定义与存在定理

在给定公式的析取范式中，若其简单合取式都是小项， 则称该范式为主析取范式

任意含$n$个命题变元的非永假命题公式$A$都有且仅有一个与其等价的主析取范式

3.4.1.3 主析取范式的求法

• 真值表法
• 公式化归法
  • 把给定公式化为析取范式
  • 删除析取范式中所有为永假的简单合取式(它们对整个范式的结果无影响)
  • 用等幂律把简单合取式中重复出现的是同一命题变元化简为一次出现
  • 用同一律补充没有出现的命题变元，然后用分配律展开，再把重复的简单合取式化为只出现一次，就能得到主析取范式
    例：求$(P\to Q)\land Q$的主析取范式

$$
\begin{align}
(P\to Q)\land Q&\Leftrightarrow \neg (P\lor Q)\land Q \\
&\Leftrightarrow (\neg P\land Q)\lor(Q\land T)\quad 分配律 \\
&\Leftrightarrow (\neg P\land Q)\lor(Q\land(\neg P\lor P))\\
&\Leftrightarrow (\neg P\land Q)\lor(Q\land \neg P)\lor(Q\land P) \\
&\Leftrightarrow (\neg P\land Q)\lor(Q\land P) \\
&\Leftrightarrow m_{1}\lor m_{3}
\end{align}
$$

3.4.1.4 主析取范式的唯一性

任意含$n$个命题变元的非永假命题公式，其主析取范式唯一

3.4.2 主合取范式

3.4.2.1 大项的概念和性质

在$n$个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，而二者之一必出现一次且仅出现一次，则称该简单析取式为大项，或布尔和

$n$个命题变元共形成$2^{n}$个大项

3.4.2.1.1 大项编码

为了简化大项的书写和表示，我们要使用大项编码，如果将命题变元按字典序排列，并且把命题变元与$0$对应， 命题变元的否定与$1$对应，则可对$2^{n}$个大项以二进制数编码， 记为$M_{i}$，其下标$i$是由二进制数转化的十进制数

比如两个命题变元$P$和$Q$的大项真值表如下

$M_{(二)}$	$M_{00}$	$M_{01}$	$M_{10}$	$M_{11}$
$P$ $Q$	$\neg P\land \neg Q$	$\neg P\land Q$	$P\land \neg Q$	$P\land Q$
0 0	0	1	1	1
0 1	1	0	1	1
1 0	1	1	0	1
1 1	1	1	1	0
$M_{(+)}$	$M_{0}$	$M_{1}$	$M_{2}$	$M_{3}$

3.4.2.1.2 大项的性质

• 没有两个大项是等价的
• 任何两个不同大项之析取式永真的，即$M_{i}\lor M_{j}\Leftrightarrow T,i\neq j$
• 所有大项的合取为永假，即$\land_{i=1}^{n}M_{i}\Leftrightarrow F$
• 每个大项只有一个解释为假，且其真值0位于主对角线上， 这表明每个大项与其成假指派建立了一一对应关系

3.4.2.2 主合取范式的定义与其存在定理

在给定公式的合取范式中，若其简单析取式都是大项， 则称该范式为主合取范式

任意含$n$个命题变元的非永真命题公式$A$都有且仅有一个与其等价的主析取范式

3.4.2.3 主合取范式的求法

它当然也可以使用真值表法和公式化归法求，但是如果我们算出了主析取范式，就可以通过大项和小项的关系来求主合取范式

3.4.3 主析取范式和主合取范式的关系

主范式是由小项和大项构成，小项和大项有下列关系：

$$
\neg m_{i}\Leftrightarrow M_{i}\quad \neg M_{i}\Leftrightarrow m_{i}
$$

所以主析取范式和主合取范式存在互补关系

3.4.3.1 从主析取范式求主合取范式

1. 求出$A$的主析取范式中没有包含到的小项
2. 求出与1中小项的下标相同的大项
3. 做2中大项的合取，就是$A$的主合取范式

3.4.4 主范式的应用

3.4.4.1 判定公式是什么公式

对于一个公式，我们求出它的主范式A

• 若$A\Leftrightarrow T$，则$A$为永真式
• 若$A\Leftrightarrow F$，则$A$为永假式
• 若$A$不与$T$或者$F$等价，且又不包含$2^{n}$个小项或者大项，则$A$为可满足式

3.4.4.2 判定两个公式是否等价

若给定两公式的主范式相同，则给定两公式是等价的

4 推理理论

4.1 推理的基本概念和形式

推理也称论证，它是指由已知命题得到新的命题的思维过程，其中已知命题称为推理的前提或假设，推得的新命题称为推理的结论或逻辑推论

在数理逻辑中，前提$H$是一个或者$n$个命题公式$H_{1},H_{2},\dots,H_{n}$，结论是一个命题公式$C$，由前提到结论的推理形式可以表示为

$$
H_{1},H_{2},\dots,H_{n}\vdash C
$$

其中符号$\vdash$表示推出，否则$H_{1},H_{2},\dots,H_{n}\not\vdash C$

推理是命题公式的一个有限序列，它的最后一个公式是结论，余下的为前提或假设

4.1.1 命题逻辑的推理定义

如果存在$H_{1},H_{2},\dots,H_{n},C$这个序列的一个指派$I$，使得$I(H_{i})(1\leq i\leq n)$为真而$I(C)$为假，人话就是使得条件为真，但结论为假，则我们说$H_{1},H_{2},\dots,H_{n}\vdash C$这个推理是无效的，即$H_{1},H_{2},\dots,H_{n}\not\vdash C$，反之推理是有效的，此时称$C$为前面条件序列的有效结论或逻辑推论，并称前面的前提构成的集合为$C$的前提集合

4.1.2 命题逻辑的推理形式

推理$H_{1},H_{2},\dots,H_{n}\vdash C$是有效的，当且仅当命题公式$(H_{1}\land H_{2}\land\dots \land H_{n})\to C$是永真式，即$(H_{1}\land H_{2}\land\dots \land H_{n})\Rightarrow C$，人话就是如果我们要证明一个推理是正确的，就要证明$(H_{1}\land H_{2}\land\dots \land H_{n})\to C\Leftrightarrow T$

4.2 推理规则

在数理逻辑中，从前提推导出结论，要依据事先提供的公认的推理规则，这些规则包括如下几种：

4.2.1 规则列表

1. P规则（前提引入规则）
   在推导过程中，前提可视具体需要引入使用

2. T规则（结论引入规则）
   在推导过程中，前面已导出的有效结论都可作为后续推导的前提引入

3. 替换规则
   在推导过程中，公式中的子公式都可以用与之等价的公式替换

4. 代入规则
   在推导过程中，重言式中的任意命题变元都可以用一个命题公式代入，其结果依然是重言式

5. CP规则（条件证明引入规则）
   若期望推出的有效结论是一个条件式$R \to C$，则可以将其前件$R$加入前提集作为附加前提，再去证明其后件$C$即可

4.3 推理定律

在推理过程中，除了运用推理规则以外，还需要使用许多推理定律

这些定律是判断有效结论的重要依据，需牢记并熟练运用

4.3.1 推理定律列表

以下是常见的推理定律及其描述：

1. 化简式
   $A \land B \vdash A$
   $A \land B \vdash B$

2. 附加式
   $A \vdash A \lor B$
   $\neg A \vdash A \to B$
   $B \vdash A \to B$

3. 假言推论
   $A, (A \to B) \vdash B$

4. 拒取式
   $\neg B, (A \to B) \vdash \neg A$

5. 析取三段论
   $\neg A, (A \lor B) \vdash B$

6. 条件三段论
   $(A \to B), (B \to C) \vdash A \to C$

7. 双条件三段论
   $(A \leftrightarrow B), (B \leftrightarrow C) \vdash A \leftrightarrow C$

4.3.2 特别推理形式

1. 合取构造二难
   $(A \to B), (C \to D), (A \land C) \vdash B \land D$

2. 析取构造二难
   $(A \to B), (C \to D), (A \lor C) \vdash B \lor D$

3. 前后件附加
   $A \to B \vdash (A \lor C) \to (B \lor C)$
   $A \to B \vdash (A \land C) \to (B \land C)$

4. 合取引入
   $A, B \vdash A \land B$

4.4 有效结论的判断方法

判断结论 $C$ 是否有效，可用以下方法：

4.4.1 真值表法

构造前提 $H_1, H_2, \dots, H_n$ 和结论 $C$ 的条件式 $(H_1 \land H_2 \land \dots \land H_n) \to C$ 的真值表。如果该条件式为永真式，则 $C$ 为有效结论

简便方法：

1. 找出前提 $H_1, H_2, \dots, H_n$ 全为真的行，若对应行中 $C$ 的真值也为真，则 $C$ 为有效结论
2. 找出 $C$ 为假的所有行，若对应行中前提 $H_1, H_2, \dots, H_n$ 至少有一个为假，则 $C$ 为有效结论

4.4.2 演绎法

形式证明：从前提集合 $H$ 构造命题公式的有限序列 $A_1, A_2, \dots, A_n$，其中：

• $A_1$ 为前提集合 $H$ 中的某前提 $H_i$
• $A_i (i \geq 2)$ 为前提 $H$ 中的某个 $H_i$，或者某些 $A_j (j < i)$ 的有效结论
• $A_n = C$ 为最终的证明目标

演绎法的具体操作可用四列若干行的一个表来表示：

• 第一列是花括号序列：表明该行是由哪些前提推出的
• 第二列是圆括号序列：是一行一行的编号
• 第三列是推导行序列：表明推出的中间逻辑结论和最终结论
• 第四列是注释行序列：表示所使用的推理规则或推理定律
  例：求证$S$是前提$P,P\to \neg Q,\neg Q\to R,R\to S$的有效结论

一	二	三	四
{1}	(1)	$P\to \neg Q$	P
{2}	(2)	$\neg Q\to R$	P
{1,2}	(3)	$P\to R$	T,(1)(2)
{4}	(4)	P	P
{1,2,4}	(5)	$R$	T,(3)(4)
{6}	(6)	$R\to S$	P
{1,2,4,6}	(7)	$S$	T,(5)(6)

4.4.3 间接证法（反证法）

反证法（或归谬法）将结论的否定（即 $\neg C$）作为出发点，加入前提集合，若推出矛盾，则得知原结论 $C$ 是有效结论