卡诺图化简逻辑函数.docx

数字电子技术课程研讨卡诺图化简逻辑函数的方法和理论依据摘要：从最小项的定义和性质入手，简述卡诺图化简逻辑函数的理论依据以及化简是否达到最简形式的判定标准。通过举例来解释利用卡诺图化简少变量逻辑函数的一般方法，以及卡诺图在数字电子技术中其他应用。另外介绍一种多变量逻辑函数的卡诺图解法。关键词：卡诺图；最小项；逻辑函数化简；多变量0 引言在逻辑电路的分析和设计中，经常会遇到逻辑函数的化简问题。如果利用常规的公式法化简，除需要掌握大量的基本公式外，还需要能够灵活、交替地运用各种方法，方可求得最简结果，而且有时不易判断是否已简化到最简形式，技巧性较强，对使用者的要求较高。当所需化简的逻辑函数输入变量较少时（一般不大于4个），利用科诺图化简法可以更简单、直接的得到逻辑函数的最简表达式。因此逻辑函数的卡诺图化简法在实际分析、设计电路时有很广泛的应用。1 最小项定义及其性质1.1最小项的定义设有n个逻辑变量，由它们组成具有n个变量的“与”项中，每个变量以原变量或者反变量的形式出现一次且仅出现一次，则称这个与项为最小项。对于n个变量来说，可有2n个最小项。任何一个逻辑函数均可表示成惟一的一组最小项之和，称它为标准的与或表达式，也称为最小项表达式。对于任意一个最小项，只有一组变量取值使它的值为1，而变量的其他取值都使该最小项为0。事实上，真值表的每一行对应着一个最小项。表（1）中列出了最小项取值为1时，各输入变量的取值。我们约定：将最小项为l时各输入变量的取值视为二进制，其对应的十进制i作为最小项的编号，并把该最小项记作mi。如A、B、C三个变量有2n =8个最小项，如表（1）所示。图（1）最小项最小项为1时变量的值i的值miABCABC0000m0ABC0011m1ABC0102m2ABC0113m3ABC1004m4ABC1015m5ABC1106m6ABC1117m71.2最小项的性质最小项具有以下三个性质：(1)全体最小项之和为1；(2)任意两个最小项之积为0；(3)若两个最小项之间只有一个变量不同，即在一个最小项中是原变量，在另一个最小项中是反变量，其余各变量均相同，则称这两个最小项是相邻项。两个相邻的最小项之和可以合并成一个与项，并消去一个因子。这一性质很重要，这正是用卡诺图化简逻辑函数的逻辑依据。如：ABC+ABC=（A+A）BC=BC。2 卡诺图2.1 卡诺图把真值表中的最小项重新排列，把它们排列成矩阵形式，并且使矩阵的横方向和纵方向的布尔变量按格雷码的顺序排列，这样构成的图形就是卡诺图。卡诺图是逻辑函数的一种图形表示。将一个逻辑函数的最小项表达式中的各最小项相应地填入一个方格图内，此方格图即为卡诺图。卡诺图是一种平面方格图，每个小方格代表一个最小项，故又称为最小项方格图。卡诺图的实质就是真值表的图形化，使得最小项排列得更紧凑，更便于化简。卡诺图中最小项的排列方案不是惟一的；变量的坐标值0表示相应变量的反变量，1表示相应变量的原变量；各小方格依变量顺序取坐标值，所得二进制数对应的十进制数即相应最小项的下标i。对应于一组n个逻辑变量，则函数共有2n个最小项。如果把每个最小项用一个小方格表示，再将这些小方格以格雷码顺序排列，就可以构成n个变量的卡诺图。下面两图展示了3输入变量和4输入变量的卡诺图表示：AB图（2）CD000111100026411375图（3）CD00011110000412801151391137151110261410AB2.2 卡诺图的特点卡诺图是逻辑函数的一种图形表示，卡诺图的图形特征表现出了它的特点。卡诺图的特点主要有以下三点：（1）卡诺图中的每个小方格对应一个最小项。（2）具有循环相邻的特性，即卡诺图中同一行里最左和最右端的小方格是相邻的，同一列里最上和最下端的小方格也是相邻的。（3）逻辑相邻的最小项在几何位置上也相邻，这个特性是由于我们对变量的排布采用的是格雷码。 每个2输入变量的最小项有两个最小项与它相邻； 每个3输入变量的最小项有三个最小项与它相邻； 每个4输入变量的最小项有四个最小项与它相邻。2.3 卡诺图化简的基本原理用卡诺图化简逻辑函数的基本原理就是把“相邻的最小项之和可以合并成一个与项，并消去因子”的逻辑依据和卡诺图的图形特征结合起来，通过把卡诺图上表征相邻最小项的相邻小方格“圈”在一起进行合并，达到用一个简单“与”项代替若干最小项的目的。2.4 卡诺图化简的性质（1）卡诺图上任何21标1的相邻最小项，可以合并为一个“与”项，并消去一个变量。（2）卡诺图上任何22标l的相邻最小项，可以合并为一个“与”项，并消去二个变量。（3）卡诺图上任何23标1的相邻最小项，可以合并为一个“与”项，并消去三个变量。可见，相邻最小项的数目必须为2i个才能合并成一个“与”项，并消去ib变量。2.5 逻辑函数是否达到最简表达式的判断方法与-或式最简的标准是：首先表达式中的与项最少，其次是与项中的变量最少，在卡诺图上体现为：甩最少量的且尽可能大的圈覆盖函数的全部最小项。函数化简过程就是按最简的标准将相邻最小项在卡诺图上合并的过程。因此根据卡诺图化简法的基本原理，我们可以得到化简是否达到最简形式的判定标准：是否选择了尽可能少的方格群，且每个方格群是否尽可能的大。3 卡诺图法化简逻辑函数的一般步骤3.1 将逻辑函数化为最小项表达式当逻辑函数不是最小项表达式时，可以用配项法将逻辑函数化为最小项表达式。这样才可以填入卡诺图并用卡诺图法化简。例如：F（A，B，C，D）= AB+BCD+ACD+ABD = AB（C+C）（D+D）+ BCD（A+A）+ACD（B+B）+ABD（C+C） =ABCD+ ABCD+ ABCD+ ABCD+ ABCD+ ABCD+ ABCD+ ABCD+ ABCD+ ABCD= m（6，9，12，13，14，15）3.2 由最小项表达式画出卡诺图例如上面给出的F（A，B，C，D）= m（6，9，12，13，14，15）。根据此最小项表达式画出对应的卡诺图：AB图（4）CD000111100000100100111100101001103.3 画圈，合并相邻的最小项相邻最小项用矩形圈圈起来，称为卡诺圈。画卡诺圈所遵循的规则为：（1）必须包含所有的最小项；（2）按照从小到大顺序，先圈孤立的“1”，即先圈孤立的最小项，再圈只能两个组合的，再圈只能四个组合的，依此类推；每个卡诺圈内包含最小项的数目应是2的幂，2n个相邻的最小项之和可以合并成一个“与”项，并消去i个因子。（3）圈的圈数要尽可能少(与项总数要少)；（4）圈要尽可能大(与项含的因子最少)，不论是否与其他圈相重，也要尽可能地画大，相重是指同一块区域可以重复圈多次，但每个圈至少要包含一个尚未被圈过的1。 按照上面规则，圈出上面给出的卡诺图中可以合并的最小项。如下图所示：AB图（5）CD000111100000100100111100101001103.4 由卡诺图写出最简与-或表达式在圈出的合并项所处位置上，若某变量的取值有0也有1，则该变量被消去，否则该变量被保留，并按0为反变量，1为原变量的原则写成一个“与”项。也就是根据卡诺图的性质合并相邻最小项，并消去变量。有几个卡诺圈就有几个“与”项，而后把这些“与”项“或”起来，就得到给定逻辑函数的最简“与-或”表达式了。因此，上图合并最小项之后的最简表达式为：F（A，B，C，D）= BCD + ACD + AB3.5 无关项的处理当我们在设计逻辑电路时，经常会遇到逻辑函数的某些变量的值可以是任意的，或者这些变量的取值根本不会出现，这些变量所对应的最小项称为无关项或任意项。既然无关项的值可以是任意的，或者说这个变量取何值对电路的设计没有影响，所以在化简逻辑函数时，它们的值既可以取0也可以取1。具体取什么值，要根据具体的情况而定，目的是尽量能使函数得到最大程度的简化。4 卡诺图的其他应用4.1 卡诺图在消除竞争-冒险现象时的应用竞争-冒险是组合逻辑电路中经常发生的一种现象，需要采取恰当的措施加以消除。例如在电路中除采取引入封锁脉冲、引人选通脉冲、接人滤波电容等。此外还可以采取修改逻辑设计的方法，实际上是增加函数的冗余项。即利用卡诺图化简逻辑函数时，考虑到消除竞争-冒险，适当增加冗余项，就可以使逻辑电路达到消除竞争-冒险的效果。例如：逻辑函数的卡诺图如下。AB图（6）CD00011110000010011110110111100100如果按上面的方式画圈，虽然满足卡诺图化简逻辑函数的基本规则，但是由于八个最小项组成的四个圈彼此相切不相交，这样根据化简后的逻辑函数组成的逻辑电路极易出现竞争-冒险现象。为了避免这种情况，我们在画圈时把中间的四个最小项也用一个大圈圈起来。如下图（7）所示。这样虽然会增加一个冗余项BD，但是可以有效地消除逻辑电路中出现的竞争-冒险现象。AB图（7）CD00011110000010011110110111100100AB4.2 利用卡诺图进行逻辑函数运算利用卡诺图，可实现逻辑函数之间与、或、异或等逻辑运算。下面以逻辑函数Y1和Y2为例加以说明：首先在一个卡诺图中将逻辑函数Y1表示出来，再在另一个卡诺图中将逻辑函数Y2表示出来。两逻辑函数Y1和Y2进行与运算时，只需将两个卡诺图中对应方格的最小项做与运算，再用上面讲到的方法对运算后的卡诺图化简，所得既两逻辑函数与运算后的结果。同理，两逻辑函数Y1和Y2进行或或者异或运算时，只需将两个卡诺图中对应方格的最小项做相同运算，再用上面讲到的方法对运算后的卡诺图化简，所得既两逻辑函数运算后的结果。4.3 利用卡诺图求反函数利用卡诺图求反函数的方法与卡诺图法化简逻辑函数类似。不同的是求反函数时需要合并消去的是值为0的最小项。4.4 利用卡诺图求最简或与式 做出关于逻辑函数最大项的卡诺图，利用圈0的方法，即与上文化简逻辑函数时用的圈1法类似，只不过圈的是值为0的项。每一个圈写成一个或项，再把所有的或项相与，即得化简后的或与式。此外还可以用卡诺图配合相应的器件设计组合逻辑电路以及时序逻辑电路。5 多变量函数的卡诺图化简法前面已经讲到，卡诺图在解决不大于4变量的逻辑函数化简问题时，能充分的体现出其优越性。但是在面对多变量逻辑函数化简时就会力不从心。这里简单介绍一个化简5变量和6变量的卡诺图化简法。卡诺图形式表示的4变量以上的逻辑函数，必须采取二维以上的表示方法，才可能保证全部仅有一个变量发生变化的方格几何相邻。N维卡诺图可以用来描述具有2N个变量的逻辑函数。对于多变量的逻辑函数，可以采取多维表示法。例如5变量的逻辑函数采用三维卡诺图，三维卡诺图通常又展开为多个二维卡诺图。以下列逻辑函数为例：F(A，B，C，D，E)= （0，4，5，6，7，8，12，13，14，15，16，18，19，20，21，22，23，24，28，29，30，31）将此逻辑函数拆分成A=0和A=1两组4变量逻辑函数的化简。如下式：FA=0（B，C，D，E）= （0，4，5，6，7，8，12，13，14，15）和 FA=1（B，C，D，E）= （16, 18, 19, 20, 21, 22, 23, 24, 28, 29, 30, 31）它们各自的卡诺图如图（8）和图（9）所示：图（8）BC00011110001000011111111111101000DE图（9）BC00011110001011011111111111101000DE 两张图化简之后的逻辑函数分别为：FA=1（B，C，D，E）= DE + C FA=0（B，C，D，E）= DE + C + ABD则最终的化简结果为两次化简的结果相或，即：F = FA=1 + FA=0 = DE + C + ABD这就是通过卡诺图化简5输入变量逻辑函数的方法。如果是6输入变量，则分为4幅卡诺图。而当输入变量继续增加时，利用卡诺图化简逻辑函数的工作量会变得十分巨大，卡诺图化简法在此时也就失去了意义。所以我们更多的时候还是在输入变量小于等于