《数字逻》课程教学中的卡诺图方法.doc

第 PAGE 页 《数字逻辑》课程教学中卡诺图方法 　　《数字逻辑》是理工科大学计算机专业一门重要基础课，卡诺图（Karnaugh Map）方法则是贯穿这门课程一种重要剖析方法，具有简单、直观、容易掌握等特点。在传统《数字逻辑》课程教学中，一般仅仅将卡诺图作为一种逻辑函数化简方法来讲授，突出其作为代数化简方法有用补充，着重介绍逻辑函数在卡诺图上表示、卡诺图上最小项合并规律以及用卡诺图化简逻辑函数步骤，而忽略了卡诺图作为逻辑函数几何表达方式，其化简方法与代数化简方法在本质上内在联系，以及卡诺图作为几何表达方式在各种实际应用中所表现出来独特优势。本文讨论如何以新方式从以上两个方面对这一传统方法进行教学。 　　1 卡诺图构成 　　卡诺图是一种平面方格图，n个变量卡诺图由2n个小方格构成，可以将卡诺图看成是逻辑函数几何表达方式，用二维图形中2n个小方格坐标值给出变量2n种取值，每个小方格与一个最小项对应。逻辑函数可以表示为最小项之与形式是卡诺图方法理论基础，用卡诺图方法化简逻辑函数基本操作就是将相邻小方格圈在一起进行合并（卡诺圈）。卡诺图中最小项排列方案不是唯一，但任何一种排列方案都必须满足最小项相邻关系，即相邻两个最小项彼此只有一个变量不同[1]。在n变量卡诺图上，每个小方格具有n个相邻小方格，它们分别是具有共同边界小方格（几何相邻），同一卡诺图中分别处于行（列）两端小方格（相对相邻）与相邻卡诺图中处于相同位置小方格（重叠相邻）。图1所示为一种5变量卡诺图，可以表示任意5变量逻辑函数，图中变量坐标值0表示相应变量反变量，1表示相应变量原变量，各小方格依变量顺序取坐标值，得到二进制数所对应十进制数即为相应最小项mi下标。为了方便，卡诺图中经常省略了符号m，直接标出m下标i。卡诺图上变量排列规律使最小项相邻关系能在图形上清晰地反映出来，如图1所示，最小项m15（对应A-BCDE）有5个相邻最小项，其中最小项m7（对应A-B-CDE），m11（对应 　　2 卡诺图化简法与代数化简法本质联系 　　卡诺图从几何上直观地反映了最小项相邻关系，用卡诺图化简逻辑函数基本原理就是将逻辑代数公理与定理以几何方式映射到卡诺图中，将逻辑依据与几何特征结合起来，完成逻辑代数方法几何表达，通过把卡诺图上表征相邻最小项相邻小方格圈在一个卡诺圈内进行合并，实现用一个简单与项代替若干最小项功能。 　　卡诺图化简法与代数化简法内在联系首先表现在卡诺图自身构成特点与逻辑代数公理系统一致性。逻辑代数公理系统包括五个公理：交换律、结合律、分配律、0-1律与互补律，它们在卡诺图中能够自然地被满足，下面分别予以说明。因为卡诺圈中最小项在合并过程中没有先后与优先级区别，运算结果对应着合并后卡诺圈，所以交换律A+B=B+A与结合律（A+B）+C=A+(B+C)自然成立。对于分配律A#8226;（B+C）=A#8226;B+A#8226;C，如图2所示，其中变量 在卡诺图上对应着{m2,m6,m1,m3,m7,m5}，变量A对应着{m6,m4,m7,m5}，所以A#8226;(B+C)对应着二者交集{m6,m7,m5}；另一方面，A#8226;B对应着{m6,m7,}，A#8226;C对应着{m7,m5}，所以A#8226;B+A#8226;C对应着二者并集{m6,m7,m5}，可见分配律在卡诺图上也自然成立。同样地，可以知道0-1律（A+0=A,A#8226;1=A，）与互补律（A+A-=1），以及以上公理对偶式在卡诺图上也一样成立。 　　卡诺图化简法与代数化简法内在联系还表现在用卡诺图方法对逻辑函数进行化简过程实际上就是自觉地运用逻辑代数各种公理与定理过程。下面以合并律、消去律与多余项定理为例，说明把卡诺图上表征相邻最小项相邻小方格圈在一个卡诺圈内进行合并操作（实现用一个简单与项代替若干最小项），实际上是这些定理在卡诺图上表达过程。图3所示为合并律在卡诺图上表达过程，对于2变量逻辑函数，在2.2卡诺图上卡诺圈A中合并了2个为1小方格，对应最小项AB与AB-，圈卡诺圈操作相当于运用合并律AB+AB-=A。对于3变量逻辑函数，在2.4卡诺图上卡诺圈A中合并了4个为1小方格，对应最小项AB-C-，AB-C，ABC-与ABC，圈卡诺圈AB-与AB操作分别相当于运用合并律AB-C-+AB-C=AB-与ABC-+ABC=AB，圈卡诺圈A操作相当于在卡诺圈AB-与AB（在3变量卡诺图中分别包含2个小方格）基础上运用合并律AB+AB-=A。 　　在2.2卡诺图上卡诺圈A中合并了2个为1小方格，对应最小项AB与AB-；卡诺圈B中也合并了2个为1小方格，对应最小项AB与A-B。因为卡诺圈A与B有公共部分AB，所以逻辑函数A+B只包含三个最小项，可以表达为A+A-B或B+AB-，这相当于