1.4 范式

1.4.1 析取范式和合取范式

范式是命题公式的规范表示形式，又称为 标准形 。一个命题公式可以有不同的等价式，因而为命题公式的研究带来一定的困难。把命题公式化成规范的标准形可为命题公式的研究和应用带来方便。

定义1.4.1 一个命题公式具有形式 A ₁ ∨ A ₂ ∨…∨ A _n （ n ≥1），其中 A ₁ ， A ₂ ，…， A _n 都是由命题变元或其否定所组成的合取式，则称该命题公式为 析取范式 。

例如，给定命题变元 p 、 q 和 是析取范式。

定义1.4.2 一个命题公式具有形式 B ₁ ∧ B ₂ ∧…∧ B _n （ n ≥1），其中 B ₁ ， B ₂ ，…， B _n 都是由命题变元或其否定所组成的析取式，则称该命题公式为 合取范式 。

例如，给定命题变元 p 、 q 和 r ， 是合取范式。

定理1.4.1（范式存在定理） 任意一个命题公式都存在着与之等价的析取范式和合取范式。

证明 设 G 为任意一个公式。

1）消去 、∧、∨以外的联结词。

2）将否定联结词内移或消去。

3）利用分配律、交换律和结合律等将公式归纳为析取范式和合取范式。

通过上面的3个步骤可以求出与 G 等价的析取范式和合取范式。因此，任意一个命题公式都存在着与之等价的析取范式和合取范式。以上也是求析取范式和合取范式的步骤。

◀

例1.4.1 求命题公式（ p ∧（ p → q ））∨ q 的析取范式和合取范式。

解

按析取范式的定义， 、（ p ∧ q ）∨ q 、 q 都是原公式的析取范式，也就是说，与某个命题公式等值的析取范式是不唯一的。同理，与某个命题公式等值的合取范式也是不唯一的，如上例中，（ p ∨ q ）∧ q 、 和 q 都是合取范式。因而析取范式和合取范式不能作为命题公式的标准形。下面介绍主范式的概念。可以证明任意命题公式的主范式都是唯一的，因而可以用与命题公式等值的主范式作为它的标准形。

1.4.2 主析取范式和主合取范式

定义1.4.3 含有 n 个命题变元的合取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的合取式称为 极小项 。

定义1.4.4 含有 n 个命题变元的析取式中，若每个命题变元与其否定不同时出现，而二者之一必出现且仅出现一次，这样的析取式称为 极大项 。

一般来说，极大项和极小项中的各个变元按下标由小到大的顺序排列，若无下标，则按字母顺序排列。例如，对于三个命题变元 p 、 q 和 r ， p ∧ q ∧ r 、 都是极小项， p ∨ q ∨ r 、 都是极大项，而 p ∧ q 和 都不是极小项，因为它们没有包含所有的命题变元。同理， p ∨ q 和 也不是极大项。

含 n 个命题变元 p ₁ ， p ₂ ，…， p _n 的极小项可表示为 ，极大项可表示为 ，其中每一个 为 p _i 或 。由 n 个命题变元产生的不同的极大项和极小项的个数均为2 ⁿ 个。每个极小项在它的2 ⁿ 个赋值中只有一个成真赋值，例如，含三个变元的极小项 p ∧ q ∧ r 的成真赋值只有111。每个极大项在它的2 ⁿ 个赋值中只有一个成假赋值，例如，含三个变元的极大项 的成假赋值只有011。因而每个极小项可以简记为 m _i ，其中，下标 i 为该极小项的成真赋值；每个极大项可以简记为 M _i ，其中，下标 i 为该极大项的成假赋值。

例如，3个命题变元可形成8个极小项，如表1.4.1所示。

一般地， n 个命题变元形成的极小项可表示为

3个命题变元形成的8个极大项如表1.4.2所示。

一般地， n 个命题变元形成的极大项可表示为

定义1.4.5 如果含 n 个命题变元的命题公式的析取范式的每个合取式全是极小项，则称该析取范式为 主析取范式 。

定理1.4.2 任何命题公式的主析取范式都是存在的，并且是唯一的。

证明 给定命题公式 A 。

1）求 A 的析取范式 A′ ， A′ 的形式为 A ₁ ∨ A ₂ ∨…∨ A _n （ n ≥1）。

2）若 A′ 中的某个简单合取式 A _i 不是极小项，则补入在 A _i 中没有出现的变元。例如，若 p _i 和 都不在 A _i 中，则将 A _i 展开成如下形式： 。

3）重复步骤2，直到所有的简单合取式都含有所有的命题变元或它的否定式。

4）消去重复出现的命题变项、矛盾式及重复出现的极小项。

按上述步骤求得的就是 A 的主析取范式。所以，任何命题公式的主析取范式都是存在的，而且是唯一的（唯一性证明略）。

◀

例1.4.2 求命题公式（ p ∨（ q ∧ r ））→（ p ∧ q ∧ r ）的主析取范式。

解

在（ p ∨（ q ∧ r ））→（ p ∧ q ∧ r ）的析取范式中含有两个合取式 和 ，均不是极小项，因而要补入没有出现的变元， 用 代换，并用分配律展开，使得每个合取式都是极小项。对 同样补入没有出现的变元 q 。消去重复出现的极小项，就得到原公式的主析取范式。极小项可以用简记 m _i 表示，按 m _i 的下标由小到大的顺序排列后可用∑表示主析取范式，如

（ p ∨（ q ∧ r ））→（ p ∧ q ∧ r ）

⇔ m ₀ ∨ m ₁ ∨ m ₂ ∨ m ₇ ⇔∑（0，1，2，7）

一个命题公式的主析取范式中的每一个极小项的成真赋值就是该公式的一个成真赋值。因而根据命题公式的真值表可以立即写出公式的主析取范式。

例1.4.3 试由 p ∧ q ∨ r 的真值表（表1.4.3）求它的主析取范式。

解 由表1.4.3知，公式 p ∧ q ∨ r 的成真赋值为001、011、101、110、111，对应的十进制数下标的极小项为 m ₁ 、 m ₃ 、 m ₅ 、 m ₆ 、 m ₇ 。因此， p ∧ q ∨ r 的主析取范式为

p ∧ q ∨ r ⇔∑（1，3，5，6，7）

利用表1.4.1， p ∧ q ∨ r 的主析取范式还可写为

设 G 是含 n 个命题变项的命题公式，当且仅当 G 的主析取范式含全部2 ⁿ 个极小项时， G 为重言式；若 G 为矛盾式， G 的主析取范式不含任何极小项，记 G 的主析取范式为0；当 G 的主析取范式中至少含有一个极小项时， G 为可满足式。

类似地可以给出主合取范式的定义。

定义1.4.6 如果含 n 个命题变元的命题公式的合取范式的每个析取式全是极大项，则称该合取范式为 主合取范式 。

定理1.4.3 任何命题公式的主合取范式都是存在的，并且是唯一的。

证明 给定命题公式 A 。

1）求 A 的合取范式 B′ ， B′ 的形式为 B ₁ ∧ B ₂ ∧…∧ B _n （ n ≥1）。

2）若 B′ 中的某个析取式 B _i 不是极大项，则补入在 B _i 中没有出现的变元。例如，若 p _i 和 都不在 B _i 中，则将 B _i 展成如下形式： 。

3）重复步骤2，直到所有的简单析取式都含有所有的命题变元或它的否定式。

4）消去重复出现的命题变项、重言式及重复出现的极大项。

按上述步骤求得的就是 A 的主合取范式。所以，任何命题公式的主合取范式都是存在的，而且是唯一的（唯一性证明略）。

◀

例1.4.4 求命题公式（ p ∨（ q ∧ r ））→（ p ∧ q ∧ r ）的主合取范式。

解

将极大项按下标由小到大的顺序排列后可用∏表示，如

（ p ∨（ q ∧ r ））→（ p ∧ q ∧ r ）⇔ M ₃ ∧ M ₄ ∧ M ₅ ∧ M ₆ ⇔∏（3，4，5，6）

一个命题公式的主合取范式中的每一个极大项的成假赋值就是该公式的一个成假赋值。因而根据命题公式的真值表可以立即写出公式的主合取范式。又因为，公式的主析取范式中没有出现的极小项的赋值就是公式的成假赋值，因而主合取范式中的极大项的下标码和主析取范式中没有出现的极小项的下标码相同。因此，只要求出了命题公式的主析取范式，就可以立即写出它的主合取范式，反之亦然。

例如，已知公式 G 的主析取范式

G ⇔ m ₀ ∨ m ₁ ∨ m ₂ ∨ m ₇ ⇔∑（0，1，2，7）

其中没有出现的极小项的下标码3、4、5、6就是主合取范式极大项的下标码，因此可以直接写出主合取范式

G ⇔ M ₃ ∧ M ₄ ∧ M ₅ ∧ M ₆ ⇔∏（3，4，5，6）

重言式的主合取范式不含任何极大项，用1表示重言式；矛盾式的主合取范式包含全部2 ⁿ 个极大项。

利用主析取范式或主合取范式可以判断公式是否等价及求命题公式的成真赋值和成假赋值。

例1.4.5 判断 和 是否等价。

解

所以， 和 等价。

◀

例1.4.6 判断公式 是否为重言式。

解

公式 是重言式，因为主析取范式包含了所有的极小项。

◀

例1.4.7 设计一个集成学习系统，该系统综合三个基学习器的分类预测（正类或负类），以投票的方式决定输入样本的预测类别，即在超过半数基学习器给出正类的情况下判定该样本为正类，否则为负类。设计满足上述条件的集成学习分类器，并尝试以逻辑电路图的方式画出该分类器。

解 三个基学习器的预测类别分别为 p 、 q 、 r ，集成学习器的最终预测类别为 A 。正类为1，负类为0。

根据题意，可将真值表列出，见表1.4.4。

由上述真值表可写出 A 的表达式

化简 A 的表达式得

分类器的逻辑电路图如图1.4.1所示。

◀

例1.4.8 某单位选派A、B、C三位业务骨干去进修，由于工作需要，选派要满足如下条件。

1）若A去，则C同去。

2）若B去，则C不能去。

3）若C不去，则A或B可以去。

问可以有哪些选派方案？

解 设 p 表示“派A去”， q 表示“派B去”， r 表示“派C去”。

由已知条件可得

该公式的成真赋值就是可行的选派方案。写出该公式的主析取范式

有3个成真赋值，所以有3种选派方案：

1）A和B不去，C去；

2）A和C不去，B去；

3）A和C去，B不去。

◀ tFJpV7VxlOEvguyvc+caibEPGi7pyxgwmxCA4Jjfc6c8KHOtgDJNrADRD2WeAq45

1.5 命题逻辑的推理

1.5.1 推理理论

数理逻辑是用数学方法研究推理的形式结构和推理规律的数学学科。推理是从前提出发推出结论的思维过程，其中前提是已知的命题公式，结论是从前提出发应用推理规则推出的命题公式。关于从前提 A 推出结论 B 的定义如下。

定义1.5.1 设 A 和 B 是两个命题公式，当且仅当命题 A → B 是重言式时（即 A → B ⇔1时），称 从 A 推出 B 是有效的 ，或 A 蕴涵 B ，或 B 是前提 A 的结论 ，可以表示成 A ⇒ B 。

一般地，推理的前提可以是多个命题公式 A ₁ ， A ₂ ，…， A _n ，若（ A ₁ ∧ A ₂ ∧…∧ A _n ）→ B 是重言式，则称由前提 A ₁ ， A ₂ ，…， A _n 推出结论 B 是有效的，可表示为（ A ₁ ∧ A ₂ ∧…∧ A _n ）⇒ B 。

注意，⇒不是逻辑联结词，因而 A ⇒ B 不是公式，称 A ⇒ B 为 蕴涵关系式 。

例1.5.1 判断下列推理是否正确。

1） p ∧（ p → q ）⇒ q

2）（ p → q ）∧ q ⇒ p

解 写出 p ∧（ p → q ）→ q 和（ p → q ）∧ q → p 的真值表。

由真值表1.5.1可知， p ∧（ p → q ）→ q 是重言式，所以蕴涵关系式 p ∧（ p → q ）⇒ q 成立。而（ p → q ）∧ q → p 不是重言式，所以蕴涵关系式（ p → q ）∧ q ⇒ p 不成立。

在由前提推出结论时，如果所有前提为真，则结论为真。但是，推理的有效性并不保证推出的结论是真的，因为有效推理并没有要求所有前提的真值必须为真，当前提中包含假命题时，有效推理可能推出真值为假的结论。

例1.5.2 证明“如果牛吃草，则马会飞；马不会飞，所以牛不吃草”是正确的推理。

证明 设 p 表示“牛吃草”， q 表示“马会飞”。

上述推理问题的前提符号化为 p → q 、 ，结论符号化为 。因此，只需证明 是 p → q 和 的结论。

而

所以， 是 p → q 和 的结论，即蕴涵关系式 成立。尽管结论“牛不吃草”真值为假，这仍然是正确的推理，这个结论是有效的，得出这个真值为假的结论的原因是前提条件中的 p → q 的真值为假。

◀

有一些重要的蕴涵关系式，称为 推理定律 。这些蕴涵式如下。

定理1.5.1 对任意公式 A ₁ ， A ₂ ，…， A _n ， B ， C ，由 A ₁ ， A ₂ ，…， A _n 推出 B → C 是有效的，当且仅当由 A ₁ ， A ₂ ，…， A _n 和 B 推出 C 是有效的。

证明 根据定义1.5.1，有（ A ₁ ∧ A ₂ ∧…∧ A _n ）→（ B → C ）⇔1。

因为

所以（ A ₁ ∧ A ₂ ∧…∧ A _n ）→（ B → C ）是永真式，当且仅当（ A ₁ ∧ A ₂ ∧…∧ A _n ∧ B ）→ C 是永真式，即 A ₁ ， A ₂ ，…， A _n 和 B 推出 C 是有效的。

◀

该定理在证明推理问题时十分有用。根据该定理，如果需要推出结论的形式为 B → C ，则可以把 B 放在前提中，设法推出 C 即可。这是一条命题推理规则，称为 CP规则 。

1.5.2 推理证明方法

根据定义1.5.1，判断由前提 A 推出结论 B 的方法就是判断 A → B 是重言式的方法，可以采用不同的证明方法，下面是常用的证明方法，其中，真值表法、等价运算法是基本的方法。

通过写出真值表判断 A → B 的类型，若 A → B 是重言式，则由前提 A 可以推出结论 B 。

1.真值表法

例1.5.3 证明前提 p ∨ q 和 可以推出结论 q ∨ r 。

证明 根据定义1.5.1，只需证明 是重言式。

其真值表如表1.5.2所示。

由真值表可知， 是重言式，所以前提 p ∨ q 和 可以推出结论 q ∨ r 。

◀

2.等价演算法

利用命题的等值演算判断 A → B 的类型，若 A → B 是重言式，则由前提 A 可以推出结论 B 。

例1.5.4 证明 q 是 和 p ∨ q 的结论。

证明

当命题公式所含命题变元较多时，上述证明方法较为不便，因而常用演绎法证明推理的有效性。

◀

3.演绎法

演绎法从前提（假设）出发，依据公认的推理规则和推理定律推导出一个结论。在证明过程中，将前提和推理定律匹配，推出结论。判断推出的结论是否为需要证明的结论，如果是，则结束；如果不是，则把推出的结论加入前提集合中，构成一组新的前提，重复上述过程，直到推出需要证明的结论为止。演绎法证明推理问题就是用命题公式序列描述推理过程，其中的每个公式或者是前提，或者是由某些前提得出的结论。在这样的证明中需要引入下面的推理规则。

1）前提引入规则。在推导的过程中，可随时引入前提集合中的任意一个前提。

2）结论引入规则。在推导的过程中，所得到的结论都可作为后续推导的前提。

3）置换规则。在推导的过程中，命题公式的子公式都可以用等值的公式置换。

4）CP规则（附加前提规则）。如果推出的结论形为 P → Q ，则可以把 P 放到前提中去，设法推出 Q 即可。

这些规则与1.5.1节的推理定律和1.3.1节的基本等价公式作为推理和演绎的基础，可以构造一个完整的命题演算推理系统，证明命题逻辑的推理。

例1.5.5 证明（ p ∨ q ）∧（ p ↔ r ）∧（ q → s ）⇒ s ∨ r 。

证明

例1.5.6 证明，由前提“今天下午有课且今天比昨天冷；只有今天下午没有课，我们才去游泳；如果我们不去游泳，我们就去打篮球；如果我们打篮球，我们就会感到精力充沛”推出结论“我们感到精力充沛”是正确的。

证明 设 p 表示“今天下午有课”， q 表示“今天比昨天冷”， r 表示“我们去游泳”， s 表示“我们去打篮球”， h 表示“我们感到精力充沛”。

则前提为 p ∧ q ， ，结论是 h 。

例1.5.7 证明 是 p →（ q → r ）和 p ∧ q 的结论。

证明

4.附加前提证明法

根据CP规则，如果推出的结论形为 P → Q ，则可以把 P 放到前提中去，设法推出 Q 即可。

例1.5.8 证明 r → s 是 p →（ q → s ）、 、 q 的结论。

证明 根据CP规则，只需证明 s 是 r 、 p →（ q → s ）、 、 q 的结论。

以上证明方法又称 直接证明法 。在推理问题的构造证明中，有时采用间接证明的方法（又称归谬法）。

5.间接推演法（归谬法）

间接推演法就是把要推出的结论否定后与原来的前提一起使用推出矛盾结论的证明方法。

定义1.5.2 设 H ₁ ， H ₂ ，…， H _r 是 r 个命题公式。若 H ₁ ∧ H ₂ ∧…∧ H _r 是矛盾式，则称 H ₁ ， H ₂ ，…， H _r 是 不相容 的，否则称 H ₁ ， H ₂ ，…， H _r 是 相容 的。

如果公式 B 是由前提 H ₁ ， H ₂ ，…， H _r 推出的，则 是重言式，因此 是矛盾式，即 H ₁ ， H ₂ ，…， H _r ， 不相容。因而，若 H ₁ ， H ₂ ，…， H _r ， 不相容，则说明 B 是公式 H ₁ ， H ₂ ，…， H _r 的逻辑结论。这种将 B 作为附加前提推出矛盾的证明方法称为 间接推演法（归谬法） 。

例1.5.9 用间接法证明 p 是 的结论。

6.归结证明法

例1.5.10 证明 蕴涵结论 r 。

证明

在例1.5.10中利用了归结规则，称为 归结证明 。归结规则在基于逻辑规则的编程语言中扮演着重要角色。可以用归结规则构建自动定理证明系统。要使用归结规则构造命题逻辑中的证明，前提和结论必须被表示为子句，子句是变元或其否定的析取，如 p ∨ q 、 等是子句。对于非子句的公式，可以用一个或多个和它等价的子句替换它，如可以用 代替公式 p → q ；对于公式 p ∨（ q ∧ r ），因为 p ∨（ q ∧ r ）⇔（ p ∨ q ）∧（ p ∨ r ），可以用两个子句 p ∨ q 和 p ∨ r 代替 p ∨（ q ∧ r ）；可以用两个子句 和 代替 ，因为 。

例1.5.11 用归结规则证明下面的推理。

如果小张守门或小李上场，则 A 队获胜；或者 A 队未获胜，或者 A 队成为联赛第一名； A 队没有成为联赛第一名。因此小张没有守门并且小李没有上场。

证明 设 p 表示“小张守门”， q 表示“小李上场”， r 表示“ A 队获胜”， s 表示“ A 队成为联赛第一名”。

前提： 。

结论： 。

前提中的 ，用两个子句 和 代替（ p ∨ q ）→ r ，前提中的 和 是子句。结论 可以用两个子句 和 代替。 tFJpV7VxlOEvguyvc+caibEPGi7pyxgwmxCA4Jjfc6c8KHOtgDJNrADRD2WeAq45