第3章布尔代数基础

布尔代数得名于英国数学家乔治·布尔（George Boole，1815—1864）。为了研究人的逻辑思维规律，他在1847年发表的《逻辑的数学分析》和1854年发表的《思维规律的研究》两部著作中，首先提出了这种代数的基本概念和性质。此后，大约经过100年之久，于1938年才由克劳德·香农（Claude E．Shannon）将布尔代数应用于电话继电器的开关电路中。至今，布尔代数已成为分析和设计开关电路的重要数学工具。

本章不是从数学的角度去研究布尔代数，而是从应用的角度介绍布尔代数的一些基本概念、基本定理、布尔函数的基本形式以及布尔函数的化简方法，以使读者掌握分析和设计数字逻辑网络所需的数学工具。

3．1布尔代数的基本概念

计算机或其他数字系统无论多么复杂，它们都是由若干种最简单的、最基本的电路（如门电路、触发器等）所组成的。这些电路的工作具有下列基本特点： 从电路内部看，或是管子导通，或是管子截止； 从电路的输入输出看，或是电平的高低，或是脉冲的有无。由于这种电路工作在开关状态，故称为开关电路。开关电路的工作状态可以用二元布尔代数来描述，故二元布尔代数通常称为开关代数，或称为逻辑代数。因此，逻辑代数只是布尔代数的一种特例。在本书中，如无特别说明，布尔代数均指逻辑代数。

3．1．1布尔变量及其基本运算

布尔代数和普通代数一样，用字母代表变量，布尔代数的变量称为布尔变量。和普通代数不同的是，布尔变量只有两种取值，即0或1。并且，常量0和1没有普通代数中的0和1的意义，它只表示两种可能，即命题的“假”和“真”，信号的“无”和“有”等。

布尔代数中的变量运算只有“或”“与”“非” 3种基本运算，任何复杂的逻辑运算都可以通过这3种基本运算来实现。

1. “或”运算

“或”运算又称为逻辑加。两个变量“或”运算的逻辑关系可表示为
F=A+B
式中，“+”号是“或”运算符。上式读作“F等于A或B”，或者“F等于A加B”，其意思是变量A和B中只要有一者取值为1，则F就为1； 若A和B全为0，则F为0。其逻辑关系可以用真值表来描述，如表3.1所示。


2. “与”运算

“与”运算又称为逻辑乘。两个变量的“与”运算的逻辑关系可表示为：
F=A·B

式中“·”号表示“与”运算符。通常，“与”运算符可以省略。上式读作“F等于A与B”，或者“F等于A乘B”。其含义是只有当变量A与B都为1时； F才为1； 否则，F就为0。其逻辑关系可以用真值表来描述，如表3.2所示。



表3.1“或”运算



A
B
F
0
0
0
0
1
1
1
0
1
1
1
1


表3.2“与”运算



A
B
F
0
0
0
0
1
0
1
0
0
1
1
1


3. “非”运算

“非”运算又称为逻辑取反。对一个变量的“非”运算的逻辑关系可表示为： 
F＝
式中“-”号表示“非”运算符。上式读作“Ｆ等于A的非”，其意思是若A为1，则Ｆ为0； 反之，若Ａ为0，则Ｆ为1。“非”运算的逻辑关系可以用表3.3所示的真值表来描述。


表3.3“非”运算



A
F
0
1
1
0



综合上述对布尔变量及其3个基本运算的定义，我们可以对布尔代数下个定义： 

布尔代数是一个由布尔变量集K，常量0、1以及“或”“与”“非” 3种运算符所构成的代数系统，记为
B＝（K，＋，· ，－，0，1）
其中，布尔变量集K是指布尔代数中的所有可能变量的集合，它可用任何字母表示，但每一个变量的取值只可能为常量0或1，而且布尔代数中的变量只有“或”“与”“非” 3种运算。

3．1．2布尔函数及其表示方法

布尔代数中的函数定义与普通代数中函数定义十分相似，可以叙述如下。

设（x1，x2，…，xn）为布尔代数的一组布尔变量，其中每个变量取值为0或1，则当把n序列（x1，x2，…，xn）映射到B＝{0，1}时，这个映射就是一个布尔函数。

从另一个角度，把布尔函数与逻辑网络联系起来，布尔函数可以这样叙述： 

设某一逻辑网络的输入变量为x1,x2,…,xn，输出变量为F，如图3.1所示。对应于变量x1,x2,…,xn的每一组确定值，F就有唯一确定的值，则称F是变量x1,x2,…,xn的布尔函数。记为
F＝f(x1，x2，…，xn）


图3.1布尔函数


注意，布尔代数中函数的取值也只可能是0或1，这与普通代数是不同的。

布尔函数的表示方法有3种形式： 布尔表达式、真值表和卡诺图。这与普通代数中用公式、表格和图解这3种方法来表示函数十分类似。

1.  布尔表达式


布尔表达式是由布尔变量和“或”“与”“非” 3种运算符所构成的式子，这是一种用公式表示布尔函数的方法。例如，要表示这样一个函数关系： 当两个变量A和B取值相同时，函数取值为0； 否则，函数取值为1。此函数称为异或函数，可以用下列布尔表达式来表示： 
F＝f（A，B）＝B＋A
显然，只要将A 和B 的4种可能取值代入这表达式，验证是正确的。

与异或函数相反，当两个变量A和B取值相同时，函数取值为1； 否则，函数取值为0。此函数称为同或函数。通常，异或运算用符号表示； 同或运算用⊙表示。因此，异或函数、同或函数可分别表示成： 
F＝B＋A＝AB； F＝＋A B＝A⊙B
2.  真值表

真值表是由输入变量的所有可能取值组合及其对应的输出函数值所构成的表格，这是一种用表格表示布尔函数的方法。例如，对于前面的异或函数，可以用表3.4所示的真值表来表示。


表3.4异或函数的真值表



A
B
F
0
0
0
0
1
1
1
0
1
1
1
0


真值表中的变量为两个，共有22种取值组合，所以该表由4行组成。当变量为n个时，真值表就由2n行组成。显然，随着变量数目的增加，真值表的行数将急剧增加。因此，一般当变量数目不超过4个时，用真值表表示函数比较方便。


3. 卡诺图

卡诺图是由表示逻辑变量的所有可能取值组合的小方格所构成的图形，如图3.2所示。图中分别表示了二变量及三变量的卡诺图。


利用卡诺图，可以很方便地表示一个函数。只要在那些使函数值为1的变量取值组合所对应的小方格上标记1，便得该函数的卡诺图。例如，对于异或函数，可以用图3.3所示的卡诺图来表示。




图3.2卡诺图




图3.3异或函数的卡诺图



卡诺图可以看成是真值表的重新排列，真值表的每一行用一个小方格来表示。当变量为两个时，真值表有4行，相应的卡诺图有4个方格； 当变量为n个时，卡诺图有2n个方格。卡诺图的这种方格排列方式比真值表更紧凑，而且便于进行函数的化简。

3．1．3布尔函数的“相等”概念

布尔函数和普通代数一样，也有函数相等的问题。两个函数相等的定义如下。

设有两个布尔函数
F＝f(x1，x2，…，xn）
G＝g(x1，x2，…，xn）
其变量都为x1，x2，…，xn。如果对应于变量x1，x2，…，xn的任何一组变量取值，F和G的值都相同，则称F和G是相等的，记为F＝G。


显然，若两个布尔函数相等，则它们的真值表一定相同； 反之，若两个布尔函数的真值表完全相同，则此两个函数相等。因此，要证明两个布尔函数是否相等，只要分别列出它们的真值表，看其是否相同。

例如，已知下列两个函数
Ｆ＝ xy，Ｇ＝ x-＋y-
列出Ｆ和Ｇ的真值表，如表3.5所示。由表可知，它们的真值表完全相同，故Ｆ和Ｇ是相等的，即有
xy＝x-＋y-



表3.5F＝xy和G＝x-＋y-的真值表



x
y
xy
F＝xy
x-
y-
G＝x-＋y-
0
0
0
1
1
1
1
0
1
0
1
1
0
1
1
0
0
1
1
1
1
1
1
1
0
0
0
0

3．2布尔代数的公式、定理和规则
3．2．1布尔代数的基本公式


根据布尔变量的取值只有0和1，以及布尔变量仅有的3种运算的定义，不难推出下列基本公式。

（1） 交换律
Ａ＋Ｂ＝Ｂ＋Ａ
Ａ·Ｂ＝Ｂ·Ａ
（2） 结合律
（Ａ＋B）＋Ｃ＝Ａ＋（B＋C）
 （Ａ·B）·C＝Ａ·（B·C）
（3） 分配律
Ａ·（B＋C）＝Ａ·B+Ａ·C
A＋B·C＝（Ａ＋B）（Ａ＋C）
（4） 01律
Ａ＋０＝Ａ
Ａ＋１＝１
Ａ·０＝0
Ａ·１＝A

（5） 互补律
Ａ＋＝１
Ａ·＝0
（6） 等幂律
Ａ＋A＝Ａ
Ａ·Ａ＝A
（7） 吸收律
A＋AB＝Ａ
Ａ＋Ｂ＝Ａ＋Ｂ
A（Ａ＋B）＝Ａ
Ａ（＋Ｂ）＝AB
（8） 对合律（双重否定律）
A=＝A
以上是布尔代数的基本公式。其中交换律、结合律、分配律、01律、互补律和对合律可以作为布尔代数的公理。公理是代数系统的基本出发点，是客观存在的抽象，它无须证明，但它可以用客观存在来验证。以此为基础，可以推得布尔代数的等幂律与吸收律。例如，等幂律的证明如下： 
A＋A＝（A＋A）·1（ 01律）
＝（A＋Ａ）（Ａ＋）（互补律）
＝ A＋A·（分配律）
＝ A+0（互补律）
＝ Ａ（01律）
又如，吸收律的证明如下： 
A＋B＝（Ａ＋）（A＋B）（分配律）
＝1·（Ａ＋B）（互补律）
＝A＋B（01律）
必须指出，上述基本公式中，有些公式与普通代数中的相同，如交换律、结合律，但有些公式却是布尔代数中所特有的，如分配律。 

3．2．2布尔代数的主要定理

定理3.1德·摩根（De Morgan）定理。

（1）  x1+x2+…+xn=x-1·x-2·…·x-n

（2） x1·x2·…·xn=x-1+x-2+…+x-n

这就是说，n个变量的“或”的“非”等于各变量的“非”的“与”，n个变量的“与”的“非”等于各变量的“非”的“或”。

当变量数目较少时，该定理可很容易用真值表证明。当变量为n个时，则可以用数学归纳法证明。

德·摩根定理是布尔代数中一个很重要且经常使用的定理，它提供了一种变换布尔表达式的简便方法。由于它具有反演特性，即把变量的与运算改成或运算，或运算改成与运算，所以又称为反演律。

定理3.2香农（Shannon）定理。
f(x1，x2，…，xn，0，1，+，·)=f(x-1，x-2，…，x-n，1，0，·，+)
这就是说，任何函数的反函数（或称补函数），可以通过对该函数的所有变量取反，并将常量1换为0，0换为1，运算符“＋”换为“·”，“·”换为“＋”而得到。

证明根据德·摩根定理，任何函数的反函数可写成
f(x1，x2，…，xn，0，1，+，·)
＝f1(x1，x2，…，xn，0，1，+，·)+f2(x1，x2，…，xn，0，1，+，·)
＝f1(x1，x2，…，xn，0，1，+，·)· f2(x1，x2，…，xn，0，1，+，·)
或写成
f(x1，x2，…，xn，0，1，+，·)
＝f1(x1，x2，…，xn，0，1，+，·)·f2(x1，x2，…，xn，0，1，+，·)
＝f1(x1，x2，…，xn，0，1，+，·)+ f2(x1，x2，…，xn，0，1，+，·)

其中，f1和f2是f的两个部分函数。对f1和f2重复上述过程，直到使f中的每个变量都用德·摩根定理。由于每对f（或f的部分函数）应用一次德·摩根定理，就将部分函数（或子部分函数）取反，并将“与”“或”运算变换一次，以求得函数f（或部分函数）的反函数f-，因此，当对f的每个变量进行德·摩根变换后，其结果必然是f(x-1，x-2，…，x-n，1，0，·，+)，证毕。

香农定理实际上是德·摩根定理的推广，它可以用在任何复杂函数。

【例3.1】已知函数Ｆ＝B＋A(Ｃ＋)，求其反函数。
= B+A(C+)= B·A(C+)
=(A+)·(A+C+)=(A+)((+B)+D)
利用香农定理，可以直接写出
＝（Ａ＋）·（＋Ｂ＋Ｄ）
定理3.3展开定理。

(1) f(x1，x2，…，xi，…，xn）

＝xi f(x1，x2，…，１，…，xn）＋x-if(x1，x2，…，０，…，xn）

(2) f(x1，x2，…，xi，…，xn）

＝（xi ＋f(x1，x2，…，０，…，xn）) ·（x-i＋f(x1，x2，…，１，…，xn）)

这就是说，任何布尔函数都可以对它的某一变量xi展开，或展开成（1） 所示的“与或”形式，或展开为（2） 所示的“或与”形式。

证明将xi＝1，x-i＝0代入上式，再将xi＝0，x-i＝1代入上式，则两种情况下等式均成立。证毕。

由展开定理可得下列两个推理。

推理3.1

（a） xi f(x1，…，xi，…，xn）＝xi f(x1，…，1，…，xn）

（b） xi ＋f(x1，…，xi，…，xn）＝xi＋f(x1，…，0，…，xn）

推理3.2

（a） xif(x1，…，xi，…，xn）＝xif(x1，…，0，…，xn）

（b） xi＋f(x1，…，xi，…，xn）＝xi＋f(x1，…，1，…，xn）

下面举例说明展开定理的应用。

【例3.2】证明公式AB＋C＋BC＝AB＋Ｃ（包含律）。

用展开定理，等号左边可展开成
左边＝A（1·B＋0·C＋BC）＋（0·B＋1·C＋ＢＣ）
＝A（B＋BC）＋（C＋BC）＝AB＋C＝右边证毕
【例3.3】将函数F＝＋AC表示成“或与”形式。

由展开定理，可得
F＝［A＋（1·＋0·C）］·［＋（0·＋1·C）］＝（A＋）（＋C）
3．2．3布尔代数的重要规则

布尔代数有3个重要规则，即代入规则、反演规则和对偶规则，现分别叙述如下。

1. 代入规则

任何一个含有变量x的等式，如果将所有出现x的位置，都代之以一个布尔函数F，则等式仍然成立。这个规则称为代入规则。

由于任何一个布尔函数也和任何一个变量一样，只有0或1两种取值，显然，以上规则是成立的。

【例3.4】已知等式A+B＝·，函数F＝B＋C，若用F代入此等式中的B，则有
A+(B+C)＝·B+C
A+B+C＝··
据此可以证明n变量的德·摩根定理的成立。

2. 对偶规则

任何一个布尔函数表达式F，如果将表达式中的所有的“＋”改成“·”，“·”改成“＋”，“1”改成“0”，“0”改成“1”，而变量保持不变，则可得到一个新的函数表达式Fd，我们称Fd为F 的对偶函数，这一规则称为对偶规则。例如，下列为几个原函数及其对偶函数：  

F＝B＋AFd＝（＋B）（A＋＋）

F＝A（＋CD）＋EFd＝［A＋（C＋D）］·E

F＝（A＋0）·（B＋C·1）Fd＝A·1＋B·（C＋0）

F＝A＋B++D+Fd＝A·B·C·D·E

需要注意的是，在运用对偶规则求对偶函数时，必须按照先“与”后“或”的顺序，否则容易写错，如F＝B＋A，若求出对偶函数Fd＝＋B·A＋＋，是错误的。因此，要特别注意原来函数中的“与”项，当这些“与”项变为“或”项时，应加括号。

从上面这些例子可以看出，如果F 的对偶函数为Fd，则Fd的对偶函数就是F。 也就是说，F 和Fd互为对偶函数，即（Fd）d= F。

由布尔代数的基本公式可以看出，它们都是成对出现的互为对偶的等式。由此证明一个规则： 如果两个函数的表达式相等，则它们的对偶函数也相等，即如果函数F=G, 则其对偶函数Fd＝Gd。

3. 反演规则

任何一个布尔函数表达式F，如果将表达式中的所有的“＋”改成“·”，“·”改成“＋”，“1”改成“0”，“0”改成“1”，原变量改成反变量，反变量改成原变量，则可得函数Ｆ的反函数（或称补函数），这个规则称为反演规则。

实际上，反演规则就是香农定理。运用反演规则可以很方便地求一个函数的补函数。例如，下列为几个原函数及其补函数： 

F＝B＋A＝（A＋）（＋B＋C）

F＝A（＋CD）＋E＝［＋B（＋）］·

F＝（A＋0）·（B＋C·1）＝·1＋·（＋0）

F＝A＋B++D+＝··C·D·E


与求对偶函数一样，求补函数需要注意的是，在运用反演规则时，必须按照先“与”后“或”的顺序进行变换。因此，特别要注意原来函数中的“与”项，当这些“与”项变换为“或”项时，应加括号。 

把上述补函数的例子与前面对偶函数的例子对照一下，可以看出，补函数和对偶函数之间在形式上只差变量的“非”。因此，若已求得一函数的对偶函数，只要将所有变量取反便得该函数的补函数； 反之亦然。

3．3布尔函数的基本形式

一个布尔函数的表达式可以有多种表示形式，本节讨论几种基本形式，它们是进行布尔函数化简的基础。

3．3．1函数的“积之和”与“和之积”形式

根据展开定理，任何一个n变量函数总可以展开成“与或”形式，或者“或与”形式。其中“与或”形式又称为“积之和”形式，而“或与”形式又称为“和之积”形式。

所谓“积之和”，是指一个函数表达式中包含若干个“积”项，其中每个“积”项可有一个或多个以原变量或反变量形式出现的字母，这些“积”项的“和”就表示了一个函数。例如，一个三变量函数为
F（A，B，C）＝+B+AC
其中，、B、AC均为“积”项。这些积项的和，就表示了函数的“积之和”形式。

所谓“和之积”，是指一个函数表达式中包含若干个“和”项，其中每个“和”项可有一个或多个以原变量或反变量形式出现的字母，这些“和”项的“积”就表示一个函数。例如，一个四变量函数为
F（A，B，C，D）＝（A＋B）（C+）（＋B＋C）
其中，（A＋B）、（C+）、（＋B＋C）均为“和”项，这些“和”项的“积”就构成了函数的“和之积”形式。

当然，布尔函数还可表示成其他形式。例如，上述四变量函数还可表示成
F（A，B，C，D）＝（AC＋B）（CD＋）＝（AC＋B）CD＋（AC＋B）
这种表示形式既不是“积之和”形式，又不是“和之积”形式，但它可以转换成后两种形式。

一个函数可以有多种表示形式，那么能不能找到统一的表示形式呢？有两种统一的标准形式。

3．3．2函数的“标准积之和”与“标准和之积”形式
1. 标准积之和


所谓标准积，是指函数的积项包含了函数的全部变量，其中每个变量都以原变量或反变量的形式出现，且仅出现一次。标准积项通常称为最小项。

一个函数可以用最小项之和的形式来表示，称为函数的“标准积之和”形式。例如，一个三变量函数为
F（A，B，C）＝B＋BC＋A＋ABC
它由4个最小项组成，这是函数的“标准积之和”形式。

由最小项的定义可知，3个变量最多可组成8个最小项： 、C、B、BC、A、AC、AB、ABC。为了叙述和书写方便，通常用mi表示最小项，其下标i是这样确定的： 把最小项中原变量记为1，反变量记为0，当变量顺序确定后，可以按顺序排列成一个二进制数。那么，与这个二进制数相对应的十进制数就是最小项的下标i。表3.6列出了3个变量的全部最小项和最大项。

表3.6三变量的所有最小项和最大项



ABC
最小项
最大项
000
m0＝
M0＝A＋B＋C
001
m1＝C
M1＝A＋B＋
010
m2＝B
M2＝A＋＋C
011
m3＝BC
M3＝A＋＋
100
m4＝A
M4＝＋B＋C
101
m5＝AC
M5＝＋B＋
110
m6＝AB
M6＝＋＋C
111
m7＝ABC
M7＝＋＋


因此，上述函数F（A，B，C）可以写成
F（A，B，C）＝B＋BC＋A＋ABC＝m２＋m３＋m４＋m７＝∑m(2,3,4,7)
其中，符号“∑”表示各最小项求“或”，括号内的十进制数字表示各最小项的下标。

最小项有下列3个主要性质。

（1） 对于任意一个最小项，只有一组变量取值使其值为1。

（2） 任意两个不同的最小项之积必为0，即
mi·mj＝0（i≠j）
（3） n变量的所有2n个最小项之和必为1，即
∑2n－1i=0mi=1

用展开定理可以证明，任一个n变量的函数都有一个且仅有一个最小项表达式，即“标准积之和”形式。下面介绍求函数的“标准积之和”的两种常用的方法。

方法一： 代数演算法，即通过反复使用公式x＋x-＝1和x（y＋z）＝xy＋xz而求得“标准积之和”的方法。例如，设F（A，B，C）＝B＋A＋BC，则得
F（A，B，C）＝B(C＋)＋A＋BC(A＋)
＝BC＋B＋A＋ABC＋BC
＝B＋BC＋A＋ABC＝m２＋m３＋m４＋m７
＝ ∑m(2,3,4,7)
方法二： 列表法，即列出函数的真值表，使函数取值为1的那些最小项，就构成了函数的“标准积之和”形式。例如，函数F（A，B，C）＝B＋A＋BC的真值表列于表3.7。根据真值表可以很方便地写出函数的表达式为
F（A，B，C）＝m２＋m３＋m４＋m７＝∑m(2,3,4,7)
式中，m２、m３、m４和m７是相应于真值表中使函数取值为1的那些最小项。


表3.7函数的真值表与最小项



ABC
Ｆ(A，B，C)
最小项
000
0

001
0

010
1
m2＝B
011
1
m3＝BC
100
1
m4＝A
101
0

110
0

111
1
m7＝ABC


2.  标准和之积

所谓标准和，是指函数的和项包含了全部变量，其中每个变量都以原变量或反变量形式出现，且仅出现一次。标准和项通常又称为最大项。

一个函数可以用最大项之积的形式表示，我们把这种形式称为函数的“标准和之积”形式。例如，一个三变量函数为
F（A，B，C）＝（A＋B＋C）（A＋B＋）（＋B＋）（＋＋C）
它由4个最大项组成，这就是函数的“标准和之积”形式。


同样，3个变量最多可组成8个最大项，如表3．6所示。通常，最大项用Mi来表示，其下标i是这样确定的： 当最大项的各变量按一定次序排好后，把其中的原变量记为0，反变量记为1，便得到一个二进制数，与该二进制数相应的十进制数就是最大项的下标i。

这样，上述函数F（A，B，C）可以写成
F（A，B，C）＝（A＋B＋C）（A＋B＋）（＋B＋）（＋＋C）
＝M0 M1 M5 M6＝∏M（0，1，5，6）
其中，符号“∏”表示各最大项相“与”，括号内的十进制数表示各最大项的下标。

最大项具有下列3个主要性质： 

（1） 对于任意一个最大项，只有一组变量取值可使其值为0。

（2） 任意两个不同的最大项之和必为1，即
Mi＋Mj＝1 （i≠j）
（3）  n变量的所有2n个最大项之积必为0，即
∏2n－1i=0Mi=0

同样地用展开定理可以证明，任何n变量的函数都有一个且仅有一个最大项表达式，即“标准和之积”形式。求函数的“标准和之积”的方法也有两种方法： 

方法一： 代数演算法，即通过反复地使用公式x·x-＝1和x＋yz＝(x＋y)(x＋z)而求得“标准和之积”的方法。例如
F＝B＋A＋BC＝(Ｂ＋A)( B＋)( B＋)＋BC
＝（＋Ａ）（Ｂ＋Ａ）（＋）（Ｂ＋）（＋）（B＋）＋ＢＣ
＝（Ａ＋Ｂ）（＋）（＋）（Ｂ＋）＋ＢＣ
＝（（Ａ＋Ｂ）（＋）（＋）（Ｂ＋）＋Ｂ）（（Ａ＋Ｂ）（＋）（＋）（Ｂ＋）＋Ｃ）
＝（（Ａ＋Ｂ＋Ｂ）（＋＋Ｂ）（＋＋Ｂ）（Ｂ＋＋Ｂ））·
（（Ａ＋Ｂ＋Ｃ）（＋＋Ｃ）（＋＋Ｃ）（Ｂ＋＋Ｃ））
＝（Ａ＋Ｂ）（＋Ｂ＋）（Ｂ＋）（Ａ＋Ｂ＋Ｃ）（＋＋Ｃ）

由于表达式中第一项缺少变量C，所以要加上C·； 第三项缺少变量A，所以要加A·，即
F＝（Ａ＋Ｂ＋Ｃ·）（＋Ｂ＋）（Ａ·＋Ｂ＋）（Ａ＋Ｂ＋Ｃ）（＋＋Ｃ）
＝（Ａ＋Ｂ＋Ｃ）（Ａ＋Ｂ＋）（＋Ｂ＋）（＋＋Ｃ）
＝M0M1M5M6＝∏M(0,1,5,6)
可见，用这种方法是比较麻烦的。

方法二： 列表法，即列出函数的真值表，那些使函数取值为0的最大项，就构成了函数的“标准和之积”形式。例如，上述函数的真值表列于表3.8，根据真值表可以很方便地写出表达式为
F(A,B,C)＝M0M1M5M6＝∏M(0,1,5,6)



表3.8函数的真值表与最大项



ABC
Ｆ(A，B，C)
最大项
000
0
M0＝A＋B＋C
001
0
M1＝A＋B＋
010
1

011
1

100
1

101
0
M5＝＋B＋
110
0
M6＝＋＋C
111
1



比较表3.7和表3.8，可以得出两点结论： 

（1） 同一个函数既可以表示成“标准积之和”的形式，又可表示成“标准和之积”的形式。对于本例，有
F（A，B，C）＝B＋A＋BC＝ ∑m(2,3,4,7) ＝∏M(0,1,5,6)

（2） 同一函数的最大项与最小项是互斥的，即如果真值表中的某一行作为函数的最小项，那么它就不可能是同一函数的最大项； 反之亦然。一般有mi＝i或者Mi＝m-i。换句话说，一个布尔函数的最小项的集合与它的最大项的集合，互为补集。因此，若已知一布尔函数的“标准积之和”形式，就可以很容易写出该函数的“标准和之积”形式。例如，已知函数的“标准积之和”形式为
F（A，B，C）＝ ∑m(1,3,4,6,7) 
则该函数的“标准和之积”形式为
F（A，B，C）＝∏M(0,2,5)
3．4不完全确定的布尔函数

前面所讨论的布尔函数都是属于完全确定的布尔函数。也就是说，它们的每一组输入变量的取值，都能得到一个完全确定的函数值（0或1）。如果布尔函数有n个变量，函数就有2n个最小项（或最大项），其中每一项都有确定的值。

在实际应用中，有时只要求某些最小项（或最大项）有确定的值，而对其余最小项（或最大项）的取值不感兴趣，它们既可为0，也可为1，即随意取值。通常，把这种可以随意取值的最小项（或最大项）称为随意项，或无关项，记为d。这种具有随意项的布尔函数称为不完全确定的布尔函数。

在数字系统的设计中，这种不完全确定的布尔函数是经常遇到的。例如，如果逻辑电路的输入是二进制编码的十进制数，4位二进制输入共有16种不同的状态，其中只有10种是允许的，有确定的输出； 而其余6种是不允许的，因此它们的输出结果是人们不关心的，换句话说，结果可以是任意的。在设计中，可以充分利用这些任意项，使设计得到简化。

【例3.5】设计一个奇偶判别电路，其输入为一位十进制的BCD码。当输入为偶数时，电路输出为0； 当输入为奇数时，电路输出为１，如图3.4所示。



图3.4奇偶判别电路



根据设计要求可以列出描述该电路的布尔函数真值表，如表3.9所示。其中，第10~15行是不确定的，所以这是一个不完全确定的布尔函数，函数的表达式为： 
F（A，B，C，Ｄ）＝ ∑m(1,3,5,7,9)＋∑d(10,11,12,13,14,15)
式中，d表示随意项，可取0，也可取1。


表3.9BCD码奇偶判别电路真值表



十进制数

r
BCD
A
B
C
D
F(A,B,C,D)

0
0
0
0
0
0
1
0
0
0
1
1
2
0
0
1
0
0
3
0
0
1
1
1
4
0
1
0
0
0
5
0
1
0
1
1
6
0
1
1
0
0
7
0
1
1
1
1
8
1
0
0
0
0
9
1
0
0
1
1
10
1
0
1
0
d
11
1
0
1
1
d
12
1
1
0
0
d
13
1
1
0
1
d
14
1
1
1
0
d
15
1
1
1
1
d


为了使设计的电路简单，可以将函数化简。下面分两种情况来考虑。

（1） 如果不考虑随意项（即取d＝0），则有
F（A，B，C，D）＝∑m（1，3，5，7，9）
＝D＋CD＋BD＋BCD＋AD
＝D（C＋）＋BD（C＋）＋D（＋A）
＝D＋BD+D
＝D＋D（3.1）
（2） 如果考虑随意项，且取随意项11、13、15的值为1，其余随意项取值为0，则有
F（A，B，C，Ｄ）＝ ∑m(1,3,5,7,9)＋∑d=1d(11, 13, 15)
＝∑m（1，3，5，7，9，11，13，15）＝D（3.2）
式（3.1）比式（3.2）要简单得多。由此可见，对随意项合理赋值，可以使函数大为简化。因而其相应的逻辑电路也简单了。

3．5布尔函数的化简

由3.3节讨论知道，同一个布尔函数可以有多种表示形式。一种形式的函数表达式相应于一种逻辑电路，尽管它们的形式不同，但其逻辑功能是相同的。函数表达式有简有繁，相应的逻辑电路也有简有繁，人们希望用尽可能少的逻辑门来完成同样的逻辑功能，这就要求函数表达式是最简单的。因此，如何使函数的表达式最简单，即函数的化简，成为逻辑设计的一个关键问题。因为函数越简单，所设计的电路就不仅简单、经济，而且出现故障的可能性也越小，可靠性就越好。

在函数的各种不同形式的表达式中，“与或”表达式是最基本的，其他形式的表达式都可由它变换而得。例如

F（A，B，C）＝＋AC(“与或”形式)

＝（＋C）（A＋）(“或与”形式)

＝·AC (“与非”形式)

＝+C+A+ (“或非”形式)

＝A+B“与或非”形式


因此，将从“与或”表达式出发来讨论函数的化简方法。

 什么是函数的最简“与或”式呢？一个最简“与或”式应同时满足以下两个条件。

（1） 该式中的“与”项最少。

（2） 该式中的每个“与”项的变量也最少。

这样，用逻辑门来实现布尔函数时，所需的“与”门数目最少，而且每个“与”门的输入端数目也最少。

本节讨论布尔函数的几种常用的化简方法，以及用不同门电路来实现布尔函数的方法。这些方法是组合逻辑网络设计的基础，应熟练掌握。

3.5.1代数化简法

所谓代数化简法，就是运用布尔代数的基本公式、定理和规则来化简布尔函数的一种方法。这种方法没有固定的步骤可以遵循，主要是凭对布尔代数的公式、定理和规则的熟练运用程度。尽管如此，我们还是可以总结出一些适用于大多数情况的方法。这些方法的基本思想是对布尔函数进行等式变换，使表达式的“与”项减少，或使“与”项中的变量减少，以达到化简函数的目的。下面介绍化简“与或”表达式的几种常用的方法。

1. 并项法

利用公式AB＋A＝A，将两项合并为一项，并消去一个变量。例如
AC＋A＝A
AB＋AB＝A
2. 吸收法

利用吸收律A＋AB＝A，消去多余的项。例如
＋AD＝
A＋ACD(E＋F)＝A
还可以利用吸收律A＋B＝A＋B，消去多余的变量。例如
＋AB＋DE＝＋B＋DE
AB＋C＋C＝AB＋（＋）C＝AB＋ABC＝AB＋C
3. 配项法

利用A·1＝A和A＋＝1，为某一项配上其所缺的一个变量，以便用其他方法进行化简。例如

AB＋C＋BC＝AB＋C＋（A＋）BC＝AB＋C＋ABC+BC
＝（AB＋ABC）＋（C＋BC）＝AB＋C（吸收法）
还可以利用公式A＋A＝A，为某项配上其所能合并的项。例如
ABC＋AB＋AC＋BC
＝（ABC＋AB）＋（ABC＋AC）＋（ABC＋BC）
＝AB＋AC＋BC
4. 消去冗余项法

等式AB＋C＋BC＝AB＋AC可以作为一个基本公式使用，它称为包含律，其中BC称为冗余项。利用这个公式，去寻找一个表达式的冗余项，然后消去冗余项。例如
A＋AC＋ADE＋D＝A＋（AC＋D＋ADE）＝A＋AC＋D
AB＋C＋AC（D＋E）＝AB＋C
以上介绍了几种常用的方法。在实际应用中可能遇到比较复杂的函数，只要熟练掌握布尔代数的公式和定理，灵活运用上述方法，总能找到化简的办法。下面是几个综合运用上述方法化简布尔函数的实例。

【例3.6】化简F＝AD＋A＋AB＋C＋BD＋ACEF＋EF＋DEFG

F＝AD＋A＋AB＋C＋BD＋ACEF＋EF＋DEFG

＝A＋AB＋C＋BD＋ACEF＋EF＋DEFG（并项法）

＝A＋C＋BD＋EF＋DEFG（吸收法）

＝A＋C＋BD＋EF＋DEFG（吸收法）

＝A＋C＋BD＋EF（消去冗余项）

【例3.7】化简F＝A＋B＋C＋B

F＝A＋B＋C＋B

＝A＋B＋(A＋)C＋B(C＋)（配项法）

＝（A＋AC）＋（B＋B）＋（C＋BC）

＝A＋B＋C（吸收法）

【例3.8】化简或与表达式
F＝（＋D）（＋D＋A＋G）（C＋E）（＋G）（A＋E＋G）
可以利用对偶规则，先求出F的对偶式： 
Fd＝D＋DAG＋CE＋G＋AEG
然后，利用与或式的化简方法进行化简，则得
Fd＝D＋CE＋G
最后，对Fd再求对偶式，则得
F＝(Fd)d ＝(＋D)( C＋E)(+G)
由本例可见，与或表达式的化简是基础，其他形式的表达式都可先变换为与或表达式进行化简，然后再变换成所需的形式。

从以上的例子可以看出，代数化简法不仅使用不便，而且难以判断所得之结果是否为最简。因此，代数化简法一般适用于函数表达式较为简单的情况。当函数较为复杂时，往往采用比较方便的、有规则的卡诺图法。

3.5.2卡诺图化简法

卡诺图化简法是将布尔函数用卡诺图来表示，在卡诺图上进行函数的化简的方法。这是一种很简单、直观的方法。

1. 卡诺图的构成

卡诺图是真值表的图形化。我们可以把真值表看成是由最小项构成的一个纵列。一个函数由若干最小项构成，则在相应的最小项上填1，其余填0。

例如，设有函数F（A，B，C）＝∑m（2，3，5，7），该函数的真值表如表3.10所示。



表3.10F（A，B，C）＝∑m（2，3，5，7）的真值表



ABC
Ｆ(A，B，C)
最小项
000
0
m0
001
0
m1
010
1
m2
011
1
m3
100
0
m4
101
1
m5
110
0
m6
111
1
m7


该函数可以进行化简，即
F（A，B，C）＝B＋BC＋AC＋ABC
＝B（＋C）＋AC（＋B）
＝B＋AC
其中，最小项B和BC（或者AC和ABC）只有一个变量互补，其余变量相同，称这样的最小项为相邻最小项，它们可以合并消去一个变量。因此，化简的实质是两个相邻最小项的合并。

从真值表上很难直观地看出最小项的相邻关系的。例如，相邻最小项m5和m7在位置上并不相邻。那么，能不能把最小项排成一种图，可以直观地从图上看出最小项的相邻关系呢？可以的。从Gray码的特点知道，两个相邻代码之间只有一位不同。因此，只要把真值表中的最小项重新排列，把它们排列成矩阵形式，并且使矩阵的横方向和纵方向的布尔变量的取值按Gray码的顺序排列，这样构成的图形就是卡诺图。图3.5表示了二变量、三变量和四变量的卡诺图的构成。



图3.5卡诺图的构成



从卡诺图可以看出，任意两个相邻的最小项在图上是相邻的。并且，图中最左列的最小项与最右列的相应最小项也是相邻的； 位于最上面一行的最小项与最下面一行的相应最小项也是相邻的。因此，每个二变量的最小项有两个最小项与它相邻； 每个三变量的最小项有3个最小项与它相邻； 每个四变量的最小项有4个最小项与它相邻。可以证明每个n变量的最小项有n个最小项与它相邻。

五变量的卡诺图如图3.6所示。图中方格内的数字为最小项的下标。它可以看成是由两个四变量的卡诺图构成的，只要把右边部分的四变量卡诺图重合到左边部分的四变量卡诺图上来，就可找出各最小项的相邻关系。例如，最小项3与最小项1、2、7、11及19是相邻的。



图3.6五变量卡诺图



六变量卡诺图如图3.7所示，它可以看成是由4个四变量卡诺图构成的。在寻找各最小项的相邻关系时，除了要注意左、右两个四变量卡诺图的重合关系外，还要注意上、下两个四变量卡诺图的重合关系。例如，最小项3除与最小项1、2、7、11、19相邻外，还与最小项35相邻。

变量多于6个时，卡诺图就显得很庞大，在实际应用中已失去它的优越性，一般就很少用它了。



图3.7六变量卡诺图


2. 布尔函数在卡诺图上的表示

从卡诺图的构成方法可知，卡诺图实际是真值表的重新排列，使最小项排列得更紧凑、更便于化简。因此，根据卡诺图与真值表的对应关系，就可以知道布尔函数在卡诺图上的表示方法。

如果布尔函数是以真值表的形式或者以“标准积之和”的形式给出的，我们只要在卡诺图上找出那些与给定布尔函数的最小项相对应的方格，并标以1，就得到该函数的卡诺图。例如，三变量函数
F（A，B，C）＝∑m（2，3，5，7）
其卡诺图如图3.8所示。

如果布尔函数是“与或”表达式，则要将各“与项”分别标在卡诺图上。例如，给定函数的表达式为
F（A，B，C）＝AB＋Ａ
只要在AB为11的列标以1，并在A为1、C为0的对应方格中标上1，便可得到如图3.9所示的卡诺图。



图3.8F（A，B，C）＝∑m（2，3，5，7）的卡诺图




图3.9F（A，B，C）＝AB＋Ａ的卡诺图





图3.10F（A，B，C，D）＝BD＋
＋D的卡诺图


又如，给定四变量函数为
F（A，B，C，D）＝BD＋＋D
其卡诺图如图3.10所示。


3. 卡诺图的性质

卡诺图化简布尔函数的基本原理是基于卡诺图的性质。前面已指出，化简的实质是相邻最小项的合并。卡诺图的一个明显优点是它能利用人的直观的阅图能力，方便地表示出所有相邻最小项。卡诺图具有下列性质。

性质3.1卡诺图上任何两个（21个）标1的相邻最小项，可以合并为一项，并消去一个变量。

例如，在图3．10中，最小项m1＝D和m3＝CD相邻，所以它们可以合并； 最小项m5＝BD和m7＝BCD相邻，所以它们也可以合并,即有
D＋CD＝D，BD＋BCD＝BD
性质3.2卡诺图上任何4个（22个）标1的相邻最小项，可以合并为一项，并消去两个变量。

例如，在图3．10中，最小项m1、m3、m5和m7彼此相邻，这4个最小项可以合并,即有
（m1＋m3）＋（m5＋m7）＝D＋BD＝D
这种合并，在卡诺图中表示为把4个1圈在一起。

在四变量卡诺图中，4个标1的小方格相邻的典型情况如图3．11所示。



图3．114个相邻最小项合并的情况



在图3．11（a）中，最小项m0、m2、m8、m10相邻，而最小项m5、m7、m12、m15也相邻。它们合并后，可得函数表达式为
F（A，B，C，D）＝＋BD
根据同样道理，将图3．11（b）中的相邻最小项合并后，可得函数表达式为
F（A，B，C，D）＝B＋D
将图3．11（c）中的相邻最小项合并后，结果为
F（A，B，C，D）＝B＋CD
性质3.3任何8个（23个）标1的相邻最小项，可合并为一项，并消去3个变量。



图3．128个相邻最小项合并的情况



图3．12表示了8个相邻最小项合并的情况。其中，图3．12（a）所示的8个最小项合并后，结果为

F（A，B，C，D）＝B
图3．12（b）中的8个最小项合并后，结果为
F（A，B，C，D）＝
由上述性质可知，相邻最小项的数目必须为2i个才能合并成一项，并消去i个变量。包含的最小项数目越多，消去的变量也越多，从而所得到的逻辑表达式就越简单。

4. 卡诺图化简的基本步骤

在讨论用卡诺图化简的具体方法之前，先定义几个概念。

蕴涵项在函数的任何与或表达式中，每个与项称为该函数的蕴涵项（Implicant）。显然，在函数的卡诺图中，任一标1的最小项以及由2i个相邻最小项所形成的圈都是函数的蕴涵项。

质蕴涵项如果函数的某一蕴涵项不是该函数中其他蕴涵项的一个子集，则此蕴涵项称为质蕴涵项（Prime Implicant）。从卡诺图上看，所谓质蕴涵项，就是大得不能再大的圈。例如，在图3．13中，BD、A和AB都是质蕴涵项，而BCD、BD等都不是质蕴涵项。


必要质蕴涵项如果函数的一个质蕴涵项，至少包含了一个其他任何质蕴涵项都不包含的标1最小项，则此质蕴涵项称为必要质蕴涵项（Essential Prime Implicant）。例如，在图3．13中，BD、A是必要质蕴涵项，而AB就不是必要质蕴涵项。

根据以上定义，可以给出用卡诺图化简布尔函数的基本步骤如下。

（1） 将布尔函数正确地标到卡诺图上，并在图上找出所有质蕴涵项。

（2） 求出所有必要质蕴涵项。

（3） 求函数的最小覆盖（即函数的最简表达式）。

下面通过具体例子来说明上述步骤。

【例3.9】用卡诺图法化简函数
F（A，B，C，D）＝∑m（0，3，4， 5，7，11，13，15）
（1） 作F的卡诺图，并求得所有质蕴涵项为BD、CD、、B，如图3．14所示。

（2） 求出所有必要质蕴涵项为CD、BD、。

（3） 由于必要质蕴涵项的集合已覆盖了函数的所有最小项，因此函数的最简与或式为
F（A，B，C，D）＝BD＋CD＋



图3．13卡诺图中的质蕴涵项




图3．14例3.9的卡诺图




【例3.10】用卡诺图化简布尔函数

F（A，B，C，D）＝∑m（0，5，6，8，15）＋∑d（1，2，3，7，10，12，13）
这是含有随意项d的情况。利用随意项求质蕴涵项时，如果它对化简有利，则取d＝1； 如果它对化简不利，则取d＝0。

（1） 作函数的卡诺图，求出所有质蕴涵项为、D、C、BD、，如图3．15所示。

（2） 求出所有必要质蕴涵项为C、BD、。注意，在求必要质蕴涵项时，只要考虑1的覆盖。

（3） 求函数的最小覆盖。本例中必要质蕴涵项已覆盖了卡诺图中所有标1的最小项。因此，布尔函数的最简与或式为
F（A，B，C，D）＝C＋BD＋
【例3.11】用卡诺图化简布尔函数

F（A，B，C，D）＝∑m（0，4，6，7，8，9，11，12，13，15）
（1） 求出所有质蕴涵项为、A、AD、B、BC、BCD，如图3．16所示。




图3.15例3.10的卡诺图




图3.16例3.11的卡诺图



（2） 求出所有必要质蕴涵项为、AD。

（3） 求函数的最小覆盖。本例中必要质蕴涵项只覆盖了函数的8个最小项，还剩下两个最小项m6、m7未被覆盖。由观察可知，在几个非必要质蕴涵项中，选择BC这一项即可覆盖m6、m7。因此，该函数的最简与或式为
F（A，B，C，D）＝AD＋＋BC
这说明，在一个最简与或式中，并非每个质蕴涵项都是必要的，其中可能包含所选择的质蕴涵项。这一点应引起注意。



必须指出，由于卡诺图化简法带有试凑性质，因此，当读者已对卡诺图应用自如时，就不必按上述步骤去做，可以在卡诺图上一次画出最小覆盖。

【例3.12】用卡诺图化简函数
F（A，B，C，D）＝∑m（0，1，3，4，7，12，13，15）
作出F的卡诺图如图3．17（a）所示。该函数有8个质蕴涵项，它们相互交连，找不出哪个是必要质蕴涵项，这种情况通常称为循环结构。对于这类循环结构，通常可选取一个最大的质蕴涵圈作为必要质蕴涵项，以打破循环结构。本例中，由于各个质蕴涵圈的大小相等，故可任选一个质蕴涵项作为必要质蕴涵项。图3．17（b）为其中的一种解，可得F的最简表达式为
F（A，B，C，D）＝＋CD＋ABD＋B
同理，可得另一个最简表达式为
F（A，B，C，D）＝D＋BCD＋AB＋D



图3.17例3.12的卡诺图



【例3.13】化简五变量函数
F（A，B，C，D，E）＝∑m（2，4，5，6，7，12，13，18，20，21，22，23，24，25，28，29）
五变量布尔函数可用两个四变量卡诺图来表示，相重叠的最小项是相邻的，可以合并。画出函数F的卡诺图如图3．18所示。重叠部分的质蕴涵项为D、C和C； 不重叠的质蕴涵项为AB。这几个都为必要质蕴涵项，且覆盖了函数的全部标1最小项。因此，函数的最简表达式为
F（A，B，C，D，E）＝D＋C＋C＋AB



图3.18例3.13的卡诺图


由上述例子可见，用卡诺图化简布尔函数简单明了，形象直观，容易掌握。

3.5．3列表化简法

上节介绍的卡诺图化简法是手算常用的方法，它的缺点是： 由于要靠人对图形的识别能力，因此不便于机器实现； 而且，当函数的变量增多时（如多于6个），这种方法就逐渐失去它的优越性。

本节介绍一种更有规律的、系统的方法，即列表化简法。这一方法是由W.V.Quine和E.J.McCluskey在1956年研究发表的，故也称奎恩麦克拉斯基法，简称QM法。这种方法的基本步骤与卡诺图法是相同的，即先找出布尔函数的所有质蕴涵项，然后找出其中的必要质蕴涵项，最后求函数的最小覆盖。所不同的是，列表化简法完成上述步骤是通过约定形式的表格，按照一定规则求得的。下面分别讨论列表法的这几个步骤。

1. 用列表法确定布尔函数的所有质蕴涵项

用列表法找布尔函数的所有质蕴涵项的基本思想是这样的： 首先将布尔函数用最小项来表示，并把最小项表示成二进制数形式。例如

m4： B表示成0100。

m5： BD表示成0101。

然后进行两两比较，如果两个二进制数只有一位不同，就可合并。例如






其中，“－”表示该位置上的变量被消去； 同理，对于带有“－”的两个二进制数，若只有一位不相同（0与1），则此二进制数又可进一步合并，得到带有两个“－”的二进制数。例如： 






就这样逐次合并只有一位数值不同的两个二进制数，所得到的不能再合并的二进制数，其对应的乘积项，即为质蕴涵项。

下面举例说明用列表法求质蕴涵项的过程。

【例3.14】求下列函数的全部质蕴涵项： 
F（A，B，C，D）＝∑m（1，3，4，5，10，11，12，13）
为便于对照，以弄懂合并的原理，不妨先给出卡诺图上合并的情况，如图3．19所示。

用QM法求质蕴涵项过程如下： 

第一步，列出最小项的二进制数形式，如表3．11所示。



表3．11最小项的二进制形式



mi
ABCD
1
0001
3
0011
4
0100
5
0101
10
1010
11
1011
12
1100
13
1101





图3．19例3.14的卡诺图



可以看出，两个二进制数可以合并有如下规律： 只有二进制数中1的个数相差1的两数才能合并，而1的个数相同或相差2和2以上的两数不能合并。这一规律启示我们，如果把上述二进制数按1的个数分组，那么，只有在相邻组之间才有合并的可能性，组内和隔组之间则不必考虑合并可能，这样可以大大地减少合并的工作量。


第二步，按1的个数分组列表，并在相邻组之间进行搜索合并。凡是能合并的两个项，则在其后面打“√”，表示它们不是质蕴涵项，并将合并结果列于另一栏中。如此继续，直到无法合并为止。最后，那些没有打“√”的项，就是质蕴涵项Pi。以上过程如表3．12所示。


表3．12求质蕴涵项Pi



miABCD
miABCD
miABCD

10001√1,300—1 P24,5
40100√1,50—01P 312,13
—10—P1

30011√4,5010—√
50101√4,12—100√
101010√3,11—011P4
121100√5,13—101√
111011√10,11101—P5
131101√12,13110—√


最后，求得全部质蕴涵项为
P1＝B，P2＝D， P3＝D，P4＝CD，P5＝AC
该结果与图3．19卡诺图上合并结果相同。

2. 用质蕴涵表确定必要质蕴涵

所谓质蕴涵表，就是函数的各个质蕴涵覆盖函数的相应最小项的情况表。下面通过例子来说明如何列质蕴涵表，以及如何用质蕴涵表来确定必要质蕴涵。

【例3.15】已知函数
F（A，B，C，D）＝∑m（1，3，4，5，10，11，12，13）
求得它的全部质蕴涵为B、D、D、CD、AD。列质蕴涵表如表3．13所示。表中，各纵列代表函数所包含的最小项，各横行是函数的质蕴涵项。每一个质蕴涵项所覆盖的最小项，都在表中行列交叉处用记号“×”标出，例如，质蕴涵项B可覆盖最小项4、5、12、13。因此，在B这一行的最小项4、5、12、13列下标上“×”号。其他各行按同样方法标上记号。


表3．13质蕴涵表



Pjmi

1
3
4
5
10
11
12
13
√B



×




D
×
×






D
×


×




CD

×



×


√AD





×


覆盖情况


×
×
×
×
×
×



必要质蕴涵是按下列步骤求得的。

（1） 逐列检查表3．13中标有“×”号的情况，凡只标有一个“×”号的列，则在该“×”的外面打一个圈，即。例如，表中最小项4、10、12、13各列都只有一个“×”，故都加上圈。

 （2） 找出包含有号的各行，这些行的质蕴涵项就是必要质蕴涵项，并在其前加上标记“√”。例如，表中B和AD就为必要质蕴涵项。

（3） 在表的最后一行覆盖情况一栏中，标上必要质蕴涵项覆盖最小项的情况。凡能被必要质蕴涵项覆盖的最小项，在最后一行的该列上打“×”号。

由表3．13可知，本例中必要质蕴涵项B和AD，没有覆盖F 的全部最小项。因此，接着要做的下一步是求F的最小覆盖。

3. 求函数的最小覆盖

一般来说，必要质蕴涵覆盖函数的最小项的情况有两种可能： 一种是必要质蕴涵已覆盖了函数的所有最小项，对于这种情况，函数的化简工作就已完成，即函数的最小覆盖就是所有必要质蕴涵项。另一种是必要质蕴涵没有覆盖函数的所有最小项，对于这种情况，还需要选择适当的质蕴涵项，以覆盖剩下的最小项。那么，覆盖剩余的最小项所需的质蕴涵应该怎样选择才能使函数表达式最简呢？下面介绍两种常用的选取所需质蕴涵的方法。

1) 行列消去法 

在质蕴涵表中，去掉必要质蕴涵项和已被其覆盖的最小项，剩下的部分称为简化的质蕴涵表。下面的两个规则——优势行规则和优势列规则，能从简化的质蕴涵表中选取所需的质蕴涵。

① 优势行规则。设质蕴涵Pi和Pj是简化质蕴涵表中的两行，其中Pj行中的“×”完全包含在Pi行中，则称Pi为优势行，Pj为劣势行，记作Pi  Pj。这时，在简化质蕴涵表中可以消去劣势行Pj（这是因为选取了优势行Pi后，不仅可覆盖劣势行Pj所覆盖的最小项，而且还可覆盖其他最小项）。

例如，由表3．13去掉必要质蕴涵项和被它所覆盖的最小项，得到简化的质蕴涵表如表3．14所示。表中，P3相对于P2来说是劣势行，即P2  P3，可消去P3； 同理，P4相对于P2来说也是劣势行，即P2  P4，可消去P4。最后只剩下P2。

② 优势列规则。设最小项mi和mj是简化质蕴涵表中的两列，其中mj列中的“×”完全包含在mi列之中，则称mi为优势列，mj为劣势列，记作mi  mj。这时，在简化质蕴涵表中可以消去优势列mi（这是因为选取了覆盖劣势列的质蕴涵后，一定能覆盖优势列，反之则不一定）。

例如，设表3．15为简化质蕴涵表，表中的m2和m3相对于m1来说是劣势列，即m2  m1，m3  m1，故可消去优势列m1。


表3．14简化的质蕴涵表



Pjmi

1
3

P2
×
×
P3
×

P4

×



表3．15优势列举例



Pjmi

m1
m2
m3
P1
×
×

P2
×

×
P3
×



这种优势行规则和优势列规则可以反复交替使用，使简化的质蕴涵表进一步简化，以便求得所需的质蕴涵项。

【例3.16】用行列消去法求所需质蕴涵项，设简化的质蕴涵表如表3．16所示。


表3．16简化的质蕴涵表



Pjmi

m2
m4
m6
m10

P2
×

×

P3
×


×
P4

×
×

P5

×


P6



×


表中，根据优势行规则，有P4  P5，P3  P6，故可消去P5 和 P6； 又根据优势列规则，由于m4  m6，m10  m2，故可消去m2和m6。最后，求得所需质蕴涵为P3和P4，它们覆盖了简化质蕴涵表的所有最小项m2、m4、m6和m10。

2） 布尔代数法

所谓布尔代数法，就是从简化质蕴涵表列出布尔表达式，从中选出最简的所需质蕴涵项。

例如，对于表3．14的简化质蕴涵表，要覆盖最小项m1，可选取质蕴涵项P2或P3； 要覆盖最小项m3，可选取质蕴涵项P2或P4。因此，若要同时覆盖m1和m3，可以用如下布尔表达式来表示： 
（P2＋P3）（P2＋P4）＝P2＋P2 P4＋P2 P3＋P3 P4＝P2＋P3 P4
该式表明，同时覆盖m1和m3的方案有两个，即选用P2或选用P3 P4，其中选用P2最简单； 该结果与行列消去法所得结果相同。

又如，对于表3．16的简化质蕴涵表，若要同时覆盖最小项m2、m4、m6和m10，则有
（P2＋P3）（P4＋P5）（P2＋P4）（P3＋P6）＝（P3＋P2 P6）（P4＋P2 P5）
＝P3 P4＋P2 P3 P5＋P2 P4 P6＋P2 P5 P6
该式表明，可供选取的所需质蕴涵集有4个，其中只有P3 P4最简单。所以，用布尔代数法求得所需质蕴涵项为P3和P4，其结果与行列消去法所得结果相同。

最后，我们举两个综合性的例子，将前面所讲的连贯起来，以说明用QM列表法化简一个布尔函数的全过程。

【例3.17】化简布尔函数
F（A，B，C，D）＝∑m（2，4，6，8，9，10，12，13，15）
①  求函数的所有质蕴涵，如表3．17所示。

求得所有质蕴涵为
P1＝A，P2＝C，P3＝C，P4＝B，P5＝B，P6＝A，P7＝ABD




表3．17求质蕴涵项Pi



miABCD
miABCD
miABCD

20010√2,60—10 P28,9
40100√2,10—010P312,13
1—0—P1

81000√4,601—0P4
60110√4,12—100P5
91001√8,9100—√
101010√8,1010—0P6
121100√8,121—00√
131101√9,131—01√
151111√12,13110－√
13,1511－1P7


② 求必要质蕴涵，如表3．18所示。



表3．18质蕴涵表



m
2
4
6
8
9
10
12
13
15
√P1



×


×
×

P2
×

×






P3
×




×



P4

×
×






P5

×




×


P6



×

×



√P7







×

覆盖情况



×
×

×
×
×


由表3．18可确定P1和P7为必要质蕴涵。

③ 求函数的最小覆盖。

去掉表3．18中的P1和P7行，以及已被P1和P7覆盖的最小项m8、m9、m12、m13和m15，得到简化的质蕴涵表，如表3．16所示。

利用前面讲的行列消去法或用代数法求得所需质蕴涵为P3和P4，因此，函数的最简表达式为
F（A，B，C，D）＝P1＋P7＋P3＋P4＝A＋ABD＋C＋B

【例3.18】化简不完全确定的布尔函数

F（A，B，C，D） ＝ ∑m（1，3，4，5，10，11，12） ＋ ∑d（2，13）
对于不完全确定的布尔函数的化简，要注意两点： 一是在列表求所有质蕴涵时，应该令d＝1，以尽量利用随意项进行合并； 二是在列质蕴涵表时，应令d＝0，即随意项的覆盖问题可不必考虑，以有利于得到最简式。

① 求所有质蕴涵项。令所有随意项为1，如表3．19所示。


表3．19求质蕴涵项Pi



miABCD
miABCD
miABCD

10001√1,300—1 P32,3
20010√1,50—01P410,11
—01—P1

40100√2,3001—√4,5
30011√2,10—010√12,13
—10—P2

50101√4,5010—√
101010√4,12—100√
121100√3,11—011√
111011√5,13—101√
131101√10,11101－√
12,13110—√



求得所有质蕴涵项为
P1＝C，P2＝B，P3＝D，P4＝D
②  求必要质蕴涵。令所有的随意项为0，即在质蕴涵表中不必列随意项，如表3．20所示。

由表3．20可确定必要质蕴涵为P1和P2。



表3．20质蕴涵表



Pj
mi
1
3
4
5
10
11
12
√P1

×





√P2



×



 P3
×
×





 P4
×


×



覆盖情况

×
×
×
×
×
×


③ 求函数的最小覆盖。

去掉质蕴涵表中被必要质蕴涵覆盖的最小项后，只剩下最小项m1未被覆盖，直接从表3．20可以选取P3或P4作为所需质蕴涵。因此，函数的最简表达式为
F（A，B，C，D）＝P1＋P2＋P3＝C＋B＋D
或者F（A，B，C，D）＝P1＋P2＋P4＝C＋B＋D

以上介绍的都是单个布尔函数的化简，然而在逻辑设计中。经常会遇到多输出布尔函数。所谓多输出布尔函数，就是同样的布尔变量输入得到多个输出的函数。我们当然可以利用卡诺图或列表法单独地化简每个输出函数。然而有时这样得到的电路不一定是最简单的。有时被某个输出函数使用的一些项可以被其他输出函数共享，从而可以减少总的门数。因此我们在化简多输出函数时要考虑尽量多地找出所有的输出函数的公共项，而不是仅仅考虑单个输出函数的化简。

习题3

3.1下列函数当变量（A，B，C，…）哪些取１时，F的值为1： 

（1） F＝AB+C（2） F＝A+B

（3） F＝+AB（4） F＝ABC+AB+AC+BC

（5） F＝（A++B）（A+）B

（6） F＝（A+B+C）（A+B+）（A++C）（A++）

（7） F＝（A+）+(A+)CD（8） F＝（AB）C+（BC）

3.2用真值表验证下列等式： 

（1） A+B＝·（2） A+B＝（+）（Ａ+Ｂ）

（3） （+）（Ａ+Ｂ）＝AB+AB(4) AB+A+B+＝1

（5） ＡＢＣ＝A⊙B⊙C（6）  (AB)C＝A(BC)

3.3用基本公式和基本规则证明下列等式： 


 (1) ＢＣ+Ｄ+（+）（ＡＤ+Ｂ）＝Ｂ+Ｄ 

 (2) AB+A+B+＝1

 (3) (A+B)(A+)(+B)(+)＝0

 (4) ABC+＝A+B+C

（5） A+B+C＝B+C+A

（6） AB+BC+AC＝（A+B）（B+C）（A+C）

（7） （AB+）（BC+）（CD+）＝A+B+C+D

（8） ＡＢＣ＝A⊙B⊙C

（9） （xy）z＝x（yz）

3.4用展开定理将下式各式化简成为A（…）+（…）形式及［A+（…）］［ +（…）］形式，括号中A及均不出现： 

（1） F＝AG+（A+B）C+D+（+F）E

（2） F＝（A+）（+C）（+E+AF）（G++J）

3.5写出下列表达式的对偶式： 

（1） F＝（A+B）（+C）（C+DE）+F（2） F＝A·C·D

（3） F＝+B+B+C+A+C+B+C（4） F＝B(AB)+B（AC）

 （5） F＝ (C⊙A)(B)

3.6求下列函数的补函数： 

（1） F＝［（x-1x2+x-3）x4+x-5］x6 （2） F＝S［+I(T+)］+H

（3） F＝A［+(C+F)G］ （4） F＝A+B+C(+D)

3.7将下列函数转换为由“标准积之和”形式表示的函数： 

（1） F（A，B，C）＝AC+B+AC+AB

（2） F（A，B，C）＝+A+BC+AC

 （3） F（A，B，C）＝B（A++）（+）C

 （4） F（A，B，C）＝ABC+

（5） F（A，B，C）＝（B+C）［（+B）Ｃ+Ａ］

3.8用“标准和之积”形式表示3.7题中的函数。

3.9用代数运算法求下列各函数的“标准积之和”形式及“标准和之积”形式： 

（1） F（A，B，C，D）＝AB+ABCD 

（2） F（A，B，C，D）＝BCD+ACD+ACD+CD

（3） F（A，B，C，D）＝B+B+ABD+BC

 （4） F（A，B，C）＝+B+C+ABC

（5） F（A，B，C，D）＝(+C)(A+)(A+B+C+D)(A+C+)

3.10设F（A，B，C，D，E）＝∑m（0,1,3,7,8,9,12,15,16,17,20,28,29,30,31），试用最大项表示这个函数。

3.11求3.10题中所给函数的补函数，并以最大项表示之。

3.12证明A+B+C+ABC＝ＡＢＣ。

3.13设A、B、C为逻辑变量，试回答： 

（1） 若已知A+B＝A+C，则B＝C，对吗？

（2） 若已知AB＝AC，则Ｂ＝Ｃ，对吗？

（3） 若已知A+B＝Ａ+C，且AB＝AC，则B＝C，对吗？

3.14用代数化简法将下列函数化简为“与或”表达式： 

（1） F＝C+BC+ABC+AB

（2） F＝A+B+BCD

（3） F＝ABC+++

（4） F＝+（AB+Ａ+B）C

（5） F＝A［B+(D+)］

（6） F＝(A+B)(+)

（7） F＝（X+Y+Z+）（V+X）（+Y+Z+）

（8） F＝ABC++BC

（9） F＝ABC(A+B+C)

（10） F＝(+ABC)(AC)

3.15用卡诺图法将下列函数化为最简“与或”表达式： 

（1）  F（A，B，C）＝∑m（0，1，2，4，5，7）

（2）  F（A，B，C，D）＝∑m（0，1，2，3，4，6，7，8，9，11，15） 

（3）  F（A，B，C，D）＝∑m（3，4，5，7，9，13，14，15）

（4）  F（A，B，C，D）＝∑m（0，1，2，5，6，7，8，9，13，14） 

（5）  F（A，B，C，D）＝∑m（0，2，3，5，7，8，10，11）+∑d（14，15） 

（6）  F（A，B，C，D，E）＝∑m（0，3，4，6，7，8，11，15，16，17，20，22，25，27，29，30，31） 

（7）  F（A，B，C，D，E）＝∑m（0，1，2，3，4，5，6，7，16，17，20，21）+∑d（24，25，27，28，30）

（8）  F（A，B，C，D，E）＝∏M（0，1，2，3，8，9，16，17，20，21，24，25，28，29，30，31）·∏d（13，14，19）

3.16用QM法求下列函数的所有质蕴涵： 

（1） F（A，B，C，D）＝∑m（0，1，2，3，6，7，8，9，10，13，14，15）

（2）  F（A，B，C，D）＝∑m（0，1，2，3，6，7，9，10，14，15）+∑d（8，13）

（3）  F（A，B，C，D，E）＝∑m（0，2，4，9，11，14，15，16，17，19，23，25，29，31）

3.17求下列函数的最简“或与”式： 

（1） F（A，B，C，D）＝∑m（4，5，6，13，14，15）

（2） F（A，B，C，D）＝∑m（4，5，6，13，14，15）+∑d（8，9，10）

3.18某单位有5位外语人员： A会英语和法语，B会英语和俄语，C会俄语和日语，D会德语，E会日语和法语。

（1） 外地有一外事活动，要求英、俄、日、德、法5种外语，求最经济的出差方案。

（2） 试写出这5人中两两进行外语会话的条件（这里指只有两人在场的会话）。

3.19已知F＝F（A，B，C，D）的全部质蕴涵为、、D、CD、B、BC、AD、AC。求F的最简与或式。要求： 列质蕴涵表，找必要质蕴涵，列简化的质蕴涵表，找最小质蕴涵覆盖。

3.20用QM法化简下列函数： 

（1） F（A，B，C，D，E）＝∏M（0，1，2，3，8，9，10，11，17，19，21，23，25，27，29，31）

（2）  F（A，B，C，D，E）＝∏M（0，2，4，6，8，10，12，14，16，18，20，22，25，27，29，31）·
∏d（5，7，13，15，24，26，28，30）

3.21用公式和定理化简下列函数： 

（1） F（A，B，C）＝ABC+C+B+A+

（2） F（A，B，C）＝AC+ABC+A++BC

3.22用卡诺图化简如下函数，并列出它们的质蕴涵项和必要质蕴涵项： 

（1） F（x1，x2，x3，x4）＝∑m（0，1，4，7，9，10，13）+∑d（2，5，8，12，15）

（2） F（X1，X2，X3，X4）＝∏M（0，13，15）·∏d（3，7，9，10，12，14）

3.23用卡诺图化简如下四变量函数： 
F（A，B，C，D）＝F1（A，B，C，D）F2（A，B，C，D）
其中，F1＝D+BC++∑d（2，11，13）

F2＝∏M（0，2，4，8，9，10，14）·∏d（1，7，13，15）

3.24用两函数卡诺图之对应单元相加的方法求两函数的布尔和F1+F２。其中
F1（x1，x2，x3，x4）＝∑m（0，3，10，12，15）+∑d（5，6，9）
F2（x1，x2，x3，x4）＝∑m（0，2，5，10，15）+∑d（1，6，12）
3.25用两函数卡诺图的对应单元相乘的方法求两函数的布尔积F1·F2。其中
F1（x1，x2，x3，x4）＝∑m（0，2，12，14）+∑d（3，5，9，15）
F2（x1，x2，x3，x4）＝∑m（5，6，10，12）+∑d（1，2，8，9，15）
3.26化简下列多输出函数： 

（1） F1（A，B，C，D）＝A+D+D

 F2（A，B，C，D）＝+ABD+D

 F3（A，B，C，D）＝+ABCD+

（2） F1（A，B，C，D）＝∑m（2，3，4，5，6，7，11，14）+∑d（9，10，13，15）

 F2（A，B，C，D）＝∑m（0，1，3，4，5，7，11，14）+∑d（8，10，12，13）