卡诺图化简简介
卡诺图化简简介
卡诺图化简法是数字逻辑中一种重要的逻辑函数化简方法，广泛应用于电路设计和编程优化。本文将从基础概念出发，通过具体实例，详细介绍卡诺图的绘制方法和化简技巧，帮助读者掌握这一实用工具。
先看个例子。力扣的题目： LeetCode 371.两整数之和
给你两个整数
a
和
b
，不使用 运算符
- 和
- ，计算并返回两整数之和。
以下是一种C/C++解法：
int getSum(int a, int b){
unsigned c = 0,ans = 0,mask = 1;
while(mask){
unsigned ai = a & mask;
unsigned bi = b & mask;
ans |= ai^bi^c;
c = ai&bi | bi&c | ai&c; // 卡诺图求解
c <<= 1; // 下一位的进位值
mask <<= 1;
}
return (int)ans;
}
其中，ai，bi，c三数和的进位，就可以用卡诺图的方法来解释。
一、前言
最小项的定义：一个函数的某个乘积项包含了函数的全部变量，其中每个变量都以原变量或反变量的形式出现，且仅出现一次，则这个乘积项称为该函数的一个标准积项，通常称为最小项。
最小项的表示方法：通常用mi来表示最小项。下标i的确定方式：把最小项中原变量记为1，反变量记为0，当变量顺序确定后，可以按顺序排列成一个二进制数，则与这个二进制数相对应的十进制数，就是这个最小项的下标i。
最小项的的相邻性：任何两个最小项如果他们只有一个因子不同，其余因子都相同，则称这两个最小项为相邻最小项。例如：m0和m1具有相邻性，m1和m2却没有，因为他们有两个不同的因子；m3和m4也不相邻，但是m3和m2相邻。相邻的两个最小项之和可以合并一项，消去一个变量。如：
到此，已经具备接下来学习卡诺图的准备知识点，接下来看看怎么画卡诺图以及卡诺图化简法。
二、卡诺图（karnaugh map）
卡诺图是由美国工程师卡诺（Karnaugh）首先提出的一种用来描述逻辑函数的特殊方格图。在这个方格图中，每一个方格代表逻辑函数的一个最小项，而且几何相邻（在几何位置上，上下或左右相邻）的小方格具有逻辑相邻性，即两相邻小方格所代表的最小项只有一个变量取值不同。对于有n个变量的逻辑函数，其最小项有2^n个。因此该逻辑函数的卡诺图由 2^n 个小方格构成，每个小方格都满足逻辑相邻项的要求。稍微整理下上面的基本知识点：
（1）一种描述逻辑函数特殊方格图。
（2）每格代表一个最小项，上下左右相邻就具备相邻性。
（3）有n个变量，最小项就有2^n且卡诺图也由2^n个格子构成。
两变量的卡诺图：
三变量的卡诺图（常用）：
通过上面的例子，我们已经掌握如何画卡诺图，接下来就是如何使用卡诺图进行化简。
三、逻辑函数的卡诺图化简法
卡诺图相邻性的特点保证了几何相邻两方格所代表的最小项只有一个变量不同。因此，若相邻的方格都为1（简称1格）时，则对应的最小项就可以合并。合并的结果是消去这个不同的变量，只保留相同的变量。这是图形化简法的依据。
综上所述，卡诺图具备以下特性：
（1）卡诺图中两个相邻1格的最小项可以合并成一个与项，并消去一个变量。
（2）卡诺图中四个相邻1格的最小项可以合并成一个与项，并消去两个变量。
（3）卡诺图中八个相邻1格的最小项可以合并成一个与项，并消去三个变量。
利用这3点特性来接着看下面的例子：
上图两个相邻1格的最小项可以合并成一个与项，并消去一个变量，化简式子如下：
根据上面3个特性再来看几个例子加深理解，以下是4个相邻1格的：
再来看一题，用卡诺图化简法求最简与或表达式：
先画出卡诺图，然后转换十进制对应1,2,3,6,7的地方填入为1，其余填写为0（这个步骤有前面的知识点支撑，应该不难理解了。）
然后获得式子：F =（m1+m3）+（m2+m3+m6+m7）。即：
好了到此，我们已经清楚如何化简了，接下来是对如何对卡诺图进行画圈进行探讨。首先，有这么几点需要明确：
（1）列出逻辑函数的最小项表达式，由最小项表达式确定变量的个数（如果最小项中缺少变量，应按例的方法补齐）。
（2）画出最小项表达式对应的卡诺图。
（3）将卡诺图中的1格画圈，一个也不能漏圈，否则最后得到的表达式就会与所给函数不等；1格允许被一个以上的圈所包围。
（4）圈的个数应尽可能得少。即在保证1格一个也不漏圈的前提下，圈的个数越少越好。因为一个圈和一个与项相对应，圈数越少，与或表达式的与项就越少。
（5）按照2k个方格来组合（即圈内的1格数必须为1，2，4，8等），圈的面积越大越好。因为圈越大，可消去的变量就越多，与项中的变量就越少。
（6）每个圈应至少包含一个新的1格，否则这个圈是多余的。
（7）用卡诺图化简所得到的最简与或式不是唯一的。
例3：用卡诺图化简以下表达式
解： 从表达式中可以看出此为四变量的逻辑函数，但是有的乘积项中缺少一个变量，不符合最小项的规定。因此，每个乘积项中都要将缺少的变量补上：
因此，获得整个表达式如下：
这里演示了刚才提示的（1）点，最小项缺少变量补齐。
错误：
正确：
错误（圈不够大）：
正确：
错误：
正确：
四、总结
（1）逻辑函数的化简有公式法和卡诺图化简法等。
（2）公式法是利用逻辑代数的公式和规则（定理）来对逻辑函数化简，这种方法适用于各种复杂的逻辑函数，但需要熟练地运用公式和规则（定理），且具有一定的运用技巧。
（3）卡诺图化简法简单直观，容易掌握，但变量太多时卡诺图太复杂，一般说来变量个数大于等于5时该法已不适用。
（4）在对逻辑函数化简时，充分利用无关项可以得到更为简单的结果。（有关无关项的知识点，在此文章没有提及。自己查找相关学习。
参考链接：
（1）卡诺图化简法-CSDN博客