专栏首页超级码力【程序中的数学】利用德摩根定律简化布尔运算

【程序中的数学】利用德摩根定律简化布尔运算

今天说说德摩根定律在编程中的实践,题目看的很吓人,其实只要有一点点的高中数学知识就能看懂,而且这部分知识掌握后可以很快的运用到项目中,投资收益比非常高。

如果你觉得我的文章对你有帮助,在收藏的过程中,一定要记得点赞点在看哦,谢谢你,这对我真的很重要?!

一、缘起:一段让人头大的逻辑判断

这两天在重构一些老项目,重构过程中遇到了一个让人非常头大的逻辑判断:

if(!((A && B) || C)) {
  // do something
} else {
  // do something
}

看了这段代码,我人都傻了,从里向外一层一层梳理逻辑时,我的大脑活动是这样的:

短短一行的逻辑判断里,与或非三个运算符都用上了,尤其是最后那个小括号一圈全体取反的操作,我脑子直接了。要知道人脑是很不擅长或运算和非运算的,更不要说这些运算组合在一起了。

又花了五分钟尝试从代码上下文中梳理业务逻辑无果后,我重新审视了这个问题:如果业务上不好处理这个问题,能不能从理论上找到突破口?

方向找对后,我很快就找到了解决方案,那就是离散数学里的德摩根定律(De Morgan's laws)[1]

二、什么是德摩根定律

德摩根定律我们其实很早就接触过了,高中数学的集合部分就讲过,大学离散数学[2]的集合运算和布尔代数部分也有所提及。

德摩根定律在离散数学的很多场景里都出现过,它一共有两个关系:

  • 命题逻辑里,可以这样表示:
\neg (P\lor Q)\iff (\neg P)\land (\neg Q)
\neg (P\land Q)\iff (\neg P)\lor (\neg Q)

其中

\neg

表示逻辑非运算符(NOT, !),

\lor

表示逻辑或运算符(OR, ||),

\land

表示逻辑与运算符(AND, &&

  • 集合里可以这样表示:
\overline {A\cup B} = \overline {A} \cap \overline {B}
\overline {A\cap B} = \overline {A} \cup \overline {B}

其中 A 和 B 表示集合,集合上的横线表示取补集,

\cap

表示取交集,

\cup

表示取并集。

  • 布尔代数里可以这样表示:
\overline {(x \cdot y)} = \overline {x} + \overline {y}
\overline {(x+y)} = \overline {x} \cdot \overline {y}

其中

\cdot

表示布尔积(AND),

+

表示布尔和(OR),上划线表示补(NOT)。

  • 上面的公式还可以用文字描述

非(

P

Q

)等价于(非

P

)且(非

Q

非(

P

Q

)等价于(非

P

)或(非

Q

  • 或者用程序员熟悉的与或非逻辑运算符表示:
!(P || Q) = !P && !Q
!(P && Q) = !P || !Q

公式已经摆在这里了,肯定可以直接用了,但是用的时候还是不太放心,最好还是自己验证一下。我们可以用真值表对

\neg (P\land Q)\iff (\neg P)\lor (\neg Q)

做个直观的验证:

P

Q

¬P

¬Q

(P∧Q)

¬(P∧Q)

(¬P)∨(¬Q)

0

0

1

1

0

1

1

0

1

1

0

0

1

1

1

0

0

1

0

1

1

1

1

0

0

1

0

0

我们也可以用 Venn 图[3]

\overline {A\cap B} = \overline {A} \cup \overline {B}

做个可视化验证:

更复杂的数学推导我这里就不多说了,感兴趣的同学可以自行搜索学习。

三、解决问题

具体到我一开始说的那个条件判断上,我们可以用德摩根定律把原表达式拆开:

!((A && B) || C) 
== !(A && B) && !C   // 德摩根律
== (!A || !B) && !C  // 德摩根律
== (!A && !C) || (!B && !C)  // 分配律

用分配律转化后,经过代码的上下文分析,我发现在这段代码的业务场景中, !A 等价于 C,所以上面的式子还可以化简:

(!A && !C) || (!B && !C)
== (C && !C) || (!B && !C) // !A 等价于 C(从业务上分析的,不具备普遍意义)
== false || (!B && !C)     // C && !C 必定为 false
== !B && !C
== A && !B  // A 等价于 !C(从业务上分析的)

到这里,我成功的把原来一段让人脑袋爆炸的判断语句化简为一段直白易懂的表达式,转换后的代码无论是从理解上还是后期维护上都比原来容易很多。

四、化简还有什么招?

与或非三者一起用的场景可以尝试用德摩根定律化简,在其它场景下,还可以利用其它运算律进行转换,比如说前面我就用了分配律。类似于积之和展开式的化简,我们还可以用卡诺图进行分析。

例如一个场景试图化简布尔函数的一个积之展开式:

x\overline {y} + \overline {x}y + \overline {x} \overline {y}

,就可以用卡诺图进行分析:

y

x

1

x

1

1

根据图示可以轻易得出最后的化简结果为

\overline {x} + \overline {y}

如果变量超过 4 个,卡诺图就非常复杂了,这时候可以用奎因-莫克拉斯基方法进行化简,限于篇幅也不多介绍了,感兴趣的同学可以自行搜索。

在此我再多说一句,如果真的出现用 4 个以上的子状态去决定最终的行为时,问题的关键就不是化简,而是顶层设计上就出了问题了

这时候需要停下来好好思考是不是模型的设计抽象程度不够,把过多的内部状态暴露了出来等等,这个得具体业务具体分析,一昧的堆 if else 或加 flag 是解决不了问题的,只会导致代码的腐化最终无法维护。


欢迎大家关注我的微信公众号:卤蛋实验室,目前专注前端技术,对图形学也有一些微小研究。

也可以加我的微信 ,欢迎大家来撩。

参考资料

[1]

德摩根定律(De Morgan's laws): https://en.wikipedia.org/wiki/De_Morgan%27s_laws

[2]

离散数学: https://book.douban.com/subject/34866266/

[3]

Venn 图: https://en.wikipedia.org/wiki/Venn_diagrams

本文分享自微信公众号 - 卤蛋实验室(egglabs),作者:卤代烃

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 电池狂人的大满足——高仿锤子科技条形图

    自从乔老爷子把苹果公司的每一次发布会都搞成个人秀后,幻灯片这个词就开始变得热门起来。大家发现好的口才搭配上一张好的幻灯片可以极大吸引听众的注意力,最关键的是可以...

    卤代烃
  • 从回形针的互动视频谈谈交互教程的发展

    2020 年 12 月 17 日,回形针工作室上新了一款新产品——「一个人工智能的诞生」互动教学视频[2],因为从高中开始就接触了 MOOC,对在线教育这块儿一...

    卤代烃
  • 可视化 | 10 张 3D 建模图还原「巴黎圣母院」火灾细节

    前两天巴黎圣母院的火灾牵动了很多人的心,育碧老贼还借势营销免费推了一波《刺客信条》,美其名曰在游戏里重游巴黎圣母院,我这种正直的人难道会信老贼的鬼话吗?

    卤代烃
  • 如何使用Cloudera Manager启用YARN的HA

    前面Fayson写过《如何使用Cloudera Manager启用HDFS的HA》,YARN的HA架构和HDFS的HA类似,需要启动两个ResourceMana...

    Fayson
  • jq生成缩略图fileReader

    93年的老男孩
  • ​JS基础测试: 下列哪一项的返回值是5?

    逻辑运算符用于测定变量或值之间的逻辑。除了常用的返回布尔值,也可以利用运算符的逻辑来获得我们想要的数字或枚举变量:

    舒克
  • 分布式系统如何定位压力问题监控监控什么呢实际的压力问题怎么发生的我用的工具

    大宽宽
  • javascript中的变量提升的简单说明

    两个输出都是undefined。为什么呢?这就要从js中变量的提升和函数作用域来说起了。

    小明爱学习
  • 卡巴斯基:手机广告软件分析

    许多用户抱怨未知来源广告软件被安装在手机上。广告软件可植入到系统分区中或者在代码级别嵌入到不可删除的系统应用和库中。数据显示,受恶意软件或广告软件攻击的所有用户...

    FB客服
  • HomePwn:一款专用于物联网设备渗透测试的“瑞士军刀”

    HomePwn是一款功能强大的物联网渗透测试框架,它可谓是该领域的一把“瑞士军刀”。HomePwn可以提供设备安全审计和渗透测试功能,企业员工可以使用HomeP...

    FB客服

扫码关注云+社区

领取腾讯云代金券