析取范式

前两章学过真值表和命题演算，用于处理以下问题：

• 一个公式的类型是什么？
• 两个公式是否等值？

本章要处理的问题是：

• 真值函数有没有对应的标准公式？
• 公式有没有标准的等值形式？

析取取式

变项及其否定统称为文字。如：

\[p,\ ¬p\]

有限个文字构成的合取式称作简单合取式。如：

\[¬p ∧ q\]

由有限个简单合取式构成的析取式称为析取范式。如

\[(¬p ∧ q) ∨ (p ∧ ¬q)\]

可以看出，析取范式的功能完备集是 $\{¬, ∧, ∨\}$。

求析取范式的步骤

任何公式都可以化为析取范式，步骤如下：

1. 消去联结词 $↔$ 和 $→$（蕴涵等值式、等价等值式）。
2. 内移或消去 $¬$（德·摩根律、双重否定律）。
3. 将括号内的 $\lor$ 提出来（分配律）。

例如求下面公式的析取范式：

\[(¬p → q) ∧ (p → r)\]

计算过程如下：

\[\begin{align} &\quad\enspace (¬p → q) ∧ (p → r) \\ &⇔ (¬¬p ∨ q) ∧ (¬p ∨ r) &\text{蕴涵等值式} \\ &⇔ (p ∨ q) ∧ (¬p ∨ r) &\text{双重否定律} \\ &⇔ (p ∧ ¬p) ∨ (q ∧ ¬p) ∨ (p ∧ r) ∨ (q ∧ r) &\text{分配律} \end{align}\]

极小项

极小项是满足以下条件的简单合取式：

• 变项及其否定不同时出现。
• 变项及其否定必有一个出现。
• 第 $i$ 个变项或其否定出现在从左算起的第 $i$ 位上。

以 $p$ 和 $q$ 生成的极小项为：

极小项	二进制	十进制	记作
$¬p ∧ ¬q$	00	0	$m_0$
$¬p ∧ q$	01	1	$m_1$
$p ∧ ¬q$	10	2	$m_2$
$p ∧ q$	11	3	$m_3$

$n$ 个变项可生成 $2^n$ 个极小项。

主析取范式

设公式 A 中含有 $n$ 个命题变项，若 A 的析取范式中的简单合取式全都是极小项，则称该析取范式为 A 的主析取范式。

任何公式的主析取范式都是存在的，并且是唯一。

补充

相应地，每个公式有对应的主合取范式，定义的方式和主析取范式类似，这里不再展开。