《數字電路設計及Verilog HDL實現》課件第2章

2.1數制與編碼

2.2邏輯代數

2.3邏輯函數的化簡

2.4邏輯門電路

習題第2章數字技術基礎2.1.1進位計數制

采用若干位數碼進行計數，并規(guī)定進位規(guī)則的科學計數法稱為進位計數制，也簡稱數制。

某一進位計數制中，所采用計數數碼的個數，稱為該數制的基數。每一位數碼因其所處的位置不同而代表的不同的數值，稱為該數位的位權。2.1數制與編碼以十進制數為例。十進制數采用0、1、2……9共10個數碼進行計數，進位規(guī)則為“逢十進一，借一當十”。十進制數的基數為10。對于十進制數(333)10=3×100+3×10+3×1，雖然每個數碼都是3，但因為所處的位置不同而代表不同的數值，100、10、1是十進制數(333)10從左到右各位的位權值。即十進制數各位的位權值為10的冪。對任意一個十進制數，都可以按位權展開，表示為

(2.1.1)例如，十進制數324.15按位權展開表示為

(324.15)10=3×102+2×101+4×100+1×10－1+5×10－2

上述十進制數的位權展開式可推廣到任意的R(R≥2)進制數。R進制數采用0、1……R－1共R個數碼進行計數，進位規(guī)則為“逢R進一，借一當R”。R進制數的基數為R，

各位的位權值為R的冪。對任意一個R進制數，都可以按位權展開，表示為(2.1.2)數字系統(tǒng)中，常用的數制有二進制、八進制、十進制和十六進制，它們所采用的數碼、進位規(guī)則、基數和位權如表2.1.1所示。表2.1.2列出了這幾種數制各數碼間的對應關系。表2.1.1數字系統(tǒng)中常用的數制表2.1.2二、八、十、十六進制數碼對應關系2.1.2數制轉換

1.R進制數轉換為十進制數

要將R進制數轉換為十進制數，只需將R進制數按位權展開的方法表示，再按十進制運算規(guī)則進行運算即可。

【例2.1.1】將二進制數11011.101轉換為十進制數。

解(11011.101)2=1×24+1×23+0×22+1×21+1×20+1

×2－1+0×2－2+1×2－3

=16+8+0+2+1+0.5+0+0.125=(27.625)10

【例2.1.2】將八進制數126.73轉換為十進制數。

解(126.73)8=1×82+2×81+6×80+7×8－1+3×8－2

=64+16+6+0.875+0.046875

=(86.921875)10

【例2.1.3】將十六進制數1F0B.C轉換為十進制數。

解

(1F0B.C)16=1×163+15×162+0×161+11×160+12×16－1

=4096+3840+0+11+0.75

=(7947.75)10

2.十進制數轉換為R進制數

將十進制數轉換為任意的R進制數，需要將整數部分和小數部分分開轉換，然后將轉換后的兩部分結果拼接在一起。

整數部分轉換時通常采用除R取余法，也就是將十進制數的整數部分除以R，余數即為轉換后R進制數整數部分的最低位，然后將商繼續(xù)除R取余，直至商為0，逐次得到的

余數就是轉換后R進制數整數部分從低到高的各個數位。例如，要將十進制數(47)10轉換為二進制數，轉換過程如下所示:

所以

(47)10=(101111)2將十進制數轉換為R進制數時，小數部分的轉換通常采用乘R取整法，也就是將十進制數的小數部分乘以R，乘積的整數位就是轉換后R進制數小數部分的最高位，然后將乘積的小數部分繼續(xù)乘R取整，直至小數部分為0或滿足精度要求，逐次得到的乘積整數位就是轉換后R進制數小數部分從高到低的各個數位。例如，要將十進制數(0.625)10轉換為二進制數，轉換過程如下所示：

所以

(0.625)10=(0.101)2

將(47)10和(0.625)10的轉換結果拼接在一起，就可以得出(47.625)10=(101111.101)2。

【例2.1.4】將十進制數493.75轉換為十六進制數。

解整數部分除16取余，如下所示:

即

(493)10=(1DE)16

小數部分乘16取整，如下所示:

即

(0.75)10=(0.C)16

所以

(493.75)10=(1DE.C)16

需要說明的是，有些時候十進制小數轉換為其他進制數時，不能完全精確轉換，也就是在乘R取整時，不能使小數部分變?yōu)?。例如，十進制小數0.3，其等值的二進制小數0.01001001001……是一無限循環(huán)小數，此時，只需要按精度要求取一定位數就可以了。

3.二進制數與八進制數和十六進制數間的轉換

若將3位二進制數看做一個整體，則3位的整體之間是逢八進一的，因此，3位二進制數對應于1位八進制數。將八進制數轉換為二進制數時，只需要將每1位八進制數替換為等值的3位二進制數，然后去掉整數部分高位的0，以及小數部分低位的0就可以了。

例如：

將二進制數轉換為八進制數時，需要從小數點開始，分別對二進制數的整數部分和小數部分按3位進行分組。整數部分從小數點開始從右到左每3位一組，左邊不足3位的用0補足。小數部分從小數點開始從左到右每3位一組，右邊不足3位的用0補足。然后將每組的3位二進制數替換為等值的1位八進制數。例如：

二進制數與十六進制數之間的轉換方法類似于二進制數和八進制數之間的轉換，只是在十六進制數轉換為二進制數時，需要將每一位十六進制數替換為等值的4位二進制數，而將二進制數轉換為十六進制數時，需要按4位進行分組。

【例2.1.5】將十六進制數(3BA8.E)16轉換為二進制數。

解

【例2.1.6】將二進制數(1011101.10111)2轉換為十六進制數。

解2.1.3幾種常用的編碼

除了用二進制數表示數值數據外，數字系統(tǒng)中還使用二進制數碼表示一些具有特定含義的信息，如字母、學號等。這些用約定的0、1數碼組合來表示特定含義信息的代碼稱為編碼。這里介紹幾種常用的編碼。

1. BCD碼

BCD(BinaryCodedDecimal)碼也稱為二—十進制代碼，就是用二進制編碼來表示十進制數。與十進制數轉換成二進制數不同，BCD碼與十進制數碼之間是一種事先約定的直接對應關系，因此能夠方便地表示日常生活中由十進制數碼表示的信息，便于實現人機交互，是一類重要的編碼。十進制有0、1……9共10個數碼，因此至少需要4位二進制數碼來表示1位十進制數碼。而4位二進制數碼共有16種組合，選擇其中不同的10種組合分別表示10個十進制數碼，就形成了不同的BCD碼。表2.1.3列出了幾種常用的BCD碼。

表2.1.3中，8421BCD碼、5421BCD碼和2421BCD碼各數位都有確定的位權值，可以按位權展開求得所代表的十進制數碼。例如：

(1001)8421BCD=1×8+0×4+0×2+1×1=(9)10

(1001)5421BCD=1×5+0×4+0×2+1×1=(6)10

(1011)2421BCD=1×2+0×4+1×2+1×1=(5)10

這些BCD碼被稱為有權BCD碼。其中，因為8421BCD碼各位的位權值與二進制數各位位權值一致，所以應用最為普遍。

余3碼的各數位并沒有確定的位權值，因此被稱為無權BCD碼。從8421BCD碼和余3碼的編碼可以看出，在有效編碼范圍內，8421BCD碼加3(對應二進制的0011)就可以獲得余3碼，這一特點能夠方便地實現8421BCD碼和余3碼之間的轉換。

表2.1.3常用BCD碼

【例2.1.7】將十進制數(93.26)10分別表示成8421BCD碼和余3碼。

解

【例2.1.8】將5421BCD碼(101110101000.0010)5421BCD轉換為十進制數。

解

(101110101000.0010)5421BCD=(1011’1010’1000.0010)5421BCD=(875.2)10

BCD碼表示的十進制數具有二進制碼的形式，同時又有十進制數的特點，碼組(也就是4位二進制數碼)之間是逢十進一的。

2.循環(huán)碼

循環(huán)碼也稱為格雷碼，是一種無權碼，具有多種形式。但不論是那種循環(huán)碼，都有一個共同的特點，就是任意兩個相鄰碼之間只有一位不同。表2.1.4列出了十進制數、二進制數與典型2位、3位、4位循環(huán)碼的對應關系。表2.1.4十進制數、二進制數與典型2位、3位、4位循環(huán)碼的對應關系

3. 奇偶校驗碼

二進制信息代碼在傳輸或存儲過程中，可能會由于噪聲或干擾而產生錯誤，致使某些位由0變成了1，或使某些位由1變成了0。為了避免或減少錯誤產生的影響，通常采用信息冗余的方法編碼，也就是在原有信息位的基礎上增加若干位校驗位，通過這些校驗位來檢出錯誤，進而糾正錯誤。具有校驗位的信息碼稱為校驗碼，其中能夠檢出錯誤的校驗碼稱為檢錯碼，而能夠發(fā)現錯誤并糾正錯誤的校驗碼則稱為糾錯碼。奇偶校驗碼是應用最多也是最簡單的檢錯碼，有奇校驗和偶校驗兩種方式。奇校驗就是在信息位之前或之后增加1位校驗位，使得校驗位與信息位一起構成的碼字中所含1的個數為奇數。而偶校驗碼則是通過增加1位校驗位，使碼字中所含1的個數為偶數。表2.1.5給出了一些4位信息碼的奇偶校驗碼示例，這里約定校驗位為碼字的高位。表2.1.5奇偶校驗碼示例邏輯代數是按一定邏輯關系進行運算的代數。與普通代數一樣，邏輯代數是變量、常量和一些運算符組成的代數系統(tǒng)。與普通代數不同的是：2.2邏輯代數

(1)邏輯代數中的變量只有0、1兩種取值。這兩種取值不代表數的大小，而表示兩種不同的狀態(tài)，如命題的真假、電平的高低、開關的通斷、脈沖的有無等。

(2)邏輯代數只有與、或、非三種基本運算。

邏輯代數中，變量也稱為邏輯變量，通常用字母A、B、C……表示。由邏輯變量、邏輯常量(0或1)、邏輯運算符按一定規(guī)則組成的表達式稱為邏輯表達式。2.2.1基本邏輯運算

1.與運算

如果決定某一事件的條件都具備時，事件才發(fā)生，否則就不發(fā)生，這樣的因果關系就是邏輯與。例如，圖2.2.1所示電路就是一個滿足這種邏輯關系的簡單電路。只有開關A、B都閉合時，燈才亮，否則燈滅。燈狀態(tài)與開關狀態(tài)之間的關系如表2.2.1所示。圖2.2.1與邏輯示例電路在表2.2.1中，如果將燈亮用邏輯1表示，燈滅用邏輯0表示，開關閉合用邏輯1表示，開關斷開用邏輯0表示，就形成了邏輯與運算的真值表，如表2.2.2所示。在這里，A、B是兩個邏輯變量，它們的不同取值會決定邏輯變量P的值，真值表列出了A、B兩個邏輯變量在各種取值組合情況下，對應P的取值，因此能夠唯一描述A、B與P之間的邏輯運算關系。表2.2.1與邏輯示例電路狀態(tài)表2.2.2與運算真值表與運算也稱為邏輯乘運算，可以用如下的邏輯表達式進行描述：

P=A·B

或

P=A∧B

在不產生歧義的情況下，也可以簡寫為P=AB。

由與運算真值表可以得出與運算的運算規(guī)則如下：

0·0=00·1=01·0=01·1=1

即有0出0，全1出1。并由此可推出一般形式：

A·0=0(2.2.1)

A·1=A(2.2.2)

A·A=A(2.2.3)

2.或運算

如果決定某一事件的條件中有一個或一個以上具備時，事件就發(fā)生，否則就不發(fā)生，這樣的因果關系就是邏輯或。圖2.2.2給出了一個描述這種邏輯關系的簡單示例電路。只要開關A、B有一個閉合，燈就會亮，只有A、B都斷開時，燈才不亮。燈狀態(tài)與開關狀態(tài)之間的關系如表2.2.3所示。圖2.2.2或邏輯示例電路同樣，在表2.2.3中，如果約定燈亮用邏輯1表示，燈滅用邏輯0表示，開關閉合用邏輯1表示，開關斷開用邏輯0表示，就形成了邏輯或運算的真值表，如表2.2.4所示。表2.2.3或邏輯示例電路狀態(tài)表2.2.4或運算真值表或運算也稱為邏輯加運算，邏輯表達式如下：

P=A+B

或

P=A∨B

由或運算真值表可以得出或運算的運算規(guī)則如下：

0+0=00+1=11+0=11+1=1

即有1出1，全0出0。一般形式有：

A+1=1(2.2.1′)

A+0=A(2.2.2′)

A+A=A(2.2.3′)

3.非運算

如果決定某一事件的條件不具備時，事件才發(fā)生，否則就不發(fā)生，這樣的因果關系稱為邏輯非。圖2.2.3給出了一個描述邏輯非關系的簡單電路，只有開關A斷開時，燈才會亮，否則，燈就不亮。燈狀態(tài)與開關狀態(tài)之間的關系如表2.2.5所示。圖2.2.3非邏輯示例電路在表2.2.5中，如果仍然約定燈亮用邏輯1表示，燈滅用邏輯0表示，開關閉合用邏輯1表示，開關斷開用邏輯0表示，就形成了邏輯非運算的真值表，如表2.2.6所示。表2.2.5非邏輯示例電路狀態(tài)表2.2.6非運算真值表非運算邏輯表達式為

由非運算真值表可以得出非運算的運算規(guī)則如下：

由此可推出：

(2.2.4)

(2.2.5)

(2.2.5′)

4.基本邏輯運算的邏輯符號

在數字電路中，實現上述基本邏輯運算的電路稱為邏輯門電路。如用來實現邏輯與運算的電路稱為與門，實現邏輯或運算的電路稱為或門，實現邏輯非運算的電路稱為非門。邏輯門電路是構成數字電路的基礎元件，通常用圖2.2.4所示的邏輯符號表示。圖中，參加邏輯運算的邏輯量A、B稱為輸入，運算結果P稱為輸出，邏輯門電路符號反映了輸入與輸出間的邏輯關系。圖2.2.4與門、或門、非門邏輯符號(a)與門；(b)或門；(c)非門圖2.2.4給出的邏輯門電路符號是國際電工委員在IEC617－12標準中推薦使用的邏輯符號，也符合我國的國家標準GB4728.12—85。如無特殊說明，本書一律采用該標準推薦使用的邏輯符號。同時，為方便讀者參考，圖2.2.5的第一行給出了國內以前沿用(部頒標準)的與、或、非門的邏輯符號，第二行給出了國外一些書籍使用(美標)的與、或、非門的邏輯符號。圖2.2.5國內沿用和國外常用與、或、非門邏輯符號(a)與門；(b)或門；(c)非門2.2.2復合邏輯運算

由與、或、非三種基本邏輯運算可以導出一些復合邏輯運算，如與非、或非、與或非、異或、同或等。實現這些常用復合邏輯運算的電路也是數字電路的基本構成單元，稱為邏輯門電路，如與非門、或非門、與或非門、異或門、同或門等。

1.與非運算

與非邏輯運算是與運算和非運算的復合，就是將輸入變量先進行與運算，再進行非運算，它可以有多個輸入變量。兩變量的與非邏輯表達式為

與非門邏輯符號如圖2.2.6所示。由與非邏輯的運算方法可得出與非運算真值表如表2.2.7所示。圖2.2.6與非門邏輯符號表2.2.7兩變量與非運算真值表

2.或非運算

或非運算是或運算和非運算的復合，就是對輸入變量先進行或運算，再進行非運算。或非運算同樣允許對多個輸入變量進行運算。

兩變量的或非運算邏輯表達式為

或非門邏輯符號如圖2.2.7所示，其真值表如表2.2.8所示。圖2.2.7或非門邏輯符號表2.2.8兩變量或非運算真值表

3.與或非運算

與或非運算是與運算和或非運算的復合，與或非門的邏輯符號如圖2.2.8所示。圖2.2.8與或非門邏輯符號與或非運算的邏輯表達式為

這里首先進行A·B和C·D的邏輯與運算，然后將邏輯與運算的結果再進行或非運算，由此可得出與或非運算真值表，如表2.2.9所示。表2.2.9與或非運算真值表

4.異或運算

異或運算是只有兩輸入變量的邏輯運算，其邏輯表達式定義為

實現異或運算的電路稱為異或門，異或門邏輯符號如圖2.2.9所示。由異或運算的邏輯表達式可得出異或運算真值表，如表2.2.10所示。從異或運算真值表可以看出，其運算的典型特點是：輸入變量“相異”為1，“相同”為0，這也是“異或”運算名稱的含義。圖2.2.9異或門邏輯符號表2.2.10異或運算真值表異或運算的運算規(guī)則為

可推導出異或運算的一般形式有：

(2.2.6)

(2.2.7)

(2.2.8)

(2.2.9)由異或運算的定義還可以推出

(2.2.10)

(2.2.11)式(2.2.6)和式(2.2.7)表明，一邏輯變量與邏輯0相異或時可獲得原變量，而與邏輯1相異或時可獲得其反變量。如果將異或門的一個輸入端作為控制端，則可對從另一個輸入端輸入的變量進行有控制的取反，這一特點使得異或門在數字電路中有著廣泛應用。

5.同或運算

同或運算也是只有兩個輸入變量的邏輯運算，其邏輯表達式定義為

由邏輯表達式，可導出同或運算的真值表如表2.2.11所示。從真值表可以看出，同或運算的典型特點是：輸入變量“相同”為1，“相異”為0。同或運算與異或運算正好相反，因此同或運算也稱為異或非運算?！袯表2.2.11同或運算真值表同或運算的運算規(guī)則為

0⊙0=10⊙1=01⊙0=01⊙1=1

同或運算的一般運算形式有：

A⊙1=A(2.2.6′)

A⊙0=(2.2.7′)

A⊙A=1(2.2.8′)

A⊙=0(2.2.9′)因為它與異或運算相反，所以有：

(2.2.12)

(2.2.12′)

實現同或運算的電路稱為同或門，邏輯符號如圖2.2.10所示。圖2.2.10同或門邏輯符號對于與非門、或非門、與或非門、異或門和同或門，圖2.2.11也給出了國內以前沿用的邏輯符號(部頒標準，第一行)以及國外一些書籍使用的邏輯符號(美標，第二行)。圖2.2.11國內沿用和國外常用的邏輯門符號(a)與非門；(b)或非門；(c)與或非門；(d)異或門；(e)同或門2.2.3邏輯函數

1.邏輯函數的概念

與普通代數的函數概念類似，一個邏輯表達式可對應于一個邏輯函數。邏輯函數反映構成表達式的邏輯變量(自變量)與邏輯函數值(因變量)之間的邏輯關系。例如，下邊的邏輯函數F：

或簡寫為

邏輯函數可以用邏輯門電路實現。例如，邏輯函數

的實現電路如圖2.2.12所示，自變量A、B、C代表邏輯電路的輸入信號，因變量F代表邏輯電路的輸出信號。邏輯電路圖能夠反映輸入信號與輸出信號間的邏輯關系，且邏輯電路圖和函數表達式又可以方便地相互表達，因此，邏輯電路圖也可以看做是邏輯函數的一種表示方式。圖2.2.12實現的邏輯電路邏輯函數還可以用真值表表示。真值表就是以表格的形式列出邏輯函數自變量的所有取值組合以及每種取值對應的函數值。由于邏輯函數的邏輯變量只有0、1兩種取值，因此,對有n個輸入變量的邏輯函數，其取值組合共有2n種。真值表窮盡了輸入變量所有可能的取值，因此能夠唯一地表示邏輯函數。例如，函數的真值表如表2.2.12所示。表2.2.12邏輯函數的真值表

2.由真值表寫出函數表達式

對于一個用真值表描述的邏輯函數，通常要先轉化為函數表達式，然后再用邏輯電路實現。下面結合一個例子介紹由真值表寫出函數表達式的方法。

【例2.2.1】某邏輯電路有A、B、C

三個輸入信號，只有當三個輸入中出現奇數個1時，輸出F才為1，否則為0，試列出其真值表，并寫出函數表達式。

解三個輸入變量有000、001、010、011、100、101、110、111共8種取值組合，依據問題描述，可列出真值表如表2.2.13所示。表2.2.13例2.2.1的真值表

1)由真值表寫出“與-或”表達式

將每一種使函數值為1的輸入變量取值組合用邏輯

與(相乘)的形式表示，如果變量取值為1，則用原變量表示，否則用反變量表示；再將表示出的邏輯與進行邏輯或(相加)，即可得到F的“與-或”表達式。在表2.2.13所示的真值表中，使F=1的輸入信號A、B、C共有001、010、100、111四組取值組合，其邏輯與可分別表示為、、和ABC。將這些邏輯與再進行邏輯或，即得到函數F的“與-或”表達式：

因其運算特點，“與-或”表達式也稱為“積之和”式?！芭c-或”式中的每一個邏輯與稱為乘積項或與項，乘積項中的每一個變量也稱為乘積項的因子。

2)由真值表寫出“或-與”表達式

將每一種使函數F值為0的輸入變量A、B、C取

值組合用邏輯或(相加)的形式表示，如果變量取值為0，則用原變量表示，否則用反變量表示；再將表示出的邏輯或進行邏輯與(相乘)，即可得到F的“或-與”表達式。在表2.2.13所示的真值表中，使F=0的輸入信號取值組合共有000、011、101和110四組，其邏輯或分別表示為A+B+C、、和。將這些邏輯或再進行邏輯與，即得到函數F的“或-與”表達式：

“或-與”式也稱為“和之積”式，其中的每一個邏輯或稱為和項或者是或項。

3.邏輯函數的相等

從前面的介紹可以看出，同一個邏輯函數可能有不同形式的函數表達式。很多時候，需要對具有不同表達形式的邏輯函數判斷是否表示的是同一個邏輯函數，也就是邏輯函數的相等問題。下面首先介紹邏輯函數“相等”的定義。設有兩個具有相同變量的邏輯函數

F=f(A1，A2，…，An)

G=g(A1，A2，…，An)

若對于A1，A2，…，An的每一種取值組合，F和G都有相同的函數值，則稱F和G是相等的，記作F=G。

顯然，若兩函數相等，則必然有相同的真值表；反之，若兩函數的真值表相同，則它們必然相等。因此，要證明兩函數相等，可以列出它們的真值表，如果完全相同，則兩函數相等。

【例2.2.2】設，，證明：F=G。

證明列出函數F和G的真值表，如表2.2.14所示。

表2.2.14和的真值表2.2.4邏輯代數的基本定律、公式和規(guī)則

1.邏輯代數的基本定律

除了在2.2.1節(jié)和2.2.2節(jié)給出的邏輯代數一般運算形式的公式之外，依據邏輯代數基本運算規(guī)則，或通過真值表證明，還可以得出以下一些基本定律。交換律

A·B=B·A(2.2.13)

A+B=B+A(2.2.13′)

(2.2.14)

A⊙B=B⊙A(2.2.14′)結合律

(A·B)·C=A·(B·C)(2.2.15)

(A+B)+C=A+(B+C)(2.2.15′)

(2.2.16)

(A⊙B)⊙C=A⊙(B⊙C)(2.2.16′)分配律

A(B+C)=AB+AC

(2.2.17)

A+BC=(A+B)(A+C)

(2.2.17′)

(2.2.18)

A+(B⊙C)=(A+B)⊙(A+C)

(2.2.18′)

反演律(德·摩根定律)

(2.2.19)

(2.2.19′)

2.三個規(guī)則

1)代入規(guī)則

任何一個含有變量A的等式，在出現A的所有地方都代之以一個邏輯函數F，則等式仍然成立，這一規(guī)則稱為代入規(guī)則。

因為任何一個邏輯函數都和邏輯變量一樣，只有0、1兩種可能的取值，因此代入規(guī)則是正確的。有了代入規(guī)則，上述基本定律中的任一個邏輯變量都可以代之以一個邏輯函數，因此能夠擴大這些基本定律的應用范圍。

【例2.2.3】證明反演律可推廣到多個變量的情況，如：

。

證明依據反演律，可知。將出現X的地方都代之以邏輯函數B+C，則：

等式左邊=

(依據結合律)

等式右邊=

(依據結合律)因此，依據代入規(guī)則，即有

2)反演規(guī)則

對任一個邏輯函數F，如果將其表達式中的0改為1，1改為0，原變量改為反變量，反變量改為原變量，“+”改為“·”，“·”改為“+”，則可得到該邏輯函數的反函數。這

個規(guī)則稱為反演規(guī)則。

【例2.2.4】已知

求和。解

需要注意的是，在運用反演規(guī)則求邏輯函數的反函數時，必須保持原有的運算順序不變，因此需要在必要的地方加上括號，尤其是將“與”運算改為“或”運算時。

3)對偶規(guī)則

對任一個邏輯函數F，如果將其表達式中的0改為1，1改為0，“+”改為“·”，“·”改為“+”，則可得到該邏輯函數的對偶式，記為F*。

若有等式F=G，且F*和G*分別是邏輯函數F和G的對偶式，則F*=G*。這一規(guī)則稱為對偶規(guī)則。例如，設F=A(B+C)，G=AB+AC，依據式(2.2.17)，有F=G。而F*=A+BC，G*=(A+B)(A+C)，則依據對偶規(guī)則，有F*=G*，即A+BC=(A+B)(A+C)，也即式(2.2.17′)。

同樣需要注意的是，在運用對偶規(guī)則求邏輯函數的對偶式時，也必須保持原有的運算順序不變。與運用反演規(guī)則求邏輯函數的反函數不同的是，求對偶式時，不能將原變量改為反變量，也不能將反變量改為原變量。

【例2.2.5】已知

求F*。

解

從例2.2.5可以看出，若邏輯函數F的對偶式為F*，再對F*求對偶式就可得到邏輯函數F本身，也就是說，F和F*互為對偶函數。觀察邏輯代數基本公式(2.2.1)~式(2.2.19)

與式(2.2.1′)~式(2.2.19′)，可以看出，用“′”號區(qū)分的具有相同序號的公式之間，是互為對偶的等式，因此利用對偶規(guī)則，記憶這些公式時只需記住一半就可以了。

3.四個常用公式

邏輯代數中，有四個常用公式，可用于邏輯函數的化簡以及邏輯函數相等的證明。

(1)

A+AB=A(2.2.20)

證明A+AB=A(1+B)(依據分配律)

=A·1

=A

這一公式也稱為吸收律，其特點是，如果一個乘積項(AB)完全包含了另一個乘積項(A)，則包含乘積項(AB)是多余的。

(2)

(2.2.21)

證明(依據分配律)

=A·1

=A

這一公式的特點是，若兩乘積項除公共因子(A)外，剩余因子(B和)恰好互補，則可合并為只有公共因子的一項(A)。

(3)

(2.2.22)

證明(依據分配律)

=A+B

這一公式的特點是，若一個乘積項的補(A的補)恰好是另一個乘積項(

B)的因子，則含有補因子(

)的乘積項(

B)中，補因子(

)是多余的。

(4)

(2.2.23)

證明

(依據分配律)

(依據結合律)

(依據式(2.2.21))這一公式的特點是，若兩乘積項含有互補的因子(A和

)，且剩余因子(B、C)都是第三個乘積項(BC)的因子，則第三個乘積項(BC)是多余的。這一公式也可以推廣

到有多個變量的情況，如

2.2.5邏輯函數的標準形式

從前面的介紹可以看出，利用邏輯代數的基本定理、規(guī)則及公式，可以對邏輯函數表達式進行多種形式的變換。幾種常用的表達式形式包括：與-或式、或-與式、與非-與非式、或非-或非式、與或非式等。下面通過一個例子說明各種形式之間的相互轉化。例如:

(或-與式)

(與-或式)

(與非-與非式)

(或非-或非式)

(與或非式)以上表達式中，與-或式和或-與式是兩種最基本的形式，其他幾種形式都可以通過這兩種表達式變換得到。與非-與非式可以通過對與-或式兩次取非，然后利用德·摩根定律展開一層非號獲得?；蚍?或非式可以通過對或-與式兩次取非，然后利用德·摩根定律展開一層非號獲得。與或非式則是對或非-或非式中的每個或非項利用德·摩根定律展開獲得。

由于同一個邏輯函數多種不同形式的表達式不便于邏輯問題的討論，因此，下面介紹邏輯函數的標準表達式形式。

1.最小項

構成邏輯函數的乘積項中，若每個輸入變量都以原變量或反變量的形式出現，且僅出現一次，這些乘積項就稱為最小項，或稱為標準積。

例如，若邏輯函數F有A、B、C

三個輸入變量，那么ABC、、就是最小項，而AB、則不是最小項。

在最小項中，每個變量只能有原變量或反變量兩種表現形式，因此，對n個輸入變量，可以構成的最小項最多有2n個。表2.2.15給出了三個輸入變量可以形成的所有最小項。表2.2.15三變量最小項與最大項

(1)對于任意一個最小項，只有一組變量取值使得它的值為1。

將最小項的原變量取值為1，反變量取值為0，就是使其值為1的唯一取值組合。也就是說，在輸入變量的所有取值組合中，使最小項取值為1的可能性最小，這也是其名字的由來。

依據這一特性，可以利用這個使其值為1的唯一變量取值組合來標識一個最小項。例如，用010標識;用111標識ABC。在變量表示順序確定的前提下，將標識最小項的取值組合轉換為對應的十進制數，即成為最小項的編號i，并可以用mi來表示該最小項。例如m6=、m7=ABC。

(2)任意兩個最小項的乘積恒為0，即mi·mj=0(i≠j)。

(3)n個變量的所有最小項之和恒為1，即。

2.函數的“標準與-或”表示形式

“標準與-或式”也稱為“標準積之和式”，就是將邏輯函數表示成最小項之和的形式。

例如：

其中，∑m表示最小項的和，括號中的數字就是最小項的編號。

將一個非標準的與-或式轉化為標準與-或式，可以采用配項的方法補齊乘積項中沒有包含的輸入變量。

【例2.2.6】將邏輯函數

轉換為標準與-或式。解

=m15+m14+m13+m12+m9+m10

=∑m(9，10，12，13，14，15)

3.最大項與函數的“標準或-與”形式

構成邏輯函數的和項中，若每個輸入變量都以原變量或反變量的形式出現，且僅出現一次，則這些和項就稱為最大項，也稱為標準和。

例如，若邏輯函數F有A、B、C

三個輸入變量，那么A+B+C、、就是最大項，而、

則不是最大項。

同樣，對n個輸入變量，可以構成的最大項最多有2n個。表2.2.15也給出了三個輸入變量可以形成的所有最大項。依據最大項的定義，可以得出最大項有以下一些性質：

(1)對于任意一個最大項，只有一組變量取值使得它的值為0。

將最大項的原變量取值為0，反變量取值為1，就是使其值為0的唯一取值組合。也就是說，在輸入變量的所有取值組合中，使最大項取值為1的可能性最大，這也是其名字的由來。與最小項的表示方法類似，在變量表示順序確定的前提下，一個最大項可以用使該最大項取值為0的唯一變量取值組合來標識，并用Mi來表示。其中，下標i就是標識最大項的取值組合轉換成的十進制數。例如，當有A、B、C三個輸入變量時，M1=，M2=。

(2)任意兩個最大項的和恒為1，即Mi+Mj=1(i≠j)。

(3)n個變量的所有最大項之積恒為0，即。

函數的“標準或-與式”就是將邏輯函數表示成最大項之積的形式，也稱為“標準和之積式”。例如：

=M1·M2·M3·M7

=∏M(1，2，3，7)例如，利用表2.2.16所給出的真值表，可以直接寫出函數F的標準與-或式：

以及標準或-與式：

表2.2.16函數真值表與最小項和最大項按照由真值表寫出函數與-或式和或-與式的方法，出現在函數標準與-或式中的最小項代表的就是使函數值為1的變量取值組合，而出現在函數標準或-與式中的最大項代表的就是使函數值為0的變量取值組合，因此，一個邏輯函數標準與-或式中的最小項編號和函數標準或-與式中的最大項編號是互補的。由此，若已知一個邏輯函數的標準與-或式，則可以很方便地寫出它的標準或-與式，反之亦然。例如：

F(A，B，C，D)=∑m(0，2，7，8，10，12，15)

=∏M(1，3，4，5，6，9，11，13，14)

邏輯函數有繁簡不同的多種表達式形式，在用邏輯門電路實現邏輯函數時，簡化的邏輯函數可以用較少的門電路實現，邏輯門之間的連線也較少。這不但有利于降低實現電路的成本，而且可以減少功耗、增加可靠性。下面介紹代數法和卡諾圖法兩種常用的邏輯函數化簡方法，主要討論如何將一個一般的與-或式化簡為最簡與-或式。利用對偶規(guī)則，不難求出或-與式的最簡形式。2.3邏輯函數的化簡與-或式最簡的標準通常定義如下：

(1)乘積項的個數最少，意味著電路實現時所用的與門個數最少。

(2)每個乘積項的因子個數最少，即每個與門所用的輸入端個數最少。

盡管在基于EDA技術的數字系統(tǒng)設計過程中，邏輯函數的化簡和優(yōu)化通常是由綜合器自動完成的，但是掌握邏輯函數化簡的基本理論和方法有助于讀者對綜合、優(yōu)化等問題的理解，而且可以在采用傳統(tǒng)方法設計電路時簡化電路的實現。2.3.1代數法化簡邏輯函數

代數法化簡邏輯函數就是利用邏輯代數的基本定律、公式、規(guī)則等對邏輯函數表達式進行變換，通過合并、消去多余因子、消除多余項等手段，最終得到最簡的邏輯表達式。下面介紹幾種常用的化簡方法。

1)并項法

可利用公式，將兩項合并為一項，且消去一個因子B。

【例2.3.1】化簡邏輯函數為最簡與-或式。

解

(依據分配律、德·摩根定律)

=A

(利用式合并乘積項)

2)消項法

可利用公式A+AB=A或公式

消去多余的乘積項。

【例2.3.2】化簡邏輯函數

為最簡與-或式。

解

(依據交換律、結合律)

(利用式(2.2.20)消去乘積、)

【例2.3.3】化簡邏輯函數

為最簡與-或式。

解

(依據交換律、結合律)

(利用式(2.2.23)消去多余項AD)

(依據結合律)

(利用式(2.2.23)消去多余項)

3)消元法

可利用公式消去多余的因子。

【例2.3.4】化簡邏輯函數為最簡與-或式。

解

(依據分配律)

(利用式(2.2.21)消去BC中與互補的因子C)

(依據分配律)

4)配項法

為了能夠利用上面介紹的方法化簡邏輯函數，有時候需要利用公式添加一些乘積項，或反向運用公式增加一些冗余項，達到化簡的目的。

【例2.3.5】化簡邏輯函數

為最簡與-或式。

解

(依據分配律)

(依據交換律、結合律)

(利用式(2.2.21)、

式(2.2.20)合并、吸收乘積項)

【例2.3.6】化簡邏輯函數為最簡與-或式。

解

(利用式(2.2.23)增加冗余項AD)

(依據分配律)

(利用式(2.2.22)消去中與A互補的因子)

(利用式(2.2.23)消去冗余項AD)

【例2.3.7】化簡邏輯函數

為最簡與-或式。

解

(依據交換律、結合律)

(利用式(2.2.20)、式(2.2.21)合并、吸收乘積項)

(依據分配律、德·摩根定律)

(利用式(2.2.22)消去互補因子)

(利用式(2.2.23)消去冗余項)

【例2.3.8】化簡邏輯函數

為最簡與-或式。

解

(依據德·摩根定律)

(依據分配律、德·摩根定律)

(依據交換律、結合律)

(利用式(2.2.20)、式(2.2.21))

(依據分配律、德·摩根定律)

(利用式(2.2.22))

【例2.3.9】化簡邏輯函數

為最簡或-與式。

解若利用分配律展開，過程會比較繁瑣。對于或-與式，可利用對偶規(guī)則，求出邏輯函數的對偶式，運用上面介紹的方法進行化簡，化簡后再運用對偶規(guī)則，即可得到邏輯函數的最簡或-與式。邏輯函數F的最簡或-與式可通過再求F*的對偶式得到：

從上面的介紹可以看出，使用代數法化簡邏輯函數時，沒有明顯的規(guī)律。要求設計人員熟練掌握各個公式，并能靈活運用。很多時候，化簡還依賴于設計者個人的經驗，化簡的結果是否最簡有時候也難以判定。2.3.2卡諾圖法(圖解法)化簡邏輯函數

卡諾圖由多個小方格構成。n變量卡諾圖包含2n個小方格，每個小方格唯一對應變量的一種取值組合，因此相當于一個最小項。我們知道，一個邏輯函數可以用真值表唯一表示，就是列出變量所有取值組合下的函數值，即各個最小項對應的函數值。因此，卡諾圖表示邏輯函數與真值表使用的方法相同，只是具有不同的形式。卡諾圖也可看做是圖形化的真值表。用卡諾圖表示邏輯函數能夠方便地進行函數的化簡。

1.卡諾圖的畫法

卡諾圖的一個特點是：邏輯相鄰的最小項也是幾何相鄰的。所謂邏輯相鄰，就是兩個最小項中只有一個變量的取值不同。幾何相鄰就是代表最小項的小方格在卡諾圖中的位置相鄰。

為滿足這一要求，通常將邏輯變量分為兩組，每組變量按循環(huán)碼(參見2.1.3節(jié))的順序取值，兩組變量的各個取值組合分別依次排列作為行或列的取值，行列交叉繪制形成代表最小項的小方格。圖2.3.1四變量卡諾圖的一般形式以四變量(從高到低位，設為A、B、C、D)為例，四變量卡諾圖的一般形式如圖2.3.1所示。四個變量A、B、C、D分為AB和CD兩組，兩組各自按2位循環(huán)碼的順序取值，即00、01、11和10。兩組變量的各自4個取值分別作為列和行的取值，行列交叉形成16個小方格，每個小方格對應四變量的一種取值組合，代表一個最小項。在圖2.3.1所示的卡諾圖中，處于相鄰位置(幾何相鄰)的任意兩個最小項之間是邏輯相鄰的。例如，m5和m13位置相鄰，它們對應的取值組合分別是ABCD=0101和ABCD=1101，只有一個變量C的取值不同，因此它們是邏輯相鄰的?？梢钥闯?，四變量卡諾圖中，任一行或任一列中，兩個位置相鄰的最小項都是邏輯相鄰的。行或列最外側的兩個最小項也是邏輯相鄰的，如m0和m2，m3和m11等。但斜線方向上的最小項之間不屬于幾何相鄰，也不屬于邏輯相鄰，如m12和m9。兩變量和三變量卡諾圖的畫法類似。兩變量(從高到低位，設為A、B)卡諾圖的一般形式如圖2.3.2所示。變量分為A、B兩組，每組按0、1的順序取值，構成4個小方格，代表4個最小項。行或列內的兩個最小項都是邏輯相鄰的。三變量(從高到低位，設為A、B、C)卡諾圖的一般形式如圖2.3.3所示。三個變量可分為AB、C兩組或A、BC兩組，兩個變量的組按00、01、11、10的順序取值，一個變量的組按0、1的順序取值，構成8個小方格，表示8個最小項。各最小項的邏輯相鄰關系與兩變量和四變量卡諾圖類似。圖2.3.2兩變量卡諾圖的一般形式圖2.3.3三變量卡諾圖的一般形式五變量邏輯函數有32個最小項，需要畫出32個小方格。五變量(從高到低位，設為A、B、C、D、E)卡諾圖的一般形式如圖2.3.4所示。圖中變量分為ABC、DE兩組(也可以分為AB、CDE兩組)，ABC按000、001、011、010、110、111、101、100的順序取值，DE按00、01、11、10的順序取值，行列交叉構成32個小方格，表示32個最小項。在判定最小項的相鄰關系時，可以以ABC取值為010和110間的豎線作為分界線，將卡諾圖分為各包含16個最小項的兩部分。每一部分內各最小項的相鄰關系與四變量卡諾圖相同。若將卡諾圖以分界線對折，如圖2.3.5(只用編號表示最小項)所示，那么兩部分間重合的最小項邏輯相鄰，如m31和m15。圖2.3.4五變量卡諾圖的一般形式圖2.3.5五變量卡諾圖相鄰關系舉例

2.用卡諾圖表示邏輯函數

n變量的卡諾圖可以表示出任意一個n變量的邏輯函數。

用卡諾圖表示邏輯函數時，首先需要根據函數的變量個數，畫出相應的卡諾圖，然后將函數的每一種變量取值組合對應的函數值1或0填入對應的小方格。填入1的含義是：當函數的變量取值與該小方格(最小項)表示的取值相同時，函數值為1。填入1的小方格簡稱為1格。填入0的含義就是當函數的變量取值與該小方格(最小項)表示的取值相同時，函數值為0。填入0的小方格簡稱為0格。有時候，0也可以省略不填。

1)標準與-或式表示的邏輯函數

對每一個出現在邏輯函數表達式中的最小項，找到它在卡諾圖中對應的小方格，填入1，其他小方格中填入0。例如，邏輯函數F(A，B，C)=∑m(1，3，5，6)的卡諾圖如圖2.3.6所示。4個1格表示：當ABC的取值與m1，或m3，或m5，或m6表示的取值相同，也就是當ABC取值分別為001、011、101或110時，F=1，其余取值組合都使F=0。圖2.3.6F(A,B,C)=∑m(1,3,5,6)的卡諾圖

2)非標準與-或式表示的邏輯函數

對一般與-或式表示的邏輯函數，可以采用兩種方法來填卡諾圖。一種方法是將一般與-或式轉化為標準與-或式；另一種方法是使用觀察法直接填卡諾圖。下面結合一個例子進行說明。

【例2.3.10】畫出邏輯函數

的卡諾圖。

解方法一：將函數F轉換為標準與-或式，然后用上面介紹的方法填卡諾圖。即

F(A，B，C，D)=∑m(2，3，8，10，11，12，14)

函數F的卡諾圖如圖2.3.7所示。

圖2.3.7例2.3.10的卡諾圖方法二：采用觀察法。

觀察法就是通過觀察表達式，確定都有哪些取值組合能使函數值為1，則在相應的小方格中填入1，其他小方格中填入0。函數F表達式中的乘積項是一個最小項，可以確定當ABCD取值為1110時，=1，F=1。因此，可以直接在ABCD取值為1110的小方格中填入1。乘積項不是最小項，少一個變量B。只要ACD取值為100，不論B取0還是1，乘積項的值都為1，使F=1。因此，可以直接在卡諾圖中找出ACD取值為100的所有小方格，填入1。即在圖2.3.7中，將ABCD分別取值為和對應的兩個小方格填入1。同理，乘積項也不是最小項，缺少變量A和D，只要BC取值為01，而不論AD取什么值，都會使乘積項BC=1，F=1。因此，可以在卡諾圖中直接將BC取值為01的所有小方格內都填入1，即圖2.3.7中,ABCD取值為

0010(

)、0011(

)、0011(

)、1010

(

)的4個小方格。最后得到與圖2.3.7相同的卡諾圖。非與-或式表示的邏輯函數在填卡諾圖時，通常需要先將函數表達式轉換為與-或式。

如果表達式的形式是標準或-與式，那么由于邏輯函數的最大項和最小項是互補的，因此可以先表示為標準與-或式，再填圖。由標準或-與式直接填寫卡諾圖的方法將在后面介紹。

3.利用卡諾圖化簡邏輯函數

1)利用卡諾圖化簡邏輯函數的原理

卡諾圖中位置相鄰的最小項都是邏輯相鄰的。邏輯相鄰的兩個最小項之間只有一個變量取值不同，因此可以利用公式將相鄰的兩個最小項圈在一起，合并為一項，并消去一個變量。這就是利用卡諾圖化簡邏輯函數的基本方法。圖2.3.8卡諾圖化簡舉例例如，邏輯函數

F(A，B，C)=∑m(1，2，5，6)

函數F利用卡諾圖的化簡過程如圖2.3.8所示。圖中，相鄰最小項和、和分別被圈在一起，每個圈內的兩個最小項合并后形成了一個乘積項，且能消去一個變量。觀察圖2.3.8中每個圈內的最小項以及合并后的乘積項可以發(fā)現，合并后的乘積項中保留下來的變量就是圈內最小項之間取值沒有變化的變量，而取值變化了的變量則被消去。如在圈①中，變量B、C在兩個最小項中的取值都是10，沒有變化，A的取值發(fā)生了變化，由0→1，因此合并后的乘積項是關于變量B、C的乘積項，A被消去。其次，若圈內取值沒有變化的變量，在圈內各個最小項中的取值都為0，則在合并后的乘積項中以反變量的形式表示；否則，以原變量的形式表示。例如，在圖2.3.8中，變量B在圈①內的兩個最小項中都取值為1，變量C在兩個最小項中都取值為0，所以在合并后的乘積項中，B以原變量的形式表示，而C以反變量的形式表示?？偨Y前面的分析，利用卡諾圖化簡邏輯函數為最簡與-或式的過程是：首先畫出邏輯函數的卡諾圖，然后對卡諾圖中的相鄰1格進行圈組合并(消去圈中取值變化了的變量)，寫出每個圈組合并后的乘積項(變量取值為0，用反變量表示；取值為1，用原變量表示)，表示為與-或式，即得到函數的最簡與-或形式。

2)利用卡諾圖合并最小項的規(guī)律

下面，將利用卡諾圖合并最小項的一些規(guī)律總結如下：

(1)兩個相鄰最小項合并，消去一個變量，形成一個乘積項。

(2)四個相鄰最小項合并，消去兩個變量，形成一個乘積項。如圖2.3.9(a)所示，四個相互相鄰的乘積項如果兩兩圈組合并(和合并，和合并)，那么所得的兩個乘積項(和)仍然邏輯相鄰，可以繼續(xù)合并成為一個乘積項(

)，從而消去了在圈中取值變化的兩個變量A、B，保留了取值沒有變化的變量C。由于C在四個相鄰最小項中都取值為0，因此合并后表示為。圖2.3.9給出了三變量和四變量卡諾圖中四個相鄰項合并的一些例子。圖2.3.9四個相鄰項合并舉例

(3)八個相鄰最小項合并，消去三個變量，形成一個乘積項。

圖2.3.10給出了四變量卡諾圖中八個相鄰項合并的一些例子。圖2.3.10八個相鄰項合并舉例

3)用卡諾圖化簡邏輯函數

從上面的分析可以看出，用卡諾圖化簡邏輯函數的關鍵就是正確的圈組。

利用卡諾圖圈“1”化簡時，應遵循如下的圈組原則：

(1)卡諾圖中所有的1格都被至少圈過一次(可以圈多次)。

(2)每個圈只能圈1，2，4，…，2i，…個1格。圖2.3.11主要項舉例

(3)圈要盡可能得大，圈的個數要盡可能得少。圈越大，就能將更多的最小項合并，且合并后的乘積項包含的變量越少；圈的個數越少，合并后的乘積項個數就越少。圈盡可能大就是指：如果再擴大圈，圈內將包含0格。盡可能大的圈合并出的乘積項稱為主要項。例如，圖2.3.11所示的卡諾圖，合并出乘積項的圈不滿足盡可能大的要求，因此不是一個主要項，只有將圖中的四個1格都圈組合并，形成的乘積項才是一個主要項。

(4)主要項圈中至少要有一個1格沒有被其他圈圈過。滿足這一要求的圈合并出的乘積項稱為必要項，邏輯函數的最簡表達式必須都由必要項組成。如果某個圈中所有的1格都曾被其他圈圈過，那么，由這個圈合并后的乘積項將是一個多余項。例如，對邏輯函數F(A，B，C)=∑m(0，2，3，7)按圖2.3.12(a)、(b)、(c)所示的過程圈組合并，合并出乘積項的圈中，兩個1格都被其他圈圈過，因此合并出的乘積項是一個多余項。圖2.3.12多余項舉例為避免上述問題，利用卡諾圖化簡邏輯函數為最簡與-或式時一般采用如下的步驟：

(1)畫出邏輯函數的卡諾圖。

(2)先圈孤立(沒有相鄰項)的1格。

(3)然后圈只有1種圈法的1格。

(4)余下的1格都有多種圈法，選擇其中的一種方法進行圈組，直至所有的1格都被圈過。

(5)由圈組寫出最簡與-或式。

【例2.3.11】用卡諾圖化簡邏輯函數F(A，B，C，D)=∑m(1，3，4，5，7，9，10，13，15)為最簡與-或式。

解第一步，畫出F的卡諾圖，如圖2.3.13(a)所示。為方便敘述，圖2.3.13中的1格用最小項的編號代替表示。

第二步，圈孤立的1格。圖2.3.13(a)中，只有m10是沒有相鄰項的孤立1格，圈組后如圖2.3.13(b)所示。第三步，圈組只有一種圈法的1格。圖2.3.13(b)中，m4只有一種圈法，就是(m4，m5)圈組合并。m9只有一種圈法，從m9開始，將(m9，m13，m5，m1)圈在一起。余下的m3、m7、m15中，m3和m15都只有一種圈法，從m3開始，將(m3，m7，m1，m5)圈在一起；從m15出發(fā)，將(m15，m7，m5，m13)圈在一起，如圖2.3.13(c)所示