数字逻辑与数字电子布尔代数和逻辑函数的化简

布尔代数和卡诺图是研究数字电路的重要工具。布尔代数是研究由与、或、非三种基本逻辑运算所组成的各种逻辑关系的一种数学工具。它可用于逻辑函数式的变换和化简。卡诺图是一种经常用来化简逻辑函数式的好方法。

1 概念、公式、定理

1.1 基本逻辑关系与基本逻辑运算

与逻辑关系(例如有两个开关的串联电路)，与运算 P=A·B
或逻辑关系(例如两个开关并联的电路)，或运算 P=A+B
非逻辑关系(例如一个开关与一个电灯进行并联的电路)，非运算 P=Ā

拓展：

与非运算 $LaTeX: $\overline {A \cdot B}$$
或非运算 $LaTeX: $\overline {A+B}$$
与或非运算 $LaTeX: $\overline {AB+CD}$$
异或非运算 $LaTeX: $A \bigoplus B$$

1.1.1 关于异或运算

真值表
A	B	$LaTeX: A \bigoplus B$
0	0	0
0	1	1
1	0	1
1	1	0

由真值表推出： $LaTeX: A \bigoplus B=\overline AB+A\overline B$

推理：

$LaTeX: \overline {A \bigoplus B}=\overline {AB}+AB$ (由最小项的性质：一部分最小项之和的反等于另外那些最小项之和，推出，见最小项和最大项的性质)

$LaTeX: A \bigoplus 0=A \ A \bigoplus 1=\overline A \ A \bigoplus A=0 \ A \bigoplus \overline A=1$

1.2 逻辑变量与逻辑函数

逻辑表达式中的字母A、B、C等称为逻辑变量，每个变量只有“0”或“1”两种取值，相当于信号的有或无，电平的高低，器件的导通或截止。

布尔代数可以直接用于双值逻辑系统电路即数字电路的研究。

如果某变量P的取值依赖于其他变量A，B，C…，则称P为A，B，C…的逻辑函数，记为

P=P(A, B, C…）

逻辑函数也只有两种取值。

1.3 公式

1.3.1 常量之间的关系(运算法则)

0·0=0
0·1=0
1·1=1
0+0=0
0+1=1
1+1=1
$LaTeX: $\overline 0=1$$
$LaTeX: $\overline 1=0$$

1.3.2 变量与常量之间的关系

A·0=0
A+1=1
A·1=A
A+0=A
$LaTeX: A \cdot \overline A=0$
$LaTeX: A+ \overline A=1$

1.3.3 运算定律

交换律

A·B=B·A
A+B=B+A

结合律

(AB)C=A(BC)
(A+B)+C=A+(B+C)

分配律

A(B+C)=AB+AC
A+BC=(A+B)(A+C)

1.3.4 特殊定理

同一律

A·A=A
A+A=A

还原律

A求非两次仍是A

摩根定理

$LaTeX: \overline {A \cdot B}=\overline A+\overline B$
$LaTeX: \overline {A+B}=\overline A \cdot \overline B$

1.3.5 常用公式(形式定理)

并项法化简

$LaTeX: A \overline B+AB=A$

证明：

$LaTeX: A(\overline B + B) = A \cdot 1 = A$

吸收法化简

$LaTeX: A + AB = A$

证明：

$LaTeX: A + AB = A(1 + B) = A$

去因子法

$LaTeX: A+ \overline AB=A+B$

证明：

$LaTeX: A+ \overline AB = A+ \overline AB + AB = A + B(A + \overline A) = A + B \cdot 1 = A+B$

消项法

$LaTeX: AB + \overline AC + BC=AB + \overline AC$

证明：

$LaTeX: AB + \overline AC + BC = AB + \overline AC + (A+\overline A)BC = AB + \overline AC + ABC + \overline ABC = AB(1+C) + AC(1+B) = AB + \overline AC$

1.4 布尔代数的基本规则

1.4.1 代入规则

在任一含有变量A的布尔等式中，如果用另一个布尔函数F去代替所有的变量A，则等式仍然成立。

1.4.2 对偶规则

对偶变换：在一个布尔函数P，实行加乘互换，“0”、“1”互换，得到的新布尔式记为P',则称P‘为P的对偶式。例如：

$LaTeX: P = A + \overline BC + 0$

$LaTeX: P' = A \cdot (\overline B + C) \cdot 1$

对偶规则为：有一布尔等式，对等号两边实行对偶变换，得到的新布尔函数式仍然相等。

1.4.3 反演规则

设P为一布尔函数，如果把式中的“·”号改为”+“号，而”+“号改为“·”号，则称为加乘互换。如果把式中的”0“换为”1“，而”1“换为”0“，则称”0“”1“互换。如果把式中原变量改为反变量，而把反变量改为原变量，则称为原反互换。

反演规则可叙述为：在一布尔函数式P中，如果实行加乘互换，”0“”1“互换、原反互换，得到的新布尔式记为 $LaTeX: \overline P$ ，则 $LaTeX: \overline P$ 为P的反式或反函数。

反演规则可用来求原函数的反函数。例如：

$LaTeX: P = \overline A \cdot \overline B + CD$

$LaTeX: \overline P = (A + B) \cdot ( \overline C + \overline D)$

又如：

$LaTeX: P = A + \overline {B + \overline C + \overline {D + \overline E}}$

$LaTeX: \overline P = \overline A \cdot (B + \overline C + \overline {D + \overline E})$

一个布尔变量或布尔式的上方有不止一个反号时，只能去掉最外层的一个，即整个布尔式的反号。

1.4.4 展开规则

展开规则也可展开定理，主要有二个公式：

展开规则一：

$LaTeX: P(x_1, x_2, ..., x_n) = x_1P(1, x_2, ..., x_n) + \overline x_1P(0, x_2, ... , x_n)$

展开规则二：

$LaTeX: P(x_1, x_2, ..., x_n) = [x_1 + P(0, x_2, ..., x_n)][ \overline x_1 + P(1, x_2, ... , x_n)]$

2 用代数法化简布尔式

2.1 同一逻辑关系布尔式形式的多样性

一个布尔式除了与或型及或与型之外，还有与非与非型、或非或非型及与或非型。这些类型的转换问题将在后面介绍。同一类型的布尔式，例如常见的与或型，它的表现形式对于同一逻辑关系也有多种形式。

用实际电路实现逻辑关系时，总希望电路比较简单。一般来说，布尔式越简单，由此实现的电路也越简单。对于与或型布尔式，最简单就是布尔式中的与项最少，每一与项中变量也最少。

2.2 与或型布尔式的化简步骤

任意布尔式都可转化成与或型的布尔式。

转化步骤：

第一步，用公式 A + AB = A 进行检验，看是否存在可吸引项。

第二步，用公式 $LaTeX: A + \overline AB = A + B$ ，进行检验，看能否化简。

第三步，用公式 $LaTeX: AB + \overline AC + BC =AB + \overline AC$ ，进行检验，看有无可消去的与项。

在以上化简过程中，有时需使用其它定理进行变换。

例如：

$LaTeX: P = A + A \overline B \overline C + \overline ACD + \overline CE + \overline DE = A + \overline ACD + \overline CE + \overline DE = A + CD + \overline CE + \overline DE = A + CD + (\overline C + \overline D)E = A + CD + \overline {CD}E = A + CD +E$

2.3 合项法与配项法

合项法就是从两个与项中提出一个 $LaTeX: (A+\overline A)$ 的部分。

配项法与合项法相反，就是给某个与项乘 $LaTeX: (A+\overline A)$ 以寻找新的组合关系，使化简继续进行。例如：

$LaTeX: P\\=A\overline B+B\overline C+\overline BC+\overline AB\\=A\overline B(C+\overline C)+B\overline C(A+\overline A)+\overline BC+\overline AB\\=A\overline BC+A\overline {BC}+AB\overline C+\overline AB\overline C+\overline BC+\overline AB\\=(A\overline BC+\overline BC)+A\overline C(B+\overline B)+(\overline AB\overline C+\overline AB)\\=\overline BC+A\overline C+\overline AB$

如果 $LaTeX: (A+\overline A)$ 的位置不对， $LaTeX: (A+\overline A)$ 变量符号是选 $LaTeX: (B+\overline B)$ ，还是选 $LaTeX: (C+\overline C)$ ，选得不合适均不能奏效，因此必须要有相当的技巧。利用代数法化简，有时虽然很简单，但并不是都很方便和很快奏效的，有时看上去似乎已经不能再化简了，而实际上还可以化简。后面将介绍卡诺图的方法来弥补代数法的不足。

3 最小项和最大项

3.1 最小项的引出

逻辑函数的表示方法：真值表→表达式，真值表比较直观，但随着变量的增加描述困难，因此使用表达式来表示逻辑函数。

通过真值表写出表达式：

因为表达式都是表示为与或型的表达式，因此先查看真值表的结果中有几个结果为1的值，有几个就表示有几个与项。如下表，P有4个结果为1的值，则P的表达式有四个与项相或组成，即P=第1个与型+第2个与型+第3个与型+第4个与型组成。
同时每个与项都由A、B、C组成，请看表达式结果为1的哪一行，分别写出四个与项，例如，第2行，A为0，B为0，C为1，则第一个表达式为 $LaTeX: \overline {AB}C$ ，同理，后面三项分别为 $LaTeX: \overline AB\overline C$ 、 $LaTeX: A\overline {BC}$ 、 $LaTeX: ABC$ 。
因此P的表达式可表示为 $LaTeX: P=\overline {AB}C+\overline AB\overline C+A\overline {BC}+ABC$
要证明表达式的有效性，比较原始的方法是将表达式的真值表再列出来，如果和原真值表一值的话，就表示表达式是有效的。事实上，它本身就是正确的。
这种表达式的每一项均包含所有变量，因此这些与项就被定义为最小项。

真值表
A	B	C	P
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

3.2 最小项的定义

最小项的定义：n个变量的最小项是n个变量的乘积项，每个变量出现且仅出现一次，每个变量既可以是原变量，也可以是反变量。0对应变量的原变量的非值，1对应该原变量。最小项的数目是2ⁿ个，最小项用m_i表示。下标用最小项所对应的二进制码相应的十进制数表示。

3.3 最大项的定义

最大项的定义：n个变量的最大项是n个变量的逻辑和，全部变量都必须出现且仅出现一次，每个变量既可以是原变量，也可以是反变量。最大项与取值组合有一一对应的关系，0对应变量的原变量，1对应该原变量的非值。最大项的数目也是2ⁿ个，最大项用M_j表示。下标也用最大项对应的二进制码相应的十进制数表示。

3.4 最小项和最大项的性质

最小项的反是最大项，最大项的反是最小项。例如：

$LaTeX: \overline {\overline A\overline B\overline C}=\overline {m_0}=A+B+C=M_0$

$LaTeX: \overline {A+\overline B+\overline C}=\overline {M_3}=\overline ABC=m_3$

全部最小项之和恒等于“1”。
全部最大项之积恒等于“0”。
一部分最小项之和的反等于另外那些最小项之和。
两个不同的最小项之和恒等于“0”。
两个不同的最大项之和恒等于“1”。
与或标准型（标准与或式）。 $LaTeX: Y=\sum m_i=\sum m(0,1,4,6,7)=m_0+m_1+m_4+m_6+m_7$
或与标准型。 $LaTeX: Y=\sum M_i=\sum M(0,1,4,6,7)=M_0+M_1+M_4+M_6+M_7$

4 卡诺图化简法

4.1 卡诺图

4.1.1 卡诺图的画法

卡诺图通常为正方形或矩形均匀分成2ⁿ个小格，每个小格代表一个最小项，二个变量、三个变量的卡诺图见下图所示。三变量及比三多的变量的卡诺图的变量值应该按照：00，01，11，10的顺序来标示。掌握卡诺图的构成特点，就可以从印在表格旁边的AB、CD的“0”、“1”值直接写出最小项的文字符号内容。

4.1.2 卡诺图的特征

卡诺图上几何相邻的最小项逻辑上也相邻。
几何相邻，包括相接和行或列首尾相接。
逻辑相邻，两个最小项中只有一个变量出现的形式不同。

4.1.3 邻接与化简

由于卡诺图中最小项的排列满足上述关系，所以可以用来化简。因为在最小项相加时，相邻两项可以进行合并，从而消去一个变量。以四变量为例，m₁₂与m₁₃相邻接，则m₁₂+m₁₃为：

$LaTeX: AB\overline {CD}+AB\overline CD=AB\overline C(\overline D+D)=AB\overline C$

规律：如果两邻接的最小项中有变化的变量时，可以直接消除此变量。

4.2 逻辑函数如何填入卡诺图

4.2.1 与项如何填入卡诺图

4.2.1.1 与项是最小项的形式

例如，将逻辑式 $LaTeX: P(A,B,C)=\overline {AB}C+AB\overline C$ 填入卡诺图。它为一个三变量的逻辑式。结果见下图：

将逻辑式中的最小项对应与卡诺图上的最小项，并在其中填入1，即与项是最小项时，按最小项编号的位置直接填入。

4.2.1.2 与项不是最小项的形式

与项不是最小项的形式，按邻接关系直接填入卡诺图。例如： $LaTeX: P(A,B,C,D)=\overline ACD+ABD$ ，即依据邻接与化简，将一项变成最小项相邻接的方式，然后直接填入两个最小项即可， $LaTeX: \overline ACD=\overline A(B+\overline B)CD=\overline ABCD+\overline {AB}CD$ ，则在 $LaTeX: \overline ABCD$ 和 $LaTeX: \overline {AB}CD$ 上填入1即可。

与项中变量数越少，在卡诺图中占的小格越多；最小项在卡诺图中占1个小格；与最小项相比，少一个变量占二个小格；少二个变量占四个小格；少三个变量占八个小格，……。

卡诺图中的与项对应的小格，只能一个一组；二个一组；四个一组；八个一组，……，即按2ⁱ的规律组成矩形带；与项只有二个变量，即缺2个变量，应占2²个小格，且组成一个矩形带；与项只有三个变量，即缺1个变量，应占2¹个小格，且组成一个矩形带。

我们的任务是化简逻辑函数，将与或型逻辑函数填入卡诺图后，这样原来的逻辑函数就以最小项的面貌出现在卡诺图中。然后，经过重新组合，将具有“1”的小格按照2ⁱ的规律尽可能大地圈成矩形带。这样新得到的逻辑函数可能会更简单一些。

4.3 卡诺图化简法

也就是如何重新组合带有“1”的小格，如何尽可能大地圈成矩形带，以得到最简与或逻辑式。

4.3.1 如何使与项最简

卡诺图中的矩形带包括的小格越多，对应的与项的变量数就越少，所以一个需要化简的逻辑函数，填入卡诺图后，经过重新组合，圈出的矩形带应越大越好。为使与项最简，圈矩形带时，小格可以公用，互相覆盖。

4.3.2 关于覆盖

在小格覆盖时，需要注意，每一个矩形带中至少要一有一个小格是独立的，即没有被其他矩形带所覆盖。

5 参见

数字逻辑与数字电子绪论
数字逻辑与数字电子视频王立欣
逻辑函数的化简法之二：卡诺图化简法. 广电电器网. 2006-03-01.

数字逻辑与数字电子 布尔代数和逻辑函数的化简

目录