卡诺图卡诺图|离散数学

卡诺图是一个平面区域, 分为2n个相等的像元, 每个像元代表n个变量的函数的点。每个变量x用于以不同的方式将面积分成两个相等的一半, 即一个代表x, 另一个代表x’ 。与该函数的值为1的自变量对应的单元格包含1。
例1：当变量数量n = 1时, 卡诺图如图所示：
2.当变量数量n = 2时, 卡诺图如图所示：
3.当变量数量n = 3时, 卡诺图如图所示：
使用K-Map简化布尔函数布尔函数可以用k-map简化。它基于在相邻单元格中组合术语的原理。如果两个单元格只有一个变量不同, 则称它们相邻。在相邻单元格中, 变量之一相同, 而另一个变量在一个单元格中以非互补形式出现, 在另一个单元格中以互补形式出现。
SOP形式的最小化：
可以使用以下算法来获得最小化的表达式：

确定那些不能与其他包围它们的组合。
识别那些只能以一种方式组合成两个组的组合, 并将它们围成一组。
确定可以与其他三个组合的组合, 以唯一的方式将其组成四个相邻的组合, 并将它们围成一组。
确定可以与其他七个组合的组合, 以唯一的方式将其组成八个相邻的组合, 并将它们围成一组。
在确定了2、4和8个基本组之后, 如果仍然存在一些尚未被包围的组, 则应将它们彼此组合或与其他已经被包围的组合并, 即, 我们应将剩下的最大组连接起来。尽可能多的分组。

示例1：使用k-map最小化以下布尔表达式：
f（A, B）= A’ B + BA
解决方案：首先绘制2变量k图, 并将1插入相应的单元格中, 如图所示：

所需的最小化布尔表达式为f = B。
示例2：使用k-map最小化以下布尔表达式：
AB + A’ B + BA’
解决方案：绘制两个变量的k-map, 并在对应的单元格中插入1, 如图所示：

所需的最小化布尔表达式为f = A + B。
示例3：使用k-map最小化以下布尔表达式：
f（A, B, C）= AB’ C + A’ BC + AB + A’ B’ C
解决方案：绘制3变量k图, 并将1插入对应的单元格中, 如图所示：

所需的最小化布尔表达式为f = AB + C’
不在最小项/最大项中的布尔函数的最小化：
最小化这种功能的一种方法是将它们转换为标准形式, 即SOP或POS, 然后制作k图并获得最小化的功能。
另一种方法是直接使用以下算法准备k-map

输入1表示最小项, 0表示最大项。
输入每个项的一对零, 其变量小于变量总数。
为两个变量少于变量总数的项输入四个相邻的“ 0”。
以类似的方式重复其他术语。

示例：最小化四变量逻辑功能
f（A, B, C, D）= A B C’ D + A’ BCD + A’ B’ C’ + A’ B’ D’ + AC’ + AB’ C + B’
解决方案：通过以下方法获得k-map
（a）在与最小项A B C’ D对应的A = 1, B = 1, C = 0, D = 1的单元格中输入1
（b）在对应于最小项A’ BCD的A = 0, B = 1, C = 1, D = 1的单元格中输入1
（c）在A = 0, B = 0, C = 0的两个单元格中输入1, 对应于术语A’ B’ C’
（d）在两个单元格中输入1, 其中A = 0, B = 0, D = 0对应于术语A’ B’ D’
（e）在两个单元格中输入1, 其中A = 1, B = 0, C = 1与项AB’ C相对应

（f）在四个单元格中输入1, 其中A = 1, C = 0对应于术语AC’
（g）在八个单元格中输入1, 其中B = 0对应于术语B’
【卡诺图】最小化的表达是B’ + AC’ + A’ CD。