1. 范式#

1.1. 范式定义#

文字：单个命题变元，或命题变元的否定
简单合取式（短语）：有限个文字的合取( $P \land Q \land R$ )
简单析取式（子句）：有限个文字的析取( $P \lor Q \lor R$ )
P与 $\neg P$ ，称为互补对。
合取范式：有限个简单析取式的合取式
析取范式：有限个简单合取式的析取式

有限个表示1个也可以

P， $\neg P$ ，可以是文字、短语、子句、析取范式、合取范式

用括号表示的析取式或者合取式，不能被拆开看待。

否定联结词只会出现在命题变元之前。

1.2. 范式存在定理#

对应任意命题公式，都存在与其等价的析取范式和合取范式。
范式的化简方法
- 利用蕴含式和等价式，除去蕴含和等价
- 双重否定和德摩根律，去除非命题变元前的否定
- 分配率，进行析取和合取之间的转化

合取范式可以指出公式合适为假

析取范式可以表示公式合适为真

范式#

极小项和极大项#

在含有n个命题变元的短语或者子句中，每个命题变元与其否定不同时存在，且二者之一恰好出现且仅出现一次，出现的次序与命题变元的次序一致，则称此短语是关于命题变元的一个极小项或极大项

没有两个不同的极大项（极小项）是等价的

每个极大项M只有一组成真赋值，可以用于给极大项编码（命题变元为0，否定为1）

对于极小项m，命题变元为1，否定为0。（优先记忆）

极大项和极小项的性质#

任何两个极小项的合取为0
任何两个极大项的析取为1
极小项和极大项是否定关系
所有极小项的析取为1
所有极大项的合取为0

主析取范式和主合取范式#

主析取范式：每个短语为极小项，且按照编码从小到大排列。

主合取范式：每个子句为极大项，且按照编码从小到大排列。

如果不包含任何极小项/极大项，称之为“空”。

任何公式都存在与之等价的主析取范式和主合取范式。

主范式求解
1. 消除重复的命题变元：幂等律、矛盾律、同一律、排中律、零律
2. 缺少命题变元：将1/0代换，再用结合律展开。
3. 重复的极大项/极小项：合并极大/小项，利用交换律调整顺序
利用真值表求解
1. 对于主合取范式，决定了命题公式的真值(0)，选出所有真值为假的行，将对应的极大项合取
2. 对于主析取范式，决定了命题公式的真值(1)，选出所有真值为真的行，将对应的极小项析取

主析取范式和主合取范式之间是互补的。

主范式的意义：
- 主析取范式：使得命题公式的真值为1的情况，即：所有成真赋值的选项。
- 主合取范式：使得命题公式的真值为0的情况，即：所有成假赋值的选项。

命题蕴含公式#

推理：从一组前提合乎逻辑地推出结论的思维过程。

对于一系列前提 $G_1 \land G_2 \land ... \land G_n$ ， $H$ 是公式。则 $H$ 是 $G$ 的逻辑结果，当且仅当：对任意解释 $I$ ，如果 $I$ 使得 $G_1 \land G_2 \land ... \land G_n$ 为真，则 $I$ 也会使 $H$ 为真。

记为 $G_1 \land G_2 \land ... \land G_n \implies H$ ， $\implies$ 称为“蕴含关系”。此时称 $G_1 \land G_2 \land ... \land G_n \implies H$ 为有效的，否则称为无效的。

$G_1 \land G_2 \land ... \land G_n$ 称为一组前提，有时用集合 $\Gamma = G_1 \land G_2 \land ... \land G_n$ 表示。此时称H是前提集合 $\Gamma$ 的逻辑结果。记为 $\Gamma \implies H$

推理的有效性和结论的真实性不同，只有在前提为真的情况下才能得出真的结论。

当且仅当( $G_1 \land G_2 \land ... \land G_n \rightarrow H$ )为永真公式， $\Gamma \implies H$ 的推理是有效的

推理定律-基本蕴含关系#

简化规则： $G \land H \implies G$ , $G \land H \implies H$
添加规则： $G \implies G \lor H$ , $H \implies G \lor H$
合取引入规则： $G, H \implies G \land H$
选言三段论： $G \lor H, \neg G \implies H$ , $G \lor H, \neg H \implies G$
假言推理规则： $G \rightarrow H, G \implies H$
否定后件式： $G \rightarrow, \neg H \implies \neg G$
假言三段论： $G \rightarrow H, H \rightarrow I \implies G \rightarrow I$
二难推论： $G \lor H, G \rightarrow I, H \rightarrow I \implies I$

推理规则#

规则P：前提引用规则，推导过程中可以随时引入前提集合中的任意一个前提。
规则T：逻辑结果引用规则，在推论过程中可以随时引入公式S，S是由前面的公式推导出来的逻辑结果
规则CP：附加前提规则：如果能从给定的前提集合 $\Gamma$ 与公式P推导出S，则能从此前提集合 $\Gamma$ 推导出 $P \rightarrow S$