數字電路學習筆記(四):邏輯代數系統

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

一、基本公式

正如加減乘除中存在各式運算律一樣,邏輯運算也有運算規律。本章中,我們主要考慮與、或、非運算;異或、同或的運算律可以很方便地推導出來。我們從常量的運算開始。

begin{matrix} 0+0=0,&0+1=1,&1+1=1\ 0times 0=0,&0times 1=0,&1times 1=1\ 0'=1,&1'=0 end{matrix}

以上相當於把真值表重新表達瞭一遍,比較直觀。

接下來,我們開始把式子抽象化,把其中一個常量用變量 A 代替,看看常量與變量的運算(0律與1律):

begin{matrix} 0+A=A,&1+A=1\ 0cdot A=0,&1cdot A=A end{matrix}

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

最後,是變量間的運算,即基本運算律:

提示:在佈爾運算中,運算優先級是 非 > 與 > 或。

(1)交換律、結合律、分配律

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

begin{matrix} A+B=B+A,&Acdot B=Bcdot A\ (A+B)+C=A+(B+C),&(AB)cdot C=Acdot (BC)\ A(B+C)=AB+AC,&A+BC=(A+B)(A+C) end{matrix}

特別的分配律:由於在佈爾運算中,與運算和或運算常常處於可以互換的地位,因此,我們也有 A+BC=(A+B)(A+C) 。它和與對或的分配律非常接近,隻是“與”和“或”調換瞭而已。可以證明一下公式的正確性:

begin{aligned} (A+B)(A+C)&=Acdot A+AB+AC+BC\ &=A+AB+AC+BC\ &=A(1+B+C)+BC\ &=A+BC end{aligned}

分別用瞭:與邏輯分配律;重疊律(見(3));與邏輯分配律逆命題;1律。

(2)還原律

A''=A

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

(3)重疊律

A+A=A,space Acdot A=A

這兩個式子比較難理解一點。但畢竟,佈爾運算與四則運算中的“加法”“乘法”不是完全一致的——如果寫成 Acup A=A,space Acap A=A ,或者A || A == A, A && A == A ,表達的意思也是一樣的。在學習邏輯運算時,有許多迷惑性的符號——比如”0”與“1”,它們並不存在大小關系,而隻是“真”與“假”的對應關系,與數字0和1無關。

(4)互補律

A+A'=1,space Acdot A'=0

因為 AA’ 中有且隻有一個為1,因此可以回到1與0的運算上來理解。

(5)德·摩根定律

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

(A+B)'=A'B',space (AB)'=A'+B'

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

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

此公式的用途之一是去括號。初學時,常常不自覺地寫出 (AB)'=A'B' 這樣的式子。但實際上,去掉帶取反的括號時,或要變與,與要變或。

還有一個用處是轉換與邏輯和或邏輯。如果在電路設計中隻能使用“或”和“非”兩種邏輯,我們也照樣能表示出與邏輯—— AB=(A'+B')' 。就比如之前提到過的,Minecraft遊戲中便隻有“或”和“非”,但能夠創造出所有邏輯元件,原理就在於此。

二、常用公式

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

註意:在之前的描述中,盡量避免瞭出現“相加”“乘積”這樣的字眼,以防造成誤會;但為瞭敘述方便,接下來會經常出現這些詞匯,它們不是一般意義上的“加法”“乘法”,請務必註意。

(1)吸收公式

A+AB=A

兩項相加,且其中一項( A )是另一項( AB )的因式時,另一項中的其他因式就被吸收瞭。

證明: A+AB=A(1+B)=A 。先提取公因式;再運用1律。

這裡一系列公式的表達都非常簡單抽象,而實際運用時,這兩項不一定會長成A與AB的樣子,但哪怕是 A(X+Y)M'+A(X+Y)(B+C'+D)M'E'F'G 這種龐大的式子,隻要眼光毒辣,也能發現公因式,並化簡成 A(X+Y)M'

(2)消因子公式

A+A'B=A+B

兩項相加,且其中一項( A取反後是另一項( A'B )的因式時,另一項中的這個相反因式就被消去瞭。(不要在意“吸收”“消去”這兩個詞到底有什麼區別,隻是為瞭區分這兩個公式而已)

證明: A+A'B=(A+A')(A+B)=1cdot (A+B)=A+B 。其中提取公因式一步比較難想到,是證明過程的重點。

要註意區分吸收公式和消因子公式:一個是相同的因式,一個是相反的因式;一個直接消去兩項中較大的一項,一個僅僅去除部分因式。

(3)並項公式

AB+AB'=A

兩項相加,部分因子相等( A ),剩下的互補( BB’ ),那麼可以合並成一項公有因子。

證明: AB+AB'=A(B+B')=Acdot 1=A

(4)消項公式

AB+A'C+BC=AB+A'C

這個較為復雜:三項相加,兩項中部分因子互補( AB 中的 AA'C 中的 A' ),剩下的都是第三項( BC )的因式(這兩項的乘積不一定要和第三項相同,隻需都是第三項的部分因式),那麼第三項可以消去。

證明:

begin{aligned} AB+A'C+BC&=AB+A'C+(A+A')BC\ &=AB+A'C+ABC+A'BC\ &=(AB+ABC)+(A'C+A'BC)\ &=AB(1+C)+A'C(1+B)\ &=AB+A'C end{aligned}

這個公式使用頻率不算很高,但它的證明用到瞭一種很有用的思想——引入冗餘項,以進行進一步簡化。可以看到,證明開頭,逆運用並項公式,創造瞭一個新的項,隨後和另外兩項分別合並。除瞭這種用法,還可以利用重疊律 A=A+A ,重復寫入一項,再和其他項化簡。這種方法很有用,但需要訓練才能掌握。

三、基本規則

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

(1)代入規則

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

如果有方程: F(M(X,Y,Z),B,C,...)=G(M(X,Y,Z),B,C,...) ,其中 F,G,M 均表示函數,則可以設 A=M(X,Y,Z) ,從而得到 F(A,B,C,...)=G(A,B,C,...)

舉個例子,之前提到,常用公式不僅僅局限於兩到三個變量的運算,還可以拓展到更多變量,這可以用代入規則解釋。以消因子公式為例:如果有 (M+N)'+(M+N)XY ,則可以設 A=(M+N)',space B=XY ,把式子變形成 A+A'B ,然後運用公式。

(2)反演規則

再看看德·摩根定律: (AB)'=A'+B',space (A+B)'=A'B' ,它可以同樣通過應用代入規則,拓展到多個變量: (ABC...)'=A'+B'+C'+...,space (A+B+C+...)'=A'B'C'...

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

  • 加變乘,乘變加——對應德·摩根定律中與和或的轉換,並保證運算順序不變;
  • 對每個量取反(包括變量變為反變量和0變1,1變0),但保留非單變量的非號。

比如, ((A+B)C+0)D'cdot 1 ,先變換符號: ((AB)+Ccdot0)+D'+1 ,再對變量逐個取反: ((A'B')+C'cdot1)+D+0 ,最後檢查運算順序,並通過添加去除括號調整: (A'B'+C')cdot1+D+0 。就這樣,得到瞭原函數的反演函數。

(3)對偶規則

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

  • 加變乘,乘變加,保證運算順序不變;
  • 0變1,1變0。

對偶式的性質是:若兩個邏輯式 F_{1}=F_{2} 成立,則它們的對偶式 F_{1}^{D}=F_{2}^{D} 也成立。比如由於 A(B+C)=AB+AC ,通過對偶變換就可以得到 A+BC=(A+B)(A+C) 。這一套東西其實比較無聊,也沒什麼用,但挺神奇的。

對偶規則也是由德·摩根定律推導而來的,具體證明過程比較trivial,不再贅述。其實,對偶式和反演式的本質區別就是沒有瞭“對所有量取反”這一步。但為什麼要保留“對常數取反”呢?如果沒有這一步——比如, 0+A=A 的對偶等式是 1cdot A=A ;如果不對常數取反,就有 0cdot A=A ,顯然不成立。


第三、四章一開始非常難理解,總結一下公式:

  • 0律: 0+A=A, space 0cdot A=0
  • 1律: 1+A=1, space 1cdot A=A
  • 交換律: A+B=B+A,space Acdot B=Bcdot A
  • 結合律: A+(B+C)=(A+B)+C,space Acdot (BC)=(AB)cdot C
  • 分配律: A(B+C)=AB+AC,space A+BC=(A+B)(A+C)
  • 還原律: A''=A
  • 重疊律: A+A=A,space Acdot A=A
  • 互補律: A+A'=1,space Acdot A'=0
  • 德·摩根定律: (AB)'=A'+B',space (A+B)'=A'B'
  • 吸收公式: A+AB=A
  • 消因子公式: A+A'B=A+B
  • 並項公式: AB+AB'=A
  • 消項公式: AB+A'C+BC=AB+A'C

為瞭加深理解,可以嘗試一下用公式化簡這些邏輯函數式。化簡要求:寫成若幹乘積項相加的形式,沒有括號,乘積項數量最少,每個乘積項中因子最少。如果思路受阻,可以隨時查看上面的公式。

  1. AB(A+BC)
  2. A'BC(B+C')
  3. (AB+A'B'+A'B+AB')'
  4. (A+B+C')(A+B+C)
  5. AC+A'BC+B'C+ABC'
  6. ABD+AB'CD'+AC'DE+AD
  7. (A'B+AB')C+ABC+A'B'C
  8. A'(C'D+CD')+BC'D+ACD'+AB'C'D
  9. (A+A'C)(A+CD+D) [1]

參考答案:

  1. AB
  2. A'BC
  3. 0
  4. A+B
  5. AB+C
  6. AD+AB'C
  7. C
  8. CD'+C'D
  9. A+CD

(感謝 @Maxwell的確良 捉蟲)

參考

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

发表回复

相关推荐

人民黃河期刊

《人民黃河》是月刊,創刊於1949年,是由水利部主管、黃河水利委員會主辦的水利科技專業學術刊物,自1992年起連續6次入選全國...

· 4分钟前

不看後悔系列:韓劇《浪漫的體質》

為什麼寫韓劇,嗯,答主是學韓語的,又是個文案,所以韓劇真的是再適合不過瞭。但是,這不是我今天寫這篇文的原因。《慶餘年...

· 4分钟前

菜字头食品搭载业务增长新引擎,构建集团完整供应链生态

应用案例概述 铱云供应链 公司名称:菜字头食品‍‍‍‍‍‍‍‍‍‍‍‍‍ 业务简介:成功孵化饭戒、韦小堡、喜赞等品牌,拥有线下门店超 ...

· 10分钟前

共聚焦顯微鏡——摩擦學領域的新款“滑板鞋”

兩個物體表面相互接觸即會產生相互作用力,研究具有相對運動的相互作用表面間的摩擦、潤滑與磨損及其三者之間關系即為摩擦學...

· 10分钟前

土耳其语语法学习

土耳其语(原:Türkçe,英语:Turkish language)属阿尔泰语系突厥语族乌古斯语支,与它同支的语言有阿塞拜疆语、土库曼语和 ...

· 17分钟前