第25卷第3期合肥工业大学学报(自然科学版)Vol.25No.3 2002年6月JOURN AL OF HEFEI U NIVERSITY OF T ECH NOLOGY Jun.2002对布尔代数中卡诺图的研究方志鸣(黄山学院物理系,安徽黄山 245021)摘 要:由于卡诺图具有几何相邻与逻辑相邻之间的良好对应关系,故在布尔代数中得到广泛应用,文章分析了传统卡诺图在简化多变量(n>5)函数时,其对应关系所面临的困难,提出三维卡诺图及卡诺图阵列的概念。
采用适当的排列方式可将图中几何相邻与逻辑相邻的对应项增加到6个以上,为了使其具有实用性,又引入一定的画图规则,对三维卡诺图加以改进,并举例说明它们的使用方法。
结果表明,采用该方法对六变量至八变量的逻辑函数进行综合化简时,仍具有简便直观、可靠性高及易操作等优点,且有较好的实用价值。
关键词:几何相邻;逻辑相邻;三维卡诺图;卡诺图阵列中图分类号:O153.2 文献标识码:A 文章编号:1003-5060(2002)03-0455-04Research on Karnaugh map in Boolean algebraFANG Zhi-ming(Dept.of Physics,Huan gshan College,Huangsh an245021,China)Abstract:Karnaug h map can be used larg ely in Boo lean alg ebra because it has fine correspondence be-tw een adjacency on g eo metr y and adjacency on log ic.In this paper,the difficulty of co rrespondence in sim plifying the m ultiple-variable(n>5)function w ith the traditional Kar naugh map is analyzed,and the concepts o f three-dimensional Karnaug h map and Karnaugh map array are proposed.By using pr oper range,the correspondence term s betw een adjacency on geom etry and adjacency on logic can in-crease to six or more in the map.Some pictorial rules are adopted,and the three-dim ensional Kar-naugh map is improved for practicality o f the map,and the usag e o f the im pro ved map is illustrated w ith examples in the paper.T he lo gic functions of six to eight variables ar e simplified and sy nthesized by using the improved m ap.The r esult show s that the presented m ethod has the advantages of sim-plicity,intuition,g ood reliability and easy operation,so it is valuable in practical use.Key words:adjacency on geometry;adjacency on logic;three-dimensional Kar naugh map;Karnaugh map array在有关文献[1～4]中,使用卡诺图时只讨论到四变量为止,因为通常画出的五变量及五变量以上的卡诺图用来化简逻辑函数时,已逐渐失去了简便直观的优点,故应用较少。
本文将卡诺图加以改进,可应用于五变量以上的逻辑函数的化简,而且不失其直观和简便的优点。
收稿日期:2001-08-14;修改日期:2001-11-04作者简介:方志鸣(1947-),男,安徽歙县人,黄山学院讲师.1 将卡诺图扩展成空间图形同一逻辑函数的2个最小项中,若仅有1个变量不同而其余变量相同时,则称它们是逻辑相邻的。
即1个n 变量的逻辑函数,对于它的任何一个最小项,当且仅当其中某一变量求反后,就可得到这个最小项的一个逻辑相邻项。
由于每个最小项都包含有n 个变量因子,所以每个最小项都可以有n 个逻辑相邻项,卡诺图在排列变量各种取值组合时,是按循环码规律进行,即相邻两组取值组合之间只有1个变量的值不同,故在卡诺图中任何几何位置相邻的最小项在逻辑上也相邻,从而可以合并化简,这种对应关系一目了然,非常直观。
但是,这种直观只能对四变量以下的卡诺图而言,因为目前给出的都是二维平面卡诺图,这种图中的某一小方格(对应于1个最小项)最多只有上、下、左、右4个几何相邻的小方格,正好等于1个四变量最小项的4个逻辑相邻项,而五变量以上的卡诺图,有些逻辑相邻的小方格并不相邻接,使其几何相邻与逻辑相邻之间失去了良好的对应关系[2,5],这是利用卡诺图化简时所面临的困难。
为了解决这个问题,须对传统的卡诺图作技术处理[6],经过折叠翻转等处理后,将六变量平面卡诺图[2]变成1个有4层方格图重叠在一起的空间图形,称之为三维卡诺图,因体现三维方向上的互换性,三维卡诺图可用1个4×4×4的正方体表示,如图1所示。
应注意与最小项对应的是每个小方块而不是小方格,显然,每个小方块(最小项)就多出前后2个相邻块,共有6个几何相邻块,经处理得到的三维卡诺图,在相互垂直的A B ,CD ,EF 三维方向上最小项均按循环码规律排列,确保了几何相邻与逻辑相邻的对应关系。
然而,图1的画法在使用中还有问题,即在A B 方向上,处于A B =01,11,10那几层图形上的大多数小方块被A B =00的这一层图形所遮盖,无法填写和观察合并。
为了便于操作,将卡诺图仍画成4×4的平面形式,但是规定每个小方格包含有逻辑函数在A B 方向的4个最小项,所以它仍旧是三维的,为了防止在观察和画圈合并时产生混淆,可将这4个最小项沿对角线方向填写。
按照这种约定,图1变成了图2所示的形式,为简便起见,图2某方格子中斜向填写的10、26、58和42实际上代表的是图1中的m 10,m 26,m 58和m 42这4个最小项。
图1 三维形式的卡诺图 图2 改进后的三维卡诺图2 用三维卡诺图化简多变量的逻辑函数利用三维卡诺图化简逻辑函数时,可以采用卡诺图画圈合并最小项的方法,只是应注意每个最小项除了有上、下、左、右4个几何相邻项以外,还多出了对角线方向(即前后)的2个几何相邻项,所以,合并时必须在A B ,CD ,EF 三个方向上同时观察和画圈,举例说明其用法。
456 合肥工业大学学报(自然科学版) 第25卷例1 f 1(A ,B ,C ,D ,E )=∑m (4,5,6,7,13,15,20,21,22,23,25,27,29,31)解 这是五变量的逻辑函数,所以三维卡诺图在垂直于纸面的方向上只有A =0和A =1两层图形,如图3所示。
对于序号在16以上的最小项,可以填在小方格的右上方,如果1个小方格中,只有一部分最小项取值是1,为了便于观察和画圈,对于那些取值为0的最小项最好也填入0,如卡诺图最下面一行中的2个小方格一样。
容易看出,第二行的4个小方格中有8个最小项相邻且可合并,用1个类似于平行四边形的圈画出,表示是在与纸面垂直的平面内进行操作,合并得B -C 。
还有,在中央的4个方格内有8个最小项也可以合并,这种合并是在与纸面平行和垂直的几个平面上同时进行,可以用1个类似于立方体六角形的圈画出,合并得CE 。
另外,在卡诺图的中下部,A =1这一层图形上有4个最小项可合并,因为是在与纸面平行的平面上进行,所以用1个四方形的圈画出,合并得A BE 。
最后结果为f 1=B -C +CE +A BE 例2 f 2(A ,B ,C ,D ,E ,F )=∑m (0,1,3,7,16,17,23,24,33,35,39,55)+∑d(10,18,19,26,51,56) 解 同理,用卡诺图可化简六变量函数,本函数中的约束项用“X ”标示,参照前面的约定在三维卡诺图中填写和画圈合并,如图4所示。
这里要注意的是位于A B =01这一层图形中的四角上有4个最小项可以合并,化简结果得f 2=C -EF +A -C -D -E -+A -B D -F -+B -C -D -F 图3 三维卡诺图化简五变量函数 图4 三维卡诺图化简六变量函数3 用卡诺图阵列实施化简由Shannon ′s theor em [7]推导,对n 变量二值逻辑函数中的某一变量x i 进行展开,可将该函数分解为2个(n -1)变量的子函数,即f (x 0,x 1,…,x n -1)=x i f (x 0,x 1,…,x i -1,1,x i +1,…,x n -1)+x -i f (x 0,x 1,…,x i -1,0,x i +1,…,x n -1) 如果n >6,经逐步递推,可以将其分解为2n -6个六变量的子函数,因此n 变量(n >6)函数的图形可以用2n -6个六变量的子卡诺图表示,形成一个卡诺图阵列。
一般情况下,七、八变量函数的卡诺图阵列分别有2个和4个六变量的子图。
以七变量函数为例,其展开式为f (A ,B ,C ,D ,E ,F ,G )=A -f (0,B ,C ,D ,E ,F ,G )+A f (1,B ,C ,D ,E ,F ,G )=A -f 0(B ,C ,D ,E ,F ,G )+A f 1(B ,C ,D ,E ,F ,G ) 易知,每个最小项除了在自己所在的子卡诺图中有6个逻辑相邻项之外,还在另一个子卡诺图的对应位置上有1个逻辑相邻项,它们也可以合并。
对这样的卡诺图阵列简化时,除了按三维卡诺图的规则进行操作外,还应在2个子卡诺图上找出相应位置的乘积项进行合并,才能得到最简结果[2,6]。
457第3期 方志鸣:对布尔代数中卡诺图的研究例3 f =A -B -C -D -F -+A B -D -E -G +A B -F G +A -B -C D -E -G +A -B -C -FG -+B -C -D -F G 解 画出七变量函数的2个子卡诺图f 0(A =0)和f 1(A =1),将有关变量值分别填入,如图5所示。