《计算机组成原理》 课件 第3、4章 布尔代数基础、组合逻辑电路

第3章布尔代数基础逻辑代数：从哲学领域中的逻辑学发展而来，用数学的语言来描述逻辑思维的科学。是数字电路的基础。布尔代数：乔治.布尔1847年进行了系统论述开关代数：1938年

克劳德.香农将布尔代数用于电话继电器的开关电路逻辑量：取值只有“是”和“非”，分别对应代数的“1”和“0”，电路的“通”和“断”等。逻辑运算：逻辑思维和逻辑推理的数学描述。布尔函数：命题的结论与前提之间的因果关系。表示方法：函数表达式3.1布尔代数的基本概念3.2

布尔代数的公式、定理和规则3.3布尔函数的基本形式3.4不完全确定的布尔函数3.4布尔函数的化简(1)或运算(逻辑加)定义：当决定事件(Y)发生的各种条件(A，B，C，…)中，只要有一个条件具备，事件(Y)就发生。表达式为：Ｙ＝Ａ+Ｂ或Ｙ＝Ａ∨Ｂ

Ｙ＝Ａ＋Ｂ＋Ｃ＋…开关A，B并联控制灯泡Y3.1.1布尔变量及其基本运算3.1布尔代数的基本概念继续返回真值表功能表或运算规则：继续返回或门：实现“或逻辑”的电路。

或门逻辑符号：+(a)我国常用符号(b)国外常用符号(c)国标符号(2)与运算(逻辑乘)定义：仅当决定事件(Y)发生的所有条件(A，B，C，…)

均满足时，事件(Y)才能发生。表达式为：Y＝ABC…..Ｙ＝ＡＢ或Ｙ＝Ａ∧Ｂ

.真值表：把所有可能的条件组合及其对应结果一一列出来的表格。功能表真值表开关：“闭合”记作1，“断开”记作0

灯：“亮”记作1，“灭”记作0与运算规则：开关A，B串联控制灯泡Y与门：实现逻辑与运算的电路。

与门逻辑符号：继续返回Ｙ＝ＡＢ.(a)我国常用符号(b)国外常用符号(c)国标符号(3)非运算定义：非逻辑指的是逻辑的否定。当决定事件(Y)发生的条件(A)满足时，事件不发生；反之事件(Y)发生。表达式为：

开关A控制灯泡YＹ＝ＡＹ＝Ａ逻辑非运算也就是我们经常说的“取反”。A接通，灯灭。真值表功能表A断开，灯亮。非门：实现非逻辑的电路。

非门逻辑符号：(a)我国常用符号(b)国外常用符号(c)国标符号继续返回

复合逻辑运算：

将三种基本逻辑运算进行组合的运算，如“与非”、“或非”、“与或非”等。常用复合逻辑：“与非”逻辑“或非”逻辑“与或非”逻辑“异或”和“同或”逻辑(1)“与非”逻辑表达式：真值表（先“与”后“非”）(a)我国常用符号(b)国外常用符号(c)国标符号

与非门逻辑符号(2)“或非”逻辑表达式：真值表（先“或”后“非”）(a)我国常用符号(b)国外常用符号(c)国标符号

或非门逻辑符号＋(3)“与或非”逻辑表达式：(a)我国常用符号(b)国外常用符号(c)国标符号与或非门逻辑符号真值表：练习完成。＋(4)“异或”逻辑表达式：真值表(a)我国常用符号(b)国外常用符号(c)国标符号异或门逻辑符号(5)“同或”逻辑表达式：(a)我国常用符号(b)国外常用符号同或门逻辑符号真值表(c)国标符号3.1.2布尔函数及其表示方法设（x1，x2，…，xn）为布尔代数的一组布尔变量，其中每个变量取值为0或1，则当把n序列（x1，x2，…，xn）映射到B＝{0，1}时，这个映射就是一个布尔函数。

从另一个角度：

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

F＝f(x1，x2，…，xn）F：输出变量A、B、C：输入变量原变量反变量1.布尔表达式:

由逻辑变量和逻辑运算构成的式子。在布尔表达式中，等式右边的字母称输入逻辑变量，等式左边的字母称为输出逻辑变量。字母上面没有非运算符的叫做原变量，有非运算符的叫做反变量。2.真值表：一种由逻辑变量的所有可能取值组合以及对应的布尔函数值所构成的表格。

（n个逻辑变量一共有2n中可能的取值组合）3.卡诺图：用图形描述布尔函数的方法。真值表0001111001ABC10110110卡诺图3.1.3布尔函数的“相等：概念1.设有两个布尔函数F＝f(x1，x2，…，xn）G＝g(x1，x2，…，xn）其变量都为x1，x2，…，xn。

如果对应于变量x1，x2，…，xn的任何一组变量取值，F和G的值都相同，则称F和G是相等的，记为F＝G。若两个布尔函数相等，则它们的真值表一定相同；反之，若两个布尔函数的真值表完全相同，则此两个函数相等。

【例】设有两个函数：

F1=A+BCF2=(A+B)(A+C)

求证：F1=F2

。解：这两个函数都具有三个变量，有23=8组逻辑取值，其真值表如表所示。由表可见，对应于A,B,C的每组取值，函数F1和F2

的值均相等，所以F1=F2

。

3.2布尔代数的公式、定理和规则3.2.1布尔代数的基本公式

逻辑常量之间的关系

基本定律继续返回（公理）证：A+A=（A+A）

1

0－1律

=（A+A）（A+A

）互补律

=A+AA分配律

=A+0互补律

=A0－1律

——（根据分配律可证明）继续返回证明：吸收率根据分配率得证明：冗余率根据互补率得继续返回3.2.2布尔代数的主要定理定理1德·摩根（DeMorgan）定理。

（1）

（2）定理2

香农（Shannon）定理。

任何函数的反函数（或称补函数），可以通过对该函数的所有变量取反，并将常量1换为0，0换为1，运算符“＋”换为“·”，“·”换为“＋”而得到。证明：根据德·摩根定理，任何函数的反函数可写成＝＝或写成：＝＝例：已知函数，求其反函数

。利用香农定理，可以直接写出：定理3展开定理。

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

＝xif(x1,x2，….,１,…，xn）＋

f(x1,x2,…,0,…,xn）

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

＝（xi

＋f(x1,x2,…,０,…,xn）)·（＋f(x1,x2,…,１,…,xn）)证明将xi＝1，

＝0代入（1）、（2）式，

再将xi＝0，

＝1代入（1）、（2）式，

则两种情况下等式均成立。由展开定理可得下列两个推理：

推理1

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

（b）xi

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

推理2

（a）

f(x1，…，xi，…，xn）＝

f(x1，…，0，…，xn）

（b）

＋f(x1，…，xi，…，xn）＝

＋f(x1，…，1，…，xn）继续返回3.2.3布尔代数的重要规则

代入规则:用同一个布尔函数代替等式中所有出现的某一变量，等式仍然成立。例如:已知等式，用函数Y=AC代替等式中的A，根据代入规则，等式仍然成立，即有：继续返回b.对偶规则（求对偶式）

将布尔函数表达式Y中的所有“·”换成“＋”，“＋”换成“·”，“0”换成“1”，“1”换成“0”，原有逻辑优先级不变，逻辑变量不变，则得到的表达式G与原表达式Y互为对偶函数。例如:转换:“与”、“或”逻辑互换，逻辑常量。不变:逻辑优先级、逻辑变量。对偶注意：括号保证了优先级不变。继续返回对偶法则：若两个函数F和G相等，则其对偶函数F'和G'

也相等。已知

AB+C+BC=AB+CF=G=>F’=G’则有（A+B）C（B+C）=（A+B）Cc.反演规则（求反演式）

对于布尔函数表达式Y，如果将表达式中的所有“·”换成“＋”，“＋”换成“·”，“0”换成“1”，“1”换成“0”，原变量换成反变量，反变量换成原变量，优先级不变后所得表达式是原函数Y的反函数(补函数)。例如:转换:逻辑远算、逻辑常量、逻辑变量。反演反演不变:逻辑优先级。继续返回

积之和表达式：“积项”的“逻辑或”运算构成的表达式。

和之积表达式：“和项”的“逻辑与”运算构成的表达式。积项：逻辑变量的“逻辑与”运算项。例如：例：3.3.1函数的“积之和”与“和之积”形式又称为“积之和”表达式。与项或积项又称为“和之积”表达式。或项或和项3.3布尔函数的基本形式1.标准积之和表达式（最小项表达式，标准的与或表达式）

标准积（最小项）：是逻辑代数中的重要概念。

如果一个具有n个变量的函数的与项（积项）包含全部n个变量,每个变量都以原变量或反变量形式出现,且仅出现一次，则这个与项被称为标准积项或最小项(mi)。

最小项表达式：假如一个函数完全由最小项所组成,那么

该函数表达式称为标准积之和表达式,

即最小项表达式。ABCCABBCACBACBAF+++=),,(例如：最小项或标准积项3.3.2函数的“标准积之和”与“标准和之积”形式三变量最小项（8个）对照表n个变量可能的最小项有2n个取编号mi方法：

1.原变量取“1”,反变量取“0”，

2.变量顺序确定后,最小项构成“二进制数”所对应的十进制即为i。=m2+m3+m6+m7注意：变量的顺序.=

m(2,3,6,7)继续返回

最小项的性质全体最小项之和为1；每个最小项只有对应的一组变量取值能使其值为1。任意不同最小项之积为0；n个逻辑变量有2n项最小项，且对每一最小项而言，有

n个相邻最小项。相邻项：任何两个由相同变量组成的逻辑项，只有一个变量取值不同，则称它们为相邻项。的相邻项有例如：、、。2.标准和之积表达式（最大项表达式，标准的或与表达式）

标准和项（最大项）

对于n个变量，如果P是含有n个因子的或项，其中每个因子都是以某个变量的原变量或者反变量的形式出现一次，且仅只出现一次，则称P为n个变量的一个标准和项或最大项(Mi)。n个变量可能的最大项有2n个。

最大项表达式：假如一个函数完全由最大项所组成,

那么该函数表达式称为标准和之积”

表达式,即最大项表达式。例如：二变量A、B构成的最大项最多有四个即A+B，A+B，A+B，A+B。编号最大项ABC取值序号

取编号Mi方法

1.原变量取“0”,反变量取“1”2.变量顺序确定后,最大项构成“二进制数”所对应的十进制即为i。例如：继续返回4）n个变量的每一个最大项有n个相邻项(其余项相同,有一项互补)。例:

最大项的性质与最小项类似，有5）且有3）Mi+Mj=1()的相邻项有、、2）每个最大项只有对应的一组变量取值能使其值为0。变量的各组取值ABC0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1对应的最小项及其编号对应的最大项及其编号最小项编号最大项编号继续返回最大项与最小项对应关系表3.函数表达式的转换

任何一个布尔函数，总可以将其转换成“最小项之和”及“最大项之积”的形式，常用代数转换法或真值表转换法。

代数演算法用代数法求一个函数"最小项之和"的形式，一般分为两步：第一步：将函数表达式变换成一般的“与或”式。第二步：反复使用X=X（Y+Y）将非最小项的"与项"扩展为最小项。例：例：将F(A,B,C)=(AB+BC)

AB转换成"最小项之和"形式

类似地，用代数法求一个函数"最大项之积"的形式，也可分为两步：第一步：将函数表达式转换成一般"或与"式；第二步：反复使用将非最大项的"或项"扩展成为最大项

列表法：利用真值表进行转换

一个布尔函数的真值表与它的最小项表达式和最大项表达式均存在一一对应的关系。函数F的最小项表达式：由使F取值为1的全部最小项之

和组成。函数F的最大项表达式：由使F取值为0的全部最大项之

积组成。真值表真值表

函数最小项表达式与最大项表达式间的关系结论：注意：任何一个布尔函数的两种标准形式唯一。完全确定的布尔函数函数的每一组输入变量的取值，都能得到一个完全确定的函数值（0或1）。不完全确定的布尔函数函数的某组输入变量的取值，能得到一个完全确定的函数值（0或1），而对于某些输入变量的取值，函数没有确定值。随意项（无关项）：一个布尔函数,如果它的某些输入取值组合因受特殊原因制约而不会再现,或者虽然每种输入取值组合都可能出现,但此时函数取值为1还是为0无关紧要,那么这些输入取值组合所对应的最小项称为随意项。无关项或随意项常用字母d或×表示。3.4不完全确定的的布尔函数

例

设计一个奇偶判别电路，其输入为一位十进制的BCD码。当输入为偶数时，电路输出为0；当输入为奇数时，电路输出为１，如图所示。根据设计要求可以列出描述该电路的布尔函数真值表其中：第10-15行是不确定的函数的表达式为：F（A，B，C，Ｄ）＝∑m(1,3,5,7,9)＋∑d(10,11,12,13,14,15)

（式中，d表示随意项，可取0，也可取1）下面分两种情况来考虑：（1）如果不考虑随意项（即取d＝0），则有（2）如果考虑随意项，且取随意项11、13、15的值为1，其

余随意项取值为0，则有F（A，B，C，Ｄ）＝∑m(1,3,5,7,9)＋(11,13,15)

＝∑m（1，3，5，7，9，11，13，15）

＝D十进制数rBCDF(A,B,C,D)ABCD000000100011200100300111401000501011601100701111810000910011101010d111011d121100d131101d141110d151111d

如何得到最简的逻辑表达式？不同类型的表达式标准不一，我们在这里主要讨论与或表达式的最简化问题。最简的标准：乘积项（与项）个数应最少；在上述前提下，每项中的变量个数也最少。或与表达式的最简化标准类同。有三种常用的方法：代数化简法卡诺图化简法列表化简法3.5布尔函数的化简

运用逻辑代数的公理、定理和规则对布尔函数进行推导、变换而进行化简，没有固定的步骤可以遵循，主要取决于对公理、定理和规则的熟练掌握及灵活运用的程度。有时很难判定结果是否为最简。3.5.1代数化简法继续返回继续返回继续返回或与式的化简可以利用对偶式

简单、直观、容易掌握，当变量个数小于等于6时非常有效，在逻辑设计中得到广泛应用。1.卡诺图的构成卡诺图是真值表的重新排列把真值表中的最小项排列成矩阵形式，且使矩阵的横方向和纵方向的布尔变量的取值按Gray码的顺序排列。n个变量的卡诺图由2n个小方格构成每一个小方格表示布尔函数的一个最小项最小项在卡诺图中的位置满足相邻性规则：任意两个相邻最小项在卡诺图中也是相邻的。3.5.2卡诺图化简法继续返回

二变量卡诺图mo

m2m1

m30 101ABAB0 1012个变量有22=4个最小项,4个小方格；每个最小项有2个相邻项；0123继续返回

三变量卡诺图3个变量有23=8个最小项；每个最小项有3个相邻项；列AB排列00,01,11,10(2位Gray码)mo

m2m6

m4m1

m3m7

m50001111001ABC0001111001ABC01234567继续返回

四变量卡诺图04

1281

5

1393715112614100001111000011110ABCD0001111000011110ABCD继续返回

五变量卡诺图ABC00000101101000011110DE10010111111004

1281

5

1393715112614101620

282417

21

292519233127182230262.卡诺图的特点n个变量的卡诺图由2n个小方格组成,每个小方格代表一个最小项。0对应最小项“反变量”

1对应最小项“原变量”n个变量的每个最小项有n个相邻项卡诺图上相邻最小项包括几何相邻、边缘相邻、重叠相邻。几何相邻：相邻项在几何位置上是相邻。边缘相邻：相邻项在图形的上下缘或左右缘相连后相邻。重叠相邻(对于5,6变量)：左右、上下图形重叠后相邻。3.布尔函数在卡诺图上的表示ABCD1)布尔函数表达式为“最小项之和”的形式

将逻辑函数所对应的最小项在卡诺图的相应方格中标以1，剩余方格标以0或不标。F（A，B，C）＝∑m（2，3，5，7）2）布尔函数是“与或”表达式的形式将各与项分别表示在卡诺图上，然后叠加起来。可表示为：例如：0001111001ABC111114.卡诺图的性质

在卡诺图上把相邻最小项所对应的小方格“圈”在一起可进行合并，以达到用一个简单"与项"代替若干最小项的目的。这样的"圈"称为"卡诺圈"。1）卡诺图上任何两个标1的相邻方格，可以合并为一项，并消去一个变量。0 101AB110 101AB110 101AB111BAAB0001111001ABC11110001111000011110ABCD1111ABAB112）卡诺图上任何四个标1的相邻方格，可以合并为一项，并消去两个变量。111101ABC00011110C继续返回3）卡诺图上任何八个标1的相邻方格，可以合并为一项，并消去三个变量。

一个卡诺圈中的小方格满足以下规律：卡诺圈中的小方格的数目为2m,m为整数2m个小方格含有m个不同变量和(n-m)个相同变量;

（合并为一项，消去m个变量）2m个小方格的卡诺圈可用(n-m)个变量的“与项”一一对应,该“与项”由这些最小项中的相同变量构成。（n:变量数）（1）几个概念蕴涵项：在函数的任何与或表达式中，每个与项称为该函数

的蕴涵项。

在函数的卡诺图中，任一标“1”的最小项以及由

2i个相邻最小项所形成的圈都是函数的蕴涵项。质蕴涵项：如果函数的某一蕴涵项不是该函数中其它蕴涵项

的一个子集，则此蕴涵项称为质蕴涵项。

从卡诺图上看，所谓质蕴涵项就是大得不能再大的圈。必要质蕴涵项：如果函数的一个质蕴涵项，至少包含了一个

其它任何质蕴涵项都不包含的标1最小项，

则此质蕴涵项称为必要质蕴涵项。5.卡诺图化简的基本步骤（2）基本步骤

①将布尔函数正确地标到卡诺图上，并在图上找出所有

质蕴涵项；

②求出所有必要质蕴涵项；

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

用卡诺图法化简函数F（A，B，C，D）＝∑m（0，3，4，5，7，11，13，15）

解（1）作F的卡诺图，并求得所有质蕴涵项为

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

（3）由于必要质蕴涵项的集合己覆盖了函数的所有最小

项，因此函数的最简与或式为例

用卡诺图化简布尔函数F（A，B，C，D）＝∑m（0，5，6，8，15）＋

∑d（1，2，3，7，10，12，13）利用随意项求质蕴涵时，如果它对化简有利，则取d＝1；如果它对化简不利，则取d＝0。解（1）作函数的卡诺图，求出所有质蕴涵项

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

（3）求最小覆盖。布尔函数的最简与或式为例

用卡诺图化简布尔函数F（A，B，C，D）＝∑m（0，4，6，7，8，9，11，12，13，15）解（1）求出所有质蕴涵项为

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

（3）求函数的最小覆盖。本例中必要质蕴涵只覆盖了函数的8个最小项，还剩下两个最小项m6，m7未被覆盖。由观察可知，在几个非必要质蕴涵中，选择

这一项即可覆盖m6，m7。因此，该函数的最简与或式为例

用卡诺图化简函数F（A，B，C，D）＝∑m（0，1，3，4，7，12，13，15）解

F的最简表达式为卡诺图法的缺点：

①由于要靠人对图形的识别能力，因此不便于机器实现；②当函数的变量数目大于6时，就失去它的优越性。列表法是一种更有规律、便于机器实现的方法，它由Quine和McCluskey在1956年提出，故称Q－M法。基本步骤如下：（1）找出函数的全部质蕴涵项；（2）找出其中的必要质蕴涵项；（3）求函数的最小覆盖。其步骤与卡诺图法一致，但是通过约定形式的表格，按照一定的规则求得。3.5.3列表化简法1.用列表法确定布尔函数的所有质蕴涵项首先将布尔函数用最小项来表示，并把最小项表示

成二进制数形式。

m4：表示成0100m5：表示成0101然后进行两两比较，如果两个二进制数只有一位不同，就可合并。逐次合并只有一位数值不同的两个二进制数，所得到的不能再合并的二进制数，其对应的乘积项，即为质蕴涵项。

例求下列函数的全部质蕴涵项：F（A，B，C，D）＝∑m（1，3，4，5，10，11，12，13）解用Q-M法求质蕴涵过程如下：

第一步列出最小项的二进制数形式：miABCD10001300114010050101101010111011121100131101第二步，按1的个数分组列表，并在相邻组之间进行搜索合并。凡是能合并的两个项，则在其后面打“√”，表示它们不是质蕴涵项，并将合并结果列于另一栏中。如此继续，直到无法合并为止。最后，那些没有打“√”的项，就是质蕴涵项Pi。最后，求得全部质蕴涵项为miABCDmiABCDmiABCD10001√1,300－1P24,5－10－P140100√1,50－01P312,1330011√4,5010－√50101√4,12－100√101010√3,11－011P4121100√5,13－101√111011√10,11101－P5131101√12,13110－√2.用质蕴涵表确定必要质蕴涵质蕴涵表：函数的各个质蕴涵覆盖函数的相应最小项的情况表。

例

已知函数F（A，B，C，D）＝∑m（1，3，4，5，10，11，12，13）求得它的全部质蕴涵为列质蕴涵表

mi

Pj134510111213√

×××××××√

×覆盖情况××××××必要质蕴涵是按下列步骤求得的

（1）逐列检查表中标有“×”号的情况，凡只标有一个

“×”号的列，则在该“×”的外面打一个圈。

（2）找出包含有

号的各行，这些行的质蕴涵项就是必要

质蕴涵项，并在其前加上标记“√”。

（3）在表的最后一行覆盖情况一栏中，标上必要质蕴涵项

覆盖最小项的情况。凡能被必要质蕴涵项覆盖的最小

项，在最后一行的该列上打“×”号。

本例中必要质直涵项3.求函数的最小覆盖必要质蕴涵覆盖函数的最小项的情况有两种可能一种是必要质蕴涵已覆盖了函数的所有最小项，对于这种情况，函数的简化工作就已完成，即函数的最小覆盖就是所有必要质蕴涵项。另一种是必要质蕴涵没有覆盖函数的所有最小项，对于这种情况，还需要选择适当的质蕴涵项，以覆盖剩下的最小项。那么，覆盖剩余的最小项所需的质蕴涵应该怎样选择才能使函数表达式最简呢？介绍两种常用的选取所需质蕴涵的方法（1）行列消去法

在质蕴涵表中，去掉必要质蕴涵项和已被其覆盖

的最小项，剩下的部分叫做简化的质蕴涵表。优势行规则设质蕴涵Pi和Pj是简化质蕴涵表中的两行，其中Pj行中的“×”完全包含在Pi行中，则称Pi为优势行，Pj为劣势行，记作Pi

Pj。在简化质蕴涵表中可以消去劣势行Pj。例如，在下表去掉必要质蕴涵项和被它所覆盖的最小项，得到简化的质蕴涵表。表中：P3相对于P2来说是劣势行，即P2

P3，可消去P3P4相对于P2来说也是劣势行，即P2

P4，可消去P4最后只剩下P2。

mi

Pj13P2××P3×P4×

mi

Pj134510111213√

×××××××√

×覆盖情况××××××优势列规则设最小项mi和mj是简化质蕴涵表中的两列，其中mj列中的“×”完全包含在mi列之中，则称mi列为优势列，mj为劣势列，记作mi

mj。在简化质蕴涵表中可以消去优势列mi。

例如，下表为简化质蕴涵表，表中的m2和m3相对于m1来说是劣势列，即m2

m1，m3

m1，故可消去优势列m1。

miPjm1m2m3P1××P2××P3×例

用行列消去法求所需质蕴涵项，设简化的质蕴涵表如表所示。表中：

根据优势行规则，有P4

P5，P3

P6，消去P5

和P6；根据优势列规则，由于m4

m6，m10

m2，故可消去m2和m6。最后，求得所需质蕴涵为P3和P4，它们覆盖了简化质蕴涵表的所有最小项m2，m4，m6和m10。

miPjm2m4m6m10P2××P3××P4××P5×P6×（2）布尔代数法布尔代数法：从简化质蕴涵表列出布尔表达式，

从中选出最简的所需质蕴涵项。例如，对于下表的简化质蕴涵表，要覆盖最小项m1，可选取质蕴涵项P2或P3；要覆盖最小项m3，可选取质蕴涵项P2或P4．因此，若要同时覆盖m1和m3，可以用如下布尔表达式来表示：

（P2＋P3）（P2＋P4）＝P2＋P2P4＋P2P3＋P3P4＝P2＋P3P4该式表明，同时覆盖m1和m3的方案有两个，即选用P2或选用P3

P4，其中选用P2最简单。

mi

Pj13P2××P3×P4×

例如，对于下表的简化质蕴涵表，若要同时覆盖最小项m2，m4，m6和m10，则有

（P2＋P3）（P4＋P5）（P2＋P4）（P3＋P6）＝（P3＋P2P6）（P4＋P2P5）

＝P3P4＋P2P3P5＋P2P4P6＋P2P5P6该式表明，可供选取的所需质蕴涵集有四个，其中只有P3P4最简单。所以，用布尔代数法求得所需质蕴涵项为P3和P4。

miPjm2m4m6m10P2××P3××P4××P5×P6×例

化简布尔函数F（A，B，C，D）＝∑m（2，4，6，8，9，10，12，13，15）

（1）求函数的所有质蕴涵，见表。miABCDmiABCDmiABCD20010√2,60－10P28,91－0－P140100√2,10－010P312,1381000√4,601－0P460110√4,12－100P591001√8,9100－√101010√8,1010－0P6121100√8,121－00√131101√9,131－01√151111√12,13110－√13,1511－1P7求得所有质蕴涵为：（2）求必要质蕴涵：P1和P7为必要质蕴涵。2468910121315√P1×××P2××P3××P4××P5××P6××√P7×覆盖情况×××××（3）求函数的最小覆盖。

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

利用前面讲的行列消去法或用代数法求得所需质蕴涵

为P3和P4，因此，函数的最简表达式为：

miPjm2m4m6m10P2××P3××P4××P5×P6×例

化简不完全确定的布尔函数F（A，B，C，D）＝∑m（1，3，4，5，10，11，12）

＋∑d（2，13）（1）求所有质蕴涵项。令所有随意项为1，见表。

求得所有质蕴涵项为miABCDmiABCDmiABCD10001√1,300－1P32,3－01－P120010√1,50－01P410,1140100√2,3001－√4,5－10－P230011√2,10－010√12,1350101√4,5010－√101010√4,12－100

√121100√3,11－011√111011√5,13－101√131101√10,11101－√12,13110－√（2）求必要质蕴涵。令所有的随意覆为0，即在质蕴涵表中不必列随意项，见表。

由表可确定必要质蕴涵为P1和P2。（3）求函数的最小覆盖。

去掉质蕴涵表中被必要质蕴涵覆盖的最小项后，只剩下最小项m1未被覆盖，直接从表可以选取P3或P4作为所需质蕴涵。因此，函数的最简表达式为

mi

Pj1345101112√P1×√P2×P3××P4××覆盖情况××××××第4章组合逻辑电路4.1常用逻辑门的图形符号4.2布尔函数的实现4.3组合电路的分析4.4组合电路的设计4.5常用组合电路4.6二进制译码器4.7多路选择器4.8多路分配器4.9组合电路中的险态数字系统的逻辑电路分为两大类组合逻辑电路时序逻辑电路组合逻辑电路：没有从输出到输入的反馈，且由功能完全的门系列构成的电路，即不含记忆元件（能存储信息，如触发器）的逻辑电路是组合逻辑电路。包含记忆元件的逻辑电路是时序逻辑电路组合逻辑的结构模型设：X是所有输入变量(x1，x2，…，xn)的集合Y是所有输出变量(y1，y2，…，yn)的集合Y=F(X)

组合逻辑电路也称为组合网络。在数字逻辑电路中，把能实现基本逻辑运算的单元电路称为逻辑门电路。常用逻辑门的图形符号4.1常用逻辑门的图形符号逻辑门国际符号国际常用符号我国部颁符号输出表达式与门或门非门与非门或非门异或门与或非门用与非门实现布尔函数：首先将函数化成最简“与或”形式；然后再对表达式二次取反，得到函数的“与非一与非”表达式；最后用与非门实现。4.2布尔函数的实现4.2.1用与非门实现布尔函数布尔函数的实现例

用与非门实现函数

（1）将函数化成最简“与或”形式F（A，B，C，D）＝AB＋AC＋AD

（2）再将上述表达式二次取反，则有（3）用与非门来实现该表达式，其逻辑电路图：用或非门实现布尔函数：首先将函数化成最简“或与”形式；然后再对表达式二次取反，得到函数的“或非一或非”表达式；最后用或非门实现。布尔函数的实现4.2.2用或非门实现布尔函数布尔函数的实现例

用或非门实现函数（1）将函数化简成“或与”形式

求得补函数

的最简“与或”式：

（2)对该式两边取一次反，求得函数F的“或与”表达式：F（A，B，C，D）＝A（B＋C＋D）（3）再对上述表达式二次取反，得函数的“或非-或非”表

达式：F（A，B，C，D）＝

＝

（4）用或非门来实现该表达式，其逻辑电路如图。布尔函数的实现用或非门实现布尔函数：首先将原函数化F成最简“与或”形式及的最简与或式；然后再对F表达式二次取反，对

表达式一次取反，得到函数F的两个与或非表达式；最后用与或非门实现，比较两者，取较简单的一个。布尔函数的实现4.2.3用与或非门实现布尔函数布尔函数的实现例

用与或非门实现函数（1）求F和

的最简“与或”式F（A，B，C，D）＝AB＋AC＋AD（2）再求得

的最简“与或”式（3）对F的最简式二次取反，则得F（A，B，C，D）＝

（4）再对补函数

的最简式一次取反，则得F（A，B，C，D）＝

（5）用与或非门来实现上述两个表达式布尔函数的实现组合网络的分析方法，一般可概括为以下几个步骤：根据给定的逻辑电路图，写出布尔函数表达式；将得到的布尔函数表达式化简；

由简化的布尔函数表达式列出真值表；判断该电路所能完成的逻辑功能，作出简要的文

字描述，或进行改进设计。4.3组合电路的分析组合电路的分析例

分析图所示逻辑电路的逻辑功能。

（1）由图写出布尔函数表达式。

为了分析方便，可先写出各个门的输出表达式，再写出总的布尔表达式，则有：L＝

，M＝，N＝

F＝

＝组合电路的分析（2）化简表达式用卡诺图化简法，可得:（3）列真值表（4）由真值表可知，只要输入A，B，C的取值不一样，输出F就为1；否则，当A，B，C取值一样时，F为0．所以这是一个三变量的非一致电路。电路无反变量输入，这是它的特点。组合电路的分析ABCF00000011010101111001101111011110组合电路的分析例

分析图所示的逻辑电路。（1）由图写出布尔函数表达式SH＝

＝B＋A＝AB

CH＝

＝AB（2）化简函数函数形式已是最简。（3）列真值表组合电路的分析（4）电路逻辑功能的描述。

由真值表可知：

该电路是求A、B的和以及进位，分别是ＳH、、ＣH。半加器：把能对两个一位二进制数进行相加而求得“和”及“进位”的逻辑电路称之为半加器。

逻辑框图如图：其中，A，B分别为两个一位二进制数的输入；SH，CH分别为相加形成的“和”及“进位”。

半加器还可以用异或门、与门实现。ＡＢＳHＣH0000011010101101组合网络的设计方法，一般可概括为以下几个步骤：根据设计的逻辑要求列出真值表；最关键的是第一步根据真值表写出布尔函数表达式；化简函数表达式；

根据给定的逻辑门，画出逻辑图。4.4组合电路的设计组合电路的设计例设两个一位二进制数为x1和y1，试设计比较器，如x1＞y1，输出1，否则输出0。（1）根据逻辑要求列真值表

显然，这里变量为x1和y1，而x1＞y1比较结果为输出，根据题意，列出真值表。（2）由真值表写出函数表达式：F=∑m（2）=x1

（该式已为最简）x1y1F(x1,y1)000010101110组合电路的设计（3）画出逻辑电路图。

用与门来实现，且输入信号中原变量和反变量都存在。组合电路的设计例

设x和y是两个两位的二进制数，其中x＝x1x2，y＝y1y2。

试设计比较器，如x＞y，输出1，否则输出0。（1）根据逻辑要求列真值表这是一个部分真值表，表中只列出使F为1的那些输入组合。d表示变量可取0，也可取1。x1y1x2y2F(x1,y1)10dd10010111101组合电路的设计（2）由真值表写出函数表达式：F=∑m（2，8，9，10，11，14）（3）化简：由卡诺图化简得

（4）画出逻辑电路图。如用与非门来实现，且输入信号中原变量和反变量都存在。F=组合电路的设计例

设计一个操作码形成器，如图所示。当按下＋、－、×各个操作键时，要求分别产生加法、减法和乘法的操作码01、10和11。（1）根据逻辑要求列真值表根据题意，所要设计的线路有三个输入，即＋、－、×三个按键，分别用变量A、B、C来表示；输出函数为F1和F2。组合电路的设计当按下某一按键时，相应输入变量的取值为1：否则，取值为0。在正常操作下，每次只允许按下一个按键，而不允许同时按下两个或两个以上按键。因此，A、B、C三个变量中同时有两个或两个以上取值为1的情况，就作为随意项处理。ABCF１

F２000000011101010011dd10001101dd110dd111dd组合电路的设计（2）由真值表写出函数表达式：F1=∑m（1，2）+∑d（3，5，6，7）F2=∑m（1，4）+∑d（3，5，6，7）（3）化简：由卡诺图化简得F1=B+C，F2=A+C（4）画出逻辑电路图（用或门来实现）实现二进制加法运算的逻辑电路，通常称为加法器。全加器（FullAdder）能对两个一位二进制数相加并考虑低位来的进位，即相当于三个一位二进制数的相加，得到“和”及“进位”的逻辑电路，称之为全加器。逻辑框图Ai和Bi分别为两个一位二进制数的输入；Ci-1为低位来的进位输入；Si和Ci分别为相加后形成的“和”及向高位的“进位”输出。4.5常用组合电路4.5.1加法器常用组合电路设计步骤列真值表写出函数的表达式Si＝∑m（1，2，4，7）Ci＝∑m（3，5，6，7）化简AiBiCi-1SiCi0000000110010100110110010101011100111111常用组合电路画逻辑图

根据给定的不同类型门电路，将布尔函数Si和Ci变换成不同形式。

方案一

用或非门实现全加器。比较上面两式可发现，它们互为对偶式。

即（Si）d＝Si，（Ci）d＝Ci，这种函数称为自对偶函数。常用组合电路方案二

用与或非门实现全加器。

Si＝Ci＝常用组合电路如果有两个n位二进制数相加，就需n位全加器，这样构成的逻辑电路称为多位并行加法器。按照进位方式的不同，并行加法器分为行波进位加法器和先行进位加法器两种。行波进位加法器把n位全加器串联起来，低位全加器的进位输出连到相邻的高位全加器的进位输入。常用组合电路形成进位的速度很慢若每级全加器形成进位的延时为2tpd，则在最坏情况下，从FA1的输入到产生高位进位Cn需要时间为2tpd×n．当n增大时，完成一次加法所需时间也随之增加。先行进位加法器根据进位表达式Ci＝AiBi＋（AiBi）Ci-1令Gi＝AiBi

Pi＝（AiBi）Ci-1（Gi为第i位的进位生成项；称Pi为进位传递条件）则Ci＝Gi＋PiCi-1

Si＝AiBiCi-1＝PiCi-1

常用组合电路S1＝P1C0

C1＝G1＋P1C0S2＝P2C1C2＝G2＋P2C1＝G2＋P2G1＋P2P1C0S3＝P3C2C3＝G3＋P3C2＝G3＋P3G2＋P3P2G1＋P3P2P1C0S4＝P4C3C4＝G4＋P4C3＝G4＋P4G3＋P4P3G2＋P4P3P2G1＋P4P3P2P1C0

……Sn＝PnCn-1Cn＝Gn＋PnCn-1＝Gn＋PnGn-1＋PnPn-1Gn-2＋…＋PnPn-1…P2G1

＋PnPn-1…P2P1C0常用组合电路常用组合电路BCD码编码器BCD码编码器的输入为10线十进制数字，十根输入线D0，D1，…，D9

分别表示数字0，1，…，9；输出为4线BCD码B8，B4，B2，B1。4.5.2十进制数字的七段显示常用组合电路BCD码编码器的设计步骤列真值表D9D8D7D6D5D4D3D2D1D0B8B4B2B1000000000000000100000000100001200000001000010300000010000011400000100000100500001000000101600010000000110700100000000111801000000001000910000000001001常用组合电路列函数表达式B1＝D1＋D3＋D5＋D7＋D9

B2＝D2＋D3＋D6＋D7B3＝D4＋D5＋D6＋D7

B1＝D8＋D9表达式已为最简。如果用或非门和与非门混合使用，且考虑公用部分，表达式可变换为常用组合电路画出逻辑图常用组合电路BCD-七段译码器的设计BCD七段译码器的输入为BCD码B8，B4，B2和B1，输出为七段显示器的输入代码a～g。BCD-七段译码器的设计步骤列真值表输入变量为四个：B8，B4，B2和B1输出函数有七个：a～g常用组合电路B8B4B2B1abcdefg000001111110100010110000200101101101300111111001401000110011501011011011601100011111701111110000810001111111910011110011101010ddddddd111011ddddddd121100ddddddd131101ddddddd141110ddddddd151111ddddddd列函数表达式并化简画出逻辑图（用与非门实现）二进制比较器是用来完成两个二进制数的大小比较的逻辑电路，简称比较器。又称数值比较器或数字比较器。4.4节已经举例说明一位和两位比较器的电路设计。4.5.3二进制比较器译码器：从广义来说就是把一种代码转换为另一种代码

的逻辑电路。二进制译码器：计算机中最常用的一种译码器。4.6二进制译码器4.6.1二进制译码器的功能和组成二进制译码器有n个输入，2n个输出。对应于每一种输入组合，2n个输出中只有一个输出为1，其余全为0，或者只有一个输出为0，其余全为1。二进制译码器例如，n＝3时，译码器的框图和真值表如图所示。

图中，A1，A2和A3为输入，Y0～Y7为输出。

把输入变量看作三位代码，而输出为八位代码，常常称之为3入-８出译码器。二进制译码器组成译码器的形式很多，常见的有如下几种：用与门构成的译码器二进制译码器用或非门构成的译码器二进制译码器常用的中规模集成译码器有双2-4译码器74139，3-8译码器74138等。为了充分利用封装的全部引线端并增强其逻辑功能，集成译码器常常带有若干个“使能端”。“使能端”的作用有两个：一是便于扩展译码器的输入变量数；二是在“使能端”加选通脉冲可以消除由于输入倒相门的延时带来的险态。4.6.2用中规模集成译码器进行设计二进制译码器3-8译码器74138其中：E1、

、为“使能端”。当E1＝1，E2A、E2B均为0时，译码器处于工作状态；

当E1＝0，或者当E2A、E2B中有一个为1时，译码器处于

禁止状态。二进制译码器例

用三变量译码器构成四变量译码器。将“使能端”作为变量输入端，可以将两块三变量译码器扩展成四变量译码器。二进制译码器例用译码器实现一位全加器电路。从全加器的真值表，可以得到全加器的函数表达式为Si（Ai，Bi，Ci-1）＝∑m（1，2，4，7）Ci（Ai，Bi，Ci-1）＝∑m（3，5，6，7）我们可以用三变量译码器的八个最小项输出来形成所需函数。又叫数据选择器4.7多路选择器4.7.1多路选择器的逻辑功能和组成多路选择器的逻辑功能从多个输入中选择一个，并把其信息传送到输出端，具体选择哪一个输入，则由一组选择变量确定。通常多路选择器有2n根输入线，n根选择线和一根输出线，根据n个选择变量的不同代码组合来选择2n个不同的输入。例如：四路选择器需要2个选择变量，八路选择器需要3个输入选择变量。一个四路选择器的框图和逻辑图I0～I3为四个数据输入端；S1和S0为选择变量输入端。根据S1和S0的四种不同取值来控制四路数据输入。F为选择器的输出。其中，mi为S1、S0组成的最小项。多路选择器多路选择器多路选择器用多路选择器来实现函数的设计