第3節(jié) 邏輯代數(shù)基礎

邏輯代數(shù)是設計、分析數(shù)字邏輯電路的數(shù)學理論工具，在常用的普通數(shù)字電路中只涉及邏輯代數(shù)知識的最基礎部分。

用不同方式表述同一個邏輯問題，稱為表述方式的轉換。用不同運算結構的表達式表示同一個邏輯問題，稱為表達式的變換。等效轉換與等效變換是邏輯代數(shù)處理邏輯問題的兩個基本手段，與表達式相關的轉換和表達式的變換是邏輯代數(shù)的主體內容。

一、真值表、最小項、標準與或表達式

1．最小項和真值表

1）最小項

邏輯代數(shù)把包含全部變量（每個變量以原變量或反變量形式只能出現(xiàn)一次）的 “全變量乘積項”，叫做最小項。

在真值表中，全部變量的每一種取值組合對應一個最小項，其中對應0值的變量加反號、對應1值的變量不加反號。最小項與全部變量的取值組合一一對應，N個變量的邏輯函數(shù)有2N種取值組合，就有2N個最小項。最小項用m表示，為便于區(qū)分，還要給予編號，編號等于取值組合的二進制數(shù)對應的十進制值。

表1-20、表1-21、表1-22分別為二變量、三變量、四變量邏輯函數(shù)真值表中變量取值組合與最小項的對應關系。

2）標準與或表達式

由最小項相或構成的邏輯表達式叫做“標準與或表達式”，簡稱“標準與或式”。標準與或表達式的結構具有以下兩個特點：

（1）式中只有與、或兩種運算和對變量取反的非號，與運算都是最小項，由對應同一種函數(shù)值的全部（且無重復的）最小項組成；

（2）式中無括號、無對運算取反的非號，表達式中的運算順序是先與后或。

一個邏輯的函數(shù)表達式可隨意變換為多種形式，只有標準與或表達式具有唯一性。

2．由真值表寫標準與或式的方法

在介紹基本邏輯時，按真值表寫邏輯表達式依據(jù)的是基本邏輯定義，不能適用于寫一般邏輯的表達式。依據(jù)標準與或表達式跟真值表的對應關系和標準與或表達式的唯一性，就可以方便、準確地按真值表寫出各種邏輯函數(shù)的標準與或表達式，并能確保它們之間的等效性。

在同一個真值表中，由函數(shù)取1值對應的最小項組成的標準與或式是邏輯正函數(shù)（也叫原函數(shù)）表達式，由函數(shù)取0值對應的最小項組成的標準與或式是邏輯反函數(shù)表達式。

（1）由真值表寫正邏輯函數(shù)的標準與或式。

以或邏輯的真值表（見表1-13）為例，按真值表寫表達式的步驟如下：

① 在真值表中找出使函數(shù)L=1所對應的變量組合及其對應的最小項如表1-23所示。

② 把所有使L=1的最小項相或，得到的就是按真值表寫出的標準與或表達式：

可用真值表（表1-24）證明1-35式和或邏輯的定義式1-14是等效（相等）的。

通過實際數(shù)據(jù)運算證明兩個表達式是等效的，即

在本節(jié)后文的“表達式化簡”內容中還將通過表達式化簡說明1-14式是1-35式的最簡式。前文介紹的七種邏輯中，非邏輯、與邏輯和異或邏輯的定義式就是標準與或式，或邏輯的標準與或式和定義式的等效關系在此已經(jīng)證明，另三種邏輯的證明、化簡留給讀者。

（2）由真值表寫反邏輯函數(shù)的標準與或式。

把L=0的所有最小項相或，構成反函數(shù)的標準與或表達式。

表1-16的真值表中還有一組使L=0的組合：A=0、B=0，寫成乘積項是

是A+B的反函數(shù)。

給正函數(shù)的表達式整體加反號也表示反函數(shù)：

所以，

在下文介紹“摩根定理”的內容中讀者還會見到這個等式并領略它的重要性。

（3）標準與或式都可用最小項求和的編號形式表示：

表達式中：Σ表示求和（即或運算）, mi表示邏輯函數(shù)的最小項含i個變量，括號中的數(shù)字表示最小項的編號。如：

可以表示為：

（4）邏輯的正、反函數(shù)成互補關系。正、反函數(shù)式相或合并，就是一個邏輯的全部最小項相或，其結果恒等于1。用表達式表示為：

邏輯函數(shù)若有不可能出現(xiàn)或不允許出現(xiàn)的變量組合，這些變量組合對應的最小項叫做約束項（或無關項）。把所有約束項相或組成約束函數(shù)的標準與或表達式，用于表示邏輯的約束條件。在真值表和后文的卡諾圖中，約束項通常用?或×表示，用?表示約束函數(shù)。

約束項對正、反函數(shù)都無影響，約束項的重要應用是參與正、反函數(shù)表達式化簡（見后文表達式的圖形化簡法部分）。

二、摩根定理和括號變換法則

邏輯表達式的等效變換有繁簡變換和運算結構變換兩種類型。表達式的繁簡等效變換由與、或運算法則保證，表達式的運算結構等效變換要參照摩根定理進行。在表達式等效變換的步驟中經(jīng)常涉及括號的用與不用，以保證變換的等效性。

1．德·摩根定理

德·摩根定理（簡稱摩根定理）是揭示與、或兩種基本邏輯之間的等效變換關系，專門用于處理反號的定理。兩個變量的摩根定理表達式形式：

1-39式表示“兩個變量相或后取反，和兩個變量取反后相與等效”。這個等效關系在或邏輯真值表（表1-25）中表現(xiàn)為正、反函數(shù)關系。

按函數(shù)值1、0定名函數(shù)的正、反，按變量正、反定名邏輯正、負。但此處不討論負邏輯，第3章內容將涉及負邏輯的使用。

Y=1對應或邏輯的正函數(shù)：

Y=A+B

Y=0則對應或運算的反函數(shù)：

正函數(shù)表達式取反和反函數(shù)表達式等效：

同樣，1-40式表示“兩個變量相與再取反，和兩個變量取反后相或等效”，從與邏輯的真值表（表1-26）中表現(xiàn)為正、反函數(shù)關系。

Y=1對應與邏輯的正函數(shù)：

Y=A·B

Y=0則對應與運算的反函數(shù)：

就是

摩根定理還適用于更多變量的與、或變換，如：

2．括號變換法則

和普通數(shù)學一樣，邏輯表達式中超越規(guī)則的運算也用加括號方式表示。在表達式的變換中加括號和去括號（也叫展開括號）的目的是保證變換的等效性。

（1）在與、或的混合運算中，不同乘積項中的相同變量也稱作公因子，相同的運算單元稱作公因式。提取公因子（或公因式）的表達式變換要加括號，如：

提取公因子（或公因式）的逆變換是展開括號，如：

這兩個表達式變換在普通數(shù)學中已是常識，在邏輯變換中的等效性是否成立，是需要給予證明的。表1-27是證明AB+AC與A(B+C)是否相等的真值表。

通過真值表證明：

AB+AC=A(B+C)

成立。

經(jīng)過證明的表達式等效變換可以作為公式使用。

（2）在與和異或的混合運算中，經(jīng)過證明，也有同樣的等效變換。

提取公因子：

展開括號：

（3）異或和或運算之間要嚴格按異或運算變換為與或復合運算處理：

（4）用摩根定理變換表達式運算類型，有時要加括號，以維持表達式原來運算順序，保證變換的等效性。如：

可用真值表檢驗表達式的等效關系，如表1-28所示。

通過真值表的實際運算證明，與非運算變換為或運算后加括號能保證等效，而不加括號的變換就不能等效（有兩組變量運算后的函數(shù)值與原式不等）。

三、邏輯表述方式之間的轉換

1．按表達式做真值表

按表達式做真值表有計算法和最小項法兩種常用方法。

（1）計算法：將變量的各組取值分別代入表達式進行計算，把計算得到的函數(shù)值填入真值表的表格，就完成了邏輯函數(shù)真值表的制作，如表1-29所示。

（2）最小項法：依據(jù)標準與或表達式跟真值表的對應關系，只要能得到邏輯函數(shù)的標準與或表達式，就可以做出邏輯函數(shù)的真值表，而任何形式的邏輯表達式都能變換為標準與或表達式。

【例1-3】

依據(jù)標準與或表達式中的最小項，按原變量對應1、反變量對應0的關系，可確定使函數(shù)取1值的變量組合（如表1-30所示）：

設計真值表，函數(shù)有3個變量A、B、C，全部變量的組合數(shù)為23=8種（N個變量的全部組合為2N）。在變量取值組合對應的函數(shù)值位置填寫1，其他位置填寫0。做出的真值表如表1-31所示。

用計算法做真值表有時比變換標準與或式的方法簡單。

2．表達式與邏輯圖之間的轉換

表達式中的運算符就是邏輯圖中的邏輯符號，也是邏輯電路中的邏輯門。表達式中的邏輯運算順序就是各邏輯門電路（邏輯符號）之間的連接關系。

表達式是邏輯圖（邏輯電路）的數(shù)學表示形式，結構一致的邏輯電路與邏輯表達式具有相互轉換的等效關系。

處理邏輯表達式與邏輯圖之間的轉換時常需要對表達式按運算順序做分層，表達式的等效分層由代入法則予以保證。

1）代入法則

借助代入法則可將表達式進行分層處理，以確定邏輯表達式中包含的各種運算及運算順序。依據(jù)代入法則，在邏輯表達式中，任何變量都可視為一個函數(shù)，任何一個或一組運算都

可用一個新變量代換。如：

Y=AB+CD

若：

D=MN+L

表達式則是

Y=AB+C（MN+L）

如果設：

F=AB

表達式又變換為

Y=F+C（MN+L）

代入法則所允許的代換對表達式的邏輯本質沒有任何影響。

2）按表達式畫邏輯圖

（1）按表達式畫邏輯圖的步驟。

① 確定變量個數(shù)，即邏輯圖的輸入信號的個數(shù)。

② 借助代入法則對表達式的運算給以分層，直到變量為止，確定各層運算的邏輯符號類型。分層順序：一般運算按或、異或、與、非、括號排序，多層的非運算按由上向下順序逐層確認。

③ 確定運算順序，即邏輯圖中邏輯符號的連接關系，畫出邏輯圖。

【例1-4】畫出表達式

的邏輯圖。

表達式中的變量：A、B、C、D，共4個。

對表達式的運算分層，直到變量為止，確定各層運算需使用的邏輯符號。

第1層：

L=X1+X2+X3

是3個輸入信號的或運算（用三輸入端的或門），其中（是3輸入端的與門，C信號要先經(jīng)過非門）, （是2輸入與非門），而還需要繼續(xù)分層確定。

第2層：

Y和D之間的運算用到一個異或門，而Y還需再分層。

第3層：

L=X1+X2+X3

其中，Z和C的運算用一個2輸入與門。

第4層：

A、B之間的運算是2輸入或門，其中B信號要先經(jīng)過一個非門。

最后，按表達式分層的逆順序，用分析出的邏輯符號畫出邏輯圖，如圖1-15所示。

（2）按邏輯器件變換表達式的運算結構。

表達式中的運算類型以及運算順序是跟邏輯圖的結構相對應的，不同的邏輯器件對應不同的邏輯運算符號。按指定的邏輯器件去設計邏輯電路，首先要通過變換得出相應運算結構的表達式。摩根定理可以隨時應用于表達式任何部位的與、或、非變換，是隨意變換表達式運算結構的方便工具。

在邏輯代數(shù)中常按運算類型（對應邏輯器件）和順序給表達式命名，例如：與或式、或與式、與或非式、與非-與非式，等等。

【例1-5】下面是一個邏輯函數(shù)表達式的4種結構：

和上述4種表達式結構對應的邏輯圖如圖1-16所示。

由于一片數(shù)字集成電路內含多個同類邏輯門，為充分利用電路資源，在實際制作電路時，通常選用同種邏輯器件構成，如與非門構成“與非-與非”結構、或非門構成的“或非-或非”結構，把與非門、或非門的輸入端并聯(lián)，都可構成非門。

3）按邏輯圖寫表達式的方法

按邏輯圖寫表達式有兩種方法，一種是從邏輯圖的輸入端入手，另一種是從邏輯圖的輸出端入手。

（1）由電路的輸入端入手寫表達式的方法。

由電路的輸入端寫邏輯表達式時，是從電路的輸入端開始依次在各邏輯門的輸出端寫出各邏輯門的輸出結果，當寫到電路的輸出端時，完整的邏輯表達式也就寫出來了。

【例1-6】圖1-17所示就是這種方法。

寫出的表達式：

（2）由電路輸出端入手寫表達式的方法。

由電路的輸出端入手寫邏輯表達式時，先給電路中的各邏輯門的輸入信號賦予一個臨時代號，再從輸出端入手依次把各個邏輯門表示的邏輯運算關系逐層代入，一直推寫到輸入端，就可寫出完整的表達式。

【例1-7】圖1-18所示就是這種方法。

寫出的表達式：

四、表達式化簡

1．表達式化簡的意義及最簡標準

數(shù)字邏輯電路是按照表達式的運算結構連接成的，而一種邏輯功能可以有多種結構的表達式。化簡結構是表達式變換的重要內容。

【例1-8】由真值表寫出的或運算表達式：

由或運算定義寫出的表達式：

M2=A+B

兩個表達式對應的邏輯圖如圖1-19所示。

前文已證明兩個表達式的邏輯功能是等效的，選擇結構簡單的表達式制作電路，可以提高電路運行的可靠性和降低制作成本。因此，表達式化簡是邏輯電路設計過程中不可忽視的環(huán)節(jié)。

把結構復雜的表達式變換為結構最簡單的表達式叫做表達式化簡，也叫邏輯函數(shù)化簡。表達式化簡要在與或表達式下進行，得到最簡與或式，再通過摩根定理變換獲得其他結構的最簡式。

與或表達式的最簡標準是：乘積項個數(shù)最少，而且每個乘積項中的變量數(shù)最少。

2．表達式化簡方法

表達式化簡要利用與或式結構進行操作。不是與或結構的表達式，要應用摩根定理變換為與或式。表達式化簡常用方法有公式法和圖形法兩種。

公式法是利用與、或運算法則和等效變換公式進行化簡。

結構簡單的與或式化簡可利用與、或運算法則AA=0、1+A=1等做公式法化簡，減少乘積項及乘積項中變量個數(shù)，獲得與或表達式的最簡結構。

【例1-9】利用=0的化簡：

【例1-10】利用1+A=1的化簡：

B+AB=B(1+A)=B

對于結構較為復雜的與或式，要利用“A+=1”消除變量，進行化簡。

【例1-11】利用A+A=1化簡：

邏輯代數(shù)把“只有1個變量互補、其他因子相同的兩個乘積項”稱為邏輯相鄰項（簡稱為相鄰項）。一對相鄰項相或，可消去其中的互補變量，合并為一個新的乘積項。通過多次相鄰項結組、消除變量，直到無變量可消時，表達式就可能達到最簡。這是公式法化簡的本質原理，以卡諾圖為工具實施這種化簡的方法就是圖形法。

卡諾圖是由真值表衍變成的方格圖，本質還是真值表。圖1-20所示分別為2變量卡諾圖、3變量卡諾圖和4變量卡諾圖，是由表1-20、表1-21、表1-22所示真值表變換結構方式而成。

卡諾圖和真值表一樣，跟標準與或表達式有嚴格的對應關系。卡諾圖中的方格，既對應全部變量的各取值組合及函數(shù)值，又對應最小項。卡諾圖的特殊結構使所有相鄰的最小項都處于相鄰位置，把各最小項的可化簡關系直觀地顯示出來。卡諾圖化簡法常用在不多于5個變量的邏輯函數(shù)的化簡（本書未用5變量卡諾圖）。

制作一個邏輯函數(shù)的卡諾圖，可依據(jù)函數(shù)的標準與或式直接填制。為使卡諾圖內容簡潔，習慣上只填一種函數(shù)值，有約束項的再用 φ 或 × 標出約束項的位置。不是標準與或式的要先變換為標準與或式，再填制卡諾圖，也可由一般與或式按“倒化簡法”直接填卡諾圖。

【例1-12】制作函數(shù)Y=ABC+ABC+ABC+ABC+ABC的卡諾圖。

這個函數(shù)表達式已經(jīng)是含有3個邏輯變量的標準與或式（沒有約束項），可按其中包含的最小項直接填制卡諾圖。具體步驟如下：

第1步，畫出3個變量的空白卡諾圖。

第2步，按表達式：

在卡諾圖的相應空格中填寫1。得到的卡諾圖如圖1-21所示。

用卡諾圖化簡，首先要制作出卡諾圖。卡諾圖跟真值表一樣，是與函數(shù)的標準與或表達式相對應的，制作卡諾圖之前通常將函數(shù)表達式變換為標準與或式。

【例1-13】制作函數(shù)的卡諾圖。

第1步，先將函數(shù)表達式轉換為標準與或式：

第2步，畫出3個變量的空白卡諾圖，然后在4個最小項所在的方格中填入1，如圖1-22所示。

填制卡諾圖也可以用一般與或式，稱為倒化簡法。

【例1-14】制作函數(shù)的卡諾圖。

先按表達式中變量個數(shù)畫出4個變量的空白卡諾圖，再在圖中找出含有表達式中各乘積項為因子的最小項對應的方格，并填入1，如圖1-23所示。

用公式法對一般結構的與或式化簡時，為明確各乘積項之間的結組合并關系，需要將其變換為標準與或式，再結組化簡。如：

若用圖形化簡，只是在卡諾圖上畫兩個圈（稱為圈項），就能得到函數(shù)化簡后的最簡與或表達式，既直觀又簡單，如圖1-24所示。

用卡諾圖圈項化簡，被圈的必須是2整數(shù)冪的同值方格。兩（21）個相鄰最小項相或，可消去其中的互反變量，合并為一個乘積項，如圖1-25所示。

4（22）個有相鄰最小項相或，可消去其中的互反變量，合并為一個乘積項，如圖1-26所示。

8（23）個有相鄰最小項相或，可消去其中的3個互反變量，合并為一個乘積項，如圖1-27所示。

用卡諾圖化簡表達式的步驟：

① 將表達式變換為標準與或式，做出邏輯函數(shù)的卡諾圖；

② 在圖中畫出圈項線，并寫出每個圈項的合并結果；

③ 將各圈項得到的新乘積項相加，寫出化簡后的與或表達式。

一個邏輯函數(shù)含幾個變量，它的每個最小項就有幾個相鄰項。在化簡時，一個最小項可參與多組合并，或運算的重疊律A=A+A說明一項多用是合法的。

【例1-15】或運算標準與或式的化簡：

或運算的重疊律在圖形法化簡中的做法就是一個最小項可參與多個圈項合并的化簡方法，目的在于使化簡一次達到最簡。上式的圖形化簡如圖1-28所示。

圖形化簡的圈項合并時要遵循“能大不小”的原則，充分利用或運算的重疊律，使圈項范圍達到最大，可確保化簡能一次達到最簡的結果。

【例1-16】用卡諾圖化簡F=ABC+ABC+ABC+ABC，如圖1-29所示。

化簡結果：F=AB+BC+AC

“能大不小”的規(guī)則不是絕對的，要因題而異。

【例1-17】化簡特例如圖1-30所示。

對于具有約束項或無關項的函數(shù)，可借助約束項（或無關項）把表達式化簡得更為簡單。

【例1-18】利用約束項化簡，函數(shù)F=∑m4(2,3,4,5,6,7,11,14) 的約束項條件是：φ=∑m4(9,10,13,15)。

化簡如圖1-31所示。

（a）為不考慮約束條件的化簡結果：

（b）為利用約束條件的化簡結果：

圖1-32所示為三例未達最簡的化簡圈項以及正確圈項方法對照。

在可以化簡的邏輯函數(shù)中，有一部分函數(shù)的最簡結果不是唯一的，如圖1-33所示。

利用反函數(shù)化簡也是圖形法化簡的常用手段。

【例1-19】用卡諾圖推證摩根定理。

設F=AB，則

用卡諾圖對F化簡，如圖1-34所示。

所以，即

在實用中，電路的主體結構通常用特定功能的數(shù)字集成電路構成，需要制作者設計的只是一些較簡單的輔助性電路，以解決各集成電路芯片之間的信號匹配問題，公式法和圖形法的化簡手段是很適用的。