《逻辑与计算机设计基础(原书第5版)》——2.3 标准形式

时间:2024-02-23 17:44:59

2.3 标准形式

布尔函数的代数形式可以有多种,但有一些特殊的方法可以用来求布尔表达式的标准形式。标准形式可以使简化布尔表达式的过程更加方便,在某些情况下可以使逻辑电路更加合乎要求。
标准形式包括乘积项(product term)与求和项(sum term)。乘积项XYZ是由三个文字的与运算组成的逻辑积,而求和项X+Y+Z是由这些文字的或运算组成的逻辑和。在布尔代数中,“积”与“和”不表示算术运算,而是分别表示与和或逻辑运算。
2.3.1 最小项和最大项
一个真值表定义一个布尔函数,一个布尔函数可以用乘积项的逻辑和来表示,对应这些乘积项函数的值为逻辑1。如果所有的变量都以原变量或反变量的形式出现,且仅出现一次,这样的乘积项叫做最小项(minterm)。其特征是在真值表中仅仅表示二进制变量的一个组合,而且对于那种组合其值为1,对其他所有组合其值为0。对于n个变量,一共有2n个不同的最小项。XY、XY、XY和XY是二变量X、Y的4个最小项。三变量X、Y和Z可以组成8个最小项,如表2-9所示。从000到111的二进制数字列在变量的下面。每一个二进制组合都有一个与之关联的最小项,每个最小项是一个含有刚好n个变量的乘积项,n是变量的个数,此例中n=3。如果一个二进制组合中某一位的值为0则对应文字为反变量,否则为原变量。表中用符号mj来表示最小项,其中下标j是与最小项所对应的二进制组合相等的十进制数。任何n个变量的最小项列表都可以用这种类似列表的形式表示,表中的二进制数为0~2n―1。另外,真值表中的每一个最小项放在表的右半部,它清楚地显示了每一个最小项取值为1所对应的二进制组合以及取值0所对应的其他所有组合。这样的真值表对于后面讲述的利用最小项来获得布尔表达式很有用。
image

最大项(maxterm)定义为一个包含了所有变量的标准求和项,在这个求和项中每一个变量都以原变量或反变量的形式出现,所以n个变量可组成2n个最大项。由3个变量组成的8个最大项如表2-10所示,每个最大项都是3个变量的逻辑和,如果二进制数字的某一位为1,则对应的变量取反,否则不取反。最大项的符号是Mj,其中下标j是与最大项所对应的二进制组合相等的十进制数。每个最大项的取值情况均在表的右半部给出。注意观察最大项取值为0所对应的组合和取值为1所对应的其他所有组合,就可以清楚地看出“最小项”和“最大项”这两个名词的来由:最小项是一个不等于0的函数,它在真值表中有最少的1;而最大项是一个不等于1的函数,它在真值表中有最多的1。从表2-9和表2-10可以看出,有同样下标的最小项和最大项,它们之间是互补关系,即Mj=mj,mj=Mj。例如,假设j=3,则有

image

一个布尔函数可以由真值表中所有使函数取值为1的最小项的逻辑和来表示,这样的表达式叫做最小项之和(sum of minterm)。例如表2-11a中的布尔函数F,当变量X、Y、Z取000、010、101和111时,函数的值为1,这些组合对应最小项0、2、5和7。通过观察表2-11和这些最小项的真值表2-9,可以清楚地看出函数F可以用这些最小项的逻辑和的形式来表示:
image

这种表示形式可以进一步简化为用最小项的十进制下标来表示:
image

符号表示最小项的逻辑和(布尔或运算),后面的数字代表函数的最小项。当最小项转换成乘积项时,F后面括号中变量必须按顺序排列。
image

现在看看布尔函数的反函数形式。在表2-11a中,把F的值从1变为0、0变为1,可以得F的二进制值。求F的最小项的逻辑和可以得到
image

注意,F中最小项的数字就是F最小项表达式中缺少的数字。我们现在将F取反得到F:
image

上式表明了如何得到布尔函数最大项之积(product of maxterm)表达式的过程,这个积可以缩写为
F(X, Y, Z)=M(1, 3, 4, 6)
符号表示最大项的逻辑积(布尔与运算),括号中的数字表示最大项。注意,最大项之积中的十进制数字,与反函数中最小项的数字是一样的,如前面例子中的(1,3,4,6)。当处理布尔函数时,最大项的形式很少直接使用,因为我们总是可以用F的最小项形式来代替。
下面是对最小项最重要性质的总结:
1) n变量的布尔函数有2n个最小项,这些最小项可以用从0~2n―1的二进制数字表示。
2)任何布尔函数都可以用最小项逻辑和的形式来表示。
3)原函数的反函数所包括的最小项,在原函数中不包含。
4)包含全部2n个最小项的函数,其值等于逻辑1。
一个不是最小项之和形式的函数可以通过使用真值表转化成最小项之和的形式,因为真值表中给出了函数的最小项。例如布尔函数
image

这个表达式不是最小项之和的形式,因为每个项不包括所有X、Y和Z这3个变量。该函数的真值表如表2-11b所示,通过该表我们可以得到函数的最小项
image

注意,包含于函数E及反函数E中的全部最小项的个数等于8,因为函数有3个变量,3个变量一共产生8个最小项。4个变量的函数总共有16个最小项,2个变量的函数总共有4个最小项。一个包括全部最小项的函数如
G(X, Y)=m(0, 1, 2, 3)=1
因为G是一个2个变量的函数,而且包含全部4个最小项,其值总是等于逻辑1。
2.3.2 积之和
最小项之和是一种标准的代数表达式,可以直接从真值表中得到。这种形式的表达式因为每一个乘积项中包含了最多数目的文字,所以所包含的乘积项的数目比必须包含的通常更多一些。这是因为根据定义,每一个最小项必须包括函数中的所有变量,这些变量可以是原变量或反变量。一旦从真值表中得到了函数的最小项之和,下一步就是尝试着简化表达式,看是否可以减少乘积项的数目以及乘积项中文字的数目,其结果是一个简化了的积之和表达式(sum-of-product),这是另一种一个乘积项最多包含n个文字的积之和表达式的标准形式。一个布尔函数表达式积之和形式的例子是
image

这个表达式有3个乘积项,第一项有1个文字,第二项有3个文字,第三项有2个文字。
积之和形式的逻辑图由一组与门电路后接一个或门电路组成,如图2-9所示。除单个文字的乘积项外,每个乘积项都需要一个与门,逻辑和使用或门,其输入是单个文字和与门的输出。通常我们假设输入变量以原变量或反变量的形式存在,所以在电路图中不出现反相器。在与门后面接或门这样的电路结构形式,被称作为两级实现(two-level implementation)或者两级电路(two-level circuit)。image

如果一个表达式不是积之和的形式,可以通过分配律转换成标准形式,例如表达式
F=AB+C(D+E)
不是积之和形式,因为D+E这一项是乘积项的一部分,不是一个文字。这个表达式可以通过使用合适的分配律转换为积之和形式,如下所示
F=AB+C(D+E)=AB+CD+CE
函数F的非标准形式如图2-10a所示,它需要用两个与门和两个或门来实现,是一个有三级门的电路。函数F的积之和形式如图2-10b所示,电路需要三个与门和一个或门,是一个有两级门的电路。决定是使用一个两级门的电路还是一个多级门的电路(三级或更多级)是一个很复杂的问题,这涉及门电路的数量、门输入端的数量以及从设置输入值到出现输出响应的时间延迟。我们在第5章将会看到,两级电路形式对于某些实现技术来说是一种自然的选择。

image

2.3.3 和之积
另外一种布尔函数表达式的标准形式是和之积(product of sum)形式,它由一系列求和项的逻辑乘组成,每一个逻辑和项可以有任意数目的不同文字。一个函数和之积表达式的例子
image

这个表达式有三个求和项,分别含有一个文字、两个文字和三个文字。求和项完成或运算,乘积项实现与运算。
和之积表达式的门结构包括一组实现或运算的或门(除只有一个文字的乘积项外)和其后跟着的一个与门,前面提及的函数F的这种结构如图2-11所示。与积之和的逻辑图一样,表达式的这种标准形式会导致一种两级门的电路结构。image