计算机辅助卡诺图化简逻辑

摘要： 随着电子技术的迅速发展，卡诺图已经成为逻辑设计中常用的一种数学工具。由于卡诺图形象、直观，能把各种复杂的逻辑函数用图形表示出来。因此，卡诺图在电子技术中得到了广泛的运用。在数字电路中，逻辑函数的表示方法有：真值表，函数表达式，逻辑图以及卡诺图。卡诺图的人工化简逻辑函数历来为试凑法，无一定规律可循，繁琐而且易出错。而用计算机辅助卡诺图来化简逻辑函数的方法将克服人工算法的缺点，使化简更方便有效。

关键词：计算机辅助，卡诺图，逻辑函数

中图分类号：TP312文献标识码：A 文章编号：1009-3044(2007)05-11270-03

1 逻辑函数的基本定义

当自变量的取值（定义域）只有0和1（非0即1）函数的取值也只有0和1（非0即1）两个数――这种代数就是逻辑代数，这种变量就是逻辑变量，这种函数就是逻辑函数。另外一种定义是：如果有若干个逻辑变量（如A、B、C、D）按与、或、非三种基本运算组合在一起，得到一个表达式L。对逻辑变量的任意一组取值（如0000、0001、0010）L有唯一的值与之对应，则称L为逻辑函数。逻辑变量A、B、C、D的逻辑函数记为：L=f(A、B、C、D)。逻辑代数，亦称布尔代数，其规定：(1)所有可能出现的数只有0和1两个。(2)基本运算只有“与”、“或”、“非”三种。

通常，逻辑函数的化简方法有两种：公式化简法和卡诺图化简法。公式化简法只适用于比较简单的逻辑函数化简。而比较复杂的逻辑函数常用卡诺图法来进行化简。因为卡诺图化简法能直观地、正确地得到函数的最简表达式，它是逻辑函数化简中较实用的一种方法。在数字电路中，逻辑函数的表示方法有：真值表，函数表达式，逻辑图以及卡诺图。

而卡诺图又分为变量卡诺图和逻辑函数卡诺图。所谓变量卡诺图就是用图示的方法，将各种输入变量取值组合下的输入函数值一一表示出来；在变量卡诺图的基础上，把构成函数的最小项填入相应的小方块中，便可得到逻辑函数的卡诺图。

2 卡诺图的化简

步骤分为三步： (1)首先将逻辑函数用卡诺图表示出来;(2)合并卡诺图中为“1”的最小项；将所有相邻的“1”按2的整数次方个为“1”的方格为一组构成若干个矩形圈，这种圈称为卡诺圈，所有圈中必须至少有一个“1”方格没有被圈过，并所有的圈尽可能大;(3)写出最简的函数表达式。

例化简函数F(A，B，C，D)=∑m(3，4，5，7，9，13，14，15)。

上图中有两种圈法，在图a中最大的圈中每一个“1”都已经被圈过“0”，如果写出其表达式共有5项，而图b的圈法是正确的。其化简的表达式为：

F（A,B,C,D）=ACD+ABC+ACD+ABC

卡诺图的化简依据：利用卡诺图化简函数的依据在卡诺图的构成特点中已讲到了，即卡诺图中每两个相邻小方格所代表的最小项只有一个变量不同，如果相邻的两个小方格填的是1，则利用构成特点消。

3 卡诺图与真值表的关系

任意与或表达式对应的卡诺图的填入方法：首先分别将每个与项的原变量用“1”表示，反变量对应的变量用“0”表示，在卡诺图上找出相交点，在其方格上填上“1”;而在其没有相交点的方格上填上“0”。 只要当任意一项的或项为“0”时，函数的取值就为“0”，什么时候或项为“0”呢？我们只须将组成该或项的原变量对应的变量用“0”、反变量对应的变量用“1”代入，这时该函数就为“0”了。故写其对应卡诺图的方法是：首先将每个或项的原变量对应的变量用“0”、反变量对应的变量用“1”代入，在卡诺图中找出相交点，在这些相交点上填上“0”；然后在没有填上“0”的方格上填“1”即可。例F(A,B,C,D)=(A+C)(B+D)(C+D)写出函数应的卡诺图。

已提到了卡诺图与真值表之间的关系，由表达式与真值表、最大项表达式与真值表、最小项表达式与真值表之间的关系我们可以方便将其填入卡诺图中。

4 逻辑函数在卡诺图上的表示

用卡诺图描述一个逻辑函数时，一般应将函数表达式变换成为"与-或"表达式或者标准"与-或"表达式。

对“与-或”表达式表示的函数，可按照卡诺图上与的公共性、或的叠加性、非的否定性作出相应卡诺图；对标准“与-或”式表示的函数则只需在卡诺图上找出和最小项对应的小方格并填上“1”，其余小方格填“0” （或以空白代替“0” ）。

在利用卡诺图对逻辑函数进行化简的时候，必须遵循有关的规则，才能得到正确的结果。规则如下：

(1)根据逻辑变量的数目或最小项的编号画出相应的卡诺图。

(2)根据逻辑函数的表示方法，在卡诺图中相应的小方块上填上乘积项或最小项的值。若乘积项是由卡诺图中斜线一边的同侧变量组成，则填写的小方块按“相连”的规则确定；拖为异侧（或含异侧）变量组成，则按“相交”的规则确定。若函数是由最小项的和式给出，则可以按最小项的编号直接在相应的小方块填入。

(3)用画包围圈的方法合并最小项，进行逻辑函数化简。包围圈应尽可能大，以便削去最多的变量，使逻辑函数最简。但包围圈中小方块（即最小项）的个数N应为： N=2n（n=0，1，2，3，4，5，6）

换言之，小方块的个数只允许为1，2，4，8，16，32或64，而不允许为3，5，6，7，9，10，…等等。

卡诺图中每一个最小项均应该被包围，但是同一最小项可被不同的圈包围多次。这样做的根据可由逻辑代数中的同一律得出。

(4)一圈中的所有最小项均由其他的圈所包围，则此圈属多余。

(5)根据几何相邻的含义，卡诺图中，最上与最下，最左与最右，四个顶角以及轴对称的最小项应该分别画在一个包围圈中。

(6)若逻辑函数带有约束项的时候，与约束项对应的小方块填入“X”，以示区别。根据需要，“X”号的值可为“1”为“0”，以便于画包围圈。

(7)根据包围圈的个数以及圈中不能削去的逻辑变量的几何关系（“相连”或“相交”），即可得到逻辑函数的最简与或式。

(8)由于包围圈中约束项的取值不同，有时逻辑函数的最简与或式可能不同，哪一种为最简，需要检查和比较才能确定。

用卡诺图化简逻逻辑函数的基本依据则是一个重要且较难理解的内容：

卡诺图实际上就是用来直观地反映最小项之间逻辑相邻关系的一种最小项方格图。在卡诺图上把逻辑相邻项安排在位置相邻(这里所说的位置相邻是一种广义的相邻，卡诺图上位置相对的方格也可说成相邻关系，因为如果将卡诺图对称折叠，这些位置相对的方格即能重合，所以把卡诺图看成可折叠的图纸，这些位置相对的方格实际上也是相邻关系)的方格中，即通过用几何位置相邻来反映逻辑相邻关系。为什么在卡诺图上逻辑相邻关系清楚，就可以为化简逻辑函数提供方便呢?这就是必须弄清楚用卡诺图化简逻辑函数的基本依据的问题，即:AB+AB=A。

以上逻辑等式表示两逻辑相邻项可以合并成一项，并消去一个变化了的因子而达到简化表达式的目的。卡诺图清楚地反映出了最小项之间的逻辑相邻关系(即哪些项之间是逻辑相邻关系)，所以在卡诺图上可以方便地将逻辑相邻项圈起来进行合并。将任何需化简的逻辑函数写成最小项之和的形式，就可以用卡诺图表示该逻辑函数并方便地对其进行化简了。了解了用卡诺图化简逻辑函数的基本依据，则可以对为什么在卡诺图上把逻辑相邻项圈起来进行合并以及合并的结果为什么是保留若干逻辑相邻项的公因子都能做到透彻理解。

用卡诺图化简逻辑函数过程中要：

(1)合并最小项的规则

在卡诺图上将逻辑相邻项加圈进行合并时，如何加圈以及加圈合并后的结果(每个合并圈代表一个由若干轻工业量构成的乘积项)与原最小项相比有什么变化，根据用卡诺图化简逻辑函数的基本依据，将在卡诺图上加圈合并最小项的基本规则总结如下:

2n个逻辑相邻且排成矩形的最小项方格可以合并成一项，并消去“n”个因子，合并结果保留这些最小项的公因子。

由以上阐述可知在卡诺图上加圈合并最小项须把握以下两点：第一、加圈合并的最小项方格数必须是2n (n=1、2、3……)，合并结果为每个合并圈代表一个乘积项，该乘积项比合并前最小项减少n个因子。第二、要合并的对应方格必须排成矩形或正方形。掌握合并最小项的规则，其一有助于检查判断化简结果的正确性，譬如四个最小项圈起来合并，而写该圈代表的乘积项时，只比原小项减少了“1”个因子，则可以肯定该乘积项是错误的。其二有助于理解为什么在卡诺图上加圈合并最小项化简逻辑函数时，合并圈越大则化简过程越方便，则化简结果越简单。

(2)为了使化简结果到最简状态，在卡诺图上加圈合并最小项的过程中须着重把握如下三点：第一、尽量减少合并圈的数目，因为每个合并圈代表着合并结果中的一个乘积项，所以合并圈数目越少，则化简结果中所包含的乘积项就越少。第二、使合并圈尽可能扩大，根据前述合并最小项的规则，合并圈越大，参与合并的最小项方格越多，即2的幂次越高，合并后减少的因子就越多，则合并圈所代表的乘积项包含的因子就越少。第三、每个合并圈内都必须保证至少有一个“1”格只被圈过一次，即每个合并圈内必须至少保证有一个特征“1”格，以此避免合并结果中出现冗余项。

化简后的结果是逻辑函数的与或表达式，在与或表达式中所含乘积项越少，每个乘积项所含因子越少，则与或表达式越简洁，所以合并过程中把握了以上几点，则能将逻辑函数化为最简状态。

5 计算机辅助卡诺图化简逻辑函数的实现

计算机辅助化简法利用C语言的位操作可以将任意复杂的五变量及以下的逻辑函数用一个表达式的形式输入计算机，输出来的就是逻辑函数对应在卡诺图上的“0”、“1”逻辑值。

以三变量为例来说明方法要点。第一部分，三变量卡诺图，共八个方格，每五个小方格对应一个逻辑值“0”或“1”。这八个值可以看成C语言一个整型数的二进制数一位。

第二部分是变量的初始化： 在进行逻辑化简时，无非就是对变量A、B、C进行与、或、非三种运算。根据A、B、C在卡诺图上所对应的方格，分别为：

A（0011 0011）

B（0110 0110）

C（0000 1111）

其中A、B、C中的前四位代表卡诺图上第一行，后四位代表卡诺图上的第二行。A、B、C分别与一个二进制数八位相对应。因此，只要给变量A赋51，B赋102，C赋15。

第三部分是C语言的位运算：当要对逻辑函数进行化简时，无非就是对逻辑函数变量A、B、C的逻辑值进行与、或、非三种运算。当作与运算时，参与运算的两个逻辑变量在同一小方格都为“1”时，他们与运算的结果才为“1”，否则对应这个方格的运算结果为“0”。这种与运算正好和C语言中对应的A、B、C初值的十进制数转化成的二进制数的位的与运算相一致。同样，逻辑或运算对应C语言的位或运算，逻辑非运算对应C语言的取反运算，逻辑异或运算对应C语言的位异或运算。可以利用C语言的位运算实现逻辑函数的逻辑运算。

第四部分是运算的先后顺序：利用C语言的位运算能实现逻辑函数的逻辑运算，还有一个问题必须解决的就是四种运算的先后顺序。逻辑运算的顺序由高到低为先非，后与，再或。而C语言的位运算由高到低是取反，与，或，逻辑运算的次序正好和对应的位运算次序相一致。因此，只需将逻辑函数转化成C语言位运算表达式。

第五部分是数据的输出： C语言的位运算结果仍然是二进制数，但是输出结果只能是以八进制或十进制数形式输出。我的一个子程序实现用二进制位形式输出，并且输出符合卡诺图的形式。因此只要将输出二进制位填入相应卡诺图上，然后将其用卡诺图化简成最简的逻辑函数。

关于本程序的几点说明：本程序为逻辑函数计算机辅助卡诺图化简程序。

a.关于变量名。程序中使用的变量名为A、B、C、D、E，若逻辑函数的变量名不是它们时，把第一个变量换成A，第二个换成B，依次类推。输出逻辑值后，相应的卡诺图上的A、B、C、D、E换成逻辑函数的变量名。

b.关于变量个数。程序中只编写了能处理五个变量及以下的计算机辅助卡诺图程序，若为三变量，只须修改程序中辅初值语句为A=51，B=102，C=15，输出函数中循环改为FOR（I=8；I〈=1；I--〉。若为四变量，则将赋值语句改为A=13017；B=26214；C=255；D=4080；

附上“逻辑计算”部份程序：

6 小结

应用了C语言编程，实现了卡诺图化简逻辑函数的高效性。

参考文献：

[1]余孟尝.数字电子技术基础.高等教育出版社.

[2]谭浩强.C语言程序设计.清华大学出版社.

[3]许开华.用卡诺图化简逻辑函数过程中的几个问题.攀枝花大学报，(19，12).

[4]陈志腾.使用卡诺图的规则.韶关大学学报，(20，2).

[5]王兆安，王成华，吴刚，等.数字基础.科学出版社.

[6]刘光正.逻辑函数卡诺图化简研究.河北大学学报.(14，3).

[7]李来运，高倩.小议卡诺图化简法.天中学刊.(14，5).

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。