數字電路與邏輯設計張俊濤_數字電路學習筆記（四）：邏輯代數系統

邏輯代數系統由基本公式、常用公式、基本規則三部分構成。掌握了這些，設計出的電路可以盡可能地簡單，減少故障幾率和元件使用；程式設計時，如果掌握了邏輯函數化簡，也能增加條件判斷式的可讀性，避免寫出垃圾代碼。

一、基本公式

正如加減乘除中存在各式運算律一樣，邏輯運算也有運算規律。本章中，我們主要考慮與、或、非運算；異或、同或的運算律可以很友善地推導出來。我們從

常量的運算

開始。

以上相當于把真值表重新表達了一遍，比較直覺。

接下來，我們開始把式子抽象化，把其中一個常量用變量

代替，看看

常量與變量的運算（0律與1律）

：

這些也很好了解，隻要把常量運算公式兩兩合并就可以得到。時刻要提示自己：變量的值隻有0與1兩種情況。

最後，是變量間的運算，即

基本運算律：

提示：在布爾運算中，運算優先級是 非 > 與 > 或。

（1）交換律、結合律、配置設定律

這些公式基本和四則運算中的形式一樣：

特别的配置設定律：

由于在布爾運算中，與運算和或運算常常處于可以互換的地位，是以，我們也有

。它和與對或的配置設定律非常接近，隻是“與”和“或”調換了而已。可以證明一下公式的正确性：

分别用了：與邏輯配置設定律；重疊律（見（3））；與邏輯配置設定律逆命題；1律。

（2）還原律

很直覺，變量兩次取反後回到它本身。和語言中的“雙重否定”是一個概念。

（3）重疊律

這兩個式子比較難了解一點。但畢竟，布爾運算與四則運算中的“加法”“乘法”不是完全一緻的——如果寫成

，或者

A || A == A, A && A == A

，表達的意思也是一樣的。在學習邏輯運算時，有許多迷惑性的符号——比如”0”與“1”，它們并不存在大小關系，而隻是“真”與“假”的對應關系，與數字0和1無關。

一道十分有趣的題目：能否通過 A + A = A 推導出 A = 0 ？

不能。由于布爾運算中沒有“減法”運算，是以不可以把等式兩端同時減去A。這告訴我們，雖然乍一看形式十分接近，但仍然不能被算術運算中的思維誤導。

（4）互補律

因為

與

中有且隻有一個為1，是以可以回到1與0的運算上來了解。

（5）德·摩根定律

迎接邏輯學中最著名、最經典、最實用的定律：

它如此優美，如此簡潔地表明了與邏輯和或邏輯互相轉化的關系。用非常數學的話說：

并集的補集是補集的交集，交集的補集是補集的并集

或者，用實際生活中的例子——

一架飛機能成功降落的前提是前後起落架均已放下，缺一不可。是以，飛機不能降落，是因為“沒有既放下前起落架又放下後起落架”，或者說是“沒有放下前起落架或者沒有放下後起落架”。

此公式的用途之一是去括号。初學時，常常不自覺地寫出

這樣的式子。但實際上，去掉帶取反的括号時，或要變與，與要變或。

還有一個用處是轉換與邏輯和或邏輯。如果在電路設計中隻能使用“或”和“非”兩種邏輯，我們也照樣能表示出與邏輯——

。就比如之前提到過的，Minecraft遊戲中便隻有“或”和“非”，但能夠創造出所有邏輯元件，原理就在于此。

二、常用公式

以上公式都比較簡單，使用時局限性也比較大。是以，我們還推導出了一系列常用公式。它們的使用頻率要高得多（基礎公式中的德·摩根定律除外）。

注意：在之前的描述中，盡量避免了出現“相加”“乘積”這樣的字眼，以防造成誤會；但為了叙述友善，接下來會經常出現這些詞彙，它們不是一般意義上的“加法”“乘法”，請務必注意。

（1）吸收公式

兩項相加，且其中一項（

）是另一項（

）的因式時，另一項中的

其他因式

就被吸收了。

證明：

。先提取公因式；再運用1律。

這裡一系列公式的表達都非常簡單抽象，而實際運用時，這兩項不一定會長成A與AB的樣子，但哪怕是

這種龐大的式子，隻要眼光毒辣，也能發現公因式，并化簡成

。

（2）消因子公式

兩項相加，且其中一項（

）

取反後

是另一項（

）的因式時，另一項中的

這個相反因式

就被消去了。（不要在意“吸收”“消去”這兩個詞到底有什麼差別，隻是為了區分這兩個公式而已）

證明：

。其中提取公因式一步比較難想到，是證明過程的重點。

要注意區分吸收公式和消因子公式：一個是相同的因式，一個是相反的因式；一個直接消去兩項中較大的一項，一個僅僅去除部分因式。

（3）并項公式

兩項相加，部分因子相等（

），剩下的互補（

與

），那麼可以合并成一項公有因子。

證明：

。

（4）消項公式

這個較為複雜：三項相加，兩項中部分因子互補（

中的

與

中的

），剩下的都是第三項（

）的因式（這兩項的乘積不一定要和第三項相同，隻需都是第三項的部分因式），那麼第三項可以消去。

證明：

這個公式使用頻率不算很高，但它的證明用到了一種很有用的思想——引入備援項，以進行進一步簡化。可以看到，證明開頭，逆運用并項公式，創造了一個新的項，随後和另外兩項分别合并。除了這種用法，還可以利用重疊律

，重複寫入一項，再和其他項化簡。這種方法很有用，但需要訓練才能掌握。

三、基本規則

何謂基本規則？很難說清楚。但大概地講，它描述了對等式進行恒等變形的一些方法。

（1）代入規則

将邏輯函數式中任一變量（或函數）用另一變量（或函數）替換，等式仍成立。這類似方程化簡中的“換元法”思想。

如果有方程：

，其中

均表示函數，則可以設

，進而得到

。

舉個例子，之前提到，常用公式不僅僅局限于兩到三個變量的運算，還可以拓展到更多變量，這可以用代入規則解釋。以消因子公式為例：如果有

，則可以設

，把式子變形成

，然後運用公式。

（2）反演規則

再看看德·摩根定律：

，它可以同樣通過應用代入規則，拓展到多個變量：

。

注意到，等式的左邊是一系列項的積或和，并進行了取反，而等式的右邊則是這個反函數的展開。由此，我們可以推導出化簡一個函數的反函數——或者叫反演——的規則。這個規則就是反演規則。得到函數的反演式有兩步：

• 加變乘，乘變加——對應德·摩根定律中與和或的轉換，并保證運算順序不變；
• 對每個量取反（包括變量變為反變量和0變1，1變0），但保留非單變量的非号。

比如，

，先變換符号：

，再對變量逐個取反：

，最後檢查運算順序，并通過添加去除括号調整：

。就這樣，得到了原函數的反演函數。

（3）對偶規則

這個規則便是之前提到的“與邏輯和或邏輯常常可以互換”的一個嚴謹定義。對偶式的得到也有兩步:

• 加變乘，乘變加，保證運算順序不變；
• 0變1，1變0。

對偶式的性質是：若兩個邏輯式

成立，則它們的對偶式

也成立。比如由于

，通過對偶變換就可以得到

。這一套東西其實比較無聊，也沒什麼用，但挺神奇的。

對偶規則也是由德·摩根定律推導而來的，具體證明過程比較trivial，不再贅述。其實，對偶式和反演式的本質差別就是沒有了“對所有量取反”這一步。但為什麼要保留“對常數取反”呢？如果沒有這一步——比如，

的對偶等式是

；如果不對常數取反，就有

，顯然不成立。

第三、四章一開始非常難了解，總結一下公式：

• 0律：

  

• 1律：

  

• 交換律：

  

• 結合律：

  

• 配置設定律：

  

• 還原律：

  

• 重疊律：

  

• 互補律：

  

• 德·摩根定律：

  

• 吸收公式：

  

• 消因子公式：

  

• 并項公式：

  

• 消項公式：

  

為了加深了解，可以嘗試一下用公式化簡這些邏輯函數式。化簡要求：寫成若幹乘積項相加的形式，沒有括号，乘積項數量最少，每個乘積項中因子最少。如果思路受阻，可以随時檢視上面的公式。

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

   [1]

參考答案：

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

（感謝 @Maxwell的确良 捉蟲）

參考

1. ^題目來源：數字電路與邏輯設計，張俊濤著，清華大學出版社2017版