什么是卡诺图

卡诺图是真值表的变形，它可以将有n个变量的逻辑函数的2^n个最小项组织在给定的长方形表格中，同时为相邻最小项（相邻与项）运用邻接律化简提供了直观的图形工具。在部分情况下，卡诺图能让你的逻辑变得一目了然，但是如果需要处理的逻辑函数的自变量较多，卡诺图会使图形更加复杂。更多

一个简单的例子

现有绿、黄、红三颗灯，当满足下面四个条件中任何一个时，需要按下按钮：

  1. 绿灯、黄灯、红灯全部都熄灭
  2. 黄灯熄灭、红灯亮
  3. 绿灯熄灭、黄灯亮
  4. 绿灯、黄灯、红灯全部亮起

如果让你写一段代码来判断是需要按下按钮，很多人会这么写:

/**
 * @param bool $a 绿灯的状态，true为亮,false为熄灭
 * @param bool $a 黄灯的状态，true为亮,false为熄灭
 * @param bool $a 红灯的状态，true为亮,false为熄灭
 * @return bool
 */
function checkEnterBtn(bool $a, bool $b, bool $c): bool 
{
    if ( (!$a && !$b && !$c) || (!$b && $c) || (!$a && $b) || ($a && $b && $c) ) {
        return true;
    }
    
    return;
}

上面的代码是不是觉得特别的繁琐。繁琐就对了，下面我们来开启高能模式，将卡诺图应用到我们实际的编码中。

定义命题：

从上面的四个条件中，我们可以明显看出，参与逻辑计算的变量只有三个，所以我们为它们分别定义一个命题：

  • 命题A: 绿灯亮起
  • 命题B: 黄灯亮起
  • 命题C: 红灯亮起

画出卡诺图的结构

我们这里使用的卡诺图是变量卡诺图的变种

image

我们这里之所以让命题B和命题C交叉的目的是为了覆盖所有的变量。如果只有两个参与运算的变量，卡诺图的机构就是一个4×4的方格。更复杂的卡诺图参见维基百科。

将四个条件在卡诺图中标出

接下我们在满足上面4个条件的方格中打上勾

image

在上面图中，我们可以一目了然的看出在什么条件下需要按下按钮。接下来，我们将相邻的打勾格所形成的最大网格用虚线围起来组成组合框(组合框之间可以相互重叠)。

image

这个时候，我们可以看出图中有两个组合框，分别为：

  • 横向组合框，就是A为false的区域，因此用¬A来表示。
  • 纵向组合框，就是C为true的区域，因此用C来表示。

最终代码

将一步得出的两个组合框用代码实现，就是：

/**
 * 判断是否能按下按钮
 * @param bool $a 绿灯的状态
 * @param bool $b 黄灯的状态
 * @param bool $c 红灯的状态
 * @return bool 
 */
function checkEnterButton($a, $b, $c) {
    if (!$a || $c) {        // 这里的两个条件就是上一步中两个组合框的内容
        return true;
    }

    return false;
}

总结

当然，并不是什么情况都能够使用卡诺图来简化逻辑的，当参与运算的变量过多，会导致卡诺图变得非常的复杂。所以你需要区分什么情况下能够使用这种方式。

好了，到这里就结束了。对比两种实现方式，是不是要简洁很多。由此可见数学对于程序员来说是多么重要的东西。

版权声明：本文为pengxiaozhi原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/pengxiaozhi/p/9037819.html