5.7.6 正规形式

1. 基本合取、基本析取

设 $B=\{B,\cap ,\cup ,\mathrm{\neg };0,1\}$ 是一个布尔代数, $\left\{x_1,\cdots ,x_n\right\}$ 是一组布尔变量. 每个合取或析取,若其中每个变量或其否定恰出现一次,则分别称为 (变量 $x_1,\cdots ,x_n$ 的) 基本合取或基本析取.

设 $T\left(x_1,\cdots ,x_n\right)$ 是一个布尔表达式. 若基本合取的析取 $D$ 满足 $D=T$ ,则称它为 $T$ 的主析取正规形式 (PDNF). 若基本析取的合取 $C$ 满足 $C=T$ ,则称它为 $T$ 的主合取正规形式 (PCNF).

• 部分 1 为了说明每个布尔函数 $f$ 可以表示为一个布尔表达式,我们来构造附表中给出的函数 $f$ 的 PDNF 形式:

布尔函数 $f$ 的 PDNF 含有基本合取 $\overline{x}\sqcap \overline{y}\sqcap z,x\sqcap \overline{y}\sqcap z,x\sqcap y\sqcap \overline{z}$ . 这些基本合取属于使得函数 $f$ 取值 1 的那些变量的赋值 $b$ . 如果变量 $v$ 在 $b$ 中有值 1,那么 $v$ 就实施基本合取,不然 $\overline{v}$ 实施基本合取.

	$x$	$y$	$z$	$f\left(x,y,z\right)$
	0	0	0	0
	0	0	1	1
	0	1	0	0
	0	1	1	0
	1	0	0	0
	1	0	1	1
	1	1	0	1
	1	1	1	0

• 部分 2 对于部分 1 中的例子, PDNF 是

$$\begin{array}{}\text{(5.312)}& \left(\overline{x}\sqcap \overline{y}\sqcap z\right)\bigsqcup \left(x\sqcap \overline{y}\sqcap z\right)\bigsqcup \left(x\sqcap y\sqcap \overline{z}\right).\end{array}$$

PDNF 的 “对偶” 形式是 PCNF: 基本析取属于函数 $f$ 取值 0 的那些变量的赋值 $b$ .

如果变量 $v$ 在 $b$ 中有值 0,那么 $v$ 就实施基本析取,不然 $\overline{v}$ 实施基本析取. 于是 PCNF 是

$$\begin{array}{}\text{(5.313)}& \left(x\bigsqcup y\bigsqcup z\right)\sqcap \left(x\bigsqcup \overline{y}\bigsqcup z\right)\sqcap \left(x\bigsqcup \overline{y}\bigsqcup \overline{z}\right)\sqcap \left(\overline{x}\bigsqcup y\bigsqcup z\right)\sqcap \left(\overline{x}\bigsqcup \overline{y}\bigsqcup \overline{z}\right).\end{array}$$

如果变量的顺序和赋值的顺序给定, 即如果将赋值考虑为二进数并且将它们按递增顺序排列,那么 $f$ 的 PDNF 和 PCNF 是唯一确定的.

2. 主正规形式

将布尔函数 $f_T$ 的主正规形式看作对应的布尔表达式 $T$ 的主正规形式.

通过变换检验两个布尔表达式的等价性通常是困难的. 主正规形式是有用的: 如果两个布尔表达式所对应的唯一确定的主正规形式是按字母逐个恒等的, 那么它们确实是语义等价的.

• 部分 3 在考虑的例子 (见部分 1 和部分 2) 中,表达式 $\left(\overline{y}\sqcap z\right)\bigsqcup \left(x\sqcap y\sqcap \overline{z}\right)$ 和 $\left(x\bigsqcup \left(\left(y\bigsqcup z\right)\sqcap \left(\overline{y}\bigsqcup z\right)\sqcap \left(\overline{y}\bigsqcup \overline{z}\right)\right)\right)\sqcap \left(\overline{x}\bigsqcup \left(\left(y\bigsqcup z\right)\sqcap \left(\overline{y}\bigsqcup z\right)\right)\right)$ 是语义等价的,因为两者的主析取 (或合取) 正规形式是相同的.