12.2 布尔函数的表示.md

12.2 布尔函数的表示

极小项

这个不用管那么多，其实就是所有变元做布尔积。比如3个布尔元x,y,z：

x	y	z	xyz
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

可以看到这种情况下，只有所有变元都是1，最终结果才为1，其他情况下都是0。

构建布尔函数

在之前都是如果知道布尔函数，可以通过定理来化简布尔函数，但是如果只知道真值表，如何构建布尔函数呢？

比如下面的真值表：

x	y	z	F
1	1	1	0
1	1	0	0
1	0	1	1
1	0	0	0
0	1	1	0
0	1	0	0
0	0	1	0
0	0	0	0

如何构建这个真值表的布尔函数呢？

这里就可以用上面的极小项来实现了，因为我们看到结果中只有一个值为1，其他情况下都是0。所以我们可以得出式子为： $$ F(x,y,z)=x \overline{y} z，这里为什么是 \overline{y} 呢？因为当时其值为0，所以需要处理一下。 $$ 上面是有1个1，其他都是0，如果有2个1时：

x	y	z	G
1	1	1	0
1	1	0	0
1	0	1	1
1	0	0	0
0	1	1	0
0	1	0	1
0	0	1	0
0	0	0	0

我们就可以表示成2个极小项的和： $$ G(x,y,z)=x \overline{y}z+ \overline{x}y \overline{z} $$ 这样我们就可以根据真值表来构建布尔函数了。

---

这样除了可以用来构建布尔函数，也可以用来化简布尔函数： $$ F(x,y,z)=(x+y) \overline{z} $$ 如果是之前，就需要按照公式一步步拆下去，现在可以首先计算出真值表为：

x	y	z	F
1	1	1	0
1	1	0	1
1	0	1	0
1	0	0	1
0	1	1	0
0	1	0	1
0	0	1	0
0	0	0	0

套用上面的公式，我们可以直接得出： $$ F(x,y,z)=xy \overline{z}+ x\overline{y} \overline{z}+\overline{x}y\overline{z} $$ 跟直接套公式得出的结论是一致的。

函数的完备性

上面我们得出，只需要使用+,.,-就可以构建出所有的布尔函数，但是根据下面的公式（德.摩根率）： $$ \begin{cases} x+y &=\overline{ \overline{x}\overline{y} } \ xy &=\overline{ \overline{x}+\overline{y} } \end{cases} $$ 所以我们只需要+,-或者.,-就可以构建所有的布尔函数了，这就是函数的完备性。

那么可以更小一点吗？也可以，我们定义一个运算符号：|，其真值表如下：

x	y	|
0	0	1
0	1	1
1	0	1
1	1	0

$$ 这样的情况下：\\ \begin{cases} \overline{x} &=x|x \\ xy &= (x|y)|(x|y) \end{cases} $$

第二个式子可以用真值表来验证：

x	y	xy	(x|y)|(x|y)
0	0	1	1
0	1	1	1
1	0	1	1
1	1	0	0

|也可以表示为NAND，就是not and，就是在布尔积的基础上取其补值。

类似的还有一个NOR，就是not or，就是在布尔和的基础上取其补值。 $$ 表示为 \downarrow $$ 真值表为：

x	y	NOR
0	0	1
0	1	0
1	0	0
1	1	0

同时因为： $$ \begin{cases} \overline{x} &=x \downarrow x \ x+y &= (x \downarrow y) \downarrow (x \downarrow y) \end{cases} $$ 所以可以说NAND和NOR也具有函数完备性。