计算机辅助卡诺图的快速化简

摘要： 本文阐述了利用VB编程绘制卡诺图，对输入的逻辑函数由计算机自动译码、逻辑运算、快速填写卡诺图，最后输入卡诺圈所包围的最小项，并由计算机自动生成最简“与-或”表达式。

Abstract： The paper describes the Karnaugh map drawing by using VB programming. For inputed logic function， it makes automatic decode， logic operation， rapidly filling in karnaugh map， finally enter the smallest item surrounded by the carnot circle， and automatically generated by the computer the simplest "and - or" expression.

关键词： 逻辑函数化简；卡诺图；快速填写卡诺图；自动生成最简“与-或”表达式

Key words： logic function reduction；Karnaugh map；quickly fill in Karnaugh map；automatically generate the minimalist "and - or" expression

中图分类号：TP391.7 文献标识码：A 文章编号：1006-4311（2013）33-0171-02

0 引言

利用计算机辅助卡诺图化简，使授课方式变得方便、快捷，节省了教师授课时的板书时间，提高了教学效率，使课堂教学活动变得活泼，生动有趣，富有启发性、真实性，可以从根本上改变传统上单调的教学模式，从而活跃学生的思维，激发学生的学习兴趣。

1 卡诺图化简逻辑简介

1.1 卡诺图的构成 卡诺图是一种平面方格图，每个小方格代表一个最小项，故又称为最小项方格图。结构特点：n个变量的卡诺图由2n个小方格组成，每个小方格代表一个最小项；卡诺图上处在相邻、相对、相重位置的小方格所代表的最小项为相邻最小项。（图1）

1.2 卡诺图的性质 卡诺图的构造特点使卡诺图具有一个重要性质：可以从图形上直观地找出相邻最小项合并。合并的理论依据是并项定理AB+AB’=A。例如，两个相邻最小项可以合并为一个“与”项并消去一个变量。用卡诺图化简逻辑函数的基本原理就是把上述逻辑依据和图形特征结合起来，通过把卡诺图上表征相邻最小项的相邻小方格“圈”在一起进行合并，达到用一个简单“与”项代替若干最小项的目的。通常把用来包围那些能由一个简单“与”项代替的若干最小项的“圈”称为卡诺圈。

1.3 逻辑函数在卡诺图上的表示 当逻辑函数为标准“与-或”表达式时，只需在卡诺图上找出和表达式中最小项对应的小方格填上1，其余小方格填上0，即可得到该函数的卡诺图。[1]

如函数Y=AB+CD+ACD的卡诺图如图2所示。

手工填写卡诺图既费时又易出错，如果在输入逻辑表达式后，由计算机自动进行逻辑运算，自动填写卡诺图既方便又快捷。

2 利用计算机的图形处理系统绘制卡诺图

2.1 绘图前的各种属性的设置 计算机的图形操作，都要使用绘图区或容器的坐标系统，窗体是一个容器，所有的控件都分布窗体内，每个容器都有一个坐标系，构成一个坐标系，需要三个元素：坐标原点、坐标度量单位、坐标轴的长度与方向。在VB中，当新建一个窗体时，新窗体采用默认坐标系，坐标原点在窗体的左上角，横向向右为X轴的正方向，纵向向下为Y轴的正向，单位为twip。为了符合日常的绘图习惯，我们可以使用屏幕的SCALE方法将坐标的原点设置在屏幕的左下角，横向向右为X轴的正方向，纵向向上为Y轴的正方向。并利用窗体的SCALEMODE属性将坐标单位改为毫米。设置好画图的线条粗细和颜色。[2]

2.2 绘图 绘图时输入变量的个数及卡诺图的大小。计算机便依据变量个数分别动态绘出三变量、四变量，或五变量卡诺图。精确绘图必须熟悉对坐标的计算。

3 逻辑表达式的输入，译码及运算

当输入逻辑表达式时，原变量照写，反变量在字母后加单引号，如Y=AB’+BC’+B’C+A’B，或者是输入函数包含最小项的形式，如Y=∑（3，2，4，5，7，6，12，13，8，9，10，11）。用一个文本框接收逻辑表达式AB’+BC’+B’C+A’B后，以“+”为界将其分解为若干个“与”项。再将每个“与”项中的反变量先进行非运算（NOT），然后进行“与”（AND）运算，最后将四个“与”项运算的结果进行“或”（OR）运算。在运算前按照变量在卡诺图上的分布分别给变量赋值：让A=&H00FF，B=&H0FF0，C=&H3333，D=&H6666（按十六进制书写）。因为变量A在四变量卡诺图最上面两行为（0000，00000），最下面两行为（1111，1111），故赋值A=&H00FF。

4 卡诺图的填写

上述逻辑运算的结果为十进制数，将其转化为二进制数后，依次赋给动态产生的十六个文本框。然后将十六个文本框依次移动到卡诺图对应的位置上，并在卡诺图上每个方格的右下角标上最小项的编号。如图2所示。

5 画卡诺圈，合并最小项，生成最简“与-或”表达式[3]

卡诺图具有循环邻接的特性，即相邻的两个最小项只有一个变量不同。若图中两个相邻的小方格均为1，则这两个相邻的最小项的和将消去一个变量；若卡诺图中四个相邻的方格为1，则这四个相邻的最小项的和将消去二个变量；八个相邻的最小项合并时可消去三个变量；利用卡诺图化简逻辑函数常用的方法是“圈1法”。用“圈1法”画包围圈的原则如下：①圈的个数应最少，圈内的小方格个数应尽可能的多。②将值为“1”的相邻方格圈成矩形或方形。③所圈取值为1的相邻小方格的个数应为1，2，4，8，其它形式是非法形式。④画包围圈时，每个取值为1的方格可以被重复包围，但每个包围圈都要有新的方格，同时不能漏去任何一项。

当输入一个卡诺圈所包含的最小项，如（3，2，7，6）时，由计算机自动生成最简与或表达式的算法如下：

①将上述包含的最小项输入给一个文本框，利用Q=SPLIT（TEXT1，”，”）语句将各个最小项分别赋值给一个动态数组Q，并按升序排列，这里Q（0）=2为四个最小项的最小值。然后根据Q（0）的值写出代表的最小项，如：Q（0）=0，则STR1=“A’B’C’D’”，Q（0）=1、则STR1=“A’B’C’D”，这里的Q（0）=2所以STR1=“A’B’CD’”。

②依次求Q（1），Q（2），Q（3）与Q（0）的差值，凡是差值为2N（即1，2，4，8）时，执行3，否则执行4。

③依据差值消去相应的变量：当差值为8时、则消去STR1中的变量A，当差值为4时、消去STR1中的变量B， 当差值为2时消去STR1中的变量C，当差值为1时、消去STR1中的变量D，例Q（1）-Q（0）=3-2=1，则消去STR1中的变量D，这里的Q（2）-Q（0）=6-2=4，则消去STR1中的变量B，所以最初STR1=“A’BCD”，则变为STR1=“A’C”。即A’C含概了最小项（3，2，7，6）。

④将上述生成的最简与项用加号“+”连接起来，就是最简“与-或”表达式。图3为输入函数Y=AB’+BC’+B’C+A’B后的运行结果。

结论：应用VB编程，由计算机绘制卡诺图，对逻辑表达式的自动译码、运算、卡诺图的自动填写、最后生成最简“与-或”表达式。实现了逻辑函数化简的高效性。

参考文献：

[1]唐德洲.数字电了技术[M].重庆大学出版社.

[2]龚沛曾.Visual Basic程序设计教程[M].高等教育出版社.

[3]叶腾，朱桂英.卡诺图化简数学新方法[J].河北大学学报，2012年6月.