🔢【程式中的數學】利用德摩根定律簡化布爾運算
今天說說德摩根定律在編程中的實踐,題目看的很嚇人,其實只要有一點點的高中數學知識就能看懂,而且這部分知識掌握後可以很快的運用到項目中,投資收益比非常高。
如果你覺得我的文章對你有幫助,在收藏的過程中,一定要記得點贊哦,謝謝你,這對我真的很重要🌟!
一、緣起:一段讓人頭大的邏輯判斷
這兩天在重構一些老項目,重構過程中遇到了一個讓人非常頭大的邏輯判斷:
if(!((A && B) || C)) {
// do something
} else {
// do something
}
看了這段程式碼,我人都傻了,從裡向外一層一層梳理邏輯時,我的大腦活動是這樣的:
短短一行的邏輯判斷里,與或非三個運算符都用上了,尤其是最後那個小括弧一圈全體取反的操作,我腦子直接炸了。要知道人腦是很不擅長或運算和非運算的,更不要說這些運算組合在一起了。
又花了五分鐘嘗試從程式碼上下文中梳理業務邏輯無果後,我重新審視了這個問題:如果業務上不好處理這個問題,能不能從理論上找到突破口?
方向找對後,我很快就找到了解決方案,那就是離散數學裡的德摩根定律(De Morgan’s laws) 。
二、什麼是德摩根定律
德摩根定律我們其實很早就接觸過了,高中數學的集合部分就講過,大學離散數學的集合運算和布爾代數部分也有所提及。
德摩根定律在離散數學的很多場景里都出現過,它一共有兩個關係:
-
在命題邏輯里,可以這樣表示:
其中 表示邏輯非運算符(NOT, !
), 表示邏輯或運算符(OR, ||
), 表示邏輯與運算符(AND, &&
)
-
在集合里可以這樣表示:
其中 A 和 B 表示集合,集合上的橫線表示取補集, 表示取交集, 表示取並集。
-
在布爾代數里可以這樣表示:
其中 表示布爾積(AND), 表示布爾和(OR),上劃線表示補(NOT)。
-
上面的公式還可以用文字描述:
非( 或 )等價於(非 )且(非 )
非( 且 )等價於(非 )或(非 )
-
或者用程式設計師熟悉的與或非邏輯運算符表示:
!(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 圖對 做個可視化驗證:

更複雜的數學推導我這裡就不多說了,感興趣的同學可以自行搜索學習。
三、解決問題
具體到我一開始說的那個條件判斷上,我們可以用德摩根定律把原表達式拆開:
!((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(從業務上分析的)
到這裡,我成功的把原來一段讓人腦袋爆炸的判斷語句化簡為一段直白易懂的表達式,轉換後的程式碼無論是從理解上還是後期維護上都比原來容易很多。
四、化簡還有什麼招?
與或非三者一起用的場景可以嘗試用德摩根定律化簡,在其它場景下,還可以利用其它運算律進行轉換,比如說前面我就用了分配律。類似於積之和展開式的化簡,我們還可以用卡諾圖進行分析。
例如一個場景試圖化簡布爾函數的一個積之展開式: ,就可以用卡諾圖進行分析:
1 | ||
1 | 1 |
根據圖示可以輕易得出最後的化簡結果為 。
如果變數超過 4 個,卡諾圖就非常複雜了,這時候可以用奎因-莫克拉斯基方法進行化簡,限於篇幅也不多介紹了,感興趣的同學可以自行搜索。
在此我再多說一句,如果真的出現用 4 個以上的子狀態去決定最終的行為時,問題的關鍵就不是化簡,而是頂層設計上就出了問題了。這時候需要停下來好好思考是不是模型的設計抽象程度不夠,把過多的內部狀態暴露了出來等等,這個得具體業務具體分析,一昧的堆 if else
或加 flag
是解決不了問題的,只會導致程式碼的腐化最終無法維護。
歡迎大家關注我的微信公眾號:滷蛋實驗室,目前專註前端技術,對圖形學也有一些微小研究。
也可以加我的微信 egg_labs,歡迎大家來撩。
