基本简化技术：代数法和卡诺法 Techniques de simplification élémentaires : méthode algébrique et méthode de Karnaugh

代数方法

函数的表达式可以从其真值表中获得：我们搜索真值表中函数等于 1 的行，并在它们之间添加与这些行中的每一行对应的最小项（对于变量的每个组合），如果在真值表的相应行中 a = 1，我们记下变量的名称 a，如果 a = 0，我们记下它的补码 a）。因此，获得的表达式是小项之和。然后可以利用布尔代数的性质获得布尔表达式的简化

以以下真值表为例：

第一个最小项是第二行，$a,b,c,d$分别对应$0,0,0,1$，由此可以写出第一项为：$\bar{a} \cdot \bar{b} \cdot \bar{c} \cdot d$。通过这种方法可以最终写出：

$S=\bar{a} \cdot \bar{b} \cdot \bar{c} \cdot d+\bar{a} \cdot \bar{b} \cdot c \cdot d+\bar{a} \cdot b \cdot c \cdot d+a \cdot b \cdot c \cdot d+a \cdot b \cdot c \cdot \bar{d}+a \cdot \bar{b} \cdot c \cdot \bar{d}+a \cdot \bar{b} \cdot c \cdot d+a \cdot \bar{b} \cdot \bar{c} \cdot d$

然后我们要进行化简：

图中公式对应：

$(1.9)$: $ab+ac = a(b+c)$
$(1.7)$: $a\cdot 1 = a$
$(1.12)$: $a+\bar a = 1$
$(1.18)$: $a+\bar a b = a+b$

最终得到最简的结果：

$S=\bar{b} \cdot d+c \cdot d+a \cdot c$

卡诺方法 Méthode de Karnaugh

介绍

我们以一个具有8个布尔变量的函数为例，我们将4个变量作为列标签，这对应16列，注意这里使用的是格雷码：

如果我们定义$\mathcal{E}x(x \in{a, b, c, d, \bar{a}, \bar{b}, \bar{c}, \bar{d}})$，将所有某个变量k为真对应的列记为$\mathcal{E}_k$，为假的列记为$\mathcal{E}{\bar k}$。例如：

$\mathcal{E}_{\bar{d}}={1} \cup [ 4,5 ] \cup [ 8,9 ] \cup [ 12,13 ] \cup{16}$
$\mathcal{E}_d=[ 2,3 ] \cup [ 6,7 ] \cup [ 10,11 ] \cup [ 14,15 ]$

有：$\mathcal{E}_{\bar{d}}=[ 1,16 ]-\mathcal{E}_d$

由此，我们可以通过这些元素的交集来表示任何一列或者几列：

$\{2\}=[ 2,3 ] \cap([ 1,2 ] \cup [ 7,10 ] \cup [ 15,16 ])=\mathcal{E}_{\bar{a} \cdot \bar{b} \cdot d} \cap \mathcal{E}_{\bar{c}}=\mathcal{E}_{\bar{a} \cdot \bar{b} \cdot \bar{c} \cdot d}$

更进一步的，我们可以直接用表示每一组框。

随后可以通过使用此方法对卡诺表中 S = 1 的所有框进行分组来确定 S 的简化代数表达式，然后以和的形式表示 S（在意义上逻辑中）术语）对应于这些分组中的每一个的代数表达式。

八行八列的例子

例如，考虑下图中的卡诺表，它表示 8 个布尔变量 a、b、c、d、e、f、g、h 的函数 S。

我们首先对这些S = 1的框分组：

第一组包括8个框，对应两个列和四个行的并集，两个列对应3个变量，四个行对应两个变量。两个列与$c$无关，因此对应$\bar a, b, \bar d$ 。四个行与fg无关，因此对应$\bar e,\bar h$

因此对应表达式：$\bar{a} \cdot b \cdot \bar{d} \cdot \bar{e} \cdot \bar{h}$
第二组同样包括16个框，包括四个行和四个列

同样的方式可以确定表达式为：$\bar{b} \cdot \bar{d} \cdot e \cdot \bar{g}$
最终的表达式为：$S=\bar{a} \cdot b \cdot \bar{d} \cdot \bar{e} \cdot \bar{h}+\bar{b} \cdot \bar{d} \cdot e \cdot \bar{g}$

四行四列的例子

普通的

$S=\bar{b} \cdot d+c \cdot d+a \cdot c$
$\begin{aligned}
S & =\overline{\bar{c} \cdot \bar{d}+b \cdot \bar{c}+\bar{a} \cdot \bar{d}}=\overline{\bar{c} \cdot \bar{d}} \cdot \overline{b \cdot \bar{c}} \cdot \overline{\bar{a} \cdot \bar{d}}=(c+d) \cdot(\bar{b}+c) \cdot(a+d) \
& =(c+\bar{b} \cdot d) \cdot(a+d)=a \cdot c+c \cdot d+a \cdot \bar{b} \cdot d+\bar{b} \cdot d=a \cdot c+c \cdot d+\bar{b} \cdot d
\end{aligned}$

特殊的

可以看到第一幅图似乎a,b都没有影响，但这是错误的，我们应该注意到a,b不能取到相同的值，因此，应将其表示为：$(a \oplus b)$。因此第一幅图对应：$S=(a \oplus b) \cdot(\overline{c \oplus d})$
第二幅更加简单：$S=(a \oplus b) \cdot \bar{c}$